[zk-SNARK 1.] Proving polynomial

이번 시리즈에서는 zk-SNARK에 대해 알아보도록 하겠습니다. 이번 시리즈를 통해 zk-SNARK의 수학적 기반을 전반적으로 설명할 예정입니다. zk-SNARK를 구성하는 수학적 내용들은 생각보다 광범위하기 때문에, 일부 디테일한 내용들은 별도의 시리즈로 다루도록 하겠습니다. 들어가기에 앞서, zk-SNARK가 무엇인지 간략하게 알아보도록 하겠습니다.

zk-SNARK란

zk-SNARK는 Zero-Knowledge Succinct Non-Interactive Argument of Knowledge의 약자로, 특정 computational problem에 대한 답을 알고 있음을 증명하는 체계입니다. Computational problem에 대한 답을 알고 있다는 말은 '특정 정보를 소유하고 있다', 혹은 '특정 computation이 정확하다' 와 같은 말들로 대체되기도 합니다.
이름에서 알 수 있듯이, zk-SNARK는 증명이 간결(Succinct)하며, 증명 과정에서 Prover(증명하고자 하는 주체)와 Verifier(증명을 검증하는 주체) 간의 상호 작용이 없어야 하며(Non-Interactive), Verifier는 Prover가 제시한 증명의 유효성 외에는 아무런 추가적인 정보도 얻지 못 해야 합니다.

Verifying Polynomials

zk-SNARK가 computational problem에 어떻게 적용되는지 알아보기에 앞서, zk-SNARK의 core concept을 알아보도록 하겠습니다. zk-SNARK의 핵심은 Prover가 Verifier에게 특정 조건을 만족하는 다항식을 알고 있음을 증명하는 것입니다. 정확히는 QAP(Quadratic Arithmetic Program)의 satisfying assignment를 알고 있음을 Prover가 증명하는 것인데, QAP가 무엇인지는 뒤에서 설명하도록 하겠습니다.

특정 다항식을 "안다"라는 것을 어떻게 증명할 수 있을까요? 다항식의 형태가 $a_{0}x_{0} + a_{1}x_{1} ... + a_{n}x_{n}$임을 생각하면, 다항식의 각 항들의 계수(coefficient)를 보여줌으로써 특정 다항식을 "안다"라는 것을 증명할 수 있습니다.

zk-SNARK는 Prover가 Verifier에게 특정 조건을 만족하는 다항식을 알고 있음을 증명하는 것이기 때문에, Prover가 알고 있는 다항식의 coefficient들을 Verifier에게 전달하면, Verifier는 해당 다항식이 특정 조건을 만족함을 확인할 수 있을 것입니다. 하지만 다항식의 크기가 매우 커진다면, 증명(을 담은 메시지)의 크기가 커진다는 단점이 있습니다. 그리고 증명 과정에서 다항식을 Verifier에게 공개하지 않아야 합니다(Zero-knowledgeness).

Prover가 다항식을 공개하지 않고, Verifier가 지정한 $x$ 좌표에서 다항식을 계산해서 Verifier가 이를 검증한다면 어떨까요? 임의로 선택된 $x$ 좌표에서 두 다항식이 같은 값을 가진다면, 높은 확률로 두 다항식이 같다고 말할 수 있습니다. $n$차 다항식은 실수체에서 최대 $n$개의 영점을 가질 수 있고, "서로 다른 두 개의 n차 다항식이 같음"이 성립하는 $x$ 좌표의 개수 또한 최대 n개로 제한되기 때문입니다. (Schwartz-Zippel Lemma)

만약 $x$ 좌표가 선택될 수 있는 범위가 매우 크다면, 높은 확률로 두 다항식이 동일하다고 말할 수 있습니다. 그런데 Verifier가 선택한 $x$ 좌표를 Prover가 알게 되면, 해당 $x$ 좌표에서만 문제의 조건을 만족하게끔 다항식을 조작할 여지가 발생합니다. 선택된 $x$ 좌표의 값을 Prover에게 공개하지 않으면서, Prover가 해당 $x$ 좌표에서 다항식을 계산할 수 있는 방법이 필요합니다. 이를 위해 Homomorphic Hiding이라는 수학적 방법이 사용됩니다.

Homomorphic Hiding

Homomorphic Hiding은 다음 성질들을 만족하는 encryption function 입니다. $E(x)$라고 명명하겠습니다.

1. $E(x)$의 값이 주어질 때, hiding 이전의 값 $x$를 알아내는 건 매우 어렵습니다.
2. $x \neq y$이면, $E(x) \neq E(y)$
3. $E(x)$, $E(y)$의 값을 통해 $x$, $y$의 산술 연산 표현식에 대한 hiding 값을 계산할 수 있습니다. (e.g. $E(x + y)$)

Homomorphic Hiding 함수는 어떻게 만들어낼 수 있을까요?

여러 방법이 있겠지만, 암호학에서 주로 사용되는 소수 $p$에 대한 multiplicative group을 이용해 Homomorphic Hiding 함수를 만들어낼 수 있습니다. 소수 p에 대한 multiplicative group은 집합 $\{ 1, 2, ..., p - 1 \}$과, $\mod {p}$에 대한 곱셈 연산으로 이루어진 group입니다. 소수 $p$에 대한 multiplicative group을 $Z_{p}^{*}$라고 명명하겠습니다. $Z_{p}^{*}$에는 다음과 같은 유용한 특성들이 있습니다.

첫 번째는 $Z_{p}^{*}$의 집합에는 특정 원소 $g$가 group을 generate한다는 것입니다. 즉 $\{ g^{0}, g^{1}, ..., g^{p-2} \}$이 집합 $\{ 1, 2, ..., p - 1 \}$과 같아지게끔 하는 원소 $g$가 항상 group 내에 존재합니다. (총 $\phi(p - 1)$개의 generator가 group 내에 존재합니다)

두 번째 특성으로는, $Z_{p}^{*}$에서 discrete logarithm 문제가 매우 어렵다고 알려져 있습니다. 소수 $p$가 매우 크다면 group 내의 원소 $h$에 대하여, $h \equiv g^{a} \pmod{p}$를 만족하는 $a$를 알아내기는 어렵습니다.

그리고 지수 법칙에 의하여 $g^{a}$, $g^{b}$를 곱함으로써 $g^{a+b \pmod {p-1}}$를 계산할 수 있습니다.

$Z_{p}^{*}$의 generator $g$에 대하여, $E(x) = g^{x} \pmod {p}$ 함수가 앞서 소개한 Homomorphic Hiding 함수의 특성들을 모두 만족함을 알 수 있습니다. 이 함수가 앞으로 소개할 Blind Evaluation of Polynomial에서 사용될 예정입니다.

Blind Evaluation of Polynomial

지금까지 살펴 본 Homomorphic Hiding 함수를 사용하면 Prover는 선택된 특정 $x$ 좌표 $s$의 hiding 값을 이용해 $s$에서 다항식을 계산한 결과값을 Verifier에게 전달할 수 있습니다.

앞서 살펴본 Homomorphic Hiding 함수는 $E(x)$, $E(y)$ 값만을 통해 $x, y$의 임의의 linear combination에 대한 hiding 값을 계산할 수 있음을 알 수 있습니다. (지수법칙을 통해 간단하게 확인할 수 있습니다) 즉 정의역의 원소들의 linear combination에 대해서 homomorphic합니다. 하지만 $E(x * y)$는 $E(x)$, $E(y)$ 값들만으로는 계산해 낼 수 없습니다.

$x$ 좌표 $s$에서 $n$차 다항식을 계산한 값이 $s^{0}, s^{1}, ..., s^{n}$의 linear combination임을 상기하면, Prover가 다항식을 계산하기 위해서는 $E(s^{0}), E(s^{1}), ..., E(s^{n})$를 Verifier에게 전달받아야 합니다. Prover는 가지고 있는 다항식의 coefficient들을 이용해, $s^{0}, s^{1}, ..., s^{n}$의 linear combination 값에 대한 hiding 값을 계산해 낼 수 있습니다. 값을 전달받은 Verifier는 Prover가 올바른 다항식을 가지고 있는지 확인할 수 있습니다.

이를 Blind Evaluation of Polynomial이라고 합니다.

마치며

zk-SNARK의 핵심 concept은 Prover가 QAP의 특정 조건을 만족하는 다항식을 알고 있음을 Verifier에게 증명하는 것이라는 것을 알았습니다. Prover가 특정 $x$ 좌표의 값을 알지 못 해도, 해당 좌표에서 다항식의 값을 계산할 수 있는 Blind Evaluation of Polynomial에 대해서도 살펴 보았습니다.

다음 글에서는 Blind Evaluation of Polynomial의 문제점과 이를 해결하기 위한 KCA(Knowledge of Coefficient Assumption)을 설명하고, QAP가 무엇인지 소개하도록 하겠습니다.