Polynomial Commitment Scheme from DARK
논문: https://eprint.iacr.org/2019/1229.pdf
Introduction
수많은 zkSNARK 체계들은 하나의 커다란 연산 과정을 간단한 게이트들로 구성된 Arithmetic Circuit으로 변환하고, 이에 대한 증명을 다항식들에 대한 항등식을 증명하는 것으로 전환합니다. 결과적으로 다루는 대상들이 다항식이므로, 자연스럽게 Polynomial Commitment라는 암호학 기술이 사용되게 됩니다.
보통 Commitment라고 하면, 값 $x$에 대한 commitment $C$를 계산하는 commit 함수가 있고, 다시 $C$를 알때 이것이 $x$의 commitment임을 증명하는 open 과정이 있습니다. $C$를 다른 값 $y$의 commitment로 open 하지 못하도록 하는 특성을 binding이라 하고, $C$만 봐서는 이것이 $x$의 commitment임을 알 수 없도록 하는 특성을 hiding이라고 합니다.
Polynomial Commitment는 결국 다항식에 대한 commitment입니다. 단, binding, hiding, commit, open 뿐만이 아니라 eval이라는 메소드를 추가적으로 지원합니다. 이는, 다항식 $f$가 commit 되었고 임의의 $x$가 주어졌을 때 $f(x) = y$임을 증명하는 proof $\pi$를 계산할 수 있다는 뜻입니다. 물론, 이는 검증 가능해야 하며 가짜 증명 역시 만들기 어려워야 합니다.
Polynomial Commitment 중 가장 대표적인 것은 KZG Commitment이며, 이에 대한 글은 여기에서 찾아보실 수 있습니다. KZG Commitment는 proof도 선형적이고, commitment도 선형적이며, 증명의 크기 및 증명 검증 시간이 매우 효율적이라 많이 사랑받는 방식입니다. 그러나, KZG Commitment에는 문제가 하나 있습니다.
앞서 링크한 글에서도 언급되었지만, KZG를 위해서는 아무도 $\alpha$를 모르는 상태에서
\[g, g^\alpha, g^{\alpha^2}, \cdots, g^{\alpha^n}\]을 생성하고 이 값을 Common Reference String으로 공개해야 합니다. 이는 쉽지 않은 과정이지만, Powers of Tau 등을 통해서 수많은 사람이 함께 참여해 그 중 한 사람만 제대로 참여하더라도 (자신의 비밀을 노출시키지 않더라도) 안전하게 $\alpha$를 생성할 수 있습니다. 또한, 생성 과정에서 나온 모든 script를 추후에 검증할 수 있습니다. 이렇게 Common Reference String을 생성하기 위해서 “믿음”을 가지고 진행하는 과정을 trusted setup이라고 합니다. Powers of Tau 정도면 나름 탈중앙화가 된 방법이지만, 어쨌든 한 번의 trusted setup으로 추후에 쭉 사용할 값들을 생성하는 것은 나름 찜찜할 수 밖에 없습니다. 어떻게 생각하면 영원한 떡밥 같은 느낌이죠.
zkSNARKs를 trusted setup 없이 만들고 싶다면, trusted setup이 필요없는 Polynomial Commitment 방법을 만드는 것이 필수적입니다. 오늘의 목표는 그 중 하나인 DARK에 대해서 간략하게 알아보는 것입니다. Security에 대한 증명은 꽤 복잡해서 (단순한 rewinding을 통한 knowledge extraction이 잘 안되는 것으로 알고 있습니다), 간략하게만 짚고 넘어가도록 하고, 전체적인 알고리즘 과정과 배경 아이디어, 그리고 몇 가지 최적화 방법들에 대해서만 알아보도록 하겠습니다.
Arguments based on Hidden Groups
이번 내용은 기본적으로 그 크기를 계산하기 힘든 군들을 기반으로 하여 구축됩니다. 암호학에서 이런 hidden order group들을 다루는 내용을 꽤 많이 볼 수 있는데, 그 중 특히 이번 글과 관련이 있는 내용이 두 개 있습니다.
먼저 Generator $g$를 갖는 Hidden Order Group $G$가 있을 때, 정수 $x$를 $x \cdot g$로 commit 할 수 있다는 아이디어를 기반으로 한, Diophantine Argument of Knowledge가 있습니다. 두 commitment 사이의 곱셈 및 덧셈을 zero knowledge로 증명할 수 있고, 이를 기반으로 모든 diophantine equation을 다룰 수 있게 됩니다. 이 논문에 대한 글은 제 2021년 글에서 찾아보실 수 있습니다.
또한, Hidden Order Group $G$가 있을 때 큰 $T$에 대해서
\[h = g^{2^T}\]라는 값이 제대로 계산되었는지 증명하는 방법이 연구되었습니다. 위 식의 우변을 계산하려면 정직하게 $T$번 거듭제곱을 해야하므로, 이는 $T$번의 sequential computation을 강제한다고 볼 수 있습니다. 이러한 기술을 Verifiable Delay Function이라고 부릅니다. 이에 대한 내용은 제 2022년 발표자료 뒷부분에서 찾아볼 수 있습니다. 특히, 여기서 나오는 많은 아이디어들이 이 글에서도 그대로 등장하는 만큼, 이 발표자료와 [BBF+18]는 한 번 읽어보는 것을 권합니다. 참고로 이 논문과 이 글에서 다루는 논문이 저자가 두 명 겹칩니다. 어느 정도 이유가 있겠죠?
Hidden Order Group 중 우리가 가장 익숙한 것은 RSA Group입니다. 하지만 이는 기본적으로 trusted setup이 필요합니다. 소수 두 개를 생성해서 곱해야 하는데 아무도 그 소수를 알면 안되겠죠? 대신, Class Group of imaginary quadratic order를 사용하면 trusted setup 없이 hidden order group을 하나 생성할 수 있습니다.
DARK Polynomial Commitment
Integer Encoding of Polynomials
첫 번째 아이디어는 다항식을 정수 하나로 encode 하는 것입니다. 충분히 큰 $q$가 있다면,
\[f(x) = \sum_{i=0}^d a_i x^i \rightarrow \sum_{i=0}^d a_i q^i = \hat{f}(q)\]를 함으로써 $\mathbb{F}_p[x]$의 원소를 정수로 보낼 수 있습니다. 좌측에서는 $a_i$가 $\mathbb{F}_p$의 원소지만, 우측에서는 $a_i$가 ${0, 1, \cdots ,p-1}$의 원소입니다. 이 값을 적은 데이터로 표기하기 위해서 hidden order group을 도입, 적당한 군 $G$와 그 원소 $g$를 하나 고정하고 $\mathcal{C} = \hat{f}(q) \cdot g$를 생각합니다.
조금 더 엄밀하게 들어가기 위해서,
\[\mathbb{Z}(b)[x] = \{f \in \mathbb{Z}[x] : \lvert f \rvert_\infty \le b \}\]를 생각합니다. 그러면 encode 과정에서는 가장 자연스러운 방법으로
\[\mathbb{F}_p[x] \rightarrow \mathbb{Z}(p-1)[x]\]로 보내고 생각을 하게 됩니다. 생각해보면, 우리가 $q$를 대입해서 encode를 하는 것도
\[\mathbb{Z}(q/2)[x]\]에서나 가능한 이야기입니다. $q$진법을 생각하면 됩니다. 결국 open 때도
\[\hat{f} \in \mathbb{Z}(q/2)[x], \quad \hat{f}(q) \cdot g = \mathcal{C}\]를 확인하게 됩니다. decode 과정은 진법 변환을 그대로 하면 됩니다.
이렇게 되면 commit, open 과정이 전부 나왔고, eval 방법만 구축하면 됩니다.
The Evaluation Protocol
Pietrzak의 VDF 증명과 비슷합니다. 차수가 $d = 2^k - 1$인 다항식 $f$을 다룬다고 하면, 먼저
\[f = f_L + x^{\lceil d / 2 \rceil} f_R\]로 다항식을 두 개로 쪼갭니다. 이러면
\[\mathcal{C}_L = \hat{f}_L(q) \cdot g, \quad \mathcal{C}_R = \hat{f}_R(q) \cdot g\]를 생각할 수 있으며, 두 값이 쪼개지는 것을 확인하기 위해
\[\mathcal{C}_L + q^{\lceil d / 2 \rceil} \mathcal{C}_R = \mathcal{C}\]를 확인할 수 있습니다. 비슷하게, $\mathbb{F}_p[x]$에서 $f(z) = y$를 보이고 싶다면,
\[y_L = f_L(z) \pmod{p}, \quad y_R = f_R(z) \pmod{p}\]를 준비하고 다항식이 제대로 쪼개진 것을 확인하기 위해
\[y_L + z^{\lceil d / 2 \rceil} y_R \equiv y \pmod{p}\]를 확인합니다. 이제 두 다항식을 합쳐서 한 번에 확인하기 위해, verifier의 $\alpha$를 하나 받고
\[\mathcal{C}' = \mathcal{C}_L + \alpha \mathcal{C}_R, \quad f' = f_L + \alpha f_R, \quad y' \equiv y_L + \alpha y_R \pmod{p}\]를 준비합니다. 이제 차수 $\lfloor d / 2 \rfloor$인 다항식 $f’$에 대한 검증을 진행합니다.
이 과정은 마지막까지 진행되며, 최종에는 $\mathcal{C}$의 이산로그 값을 직접 공개하면 됩니다.
The Evaluation Protocol: $\mu$-linear multivariate
이 과정을 $\mu$-linear multivariate polynomial에 대해서도 그대로 적용할 수 있습니다. 즉, $x_1, x_2, \cdots, x_\mu$를 변수로 가지며 각 변수에 대해서는 선형적인 다항식에 대해서도 그대로 적용할 수 있습니다. 이는 위 방법의 일반화인게, $x_i = x^{2^{i-1}}$을 대입해서 생각하면 모든 $x$의 거듭제곱을 이진법 전개를 활용하여 $x_i$들에 대한 $\mu$-linear multivariate monomial로 표현할 수 있습니다.
방법 자체는 비슷한 게, $x_\mu$에 대한 부분을 처리하기 위해서
\[f = f_L(x_1, \cdots , x_{\mu - 1}) + x_\mu f_R(x_1, \cdots , x_{\mu - 1})\]로 쪼개는 방식을 사용하면 됩니다. 나머지 부분은 사실상 동일합니다.
Details 1: VDF Techniques for Faster Exponentiation
일단 위 과정에서 가장 무서워보이는 부분은
\[q^{\lceil d / 2 \rceil} \mathcal{C}_R\]을 계산하는 부분입니다. 대강만 봐도 이는
\[\mathcal{O}(d \log q)\]번 정도의 군 연산이 필요합니다. $d$도 꽤 크고, 뒤에서 나오겠지만 사실 $q$도 상당히 커서, 이 값을 Prover가 직접 계산하는 것은 그렇다치더라도 Verifier가 이를 직접 계산하게 되면 verify 과정이 지나치게 느려져, 우리가 원하는 Polynomial Commitment Scheme과는 거리가 멀어지게 됩니다.
이를 해결하기 위해서, 꽤 자주 쓰이는 테크닉을 하나 적용합니다. Prover가 $q^{\lceil d / 2 \rceil} \mathcal{C}_R$의 값을 계산해서 그냥 Verifier에게 직접 주는 것입니다. 물론, Verifier는 이를 바로 믿으면 안되고, 이것이 제대로 계산된 값인 증명을 Prover에게 받아야 합니다. 이렇게 되면 상황이 VDF에서 우리가 다루었던 상황과 정확히 동일하게 됩니다. 여기서는 Wesolowski의 방식으로 증명을 합니다. 이 테크닉은 Halo2를 이용한 Bulletproofs 최적화에서도 사용되는 접근입니다.
Details 2: The rough size of $q$
기본적으로 $\alpha \in [0, 2^\lambda)$라고 하면, 다항식을 쪼개고 더하면서 그 계수가 $2^\lambda$배까지 커지게 됩니다. 이를 $\mu \approx \log_2 d$ round에 걸쳐 진행하므로, 아무리 낮아도 $q \ge p \cdot 2^{\lambda \mu}$ 정도는 가져가야 함을 알 수 있습니다. 실제 security proof를 보면 (논문의 Theorem 1) $q$가 상당히 커야 함을 알 수 있습니다.
Details 3: Optimizations
$q^i \cdot g$의 값을 각 $0 \le i \le d$에 대해서 precompute 할 수 있습니다. 이러면 $\hat{f}(q) \cdot g$의 계산도 빨라지며 parallelization도 추가할 수 있게 됩니다. 또한, multi-scalar-multiplication 알고리즘들을 사용하여 군 연산을 더 빠르게 만드는 최적화도 가능합니다. 이것들 모두는 VDF에서도 어느 정도 적용되는 최적화 방법입니다.
Communication 비용을 줄이기 위해서, Prover가 $\mathcal{C}_L, \mathcal{C}_R$을 전부 다 넘겨주는 대신에 $\mathcal{C}_R$만을 넘겨주는 방법을 생각할 수 있습니다. Verifier는 VDF 증명의 결과에서 빠르게 $q^{\lceil d/2 \rceil} \mathcal{C}_R$을 계산할 수 있고, $\mathcal{C}$도 이미 알고 있으니 이를 통해서 $\mathcal{C}_L$을 역산할 수 있습니다. 이는 $y_L$에 대해서도 마찬가지입니다.
한 다항식 $f$를 여러 점 $y_1, y_2, \cdots , y_k$에서 evaluate 하는 것을 동시에 할 수 있습니다. 동일한 challenge $\alpha$를 사용해도 문제가 없고, 특히 이러면 hidden group 위의 연산이 전부 동일하므로 시간을 많이 절약할 수 있습니다. batch evaluation이 되는 것은 강력한 장점입니다.
여러 다항식을 한 점 $z$에서 evaluate 하는 것을 동시에 할 수 있습니다. 이는 나름 전형적인 방법으로 할 수 있는데, 여러 다항식들의 random linear combination을 취한 후 그 다항식 하나에서 증명을 진행하면 됩니다. 이 역시 Polynomial Commitment Scheme이 가질 수 있는 강력한 기능 중 하나입니다. 단, security 측면에서 이를 진행하려면 $q$의 값이 더욱 커져야 합니다.
여러 체 $\mathbb{F}_p$에 대한 증명을 동시에 진행할 수 있습니다. 사실 어떻게 보면 당연한 것이, 애초에 encoding 하는 과정에서 체를 제거하고 $\mathbb{Z}$로 옮겨서 작업하기 때문에 체가 딱히 중요하지는 않습니다. 실제로 $q$의 크기만 충분히 크다면 체는 크게 중요하지 않고, 여러 체를 사용하는 것도 가능합니다. 나아가서, 중국인의 나머지 정리를 통해서 $\mathbb{Z}_m[x]$를 다루는 것도 가능합니다. 이렇게 보면 어느 정도 동형암호와 비슷한 느낌도 많이 납니다.
최종적인 시간복잡도는 논문의 4.6에서 볼 수 있습니다.
Conclusion
지금까지 DARK Polynomial Commitment Scheme에 대해서 알아보았습니다. Trusted Setup은 그로부터 얻을 수 있는 것도 많지만, 실제로 사용하면 영원한 떡밥으로 남을 수 있는 것이니만큼 많은 암호학자들이 가능하면 피해야하는 대상으로 생각합니다. 블록체인에서도 KZG Commitment를 활용하는 아이디어가 나오기도 하는데, 이러한 떡밥이 있으면 아무래도 찜찜하겠죠. 그러니 Transparent한, 즉 Trusted Setup이 필요하지 않은 접근이 필요했고, 그 중 하나가 바로 이 글에서 다룬 DARK였습니다. 다항식을 정수로 encoding 하고, 이를 다시 hidden order group에 encode 했고 Polynomial Commitment Scheme에서 필요한 여러 method 들을 VDF에서 익숙한 아이디어들을 활용하여 구축해냈습니다. KZG에 비해서는 느리지만, trusted setup을 제거했으며 Polynomial Commitment Scheme에 원하는 여러 성질과 방법들을 고루 갖춘 강력한 방법이었습니다.
긴 글을 읽어주셔서 감사합니다.