[zk-SNARK 2.] Verifiable Blind Evaluation

앞선 글에서 Blind Evaluation of Polynomial이 무엇인지에 대해 소개했습니다. 이를 통해 Prover는 Verifier에게 특정 다항식을 알고 있음을 간결하고(succinct), 다항식을 공개하지 않으면서(zero-knowledgeness) 증명할 수 있었습니다. Blind Evaluation of Polynomial의 과정을 다시 한 번 살펴보겠습니다.

1. Verifier가 특정 $x$ 좌표 $s$를 선택한 후, $E(s^{0}), E(s^{1}), ..., E(s^{n})$을 Prover에게 전송합니다.
2. Prover는 $E(s^{0}), E(s^{1}), ..., E(s^{n})$ 값들을 이용해 다항식 $P(x) = a_{0} + a_{1}x^{1} + ... + a_{n}x^{n}$을 $s$에서 계산한 값을 hiding한 값인 $E(P(s))$를 계산합니다. (Homomorphic Hiding 함수는 정의역의 원소들의 linear combination에 대해서 homomorphic하고, $P(s)$는 $s^{0}, s^{1}, ..., s^{n}$의 linear combination이므로 계산이 가능합니다)
3. Verifier는 $E(P(s))$ 값을 통해 Prover가 다항식을 알고 있는지 검증할 수 있습니다.

Verifier는 Prover가 계산한 다항식의 hiding 값이 특정 조건을 충족하는지를 검증함으로써, Prover가 올바른 다항식을 알고 있는지를 검증할 수 있습니다. 그런데 위 과정에서 Prover가 반드시 어떤 다항식의 hiding 값을 전달한다고 보장할 수 있을까요? Verifier는 Prover가 $E(s^{0}), E(s^{1}), ..., E(s^{n})$ 값들을 통해 $E(P(s))$을 계산해 줄 것이라고 기대하지만, Prover가 실제로 $E(P(s))$을 전달한다는 보장은 없습니다. Prover가 "우연히" 특정 조건을 만족하는 값을 맞출 수도 있습니다.

Prover가 반드시 어떤 다항식에 대한 hiding 값을 전달하도록 강제할 방법이 필요합니다. 다시 말하면, Prover가 전달한 값이 $s^{0}, s^{1}, ..., s^{n}$의 linear combination의 hiding 값임을 증명할 수 있어야 합니다. 이를 위해 KCA (Knowledge of Coefficient Assumption)이라는 가정을 사용합니다.

Knowledge of Coefficient Assumption

Knowledge of Coefficient Assumption은 zk-SNARK 전반에서 사용되는 가장 중요한 가정입니다. 그 내용을 살펴보겠습니다.

$\alpha \in \{ 1, ..., p - 1 \}$에 대해서, $a, b \in Z_{p}^{*}$이면서 $b = a^{\alpha}$를 만족하는 $(a, b)$ 쌍을 $\alpha$-pair라고 부르겠습니다. $Z_{p}^{*}$에서 소수 $p$가 매우 클 때, discrete logarithm 문제가 매우 어렵다고 알려져 있기 때문에, $a, b$의 값들만을 통해 $\alpha$ 값을 알아내는 건 매우 어렵습니다.

Bob이 임의의 $\alpha, a$ 값을 골라 Alice에게 $\alpha$-pair $(a, b)$를 전달했다고 가정합니다. 만약 Alice가 또다른 $\alpha$-pair $(a', b')$을 생성해서 Bob에게 돌려준다면, Bob은 Alice가 어떤 상수 $\gamma$에 대해, $a' = a^{\gamma}, b' = b^{\gamma}$을 계산했음을 확신할 수 있습니다.($(a')^{\alpha} = b'$) Alice가 $(a, b)$ 쌍을 통해 $\alpha$ 값을 알아내는 건 매우 어렵기 때문에, $a', b'$이 $a, b$의 값으로부터 동일한 비율로 계산되었다고 결론 내릴 수 있는 것입니다.

An Extended KCA

위에서 살펴본 KCA를 좀 더 확장해 보겠습니다. Bob이 하나의 $\alpha$-pair가 아닌, 여러 개의 $\alpha$-pair $(a_{1}, b_{1}), (a_{2}, b_{2}), ..., (a_{n}, b_{n})$을 Alice에게 전달했다고 가정합시다. Alice가 주어진 여러 개의 $\alpha$-pair들을 이용해 또다른 $\alpha$-pair $(a', b')$을 생성했다면, $a', b'$는 $a_{i}, b_{i}$ 값들과 어떤 관계를 가지고 있을까요? Alice는 임의의 $c_{1}, c_{2}, ..., c_{n} \in \{ 1, 2, ..., p - 1 \}$를 이용해 $a_{i}, b_{i}$들의 exponentiation의 product를 계산함으로써, 또다른 $\alpha$-pair를 생성해 낼 수 있습니다.

만약 Alice가 $\alpha$-pair $(a', b')$를 생성한다면, Bob은 매우 높은 확률로 Alice가 위와 같은 방법으로 $a', b'$을 계산했다고 확신할 수 있습니다.

이 가정이 어떻게 유용하게 사용될 수 있을까요? $a_{i}$ 값들을 앞서 살펴 본 Homomorphic Hiding 함수의 결과 값이라고 생각한다면, $a'$은 $a_{i}$가 hiding하는 값들의 linear combination을 다시 hiding한 값이 됩니다.

d-KCA

Bob이 $\alpha \in \{ 1, ..., p - 1 \}, s \in Z_{p}^{*}$을 만족하는 $\alpha, s$를 선택한 후 Alice에게 $(E(s^{0}), E(\alpha * s^{0}))$, $(E(s^{1}), E(\alpha * s^{1}))$, ..., $(E(s^{d}), E(\alpha * s^{d}))$ 값을 보냈다고 가정했을 때, Alice가 또 다른 $\alpha$-pair $(a', b')$을 생성한다면, Alice가 매우 높은 확률로 어떤 상수 $c_{0}, c_{1}, ..., c_{d}$에 대해서 $a' = E(\sum_{i=0}^{d}c_{i} * s^{i})$을 통해 계산되었음을 알 수 있습니다.

Verifiable Blind Evaluation of Polynomial

Blind Evaluation of Polynomial 과정에서 Verifier가 Prover에게 $(E(s^{0}), E(\alpha * s^{0}))$, $(E(s^{1}), E(\alpha * s^{1}))$, ..., $(E(s^{n}), E(\alpha * s^{n}))$ pair들을 넘겨주고, Prover가 새로운 $\alpha$-pair을 생성한다면, Verifier는 Prover가 가지고 있는 다항식의 coefficient들을 이용해 hiding 값을 계산한 것을 검증할 수 있습니다. 이를 Verifiable Blind Evaluation of Polynomial이라고 합니다.

마치며

이때까지 다항식의 검증에 필요한 기본적인 메커니즘에 대해서 알아보았습니다. zk-SNARK가 실제 computational problem에 적용되기 위해서는 특정 다항식에 대한 문제로 변환하는 과정이 필요합니다. 이 과정을 arithmetization이라고 부르는데, zk-SNARK에서는 이 과정을 통해 QAP(Quadratic Arithmetic Program)라는 문제로 변형합니다. 다음 글에서는 QAP에 대해서 알아보도록 하겠습니다.