rkm0959's profile image

rkm0959

May 15, 2022 00:00

들어가기 전에

논문

• https://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf (KZG Commitment, Asiacrypt 2010)
• https://eprint.iacr.org/2020/527.pdf (eprint)
  • 이 논문의 저자에는 Vitalik Buterin도 있습니다.

선행지식

• https://github.com/rkm0959/rkm0959_presents/blob/main/TornadoCash.pdf
• 정확히는, Powers of Tau와 Pairing에 대한 기본적인 이해
• 다항식의 연산에 관한 알고리즘 (FFT 계열)

이 글에서 Security에 대한 부분은 생략하도록 하겠습니다. 필요한 가정과 실제 scheme의 security 증명 사이의 gap이 그렇게 크지 않고, 글에서 다루는 내용이 이미 많기 때문입니다. 이 부분에 대해 궁금한 점이 있는 독자들은 KZG Commitment 논문의 Section 2에 있는 Assumption들과 Appendix C를 참고하시기 바랍니다.

서론

Commitment Scheme은 암호학에서 매우 중요한 대상 중 하나입니다. 메시지 $m$이 있을 때, 이를 공개하지 않은 상태로 확정하기 위한 암호학적 접근입니다. $m$을 commit하고 싶은 사람은, random 값 $r$을 하나 뽑고 세상에 $C(m, r)$을 공개합니다. 추후에, $m$을 reveal 할 때가 오면, $m, r$의 값을 세상에 공개하면 사람들이 직접 $C$에 $m, r$을 대입하여 기존에 공개되었던 $C(m, r)$이 정확한지 검증할 수 있을 겁니다.

이 방식이 우리가 원하는 것을 만족하려면,

• $C(m, r)$만을 보고 $m$에 대한 정보를 얻을 수 없어야 하고 (또는, negligible한 정보만을 얻을 수 있고)
• $C(m, r) = C(m’, r’)$인 $m’, r’$을 찾기 매우 어려워야 합니다.

전자는 $C$가 hiding, 즉 $m$에 대한 정보를 유출하지 않기 위함이며, 후자는 $C$가 binding, 즉 $m$을 확정하는 의미를 제대로 갖기 위함입니다. 단순하게 생각하면 $C$로 적합한 함수는 많습니다. 해시함수를 믿고 있다면, 해시함수를 넣어도 직관적으로 괜찮음을 알 수 있고, 이는 Random Oracle Model에서 실제로 성립함을 증명할 수 있습니다.

하지만 $C$에 조금 더 유용한 성질을 부여하고 싶거나, commit 하는 대상인 $m$이 단순한 bit string이 아닌 수학적 구조를 더욱 갖는 대상이라면 $C$를 어떻게 만들지 조금 더 제대로 생각할 필요가 있습니다.

이 글에서는 $m$이 $\mathbb{F}_p[x]$에 속하는 다항식인 경우에 대해서 다룹니다. 이제부터 메시지를 다항식 $\phi$로 표기합니다.

이 글에서는

• $\phi$에 대한 기본적인 commit-reveal scheme과
• $\phi$의 evaluation에 대한 효율적인 proof와 verification을 제공

하는 KZG commitment scheme에 대해서 알아보겠습니다.

Lagrange Interpolation을 생각하면 다항식은 벡터에 대응될 수 있으며, 그렇기 때문에 KZG commitment scheme을 이용하여 vector에 대한 commitment scheme을 만들자는 생각을 할 수 있습니다. 여기에 vector에 “각 계좌의 잔고”를 저장하자는 아이디어를 추가하면, 작은 크기의 commitment 하나로 현재 상태가 전부 표시 가능한 매우 효율적인 단순 암호화폐 체계를 구축할 수 있게 됩니다.

• 이 암호화폐 체계에 대해서는 매우 간략하게만 설명하겠습니다.

이더리움으로 유명한 Vitalik Buterin을 포함한 연구진이 이를 어떻게 구축했는지 알아보겠습니다.

KZG Commitment

디테일을 들어가기 전에, 필요한 알고리즘이 무엇인지 생각해봅시다.

• Setup : 필요한 public value들을 생성하는 과정
• Commit : 주어진 다항식 $\phi$에 대한 commitment $\mathcal{C}$를 생성하는 과정
• Verify : $\phi$가 reveal 되었을 때, $\mathcal{C}$와 consistent 한지 확인하는 과정
• Create Proof : $\phi$를 아는 사람이 $\phi(i)$의 값에 대한 proof $w_i$를 생성하는 과정
• Verify Eval : $i, \phi(i)$의 값과 $w_i$, $\mathcal{C}$를 아는 사람이 실제로 $\phi(i)$가 잘 계산되었는지 확인하는 과정

이 필요합니다. 핵심 아이디어는 다음 두 개입니다.

• $(x-i) \vert (\phi(x) - \phi(i))$가 성립함
• order $p$의 group $G$와 generator $g$, 비밀값 $\alpha \in \mathbb{F}_p$를 준비하고, $\phi$에 대한 commitment를 $g^{\phi(\alpha)}$로 두는 것

Setup - Powers of Tau

$\alpha$가 모두에게 비밀인 상태에서 $g^{\phi(\alpha)}$를 commitment로 둘 수 있게 하려면, $g, g^\alpha, g^{\alpha^2}, \cdots , g^{\alpha^n}$을 공개해야 합니다. 이러면 $\deg \phi \le n$에 대해서는 KZG commitment를 계산할 수 있게 됩니다.

문제는 $\alpha$를 아무도 모르는 상태에서 저 값을 생성해야 한다는 것인데, 이는 Groth16 + Powers of Tau 등에서도 이미 익숙한 세팅입니다. 이 문제를 해결하는 방식은

• 중앙화, i.e. trusted third party 사용
• 탈중앙화, i.e. multiparty computation via Powers of Tau

가 있습니다. KZG는 2010년 논문이라 일단 trusted authority를 가정했지만, 후에 암호화폐 컨텍스트에서 쓰인 논문들은 대부분 Powers of Tau를 이용하게 됩니다. 또한, 후에 사용될 알고리즘을 위해서 group $G$는 pairing operation을 지원하는 것으로 선택해야 합니다. 즉, 실전에서는 적합한 타원곡선이 선택될 것입니다.

Commit, Verify

앞서 언급한 것처럼 commitment는 $\mathcal{C} = g^{\phi(\alpha)}$입니다. $\phi$를 아는 사람이 commit, verify 하는 방법은 자명합니다.

Create Proof, Verify Eval

이 부분이 KZG의 아름다움이자 유용한 점입니다.

proof를 만드는 사람은 다항식 $\psi_i(x) = \frac{\phi(x) - \phi(i)}{x - i}$를 구하고, $\phi(i)$에 대한 proof를 $w_i = g^{\psi_i(\alpha)}$로 둡니다.

이를 verify 하는 입장에서는, $G$가 pairing operation을 지원한다는 사실을 활용할 수 있습니다.

\[e(\mathcal{C}, g) = e(w_i, g^\alpha \cdot g^{-i}) \cdot e(g, g)^{\phi(i)}\]

가 $w_i$가 정당한 값이라면 성립해야 함을 알 수 있고, 이를 확인하는 것으로 verify가 가능합니다. 물론, 이 식은 $\phi(x) = \phi(i) + (x - i) \psi_i(x)$를 group 위에서 풀어쓴 것에 불과합니다.

Proving Multiple Evaluations in a Batch

또 다른 KZG의 아름다움이자 매우 유용한 점입니다.

점들의 집합 $I$에 대하여, 각 $i \in I$에 대한 $\phi$의 evaluation $\phi(i)$에 대한 증명을 batch로 한 번에 해봅시다.

먼저 $a(x) = \prod_{i \in I} (x-i)$를 계산합니다. 이는 FFT + Divide and Conquer로 $\mathcal{O}( \lvert I \rvert \log^2 \lvert I \rvert)$ 시간에 할 수 있습니다. 이제 $\phi$를 $a$로 나눠서 몫과 나머지를 얻습니다. 이 과정은 $\mathcal{O}(\lvert I \rvert \log \lvert I \rvert)$ 시간에 가능합니다. $\phi = aq + r$이라고 하면, batch proof는 $w = g^{q(\alpha)}$가 됩니다.

이를 verify 하는 입장에서는, 먼저 $I$와 ${\phi(i)}_{i \in I}$의 값들을 가지고 $\deg r = \lvert I \rvert - 1$이고 $r(i) = \phi(i)$가 각 $i \in I$에 대해서 성립하는 $r$을 Lagrange Interpolation을 통해서 구합니다. 이 과정 역시 $\mathcal{O}( \lvert I \rvert \log^2 \lvert I \rvert)$ 시간에 할 수 있습니다. 비슷하게 $a(x)$도 직접 계산하고, 이제

\[e(\mathcal{C}, g) = e(w, g^{a(\alpha)}) \cdot e(g^{r(\alpha)}, g)\]

임을 확인합니다. 물론, 이 식은 $\phi = aq + r$를 group 위에서 풀어쓴 것에 불과합니다.

Aggregatable Subvector Commitments

구현하고자 하는 명세는 다음과 같습니다. 모든 vector의 값은 $\mathbb{F}_p$의 원소들입니다.

• KeyGen
  • $n$을 입력받고, proving key $prk$, verification key $vrk$와 update key $upk_0, \cdots, upk_{n-1}$을 출력합니다.
  • $n$은 앞으로 다루게 될 vector의 길이를 의미합니다.
  • 이 함수는 맨 처음에 scheme의 세팅을 위해서 한 번 호출됩니다.
• Commit
  • vector $v$를 입력받고, 이에 대한 commitment $c$를 출력합니다.
• ProvePos
  • index의 집합 $I$와 vector $v$를 입력받고, $I$-subvector $v_I$에 대한 proof $\pi_I$를 출력합니다.
• VerifyPos
  • commitment $c$, $v_I$, $I$, $\pi_I$를 입력받고, proof $\pi_I$가 정당한지 여부를 출력합니다.
• VerifyUPK
  • index $i$와 update key $upk_i$를 입력받아, 제대로 된 update key인지 여부를 출력합니다.
• UpdateComm
  • commitment $c$, $\delta$, index $i$, update key $upk_i$를 입력받아, $v_i$에 $\delta$를 더하고 이에 대응하여 기존 commitment $c$를 새로운 commitment $c’$로 update 하여 반환합니다.
• UpdateProof
  • $\delta$, index $i, j$, update key $upk_i, upk_j$를 입력받아, $v_j$가 $v_j + \delta$로 update 되었을 때 $v_i$에 대한 증명 $\pi_i$를 새 증명 $\pi_i’$으로 update 하여 반환합니다. 이때 $i = j$일 수 있음에 유의합시다.
• AggregateProofs
  • 각 $i \in I$에 대해 $v_i$에 대한 증명 $\pi_i$가 주어졌을 때, 이를 합쳐서 $\pi_I$를 반환합니다.

KZG Commitments, Lagrange Polynomials

우선 계산을 쉽게 하기 위해서 $n$이 2의 거듭제곱이라 하고, $p-1$이 $n$의 배수라고 합시다. 이는 FFT 계열 알고리즘을 (정확히는, NTT 계열) 사용하기 위해 적합한 세팅입니다. 이제 $\mathbb{F}_p$ 위에서 $n$th roots of unity $\omega^i$를 생각할 수 있으며, Lagrange Polynomial

\[\mathcal{L}_i(x) = \prod_{j=0, j\neq i}^n \frac{x - \omega^j}{\omega^i - \omega^j} = \frac{1}{n} \sum_{j=0}^{n-1} \omega^{-ij} x^j\]

를 도입하면 $\mathcal{L}_i(\omega^j)$가 $i=j$일때 $1$, 아니면 $0$임을 알 수 있습니다.

vector와 다항식을 대응시키는 방법은 역시 Lagrange Interpolation이며, 이는 결국 $[v_0, v_1, \cdots, v_{n-1}]$을 $\phi(\omega^i) = v_i$인 다항식 $\phi$에 대응시키는 것과 같고, 즉

\[\phi = \sum_{i=0}^n \mathcal{L}_i v_i\]

과 같습니다. 이렇게 되면 KZG commitment의 값은

\[\mathcal{C} = g^{\phi(\alpha)} = \prod_{i=0}^n (g^{\mathcal{L}_i(\alpha)})^{v_i}\]

입니다. 이때 각 $l_i = g^{\mathcal{L}_i(\alpha)}$를 얻는것은 $g, g^\alpha, \cdots , g^{\alpha^n}$이 주어지면 NTT 한 번에 얻을 수 있습니다. 이제

\[\mathcal{C} = g^{\phi(\alpha)} = \prod_{i=0}^n l_i^{v_i}\]

로 쓸 수 있습니다. 이는 $v_i$가 $v_i+\delta$로 바뀐다면, 단순히 $l_i^\delta$를 $\mathcal{C}$에 곱해주면 된다는 뜻입니다.

한 원소 $v_i$에 대한 증명은 결국 $\phi(\omega^i)$에 대한 KZG evaluation proof가 되며, KZG batch proof가 가능하니 vector의 입장에서 보면 subvector proof도 충분히 가능한 상황입니다.

이제 Commit, ProvePos, VerifyPos, UpdateComm 작업은 KZG와 동일하게 할 수 있습니다.

문제는 UpdateProof와 AggregateProof, 그리고 update key의 설정입니다.

Proof Aggregation via Partial Fraction Decomposition

이제 $\phi(\omega^i)_{i \in I}$가 주어졌다고 가정했을 때, 이를 interpolate 하는 Lagrange Polynomial

\[\mathcal{L}_i (x) = \prod_{j \in I, j \neq i} \frac{x - \omega^j}{\omega^i - \omega^j}\]

를 생각하면, $a_I(x) = \prod_{i \in I} (x - \omega^i)$라 할 때

\[\mathcal{L}_i(x) = \frac{a_I(x)}{a_I'(\omega^i)(x - \omega^i)}\]

가 성립합니다. $\phi = \sum_{i \in I} \mathcal{L}_i \phi(\omega^i)$이므로 이를 정리하면

\[\phi = \sum_{i \in I} \phi(\omega^i) \cdot \frac{a_I(x)}{a_I'(\omega^i)(x - \omega^i)}\]

입니다. 여기에 $\phi = 1$을 대입하면

\[1 = \sum_{i \in I} \frac{a_I(x)}{a_I'(\omega^i)(x - \omega^i)}\]

를 얻습니다. 이 사실이 KZG proof를 aggregate 하는데 사용됩니다.

$\pi_i$가 $v_i$에 대한 proof라면, 이는 group에서 다항식 $\frac{\phi(x) - v_i}{x - \omega^i}$에 대응되는 값입니다. $\pi_I$가 $v_I$에 대한 proof라면, 이는 group에서 다항식 $\frac{\phi(x) - r(x)}{a_I(x)}$에 대응되는 값입니다. 결국 이 값들 사이의 관계식을 이끌어낼 수 있다면, proof aggregation이 완료되겠죠. 다시 Lagrange Interpolation 공식

\[r(x) = \sum_{i \in I} v_i \cdot \frac{a_I(x)}{a_I'(\omega^i) (x - \omega^i)}\]

임을 생각하면, 결국

\[\frac{\phi(x) - r(x)}{a_I(x)} = \sum_{i \in I} \frac{\phi(x)}{a_I'(\omega^i)(x - \omega^i)} - \sum_{i \in I} \frac{v_i}{a_I'(\omega^i) (x - \omega^i)} = \sum_{i \in I} \frac{1}{a_I'(\omega^i)} \cdot \frac{\phi(x) - v_i}{x - \omega^i}\]

입니다. 이는 결국 $a’_I(\omega^i)$를 각 $i \in I$에 대해서만 알면 proof aggregation이 된다는 의미입니다. 이는 $a_I$를 FFT + Divide and Conquer로 계산하고, 직접 미분한 다음, multipoint evaluation technique를 사용하면 $\mathcal{O}(\lvert I \rvert \log^2 \lvert I \rvert)$ 시간에 할 수 있습니다. 이 아이디어를 완성하는데도 Vitalik이 참여했다고 하네요.

Proof Update, and Update Keys

기본적으로 각 증명은 $\frac{\phi(x) - v_i}{x - \omega^i}$에 대응되는 group의 원소입니다. 결국 각 update에 대해서 이 값이 어떻게 변화하는지만 잘 파악하면 됩니다. 만약 $i = j$라면, $\phi$는 $\delta \mathcal{L}_i(x)$만큼 증가하며 $v_i$는 $\delta$만큼 증가합니다. 결국 이 값은

\[\delta \cdot \frac{\mathcal{L}_i(x) - 1}{x - \omega^i}\]

만큼 증가하게 됩니다. 여기서

\[u_i = g^{\frac{\mathcal{L}_i(\alpha) - 1}{\alpha - \omega^i}}\]

라 하면, 이는 $\mathcal{L}_i(\omega^i) = 1$에 대응되는 KZG proof가 됩니다.

$i \neq j$인 경우에는 조금 더 계산이 필요한데, 값은

\[\delta \cdot \frac{\mathcal{L}_j(x)}{x - \omega^i}\]

만큼 증가하게 됩니다. 계산을 조금 해보면

\[\frac{\mathcal{L}_j(x)}{x- \omega^i} = \frac{1}{n} \omega^j \cdot \frac{x^n - 1}{(x-\omega^i)(x-\omega^j)} = \frac{1}{n} \omega^j \cdot \left( \frac{1}{\omega^i - \omega^j} \cdot \frac{x^n - 1}{x - \omega^i} - \frac{1}{\omega^i - \omega^j} \cdot \frac{x^n - 1}{x - \omega^j} \right)\]

입니다. 그러니

\[a_i = g^{\frac{\alpha^n - 1}{\alpha - \omega^i}}\]

라 하면 이는 $x^n$에 대한 KZG proof가 됩니다.

결국 필요한 update key들은 $a_i, u_i$들이 되겠습니다. 이 값들을 $0 \le i < n$에 대해서 전부 계산하는 것은 FFT technique를 (특히 FK20에서 등장한 FK technique - 이에 대해서는 https://alinush.github.io 의 KZG 관련 글들을 읽는 것이 가장 빠릅니다. 재밌으니 읽어보세요.) 이용하여 할 수 있습니다.

update key들의 특수한 형태 때문에, 이들을 verify 하는 것이 가능합니다. 예를 들어,

\[e(a_i, g^\alpha \cdot g^{-\omega^i}) = e(g^{\alpha^n} \cdot g^{-1}, g)\]

를 확인하여 $a_i$가 정확한 값인지를 파악할 수 있습니다.

비슷하게 $u_i$도 verify가 가능하고, 이는 채굴자들이 update key를 따로 보관해야 할 필요를 없애줍니다.

이제 UpdateProof, AggregateProof, VerifyUPK 과정도 모두 설계가 완료되었습니다.

KeyGen에서는 앞서 등장한 $l_i, a_i, u_i$ 및 Powers of Tau로 생성된 값들을 준비하면 됩니다.

Stateless Cryptocurrencies from ASVC

기본적인 세팅은 Aggregatable Subvector Commitment에서 다 되어있습니다.

여기에 몇 가지를 추가하면 암호화폐 체계가 됩니다. 추가해야 하는 것의 목록을 간단하게 정리해봅니다. 이를 직접 추가하는 것은 두 번째 논문의 Section 4에 정리되어 있으나, 이에 대해 직접 생각해보는 것이 꽤 재밌기 때문에 여기에는 간단한 힌트만 작성하겠습니다. 블록체인 기술 자체에 관심이 있으시다면 꼭 풀어보세요.

암호화폐의 기본적인 구조는 다음과 같습니다.

• vector에 저장하는 값은 각 사용자의 balance가 됩니다.
• 각 update key는 각 사용자가 가져가게 됩니다.
• 각 사용자는 transaction을 보낼 때마다 자신의 KZG proof를 이용해서 자신의 balance를 증명합니다.
• 각 사용자는 자신의 update key와 KZG proof만 잘 가지고 있으면 충분합니다.
• 채굴자는 전체 상태에 대한 commitment 만을 다루면 충분합니다.

이때, 여러분이 해결해야 하는 문제는 다음과 같습니다.

• 이때, transfer를 어떻게 처리해야 할지 채굴자나 각 사용자의 입장에서 생각해야 합니다.
• Transaction Fee를 추가한다면, 어떻게 구현하는 게 좋을까요?
• Commitment Scheme은 준비되었지만, 이더리움과 마찬가지로 기본적인 digital signature scheme이 있어야 합니다. 이를 위해서는 ECDSA를 암호화폐 체계에 추가해야 합니다. 어떻게 할까요?
• 위 질문에 이어서, ECDSA signature replay attack을 어떻게 막을지 고민해야 합니다.
• 새로운 사용자의 추가를 어떻게 처리해야 할지 고민해야 합니다. 이 구조에서는 $n$이 고정이기 때문에, Denial-of-Service Attack이 가능합니다 (사용자 등록 무한반복). 이를 어떻게 막아야할까요?

결론

지금까지 polynomial에 대한 commitment scheme 중 대표적인 KZG commitment에 대해서 알아보았고, 이를 강화하여 aggregation까지 지원하는 Aggregatable Subvector Commitments에 대해서 알아보았습니다. 또한, 이를 활용하여 간단한 transfer transaction을 지원하는 사용자 및 채굴자 입장에서 매우 효율적인 암호화폐 체계를 구축할 수 있음을 알아보았습니다. 전체적으로 되게 재밌고 유용한 논문 같습니다 :)