Polymath: Groth16 is Not The Limit
소개
ZKP의 성능을 측정하는 요소에는 여러 가지가 있습니다. Prover와 Verifier의 입장에서 생각해보면, 가장 중요한 것은 아무래도
- Prover가 proof를 생성하는데 걸리는 시간 및 리소스
- Verifier가 proof를 검증하는데 걸리는 시간 및 리소스
입니다. 하지만, Recursive ZKP나 최종적으로 Verifier가 위치하는 곳이 어디인지 등을 생각해보면, 시간 및 리소스만큼이나 중요한 것이 바로 Proof의 크기, 즉 proof size임을 알 수 있습니다. Proof의 크기 자체가 크면 blockchain 위에 올리는 데 비용이 커지며, 동시에 Recursive ZKP를 하는 overhead도 커지기 때문입니다.
특히, blockchain 위에 큰 데이터를 올리는 것은 매우 비용이 큽니다. 이 문제를 해결하기 위해, 많은 ZKP 팀들은 일단 생성하고자 하는 ZKP를 원하는 방법으로 생성한 후 (STARK 등) 최종적으로 이 ZKP를 “wrap” 합니다. 즉, proof 자체를 직접 전달하는 게 아니라, “verifier를 통과시키는 proof를 알고 있다”는 것을 새로운 명제로 한 proof를 만들어 이를 전달합니다. 이 새로운 명제를 증명하기 위한 ZKP를 proof size가 작은 알고리즘을 사용해 만들면, 실제로 blockchain으로 보낼 데이터의 크기가 줄어들게 됩니다.
대부분의 경우, 최종 “wrap”을 위해서 Groth16을 사용합니다. 최종 wrap 과정은 전체 ZKP 생성 과정을 기준으로 보면 시간의 극히 일부만을 차지하니, 중요한 것은 proof 생성 시간보다는 최종 proof size가 더욱 중요한 상황이 되겠습니다. 이 점을 감안하여, proof 생성 시간을 크게 증가시키지 않으면서 proof size를 조금이라도 더 줄이는 방향의 연구가 필요하게 되었습니다.
Polymath는 최근 이 문제를 해결한 논문으로, CRYPTO 2024에 등재되었습니다. 이 글에서는 Polymath의 기본적인 아이디어들에 대해서, 그리고 실제로 어느 정도의 proof size 개선이 있었는지에 대해서 다룹니다.
Quick Review of Groth16 Techniques
R1CS를 위한 Groth16은, interpolation 후
\[\sum_{i=0}^{m} a_i u_i(X) \cdot \sum_{i=0}^m a_i v_i(X) = \sum_{i=0}^m a_i w_i(X) + h(X)t(X)\]형태의 식을 증명하기를 원합니다. 이를 위해서 trapdoor $\tau = (\alpha, \beta, \gamma, \delta, x)$와 함께 common reference string을 다음과 같이 준비합니다.
\[\sigma_1 = \left(\alpha, \left\{ \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} \right\}_{i=0}^l, \left\{ \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} \right\}_{i=l+1}^m, \left\{ \frac{x^i t(x)}{\delta} \right\}_{i=0}^{n-2}\right)\] \[\sigma_2 = (\beta, \gamma, \delta, \{x^i\}_{i=0}^{n-1})\]그 후, 증명을 생성하기 위해서 $r, s$를 prover가 random sample 한 다음,
\[A = \alpha + \sum_{i=0}^m a_i u_i(x) + r\delta\] \[B = \beta + \sum_{i=0}^m a_i v_i(x) + s \delta\] \[C = \sum_{i=l+1}^m a_i \cdot \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} + \frac{h(x)t(x)}{\delta} + As + rB - rs\delta\]를 계산하며, verifier는 이 값을 받고
\[A \cdot B = \alpha \cdot \beta + \sum_{i=0}^l a_i \cdot \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} \cdot \gamma + C \cdot \delta\]를 검증합니다. 물론, 이 과정은 타원곡선 위에서 진행됩니다. 즉, $G_1 \times G_2 \rightarrow G_T$ 형태의 elliptic curve pairing을 하나 준비하고, $\sigma_1$에 속한 값들은 $G_1$ 위로, $\sigma_2$에 속한 값들은 $G_2$ 위로 준비한다음 (즉, $g$를 generator로 하나 고정하고 $x$를 $x \cdot g$에 대응) pairing을 통해서 모든 과정을 진행합니다. 실제로 verifier에게 전달되는 값은 $[A]_1, [B]_2, [C]_1$이 되며, 실제로 verifier가 확인하는 것은
\[[A]_1 \cdot [B]_2 = [\alpha]_1 \cdot [\beta]_2 + \sum_{i=0}^l a_i \cdot \left[ \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma}\right]_1 \cdot [\gamma]_2 + [C]_1 \cdot [\delta]_2\]입니다.
안전성 증명의 핵심은, affine prover strategy로 (algebraic group model) 접근했을 때 adversary가 verifier를 통과하는 proof를 생성했을 경우, 이를 통해서 witness를 extract 할 수 있음을 보이는 것입니다. 즉, $A, B, C$를 $\sigma_1, \sigma_2$ 위의 값들을 선형결합해서 만든 값이라고 하고, verifier가 검증하는 식이 어떻게 되는지 확인하는 것입니다. 이 과정에서, 양쪽의 식을 trapdoor $\alpha, \beta, \gamma, \delta, x$에 대한 Laurent polynomial로 보고, 양쪽에서 계수 비교를 진행합니다. 계수 비교를 열심히 하다보면, 결국 양변이 Laurent polynomial로서 동일하다면 witness가 extract 됨을 증명할 수 있습니다. 결론적으로 “trapdoor를 기준으로 한 Laurent polynomial로 verifier가 통과되려면 witness가 있어야한다”가 핵심 아이디어입니다.
Groth16의 증명 크기는 $G_1$ 원소 2개와 $G_2$ 원소 1개임을 알 수 있습니다.
[Lip22] and Improvements
Polymath는 SAP를 다루는 SNARK입니다. R1CS가 2차식까지의 곱셈과 덧셈을 지원한다면, SAP는 2차식까지의 거듭제곱과 덧셈을 지원합니다. 사실 R1CS로 할 수 있는 것은 SAP로도 할 수 있는데, 단순히 $xy = (x+y)^2/4 - (x-y)^2/4$를 쓰면 됩니다. R1CS에서 $Ux \circ Vx = Wx$를 다뤘다면, SAP에서는 $Ux \circ Ux = Wx$를 다룬다고 보면 되겠습니다.
비슷하게, 목표는
\[u(X) = \sum_{j=1}^m z_j u_j(X), \quad w(X) = \sum_{j=1}^m z_j w_j(X)\]라고 했을 때
\[u(X)^2 - w(X) = h(X) Z_{\mathbb{H}}(X)\]가 성립하는 것을 증명하는 것입니다.
$\alpha, \gamma$를 작은 정수라고 하고, 나중에 결정하도록 합시다. 또한, $Y = X^\sigma$라고 하고 $\sigma$ 역시 나중에 정합시다. 먼저,
\[A(X) = u(X) + r_a(X) \cdot Y^\alpha\]로 둡시다. 여기서 $r_a(X)$는 random sample 된 차수 1 이하 다항식입니다. 궁극적으로, 나중에 $A$를 KZG open 하기 때문에, zero knowledge를 보존하려면 random sample이 필요합니다.
또한, 추가적으로
\[R_0(X) = r_a(X) Y^\alpha \cdot (2u(X) + r_a(X) Y^\alpha + Y^\gamma)\] \[C_0(X) = (A(X) + Y^\gamma)A(X) = u(X)Y^\gamma + u(X)^2 + R_0(X)\]라고 합시다. 이러면, 만약 prover가 honest 하다면
\[C_0(X) = u(X)Y^\gamma + w(X) + h(X) Z_{\mathbb{H}}(X) + R_0(X)\]가 성립하게 됩니다. 기존 연구에서는
\[C_0(X) = C(X) Y^\alpha + \text{PI}_0(X) Y^\eta\]로 쓰기 위해서,
\[\text{PI}_0(X) = \sum_{j=1}^{m_0} z_j (u_j(X) Y^\gamma + w_j(X)) / Y^\eta\] \[C(X) = \sum_{j=m_0+1}^m z_j(u_j(X) Y^\gamma + w_j(X)) / Y^\alpha + h(X) Z_{\mathbb{H}}(X) / Y^\alpha + R(X)\] \[R(X) = R_0(X) / Y^\alpha = r_a(X) (2u(X) + r_a(X) Y^\alpha + Y^\gamma)\]로 씁니다. 이를 확인하기 위해서, verifier는 pairing
\[[a + y^\gamma]_1 \cdot [a]_2 = [c]_1 \cdot [y^\alpha]_2 + [\text{PI}_0(x)]_1 \cdot [y^\eta]_2\]를 검증합니다. 여기서 $[a] = [A(X)], [c] = [C(X)]$.
$\alpha, \gamma, \eta, \sigma$ 등의 값은 Groth16 형태의 Laurent Polynomial을 기반으로 한 증명이 적용되도록 결정합니다.
그런데 문제가 있습니다. 이 방법은 $[(u_j(x) y^\gamma + w_j(x)) / y^\eta]_1$을 common reference string에 넣고, $[\text{PI}_0(x)]_1$을 verifier가 직접
\[[\text{PI}_0(x)]_1 = \sum_{j=1}^{m_0} z_j [(u_j(x) y^\gamma + w_j(x)) / y^\eta]_1\]로 계산을 해야합니다. 즉, $m_0$ 크기의 MSM을 verifier가 해야합니다. 해시를 사용하는 등의 방법으로 $m_0 = 1$로 줄일 수 있긴 하지만, 해시를 사용하는 방법은 추가 constraint를 필요로 하며 (in-circuit hashing 필요) verifier 역시 해시를 한 번 해야하기 때문에 여전히 비효율적이라고 볼 수 있습니다. 또한, $y^\eta$가 등장하는 위치가 여기에서밖에 없는데, $\eta$가 추가되어 common reference string도 커지고, 안전성 증명을 위해 필요한 $\alpha, \gamma$ 등의 값도 커지게 되어 prover가 더 비효율적이게 됩니다.
이를 해결하기 위해, $j \le m_0$에 대해 $U, W$에 추가적인 제약을 걸어 효율을 올리는 방법을 제시합니다. $j \le m_0$에 대해서 $U$는 non-zero coefficient 최대 2개, $W$는 전부 zero coefficient를 갖는다고 가정할 수 있습니다. 이는 간단하게 첫 $m_0$개 변수를 뒤에 있는 변수들로 copy constraint를 건다음, 뒤에 있는 변수들만 사용하는 방법으로 얻을 수 있습니다. SAP 상으로는,
\[z_{m_0 + 2j} = (z_j + 1)^2 / 4\] \[z_{m_0 + 2j + 1} = (z_j - 1)^2 / 4\]라는 제약을 걸고, $z_j$가 등장할 때 $z_{m_0 + 2j} - z_{m_0 + 2j+1}$을 사용하는 것으로 대체하면 됩니다.
또한, public input에 대응되는 space $\mathbb{K}$를
\[\mathbb{K} = \{ \omega^{n/m_0 \cdot j} : j \in [0, m_0)\}\]로 정의해봅시다. (단, $n$이 $m_0$의 배수라고 가정합니다)
결국, 이제는 $w_j(x)$에 대해서 고민할 필요가 없으니
\[\sum_{j} z_j u_j(X) \cdot Y^\gamma\]만 잘 다루면 되고, $U$ 쪽에서 non-zero coefficient가 매우 적음을 알고 있으니 이는
\[\sum_{j} \tilde{z}_j l_j(X) \cdot Y^\gamma\]형태로 쓸 수 있습니다. 단, $l_j$는 $\mathbb{H}$에 대한 lagrange polynomial. 그런데 space $\mathbb{K}$를 $\mathbb{H}$의 subgroup으로 잡았으므로, 간단한 계산을 통해서
\[l_j(X) = \frac{m_0}{n} l_j^{\mathbb{K}}(X) \cdot Z_{\mathbb{H} \setminus \mathbb{K}}(X)\]임을 알 수 있습니다. 그러니,
\[\text{PI}(X) = \sum_{j} \tilde{z}_j l_j^{\mathbb{K}}(X) \cdot Y^\gamma\]로 두면, 체크를 간단하게
\[[a + y^\gamma]_1 \cdot [a]_2 = [c]_1 \cdot [y^\alpha]_2 + [\text{PI}(x)]_1 \cdot \left[\frac{m_0}{n} Z_{\mathbb{H}\setminus \mathbb{K}}(X)\right]_2\]로 진행할 수 있어 계산이 더 깔끔해집니다.
여기까지는 [Lip22]와 비슷하며, 이에 대한 improvement라고 볼 수 있습니다. 아직까지는 proof size에 관해서는 여전히 $[a]_1, [a]_2, [c]_1$을 보내므로 큰 차이가 없습니다. 이제, $[a]_2$ 제거해서 proof size를 줄여봅시다.
Polymath: Main Idea
$[a]_2$를 보내는 게 문제이니, 이를 피해봅시다.
이를 위해서, KZG Commitment의 기본적인 아이디어를 사용합니다. Verifier가 $x_1$을 random sample 하고, $A_{x_1} = A(x_1)$의 값을 prover에게 요청합니다. Prover는 이 값을 KZG proof와 함께 제공합니다. Verifier는
\[y_1 = x_1^\sigma, y_1^\alpha, Z_{\mathbb{H} \setminus \mathbb{K}}(x_1), y_1^\gamma\]등을 직접 계산할 수 있으며, 특히 $\text{PI}(x_1)$ 역시 $\tilde{\mathcal{O}}(m_0)$번의 field operation을 통해서 쉽게 계산할 수 있습니다. 그러므로, 남은 것은 $C(x_1)$이
\[((A_{x_1} + y_1^\gamma)A_{x_1} - \text{PI}(x_1) \cdot \frac{m_0}{n} Z_{\mathbb{H} \setminus \mathbb{K}}(x_1)) / y_1^\alpha\]와 같은지 확인하는 것 뿐이며, 이건 또 KZG를 쓰면 됩니다. KZG opening 2개는 batch가 가능합니다.
Groth16과 동일한 증명을 적용하기 위한 $\alpha, \gamma, \sigma$의 값에 대해 고민해보면, $\alpha = -3, \gamma = -5, \sigma = n+3$을 선택하면 됨을 증명할 수 있습니다. 이 과정에 대해서는 이 글에서는 생략하도록 하겠습니다. 결과적으로, 새 argument는 Fiat-Shamir 이후 $G_1$의 element 3개와 field element 1개로 구성됩니다.
$[a]_1$, $[c]_1$과 $A_{x_1}$으로 주장할 값, 그리고 $A_{x_1}$으로 주장할 값과 이로 유도된 $C_{x_1}$으로 나와야 할 값에 대한 batch KZG proof으로 증명이 구성됩니다. Groth16이 $G_1$ 원소 2개와 $G_2$ 원소 1개로 구성되어있고, $G_2$ 원소의 크기가 $G_1$과 비교하면 훨씬 크다는 점을 감안하면 이는 좋은 개선임을 알 수 있습니다.