[ZK Study 04] PlonK

“코드 한 줄을 고쳤을 뿐인데, 전 세계 수백 명의 사람을 다시 모아 ‘Ceremony’을 치러야 한다면 믿으시겠습니까?”

불과 몇 년 전, 초기 영지식 증명(ZK) 프로젝트들이 겪었던 악몽 같은 현실이었다. 당시 ZK의 표준이었던 Groth16은 압도적인 성능을 자랑했지만, 한 번 설계하면 수정이 불가능했다. 버그를 고치거나 기능을 추가하려면 수개월의 시간과 막대한 비용을 들여 보안 설정(Trusted Setup)을 처음부터 다시 해야만 했다.

이러한 경직성은 블록체인의 핵심 가치인 ‘빠른 업데이트’와 ‘확장성’을 가로막는 가장 큰 장벽이었다. 이에 따라 개발자들은 생각했다. “그냥 소프트웨어 업데이트하듯이, 한 번 세팅해놓고 프로그램만 갈아 끼울 수는 없을까?”

PlonK는 바로 이 질문에서 탄생했다. ZK의 패러다임을 ‘하드웨어’에서 ‘소프트웨어’로 전환시킨 이 혁신적인 프로토콜이 어떻게 영지식 증명의 대중화를 이끌었는지, 그 작동 원리를 파헤쳐 보겠다.

1. PlonK란 무엇인가: 범용성을 향한 도약

PlonK는 “한 번의 설정으로 다양한 회로를 커버할 수 있다”는 범용성(Universality)을 핵심 무기로 하는 영지식 증명 프로토콜이다.
이름조차 복잡한 약어(Permutations over Lagrange-bases for Oecumenical Non-interactive arguments of Knowledge)로 되어 있지만, 핵심은 ‘Oecumenical(보편적인, 범용적인)’이라는 단어에 있다. 기존 방식들은 회로의 로직이 조금만 바뀌어도 암호학적 설정을 처음부터 다시 해야 하는 ‘회로 종속적(Circuit-specific)’ 구조였지만, PlonK는 충분히 큰 범위의 SRS를 한 번 생성해두면 그 안에서 회로가 달라져도 재설정이 필요 없는 ‘범용적(Universal)’ 구조를 갖추고 있다.

이 때문에 개발자들이 회로를 훨씬 자유롭게 구성할 수 있게 되었고, 2019년 Aztec 팀이 제안한 이후 zkSync, Polygon zkEVM, Scroll 등 현재 대부분의 ZK 롤업 프로젝트들이 Plonkish 계열 프로토콜을 기반으로 사용하고 있다.

2. Groth16과의 차이점

그렇다면 PlonK가 Groth16과 비교해 어떤 차이를 갖는지 살펴보자.

Groth16의 근본적인 한계는 회로 종속적(Circuit-specific)인 신뢰 설정이었다.

Groth16은 증명 크기가 매우 작고 검증 속도도 가장 빠른 축에 속한다는 강점이 있다. 그러나 회로의 로직이 조금만 달라져도 매번 새로운 SRS(Structured Reference String)를 생성해야 한다는 치명적인 제약을 가지고 있다. 이 SRS를 만드는 과정이 바로 ‘Trusted Setup’이며, 이때 생성되는 비밀 값, 즉 ‘독성 폐기물(Toxic Waste)’이 유출되면 시스템 전체의 보안성이 붕괴된다.

따라서 프로젝트가 업데이트될 때마다 전 세계의 참가자들을 모아 안전한 생성·파기 과정을 수행하는 복잡한 “의식(ceremony)”을 반복해야 했고, 이는 유지보수를 심각하게 어렵게 만드는 족쇄였다.

PlonK는 이 문제를 범용적이고 업데이트 가능한(Universal & Updatable) 신뢰 설정으로 해결했다.

PlonK는 충분히 큰 최대 차수(max degree)를 가진 ‘Universal SRS’를 한 번 생성해두면, 그 범위 안에서는 회로가 변경되더라도 SRS를 다시 만들 필요가 없다. 즉, 새로운 기능을 추가하거나 로직을 수정하더라도 매번 의식을 치를 필요 없이 단지 회로를 다시 컴파일하고 배포하면 된다.

비록 증명 크기와 검증 비용이 Groth16보다 약간 증가하는 트레이드오프가 있지만, 개발자가 다양한 회로를 유연하게 설계하고 반복적으로 업데이트할 수 있다는 점에서 훨씬 실용적이다. 이러한 특성 덕분에 PlonK는 ZK 기술이 연구 단계에서 벗어나 산업 현장에서 실질적으로 활용되는 기반이 되었다.

3. PlonK가 증명하려는 것: 다항식을 통한 무결성

PlonK의 목표는 단순하다.

“Prover가 어떤 계산을 올바르게 수행했다는 사실을, 입력값을 공개하지 않고도 증명하는 것.”

그리고 그 접근 방식은 Groth16과 유사하게, 모든 계산 조건을 다항식(polynomial)으로 변환해 검증 가능한 형태로 만드는 데서 출발한다. 하지만 PlonK는 Groth16이 고정된 회로 구조만을 다루는 한계를 넘어서기 위해, 게이트·와이어·연결 관계 전체를 훨씬 유연한 방식으로 다항식화한다.

어떤 프로그램에서 아래와 같은 계산을 수행했다고 주장한다고 한다.

PlonK 역시 이 계산 전체를 산술 회로(Arithmetic Circuit)로 변환하며, 모든 연산은 하나의 게이트(Gate), 게이트 간 데이터 전달은 와이어(Wires)로 나타난다. 다만 PlonK는 Groth16보다 훨씬 일반화된 단일 게이트 형태를 사용해 더 다양한 회로 구조를 단 하나의 방정식으로 처리할 수 있도록 설계되어 있다.

아래 그림은 $(x \cdot y) + x = z$라는 단순한 계산을 회로 형태로 나타낸 것이다. Gate1을 자세히 살펴보면,

와이어 $w_1(x)$ 와 $w_2(x)$가 입력값 $x$와 $y$를 전달하고, 출력 와이어 $w_3(x)$가 $x\cdot y$ 값을 다음 게이트로 넘긴다. 와이어를 통해 값이 흐르고, 각 게이트가 정확한 연산을 하는지를 보여주는 것이다.

이를 좀 더 일반화해서 표현하면, PlonK는 모든 게이트 연산을

라는 하나의 통합된 방정식으로 표현한다. 곱셈이면 $ab - c = 0$, 덧셈이면 $a + b - c = 0$같은 형태가 되어, Prover는 각 게이트가 정확한 연산을 수행했다는 사실을 증명해야 한다.

하지만 개별 게이트의 연산이 올바르다고 해서 전체 계산이 정확하다고 말할 수는 없다. 와이어의 값이 잘 전달되는지 확인해야 한다. 게이트 1의 출력이 게이트 2의 입력으로 정확히 연결되어야 하고, 동일한 입력이 여러 게이트에서 재사용될 때는 값이 완전히 동일해야 한다. 예컨대 $w_3 = a_2, w_1 = w_4$ 같은 연결 규칙들이 모두 보장되어야 한다. Groth16도 이런 동일성 제약을 다항식으로 표현했지만, PlonK는 이보다 더 강력한 구조를 도입한다. 즉, 수많은 wiring 관계를 하나하나 제약으로 기록하는 대신, 전체 wiring을 하나의 순열(permutation)로 추상화해버리는 것이다.

예를 들어, 와이어값이 ($w_1, w_2, w_3, w_4$) 순서로 배치되어 있고, 실제 회로 wiring에 따라 ($w_4, w_3, w_2, w_1$)로 대응된다고 하자. PlonK는 이러한 값의 자리 이동 전체를 단일 순열 σ로 표현하고, 이를 검증하기 위해 Grand Product Polynomial $z(X)$를 사용한다.

원래 값 목록을 $f(i)$, 순열 적용 뒤의 값 목록을 $g(\sigma(i))$ 라 하고, 여기에 치팅 방지를 위해 $\beta, \gamma$로 랜덤화한$f'(i), g'(\sigma(i))$ 를 사용한다. 그러면 PlonK가 최종적으로 확인하고 싶은 것은 다음 하나의 조건뿐이다:

이 식은 사실 매우 직관적이다. 모든 대응 위치에서 값이 정확히 일치했다면 비율 $f'(i)/g'(\sigma(i))$는 모두 1이 되고, 전체 곱 역시 1이 된다. 반대로 하나라도 mismatching이 생기면 곱은 절대 1이 될 수 없다. 이 누적 비율을 관리하는 것이 바로 Grand Product Polynomial Z(X)이다.

즉, $Z$는 각 단계에서의 비율을 계속 곱해가며 누적한 값을 담는 다항식이다. 만약 wiring이 전부 올바르다면 마지막 점에서 $Z(n+1)=1$이 성립하게 된다. 이 하나의 보조 다항식만으로 회로 전체 wiring consistency를 검증할 수 있게 되며, 결과적으로 복잡한 복사·연결 제약들이 하나의 “순열 항등식”으로 압축된다. 이 부분이 PlonK가 Groth16보다 훨씬 더 범용적 회로를 다룰 수 있게 해주는 기술적 핵심이다.

이처럼 PlonK는 회로 전체를 단 몇 개의 다항식으로 요약한다. 모든 게이트의 왼쪽 입력 값은 $a(X)$, 오른쪽 입력 값은 $b(X)$, 출력 값은 $c(X)$라는 세 개의 긴 다항식으로 인코딩된다. 겉보기에는 Groth16과 비슷해 보이지만, PlonK는 고정된 회로에 묶이지 않고 자유로운 wiring과 다양한 게이트 구성을 수용할 수 있도록 이 구조를 훨씬 더 유연하게 확장한다.

4. PLONK prover 1-5 Round

이제 증명자가 최종 증명 $\pi_{SNARK}$를 생성하기 위해 수행하는 구체적인 5개 라운드(Rounds)에 대해 설명한다. 각 라운드는 검증자(Verifier)로부터 받은 챌린지에 응답하고, 다음 라운드에 필요한 증명 구성 요소를 구축하는 과정을 포함한다. (PlonK는 비상호작용 영지식 증명이므로 실제로는 검증자로 부터 챌린지를 받지 않고 피아트-샤미르 휴리스틱을 통해 생성된 챌린지를 사용한다.)

Round 1 : Wire Polynomial Commitment 생성

증명자(Prover)는 알려진 모든 와이어 값(위트니스)을 수학적으로 다루기 쉬운 형태로 변환하는 것으로 시작한다. 이 단계의 목표는 회로의 전체 실행 상태를 세 개의 다항식으로 압축하고, 검증자에게 이를 비밀리에 커밋(commit)하는 것이다.

증명자는 회로의 왼쪽, 오른쪽, 출력 와이어에 해당하는 값들 $(a_i,b_i,c_i)_{i=1}^n$을 보간(interpolate)하여 세 개의 Wire polynomial) $*a(X),b(X),c(X)*$를 만든다. wire polynomial 를 다음과 같이 계산한다. 이때, 영지식을 위해, 랜덤한 블라인딩 스칼라 $*b_1,...,b_6*$를 선택한다.

$a(X) = (b_1 X + b_2) Z_H(X) + \sum_{i=1}^{n} w_i L_i(X)$

$b(X) = (b_3 X + b_4) Z_H(X) + \sum_{i=1}^{n} w_{n+i} L_i(X)$

$c(X) = (b_5 X + b_6) Z_H(X) + \sum_{i=1}^{n} w_{2n+i} L_i(X)$

• $\sum_{i=1}^{n} w_i L_i(X)$ : 와이어 값들을 다항식 평가값으로 인코딩
  라그랑주 기저 다항식 $L_i(X)$는 특정 점($i$)에서만 1이되고 나머지에서는 0이되는 다항식이다. 라그랑주 기저 다항식을 활용하여 $H$의 각 지점에서 순서대로 정확히 $w_1, w_2, ...$ 값을 갖게 한다.
• $(b_1 X + b_2) Z_H(X)$ : 영지식성 추가 소멸 다항식(vanishing polynomial) $*Z_H(X)=X^n−1*$ 을 곱해준다. $*Z_H(X)*$는 우리가 관심 있는 영역(도메인 H)에서는 값이 0이 되는 다항식이다. 이를 활용해서 $H$에서 증명의 유효성(soundness)에는 영향을 주지 않으면서, $H$밖에서의 다항식 값을 무작위화한다. 이는 비밀 와이어 값 $w_i$이 노출되는 것을 방지한다.
  

이렇게 블라인딩 처리된 최종 다항식들을 Kate-Zaverucha-Goldberg (KZG) 다항식 커밋먼트 스킴을 사용하여 커밋한다. 즉, 신뢰할 수 있는 설정(SRS) 값 $[s_i]_1$을 이용해 아래의 커밋먼트를 계산한다.

최종적으로 블라인딩 처리된 증명 다항식의 커밋먼트 $[a],[b],[c]$를 verifier에게 보내고,

Round 2 : Permutation Polynomial Commitment 생성

모든 와이어들이 올바르게 연결되었다는 제약(copy constraint)을 단일 다항식 Z(X)으로 압축하고, 이 다항식을 블라인딩 처리하여 커밋한다.

모든 와이어 연결 정보를 담고 있는 순열 다항식(permutation polynomial) $Z(X)$를 구성한다. 이 다항식은 “누적 곱(running product)” 방식으로 만들어지며 모든 와이어 연결이 올바른지를 확인하는 역할을 하게 된다.

Z(X)의 시작점은 $*Z(g_1)=1*$로 정의한다. 이후 $i=1,…,n$에 대해, 다음과 같은 재귀적인 관계로 $*Z(g_{i+1})*$ 값을 계산하여 $Z(X)$를 구성한다.

$Z(g_{i+1}) := Z(g_i)\cdot \frac{(a_i + \beta g_i + \gamma)(b_i + \beta k_1 g_i + \gamma)(c_i + \beta k_2 g_i + \gamma)}{(a_i + \beta S_{\sigma_1}(g_i) + \gamma)(b_i + \beta S_{\sigma_2}(g_i) + \gamma)(c_i + \beta S_{\sigma_3}(g_i) + \gamma)}$

이 수식은 두 다중집합이 서로의 순열 관계인지 확인하는 과정이다.

• 분자: 게이트에 연결된 각 와이어의 값($*a_i,b_i,c_i*$)과 원래 위치 정보를 결합하여 하나의 항으로 만든다. $g_i,k_1g_i,k_2g_i$는 각각 $a, b, c$ 와이어의 원래 위치 인덱스를 나타낸다.
  
• 분모 : 게이트에 연결된 각 와이어의 과 순열 후 위치 정보를 결합한다. 여기서 $S_{σ1}(g_i),S_{σ2}(g_i),S_{σ3}(g_i)$는 실제 순열 $\sigma$를 인코딩한 다항식으로, 와이어 값들이 연결되어 이동한 후의 위치 인덱스를 나타낸다.
• $\beta, \gamma$: 이 무작위 챌린지들은 증명자가 순열 관계를 속이는 것을 방지하고, 각 와이어 값을 위치 정보와 강력하게 묶어준다.

최종적으로 $Z(X)$를 유형별로 묶어서 정리하면 다음과 같다:

$z(X) = \underbrace{(b_7X^2 + b_8X + b_9)Z_H(X)}_{\text{Part 1}} + \underbrace{L_1(X)}_{\text{Part 2}} + \underbrace{\sum_{i=1}^{n-1} \left( L_{i+1}(X) \prod_{j=1}^{i} \frac{f(\omega^{j-1})}{g(\omega^{j-1})} \right)}_{\text{Part 3}}$

• Part 1 (블라인딩) : 무작위 값을 결합하여 영지식성을 보장 Round 1과 마찬가지로, 영지식을 위해 랜덤 스칼라 $*b_7,b_8,b_9*$를 선택하여 $Z(X)$를 블라인딩 처리한다.
  
• Part 2 : 초기 조건 설정 누적 곱(Accumulated Product)이 반드시 1에서 시작하도록 강제하는 역할을 한다. $X=1$일 때, Part1은 $Z_H(X)$에 의해 0이 되고, Part3는 라그랑주 선형 방정식의 성질로 인해 0이 된다. 이를 통해 순열 다항식 $Z(X)$의 초기 조건이 1이 되는 것을 확인한다.
  
• Part 3 : 누적 곱 확인 모든 와이어의 연결이 올바르다면, 분자에 있는 모든 항의 다중집합과 분모에 있는 모든 항의 다중 집합은 순서만 다를 뿐 정확히 동일하다. 따라서 누적 곱을 계속해 나가면 분자와 분모가 서로 상쇄되어 최종적으로 $Z(g_{n+1})=1$이 된다. (Schwartz-Zippel 보조정리에 기반한 확률적 검증 방법)
  

증명자(Prover)는 이렇게 얻어진 순열 다항식 $Z(X)$에 대해 KZG 커밋먼트를 수행하여, 그룹 원소 $[z]_1$을 계산하고, 이를 검증자(Verifier)에게 보낸다.

Round 3 : 몫 다항식 커밋먼트 (Quotient Polynomial Commitment)

증명자는 피아트-샤미르 휴리스틱을 통해 새로운 무작위 챌린지 $\alpha$를 받는다. 이 $\alpha$를 사용하여 지금까지의 모든 gate constraint와 copy constraint를 단일 다항식으로 통합하고, 이를 소멸 다항식 $Z_H(X)$로 나눈다. 그 결과가 몫 다항식 $t(X)$이다.

여기서 분자 f(X)는 다음과 같이 구성된다.

$\begin{aligned} f(X) &:= \underbrace{\Big( a(X) q_L(X)+ b(X) q_R(X)+ a(X) b(X) q_M(X)+ c(X) q_O(X)+ PI(X)+ q_C(X) \Big)}_{\text{Part1 Gate Constraints}} \\ \\ &\quad + \alpha \cdot \underbrace{\Bigg( \begin{aligned} &\big(a(X) + \beta X + \gamma\big)\big(b(X) + \beta k_1 X + \gamma\big)\big(c(X) + \beta k_2 X + \gamma\big)Z(X) \\ -&\big(a(X) + \beta S_{\sigma_1}(X) + \gamma\big)\big(b(X) + \beta S_{\sigma_2}(X) + \gamma\big)\big(c(X) + \beta S_{\sigma_3}(X) + \gamma\big)Z(X\omega) \end{aligned} \Bigg)}_{\text{Part2 Permutation Constraints}} \\ \\ &\quad + \alpha^2 \cdot \underbrace{\Big(L_1(X)(Z(X)-1) \Big)}_{\text{Part3 Permutation Start Constraints}} \end{aligned}$

• Part1 : 게이트 제한조건
  PlonK의 게이트 방정식이다. 모든 연산이 모든 게이트에서 올바르게 수행되었다면, 이 다항식은 $H$의 모든 지점에서 0이어야 한다. $PI(X)$는 공개 입력을 처리하는 항으로, 상수항 $q_C(X)$를 더하는 것을 포함한다.
• Part2 : 와이어 값 제한조건
  라운드 2의 재귀 관계식 $z(X\omega) = z(X) \cdot f(X)/g(X)$를 $f(X)z(X) - g(X)z(X\omega) = 0$ 형태로 변환한 것이다.
• Part3 : 초기 조건 확인
  $z(X)$가 1에서 시작해야 한다는 제약($z(1)=1$)을 강제한다. $L_1(X)$는 $X=1$에서만 1이고 $H$의 다른 모든 지점에서는 0이므로, 이 항은 $z(1)-1=0$이라는 제약을 $H$ 전체로 확장한다.

이렇게 계산된 t(X)는 차수가 매우 높기 때문에(3n 이상), 효율적인 처리를 위해 이를 n−1차 다항식 세 개로 분할한다.

이 세 조각 각각에 대해 KZG 커밋먼트를 수행하여, 그룹 원소 $[t_{low}]1, [t{mid}]1, [t{high}]_1$을 계산하고 분할된 몫 다항식들의 커밋먼트 $[t_{lo}], [t_{mid}], [t_{hi}]$를 검증자에게 보낸다.

Round 4 : Polynomial Evaluation

지금까지 증명자는 자신의 주장을 여러 다항식($a, b, c, z, t$)으로 공식화하고 이에 대해 암호학적으로 커밋했다. 검증자는 이 다항식들이 특정 항등식을 만족하는지 검증해야 하지만, 다항식 전체를 전송받아 확인할 수는 없다. 이 문제를 해결하기 위해 PlonK는 슈워츠-지펠 보조정리(Schwartz-Zippel Lemma)를 활용한다.

여기서 슈워츠-지펠 보조정리는 서로 다른 두 다항식이 존재할 때, 이 두 다항식이 무작위로 선택된 한 점에서 만날 확률이 0에 가깝다는 것이다. 이 보조정리를 활용하여, 다항식 전체를 비교하는 대신 무작위로 한 점을 선택하여 그 점에서 방정식이 성립하는지 여부를 검증한다. 라운드 4는 이 무작위 지점에서 필요한 모든 다항식 평가값을 계산하고 공개한다.

증명자는 피아트-샤미르 휴리스틱을 통해 이전의 모든 정보를 바탕으로 새로운 무작위 챌린지 $\zeta$를 생성한다. 이 $\zeta$는 모든 다항식이 평가될 무작위 평가 지점이다.
증명자는 $\zeta$와 그 "이웃" 지점인 $\zeta\omega$에서 자신의 다항식들을 평가하여 다음 값들을 계산하고 검증자에게 전송한다.:

• $a(ζ),b(ζ),c(ζ)$ : 세 개의 wire 다항식
• $S_{σ1}(ζ),S_{σ2}(ζ)$ : 두 개의 permutation 다항식
• $z(\zeta\omega)$ : permutation constrain 검증에 필요한 Z(X)다항식은 ζ의 shifted point인 $*ζw*$에서 평가한다.

$\zeta$와 $\zeta\omega$ 지점에서의 각 다항식 평가 값(evaluation)들을 $(\overline{a}, \overline{b}, \overline{c}, \overline{s_{\sigma 1}}, \overline{s_{\sigma 2}}, \bar{z}_{\omega})$을 검증자에게 보낸다. 검증자에게 보낸다.

Round 5 : 선형화 다항식 계산 및 최종 평가

라운드 4에서 증명자는 여러 값에 대한 평가값을 공개했다. 그런데 검증자는 이 값들이 라운드 1-3에서 커밋된 다항식들의 실제 평가값인지 아직 알 수 없다. 라운드 5는 이 모든 평가 주장들을 하나의 효율적인 증명으로 일괄 처리(batch)하여, 공개된 값들의 유효성을 최종적으로 입증하는 것이다.

증명자는 피아트-샤미르 휴리스틱을 통해 두 개의 새로운 무작위 챌린지 $v$와 $u$를 생성한다. $v$는 동일한 지점($\zeta$)에서의 평가들을 일괄 처리하는 데 사용되며, $u$는 서로 다른 지점($\zeta$와 $\zeta\omega$)에서의 평가들을 일괄 처리하는 데 사용된다.
이 챌린지들을 사용하여, 증명자는 두 개의 오프닝 증명 다항식 $W_\zeta(X)$와 $W_{\zeta\omega}(X)$를 구성한다:

첫 번째 Opening Proof Polynomial $*W_ζ(X)*$계산

첫 번째로 계산하는 Opening Proof Polynomial은 $*W_ζ(X)*$이다. 이는 여러 다항식들의 무작위 선형 결합이다. 각 다항식은 특정 평가 지점인 ζ에서 평가된 값들과 결합된다.

$W_\zeta(X) = \frac{1}{X - \zeta} \left( \underbrace{r(X)}_{\text{Part 1}} + \underbrace{v(a(X) - \bar{a}) + v^2(b(X) - \bar{b}) + v^3(c(X) - \bar{c}) + v^4(S_{\sigma1}(X) - \bar{s}_{\sigma1}) + v^5(S_{\sigma2}(X) - \bar{s}_{\sigma2})}_{\text{Part 2}} \right)$

• Part1 : 선형화 다항식
  $r(X) = [\bar{a}\bar{b}q_M(X) + \bar{a}q_L(X) + \bar{b}q_R(X) + \bar{c}q_O(X) + PI(\zeta) + q_C(X)] \\ + \alpha [ (\bar{a} + \beta\zeta + \gamma)(\bar{b} + \beta k_1\zeta + \gamma)(\bar{c} + \beta k_2\zeta + \gamma)z(X) \\ - (\bar{a} + \beta\bar{s}_{\sigma 1} + \gamma)(\bar{b} + \beta\bar{s}_{\sigma 2} + \gamma)(\bar{c} + \beta S_{\sigma 3}(X) + \gamma)\bar{z}_\omega ] \\ + \alpha^2 [ (z(X) - 1)L_1(\zeta) ] \\ - Z_H(\zeta) ( t_{lo}(X) + \zeta^n t_{mid}(X) + \zeta^{2n} t_{hi}(X) )$
  이 다항식은 라운드 3의 $t(X)$와 관련된 복잡한 항등식을 $\zeta$에 대해 선형화(linearizing)한 결과이다. 즉, $\zeta$에서의 평가값들($\bar{a}, \bar{b}, \dots$)을 상수로 취급한다. $r(X)$는 라운드 3에서 커밋된 $t_{low}, t_{mid}, t_{high}$와 라운드 4에서 공개된 평가값들 간의 일관성을 검증한다.
  
• Part2 : 배치 평가된 값들 이것은 $a(\zeta)=\bar{a}, b(\zeta)=\bar{b}$ 등과 같은 지점 $\zeta$에서의 모든 평가 주장들을 무작위 가중치 $v$의 거듭제곱을 사용하여 하나의 다항식으로 결합한다.
  
• $(X-\zeta)$로 나눗셈: 만약 모든 주장이 사실이라면, 괄호 안의 다항식은 $X=\zeta$일 때 0이 되어야 gks다. 따라서 $(X-\zeta)$로 나누어떨어지며, 그 몫이 바로 $W_\zeta(X)$가 된다.

두 번째 Opening Proof Polynomial $*W_{ζω}(X)*$계산

여기서 z(X)는 copy constraint를 나타내는 다항식이고, $\overline{z_{\omega}}$는 이 다항식이 평가된 값이다. 또한 $\zeta\omega$는 무작위 평가점이다. Plonk에서는 copy constraint를 한 칸씩 전진하며 점검하는데, 현재점 $ζ$에서의 관계가 다음점 $ζω$에서도 맞는지 확인해야 하기에 두 곳에서 값을 열어보는 절차가 필요한 것이다. 즉, 이 다항식은 copy constraint가 올바르게 성립하는지 확인하기 위해 사용된다. Plonk Prover Algorithm의 최종 결과는 아래와 같다.

최종적으로 증명자는 마지막으로 두 오프닝 증명 다항식 $W_\zeta(X)$와 $W_{\zeta\omega}(X)$에 대해 KZG 커밋먼트를 수행하여, 그룹 원소 $[W_\zeta]_1$ **와 $[W{\zeta\omega}]_1$을 계산하여 검증자에게 전송한다.

이제 라운드 1부터 5까지 생성된 모든 구성 요소(커밋먼트, 평가값, 오프닝 증명)를 모아, 최종 증명 $\pi_{SNARK}$가 완성되어 검증자에게 전송된다.

---

5. PLONK Verifier : 모든 것을 검증하는 하나의 방정식

증명자(Prover)가 생성한 최종 증명 $\pi_{SNARK}$는 여러 커밋먼트(commitments), 평가값(evaluation values), 오프닝 증명(opening proofs)을 포함하여 구성된다. 검증자의 역할은 이 증명을 사용하여 증명자가 실제로 유효한 연산을 수행했는지 검증한다. 이때 증명자의 비밀 정보(witness) 없이, 매우 효율적인 방식으로 검증을 수행해야 한다.

PlonK 검증자는 모든 것을 한 번에 검증할 수 있는 단일 최종 방정식을 구성하고, 단순히 이 방정식이 성립하는지 여부만 확인한다.

검증자가 증명의 유효성을 확인하기 위해 수행하는 일련의 연산 과정을 순서대로 살펴보자.

과정

검증자는 증명 $\pi_{SNARK}$와 공개 입력값 $(w_i)_{i \in [\ell]}$을 수신하고, 다음 단계를 통해 검증을 수행한다.

1. 증명 유효성 확인 및 챌린지 복구

   • 다음과 같이 두 문장으로 깔끔하게 정리할 수 있습니다.수신된 증명 $\pi_{SNARK}$를 구성하는 모든 데이터가 유효한 형식을 갖추었는지 검증한다. 구체적으로 9개의 그룹 요소와 6개의 필드 요소가 각각 정의된 공간인 $\mathbb{G}_1^9$과 $\mathbb{F}^6$에 올바르게 속해 있는지 확인한다.
   • Prover가 전송한 각 공개 입력 값($w_i$)이 정의된 필드 $\mathbb{F}$의 범위 내에 존재하는지 유효성을 검사한다. 이후 증명자와 동일한 방식으로 공개 입력과 증명 요소를 순차적으로 해시(Hash)하여 트랜스크립트를 재구성하고, 이를 통해 모든 무작위 챌린지($\beta, \gamma, \alpha, \zeta, \nu, u$)를 복구한다

2. 소멸 다항식 및 라그랑주 다항식 평가

   • 무작위 챌린지 $\zeta$에서 소멸 다항식을 평가한다. : $Z_H(ζ)=ζ^n−1$ 소멸 다항식은 부분군 $H$의 모든 원소에서 0이 되는 성질을 가지며, 슈워츠-지펠 보조정리에 의해 무작위 점 $\zeta$에서 증명자의 다항식이 $Z_H(\zeta)$로 나누어떨어지는지 확인하는 것만으로 전체 도메인에서의 유효성을 확률적으로 보장한다. 즉, 이 값이 0이 됨을 확인함으로써 증명자가 생성한 제약 조건이 모든 지점에서 올바르게 만족됨을 효율적으로 검증할 수 있다.
     
   • 무작위 챌린지 $\zeta$에서 라그랑주 다항식을 평가한다. : $L_1(\zeta) = \frac{\omega(\zeta^n - 1)}{n(\zeta - \omega)}$ $L_1(X)$는 첫 번째 지점(X=1)에서만 1이 되고 나머지에서는 0이 되는 특수한 다항식으로, 순열 다항식 $z(X)$의 시작점이 1이어야 한다는 경계 조건($z(1)=1$)을 강제하는 역할을 한다. 만약 시작값이 올바르지 않다면 $L_1(\zeta)$가 포함된 항이 소멸하지 않아 전체 검증이 실패하게 되므로, 이를 통해 누적 곱 연산의 무결성을 확인한다.
     
   • 무작위 챌린지 $\zeta$에서 공개 입력 다항식 $PI(X)$를 평가한다. : $PI(\zeta) = \sum_{i \in [\ell]} w_iL_i(\zeta)$ $PI(X)$는 검증자가 각 공개 입력값 $w_i$에 라그랑주 기저 다항식을 결합하여 직접 재구성하는 다항식으로, 증명자가 공개 입력값을 임의로 조작하는 것을 원천적으로 방지한다. 이 다항식을 $\zeta$에서 평가하여 최종 검증식에 반영함으로써, 약속된 공개 입력값들이 회로 연산에 올바르게 포함되었는지 확실하게 인증한다.
     

1. 일괄 선형 다항식 구성

   검증자는 스칼라 곱셈을 절약하기 위해, r을 상수항과 비-상수항으로 나눈다. : $r(X)=r_0+r^′(X)$

   • 상수항 $r_0$계산 : $r_0 := PI(\zeta) - L_1(\zeta)\alpha^2 - \alpha(\overline{a} + \beta\overline{s_{\sigma1}} + \gamma)(\overline{b} + \beta\overline{s_{\sigma2}} + \gamma)(\overline{c} + \gamma)\overline{z_{\omega}}$
   • 비상수항 계산 : Prover가 제출한 모든 증명 다항식들의 커밋먼트를 하나의 값으로 합친다.
     • 챌린지 $u$를 사용하여 $r(X)$의 비상수 부분과 $z(X)$를 결합한 커밋먼트인 $[D]_1:=[r^′]_1+u⋅[z]_1$을 계산한다 $\begin{aligned}[D]_1 := \;& \underbrace{\Big( \overline{a}\overline{b}\cdot [q_M]_1 + \overline{a}\cdot [q_L]_1 + \overline{b}\cdot [q_R]_1 + \overline{c}\cdot [q_O]_1 + [q_C]_1 \Big)}_{\text{Part 1: 게이트 논리 확인}} \\\\&+ \underbrace{\Bigg( \begin{aligned} &\Big( (\overline{a}+\beta\zeta+\gamma)(\overline{b}+\beta k_1\zeta+\gamma)(\overline{c}+\beta k_2\zeta+\gamma)\alpha + L_1(\zeta)\alpha^2 + u \Big)\cdot [z]_1 \\ &- (\overline{a}+\beta\overline{s_{\sigma1}}+\gamma)(\overline{b}+\beta\overline{s_{\sigma2}}+\gamma)\alpha\beta\overline{z_{\omega}}\cdot [s_{\sigma3}]_1 \end{aligned} \Bigg)}_{\text{Part 2: 순열 제약 확인}} \\\\&+ \underbrace{\Bigg( - Z_H(\zeta)\Big([t_{lo}]_1 + \zeta^n [t_{mid}]_1 + \zeta^{2n}[t_{hi}]_1\Big) \Bigg)}_{\text{Part 3: 몫 다항식 확인}}\end{aligned}$
       • 게이트 논리 확인 : 회로의 각 게이트가 올바른 연산을 수행했는지를 확인하는 식
         $\overline{a}\overline{b} \cdot [q_M]_1 + \overline{a} \cdot [q_L]_1 + \overline{b} \cdot [q_R]_1 + \overline{c} \cdot [q_O]_1 + [q_C]_1$
       • 순열 제약 확인 : 회로의 와이어 연결이 올바른지를 확인하는 순열 확인 논리를 담은 식
         $\begin{aligned} &\Big( (\overline{a}+\beta\zeta+\gamma) (\overline{b}+\beta k_1\zeta+\gamma) (\overline{c}+\beta k_2\zeta+\gamma)\alpha \\ &\qquad + L_1(\zeta)\alpha^2 + u \Big)\cdot [z]1 \\ &\;- (\overline{a}+\beta\overline{s{\sigma1}}+\gamma) (\overline{b}+\beta\overline{s_{\sigma2}}+\gamma) \alpha\beta\overline{z_{\omega}}\cdot [s_{\sigma3}]_1 \end{aligned}$
       • 몫 다항식 확인 : 증명자가 보낸 몫 다항식($t(X)$)이 영 다항식($Z_H(X)$)으로 나누어떨어짐을 증명
         $-Z_H(\zeta)([t_{lo}]1 + \zeta^n \cdot [t{mid}]1 + \zeta^{2n} \cdot [t{hi}]_1)$
     • 챌린지 $v$를 사용하여 $[D]_1$과 $\zeta$에서 평가된 모든 다항식 커밋먼트를 함께 배치 처리한 최종 결합 커밋먼트인 전체 일괄 다항식 커밋먼트 $[F]_1$을 계산한다.
       $[F]_1 := [D]_1 + \nu \cdot [a]_1 + \nu^2 \cdot [b]_1 + \nu^3 \cdot [c]1 + \nu^4 \cdot [s_{\sigma2}]_1$
       • $[D]_1$: 앞서 계산한 값으로, 게이트 제약, 순열 제약, 그리고 몫 다항식 제약이 모두 결합된 다항식 커밋먼트. 이 자체로 이미 프로토콜의 핵심적인 논리를 담고 있다.
       • $ν,ν^2,ν^3,ν^4$: 이들은 검증자가 라운드 5에서 계산한 무작위 챌린지 ν의 거듭제곱. 이 무작위 값들은 증명자가 특정 항에만 맞춰서 속이는 것을 방지하는 역할을 한다.
       • $[a]_1,[b]_1,[c]_1$: 라운드 1에서 증명자가 보낸 와이어 다항식의 커밋먼트.
       • $[sσ_2]_1$: 순열 제약 확인에 사용되는 순열 다항식의 커밋먼트.

2. 일괄 평가값 계산

   그룹-인코딩된 일괄 평가($[E]1$)를 계산한다.

   $[E]_1 := -r_0 + \nu\overline{a} + \nu^2\overline{b} + \nu^3\overline{c} + \nu^4\overline{s{\sigma1}} + \nu^5\overline{s{\sigma2}} + u\overline{z_{\omega}}$

   증명자가 보낸 평가값들을 무작위 챌린지($ν,u$)를 이용하여 하나의 그룹 원소로 선형 결합한다. $[E]_1$는 모든 평가값들을 하나의 값으로 합친 뒤, 최종 검증식(12단계)에 사용되어 증명자의 주장들이 올바르게 '개봉(open)'되었는지 확인하는 역할을 한다.

3. 모든 평가들을 일괄적으로 검증

   결국 verifier가 검증하는 것은 ‘증명자가 제출한 정보가 검증자가 재구성한 정보와 일치한다'는 것이다. 검증자는 모든 것을 결합하여 단일 페어링 방정식을 확인한다. 이 방정식은 배치된 KZG 오프닝 증명이 유효한지 검증한다.

   아래의 식에서 좌변은 증명자가 주장하는 ‘압축된 다항식 정보’이고, 우변은 증명자가 제출한 평가값들($[F]_1, [E]_1$)을 기반으로 검증자가 재구성한 것이다.

   $e([W_\zeta]_1 + u \cdot [W{\zeta\omega}]_1, [x]_2) \stackrel{?}{=} e(\zeta \cdot [W\zeta]_1 + u\zeta\omega \cdot [W{\zeta\omega}]_1 + [F]_1 - [E]_1, [1]_2)$

왜 이 디자인인가?

전체 검증자(Verifier) 과정은 효율성에 초점을 맞추고 있다.

• 간결성 (Succinctness): 검증자는 회로의 크기(n)에 비례하는 연산을 수행하지 않는다. 모든 계산은 증명의 크기에만 의존하며, 이는 거의 상수 시간(near-constant time)에 가깝다.
• 비상호작용성 (Non-interactive): 검증은 제출된 증명만으로 완료될 수 있으며, 증명자와 상호작용할 필요가 없다
• 일괄 처리 (Batching): 여러 개의 KZG 개봉 증명들이 압축되어 단 두 번의 페어링 연산만으로 검증된다. 이것이 바로 PlonK의 빠른 검증 속도를 가능하게 하는 핵심적인 최적화 기술이다.

---

Reference

1. PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge
2. ZKP MOOC Lecture 5: The Plonk SNARK
3. PLONK by hand
4. EXPLORING PLONK