[Note] PLONK algorithm - Prover

PLONK algorithm에서 증명하고자 하는 것은 witness들이 gate constraint와 copy constraint를 만족함을 증명하는 것이다.

먼저 circuit에 대해 다음과 같은 정보들이 주어진다.

• 'selector' polynomials

  $q_M(X), q_L(X), q_R(X), q_O(X), q_C(X)$

• permutation polynomials

copy constraint를 나타내는 permutation $\sigma: [3n] \rightarrow [3n]$이 있을 때, 다음과 같이 permutation polynomial들이 정의된다.

$\sigma^*$는 permutation된 결과를 multiplicative subgroup의 element로 대응시키는 함수다. PLONK의 각 wire에 $[3n]$을 부여하는 대신, multiplicative subgroup $H= \{1, \omega, \dots, \omega^{n-1}\}$와 $H$와 서로 다른 $H$의 cosets $k_1 \cdot H$, $k_2 \cdot H$의 원소들을 대응한다.

SNARK relation은 다음과 같이 정의된다.

$l$은 public input의 개수, $3n - l$은 witness의 개수라고 생각하면 된다.

$x$는 public input 값들의 쌍, $w$는 witness 값들의 쌍이다. 각 값들은 field $\mathbb{F}$의 원소들이다.

Relation의 witness 값들이 다음 조건을 만족해야 한다.

이제 PLONK protocol을 paper 그대로 쭉 따라가보자.

PLONK protocol은 Fiat-Shamir heuristic을 통해 non-interactive하게 기술될 수 있다. PLONK paper에서는 transcript를 통해 random challenge 값을 얻어낸다. Verifier는 transcript로부터 prover와 동일한 random challenge 값을 얻어낼 수 있다.

Common preprocessed input

Prover algorithm

Prover algorithm의 input은 witness 값들 $(w_i)_{i \in [3n]}$이다.

Round 1:

Round 1에서는 $a(X), b(X), c(X)$들의 commitment가 계산된다.

output: $([a]_1, [b]_1, [c]_1)$

Round 2:

Round 2에서는 permutation challenge $\beta, \gamma$를 얻어내고, permutation polynomial $z(X)$의 commitment가 계산된다. $z(X)$는 copy constraint를 만족함을 증명하는 다항식이다.

output: $([z]_1)$

Round 3:

Round 3에서는 앞서 계산된 다항식 $a(X), b(X), c(X), z(X)$를 이용해 gate constraint와 copy constraint를 만족하는지 검사하기 위한 quotient polynomial $t(X)$를 계산한다.

먼저 transcript로부터 quotient challenge $\alpha$를 계산한다.

$t(X)$는 다음과 같이 계산된다.

매우 더럽지만, $\alpha$의 차수에 대해서 생각했을 때 상수항은 gate constraint를 만족해야 함을 나타내며, 일차항은 $z(X)$가 multiplicative subgroup 위에서 어떻게 정의되는지를 나타내며, 이차항은 $z(\omega) = 1$, 즉 copy constraint가 만족해야 함을 나타낸다. PLONK에서 check하려는 모든 조건이 담겨 있는 다항식임을 알 수 있다.
$t(X)$의 degree가 최대 $3n + 5$일 수 있는데 srs에는 $x^{n+5}$까지만 준비돼 있기 때문에, $t(X)$를 다음과 같이 표현한다.

$t_{lo}(X), t_{mid}(X), t_{hi}(X)$에 대한 commitment를 계산한다.

output: $([t_{lo}]_1, [t_{mid}]_1, [t_{hi}]_1)$

Round 4:

Round 4에서는 다항식들을 각각 특정 점에서 evaluate한다. 먼저 transcript로부터 evaluation challenge $\zeta$를 얻어낸다. 그리고 다음과 같이 다항식들의 opening evaluation을 계산한다.

output: $(\bar{a}, \bar{b}, \bar{c}, \bar{s}_{\sigma1}, \bar{s}_{\sigma2}, \bar{z}_{\omega})$

Round 5:

Round 5가 최종 관문이다. Round 5에서는 모든 다항식들의 evaluation proof를 계산한다. 먼저 transcript로부터 opening challenge $v$를 얻어낸다.

Round 3에서 계산한 quotient polynomial $t(X)$의 형태를 생각해 보자. 분자의 더러운 다항식들을 $p(X)$라고 할 때, $t(X) = {p(X) \over {Z_H(X)}}$ 형태이다. Prover가 $q(X)$를 알고 있음을 증명하기 위해서는 evaluation challenge에서 $t(X), Z_H(X), p(X)$를 각각 계산한 값들을 전달하면 된다. 총 3개의 field element를 전달해야 한다.
PLONK paper에서는 다항식을 open할 때 Prover가 전달해야 하는 field element의 개수를 줄이기 위해 linearisation polynomial을 만든다.

Linearisation polynomial은 다음과 같이 정의된다.

진짜 뭔가 싶지만 $t(X) = {p(X) \over {Z_H(X)}}$를 $r(X) = p(X) - t(X)Z_H(X)$ 형태로 바꾼 것 뿐이다. $t(X), Z_H(X), p(X)$ 각각에 대해 evaluation proof를 만드는 대신에, $r(\zeta) = 0$에 대한 evaluation proof만 생성하면 된다. $r(X)$의 commitment는 $q_M(X), q_L(X), q_R(X), q_O(X), q_C(X), z(X), S_{\sigma 3}(X), t_{lo}(X), t_{mid}(X), t_{hi}(X)$에 대한 commitment들로 계산할 수 있다는 것이 또 다른 포인트다.

자, 이제 첫 번째 opening proof polynomial $W_{\zeta}(X)$를 계산한다.

이 다항식은 $r(X), a(X), b(X), c(X), S_{\sigma1}(X), S_{\sigma2}(X)$들을 $\zeta$에서 evaluation proof들을 random linear combination한 것이다.

두 번째 opening proof polynomial $W_{\zeta w}(X)$를 계산한다.

서로 다른 점 $\zeta, \zeta \omega$에서 evaluate됐음을 알 수 있다. 뒤에서 Batched KZG를 쓸 예정이다.
마지막으로 opening proof polynomial들의 commitment를 계산한다.

output: $([W_{\zeta}]_1, [W_{\zeta \omega}]_1)$

PLONK prover algorithm의 결과는 다음과 같다.

그냥 각 라운드별로 계산한 output들 전부 모은 거다. 마지막으로 transcript에서 multipoint evaluation challenge $u$를 얻어낸다. Batched KZG를 참고하길 바란다.

아쉽게도 모든 게 끝난 게 아니다. 다음은 Verifier algorithm을 알아보자.