rkm0959's profile image

rkm0959

March 17, 2022 00:00

서론

최근 회사에서 Groth16, Powers of Tau, Tornado Cash에 대한 세미나를 진행했습니다.

이번 글에서는 해당 세미나의 첫 주제인 Groth16에 대해서 정리하는 시간을 갖겠습니다.

세미나 발표자료는 https://github.com/rkm0959/rkm0959_presents/blob/main/TornadoCash.pdf 에서 확인하실 수 있습니다.

Zero Knowledge Proof (ZKP)

Zero Knowledge Proof란, 비밀키의 소유를 증명하고자 하는 사람이 자신의 소유 사실에 대한 증명을 하되, 이를 넘어선 다른 정보는 아예 공개되지 않도록 하는 방법론입니다.

예를 들어서, Discrete Logarithm 문제가 있다고 합시다. $G$는 $\lvert G \rvert =q$가 소수인 generic group이고, $g, h$가 $G$의 generator이자 public한 값들이라고 할 때, $h=g^\alpha$를 만족하는 $\alpha$를 알고 있다는 사실을 어떻게 $\alpha$를 공개하지는 않으면서 증명할 수 있을까요?

이에 대해서 알아보기 전에, 우선 ZK를 수학적으로 엄밀히 정의해봅시다.

Prover와 Verifier 사이의 Interaction이 가능한 경우, ZK는

• Completeness : Honest Prover는 증명에 성공
• Zero-Knowledge : Verifier는 증명으로부터 아무런 추가적인 사실을 얻을 수 없음. 실제로는, Prover-Verifier의 통신 내역이 속한 확률분포를 $\alpha$ 없이 public value들만 가지고도 만들어낼 수 있으며, 이 확률분포를 만들어내는 알고리즘을 Simulator라 함.
• Computational Knowledge Soundness : Prover가 (Adversarial 할 수도 있음) 증명에 성공했다면, 매우 높은 확률로 Prover의 내부 상태를 갖고 비밀을 도출해낼 수 있는 extractor 알고리즘이 존재함

를 만족해야 합니다.

이제 Discrete Logarithm 문제에 대한 ZKP Protocol인 Schnorr’s Protocol을 봅니다. 다음과 같은 통신을 합니다.

• Prover는 random $\alpha_t \in \mathbb{F}_q$를 고르고 $u_t = g^{\alpha_t}$를 Verifier에게 보냄
• Verifier는 random challenge $c \in \mathbb{F}_q$를 Prover에게 보냄
• Prover는 $\alpha_z = \alpha_t + \alpha c \in \mathbb{F}_q$를 Verifier에게 보냄
• Verifier는 $g^{\alpha_z} = u_t \cdot h^c$를 검증함

이제, 이것이 ZKP인지 검증해봅시다.

• Completeness는 자명. 정직하게 하면 됩니다.
• Zero-Knowledge : $(u_t, c, \alpha_z) = (g^{\alpha_z} h^{-c}, c, \alpha_z)$가 Simulator가 됩니다.
• Computational Knowledge Soundness : Verifier가 두 challenge $c_1, c_2$를 보냈을 때 둘 다 성공한다면 일차방정식을 풀어서 $\alpha$를 도출할 수 있습니다. 이 사실을 활용하여, Discrete Logarithm이 어렵다면 증명을 만들어내는 것 역시 어려움을 증명할 수 있습니다. 엄밀한 논리는 Rewinding Lemma 등을 활용하며, 아래에 있는 제 블로그의 링크를 사용해주세요.

추가적으로, Random Oracle Model을 이용하여 $c$를 deterministic하게 고르고, interaction을 제거하는 Schnorr’s Signature도 있습니다. Schnorr’s Protocol에 대한 자세한 내용은 https://rkm0959.tistory.com/202 를 참고해주세요.

Groth16 Protocol

Groth16은 덧셈과 곱셈으로 이루어진 arithmetic circuit을 consistent 하게 만드는 값들을 알고 있다는 사실을 ZK로 증명할 수 있게 해주는 기법입니다.

먼저, 주어진 시스템의 형태를

\[\sum_{i=0}^m a_i u_{i, q} \cdot \sum_{i=0}^m a_i v_{i, q} = \sum_{i=0}^m a_i w_{i, q}\]

로 씁시다. 단, $u_{i, q}, v_{i, q}, w_{i, q}$는 public한 계수들입니다.

underlying field $F$의 크기가 충분히 크다면, Lagrange Interpolation으로

\[u_i(r_q) = u_{i, q}, \quad v_i(r_q) = v_{i, q}, \quad w_i(r_q) = w_{i, q}\]

를 만족하는 다항식 $u_i, v_i, w_i$를 찾을 수 있습니다. 이를 정리하면

\[\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)\]

를 만족하는 $a_1, \cdots , a_m$을 찾는 문제가 됩니다. 물론, 이때

\[t(x) = \prod_{i=1}^n (x - r_i)\]

$a_0 = 1$, $a_1, \cdots , a_l$은 public입니다. 이제 목표는 $a_{l+1}, \cdots , a_m$을 안다는 것을 증명하는 겁니다.

이를 위해서,

• Non-Interactive Linear Proof
• Homomorphic Hidings

에 대해서 알아봅시다.

Non-Interactive Linear Proof

$\mathcal{R}$이 효율적으로 확인 가능한 relation이라 합시다.

$(\phi, \omega) \in \mathcal{R}$이라면, $\phi$를 statement라 하고 $\omega$를 witness라 합니다.

우선 Non-Interactive ZK의 정의를 봅시다.

다음 4가지가 준비되어야 합니다.

• $(\sigma, \tau) \leftarrow \text{Setup}(\mathcal{R})$, providing CRS $\sigma$ and simulation trapdoor $\tau$
• $\pi \leftarrow \text{Prove}(\mathcal{R}, \sigma, \phi, \omega)$, providing proof of knowledge
• $0/1 \leftarrow \text{Verify}(\mathcal{R}, \sigma, \phi, \pi)$ which verifies the proof
• $\pi \leftarrow \text{Sim}(\mathcal{R}, \tau, \phi)$, which simulates the proof with the trapdoor

CRS는 Common Reference String으로, Prover/Verifier가 공통으로 사용할 수 있는 public한 값들입니다. 후에 Powers of Tau라는 과정으로 CRS를 안전하게 생성하게 됩니다.

Non-Interactive Linear Proof는 증명 방식이 조금 특수합니다.

• $\pi \leftarrow \text{Prove}(\mathcal{R}, \sigma, \phi, \omega)$ generates the proof - here, it runs $\Pi \leftarrow \text{ProofMatrix}(\mathcal{R}, \phi, \omega)$ then constructs the proof as $\pi = \Pi \sigma$

즉, 증명이 CRS의 linear combination이어야 하며, 그 계수는 CRS와 independent하며 statement, witness에만 dependent 할 수 있습니다.

Groth16의 단순 NILP 버전의 CRS는 다음과 같습니다. 먼저 $\alpha, \beta, \delta, x$를 $\mathbb{F}^\star$에서 뽑고,

• $\beta, \delta$
• $x^i$ for $0 \le i \le 2n-2$
• $\alpha x^i$ for $0 \le i < n$
• $\beta x^i$ for $1 \le i < n$
• $\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta}$ for $l+1 \le i \le m$
• $\frac{x^i t(x)}{\delta}$ for $0 \le i \le n-2$

가 CRS가 됩니다. 이때, $n = \deg t$입니다. simulation trapdoor는 $\tau = (\alpha, \beta, \delta, x)$.

증명을 위해서는, $a_1, \cdots , a_m$을 준비하고 $r, s$를 $\mathbb{F}$ 위에서 랜덤하게 뽑은 뒤

\[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 = \frac{\sum_{i=l+1}^m a_i(\beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x) t(x)}{\delta} + As + rB - rs \delta\]

를 줍니다. 증명이 $A, B, C$ 원소 세 개로 이루어진 겁니다.

이를 확인하기 위해서는,

\[A \cdot B = \alpha \cdot \beta + \sum_{i=0}^l a_i (\beta u_i(x) + \alpha v_i(x) + w_i(x)) + C \cdot \delta\]

를 확인하면 되며, simulator 역시 위 식이 만족하는 $(A, B, C)$를 랜덤하게 뽑으면 됩니다.

이 프로토콜에서 확인할 점들은 다음과 같습니다.

• Completeness는 단순 계산으로 증명됩니다.
• 위 증명 방식은 NILP의 정의를 만족합니다. 즉, $A, B, C$는 CRS의 선형결합.
• $r, s$ 값의 도입으로 $A, B$의 값이 랜덤화되어, Zero Knowledge가 됩니다.
• 단순하게 생각하면 Knowledge Soundness는 성립하지 않습니다.
• 그러나, Prover가 CRS의 선형결합으로 증명해야 한다면 Knowledge Soundness가 성립합니다. 이는 Schwartz-Zippel Lemma + 계수비교법으로 증명되는데, 자세한 건 [Groth16] 원 논문을 참고하는 것을 추천합니다. 자주 사용되는 기법입니다.
• $u_i, v_i, w_i$는 전처리가 가능하므로, 전처리가 되었다는 가정하에서 증명의 생성은 $\mathcal{O}(m)$, 증명의 검증은 $\mathcal{O}(l) \approx \mathcal{O}(1)$에 가능합니다. 검증이 빠르다는 것이 장점.

하지만 이 상태에서는 모든 값이 공개되어 있으니 보안성이 아예 없습니다.

이를 해결하기 위해서, 암호화된 상태에서 계산하는 Homomorphic Hiding이 필요합니다.

Homomorphic Hidings

잠시 additive notation을 이용하겠습니다.

덧셈 : Discrete Logarithm이 어려운 group $G$를 준비합시다. 단, $\lvert G \rvert =q$는 소수입니다. 이제, generator $g$를 하나 공개적으로 고정합시다. $a \in \mathbb{F}_q$를 숨기기 위해서 $E(a) = ag$를 사용하면 $E(a) + E(b) = E(a+b)$라는 놀라운 성질을 얻을 수 있습니다. $E(a)$에서 $a$를 복구하지 못하니, $E$를 통해서 우리는 덧셈을 숨겨진 상태에서 할 수 있는 거죠.

곱셈 : 곱셈을 위해서는 Bilinear Pairing을 알아야 합니다.

$G_1, G_2, G_T$가 각각 order $q$인 group이라 합시다. $e : G_1 \times G_2 \rightarrow G_T$가

• 각 $a, b \in \mathbb{F}_q$, $P, Q \in G_1, G_2$에 대해서 $e(aP, bQ) = ab \cdot e(P, Q)$
• $e$는 non-trivial 하지만 efficiently computable

이라면 $e$를 Bilinear Pairing이라고 부릅니다.

이제 $G_1, G_2, G_T$가 Discrete Logarithm이 어렵고 Bilinear Pairing이 존재한다고 가정합시다. $e(g_1, g_2) = g_T$인 generator $g_1, g_2, g_T$를 준비하고,

\[E_1(a) = ag_1, \quad E_2(b) = bg_2, \quad E_T(c) = c g_T\]

라고 합시다. 그러면

\[e(E_1(a), E_2(b)) = E_T(ab)\]

가 성립하므로, 곱셈도 숨겨진 상태에서 할 수 있습니다.

Groth16 : Final Version

이제 Groth16를 소개합니다. Discrete Logarithm이 어렵고 Bilinear Pairing이 있는 $G_1, G_2, G_T$를 잡습니다. $E_1, E_2, E_T$를 위처럼 정의하고 $E = (E_1, E_2)$라 합시다.

Groth16의 CRS는 다음과 같습니다. 먼저 $\alpha, \beta, \delta, x$를 $\mathbb{F}^\star$에서 뽑고,

• $E(\alpha), E(\beta), E(\delta)$
• $E(x^i)$ for $0 \le i \le 2n-2$
• $E_1(\alpha x^i)$ for $0 \le i < n$
• $E_1(\beta x^i)$ for $1 \le i < n$
• $E_1\left( \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta} \right)$ for $l+1 \le i \le m$
• $E_1 \left( \frac{x^i t(x)}{\delta} \right)$ for $0 \le i \le n-2$

가 CRS가 됩니다. 이때, $n = \deg t$입니다. simulation trapdoor는 $\tau = (\alpha, \beta, \delta, x)$.

증명을 위해서는, $a_1, \cdots , a_m$을 준비하고 $r, s$를 $\mathbb{F}$ 위에서 랜덤하게 뽑은 뒤

\[E_1(A) = E_1(\alpha) + \sum_{i=0}^m a_i E_1(u_i(x)) + r E_1(\delta)\] \[E_2(B) = E_2(\beta) + \sum_{i=0}^m a_i E_2(v_i(x)) + s E_2(\delta)\]

와 마찬가지 방법으로 $E_1(C)$를 계산합니다. 즉, $E_1(A), E_2(B), E_1(C)$가 증명입니다.

이를 확인하기 위해서는,

\[e(E_1(A), E_2(B)) = e(E_1(\alpha), E_2(\beta)) + e(E_1(C), E_2(\delta))\] \[+ \sum_{i=0}^l e( E_1(\beta u_i(x) + \alpha v_i(x) + w_i(x)), E_2(a_i))\]

를 확인하면 되며, simulator 역시 위 식이 만족하는 $(A, B, C)$를 랜덤하게 뽑으면 됩니다. 이는 simulation trapdoor를 가지고 있기 때문에 가능합니다.

추가적으로 알면 좋은 사실들은

• Generic Group Model 위에서 작업하면, 여기서 Prover가 CRS의 linear combination을 사용해야 한다는 것이 강제되어 안전성 증명이 마무리됩니다. NILP에서 증명을 했기 때문이죠. 추후 Algebraic Group Model에서도 증명이 되었습니다.

결론

지금까지 ZK의 기본과 Groth16 Protocol에 대해서 알아봤습니다. 다음 글에서는 Powers of Tau와 Tornado Cash에 대해서 알아보겠습니다. 읽어주셔서 감사합니다.