GKR Protocol

본 글에서는 Field 위에서 덧셈과 곱셈 연산을 수행하는 arithmetic circuit의 결과를 증명하는 IP인, GKR 프로토콜에 대해 알아보겠습니다.

Settings

유한체 $\mathbb F$ 위에서 정의된 fan-in이 2인 arithmetic circuit $\mathcal C$ 를 고려하겠습니다. (Circuit 의 정의는 지난 블로그를 참고하세요.) GKR 프로토콜의 목표는 $\mathcal P$가 $\mathcal V$에게 'input $x\in\{0,1\}^n$ 가 $\mathcal C(x)=y$ 를 만족시킨다'는 것을 증명하는 것입니다.

먼저 $\mathcal C$가 log-space uniform 하다는 조건이 필요한데, 이는 임의의 게이트를 입력으로 받았을 때 그 neighbors와 게이트 종류 등 정보를 구할 수 있는 log-space 알고리즘이 존재한다는 가정입니다. 또한 $\mathcal C$가 input layer $d$ 부터 output layer $0$ 까지 depth $d$ 로 layered 되어있다고 가정합니다. (그렇지 않을경우 더미 게이트를 추가하여 크기가 $d$ 배인 layered circuit으로 만들 수 있습니다.)

이제 $\mathcal C$의 크기 (게이트 개수)를 $S$, depth를 $d$, 변수 개수를 $n$ 이라고 하겠습니다. 각 layer $i$가 $S_i=2^{k_i}$ 개의 게이트로 이루어져 있다고 가정하고, layer $i$ 의 게이트를 $0$부터 $S_i-1$ 까지 라벨을 붙이겠습니다. 그리고 $W_i: \{0,1\}^{k_i}\to\mathbb F$ 를 layer $i$에서 라벨을 입력으로 받아 해당 게이트의 값을 반환하는 함수로 정의하겠습니다. 또한 layer $i$의 게이트 $a$에 대해 $a$와 연결된 layer $i+1$의 두 게이트를 $\text{in}_{1,i}(a), \text{in}_{2,i}(a)$ 라고 하겠습니다. 그러면 $\text{add}_i, \text{mult}_i: \{0,1\}^{k_i+2k_{i+1}}\to \{0,1\}$ 함수를 입력 $(a,b,c)$에 대해 $(b,c)=(\text{in}_{1,i}(a), \text{in}_{2,i}(a))$ 이고 게이트 $a$가 ADD (후자에 대해선 MULT) 일 때만 $1$, 이외는 $0$을 가지는 indicator function으로 정의할 수 있습니다.

Details

GKR 프로토콜에서 우리는 Sum-check를 활용하기 위해, $\tilde W_i$ ($W_i$의 multilinear extension) 를 다음과 같은 합의 꼴으로 나타낼 것입니다:

Lemma 4.2.

$$\widetilde{W}_i(z) = \sum_{b, c \in \{0,1\}^{k_{i+1}}} \widetilde{\operatorname{add}}_i(z, b, c) \bigl(\widetilde{W}_{i+1}(b) + \widetilde{W}_{i+1}(c)\bigr) + \widetilde{\operatorname{mult}}_i(z, b, c) \bigl(\widetilde{W}_{i+1}(b) \cdot \widetilde{W}_{i+1}(c)\bigr)$$

Proof. 변수 $z$에 대해 우변은 multilinear 다항식들의 합이므로 양변이 모두 multilinear 함은 자명합니다. MLE 다항식의 유일성에 의해, 양변이 모든 $z\in\{0,1\}^{k_i}$ 에 대해 값이 같다는 것만 보이면 증명이 끝납니다. 임의의 ADD 게이트 $a\in\{0,1\}^{k_i}$ 는 오직 두 개의 자식 $\text{in}_{1,i}(a), \text{in}_{2,i}(a)$ 만을 가지므로, 위 합은 $(b,c)=(\text{in}_{1,i}(a), \text{in}_{2,i}(a))$ 에서만 살아남고 다른 모든 $b, c \in \{0,1\}^{k_{i+1}}$ 에서는 0이 되어 사라집니다. 즉,

$$\sum_{b,c \in \{0,1\}^{k_{i+1}}} \widetilde{\operatorname{add}}_i(a,b,c) \big( \widetilde{W}_{i+1}(b) + \widetilde{W}_{i+1}(c) \big) + \widetilde{\operatorname{mult}}_i(a,b,c) \big( \widetilde{W}_{i+1}(b) \cdot \widetilde{W}_{i+1}(c) \big)$$

$$= \widetilde{W}_{i+1}\big(\operatorname{in}_1(a)\big) + \widetilde{W}_{i+1}\big(\operatorname{in}_2(a)\big) = W_{i+1}\big(\operatorname{in}_1(a)\big) + W_{i+1}\big(\operatorname{in}_2(a)\big) = W_i(a) = \widetilde{W}_i(a).$$

이는 MULT 게이트에 대해서도 성립합니다. $\square$

처음으로 돌아가 우리는 circuit $\mathcal C$의 output layer $0$에서 $W_0(z)$ 값을 증명해야 합니다. 그러나 이를 위해 모든 $z\in\{0,1\}^{k_0}$의 함숫값을 검증하는 것이 아니라, 임의의 $z=r_0\in\mathbb F^{k_0}$ 에 대해 Lemma 4.2가 성립하는지 한번 검증하는 것으로 충분합니다! (이 방법이 sound한 이유는 Schwartz-Zippel Lemma 덕분입니다.)

이제 우리는 고정된 $r_i\in\mathbb F^{k_i}$에 대해 합 내부의 함수

$$f_{r_i}^{(i)}(b, c) := \widetilde{\operatorname{add}}_i(r_i, b, c) \big( \widetilde{W}_{i+1}(b) + \widetilde{W}_{i+1}(c) \big) + \widetilde{\operatorname{mult}}_i(r_i, b, c) \big( \widetilde{W}_{i+1}(b) \cdot \widetilde{W}_{i+1}(c) \big).$$

에 Sum-check 프로토콜을 적용함으로써 $\tilde W_i(r_i)$ 값을 증명할 수 있습니다. 그러나 Sum-check 프로토콜의 마지막 라운드에서 $\mathcal V$는 임의의 $b^*,c^*\in\mathbb F^{k_{i+1}}$에 대해 $f_{r_i}^{(i)}(b^* , c^* )$ 를 구해야하므로 $\tilde W_{i+1}(b^* )$와 $\tilde W_{i+1}(c^* )$ 값을 필요로 하는데, 이 값들을 $\mathcal P$ 에게 요청합니다. 이때 이 두 값에 대한 증명도 필요하게 됩니다. 즉, layer $i$에 대한 결과값 증명이 sum-check를 적용하면서 layer $i+1$에 대한 두 개의 증명으로 환원된 것입니다!

Reducing Two Polynomial Evaluations to One

더 나아가, 우리는 $\tilde W_{i+1}$ 에 대한 두 점에서의 증명을 오직 한 점에서의 증명으로 줄일 수 있습니다. 그 과정은 다음과 같습니다:

Subroutine Protocol: $\ell: \mathbb F\to \mathbb F^{k_{i+1}}$ 을 $\ell(0)=b^*$, $\ell(1)=c^*$으로 두 점을 지나는 (유일한) 직선으로 정의합니다. 이제 $\tilde W$의 $\ell$ 위의 restriction $q(x)=(\tilde W\circ \ell)(x)$ 를 고려하겠습니다. 그러면 $q(x)$는 $q(0)=\tilde W(b^* )$, $q(1)=\tilde W(c^* )$ 를 만족하는 일변수 다항식이며, $\tilde W$가 multilinear 하므로 최대 차수는 $\tilde W$의 변수 개수인 $k_{i+1}$ 입니다. Verifier $\mathcal V$는 임의의 $r^* \in\mathbb F$를 뽑아 $q(r^* )=(\tilde W\circ \ell)(r^* )$ 만을 검증합니다.

위 과정이 complete함은 자명합니다. 또한 soundness error $k_{i+1}/|\mathbb F|$ 으로 sound한데, 그 이유는 $q(x)$ 의 차수가 최대 $k_{i+1}$이므로 false $q$가 임의의 점에서 $q(r^* )=(\tilde W\circ \ell)(r^* )$ 를 만족할 확률은 최대 $k_{i+1}/|\mathbb F|$ 이기 때문입니다. (Schwartz-Zippel Lemma)

Final iteration

위 방법을 이용하면 우리는 layer $i$에 대한 증명을 Sum-check + layer $i+1$에 대한 증명 으로 환원시킬 수 있습니다. 이를 반복한 뒤 마지막 layer $d$ 에서 $\mathcal V$는 $\tilde W_d(r_d)$ 값을 직접 계산해야합니다. 이 때 layer $d$는 input layer이므로 모두 공개되어있고, $\mathcal V$는 MLE 함숫값 구하기 를 통해 $O(n)$ 시간에 해당 값을 직접 계산할 수 있습니다.

이제 모든 것을 종합한 GKR 프로토콜을 살펴보겠습니다.

Protocol

1

프로토콜 시작 시, $\mathcal P$는 $W_0$ (출력 게이트 라벨을 출력값에 매핑하는 함수)와 같다고 주장하는 $D: \{0, 1\}^{k_0} \to \mathbb{F}$를 보냅니다.

2

$\mathcal V$는 임의의 $r_0 \in \mathbb{F}^{k_0}$ 를 선택하고 $m_0 \leftarrow \tilde{D}(r_0)$로 설정합니다. 이제 $m_0 = \tilde{W}_0(r_0)$ 가 참이라는 것을 재귀적으로 증명합니다.

3

$i$-th iteration ($0 \leq i < d$)

claim: $\sum_{b, c \in \{0, 1\}^{k_{i+1}}} f_{r_i}^{(i)}(b, c) = m_i.$

이 때 $(2k_{i+1})$-변수 다항식 $f_{r_i}^{(i)}$ 를 다음과 같이 정의합니다:

$$f_{r_i}^{(i)}(b, c) := \widetilde{\operatorname{add}}_i(r_i, b, c) \left( \tilde{W}_{i+1}(b) + \tilde{W}_{i+1}(c) \right) + \widetilde{\operatorname{mult}}_i(r_i, b, c) \left( \tilde{W}_{i+1}(b) \cdot \tilde{W}_{i+1}(c) \right).$$

$\mathcal P$는 $\mathcal V$에게 claim을 Sum-check 프로토콜을 이용해 증명합니다. Sum-check의 마지막에서 $(b^*, c^*) \in \mathbb{F}^{k_{i+1}} \times \mathbb{F}^{k_{i+1}}$에서 $f_{r_i}^{(i)}$ 값을 구해야 할 때까지 진행합니다.

$\ell(0) = b^*$와 $\ell(1) = c^*$를 만족하는 직선 $\ell$ 을 정의한 뒤, $\mathcal P$가 $\mathcal V$에게 $q(x)=(\tilde W_{i+1}\circ \ell)(x)$ 라고 주장하는 $q$를 보냅니다. ($q$는 차수는 최대 $k_{i+1}$인 일변수 다항식) $\mathcal V$는 $\tilde{W}_{i+1}(b^* )$ 와 $\tilde{W}_{i+1}(c^* )$ 대신 $q(0)$와 $q(1)$ 값을 사용해 $f_{r_i}^{(i)}(b^* , c^* )$ 를 계산하여 Sum-check를 마칩니다.

이제 $q=\tilde W_{i+1}\circ \ell$ 라는 주장을 검증해야 합니다. 이를 위해 $\mathcal V$가 임의의 $r^* \in \mathbb{F}$를 뽑아 $r_{i+1} = \ell(r^*)$ 및 $m_{i+1} \leftarrow q(r^*)$ 로 설정한 뒤, 다음 iteration에서 $m_{i+1}$ 에 대한 claim을 검증합니다.

4

$d$-th iteration (final)

마지막으로 $\mathcal V$는 $m_d = \tilde{W}_d(r_d)$임을 직접 확인합니다. Circuit의 input $x$를 $\{0, 1\}^{\log n} \to \mathbb{F}$, input layer에서 라벨을 입력으로 받아 그 값을 출력하는 함수로 해석하면, $\tilde W_d$ 는 $x$의 MLE $\tilde x$가 되고 이는 $\mathcal V$가 직접 계산 가능합니다.

Costs

Communication costs & Rounds: $f_{r_i}^{(i)}$ 는 $(2k_{i+1})$-변수 다항식이며 각 변수에 대한 차수가 최대 2입니다. 따라서 $i$번째 iteration의 Sum-check 프로토콜에 필요한 communication은 $2k_{i+1}=O(\log S)$ 이고, 전체 cost는 프로토콜의 시작 때 $D$를 전송하는데 필요한 $S_0$를 포함해 $O(S_0+d\log S)$ field elements 입니다. 또한 전체 라운드 수는 $O(d\log S)$ 입니다.

Soundness error: GKR의 $i$번째 iteration에서 검증하는 $q(x)$는 차수가 최대 $k_{i+1}=O(\log S)$ 이므로 false $q$가 증명을 통과할 확률은 최대 $O(\log S/|\mathbb F|)$ 입니다. 이를 $d$번 반복하므로 적어도 한번 통과할 확률은 최대 $O(d\log S/|\mathbb F|)$ 이고 이것이 곧 GKR 프로토콜의 Soundness error입니다.

$\mathcal V$의 시간복잡도: $\mathcal V$의 시간복잡도는 $O(n+d\log S+t+S_0)$ 로, 마지막 iteration에서 $\tilde{W}_d(r_d)$를 계산하는데 $O(n)$, 각각의 sum-check 프로토콜에서 총 $O(d\log S)$, $\widetilde{\operatorname{add}}_i$ 와 $\widetilde{\operatorname{mult}}_i$ 를 랜덤 input에서 계산하는 시간 $t$, 맨 처음 $\tilde{D}(r_0)$ 를 계산하는 시간 $O(S_0)$ 이 소요됩니다. 뒤에서 살펴볼 것이지만 $t$를 low-order으로 가정하고 $S_0=1$로 놓으면 총 시간복잡도는 $O(n+d\log S)$ 입니다.

$\mathcal P$의 시간복잡도: MatMult 프로토콜에서 사용했던 아이디어를 사용한 두 개의 최적화 방법을 살펴보겠습니다.

Method 1, $O(S^3)$

Sum-check를 적용하는 $f_{r_i}^{(i)}$는 $v=2k_{i+1}$-변수 다항식이며 각 변수에 대한 차수가 최대 2라는 것을 확인할 수 있습니다. 따라서 MatMult와 동일하게 각 라운드 $k$에서 다음 꼴의

$$(s_{1}, \ldots, s_{k-1}, \{0,1,2\}, b_{k+1}, \ldots, b_{v}) : (b_{k+1}, \ldots, b_{v}) \in \{0,1\}^{v - k}$$

총 $3\cdot 2^{v-k}$ 개 점에서 함숫값만 구하면 됩니다. 임의의 점에서 $f_{r_i}^{(i)}$의 함숫값을 구하는 것은 MLE 함숫값 구하기 테크닉으로 $O(S_i+S_{i+1})$ 시간에 가능하고, 따라서 전체 시간복잡도는 $O(\sum_{i=0}^{d-1}2^v\cdot (S_i+S_{i+1}))=O(S^3)$ 으로 정리됩니다.

Method 2, $O(S\log{S})$

먼저 $f_{r_i}^{(i)}$의 정의를 관찰해보겠습니다.

$$f_{r_i}^{(i)}(b, c) := \widetilde{\operatorname{add}}_i(r_i, b, c) \left( \tilde{W}_{i+1}(b) + \tilde{W}_{i+1}(c) \right) + \widetilde{\operatorname{mult}}_i(r_i, b, c) \left( \tilde{W}_{i+1}(b) \cdot \tilde{W}_{i+1}(c) \right).$$

우리는 모든 $k$에 대해 $(s_{1}, \ldots, s_{k-1}, \{0,1,2\}, b_{k+1}, \ldots, b_{v})$ 꼴의 $3\cdot 2^{v-k}$ 개 점에서, 각 multilinear 함수들 $\widetilde{\operatorname{add}}_i$, $\widetilde{\operatorname{mult}}_i$, $\tilde{W}_{i+1}$ 의 함숫값을 계산하면 상수 시간에 $f_{r_i}^{(i)}$를 구할 수 있습니다. 이를 위해 MatMult 프로토콜의 Method 3에서 사용했던 점화식을 활용하겠습니다. $v$-변수 multilinear 다항식 $\tilde g$에 대해, 다음 점화식으로 이전 라운드의 함숫값을 이용해 현재 라운드의 함숫값을 모두 계산할 수 있습니다.

$$\begin{align*} \tilde g(s_{1}, \ldots, s_{k-1}, \{0,1\}, x_{k+1}, \ldots, x_{v}) &= s_{k-1} \cdot \tilde g(s_{1}, \ldots, s_{k-2}, 1, \{0,1\}, x_{k+1}, \ldots, x_{v}) \\ &\qquad + (1 - s_{k-1}) \cdot \tilde g(s_{1}, \ldots, s_{k-2}, 0, \{0,1\}, x_{k+1}, \ldots, x_{v}) \\ \\ \tilde g(s_{1}, \ldots, s_{k-1}, 2, x_{k+1}, \ldots, x_{v}) &= 2 \cdot \tilde g(s_{1}, \ldots, s_{k-1}, 1, x_{k+1}, \ldots, x_{v}) \\ &\qquad - 1 \cdot \tilde g(s_{1}, \ldots, s_{k-1}, 0, x_{k+1}, \ldots, x_{v}). \end{align*}$$

즉, 어떤 multilinear 다항식 $\tilde g$ 의 $\forall x\in\{0,1\}^v$ 에서 함숫값을 계산해두면, 그것을 초기값으로 DP를 이용해 $O(2^v)$ 시간에 필요한 모든 함숫값을 구할 수 있습니다.

먼저 $\tilde{W}_{i+1}$ 에 대해서는 간단합니다. 초기값은 layer $i+1$의 값들이므로 알고있고, 변수 개수는 $v=k_{i+1}$ 이므로 $O(2^{k_{i+1}})=O(S_{i+1})$ 시간이 걸립니다. 이제 $\widetilde{\operatorname{add}}_i$ 를 살펴보겠습니다. ($\widetilde{\operatorname{mult}}_i$ 도 동일합니다.) $\widetilde{\operatorname{add}}_i$ 는 변수 개수가 $v=2k_{i+1}$ 이므로 naive 하게 작성하면 $O(S_{i+1}^2)$ 시간이 들게됩니다. 이를 보완하기 위해 MatMult 프로토콜의 Method 2의 관찰을 활용해보겠습니다.

관찰. $\operatorname{add}_i$와 $\operatorname{mult}_i$는 sparse 합니다; $(a, \text{in}_{1,i}(a), \text{in}_{2,i}(a)): a \in \{0,1\}^{k_i}$ 꼴의 점 $S_i$ 개를 제외한 모든 점에서 $\operatorname{add}_i(a,b,c)=\operatorname{mult}_i(a,b,c)=0$ 입니다.

따라서, $\operatorname{add}_i$ 의 MLE는 다음과 같이 $a \in \{0,1\}^{k_i}$ 에 대한 합으로 표현할 수 있습니다:

$$\widetilde{\operatorname{add}}_i(r_i, z) = \sum_{a \in \{0,1\}^{k_i}} \chi_{(a, \operatorname{in}_{1,i}(a), \operatorname{in}_{2,i}(a))}(r_i, z) = \sum_{a \in \{0,1\}^{k_i}} \chi_a(r_i)\chi_{(\operatorname{in}_{1,i}(a), \operatorname{in}_{2,i}(a))}(z),$$

이제 모든 $a \in \{0,1\}^{k_i}$ 에 대해 $\chi_a(r_i)$ 값을 pre-compute 한 뒤 (이는 $O(2^{k_i})=O(S_i)$ 시간이 걸립니다), $a$에 대해 iterate 하면서 $(\operatorname{in}_{1,i}(a), \operatorname{in}_{2,i}(a))=z$ 인 $z\in\{0,1\}^{2k_{i+1}}$ 에 대해서만 값을 업데이트 해줍니다:

$$\widetilde{\operatorname{add}}_i(z) \leftarrow \widetilde{\operatorname{add}}_i(z) + \chi_a(r_i)\chi_{(\operatorname{in}_{1,i}(a), \operatorname{in}_{2,i}(a))}(z).$$

이 때 고정된 $z_0\in\{0,1\}^{2k_{i+1}}$에 대해, 앞서 살펴본 점화식을 이용하면 모든 라운드 $1\leq k< v=2k_{i+1}$에서 마지막 $v-k$ 비트가 $z_0$ 와 겹치는 $z$의 함숫값을 모두 구할 수 있습니다. 이 과정은 총 $O(2^{k_i}\cdot 2k_{i+1})=O(S_i\log{S_{i+1}})$ 시간이 소요됩니다.

종합하면, $i$번째 iteration에서 총 $O(S_{i+1}+S_i\log{S_{i+1}})$ 시간이 걸리므로 전체 시간복잡도는

$$O(\sum_{i=0}^{d-1}\left (S_{i+1}+S_i\log{S_{i+1}}\right ))=O(\sum_{i=0}^{d-1} S_{i+1}+\log S\sum_{i=0}^{d-1} S_i)=O(S\log S)$$

입니다.

Linear time prover, $O(S)$

더 나아가 $\mathcal P$의 시간을 $O(S)$로 linear하게 줄이는 것도 가능합니다. 다음 논문을 참고하세요. [XZZ+19]

---

GKR의 Cost를 정리하면 다음과 같습니다.

Communication	Rounds	$\mathcal{V}$ time	$\mathcal{P}$ time	Soundness error
$O(d\log S)$ field elements	$d\log S$	$O(n+d\log S)$	$O(S\log S)$	$O(d\log S/\|\mathbb F\|)$

표 4.5. GKR 프로토콜의 costs. Prove time은 구현에 따라 $O(S)$ 까지 줄일 수 있다.

Conclusion

이번에 살펴본 GKR 프로토콜은 1장에서 살펴본 VC (Verifiable Computation)의 한 예시입니다. GKR이 유용한 이유는 우리가 계산하는 많은 알고리즘은 arithmetic circuit으로 변환될 수 있고, 따라서 이들을 증명할 수 있게되기 때문입니다. 또한, GKR은 parallel computation에 강점이 있어 더욱 효율적으로 구현할 수 있습니다.

다음 글에서는 임의의 IP를 Non-interactive Proof로 변환하는 기술인 Fiat-Shamir Transform에 대해 알아보겠습니다. 감사합니다.