# PlonK Verify
### PlonK Verifier Round
지금까지 Prover가 Proof를 어떻게 생성하는지 확인해봤다면, 이제부터 Verifier가 prover로부터 받은 proof를 어떻게 검증하는지 살펴보자.
#### **Verifier 알고리즘**
**검증자 전처리 입력 (Verifier preprocessed input):**
* $$\[q\_M]\_1 := q\_M(x) \cdot \[1]\_1,\[q\_L]\_1 := q\_L(x) \cdot \[1]\_1,\[q\_R]\_1 := q\_R(x) \cdot \[1]\_1,\[q\_O]\_1 := q\_O(x) \cdot \[1]\_1,$$\
$$\[q\_C]\_1 := q\_C(x) \cdot \[1]\_1,\[s{\sigma1}]\_1 := S{\sigma1}(x) \cdot \[1]\_1,\[s{\sigma2}]\_1 := S{\sigma2}(x) \cdot \[1]\_1,$$
$$\[s\_{\sigma3}]\_1 := S{\sigma3}(x) \cdot \[1]\_1,x \cdot \[1]\_2$$
**Prover로 부터 받은 값들의 유효성 확인**
수신한 $$\pi\_{SNARK}$$에 포함된 그룹 원소와 필드(field) 원소들이 올바른 형식을 갖췄는지 확인한다.
* **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)$$가 $$G\_1^9$$에 속하는지 확인한다.
각각의 값들은 prover가 commitment를 거쳐서 보내기 때문에 그래프 위의 한 점$(x\_a,y\_a)$이 된다. 따라서 $$G\_1$$이 $$y^2=x^3+Ax+B$$와 같은 특정 방정식으로 이뤄졌다고 할 때, 그래프에 각각의 점들을 넣어서 그래프 위의 점인지 확인하는 것이다.
* **2단계:** $$(\overline{a}, \overline{b}, \overline{c}, \overline{s\_{\sigma1}}, \overline{s\_{\sigma2}}, \overline{z\_{\omega}})$$가 $$F^6$$에 속하는지 확인한다.
$$(\overline{a}, \overline{b}, \overline{c}, \overline{s\_{\sigma1}}, \overline{s\_{\sigma2}}, \overline{z\_{\omega}})$$의 여섯 개 값들은 각각 스칼라 값에 해당한다. 따라서 각 값에 대한 기본적인 유효성 검사를 진행한다. verifier는 받은 각각의 값이 소수 필드 $$\mathbb{F}$$의 유효한 원소인지 확인한다. 이 필드는 크기가 $$r$$로 정의되며, 유효한 원소는 일반적으로 0부터 $$r−1$$ 사이의 정수여야한다.
* **3단계:** $$(w\_i)\_{i \in \[\ell]}$$가 $$F^ℓ$$에 속하는지 확인한다.
Prover가 보낸 각 공개 입력 값( $$w\_i$$)이 필드 $$\mathbb{F\_l}$$의 정의된 범위 내에 있는지 확인한다.
**챌린지 복구 및 다항식 평가**
증명자와 동일한 방식을 사용하여, 공개 정보와 증명의 각 부분을 순차적으로 해시(hash)함으로써 모든 무작위 챌린지값을 복구하고, 필요한 다항식을 계산한다.
* **4단계:** 공통 입력, 공개 입력, 그리고 $$\pi\_{SNARK}$$의 요소들로부터 증명자의 설명과 같이 챌린지 $$\beta, \gamma, \alpha, \zeta, \nu, u \in \mathbb{F}$$를 계산한다.
verifier는 Fiat-Shamir heuristic을 사용해서 챌린지($$β,γ,α,ζ,ν,u$$)를 계산한다. 여기서 Transcript는 모든 공개된 정보(공통 전처리 입력, 공개 입력, 증명자가 보낸 증명 요소들)를 순서대로 하나로 합친 것을 말한다. Verifier는 이 transcript를 해시함수 $$\mathcal{H}$$(hash)에 입력하여 무작위처럼 보이는 챌린지 값들을 생성한다.
예를 들어, $$β=H(transcript), γ=H(transcript|β), α=H(transcript|β|γ)$$ 와 같이, 트랜스크립트에 특정 값을 추가하여 여러 개의 챌린지 값을 만드는 것이다.
* **5단계:** 영 다항식 평가값 $$Z\_H(ζ)=ζ^n−1$$을 계산한다.
영 다항식 $$Z\_H(X)$$는 **곱셈 부분군 H의 모든 원소에서 0이 되는** 다항식을 말한다. 이 부분군 H는 $$\mathbb{F}$$에서 n차 단위근(n'th roots of unity)으로 구성된다. 따라서 이 다항식은 $$X^n−1$$형태를 가진다. Verifier는 Prover가 만든 다항식(예: 회로의 제약 조건을 인코딩한 다항식)이 부분군 H의 모든 지점에서 0이 된다고 주장하는 것을 검증해야 한다. 이때, 다항식 전체를 확인하는 것이 아니라 무작위 챌린지 $$\zeta$$를 던진다. 그리고 $$Z\_H(\zeta)$$ 값을 계산하여, 증명자의 다항식이 $\zeta$지점에서 올바르게 0이 되는지(즉, $$Z\_H(\zeta)$$로 나누어떨어지는지)를 최종적으로 확인한다.
이렇게 한개의 점에서만 확인해도 되는 이유는 PlonK와 같은 영지식 증명의 핵심적인 아이디어 중 하나인 **다항식의 성질**을 활용하는 것이다. 슈워츠-지펠 보조정리(Schwartz-Zippel Lemma)에 따르면, $$P(X)$$가 영 다항식이 아닌 경우, $$P(X)$$가 0이 되는 지점의 수는 다항식의 차수($\deg(P)$)보다 많을 수 없다. 따라서, 우리가 필드 $$\mathbb{F}$$에서 무작위로 하나의 값( $$\zeta$$)을 선택했을 때, $$P(\zeta)$$가 0일 확률은 $$\frac{\deg(P)}{|\mathbb{F}|}$$보다 작다. 만약 필드의 크기( $$|\mathbb{F}|$$)가 다항식의 차수( $$\deg(P)$$)보다 훨씬 크다면, $$P(ζ)=0$$이 될 확률은 매우 낮다. 즉, 항등식이 아닌 다항식이 무작위 지점에서 0이 될 확률은 매우 낮은데 이걸 만족했다는 건 Prover가 만든 다항식은 H의 모든 지점에서 0이 된다는 소리이다.
* **6단계:** 라그랑주 다항식 평가값 $$L\_1(\zeta) = \frac{\omega(\zeta^n - 1)}{n(\zeta - \omega)}$$을 계산한다.
순열 다항식 $$z(X)$$의 **시작점 제약**을 검증하기 위한 과정이다. 여기서 라그랑주 다항식 $$L\_1(X)$$는 **단일 지점에서만 1의 값을 갖고, 나머지 모든 지점에서는 0이 되는** 특별한 다항식이다. 여기서 '단일 지점'은 곱셈 부분군 H의 첫 번째 원소인 $$ω^0=1$$이다.
$$L\_1(X) = \frac{Z\_H(X)}{n(X-\omega^0)}$$와 같이 정의할 수 있는데 여기에 $$ω^0=1$$을 대입하여 정리하면 $$L\_1(X) = \frac{X^n-1}{n(X-1)}$$이 된다.
PlonK의 순열 제약에는 $$z(X)$$ **다항식이** $$X=1$$**에서 1의 값을 가져야 한다**는 규칙이 있다. 이는 누적 곱의 시작점이 올바른 값으로 시작되었음을 보장하기 위함이다. 증명자는 $$\frac{(z(X)-1)L\_1(X)\alpha^2}{Z\_H(X)}$$라는 항을 몫 다항식 $$t(X)$$에 포함시킵니다. 만약 $$z(1)\neq1$$이라면, 이 항은 X=1에서 0이 되지 않아 전체 몫 다항식이 $$Z\_H(X)$$로 나누어떨어지지 않는다.
* $$Z\_H(X)$$는 $$X^n-1$$의 형태를 가질 것이고, 임의의 지점에서 나누어 떨어지려면 $$L\_1(X)$$가 $$X=1$$이 아닌 모든 지점에서 0이 되어야 한다.
* **만약** $$Z(1)=1$$**이 참이라면:** $$X=1$$ 지점에서 $$(Z(1)−1)=0$$이므로, 분자 전체가 0이 된다. $$X \neq 1$$인 H의 다른 지점에서는 $$L\_1(X)=0$$이므로, 역시 분자 전체가 0이 된다. 따라서 분자는 H의 모든 지점에서 0이 되어 $$Z\_H(X)$$로 **나누어 떨어진다.** 이 경우 프로토콜이 성공한다.
* **만약** $$Z(1)\neq1$$**이 거짓이라면:** X=1 지점에서 $$(Z(1)−1)\neq 1$$이고, $$L\_1(1)=1$$이므로 분자는 **0이 되지 않는다.** 분자가 $$X=1$$에서 0이 아니므로, H의 모든 원소를 근으로 갖는 $$Z\_H(X)$$로는 **나누어 떨어지지 않는다.** 이 경우 최종 몫 다항식 $$t(X)$$가 유효하지 않게 되어, 검증자는 증명을 **거부**하게 된다.
* **7단계:** 공개 입력 다항식 평가값 $$PI(\zeta) = \sum\_{i \in \[\ell]} w\_iL\_i(\zeta)$$를 계산한다.
Prover가 제공한 공개 입력 값( $$w\_i$$)이 최종 검증식에 올바르게 포함되도록 하기 위해서 공개 입력 다항식 평가값을 계산한다. $PI(X)$는 회로의 공개 입력 값들( $$w\_1,…,w\_ℓ$$)을 인코딩하는 다항식이다. $$PI(X)$$는 각 공개 입력 값($$w\_i$$)에 해당하는 라그랑주 다항식( $$L\_i(X)$$)을 곱한 후 모두 더하여 만들어진다. 여기서는 특정값 $$\zeta$$에서의 $$PI(X)$$를 구한다. 여기서 $$L\_i(X)$$는 곱셈 부분군 H의 i번째 원소( $$g^{i−1}$$)에서만 1의 값을 갖고, 나머지 지점에서는 0이 되는 라그랑주 다항식이다. PI는 아래와 같은 식이 되는데 이를 통해서 H의 i번째 지점( $$g^{i−1}$$)에서 $$PI(X)$$를 평가하면, 정확하게 $$w\_i$$만 남고 나머지 항은 모두 0이 된다.\
$$PI(g^{i−1})=w\_1L\_1(g^{i−1})+⋯+w\_iL\_i(g^{i−1})+…$$
$$PI(g^{i−1})=w\_1⋅0+⋯+w\_i⋅1+⋯=w\_i$$
만약 증명자가 $$PI(X)$$ 를 직접 만들게 허용하면, 증명자가 공개 입력값을 조작하여 부정행위를 시도할 수 있다. 하지만 검증자가 직접 $$PI(X)$$를 재구성하고 이를 증명자의 다항식과 비교하면, 공개 입력값이 올바르게 사용되었음을 확실하게 검증할 수 있다.
**최종 검증식 만들기(일괄 다항식 구성 및 일괄 평가값 구성)**
검증자는 효율적인 연산을 위해 회로의 모든 제약 조건과 평가값들을 선형 결합하여 하나의 거대한 식으로 통합하고, 단 한 번의 페어링 연산으로 증명의 유효성을 최종 확인한다.
* **8단계:** 검증자의 스칼라 곱셈을 절약하기 위해, r을 상수항과 비-상수항으로 나눈다. r의 상수항을 계산한다
$$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}}$$
그리고 $$'(X) := r(X) - r\_0$$라고 둡니다.
계산을 최적화하기 위해 다항식 $$r(x)$$를 다음과 같이 분리한다.
$$r(X)=r\_0+r^′(X)$$
* $$r\_0$$ : X와 관련이 없는 상수항
$$r\_0$$ 는 다항식 $$r(X)$$를 무작위 챌린지 $$ζ$$에 대해 평가한 값들의 조합으로 계산된다.
증명자가 보낸 평가값들( $$\overline{a}, \overline{b}$$ 등)과 자신이 계산한 챌린지 값들( $$α,β,γ$$ 등)을 사용하여 $$r\_0$$를 직접 계산한다.
* $$r^′(X)$$ : X에 대한 다항식
$$r'(X)$$는 전체 다항식 $$r(X)$$에서 상수항 $$r\_0$$를 뺀 나머지 부분
* **9단계:** 일괄 다항식 커밋먼트의 첫 번째 부분 $$\[D]\_1:=\[r^′]\_1+u⋅\[z]\_1$$을 계산한다
$$\[D]\_1$$는 회로의 모든 제약 조건이 다항식 형태로 올바르게 만족되었는지 확인하기 위해 verifier가 직접 재구성하는 핵심적인 암호화된 값이다. 위의 식은 매우 복잡해 보이는데 이것들은 PlonK의 여러개의 제약 조건 확인을 하나로 합쳐놓은 식이다.
$$\begin{aligned} \[D]\_1 := {}& \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( (\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 \ &- Z\_H(\zeta)\Big(\[t{lo}]1 + \zeta^n \[t{mid}]1 + \zeta^{2n}\[t{hi}]\_1\Big) \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)$$
즉, $$\[D]\_1$$는 이 모든 복잡한 검증 논리를 하나의 그룹 원소로 압축한 뒤, 최종 페어링 검증식에 사용된다.
* **10단계:** 전체 일괄 다항식 커밋먼트 $$\[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$$
Prover가 제출한 모든 증명 다항식들의 커밋먼트를 하나의 값으로 합친다.
* $$\[D]\_1$$: 앞서 계산한 값으로, **게이트 제약, 순열 제약, 그리고 몫 다항식 제약**이 모두 결합된 다항식 커밋먼트. 이 자체로 이미 프로토콜의 핵심적인 논리를 담고 있다.
* $$ν,ν^2,ν^3,ν^4$$: 이들은 검증자가 라운드 5에서 계산한 **무작위 챌린지 ν의 거듭제곱**. 이 무작위 값들은 증명자가 특정 항에만 맞춰서 속이는 것을 방지하는 역할을 한다.
* $$\[a]\_1,\[b]\_1,\[c]\_1$$: 라운드 1에서 증명자가 보낸 **와이어 다항식의 커밋먼트**.
* $$\[sσ\_2]\_1$$: 순열 제약 확인에 사용되는 **순열 다항식의 커밋먼트**.
이 커밋먼트는 **와이어 값, 게이트 논리, 순열 제약 등** 모든 증명 요소들이 포함된 다항식 커밋먼트의 총합이다.
* **11단계**:그룹-인코딩된 일괄 평가( $$\[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)'되었는지 확인하는 역할을 한다.
* **12단계:** 모든 평가들을 **일괄적으로 검증**한다.
결국 verifier가 검증하는 것은 ‘증명자가 제출한 정보가 검증자가 재구성한 정보와 일치한다'는 것이다. 아래의 식에서 좌변은 증명자가 주장하는 ‘압축된 다항식 정보’이고, 우변은 증명자가 제출한 평가값들( $$\[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)$$
$$LHS=x⋅Wζ(x)+u⋅Wζω(x)⋅x$$
$$RHS = \zeta \cdot W\_\zeta(x) + u\zeta\omega \cdot W\_{\zeta\omega}(x) + (W\_\zeta(x)(x-\zeta)+r(\zeta)) - E(x)$$ \
( $$F(X)= Wζ(X) · (X - ζ) + r(ζ)$$)
$$= \zeta \cdot W\_\zeta(x) + u\zeta\omega \cdot W\_{\zeta\omega}(x) + x \cdot W\_\zeta(x) - \zeta \cdot W\_\zeta(x) + r(\zeta) - E(x)$$
$$= x \cdot W\_\zeta(x) + u\zeta\omega \cdot W\_{\zeta\omega}(x) + r(\zeta) - E(x)$ $= x⋅Wζ(x)+uζω⋅Wζω(x)$$
#### Why This Design?
전체 검증자(Verifier) 과정은 **효율성**에 초점을 맞추고 있다.
* **간결성 (Succinctness):** 검증자는 회로의 크기(n)에 비례하는 연산을 수행하지 않는다. 모든 계산은 증명의 크기에만 의존하며, 이는 거의 상수 시간(near-constant time)에 가깝다.
* **비상호작용성 (Non-interactive):** 검증은 제출된 증명만으로 완료될 수 있으며, 증명자와 상호작용할 필요가 없다
* **일괄 처리 (Batching):** 여러 개의 KZG 개봉 증명들이 압축되어 단 두 번의 페어링 연산만으로 검증된다. 이것이 바로 PlonK의 빠른 검증 속도를 가능하게 하는 핵심적인 최적화 기술이다.
### Reference
1. [PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge](https://eprint.iacr.org/2019/953.pdf)
2. [ZKP MOOC Lecture 5: The Plonk SNARK](https://www.youtube.com/watch?v=A0oZVEXav24)
3. [PLONK by hand](https://www.google.com/url?q=https://research.metastate.dev/plonk-by-hand-part-1/\&sa=D\&source=docs\&ust=1756311378886581\&usg=AOvVaw3Ky2xwxTL5boldt3fEh1DE)
4. [EXPLORING PLONK](https://hackmd.io/@Zer0Luck/EXPLORING-PLONK#11-Gate-Constraints)
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://upsidezkp.gitbook.io/upside-zkp-docs/step-2/kzg-plonk/plonk-verify.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.