[영지식 증명] PLONK 파헤치기 1

Introduction

PLONK는 현재 많이 사용되는 zk-SNARK 의 한 종류입니다. Halo2 등 여러 영지식 증명의 방법으로 PLONK를 사용합니다. Groth16 방식이 각 circuit 마다 새로운 setup을 해주어야 하는 것과 달리, PLONK의 setup은 universal 해서, 한번 setup을 진행한 후, 다른 여러 circuit이 해당 setup을 사용할 수 있다는 장점이 존재하기도 합니다. 이번 글을 통해, PLONK의 증명방식에 대하여 훑어보려고 합니다. 이번 글을 통해 독자분들이 PLONK에 대하여 전반적으로 이해하시는데 도움이 되었으면 좋겠습니다. 본 글은 How Plonk Works, velog Plonk 관련 한글 게시물 을 바탕으로 작성되었습니다. 

 

Motivating Example

Prover는 $x^3 + x + 5 = 35$ 를 만족하는 x 값을 알고 있습니다. (이 경우 $x=3$ 입니다) 이제 Prover는 Verifier 에게 자신이 $x=3$ 이라는 정답을 알고 있다는 사실을 증명하면서도, 이를 만족하는 값이 3이라는 사실은 노출하고 싶지 않습니다. 이 경우 Prover 는 어떠한 방식으로 Verifier 에게 증명할 수 있을까요?

 

Arithmetic Circuit

그림 1: given function에 대한 arithmetic circuit

Prover는 주어진 함수 $x^3 + x + 5 = 35$ 를 확인하는 arithmetic circuit을 만들게 됩니다. arithmetic circuit는 산술 연산이 이루어지는 gate, 그리고 각 gate를 연결하는 wire로 구성되어 있습니다. Arithmetic circuit에는 두 가지 종류의 gate가 존재합니다. Addition gate의 경우 각 gate 에 들어오는 두가지 input을 더해주게 되고, multiplication gate는 gate에 들어오는 두 가지 input을 곱해주게 됩니다. 

주어진 함수에 해당하는 arithmetic circuit을 만들었다고 가정해봅시다. 이제 $x^3 + x + 5 = 35$ 의 해를 Prover 가 가지고 있다는 것은, 그림 1처럼 만들어진 arithmetic circuit 내부에 올바른 arithmetic circuit gate 간의 조건을 만족하는 $a_0, b_0, c_0, \dots, a_3, b_3, c_3$ 를 가지고 있다는 말과 동일합니다.

 

Constraints in Arithmetic Circuit

Prover는 자신이 주어진 함수에 대한 해를 가지고 있다는 것을 증명하기 위해, arithmetic circuit을 만들고, 해당 arithmetic circuit에서 올바른 계산을 통해 만들어진 $a_0, b_0, c_0, \dots, a_3, b_3, c_3$를 가지고 있음을 증명하고 싶습니다. 어떻게 하면 각 값들을 직접적으로 밝히지 않으면서 올바른 내부 값들을 가지고 있다는 것을 증명할 수 있을까요? 이것은 각 내부 값들이 circuit 고유적으로 만족해야 하는 조건을 실제로 만족한다는 것을 보이면 됩니다. 예를 들어, $c_0$ 는 실제로 $a_0 + b_0$ 와 값이 동일해야 합니다. 또한 $c_0$ 값은 다음 게이트의 $a_1$에서 사용되기 때문에 이 둘의 값은 동일해야 합니다. circuit안의 값들에는 앞서 방금 언급된 것처럼 두 가지 종류의 constraint가 있습니다. 

• Gate Constraint: $a_0 + b_0 = c_0$ 처럼 circuit의 각 gate에서의 연산값이 올바름을 확인합니다.
• Copy Constraint: $c_0 = a_1$ 처럼 circuit 에서 같은 값을 갖는 변수들의 값이 실제로 동일함을 확인합니다. 

PLONK의 경우 Gate Constraint를 확인하기 위해 Polynomial Commitment 를 사용하고 Copy Constraint를 확인하기 위해 Permutation Check를 사용합니다. 

 

Transforming gate constraint into polynomials

PLONK에서는 각 gate constraint를 다항함수로 변화시키는 과정을 거치게 됩니다. 이번 섹션에서는 어떻게 각 Constraint들이 다항함수로 변환될 수 있는지 알아보겠습니다. 우선 위에 주어진 circuit에 해당하는 gate constraint들은 다음과 같이 나열할 수 있습니다. 

• $a_0 + b_0 = c_0$
• $a_1 \times b_1 = c_1$
• $a_2 + b_2 = c_2$
• $a_3 + b_3 = c_3, b_3 = 5, c_3 = 35$

Arithmetic circuit는 두 가지 종류의 gate만을 가질 수 있기 때문에, 모든 gate constraint는 아래와 같은 식으로 일반화될 수 있습니다. 

$Q_la + Q_rb + Q_oc + Q_mab + Q_c = 0$

해당 식의 각 $Q_l, Q_r, Q_o, Q_m, Q_c$ 값들에 어떠한 값을 선택하느냐에 따라, addition 혹은 multiplication gate constraint를 나타낼 수 있습니다. 예를 들어, 첫 gate constraint의 경우 $Q_l = Q_r = 1, Q_o = -1, Q_m = Q_c = 0$ 을 선택해서 표현할 수 있습니다.

이제 해당 형식으로 모든 gate constraint들을 표기해 봅시다. 

• $1 \times a_0 + 1 \times b_0 + -1 \times c_0 + 0 \times a_0b_0 + 0 = 0$
• $0 \times a_1 + 0 \times b_1 + -1 \times c_1 + 1 \times a_1b_1 + 0 = 0$
• $1 \times a_2 + 1 \times b_2 + -1 \times c_2 + 0 \times a_2b_2 + 0 = 0$
• $1 \times a_3 + 1 \times b_3 + 0 \times c_3 + 0 \times a_3b_3 - 30 = 0$

또한 이제 각 Q_l, Q_r, Q_o, Q_m, Q_c 값들을 모아서 벡터로 표기하게 되면, 

• $Q_l = (1, 0, 1, 1)$
• $Q_r = (1, 0, 1, 1)$
• $Q_o = (-1, -1, -1, 0)$
• $Q_m = (0, 1, 0, 0)$
• $Q_c = (0, 0, 0, -30)$

으로 표기할 수 있습니다. 또한, a, b, c 값들도 모아서 벡터로 표기하도록 하겠습니다. 

• $\textbf{a} = (a_0, a_1, a_2, a_3)$
• $\textbf{b} = (b_0, b_1, b_2, b_3)$
• $\textbf{c} = (c_0, c_1, c_2, c_3)$

이제 gate constraint에 대한 polynomial 을 만들기 위한 준비가 전부 끝났습니다. 우선 $Q_l$ 에 대한 polynomial $F_l$ 은 정수 $0, 1, 2, 3$ 에서, 각각 $(1, 0, 1, 1)$ 의 값을 갖도록 정의합니다. 해당 다항식은 라그랑주 보간법으로 계산 가능하지만 해당 포스트에서는 다루지 않습니다. 또한 동일한 방법으로 $Q_r, Q_o, Q_m, Q_c$ 에 해당하는 polynomial $F_r, F_o, F_m, F_c$ 를 정의해 줍니다. 예를 들어, $F_l$ 은 다음과 같은 다항식으로 변환됩니다. 

$F_l = -\frac{1}{3}x^3 + \frac{3}{2}x^2 -\frac{7}{6}x$

실제로 $0, 1, 2, 3$에서의 값들을 넣어보면, 이들은 $1, 0, 1, 1$ 의 값을 가짐을 확인할 수 있습니다.

이제 계산한 $F_l, F_r, F_o, F_m, F_c$를 바탕으로 gate constraint에 대한 다항식은 다음과 같이 정의할 수 있습니다. 

$G(x) = F_l(x)a(x) + F_r(x)b(x) + F_o(x)c(x) + F_m(x)a(x)b(x) + F_c(x)$

$a, b, c$의 $x$에서의 evaluation은 각 벡터의 $x$번째 원소로 정의됩니다. 

$G(x)$는 각 $0, 1, 2, 3$ 값에서 앞에서 정의된 gate constraint를 하나씩 내포하고 있음을 알 수 있습니다. 

또한 각 gate constraint의 우변을 $0$으로 두었기때문에, $G(x)$ 또한 $0,1,2,3$ 에서 $0$값을 가져야 함을 알 수 있습니다. 

즉, $G(x) = x(x-1)(x-2)(x-3)Q(x) = Z(x)Q(x)$ 로 표현될 수 있습니다. 

Proving protocol

만약 prover 가 실제로 처음 다항식  $x^3 + x + 5 = 35$ 에 대한 해를 가지고 있다면, prover는 circuit 내부의 올바른 $a, b, c$ 값들을 계산할 수 있고, 앞서 소개된 절차를 통해 올바른 $G(x), Z(x), Q(x)$를 만들어낼 수 있습니다. 하지만 prover가 만약 해를 가지고 있지 않다면, 올바른 $G(x)$를 계산해낼 수 없습니다. 만약 나쁜 prover가 임의의 $G(x)$를 생성해 verifier를 속이려 해도, verifier는 $Z(x), Q(x)$에 대한 정보를 요구하여 prover의 증명을 검증할 수 있습니다. 이에 대한 자세한 내용은 다음 포스트에서 polynomial commitment scheme과 함께 알아보도록 하겠습니다.