[ZK Study 01] Pinocchio Protocol

omin·2025년 8월 12일

Cryptography Pinocchio Protocol zk-SNARK 블록체인 암호학 영지식증명

ZK Study

목록 보기

1/6

Web3의 핵심 철학은 탈중앙화와 투명성이다. 이 철학 덕분에 모든 거래 기록이 블록체인에 공개되어 누구나 확인할 수 있게 된다. 하지만 이 투명성은 때때로 개인에게는 양날의 검이 될 수 있다. 모든 자산 정보와 거래 내역이 공개된다는 점은 사생활 침해에 대한 우려를 낳기 때문이다.

사실, 우리가 현재 사용하고 있는 대부분의 중앙화된 온라인 서비스에서도 비슷한 문제가 발생한다. 특정 서비스를 이용하기 위해 주민등록번호, 주소, 전화번호와 같은 민감한 개인 정보를 직접 입력해야 한다. 이는 서비스 제공자에게 우리가 '정당한 사용자'임을 증명하는 가장 손쉬운 방법이지만, 이 과정에서 우리의 데이터는 위험에 노출된다.

이러한 문제점을 해결하기 위해 등장한 개념이 바로 영지식 증명(Zero-Knowledge Proof, ZK Proof)이다. 영지식 증명은 내가 어떤 정보를 알고 있다는 사실을 직접적으로 보여주지 않고도, 그 정보가 맞다는 것을 상대방에게 증명하는 암호학적 기술이다.

해당 아티클은 J. Groth, "On the Size of Pairing-based Non-interactive Arguments."를 읽고 정리한 내용이다

영지식 증명

영지식 증명은 다음 세 가지 핵심 속성을 가진다.

완전성(Completeness): 명제와 증거(witness)가 주어졌을 때, 정직한 증명자는 검증자를 설득할 수 있다.
건전성(Soundness): 악의적인 증명자는 거짓 명제에 대해 검증자를 설득할 수 없다.
영지식성(Zero-knowledge): 증명은 명제가 참이라는 사실 외에 어떤 것도 드러내지 않는다. 특히, 증명자가 사용한 증거를 노출하지 않는다.

영지식 증명은 증명 절차에 따라 크게 두가지로 나뉜다. 첫째는 증명자와 검증자가 상호작용하는 대화형 영지식 증명(IZK, Interactive Zero-Knowledge), 둘째는 상호작용이 없이 검증을 하는 비대화형 영지식 증명(NIZK, Non-Interactive Zero-Knowledge)이다.

IZK(대화형 영지식증명)

기존의 대화형 영지식 증명(IZK)은 증명자와 검증자가 여러 차례 질의응답을 주고받으며 증거에 대한 지식을 증명하는 방식으로 이루어졌다. 이는 다음과 같은 기본적인 단계를 따랐다.(뭔가 Digital Signature에서 identification의 과정과 유사)

1. 첫 번째 메시지 (Commitment)

Prover는 자신이 알고 있는 witness를 바탕으로 어떤 메시지를 생성한다. 이 메시지는 증명자가 추후에 자신의 주장을 변경하지 못하도록 하는 '약속' 또는 '커밋먼트' 역할을 한다. 그리고 prover는 이 메시지를 verifier에게 보낸다.

2. 무작위 질문 (Challenge)

Verifier는 첫 번째 메시지를 받은 후, prover에게 witness와 관련된 무작위 질문(challenge)을 던진다.

3. 답변 (Response)

Prover는 verifier의 질문에 대해 자신의 witness를 사용하여 답변(response)을 생성한다.

4. 반복 및 확신

Verifier는 prover의 답변을 확인하고, 여러 번에 걸쳐 이 질의응답 과정을 반복했다. 이 과정을 충분히 반복하면, verifier는 prover가 우연히 정답을 맞혔을 가능성이 무시할 수 있을 만큼 낮아졌다고 확신하게 된다. 이 과정을 통해 verifier는 prover가 실제로 witness를 알고 있었다고 결론 내리지만, verifier가 얻는 정보는 '정답'뿐이며, witness 그 자체는 알 수 없다.

NIZK (비대화형 영지식 증명)

NIZK(Non-interactive Zero-knowledge, 비대화형 영지식 증명)는 증명자가 검증자에게 어떤 명제가 참임을 설득할 수 있게 해주는 암호학적 기법이다. NIZK는 공통 참조 문자열(common reference string, CRS) 모델에서 영지식 증명(zero-knowledge proof) 개념을 확장한 것이다.

NIZK 프로토콜의 구성 요소

NIZK 프로토콜은 네 가지 확률적 다항식 시간 알고리즘으로 구성된다.

Setup(셋업): Trusted setup을 통해 τ를 생성하고, τ를 이용해 σ(CRS)와 Proving Key, Verification Key를 생성한다.
- 신뢰할 수 있는 셋업 절차는 무작위 비밀 값들을(τ) 사용하여 증명과 검증에 필요한 공통 참조 문자열(σ)을 생성한다.
- Proving Key와 Verification Key는 모두 이 공개된 σ의 일부입니다. Proving Key는 증명자가, Verification Key는 검증자가 사용한다.
- τ는 σ를 만드는 데 사용된 비밀 값들의 집합이며, 시뮬레이션 함정문(simulation trapdoor)으로 사용됩니다. σ를 만든 이후, τ는 폐기되어야 한다.
  - 만약 이 비밀값들이 안전하게 파기되지 않고 누군가에게 유출된다면 그 사람은 시스템의 암호학적 제약을 우회하여 거짓 증명(fake proof)을 생성할 수 있다. 이 때문에 CRS를 생성하는 과정은 반드시 신뢰할 수 있어야 하며 생성 후에는 해당 파라미터를 반드시 제거해야한다.
CRS란?
CRS(공통 참조 문자열, Common Reference String)는 NIZK(비대화형 영지식 증명)에서 검증자의 무작위 챌린지 역할을 대신 수행한다.
상호작용 증명에서는 검증자가 무작위 값을 전송하여 증명자를 시험하지만, NIZK에서는 CRS가 그 무작위성을 미리 준비해둠으로써 상호작용 없이 검증을 가능하게 한다.
CRS는 신뢰 설정(Trusted Setup)이라는 특별한 과정을 통해 생성된 다수의 군 원소(group element) 집합으로 표현한다.
이 과정에서 α,β,γ,δ,x와 같은 아무도 모르는 비밀값(“toxic waste”)을 무작위로 선택하고, CRS는 이 비밀값들을 암호화된 형태로 포함하도록 한다.
CRS의 핵심 목적은 증명과 검증 과정에서 동일한 고정된 참조값을 제공하여, 증명자가 임의로 검증 과정을 조작하지 못하게 하는 것이다.
이때, 신뢰 설정을 올바르게 수행하지 않으면, 해당 비밀값을 아는 자가 임의의 잘못된 증명을 만들어도 검증을 통과시키는 공격이 가능해지므로, 시스템 전체의 보안을 심각하게 해친다.
따라서 신뢰 설정은 시스템의 규칙이 담긴 ‘암호화된 약속’을 만드는 과정이며, 이 약속이 올바르게 만들어졌다는 전제하에만 zk-SNARK 시스템이 안전하게 동작하도록 한다.

Prove(증명): Prover는 Proving Key를 이용해 proof π(A, B, C)를 생성한다.
- Prover는 Proving Key를 포함하는 σ와 자신의 witness를 사용해서 증명(Proof)을 생성힌다.
- 이 증명은A, B, C와 같은 3개의 그룹 요소로 구성된다.
Vfy(검증): Verifier는 Verification Key, σ(CRS), proof(A, B, C)를 이용해 검증한다.
- Verifier는 Verification Key를 포함하는 σ, Proof, 그리고 공개된 입력(public inputs)만을 사용해서 증명이 유효한지 확인한다.
- Verifier는 witness를 모르고도 검증을 수행할 수 있다. Verifier는Vfy 알고리즘을 통해 Proof가 유효한지 확인하고 0(거절) 또는 1(수락)을 반환한다.
Sim(시뮬레이션): 시뮬레이터는 τ와 명제를 입력으로 받아 증명을 반환한다. 이 알고리즘은 실제 프로토콜의 일부가 아니라, NIZK의 영지식성을 증명하기 위한 이론적 도구이다.

NIZK의 핵심 원리

기존의 영지식 증명(ZK)은 증명자와 검증자가 여러 차례 질문과 응답을 주고받으며(interactive), 증명자가 증거를 알고 있음을 증명했다. 하지만 NIZK는 이 과정을 단 한 번의 메시지 전달로 줄인다.

신뢰할 수 있는 셋업 (Trusted Setup)의 역할:
- 이 과정에서 Proofing Key와 Verification Key를 포함하는 공통 참조 문자열(CRS)이 생성된다. 이 CRS는 증명자와 검증자 모두가 사용하는 공개된 매개변수 역할을 한다.
- CRS는 프로토콜의 '규칙'을 정의하고, 복잡한 검증 과정을 효율적으로 압축할 수 있게 해준다.
비대화형 증명:
- 증명자는 CRS와 자신의 witness를 사용하여 단 한 번의 계산으로 증명(π)을 생성한다.
- 검증자는 증명자가 보낸 증명(π)과 CRS를 사용하여 단 한 번의 검증을 수행한다.

이러한 방식은 상호작용이 필요한 프로토콜에서 발생할 수 있는 잠재적인 문제를 해결한다. 예를 들어, 인터넷 연결이 불안정하거나 증명자가 오프라인 상태일 때도 증명이 가능해지며, 블록체인과 같이 모두가 검증자 역할을 해야 하는 환경에 적합하다. 즉, NIZK는 셋업 단계에서 미리 합의된 규칙(CRS) 덕분에 증명자와 검증자가 실시간으로 소통하지 않아도 된다.

Pinocchio Protocol

Pinocchio Protocol은 zk-SNARK(영지식 간결 비대화형 지식 증명)의 선구적인 프로토콜 중 하나이다.

Pinocchio는 동형 암호(Homomorphic Hiding)와 KoE(Knowledge of Exponent)등의 암호학적 기술을 활용한다. 이를 통해 증명자는 자신이 알고 있는 witness를 공개하지 않고도, $A(x)⋅B(x)−C(x)=H(x)⋅T(x)$ 와 같은 다항식 방정식의 해를 알고 있음을 간결하게 증명한다.

진행 순서

평탄화 (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 최종 출력

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`	최종 출력

Gates to R1CS

R1CS (Rank-1 Constraint System) 부분은 모든 계산을 L * R = O (좌항 * 우항 = 출력) 형태의 제약으로 변환하는 것이 핵심이다. 회로에 사용되는 모든 변수를 하나의 벡터(s)로 매핑한다.

각 게이트를 A(좌항) * B(우항) = C(출력)의 형태로 만들고, 각각에서 A는 A끼리, B는 B끼리, C는 C끼리 모아 메트릭스를 구성한다.

2-1 벡터 생성

순서 규칙

항상 값이 1인 변수 one (상수항 처리를 위해 필요)
공개 입력 변수 (public inputs)
출력 변수 (예: ~out)
중간 변수 (평탄화에서 생성된 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-2 Gate → R1CS 제약 변환

각 게이트는 (s·a) * (s·b) = (s·c) 꼴로 표현된다. (여기서 a,b,c는 s 길이와 같은 계수벡터)

Gate별 a, b, c 및 검증

게이트	수식	a (L)	b (R)	c (O)
G1	`sym_1 = x * x`	`[0,1,0,0,0,0]`	`[0,1,0,0,0,0]`	`[0,0,0,1,0,0]`
G2	`y = sym_1 * x`	`[0,0,0,1,0,0]`	`[0,1,0,0,0,0]`	`[0,0,0,0,1,0]`
G3	`sym_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 + 51)1 = ~out`	`[5,0,0,0,0,1]`	`[1,0,0,0,0,0]`	`[0,0,1,0,0,0]`

R1CS to QAP

지금까지는 각 gate에 대한 검증을 $A(x) * B(x) - C(x) =0$ 을 통해서 검증한다. 그러나 암호학적으로 수많은 지점에서의 등식 만족 여부를 하나하나 검증하는 것은 비효율적이다. 따라서 groth16은 제약조건을 일일이 계산하지 않기 위해 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$

구한 다항식에 대한 그래프는 다음과 같이 나온다.

나머지 두 점에 대해 반복하면 총 다항식들은 다음과 같다.
1.5 $x^2$ - 7.5 $x$ + 9
2* $x^2$ + 8 $x$ - 6
2* $x^2$ - 6 $x$ + 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의 각 열에 대해서 진행한다.

결과는 다음과 같으며, 상수부터 오름차순 정렬되어 값들만 적혀 있다.
```
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]
```
A 벡터의 다항식으로 첫 번째 제약 조건(x=1에서의 제약조건)을 도출해보면 다음과 같다.

결과적으로 01000이 나오므로 벡터 a의 첫 번째 제약조건과 맞아떨이짐을 확인할 수 있다.

이제 다항식이 저절하게 도출되었으므로 A, B, C를 s(솔루션 벡터)와 내적을 통해 검증다항식(T(x))를 생성할 수 있다. (여기서 솔루션 벡터는 해당 제약조건을 만족하는 임의의 값)

A, B, C를 솔루션 벡터와 내적한 A.s, B.s, C.s는 다음과 같다. (여기서 솔루션 벡터는 s = [1, 3, 35, 9, 27, 30])
```
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 결과는 다음과 같다.
```
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)$ 과 같다.
```
Z = [24, -50, 35, -10, 1]
```
이제 t를 Z로 나누면 딱 떨이지게 되어 다음과 같은 다항식이 나오며 t는 Z의 배수임을 알 수 있다.
```
h = t / Z = [-3.666, 17.055, -3.444]
```
즉, witness s를 사용하여 구성된 다항식 A(x)B(x) - C(x)가, 모든 제약 조건의 좌표를 근(root)으로 가지는 다항식 Z(x)로 나누어 떨어진다면, 해당 witness s는 모든 계산 제약 조건을 만족시킨다는 것을 증명한다. QAP를 통해 하나의 식을 통해 하나의 식으로 모든 제약 조건을 확인할 수 있게 되는 것이다.

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의 문제를 아래와 같은 방법으로 발전시켰다.