[PLONK 2.] KZG polynomial commitment

DoHoon Kim·2022년 7월 25일

PLONK

목록 보기

2/5

이번 글에서는 다항식을 알고 있음을 증명하는 방법 중 하나인 polynomial commitment scheme과, polynomial commitment 방법 중 하나인 KZG commitment에 대해서 알아보겠습니다.

Commitment scheme

Commitment scheme은 cryptographic protocol에서 자주 등장하는 개념입니다. Commitment scheme에서는 committer가 특정 메시지에 대한 commitment를 공개하고, 이후 이 commitment를 open하여 commit된 메시지를 공개함으로써 Verifier는 메시지를 검증할 수 있습니다.
Commitment scheme은 다음과 같은 두 가지 특성이 있습니다.

Committer는 publish한 commitment에 binding됩니다.
Commitment는 commit된 메시지를 hiding합니다.

Committer는 자신의 commitment에 bind되기 때문에 한 번 commit된 메시지는 변경할 수 없으며(메시지를 변경하면 이후 commitment를 open할 때 protocol에 의해 abort), 메시지가 hiding돼 있기 때문에 Verifier는 commitment만을 가지고 commit된 메시지를 알아낼 수 없습니다. 이러한 특성 덕분에 commitment scheme은 어떤 사실을 알고 있음을 안전하게 증명하고 검증하는데 사용됩니다.

zk-SNARK에서는 Prover가 Verifier에게 특정 조건을 만족하는 다항식을 알고 있음을 해당 다항식을 밝히지 않고 증명합니다. 특히 다항식이 특정 점에서 어떤 값을 가짐을 안전하게 증명해야 할 때 polynomial commitment scheme을 사용할 수 있습니다. Prover가 먼저 다항식에 대한 commitment를 publish하고, 이후 commitment를 open하여 다항식의 evaluation에 대한 proof를 생성할 수 있습니다. Polynomial commitment scheme 중 하나인 KZG commitment를 통해 그 방법에 대해 알아보겠습니다.

KZG commitment scheme

Order가 prime $p$ 로 동일하고, 다음과 같이 pairing이 존재하는 두 개의 elliptic curve group $G_1, G_2$ 를 생각하겠습니다.

e : G_1 \times G_2 \rightarrow G_T

$G_1, G_2$ 의 generator를 각각 $G, H$ 라고 하고, $G, H$ 의 scalar multiplication을 다음과 같이 나타내겠습니다.

[x]_1 = xG \in G_1, \;[x]_2 = xH \in G_2

이제, Trusted Setup 과정을 통해 random point $s$ 를 선택한 후, $[1]_1, [s^1]_1, [s^2]_1, \dots, [1]_2, [s^1]_2, [s^2]_2, \dots$ 를 계산합니다.(hiding 값들을 계산한 후 $s$ 는 삭제됩니다) 이 값들을 SRS(Structured Reference String)이라고 명명합니다. SRS를 이용해 임의의 다항식을 $s$ 에서 계산한 값의 hiding을 계산할 수 있습니다.(단, 다항식의 degree에 upper bound가 존재합니다)

이제 Prover가 SRS를 이용해 특정 다항식 $p(x)$ 에 대한 commitment를 계산합니다. 다항식 $p(x)$ 의 commitment는 다음과 같이 정의됩니다.

C = [p(s)]_1

이제, Prover가 $p(x)$ 가 $x = z$ 에서 값 $y$ 를 가짐을 증명하려 합니다. 만약 다항식 $p(x)$ 에 대해 $p(z) = y$ 를 만족한다면 어떤 다항식 $q(x)$ 가 존재해 다음 식이 성립함을 알 수 있습니다.

p(x) - y = (x - z)q(x)

Prover는 다음과 같이 다항식 $p(z) = y$ 에 대한 proof를 생성합니다.

\pi = [q(s)]_1

Verifier는 $p(x)$ 에 대한 commitment와 Prover가 전달한 proof를 이용해 $p(x) - y = (x - z)q(x)$ 임을 증명할 수 있습니다. Schwartz-Zippel Lemma에 의해 다음 등식이 성립함을 보이면 충분합니다.

p(s) - y = q(s)(s - z)

Verifier는 pairing 함수를 이용해 위 등식이 성립함을 보일 수 있습니다.

e([p(s)]_1 - [y]_1, [1]_2) = e([q(s)]_1, [s]_2 - [z]_2)

$[p(s)]_1$ 은 $p(x)$ 에 대한 commitment, $[q(s)]_1$ 는 Prover가 전달한 proof이고, 나머지 값들은 SRS로부터 계산할 수 있습니다.

Multiproof

KZG commitment의 강력한 점은 polynomial commitment와 evaluation proof를 각각 (서로 다른)단일 group element로 표현할 수 있다는 점입니다. KZG commitment paper에서는 여전히 단일 group element 이용해 다수의 점에서 evaluation proof를 생성할 수 있는 방법을 제시하고 있습니다.

다항식 $p(x)$ 에 대한 commitment는 다음과 같습니다.

C = [p(s)]_1

이제 Prover가 다항식 $p(x)$ 가 $(z_0, y_0), \dots, (z_{n-1}, y_{n-1})$ 점들을 지나는 것을 증명하고자 합니다. 위와 같이 $n$ 개의 점들이 주어질 때, 위의 점들을 모두 지나면서 degree가 $n$ 미만인 interpolation polynomial은 다음과 같이 유일하게 주어집니다. (Lagrange Interpolation을 이용해서 쉽게 구할 수 있습니다)

I(x) = \sum_{i=0}^{n-1}y_i \prod_{j=0, \\j \neq i}^{n-1}{(x-z_j) \over (z_i - z_j)}

다항식 $p(x)$ 가 위 점들을 모두 지난다면, 어떤 다항식 $q(x)$ 가 존재해 다음 관계가 성립함을 알 수 있습니다.

p(x) - I(x) = q(x) * \prod_{i=0}^{n-1}(x-z_i)

이제 Prover는 $p(x)$ 에 대한 evaluation proof $\pi = [q(s)]_1$ 를 생성합니다.

Verifier는 다음과 같이 pairing check를 통해 proof를 검증할 수 있습니다.

e(C - [I(s)]_1, [1]_2) = e(\pi, [\prod_{i=0}^{n-1}(s-z_i)]_2)

마치며

이번 글에서는 polynomial commitment scheme 중 하나인 KZG commitment scheme에 대해서 알아보았습니다. 이외에도 Pederson commitment, Zcash의 Halo2에서 사용하는 Inner product argument도 존재합니다. 최근 Ethereum에서는 Zcash의 Halo2에서 Inner product argument scheme을 걷어내고, KZG commitment로 대체하는 업데이트가 있었습니다. Inner product argument는 추후 Bulletproof 및 Halo에 대해 연재하면서 알아보겠습니다.

다음 글에서는 실제 PLONK protocol을 살펴보겠습니다.

DoHoon Kim

Researcher & Developer

이전 포스트

[PLONK 1.] PLONK-style Arithmetization

다음 포스트