rkm0959's profile image

rkm0959

June 13, 2022 00:00

논문은 https://eprint.iacr.org/2022/621 입니다.

선행지식

• https://github.com/rkm0959/rkm0959_presents/blob/main/TornadoCash.pdf
• https://www.secmem.org/blog/2022/05/15/KZG-ASVC/
• 정확히는, Powers of Tau 및 KZG Commitment 계열 이론, ZK 계열 이론 기초

Membership Proofs in Zero Knowledge

우리의 목표는 집합 $S$가 있을 때, 어떤 $v$가 $v \in S$를 만족한다는 사실을 영지식으로 증명하는 겁니다.

이를 위해서 사용된 대표적인 방법이 두 가지가 있는데, 하나는 Tornado Cash에서 사용하고 있는 것과 같은 Merkle Tree + zkSNARKS입니다. 적당한 hash function을 기반으로 한 Merkle Tree를 만들고, 자신이 갖고 있는 원소가 leaf 중 하나임을 Merkle Proof로 보일 수 있습니다. 이 증명을 영지식으로 하기 위해서, zkSNARKs를 도입할 수 있습니다. Tornado Cash에서는 Merkle Tree를 구축하기 위해서 MiMC hash function을 사용하였으나, ZK-friendly한 hash function에 대한 연구는 활발하게 진행되었기 때문에 현재 State of the Art는 Poseidon hash function이라고 볼 수 있습니다. 즉, Merkle Tree + Poseidon Hash로 문제를 해결할 수 있습니다.

또 다른 방식은 RSA Accumulator입니다. 이에 대해서는 논문을 첨부하며, 추후에 글을 작성할 수도 있습니다.

• https://cs.brown.edu/people/alysyans/papers/camlys02.pdf
• https://eprint.iacr.org/2021/1672.pdf

이 논문에서는 KZG Commitment와 Pedersen Commitment를 기반으로 하는 membership proof 방식인 Caulk를 소개합니다. KZG를 사용하니까 Trusted Setup이 필요하지만 이는 Powers of Tau로 충분합니다. $m$개의 원소의 membership proof를 한 번에 증명하기 위해서, 다음과 같은 시간복잡도가 필요합니다. 단, $\lvert S \rvert = N$.

• Merkle Tree + Hash : Prover 연산 $\mathcal{O}(m \log N)$, Verifier 연산 Pairing 2회
• Caulk : Prover 연산 $\mathcal{O}(m^2 + m\log N)$, Verifier 연산 Pairing 4회

하지만 Merkle Tree + Hash는 기본적으로 hash function을 zkSNARKs 안으로 인코딩하기 위한 overhead가 상당해서, 실제로는 Caulk가 대략 100배 정도 빠르다고 합니다. 본 논문의 Section 9를 참고하세요.

논문에서는 $m = 1$인 경우와 $m > 1$인 경우를 따로 설명하고, 실제로 $m > 1$인 경우에서 추가적으로 할 일들이 많아집니다. 이 글에서는 간략하게 $m = 1$인 경우만을 설명하도록 하겠습니다.

Basic Setting of Caulk, $m = 1$

기본적인 KZG Commitment의 세팅을 그대로 가져갑니다.

• Pairing이 되는 group $G_1, G_2, G_T$가 있어야 합니다.
• $G_i$에서 generator $g_i$를 가져오고, $e(g_1, g_2) = g_T$라 합니다.
• $[x]_i = x g_i$라고 정의합니다.
• Powers of Tau 세팅을 거칩니다. 이는 $[x^i]_{1, 2}$가 $0 \le i \le d$에 대해서 계산되었음을 의미합니다.
• $\omega^i$들을 모두 roots of unity라고 합시다. 여기서 $N$은 물론 2의 거듭제곱.
• $\lambda_i(x)$를 $\lambda_i(\omega^j) = \delta_{ij}$를 만족하는 Lagrange Basis라고 합시다.

일단 우리의 목표는 집합 $S$와 그에 대한 commitment $C$와, membership을 체크할 원소 $v$에 대한 commitment $C’$이 주어졌을 때, $C$와 $C’$만을 가지고 $v \in S$인지를 확인하는 것입니다. 물론, $m > 1$인 경우에는 $v$가 원소가 아니라 하나의 집합이 됩니다. 어떤 commitment를 사용하는지 봅시다.

이를 위해서, 집합을 commit 하는 경우에는 집합을 벡터 $c = (c_0, c_1, \cdots, c_{N-1})$이 있으면 이를 $f(\omega^i) = c_i$를 만족하는 degree $N$ 미만의 다항식으로 대응시킨 후, 이 다항식에 대한 KZG Commitment $C$를 생각합니다.

원소 $v$를 commit 하는 경우에는, hiding을 만족시키기 위해 Pedersen Commitment를 이용합니다. 이를 위해서, KZG Commitment를 세팅하기 위한 작업을 거칠 때 랜덤한 $h$를 하나 생성해서 $hg_1 = [h]_1$을 Structured Reference String에 추가하게 합니다. 물론 $h$의 값은 Powers of Tau에서 하듯이 아무도 모르게 합니다. 이제 랜덤한 $r$을 생성한 후, $[v]_1 + r[h]_1 = [v + rh]_1$을 계산하면 이게 Pedersen Commitment $C’$가 됩니다.

결국 우리의 목표는, $C, C’$가 주어졌을 때,

• 적당한 index $i$가 있어 $C$의 $\omega^i$에서의 evaluation이 $C’$에서 commit한 값과 같음

을 증명해야 합니다. 여기서 ZK임을 확정하려면 $i$까지 숨겨야 합니다.

Part 1 : Evaluation Check via Blinding

일단 계산 자체를 어떻게 ZK로 하는지 봅시다. 기본적인 KZG를 하려면 우선

\[C(X) = \sum_{i=0}^{N-1} c_i \lambda_i(X)\]

를 생각하고, KZG의 evaluation proof을 하기 위해서

\[q(X) = \frac{C(X) - v}{X - \omega^i}\]

를 생각해야 합니다. 그런데 일단 실제 KZG의 evaluation proof에서는 verifier가 evaluation point인 $\omega^i$의 값을 알고 $[x - \omega^i]_2$를 사용하게 됩니다. 지금은 $\omega^i$도 모르게 해야 하니, 추가적인 절차가 필요합니다.

이를 위해서, 랜덤한 $a$를 하나 생성하고 $z(x) = ax - b = a(x - \omega^i)$라고 두고 $[z(x)]_2$를 준비합니다.

추가된 blinding factor $a$를 고려해주기 위해서, prover는 blinding factor $s$를 하나 추가하고

\[T(X) = \frac{q(X)}{a} + hs, \quad S(X) = -r - sz(X)\]

를 계산합니다. 이제 다음 식이 성립함을 단순 계산으로 얻을 수 있습니다.

\[C(X) - v - hr = T(X) z(X) + h S(X)\]

이를 확인하기 위해서 verifier는 다음과 같은 pairing check를 할 수 있습니다.

\[e(C C'^{-1}, [1]_2) = e([T]_1, [z]_2) e([h]_1, [S]_2)\]

여기서 $[T]_1$은 prover 역시 $[h]_1$을 알고 있으니 계산할 수 있습니다.

돌아보면, $[T]_1$을 보내는 과정에서 $q(X) / a$를 완전히 숨기기 위해 blinding factor $s$를 추가했음을 알 수 있습니다.

이제 확인해야 하는 것은 다음 두 가지입니다.

• $C’$이 정말 Pedersen Commitment인지 (Prover가 실제로 $C’$을 open 할 수 있는지) ZK 증명
• $z(x) = a(x - \omega^i)$가 정말 맞는지를 ZK 증명

전자는 Pedersen Commitment를 위한 전형적인 Sigma Protocol을 사용하면 됩니다. 후자가 문제입니다.

참고 : 위 과정은 적당한 precomputation을 거친 이후에는 매우 빠르게 할 수 있습니다. 단순하게 생각하면 bottleneck은 $[q(x)/a]_1$을 구하는 건데, $a$를 prover가 결정하기 때문에 $[q(x)]_1$만 prover가 미리 구해놓으면 충분합니다. 이는 FK technique로 가능합니다. 이에 대한 글을 아래에 링크해놓았습니다.

• https://alinush.github.io/2021/06/17/Feist-Khovratovich-technique-for-computing-KZG-proofs-fast.html

Part 2 : Unity Check for $\omega^i$

Prover가 증명하고자 하는 것은 다음과 같습니다. $[z(x)]_2 = [a(x - \omega^i)]_2$가 주어졌을 때,

• $z(x) = ax - b$인 $a, b$를 Prover가 알고 있으며
• $b/a = \omega^i$가 $N$th root of unity, 즉 $a^N = b^N$이 성립

이를 위해서, 위 조건들을 만족하는 $z$만이 갖는 성질을 압축된 형태로 가져옵니다.

정리 : $z$가 degree $1$의 polynomial이라 합시다. $n = \log N + 6$이라 하고, $\sigma^n = 1$인 $\sigma$가 있습니다. 이때, $f \in \mathbb{F}[X]$가 있어

• $f(1) = z(1)$
• $f(\sigma) = z(\sigma)$
• $f(\sigma^2)(1-\sigma) = f(1) - f(\sigma)$
• $f(\sigma^3) = \sigma f(\sigma^2) - f(\sigma)$
• $f(\sigma^4) f(\sigma^3) = f(\sigma^2)$
• $f(\sigma^{4+\log N}) = 1$
• $f(\sigma^{4+i+1}) = f(\sigma^{4+i})^2$가 $0 \le i < \log N$에서 성립

이라면, $z(X) = aX - b$이며 $b/a$는 $N$th root of unity이다.

증명 : 단순 계산입니다. $z(X) = aX - b$라고 하고 계산해보면,

• $f(1) = a - b$
• $f(\sigma) = a\sigma - b$
• $f(\sigma^2) = a$
• $f(\sigma^3) = b$
• $f(\sigma^4) = a / b$
• $f(\sigma^{4+i}) = (a/b)^{2^i}$, i.e. $1 = f(\sigma^{4+\log N}) = (a/b)^N$

가 성립합니다. 물론, 우리는 이를 통해서 $f$를 구축할 수 있습니다.

${\rho_i(X)}$를 $V_n = {\sigma^0, \cdots , \sigma^{n-1}}$에 대한 Lagrange Basis라고 하면,

\[f(X) = (a - b) \rho_0(X) + (a \sigma - b) \rho_1(X) + a \rho_2(X) + b \rho_3(X) + \sum_{i=0}^{\log N} (a/b)^{2^i} \rho_{4+i} (X)\]

를 준비하면 이 다항식은 원하는 모든 조건을 만족합니다.

이제 문제는 위 성질들을 verifier가 검증하기 쉽게 준비해주는 것입니다.

이를 위해서, $f$가 가지고 있는 성질들을 통해서

\[z_{V_n}(X) = (X - \sigma^0)(X-\sigma^1) \cdots (X-\sigma^{n-1})\]

의 배수가 되는 다항식을 구축합니다. 이를 구축하기 위해서 예시를 두 개 들어봅니다.

• $x = 1, \sigma$면 $f(x) - z(x) = 0$입니다. $x \in V_n \setminus {1, \sigma}$라면, $\rho_0(x) + \rho_1(x) = 0$입니다.
• $x = \sigma^2$이라면 $(1-\sigma)f(x) = f(x \sigma^{-2}) - f(x \sigma^{-1})$입니다. $x \in V_n \setminus { \sigma^2 }$이라면, $\rho_2(x) = 0$입니다.

그렇다면,

\[(f(X) - z(X))(\rho_0(X) + \rho_1(X)) \equiv 0 \pmod{z_{V_n}(X)}\] \[((1-\sigma)f(X) - f(X \sigma^{-2}) + f(X \sigma^{-1})) \rho_2(X) \equiv 09 \pmod{z_{V_n}(X)}\]

등이 성립해야 합니다. 이 방식으로 계속해나가면,

\[(f(X) - z(X))(\rho_0(X) + \rho_1(X)) + ((1-\sigma)f(X) - f(X \sigma^{-2}) + f(X \sigma^{-1})) \rho_2(X)\] \[+ (f(X) + f(X \sigma^{-2}) - \sigma f(X \sigma^{-1})) \rho_3(X) + (f(X) f(X\sigma^{-1}) - f(X\sigma^{-2})) \rho_4(X)\] \[+ (f(X) - f(X \sigma^{-1})^2) \prod_{i \in \{0, 1, 2, 3, 4, n-1\}} (X - \sigma^i) + (f(X \sigma^{-1}) - 1) \rho_{n - 1}(X)\]

라는 거대한 다항식이 $z_{V_n}(x)$의 배수가 되는 것이 $f$에 대한 모든 조건을 encode 한다고 볼 수 있습니다.

이 거대한 다항식을 $p(X)$라고 부르겠습니다. 이제 해야하는 것은

• $f(X)$에 대한 commitment를 계산해서 verifier에게 전달하고
• $p(X)$가 실제로 위 식과 같은 방식으로 계산되었음을 verifier에게 증명하고
• $p(X)$가 $z_{V_n}(X)$의 배수임을 verifier에게 증명

하는 것입니다. 보통 이러한 증명을 위한 전형적인 방법은 다음과 같습니다.

Step 1. Prover의 KZG Commitment 전달

우선 $h(X) = p(X) / z_{V_n}(X)$를 계산합니다. 이제 $[f(x)]_1$와 $[h(x)]_1$을 전달합니다.

Step 2. Verifier의 Challenge 전달

Verifier가 challenge $\alpha$를 uniformly random하게 선택하여 전달합니다.

Step 3. Prover의 KZG evaluation proof 전달

Prover가 $f(\alpha)$, $h(\alpha)$에 대한 evaluation proof를 전달합니다.

Step 4. Verifier의 최종 계산

Verifier가 Prover의 evaluation proof를 검증하고, $p(\alpha), h(\alpha), z_{V_n}(\alpha)$를 계산하여 다음을 검증합니다.

\[p(\alpha) = h(\alpha) z_{V_n}(\alpha)\]

보통 이렇게 하면 Schwartz-Zippel Lemma를 적용해서 증명이 완료되는데, 지금은 상황이 조금 다릅니다.

• 우선 계산 과정에서 $z(X)$가 들어가는데 우리가 공개하고 있는 것은 $[z(x)]_2$가 전부입니다.
• $p(X)$에는 $f(X)$도 들어있지만 $f(X \sigma^{-1})$, $f(X\sigma^{-2})$ 등도 들어있습니다.
• 사실 $z(X)$가 degree 1 다항식이라는 사실도 증명을 하고 넘어가야 합니다.
• Zero Knowledge를 위해서는 $f, h$ 등에 blinding factor를 추가해야 합니다.

그래서 우리가 얻는 최종 프로토콜은 약간 더 생각을 해야 얻을 수 있습니다.

Step 1. Prover의 Blinding 및 KZG Commitment 전달

우선 Blinding을 위해서 $r_0, r_1, r_2, r_3$를 $\mathbb{F}$에서 랜덤하게 가져옵니다. 이제

\[f(X) = (a - b) \rho_0(X) + (a \sigma - b) \rho_1(X) + a \rho_2(X) + b \rho_3(X) + \sum_{i=0}^{\log N} (a/b)^{2^i} \rho_{4+i} (X)\] \[+ r_0 \rho_{n-1} (X) + (r_1 + r_2 X + r_3X^2) z_{V_n}(X)\]

라 합니다. 두 번째 줄에 적은 식들이 blinding을 위해서 추가되는 값들입니다.

이제 $p(X)$를 앞에서와 마찬가지로 정의하고,

\[\hat{h}(X) = \frac{p(X)}{z_{V_n}(X)}, \quad h(X) = \hat{h}(X) + X^{d-1} z(X)\]

라고 합니다. 이제 $[F]_1 = [f(x)]_1$과 $[H]_1 = [h(x)]_1$을 전달합니다.

참고 : Powers of Tau 세팅이 $[x^0]_1$부터 $[x^d]_1$까지 되었다면, $[x^{d-1}z(x)]_1$을 계산할 수 있기 위해서는 $z$가 일차식인 것이 필수입니다. 즉, $z$가 degree 1이라는 것을 강제하기 위해서 추가된 장치가 $x^{d-1}z(x)$입니다.

Step 2. Verifier의 Challenge 전달

Verifier가 challenge $\alpha$를 uniformly random하게 선택하여 전달합니다.

Step 3. Prover의 evaluation proof

이제 $\alpha_1 = \alpha \sigma^{-1}$, $\alpha_2 = \alpha \sigma^{-2}$라 합시다. $f$를 $\alpha_1, \alpha_2$에서 evaluate한 결과가 필요하니까, 이를 제공해야 합니다.

즉, $v_1 = f(\alpha_1)$, $v_2 = f(\alpha_2)$를 계산하고 이에 대한 KZG evaluation proof를 준비합니다. 이제

\[p_\alpha(X) = -z_{V_n}(\alpha) \hat{h}(X) + (f(X) - z(X))(\rho_0(\alpha) + \rho_1(\alpha)) + ((1-\sigma)f(X) - v_2 + v_1) \rho_2(X)\] \[+ (f(X) + v_2 - \sigma v_1) \rho_3(X) + (f(X) v_1 - v_2) \rho_4(X) + (f(X) - v_1^2) \prod_{i \in \{0, 1, 2, 3, 4, n-1\}} (X - \sigma^i) + (v_1 - 1) \rho_{n - 1}(X)\]

라고 하면 $p_\alpha(\alpha) = 0$이 성립해야 합니다. 이를 증명하기 위해서 KZG proof인

\[\pi = \left[ \frac{p_\alpha(x)}{x - \alpha} \right]_1\]

를 전달합니다. 물론 $v_1, v_2$의 값과 그에 대한 KZG proof도 전달합니다.

Step 4. Verifier의 최종 계산

우선 $v_1, v_2$에 대한 KZG proof를 검증합니다. 이제 verifier가

\[[P]_1= -z_{V_n}(\alpha) [H]_1 + (\rho_0(\alpha) + \rho_1(\alpha)) [F]_1 + \rho_2(\alpha) ((1-\sigma)[F]_1 + [v_1 - v_2]_1)\] \[+ \rho_3(\alpha) ([F]_1 + [v_2 - \sigma v_1]_1 ) + \rho_4(\alpha) (v_1 [F]_1 - [v_2]_1) + \prod_{i \in \{0, 1, 2, 3, 4, n-1\}} (\alpha - \sigma^i) ([F]_1 - [v_1^2]_1) +\rho_{n - 1}(\alpha) [v_1 - 1]_1\]

를 계산합니다. 이 값은 전체적으로 다 동일하지만, $z(X)$에 대한 부분이 빠졌습니다.

실제로, $P = p_\alpha(x) - z_{V_n}(\alpha) x^{d-1} z(x) + (\rho_0(\alpha) + \rho_1(\alpha)) z(x)$가 성립합니다.

그러므로, 검증을 하기 위해서는

\[e([P]_1, [1]_2) e(z_{V_n}(\alpha) [x^{d-1}]_1 - [\rho_0(\alpha) + \rho_1(\alpha)]_1, [z(x)]_2) = e(\pi, [x - \alpha]_2)\]

가 성립하는지 확인하면 됩니다. 이제 모든 과정이 끝났습니다.

Conclusion

지금까지 Caulk를 알아보았습니다. 훨씬 더 빠른 prover time이 가능한 알고리즘으로, 단일 membership proof과 batch membership proof가 모두 가능한 알고리즘이었습니다. Merkle Tree + Poseidon Hash보다 빠르기 때문에, 자연스럽게 Tornado Cash와 같은 private transaction을 위해서 사용될 수 있는지 고민할 수 있습니다. 하지만 zkSNARKs의 일반적인 연산을 지원하는 강력함이 없어서 그런지, double spending을 nullifier를 통해서 막는 과정을 추가하는 것이 매우 어려워보입니다. 그래서 Caulk는 빠른 zero knowledge lookup이라는 개념으로 생각하는 것이 더욱 적합할 것 같습니다. 글 읽어주셔서 감사하고, 질문은 rkm0959.tistory.com에서 받습니다.