Sum-Check Protocol and Applications
Introduction
최근 개인적인 사정으로 공부를 제대로 못하다가 정신을 차리고 Thaler의 책을 읽고 있습니다. 그 내용 중 일부분인 Sum-Check Protocol과 이를 활용한 application들에 대해서 짚고 넘어가고자 합니다. 이번 글에서는 다루지 않으나, 최근 등장한 HyperPLONK도 역시 Sum-Check Protocol에 기반하고 있으니, 이를 공부하기 위해서라도 Sum-Check에 대해서 제대로 공부해놓는 것이 좋아보입니다.
The Sum-Check Protocol
$v$-variate polynomial $g$가 유한체 $\mathbb{F}$ 위에서 정의되었다고 합시다. 목표는
\[H = \sum_{(b_1, \cdots, b_v) \in \{0,1\}^v} g(b_1, \cdots , b_v)\]가 성립함을 증명하는 것인데, 특히 verifier가 $2^v$번 $g$ 값을 계산해도 되지 않도록 하는 것이 목표입니다. 실제로 시간복잡도는 $v + T$로, 이때 $T$는 $g$를 계산하는데 걸리는 시간입니다.
프로토콜의 진행과정은 Schwartz-Zippel Lemma를 알고 있다면 특별히 어렵지 않습니다.
시작하자마자 Prover는 $H$의 값을 보냅니다. 이제 $v$개의 round를 거칩니다.
첫번째 round에서 Prover는
\[g_1(X_1) = \sum_{(x_2, \cdots, x_v) \in \{0,1\}^v} g(X_1, x_2, \cdots, x_v)\]라는 $X_1$에 대한 다항식을 verifier에게 넘깁니다. 이때, verifier는
\[C = g_1(0) + g_1(1)\]이 성립하는지 확인하고, random element $r_1 \in \mathbb{F}$를 보냅니다.
이제 각 $1 < i < v$번째 round에서 Prover는
\[g_i(X_i) = \sum_{(x_{i+1}, \cdots , x_v) \in \{0, 1\}^{v-i}} g(r_1, \cdots, r_{i-1}, X_i, x_{i+1}, \cdots, x_v)\]를 보내고, verifier는 다시 $g_{i-1}(r_{i-1}) = g_i(0) + g_i(1)$을 확인하고 $r_i \in \mathbb{F}$를 보냅니다.
마지막으로, $v$번째 round에서 Prover는
\[g_v(X_v) = g(r_1, \cdots , r_{v-1}, X_v)\]를 보내고, verifier는 $g_{v-1}(r_{v-1}) = g_v(0) + g_v(1)$을 확인합니다.
마지막으로, verifier는 $r_v$의 값을 랜덤하게 잡고
\[g_v(r_v) = g(r_1, \cdots, r_v)\]가 성립하는지 $g$를 직접 계산하여 확인힙니다.
Completeness는 자명하며, Soundness는 Schwartz-Zippel Lemma에 Union Bound를 취하면 얻을 수 있습니다. Soundness error는 최대 $dv/\lvert\mathbb{F}\rvert$입니다.
Cost를 조금 더 제대로 생각해보면, $g$의 $x_i$에 대한 차수 $\deg_i(g)$가 중요함을 알 수 있습니다.
- Communication: $\mathcal{O}(\sum_i \deg_i(g))$
- Prover Time: $\mathcal{O}(\sum_i \deg_i(g) 2^{v-i}T)$
- Verifier Time: $\mathcal{O}(v + \sum_i \deg_i(g) + T)$
Application 1: #SAT Problem
#SAT 문제는 boolean formula가 주어졌을 때 이를 참으로 만드는 $(x_1, \cdots, x_n)$의 개수를 세는 문제라고 해석할 수 있습니다.
boolean formula가 참일 경우에 1이 나오고 아닌 경우에 0이 나오는 $v$-variate polynomial은 충분히 쉽게 만들 수 있습니다.
그러므로, Sum-Check Protocol을 사용하면 #SAT 문제에 대한 답이 올바름을 증명할 수 있고, 특히 이때 verifier는 다항시간에 작동함을 알 수 있습니다. 즉,
\[\#SAT \in \mathbb{IP}\]Application 2: Matrix Multiplication
$f(a_1, \cdots, a_n) = w_{a_1, \cdots, a_n}$이 각 $(a_1, \cdots, a_n) \in {0, 1}^n$에 대해 성립하도록 interpolate 하는 법은
\[f(x_1, \cdots, x_n) = \sum_{(a_1, \cdots, a_n) \in \{0,1\}^n} w_{a_1, \cdots, a_n} \prod_{i=1}^n (a_ix_i + (1-a_i)(1-x_i))\]입니다. 이제 $A, B$가 $n \times n$ matrix고 $n$이 2의 거듭제곱이라 합시다.
이때, $f_A$를
\[f_A(i_1, \cdots, i_{\log n}, j_1, \cdots j_{\log n}) = A_{i, j}\]가 성립하도록 잡고, $f_B, f_C$도 동일하게 잡습니다.
이러면 증명해야 하는 것은
\[f_C(x, y) = \sum_{b \in \{0, 1\}^{\log n}} f_A(x, b) \cdot f_B(b, y)\]입니다. 좌변과 우변이 모든 $x, y \in {0, 1}^{\log n}$에 대해 성립하므로, 결국 항등식이어야 하기 때문입니다. 결국 이를 확인하기 위해서 $r_1, r_2$를 랜덤하게 잡고
\[f_C(r_1, r_2) = \sum_{b \in \{0, 1\}^{\log n}} f_A(r_1, b) \cdot f_B(b, r_2)\]임을 Sum-Check Protocol로 증명하면 됩니다.
$g(z) = f_A(r_1, z) \cdot f_B(z, r_2)$라고 정의하면, $g$는 각 변수에 대해 최대 이차식임을 알 수 있습니다. 그러므로, Sum-Check을 위해서 prover가 계산해야 하는 것은
\[(r_{3, 1}, \cdots , r_{3, k-1}, \{0, 1, 2\}, b_{k+1}, \cdots, b_{\log n}): \quad (b_{k+1}, \cdots , b_{\log n}) \in \{0, 1\}^{\log n - k}\]에서의 $g$의 값입니다. 이는 겹치는 부분을 동시에 잘 계산하면 $\mathcal{O}(n^2)$에 가능합니다.
Reducing Number of Evaluations to 1
$W$가 $\mathbb{F}$ 위의 $v$-variate multilinear polynomial이라 하고, $W(v_0) = w_0, \cdots, W(v_{n-1}) = w_{n-1}$을 보이고 싶다고 합시다.
이를 위해서, $l: \mathbb{F} \rightarrow \mathbb{F}^v$를 잡아서 $l(i) = v_i$가 되도록 interpolate 합니다. 이제 $q = W \circ l$이라 하면 $q$는 일변수 다항식이 됩니다. Prover는 이 다항식을 보내고, Verifier는 랜덤한 $r$ 값을 선택한 뒤
\[q(r) = W(l(r))\]가 진짜 성립하는지 확인합니다. 이때 $W$를 한 번 계산해야 합니다. $l$의 정당성도 확인이 되면, 이제 $W(v_i)$의 값을 확인하기 위해서 $q(i)$의 값을 직접 계산하면 충분합니다. 이제 단일변수 다항식이므로, 직접 계산해도 충분하기 때문입니다. 증명은 역시 Schwartz-Zippel Lemma로 충분합니다.
이처럼 여러 개의 instance를 하나로 합치는 것은 ZK에서 굉장히 많이 보이는 접근입니다.
Matrix Powers
Matrix Multiplication을 했으니 Matrix Power도 할 수 있습니다.
\[A^k = A^{k/2} \cdot A^{k/2}\]를 확인하고 싶은데, Sum-Check를 돌릴 때 Verifier가 문제에 마주치게 됩니다. $A^{k/2}$에 대응되는 다항식을 모르기 때문에, 직접 연산을 할 수가 없기 때문입니다. 여기에서 다항식 계산을 두 번 해야 하는데 (왜냐면 $(r_1, r_3), (r_3, r_2)$에서 한 번씩 해야 하므로) 이를 앞선 방식을 사용하면 한 번으로 줄일 수 있습니다. Prover 한테 값까지 미리 달라고 한 다음에, 합쳐서 다시 증명하면 되기 때문입니다. 이러면 결국 $A^{k/2}$에서 한 번 다항식 계산을 하는 게 목표가 되는데, 이러면 문제의 크기를 절반으로 줄인 셈입니다. 이를 반복하면 Matrix Power도 증명할 수 있습니다.
이를 이용해서, 예를 들면, Graph Diameter도 succint 하게 증명할 수 있습니다.
Conclusion
지금까지 Sum-Check Protocol과 그 활용에 대해서 알아보았습니다. 이를 활용한 GKR protocol도 유명하니, 알아둘만 한 것 같습니다. 기회가 되면 GKR에 대한 글이나 HyperPLONK에 대한 글도 작성해보도록 하겠습니다. Thaler 책을 읽으면서 근본을 더 쌓아야겠습니다. 글 읽어주셔서 감사합니다.