[영지식증명] GKR protocol 파헤치기

안녕하세요, 오늘은 지난번 Sum-Check protocol에 이어 GKR protocol에 대하여 알아보도록 하겠습니다. 

이번 글은 Thaler 교수님의 A Note on the GKR Protocol을 바탕으로 작성되었습니다.

Sum-Check Protocol 복습

GKR protocol은 Sum-Check protocol을 활용해 주어진 circuit을 증명해내는 방법입니다. 따라서 우선 Sum-Check Protocol에 대하여 다시 한번 복습해 봅시다. 우선 우리에게 finite field $\mathbf{F}$ 에서 $v$ variate polynomial $g(\cdot)$ 이 주어졌다고 가정해 봅시다. Sum-Check protocol의 목적은 아래 식을 verifier에게 증명하는 것입니다. 

$H := \sum_{b_1 \in \{0, 1\}} \sum_{b_2 \in \{0, 1\}} \dots \sum_{b_v \in \{0, 1\}} g(b_1, \dots, b_v)$

 

해당 식을 검증하기 앞서 우리는 verifier가 임의의 $(r_1, \dots, r_v) \in \mathbf{F}^v$ 에서의 $g(r_1, \dots, r_v)$를 계산할 수 있다고 가정했습니다. Sum-Check protocol은 $v$ 번의 라운드를 거치게 되는데요, 매 라운드마다 prover는 $g_j(X_j) = \sum_{(x_{j+1}, \dots, x_v) \in \{0, 1\}^{v-j}} g(r_1, \dots, r_{j-1}, X_j, x_{j+1}, \dots, x_v)$임을 claim 하게 됩니다. 

만약 prover의 claim이 맞다면, $g_{j-1}(r_{j-1}) = g_j(0) + g_j(1)$의 식이 성립해야하고, verifier는 이것을 확인하게 됩니다. 

 

모든 라운드가 마무리되면, 결국 prover는 $g(r_1, \dots, r_v)$ 값을 verifier에게 전달하게 됩니다. 앞선 가정에 의해 verifier는 해당 값을 직접 계산할 수 있고, 이것을 prover의 claim 과 비교하여 일치하다면, prover의 claim을 받아들이게 됩니다.

 

GKR protocol setting

이제 GKR protocol의 세팅에 대하여 알아보도록 하겠습니다. 이번에 prover가 증명하고자 하는 arithmetic circuit을 $\mathbf{C}$라고 하겠습니다. 해당 circuit은 덧셈과 곱셉 두 가지 연산을 진행할 수 있는 게이트로 이루어져 있습니다. 또한 각 게이트는 2개의 인풋을 받습니다. 또한 해당 circuit $\mathbf{C}$는 각 layer 별로 분해할 수 있다는 가정이 이루어집니다. 각 Circuit의 layer에 속한 게이트들은 adjacent한 layer들과만 연결되어 있습니다. 

 

Protocol의 시작은, prover가 verifier에게 해당 circuit의 output을 claim 하면서 시작됩니다. 증명은 가장 위에 있는 (output과 가까운) layer에서 시작하여 input이 들어오는 layer에서 마무리되게 됩니다. 이제 뒤에서 설명드리겠지만, 각 layer마다 Sum-Check protocol을 활용해 증명이 이루어지고, 결국 verifier는 자신이 직접 circuit계산을 하지 않고도 prover의 claim을 받아들일 수 있게 됩니다. 

 

우선 circuit $\mathbf{C}$ 의 size를 $S(n)$, depth를 $d(n)$, $i$ 번째 layer의 게이트 갯수를 $S_i$라고 하겠습니다. 또한 $S_i = w^{si}$라고 하겠습니다. 이제 각 layer에서의 게이트에 $0$번에서부터 $S_i - 1$까지의 숫자로 주석을 달아주도록 하겠습니다. 그렇다면 우리는 $W_i: \{0, 1\}^{s_i} \rightarrow \mathbf{F}$ 함수를 통해 각 게이트의 binary label을 받아 해당 게이트의 값을 내뱉어주는 함수를 정의할 수 있습니다. 

 

이번에는 각 게이트를 연결시키는 와이어를 수식으로 나타내어보도록 하겠습니다. Layer i 에서 우리는 두개의 함수 $add_i, mult_i$를 정의하겠습니다. 해당 함수들은 $\{0, 1\}^{s_i + 2s_{i+1}}$ 의 binary label를 input으로 받게 됩니다. 또한 해당 함수는 만약 인풋 $(j_1, j_2, j_3)$에 대하여 layer $i$에서의 $j_1$ 게이트가 만약 layer $i+1$에서의 $j_2, j_3$를 인풋으로 받는다면 $1$의 값을, 그렇지 않다면 $0$의 값을 가지게 됩니다.

 

이제 우리는 $\beta_{s_i}(z, p) = \prod{j=1}{s_i}((1-z_j)(1-p_j) + z_jp_j)$를 정의해주도록 하겠습니다. 해당 함수는 함수 $B(x, y): \{0, 1\}^{s_i} \times \{0, 1\}^{s_i} \rightarrow \{0, 1\}$가 있을 때, $x = y$인경우만 $1$을 값을 갖고 나머지 값들에서는 $0$의 값을 갖는 $B$의 multilinear extension임을 쉽게 확인할 수 있습니다. 

 

GKR protocol

이제 본격적으로 각 layer에서 prover가 무엇을 증명하는지 알아보도록 하겠습니다. 각 layer $i$의 한 게이트를 나타내는 $z \in \mathbf{F}^{s_i}$에 대하여 $W_i(z) = \sum_{(p, \omega_1, \omega_2) \in \{0, 1\}^{s_i + 2s_{i+1}}}f^{i}(p, \omega_1, \omega_2)$ 가 성립합니다. 여기서 $f$는 아래와 같습니다.  

$f^i(p, \omega_1, \omega_2) = \beta_{s_i}(z, p) \cdot (add_i(p, \omega_1, \omega_2)(W_{i+1}(\omega1) + W_{i+1}(\omega_2)) + mult_i(p, \omega_1, \omega_2) (W_{i+1}(\omega_1) + W_{i+1}(\omega_2))$

 

수식을 잘 살펴보면, $W_i(z)$의 경우 이미 정의된 $add, mult$함수, 그리고 $\beta$함수에 의해 $i+1$ 게이트에서 실제로 받아오는 연산만을 계산하게 됩니다. 즉, GKR protocol은 해당 $f$ 함수에 Sum-Check protocol을 적용함으로 layer i 에서의 증명을 layer i+1 에서의 증명으로 내릴 수 있게 됩니다. 즉 layer i 에서 $s_i + 2s_{i+1}$의 Sum-Check protocol 라운드를 진행하게 됩니다. 

 

또한 마지막 layer가 인풋임을 감안하면, 증명자는 circuit을 직접 계산하지 않고도, 올바른 계산을 통해 prover의 claim 이 옳은지 옳지 않은지 확인할 수 있습니다. 

 

Refinement

조금 더 나아가 보자면, 우리는 GKR protocol을 조금 수정함으로 각 layer에서의 연산을 $2s_i$로 줄일 수 있습니다. 이 수정은 이전에 사용하던 $\beta$함수를 사용하지 않고, $(\omega_1, \omega_2) \in \{0, 1\}^{2s_{i+1}}$ 만 덧셈 summation을 돌아도 이전처럼 올바른 $W_i(z)$값을 계산할 수 있다는 사실에서 기인합니다. 즉, 우리는 다음과 같이 다시 수식을 써볼 수 있습니다. 

$W_i(z) = \sum_{(\omega_1, \omega_2) \in \{0, 1\}^{2s_{i+1}}}g^{i}(\omega_1, \omega_2)$

이 경우, $g$는 다음과 같이 정의됩니다.

$g^i(\omega_1, \omega_2) = add_i(z, \omega_1, \omega_2)(W_{i+1}(\omega1) + W_{i+1}(\omega_2)) + mult_i(z, \omega_1, \omega_2) (W_{i+1}(\omega_1) + W_{i+1}(\omega_2)$

저는 새롭게 정의된 $W_i(z)$의 값이 이전과 같다는 사실을 증명하지는 않겠지만, 궁금하시다면 Thaler 교수님의 렉쳐노트에 증명또한 포함되어 있습니다.

Conclusion

오늘은 Sum-Check protocol을 활용해 arithmetic circuit을 증명할 수 있는 GKR protocol에 대하여 알아보았습니다. 

다음 시간에는 GKR protocol의 implementation에 대하여 살펴보는 시간을 갖도록 하겠습니다.