[영지식 증명] PLONK 파헤치기 2 - Polynomial Commitment

Introduction

안녕하세요, 오늘도 지난 시간에 이어 zk-SNARK의 일종인 PLONK에 대하여 이어서 알아보도록 하겠습니다. 

간단하게 지난 내용을 복습해보자면, prover 가 다항식 $x^3 + x + 5 = 35$ 의 해를 알고 있을 때, 어떻게 가지고 있는 해를 직접적으로 verifier에게 알리지 않으면서도 해를 가지고 있음을 증명할 수 있는지 알아보았습니다. 

 

우선적으로 가지고 있는 다항식을 arithmetic circuit으로 변환하였고, 변환한 arithmetic circuit을 만족하는 내부 값들을 올바르게 검증하기 위한 두 가지 constraint (gate constraint, copy constraint)를 확인했습니다. 남은 글들에서는 각 constraint에 대하여 어떻게 하면 zero-knowledgeness (내부 값들을 직접 공개하지 않으면서 constraint를 만족하는지 확인) 를 유지하면서 prover 가 verifier에 circuit 내부값들에 대한 증명을 할 수 있을지 알아보겠습니다. 이번 포스트는 Risen Crypto 의 KZG-PCS 글을 참조하여 작성되었습니다., 

 

그 중에서도 이번글에서는 지난 시간에 이어 gate constraint에 대한 이야기를 먼저 해보려 합니다. 

Gate Constraint as Polynomial

지난 시간에는 어떻게 하면 각 gate constraint를 다항식 $G(x)$ 로 변환하는 방법을 알아보았습니다. 만약 prover가 올바른 circuit 내부값들을 가지고 다항식 $G(x)$을 생성해 냈다면, $G(x)$는 constraint 갯수 $n$개에 대하여 $0, 1, \dots, n-1$의 값에서 $0$값을 가져야 합니다. 또한 따라서 나머지 정리에 의하여 $G(x) = x(x-1)(x-2)\dots(x-n-1)Q(x) = Z(x)Q(x)$ 로 표현될 수 있습니다. 

 

이번엔 새로운 다항식 $g(x) = G(x) - Z(x)Q(x)$를 정의하겠습니다. 정상적으로 prover 가 계산을 진행했다면 필연적으로 $G(x) = Z(x)Q(x)$일 것이고, $g(x)$는 모든 정의역에서 $0$의 값을 가져야 합니다. 따라서 verifier에게 남은 작업은 다항식 $g(x)$가 실제로 모든 값에서 $0$값을 갖는지 확인하는 작업입니다.

 

Schwartz-Zippel Lemma

하지만 만약 정의역이 크다면, 실제로 모든 값에서 해당 다항식이 $0$값을 갖는지 확인하는 작업은 굉장히 비싼 작업입니다. 여기서 Schwartz-Zipple Lemma 가 도입되게 되는데요, 해당 Lemma 의 내용은 다음과 같습니다. 

 

정의역의 크기가 $N$이고 차수가 $n$인 다항식 $f(x)$가 있을 때, 임의의 값 $r$ 에서 $f(r) = 0$일 확률은 최대 $\frac{n}{N}$이다. 

 

어떻게 보면 직관적인 Lemma입니다. 차수가 $n$인 다항식은 최대 $n$개의 정의역 원소만에서 $0$값을 가질 수 있습니다. 또한 만약 정의역의 크기가 충분히 크다면, $f(r) = 0$일 확률을 매우 작게 만들 수 있고, 이말은 즉슨 우리는 다항식이 zero-polynomial (모든 정의역에서 $0$값을 가짐) 임을 증명하기 위해, 정의역의 모든 원소에서 다항식을 평가할 필요 없이 랜덤한 값 $r$ 하나를 뽑아 해당 값에서 다항식이 $0$값을 가지는 것만 확인하면 된다는 의미가 됩니다.

 

Polynomial Commitment Scheme

앞서서 우리는 gate constraint를 증명하기 위해 다항식을 사용한 검증에 대하여 이야기했습니다. 실제로 PLONK는 다항식 검증을 할 때 PCS (Polynomial Commitment Scheme), 그 중에서도 KZG-PCS 를 사용합니다. 그렇기때문에 이번 시간에는 KZG-PCS에 대하여 이야기해 보려고 합니다. KZG-PCS는 elliptic curve 에서의 pairing 을 사용하지만, 해당 내용에 대하여 이번 포스트에서 자세히 다루지는 않고, 이와 관련된 포스트를 남겨두겠습니다. 

 

우선 KZG-PCS에서 prover의 목적은 자신이 가지고 있는 polynomial $f(x)$ 에 대하여, $f(a) = b$라는 것을 verifier에게 증명하는 것입니다. 이제부터 prover 가 f에 대한 정보를 하나도 유출하지 않으며 $f(a) = b$를 증명하는 과정에 대하여 살펴봅시다. 

 

1. Trusted Setup을 통하여 랜덤한 값 $r$ 생성.

Trusted Setup을 사용하면, prover 와 verifier 전부 알 수 없는 랜덤한 값 $r$을 선택할 수 있습니다. 선택된 $r$값을 가지고 elliptic curve 위에서의 $G, rG, r^2G, \dots, r^nG$ 값들이 계산됩니다. 여기서 $G$는 사용되는 elliptic curve의 generator 이고, $n$은 polynomial 의 차수입니다.

 

2. Prover는 다항식 $f(x)$에 대한 commitment 로 $C_f = f(r)G$ 를 계산.

$f(x) = a_0 + a_1x + a_2x^2 + \dots + a_nx^n$ 이라고 가정하겠습니다. 그렇다면

$f(r)G = (a_0 + a_1r + a_2r^2 + \dots + a_nr^n)G$ 입니다. elliptic curve에서의 성질을 사용하면, 

$f(r)G = C_f = a_0G + a_1rG + a_2r^2G + \dots + a_nr^nG$가 되고, 이미 $G, rG, r^2G, \dots, r^nG$ 값들은 주어졌기 때문에, prover는 성공적으로 $C_f$ 값을 계산할 수 있습니다. 

 

3. Prover 는 $f(a) = b$ 임을 주장.

이제 Prover는 자신이 증명하고 싶은 claim 을 하게 됩니다. 

 

4. Verifier는 $C_q = Q(a)G$ 값을 요구.

만약 $f(a) = b$라면, $a$값은 $f(x)-b = 0$의 해가 되고, $f(x) - b = (x-a)Q(x)$로 표현할 수 있습니다. 이제 $Q(x)$는 다음과 같이 정의됩니다. $Q(x) = \frac{f(x) - b}{x-a}$ Verifier는 $Q(a)G$값을 요구하게 되고, prover는 $Q(a)G$값을 계산해 verifier에게 넘겨주게 됩니다. 만약 실제로 $f(a) \neq b$ 라면, 정상적으로 주어진 정의역에서 $Q(a)$를 계산할 수 없고, $Q(a)G$ 또한 계산할 수 없습니다. 

 

5. 주어진 값들을 가지고 Verifier의 검증

앞선 $Q(x)$의 정의로부터, $Q(x)(x-a) = f(x) - b$ 라는 식이 성립하게 됩니다. 2단계에서 계산한 값 $r$을 해당식에 대입해보게 되면, 

$Q(r)(r-a) = f(r) - b$ 라는 식이 성립하게 됩니다. 이제 이 두 값을 generator G를 사용한 elliptic curve위로 들고 올라가보면, $Q(r)(r-a)G = f(r)G - bG$를 검증하는 것으로 이전의 목표가 변경될 수 있습니다. 우리가 이전에 prover에게서 받아 이미 알고있는 값들을 대체해보면, $(r-a)C_q = C_f - bG$로 표현할 수 있습니다. 하지만 여기서의 문제는, verifier가 $r$ 값을 알 수 없어서 해당 식을 검증할 수 없다는 것입니다. 

 

여기서 elliptic curve에서의 pairing 이라는 개념이 사용됩니다. 본 포스트에서는 pairing에 대하여 깊게 들어가지는 않습니다. 이것은 $r$값을 모르더라도 verifier가 이전의 식을 검증할 수 있도록 도와주는 도구 정도로 생각하시면 편할 것 같습니다. 

 

Pairing $e$ 는 group 의 원소 2가지를 받아, 다른 group의 원소를 배출합니다. $e: G \times G \rightarrow G'$.

사용되는 pairing 의 중요한 특징으로는, $e(\alpha A, B) = e(A, \alpha B)$ 가 성립됩니다. 

이제 검증해야 하는 $(r-a)C_q$ 값과 $C_f - bG$ 값을 모두 generator $G$와 pairing 함수에 넣어주겠습니다. 

이제 우리가 검증하고 싶은 식은: 

$e((r-a)C_q, G) = e(C_f - bG, G)$ 이고, 앞선 pairing의 성질을 사용하면 이것은 $e(C_q, rG - aG) = e(C_f - bG, G)$ 가 됩니다. 헌데 이번에는, 앞서 생성한 $G, rG, r^2G, \dots, r^nG$ 으로부터 $rG$ 값을 계산할 수 있습니다. 이제 모든 값들이 계산 가능하므로 verifier는 검증을 완료할 수 있습니다. 만약 prover가 $Q(r)$을 임의로 생성해 검증과정을 속이려고 해도, 랜덤한 $r$ 값에서의 $Q(r)(r-a) = f(r) - b$라는 조건을 만족하게 생성해내는 것은 거의 불가능하므로 검증과정을 속일 수 없습니다. 

Conclusion

정리해보자면, prover는 다항식의 해를 들고 있음을 증명하기 위해 arithmetic circuit을 생성하고, 이에 해당하는 gate constraint들을 다항식으로 변환시켰습니다. Prover는 gate constraint를 모두 만족하는 circuit 내부값들을 가지고 있음을 증명하기 위해 $g(x) = G(x) - Z(x)Q(x)$이 zero-polynomial (모든 정의역에서 $0$값을 가짐) 임을 보여야 합니다. Schwartz-Zippel lemma 에 의해 이것은 한 가지 랜덤한 값에서 $g(x)$값을 구하는 것으로 대체될 수 있으며, prover는 $g(x)$를 공개하지 않으면서도 랜덤한 값에서 $g(x)$를 올바르게 계산했음을 KZG-PCS 를 통해 증명하게 됩니다.

 

이번 포스트까지가 gate constraint를 증명하는 과정이었습니다. 다음 포스트에서는 copy constraint와 관련한 내용을 알아보도록 하겠습니다.