# The Pinocchio Protocol {% hint style="warning" %} **목표 : zk-SNARK를 구현한 대표적인 프로토콜인 Pinocchio Protocol을 통해 복잡한 계산을 증명하는 ZK-SNARKs 계열의 기초를 학습한다.** {% endhint %} ## The Pinocchio Protocol Pinocchio Protocol은 zk-SNARK(영지식 간결 비대화형 지식 증명)의 선구적인 프로토콜 중 하나이다. Pinocchio는 동형 암호(Homomorphic Hiding)와 KoE(Knowledge of Exponent)등의 암호학적 기술을 활용한다. 이를 통해 증명자는 자신이 알고 있는 witness를 공개하지 않고도, $$A(x)⋅B(x)−C(x)=H(x)⋅T(x)$$와 같은 다항식 방정식의 해를 알고 있음을 간결하게 증명한다. Pinocchio Protocol은 우리가 증명하고자 하는 것을 다항식으로 변환하는 과정이 필요하다. 해당 과정을 자세하게 알아보자. #### 진행 순서 1. **평탄화 (Flattening)** 임의의 복잡한 constraint를 하나의 연산을 처리하는 간단한 식으로 바꾼다. \ **예시** 원래 식 : $$out = x^3 + x + 5$$ 평탄화 과정(총 4개의 게이트로 표현 가능): | Step | 게이트 표현 | 설명 | | ---- | ------------------ | ------------ | | 1 | `sym_1 = x * x` | $$x^2$$ 계산 | | 2 | `y = sym_1 * x` | $$x^3$$ 계산 | | 3 | `sym_2 = y + x` | $$x^3+x$$ 계산 | | 4 | `~out = sym_2 + 5` | 최종 출력 | 2. **Gates to R1CS** R1CS (Rank-1 Constraint System) 부분은 모든 계산을 `L * R = O` (좌항 \* 우항 = 출력) 형태의 제약으로 변환하는 것이 핵심이다. 회로에 사용되는 모든 변수를 하나의 벡터(`s`)로 매핑한다.
각 게이트를 A(좌항) \* B(우항) = C(출력)의 형태로 만들고, 각각에서 A는 A끼리, B는 B끼리, C는 C끼리 모아 메트릭스를 구성한다.
1. **벡터 생성**\ **순서 규칙** 1. 항상 값이 1인 변수 `one` (상수항 처리를 위해 필요) 2. 공개 입력 변수 (public inputs) 3. 출력 변수 (예: `~out`) 4. 중간 변수 (평탄화에서 생성된 sym 계열) **예시** 0 : one → 항상 1 1: x → 공개 입력 2: \~out → 최종 출력 3: sym\_1 → x² 4: y → x³ 5: sym\_2 → x³ + x \ 최종 벡터 : \[one, x, \~out, sym\_1, y, sym\_2] 2. **Gate → R1CS 제약 변환** 각 게이트는 `(s·a) * (s·b) = (s·c)` 꼴로 표현된다. (여기서 `a,b,c`는 s 길이와 같은 계수벡터) **Gate별 a, b, c 및 검증**
게이트수식a (L)b (R)c (O)
G1sym_1 = x * x[0,1,0,0,0,0][0,1,0,0,0,0][0,0,0,1,0,0]
G2y = sym_1 * x[0,0,0,1,0,0][0,1,0,0,0,0][0,0,0,0,1,0]
G3sym_2 = y + x → (y + x)*1 = sym_2[0,1,0,0,1,0][1,0,0,0,0,0][0,0,0,0,0,1]
G4~out = sym_2 + 5 → (sym_2 + 5*1)*1 = ~out[5,0,0,0,0,1][1,0,0,0,0,0][0,0,1,0,0,0]

R1CS를 마친 이후 결과

3. **R1CS to QAP** 지금까지는 각 gate에 대한 검증을 $$A(x) \* B(x) - C(x) =0$$을 통해서 검증한다. 그러나 암호학적으로 수많은 지점에서의 등식 만족 여부를 하나하나 검증하는 것은 비효율적이다. 따라서 제약조건을 일일이 계산하지 않기 위해 QAP를 이용해서 각 벡터를 다항식으로 변환한다.
QAP 변환은 Lagrange interpolation을 이용하며, Lagrange interpolation은 특정한 점들을 모두 지나는 다항식을 구할 수 있다.
Lagrange interpolation은 다음과 같이 수행된다. * 얻고자 하는 y 좌표가 있는 점 한 개를 정한다. * 해당 점을 제외한 나머지 점은 y좌표를 0으로 설정하며, 나머지 점을 지나는 다항식을 만든다. (y가 0이므로 쉽게 구할 수 있다.) * 구한 다항식에 얻고자 하는 y좌표를 다항식에 곱해주고 현재 다항식에 얻고자 하는 y좌표에 대한 x값을 넣었을 때 나오는 값으로 나눠준다. * 모든 점들에 대해 수행 후 도출된 다항식을 모두 더해준다. 과정을 봤을 때, 쉽게 이해가 되지 않을 수 있다. 따라서 (1, 3), (2, 2), (3, 4)를 예시로 Lagrange interpolation를 이해해보자.
(1, 3)을 얻고 싶은 좌표로 정하고 나머지를 좌표로 기저 다항식을 만든다. 그렇다면 **(1, 3), (2, 0), (3, 0)**로 점을 설정하고, 아래와 같이 식을 만들 수 있다. * $$(x-2)(x-3)$$ * $$(x-2)(x-3) \* (3) /(1-2)(1-3)$$ * $$1.5 \* x^2 - 7.5 \* x + 9$$ 구한 다항식에 대한 그래프는 다음과 같이 나온다. ```python from sage.all import * x = var('x') P = [시각화 할 다항식] graph = plot(P, xmin=-1, xmax=5, ymin=-5, ymax=7, plot_points=200, legend_label='1.5* x **2 - 5.5 * x + 7') graph.save('polynomial_plot.png') ```
\ \ 나머지 두 점에 대해 반복하면 총 다항식들은 다음과 같다. * $$1.5 \* x^2 - 7.5 \* x + 9$$ * $$2\*x^2 + 8x- 6$$ * $$2\*x^2- 6x + 4$$ 세 다항식을 모두 더 하면 최종적으로 $$1.5\* x^2 - 5.5 \* x + 7$$이 나오게 된다. 구한 다항식은 세 점을 모두 지나는 것을 확인할 수 있다.
라그랑주 보간법에서 각 점이 n개 존재할 때 한 개의 기저 다항식을 구할 때 n-1개의 1차 다항식을 곱하기 때문에 $$O(n^2)$$ 만큼의 시간 복잡도가 걸리며, 총 n개의 점이 존재하기 때문에 전체 시간 복잡도는 $$n \* O(n^2)$$를 만족한다. 즉, 라그랑주 보간법은 $$O(n^3)$$의 시간 복잡도를 갖는다.(Fourier transform algorithms을 사용할 경우 더 단축할 수 있다.)
우리가 위에 구한 R1CS에 대해 라그랑주 보간법을 사용하는 방법은 다음과 같다. 아래와 같이 우리가 R1CS를 통해 정리한 식에서 행과 열은 각각 다음과 같은 의미를 지닌다. * **행 (Row) : 좌표 할당** R1CS 행렬(A, B, C)의 **각 행**은 하나의 게이트(제약)를 나타내며, 순서대로 x=1, x=2, x=3,…, x=m과 같은 **고유한 x좌표**를 할당한다. * **열 (Column) : 다항식 생성** 각 행렬(A, B, C)의 **각 열**은 하나의 **다항식**($$A\_i(x), B\_i(x), C\_i(x)$$)을 생성한다. 각 열을 대상으로 라그랑주 보간법을 적용하여 다항식을 정의한다.
사진에서 A의 첫번째 열을 예시로 들면 해당 다항식은 (1,0), (2,0), (3,0), (4,5)를 지난다. 이걸 바탕으로 3차 다항식을 생성하면 $$0.833x^3 -5x^2+9.166x -5$$라는 다항식을 얻을 수 있다. 이를 A,B,C의 각 열에 대해서 진행한다.
결과는 다음과 같으며, 상수부터 오름차순 정렬되어 값들만 적혀 있다. ```python A polynomials [-5.0, 9.166, -5.0, 0.833] [8.0, -11.333, 5.0, -0.666] [0.0, 0.0, 0.0, 0.0] [-6.0, 9.5, -4.0, 0.5] [4.0, -7.0, 3.5, -0.5] [-1.0, 1.833, -1.0, 0.166] B polynomials [3.0, -5.166, 2.5, -0.333] [-2.0, 5.166, -2.5, 0.333] [0.0, 0.0, 0.0, 0.0] [0.0, 0.0, 0.0, 0.0] [0.0, 0.0, 0.0, 0.0] [0.0, 0.0, 0.0, 0.0] C polynomials [0.0, 0.0, 0.0, 0.0] [0.0, 0.0, 0.0, 0.0] [-1.0, 1.833, -1.0, 0.166] [4.0, -4.333, 1.5, -0.166] [-6.0, 9.5, -4.0, 0.5] [4.0, -7.0, 3.5, -0.5] ``` 벡터의 다항식으로 첫 번째 제약 조건(x=1에서의 제약조건)을 도출해보면 다음과 같다. * $$0.833 \* x^3 - 5 \* x ^2 + 9.166 \* x - 5$$ * 0.833 - 5 + 9.166 - 5 = 0 * $$0.666 \* x^3 + 5 \* x ^2 - 11.333 \* x + 8$$ * 0.666 + 5 - 11.333 + 8 = 1 * $$0.5 \* x^3 - 4 \* x ^2 + 9.5 \* x - 6$$ * 0.5 -4 + 9.5 - 6 = 0 * $$0.5 \* x^3 + 3.5 \* x ^2 - 7 \* x + 4$$ * 0.5 + 3.5 -7 + 4 = 0 * $$0.166 \* x^3 - x ^2 + 1.833 \* x - 1$$ * 0.166 - 1 + 1.833 - 1 = 0 결과적으로 01000이 나오므로 벡터 a의 첫 번째 제약조건과 맞아떨어짐을 확인할 수 있다.
이제 다항식이 적절하게 도출되었으므로 A, B, C를 s(솔루션 벡터)와 내적을 통해 검증다항식(T(x))를 생성할 수 있다. (여기서 솔루션 벡터는 해당 제약조건을 만족하는 임의의 값)
A, B, C를 솔루션 벡터와 내적한 A.s, B.s, C.s는 다음과 같다. (여기서 솔루션 벡터는`s = [1, 3, 35, 9, 27, 30]`) ```python A . s = [43.0, -73.333, 38.5, -5.166] B . s = [-3.0, 10.333, -5.0, 0.666] C . s = [-41.0, 71.666, -24.5, 2.833] ``` \ A . s \* B . s — C . s 결과는 다음과 같다. ```python t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444] ``` \ 다항식 t는 특정 제약 조건의 x 값에 대해 0을 만족하면 된다. 때문에 다른 점들에서는 0이 아닌 다른 값을 가질 수 있다.
위 전제를 기반으로 제약 조건의 x 값에 대해 항상 0을 갖는 다항식 Z를 정의하고, 이를 t와 나누었을 때 나머지가 0이면 다항식 t는 제약 조건의 x 값에 대해 항상 0임을 증명할 수 있다. 즉, Z을 증명할 수 있다. 해당 논리 게이트에 존재하는 하는 x 좌표들 중 y가 0인 다항식 Z는 $$(x - 1) \* (x - 2) \* (x - 3) \* (x - 4)$$과 같다. ```python Z = [24, -50, 35, -10, 1] ``` \ 이제 t를 Z로 나누면 딱 떨이지게 되어 다음과 같은 다항식이 나오며 t는 Z의 배수임을 알 수 있다. ```python h = t / Z = [-3.666, 17.055, -3.444] ``` \ 즉, witness s를 사용하여 구성된 다항식 A(x)B(x) - C(x)가, **모든 제약 조건의 좌표**를 근(root)으로 가지는 다항식 Z(x)로 **나누어 떨어진다면,** 해당 witness s는 **모든 계산 제약 조건을 만족시킨다는 것**을 증명한다. QAP를 통해 하나의 식을 통해 하나의 식으로 모든 제약 조건을 확인할 수 있게 되는 것이다.
4. **Pinocchio 프로토콜** 무작위 점 $$s(\tau)$$에서 다항식의 평가값을 비교하면 두 다항식의 동일함을 높은 확률로 확인할 수 있다는 **Schwartz-Zippel 보조정리**를 활용한다. 이를 통해 거대한 다항식 전체를 보내는 대신, 특정 점에서의 계산 값만 검증함으로써 증명 크기를 상수(constant) 크기로 줄이고 검증 연산을 효율화한다.
그러나 Pinocchio는 zk-SNARK(비대화형)이므로 검증자가 실시간으로 무작위 값을 줄 수 없다. 대신 사전에 **신뢰 설정(Trusted Setup)** 과정을 통해 비밀 값($$\tau, \alpha$$등)을 생성하고, 이를 타원곡선 상의 점으로 암호화하여 **CRS(Common Reference String)** 형태로 공개한다.
**동일한 Witness 사용 증명 (Variable Consistency Check)** \ Prover가 $$A(x), B(x), C(x)$$를 생성할 때 서로 다른 witness를 섞어 쓰지 않고, 동일한 witness 벡터 s를 사용했음을 증명해야 한다. 이를 위해 Pinocchio는 선형 결합 검증(Linear Combination Check)과 Shifted Polynomial 기법을 사용한다. 1. **Setup:** CRS에는 기본 다항식 값들뿐만 아니라, 비밀 값 $$\alpha$$가 곱해진 **Shifted 요소**( $$g^{\alpha x^i}$$등)들이 포함된다. 2. **Proving:** 증명자는 다항식의 결과값 $$g^{P(\tau)}$$뿐만 아니라, 해당 witness들에 $$\alpha$$가 적용된 $$g^{\alpha P(\tau)}$$값도 함께 계산하여 제출한다. 3. Verifying (Pairing): 검증자는 쌍선형 페어링(Bilinear Pairing) 함수 $$e$$를 사용하여 아래와 같은 등식이 성립하는지 확인한다. $$ e(Proof, g^\alpha) = e(Proof\_{shifted}, g) $$ 이 등식이 성립하면, 증명자가 위조 없이 동일한 witness 계수를 사용하여 다항식을 생성했음이 수학적으로 증명된다. 즉, 상호작용 없이도 **Pairing**을 통해 $$A(x) \cdot B(x) - C(x) = H(x) \cdot Z(x)$$의 성립 여부(QAP)와 Witness의 일관성을 동시에 검증할 수 있게 된다. #### **Groth16으로의 확장** Pinocchio는 증명 구조가 8개의 그룹 원소로 되어 있고, Prover가 A,B,C 다항식에 **동일한 witness를 사용했는지**를 검증하기 위해 복잡한 과정을 거친다. Verifier는 무작위 값을 제공하고, Prover는 이 값을 기반으로 F라는 다항식에 대한 계산을 수행하여 일관성을 증명했다. Groth16은 이러한 Pinocchio의 문제를 아래와 같은 방법으로 발전시켰다. * Groth16은 Pinocchio의 증명 구조를 **3개의 그룹 원소**로 압축. * $$A', B', C'$$ 3개만으로 pairing 검증 가능. * $$π\_K$$와 여러 보정항을 $$π\_C$$ 내부로 통합. * 증명 크기와 검증 속도를 대폭 개선. ### Reference 1. [Quadratic Arithmetic Programs: from Zero to Hero](https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649) 2. [영지식 증명: Linear PCP (QAP, R1CS, 피노키오, Groth16)](https://www.youtube.com/watch?v=qNQEolaQHLg) 3. [Groth16: \[On the Size of Pairing-based Non-interactive Arguments\]](https://eprint.iacr.org/2016/260.pdf) 4. 5. --- # 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-1/groth16/the-pinocchio-protocol.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.