[zk-SNARK 4.] Pinocchio Protocol

이번 글에서는 Prover가 Verifier에게 특정 QAP의 satisfying assignment를 알고 있음을 interactive하게 증명하는 Pinocchio Protocol에 대해서 살펴보겠습니다.

Proving satisfying assignment of QAP

특정 QAP의 satisfying assignment $(s_1, ..., s_m)$은 다음과 같은 조건을 만족해야 합니다.

Prover는 Verifier에게 QAP의 satisfying assignment를 알고 있음을 증명해야 합니다. Prover의 proof에는 다음이 포함돼야 합니다.

• Prover는 다항식 $a_1(x), ..., a_m(x)$ $b_1(x), ..., b_m(x)$ $c_1(x), ..., c_m(x)$들의 linear combination을 통해 $A(x)$, $B(x)$, $C(x)$를 계산할 수 있음을 보여야 합니다.
• Prover는 다항식 $A(x), B(x), C(x)$가 동일한 assignment $(s_1, ..., s_m)$으로부터 생성되었음을 보여야 합니다.
• Prover는 $A(x)B(x) - C(x) = Z(x)H(x)$를 만족하는 다항식 $H(x)$가 존재함을 보여야 합니다.

앞선 글에서 Prover가 Verifier에게 특정 다항식을 알고 있음을 증명하는 방법으로 Verifiable Blind Evaluation of Polynomial 에 대해서 살펴보았습니다. Verifier는 특정 $x$ 좌표 $s$를 선택한 후, 임의의 값 $\alpha$에 대한 $\alpha$-pair들 $(E(s^1), E(\alpha s^1)), ..., (E(s^d), E(\alpha s^d))$을 Prover에게 전달했습니다. 만약 Prover가 또다른 $\alpha$-pair를 생성한다면, Verifier는 Prover가 $s^1, ..., s^d$의 linear combination을 계산했음을 확신할 수 있었습니다.

Pinocchio protocol에서도 동일한 방법을 적용합니다. Verifier는 다음과 같은 $\alpha_A, \alpha_B, \alpha_C$-pair들을 준비합니다.

Verifier가 Prover에게 위 pair들을 전달한 후, Prover가 또다른 $\alpha_A, \alpha_B, \alpha_C$-pair들을 생성하는 데 성공한다면 Prover가 $a_1(s), ..., a_m(s)$ $b_1(s), ..., b_m(s)$ $c_1(s), ..., c_m(s)$들의 linear combination을 계산했음을 확신할 수 있습니다.

뿐만 아니라 동일한 assignment로부터 생성되었음을 보여야 하므로, 다음과 같은 $\alpha_{A+B+C}$-pair를 하나 더 준비합니다.

만약 Prover가 또다른 $\alpha_{A+B+C}$-pair를 생성한다면, $a_i(s) + b_i(s) + c_i(s)$들의 linear combination을 계산했음을 확신할 수 있고, 이는 동일한 assignment로부터 생성된 어떤 다항식 $A(x), B(x), C(x)$들의 합으로부터 계산됐음을 알 수 있습니다.

마지막으로, $A(x)B(x) - C(x) = H(x)Z(x)$를 만족하는 $H(x)$를 계산해야 합니다. Prover는 $A(x)B(x) - C(x) / Z(x)$를 통해 $H(x)$를 계산하고, $s$에서의 Homomorphic Hiding 값인 $E(H(s))$를 계산해야 합니다. $H(x)$는 임의의 다항식일 수 있기 때문에, Verifier는 $s$의 exponentiation의 hiding 값을 전달해야 합니다. 따라서 Verifier는 다음 값들을 계산해서 Prover에게 전달합니다.

Verifier는 Prover의 proof에 포함된 $E(A(s)), E(B(s)), E(C(s)), E(H(s))$와, Verifier가 계산한 $E(Z(s))$를 통해 어떻게 $A(s)B(s) - C(s) = H(s)Z(s)$를 확인할 수 있을까요?

앞서 살펴 본 Homomorphic Hiding 함수 $E(x)$는 소수 $p$에 대한 multiplicative group의 generator $g$에 대해 $E(x) = g^x \pmod {p}$로 정의했습니다. 이 함수는 linear combination에 대해서는 homomorphic하지만, domain의 원소들 간의 multiplication에 대해서는 homomorphic하지 않습니다. 즉, $E(x)$, $E(y)$의 값들만으로 $E(x * y)$를 계산할 수 없습니다. zk-SNARK에서는 이 문제를 해결하기 위해 Elliptic curve pairing이라는 수학적 도구를 사용합니다.

Homomorphic Hiding on EC

앞서 Finite field $F_p$ 상에서 정의된 타원곡선의 점들과, 점 $\Omicron$(point at infinity)가 덧셈에 대한 group을 이룬다는 사실을 소개한 적 있습니다. 그리고 타원곡선 상의 임의의 점 $G$의 scalar multiplication을 한 결과를 모두 모은 집합이 타원곡선 상의 group의 cyclic subgroup이 되는 것도 살펴 보았습니다. 그리고 finite field 상에서 정의된 타원곡선 상의 discrete logarithm 문제가 매우 어렵다는 사실도 알아 보았습니다.

Homomorphic Hiding 함수를 타원곡선 상의 어떤 점 $G$에 대해 $x$번 scalar multiplication한 결과로 다시 정의하겠습니다.

이 함수가 앞서 정의한 Homomorphic Hiding 함수의 성질들을 모두 만족하는 것은 쉽게 확인할 수 있습니다. 이 함수는 $F_p$ 상의 원소들의 linear combination에 대해 homomorphic함을 알 수 있습니다. 하지만 여전히 곱셈에 대해서는 homomorphic하지 않음을 알 수 있습니다.

동일한 타원곡선 내의 점들에 대해서는 곱셈을 homomorphic하게 계산하지 못 하지만, 곱셈의 결과를 전혀 다른 finite cyclic group의 원소로 mapping할 수 있는 함수가 존재합니다. 이를 Elliptic curve pairing 함수라고 명명합니다.

Elliptic curve pairing

Elliptic curve pairing 함수의 형태는 다음과 같습니다.

$G_1$, $G_2$가 order가 같은 특정 타원곡선 상의 subgroup이고, $G_T$를 잘 정의된 어떤 finite cyclic group이라고 하면, pairing 함수는 다음과 같은 성질을 가집니다.

$\bm{g}$는 $G_1$의 generator $g$와는 다른, 새로운 cyclic group $G_T$의 generator입니다. $F_p$의 원소들의 곱셈의 결과를 $G_T$ group의 원소에서 확인할 수 있는 것입니다. $G_1$, $G_2$, $G_T$를 정의하기 위해서는 타원곡선의 embedding degree와 field extension, 그리고 divisor와 같은 좀 더 추상적인 수학적 개념들을 논해야 햐기 때문에, 별도의 포스트에서 더 심도 있게 다루도록 하겠습니다.

중요한 사실은 pairing 함수를 통해 값들을 hiding된 상태에서 곱할 수 있다는 것입니다.

Checking QAP

앞서 Verifier는 Prover의 proof에 포함된 $E(A(s)), E(B(s)), E(C(s)), E(H(s))$와, Verifier가 계산한 $E(Z(s))$를 통해 $A(s)B(s) - C(s) = H(s)Z(s)$가 성립함을 보여야 했습니다. $E(x)$가 타원곡선 상의 점 $G$에 대해 $E(x) = x * G$라고 하면, pairing 함수를 통해 위 관계가 성립하는지 검증할 수 있습니다.

위와 같이 pairing 함수를 통해 QAP의 조건이 충족되는지 확인할 수 있습니다.

마치며

이번 글에서는 Prover가 Verifier에게 QAP의 satisfying assignment를 알고 있음을 interactive하게 증명할 수 있는 방법인 Pinocchio protocol에 대해서 알아보았습니다. zk-SNARK에 필요한 수학적 기반은 대부분 다 살펴보았습니다.

zk-SNARK가 실제 블록체인과 같은 분야에 응용되기 위해서는 non-interactive하게 동작해야 합니다. zk-SNARK는 non-interactive하게 작동하기 위해 CRS (Common Reference String) 모델을 사용합니다. 다음 글에서는 CRS 모델에 대해 살펴보겠습니다.