[Note] PLONK algorithm - Verifier

PLONK의 verifier algorithm을 알아보자. Verifier의 preprocessed input은 다음과 같다.

Verifier preprocessed input

Common preprocessed input의 다항식들의 commitment + toxic waste가 $\mathbb{G}_2$에서 hiding된 값들로 이루어져 있다.

Verifier algorithm

Verifier algorithm의 input은 circuit의 public input $(w_i)_{i \in [n]}$과 $\pi_{SNARK}$이다.

$V((w_i)_{i \in [n]}, \pi_{SNARK}):$

1. $([a]_1, [b]_1, [c]_1, [z]_1, [t_{lo}]_1, [t_{mid}]_1, [t_{hi}]_1, [W_{\zeta}]_1, [W_{\zeta \omega}]_1) \in \mathbb{G}_1^9$

$\pi_{SNARK}$의 각 다항식들의 commitment가 $\mathbb{G}_1$의 element인지 확인

2. $(\bar{a}, \bar{b}, \bar{c}, \bar{s}_{\sigma1}, \bar{s}_{\sigma2}, \bar{z}_{\omega}) \in \mathbb{F}^6$

$\pi_{SNARK}$의 opening evaluation들이 field의 element인지 확인

3. $(w_i)_{i \in [l]} \in \mathbb{F}^l$

Public input들이 field의 element인지 확인

4. Prover와 동일한 방법으로 transcript로부터 challenge 값 $\beta, \gamma, \alpha, \zeta, v, u$ 얻어냄

5. $Z_H(\zeta)$ 계산

6. $L_1(\zeta)$ 계산

7. $PI(\zeta)$ 계산

8. 여기부터 Batched KZG를 사용하는 부분이다. $\pi_{SNARK}$의 $[W_{\zeta}]_1, [W_{\zeta \omega}]_1$의 형태를 떠올려보자.

$\zeta$에서 $r(X), a(X), b(X), c(X), S_{\sigma1}(X), S_{\sigma2}(X)$의 evaluation proof들과 $\zeta \omega$에서 $z(X)$의 evaluation proof를 KZG로 batch verify하는 과정이 될 것이다. 먼저 step 7에서는 verifier의 scalar multiplication을 줄이기 위해 linearisation polynomial을 약간 변형한다.

역시나 처음에는 이 짓거리를 왜 하나 싶지만, 약간만 생각해 보면 $r'(\zeta) = r(\zeta) - r_0$가 되고, $r(\zeta) = 0$이기 때문에 $r'(\zeta) = - r_0$를 바로 얻을 수 있기 때문이다. 다항식 하나에 대한 evaluation을 꽁으로 얻은 셈이지.

9. Batched polynomial commitment의 첫 번째 부분을 계산

KZG batch verify algorithm에서 $\mathbb{G}_1$의 element $F$의 형태를 생각해 보자. Random challenge $\gamma, \gamma'$ power의 계수들이 각각 $\{cm_i - f_i(z)\}, \{cm'_i - f'_i(z')\}$ 형태였다. Step 9에서는 각 다항식들의 commitment의 합부터 계산한다.

$[D]_1$ 계산은 너무 더러우므로 생략.
$a(X), b(X), c(X), S_{\sigma1}(X), S_{\sigma2}(X)$의 commitment는 step 10에서 계산한다. 왜 나누어져 있는지는 모르겠다.

10. Full batched polynomial commitment 계산

$a(X), b(X), c(X), S_{\sigma1}(X), S_{\sigma2}(X)$의 commitment들까지 계산해서 $[D]_1$에 더한다.

11. Group-encoded batch evaluation 계산

이제 모든 다항식들의 opening evaluation들의 random linear combination한 값을 $\mathbb{G}_1$으로 encoding한 $[E]_1$을 계산한다.

12. 드디어 마지막 단계... KZG batch verify algorithm의 pairing check 단계이다. Pairing check equation은 다음과 같다.

이로써 PLONK verifier algorithm까지 모두 살펴보았다. 식이 너무 더러워서 절대 paper를 읽어보고 싶지 않았는데, 한 번 쭉 훑어보았다.

현재 research 중인 주제로 EVM 상에서 PLONK verifier를 구현하는 건데, 마지막 pairing check가 비싼 연산이라서 여러 개의 proof를 aggregation해서 한 번의 pairing check만 하도록 하는 게 중요한 포인트다.