Folding Part 1: ProtoStar
이 글에서는 ZKP에서 사용되는 테크닉인 folding의 두 대표적인 논문인 ProtoStar와 HyperNova 중 ProtoStar에 대해서 다룹니다.
- https://eprint.iacr.org/2023/620.pdf
Folding이란 무엇이며, ProtoStar의 목표는 무엇인가
Folding은, input 자체만 제외하면 증명하고자 하는 연산의 형태는 동일한 두 ZKP instance를 하나의 instance로 fold 하는 테크닉으로, 올해 초부터 더욱 본격적인 관심을 받게된 테크닉입니다. 기존에 IVC를 (Incrementally Verifiable Computation) 얻으려면 recursive SNARKs, 즉 이전 SNARK의 verification 과정을 다시 SNARK로 올려 계산하는 방식으로 구현했다면, 이제는 SNARK를 accumulate 하여 접어가면서 쌓아올린 후 최종 accumulator를 가지고 전체 과정을 증명하는 것이 대세가 되었다고 볼 수 있습니다. 이런 folding 계열 논문으로 가장 유명한 것은 R1CS를 relax 시켜 relaxed-R1CS를 만든 후 이를 fold 하는 Nova입니다. 그러나 R1CS만으로 real-world application을 전부 다루기에는 어려움이 많아, 조금 더 expressive 한 방식을 찾는 것이 중요한 문제가 되었습니다. 이를 위해서, ProtoStar는 임의의 $2k - 1$ move special-sound interactive argument를 가지고 IVC를 만드는 일반적인 compiler를 제시합니다. Verifier가 algebraic degree $d$를 가지고 있다면, recursive circuit은 $k + d - 1$번의 scalar multiplication (commitment scheme의 additive group 기준) 에 의해 dominate 되며, 이는 $k = 1, d = 2$인 경우의 특수 경우라고 볼 수 있는 Nova와 동일합니다. 이 compiler에 custom gate, lookup 등에 대응되는 argument를 넣어, 매우 expressive 한 ZKP scheme에 대응되는 IVC scheme을 얻을 수 있게 됩니다.
Part 1: The Compiler
우선 다루는 special-sound protocol들에 대한 정의부터 명확하게 합시다. $(2k - 1)$-move protocol이므로, $k$개의 round를 거치게 됩니다. Prover는 public input, witness, 그리고 이전 $i-1$번의 round에서 나온 prover message와 verifier challenge를 가지고 $i$번째 round를 위한 prover message를 계산합니다. Verifier는 이를 가지고 $i$번째 round를 위한 verifier challenge를 전달합니다. Prover message를 $m_i$, verifier challenge를 $r_i$라고 두면, $m_k$를 전달받은 verifier는 이를 기반으로 accept/reject를 결정해야 합니다.
Verifier의 최종 로직은 $l$개의 degree $d$ algebraic equation을 확인하는 형태입니다. 즉, $f_j$가 homogeneous degree $j$ algebraic map이라고 하면,
\[V_{sps}(pi, [m_i]_{i=1}^k, [r_i]_{i=1}^{k-1}) = \sum_{j=0}^d f_j^{V_{sps}}(pi, [m_i]_{i=1}^k, [r_i]_{i=1}^{k-1})\]이라고 볼 수 있으며, $l$개의 식을 체크해야 하니 $V_{sps}, f_j$ 등은 전부 길이 $l$의 vector라고 볼 수 있습니다.
여기서 두 가지 과정을 추가할 수 있는데,
- $m_i$들을 직접 보내는 게 아니라 먼저 그의 commitment $C_i$를 보낼 수 있으며
- $r_i$를 직접 verifier에게서 받는 게 아니라 Fiat-Shamir를 통해서 받을 수 있습니다.
이러면 확인해야 하는 것은
\[\pi.x = [C_i]_{i=1}^k, \quad \pi.w = [m_i]_{i=1}^k\]라고 했을 때,
- $r_i = \rho_{NARK}(r_{i-1}, C_i)$
- $\text{Commit}(m_i) = C_i$
임과 동시에
\[V_{sps}(pi, [m_i]_{i=1}^k, [r_i]_{i=1}^{k-1}) = \sum_{j=0}^d \mu^{d-j} \cdot f_j^{V_{sps}}(pi, [m_i]_{i=1}^k, [r_i]_{i=1}^{k-1}) = e\]인 것을 확인해야 합니다. 단, $\mu = 1, e = 0^l$입니다.
Nova의 context를 안다면 여기서 $\mu, e$가 relax를 위한 것임을 알 수 있습니다. 실제로 그 느낌이 맞으며, accumulator의 형태는 다음과 같습니다.
accumulator instance는 public input $pi$, commitment들 $[C_i]{i=1}^k$, challenge들 $[r_i]{i=1}^{k-1}$, error term에 대한 commitment $E$, 그리고 slack variable $\mu$로 구성되어 있습니다.
accumulated witness는 prover message들 $[m_i]_{i=1}^k$로 구성되어 있습니다.
Accumulation Prover
accumulated instance인
\[acc = (acc.x = \{pi', [C_i']_{i=1}^k, [r_i']_{i=1}^{k-1}, E, \mu\}, acc.w = \{[m_i']_{i=1}^k\})\]와, 여기에 추가해야 할 proof
\[\pi = (\pi.x = [C_i]_{i=1}^k, \pi.w = [m_i]_{i=1}^k)\]를 합치면 됩니다. 우선 challenge를 얻기 위해 $r_i = \rho_{NARK}(r_{i-1}, C_i)$를 계산합니다. 이제 두 instance를 합치기 위해서
\[\sum_{j=0}^d (X + \mu)^{d-j} \cdot f_j^{V_{sps}}(X \cdot pi + pi', [X \cdot m_i + m_i']_{i=1}^k, [X \cdot r_i + r_i']_{i=1}^{k-1})\]를 계산합니다. 여기서 $X^0$과 $X^d$의 계수를 생각해보면, 전자는 $e$이며 후자는 $0$임을 알 수 있습니다. 즉, 이는
\[e + \sum_{j=1}^{d-1} e_j X^j\]형태로 쓸 수 있으며, 각각을 commit 하여 $E_j = \text{Commit}(e_j)$를 계산합니다.
이제 random 값 하나를 얻기 위해
\[\alpha = \rho_{acc}(acc.x, pi, \pi.x, [E_j]_{j=1}^{d-1})\]를 계산하고, 모든 값을 $\alpha$를 계수로 한 random linear combination으로 둡니다. 즉, $X = \alpha$로 설정한 상황을 생각합니다. $C_i’’ = \alpha C_i’ + C_i$ 등을 사용한다고 보면 되겠습니다. 특히
\[E' = e + \sum_{j=1}^{d-1} \alpha^j E_j\]입니다. 이때 accumulation proof는 $E_j$들이 되겠습니다.
Accumulation Verifier
우선 challenge들의 계산을 검증해야 합니다. 즉, $r_i$들의 계산과 $\alpha$의 계산이 정당했는지는 전부 확인해야 합니다.
그 후에는 값들이 전부 정확히 linearly combine 되었는지 확인하고, error 값에 대한 식인
\[acc'.x.E = acc.x.E + \sum_{j=1}^{d-1} \alpha^j E_j\]가 성립하는지 확인하면 됩니다.
Accumulation Decider
우선 commitment들이 전부 정확한지 확인해야 합니다. 즉, $C_i = \text{Commit}(m_i)$인지 확인합니다. 그 후,
\[e = \sum_{j=0}^d \mu^{d-j} f_j^{V_{sps}}(pi, [m_i]_{i=1}^k, [r_i]_{i=1}^{k-1})\]를 계산하여 $E = \text{Commit}(e)$인지 확인합니다.
Sketch of Proofs
Completeness는 단순 계산이고, Knowledge Soundness가 문제입니다.
여기서 Accumulation의 Knowledge Soundness에 대해서 이야기 해보자면, $(pi, \pi.x, acc.x)$가 주어졌을 때 Prover가 두 instance를 합친 $acc’$와 이를 잘 합쳤다는 증명 $pf$를 제공했을 때, Verifier가 $acc’$에 대한 decider와 잘 합쳤다는 증명 $pf$를 통한 검증만 (accumulation에 대한 검증) 거쳐도 $acc$에 대한 decider와 $\pi$ 자체에 대한 NARK 자체의 verification이 된다고 주장해도 된다는 것이 정의입니다. Definition 8을 참고하시길 바랍니다. 그러니, $(pi, \pi.x, acc.x)$에서 시작해서 두 instance를 합치는 random challenge $\alpha$를 여러 개 생각하고, 각각에 대해서 Verifier가 통과했다고 가정한 다음 이를 통해서 $acc, \pi$를 복구할 수 있으면 됩니다.
즉, $(d+1)$-special-soundness의 증명을 하면 됩니다. 다행히도 일반적인 테크닉으로 가능합니다. $d+1$개의 $\alpha$에 대응되는 accumulation을 모두 찾을 수 있다면, 선형방정식을 풀어서 $E, e$들을 전부 복구할 수 있으며, $acc.w, \pi.w$ 역시 쉽게 복구가 가능합니다. 궁극적으로 $d$차 다항식인
\[\sum_{j=0}^d (X + acc.\mu)^{d-j} \cdot f_j^{V_{sps}}(X \cdot pi + pi', [X \cdot m_i + m_i']_{i=1}^k, [X \cdot r_i + r_i']_{i=1}^{k-1})\]와
\[e + \sum_{j=1}^{d-1} e_j X^j\]가 $d+1$개 점에서 같다는 것이 나오게 되어, 앞서 언급한 $X^0$과 $X^d$의 계수 비교를 통하여 $acc$의 decider와 $\pi$의 NARK 통과여부가 증명이 됩니다.
Compression of $l$ checks
$l$과 $d$가 모두 큰 경우, $\Omega(dl)$번의 group operation을 통해서 $e$들을 전부 commit해야 한다는 점은 무리가 될 수 있습니다. 이를 막기 위해서, $l$개의 check들을 하나로 합치는 방법을 고안할 수 있습니다.
이를 위한 가장 전형적인 방법은 random $\beta$를 sample 한 다음, $l$개의 check들에 coefficient $\beta^i$를 붙여 합친 후 그 결과가 $0$임을 확인하는 것입니다.
하지만 실제로는 $\beta$ 역시 Fiat-Shamir로 계산되어야 하는 값이며, $\beta$에 대한 계산 역시 in-circuit으로 이루어져야 하니 $\beta^l$의 계산에 대한 증명 역시 verifier에게 맡기게 되면 degree가 $l$만큼 커지는 효과가 발생하게 됩니다.
이를 막기 위해서, 버킷을 사용합니다. $l$이 제곱수라고 가정하고,
\[\beta_i = \beta^i, \quad \beta'_i = \beta^{i \sqrt{l}}\]을 두고 이 값들을 $k+1$번째 message로 둡니다. 그러면 verifier는 random linear combination에 대한 체크와 함께, $\beta_i, \beta’_i$들의 계산에 대해서만 검증하면 됩니다.
모든 $\beta$의 거듭제곱은 $\beta_i \cdot \beta’_j$ 형태로 표현할 수 있으므로, degree는 최대 2만큼 증가하며, $\beta_i, \beta’_i$들에 대한 verification 역시 low-degree로 진행할 수 있습니다.
Subprotocols for ProtoStar
Permutation
$w_i = w_{\sigma_i}$를 증명하고 싶다면, 그대로 $w_i - w_{\sigma_i} = 0$을 확인하면 됩니다. 차수는 1입니다.
High-Degree Custom Gate
마찬가지로 정직하게 계산하면 됩니다. 차수는 $d$입니다.
Lookup Relation
이 부분이 조금 어렵습니다. Logarithmic Derivative의 테크닉을 가져와서,
\[\sum_{i=1}^{l} \frac{1}{X + w_i} = \sum_{i=1}^{T} \frac{m_i}{X + t_i}\]인 $m_i$를 제시하면 됩니다. $w_i$들과 $m_i$들을 prover에서 제시하면, random challenge $r$을 verifier가 제시하고, 다시 prover가
\[h_i = \frac{1}{w_i + r}, \quad g_i = \frac{m_i}{t_i + r}\]를 계산하면, 이를 가지고 verifier가
\[\sum h_i = \sum g_i, \quad h_i(w_i + r) = 1, \quad g_i(t_i+r) = m_i\]를 검증하면 됩니다. 이러면 3-move protocol로 degree는 2입니다. 여기서 중요한 점은 prover message에서 non-zero element의 최대 갯수는 $4l$개라는 겁니다. 즉, cost가 실제 lookup 개수에 비례한다는 점입니다.
그런데 이러한 sparseness는 accumulation 과정에서 깨질 수 있습니다. Error term에 대한 accumulation이 유일하게 어려운 부분인데, 다행히도 error term의 commitment만 계산해도 되므로 빠르게 계산이 가능하도록 알고리즘을 설계할 수 있습니다. 이에 대해서는 논문의 34 페이지를 참고하시길 바랍니다.
비슷한 random linear combination 트릭으로 vector lookup도 지원할 수 있습니다.
Program Counter
$b$가 $b_{pc} = 1$이고 나머지는 $0$임을 증명하기 위해서,
\[b_i (pc - i) = 0, \quad b_i(b_i - 1) = 0, \quad \sum b_i = 1\]을 확인하게 할 수 있습니다. 차수는 2입니다.
이러한 과정을 거쳐서 branch circuit을 지원하며 동시에 PLOOKUP의 모든 primitive를 지원하는 special-sound protocol을 구축할 수 있고, 이에 앞서 언급한 Compiler를 적용하여 ProtoStar를 얻을 수 있습니다.
다음 글에서는 ProtoStar와 비슷한 계열의 연구인 Hypernova와 관련 연구들에 대해서 알아보도록 하겠습니다.