[ZK Study 02] Groth16

omin·2025년 8월 12일
Cryptographygroth16zk-SANRK블록체인암호학영지식증명

ZK Study

목록 보기
2/6

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

Groth16은 zk-SNARK(영지식 간결 비대화형 지식 증명)의 한 종류로, 영지식 증명 시스템 중 가장 널리 사용되고 효율적인 프로토콜 중 하나이다. Groth16은 복잡한 계산의 유효성 증명을 하나의 다항식 방정식 문제로 변환한 후, 페어링(pairing) 연산을 사용하여 이 방정식의 해가 존재함을 간결하게 증명하는 방식으로 작동한다. (피노키오 프로토콜과 마찬가지로 A*B-C=HT를 증명하려고 하는데, 이때 사용하는 그룹을 3개로 줄여서 간결하게 작동한다.)

Groth16의 전체적인 과정은, 주어진 계산을 게이트 단위로 분해(Flattening) 하고, 이를 Rank-1 Constraint System(R1CS) 형태로 변환한 뒤, QAP을 이용해 모든 제약을

A(x)⋅B(x)−C(x)=H(x)⋅Z(x)A(x) \cdot B(x) - C(x) = H(x) \cdot Z(x)

형태의 하나의 다항식 식으로 묶는다. 이후 페어링 기반 연산을 통해 이 식이 특정 점에서 성립함을 효율적으로 증명하고 검증한다.

Groth16의 알고리즘

Groth16도 NIZK 중 하나이므로 위에서 설명했던 4가지 알고리즘으로 구성된다.(Simulation의 경우에는 NIZK의 영지식을 증명하기 위한 이론적인 도구이므로 따로 설명하지 않는다.)

신뢰 설정(Trusted Setup)

증명자(Prover)가 증명에 필요한 요소들을 지수에서의 선형성만으로 구성하고, 검증자(Verifier)는 하나의 페어링 연산으로 검증할 수 있도록 공통된 기준점을 제공한다. 이를 위해 아무도 모르는 비밀 값(α,β,γ,δ,x)을 무작위로 선택한다. 이 비밀 값들이 '독성 폐기물(toxic waste)'이며, 이 값을 아는 사람은 위조 증명을 만들 수 있다. 따라서 이 값들은 즉시 파기되어야 한다.

CRS 구성:

  • G1 그룹 원소:
    • [xix_i]1 (다항식의 평가점)
    • [γβui(x)+αvi(x)+wi(x)]1[γβu_i(x)+αv_i(x)+w_i(x)]_1 (공개 입력)
    • [δβui(x)+αvi(x)+wi(x)]1[δβu_i(x)+αv_i(x)+w_i(x)]_1 (증인(witness) 등)
    • [t(x)xj]1[t(x)x_j]_1 (t(x) 다항식)
  • G2 그룹 원소:
    • [xi]2[x_i]_2
    • [β]2,[γ]2,[δ]2[β]_2,[γ]_2,[δ]_2

Proof 구성

π=([A]1,[C]1,[B]2)π=([A]_1,[C]_1,[B]_2)

Groth16 증명 시스템에서 A,B,C는 Prover가 생성하는 최종 증명의 핵심 구성 요소이다. 이들은 단순한 행렬이 아니라, 증명에 사용된 witness를 숨기면서도 그 증거의 유효성을 검증자에게 확신시켜주는 암호학적 객체들이다. 이 객체들을 만드는 데에는 α, β, r, s와 같은 특별한 값들이 중요한 역할을 한다. 각각의 요소들의 역할에 대해 알아보자.

[A]1=[α+∑aiui(x)+rδ]1[A]_1=[α+∑a_iu_i(x)+rδ]_1
[B]2=[β+∑aivi(x)+sδ]2[B]_2=[β+∑a_iv_i(x)+sδ]_2
[C]1=[∑i=l+1mai(βui(x)+αvi(x)+wi(x))+h(x)t(x)δ+As+rB−rsδ]1[C]_1 = \left[ \frac{\sum_{i=l+1}^{m} a_i(\beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x)t(x)}{\delta} + As + rB - rs\delta \right]_1

A,B,C의 역할: 여기서 말하는 A,B,C는 증명자가 생성하는 최종 증명(Proof)의 세 가지 핵심 원소이다. 이들은 계산 문제를 다항식 문제로 변환하는 QAP(Quadratic Arithmetic Program)의 결과물인 A(x),B(x),C(x) 다항식과 깊이 연관되어 있다. Prover는 자신만 알고 있는 값(aia_i)와 공통 참조 문자열(CRS)에 담긴 값들을 이용해 이 세 개의 원소를 계산한다. 결국, 이 A,B,C는 '내가 이 계산을 올바르게 수행했다'는 것을 검증자에게 보여주는 압축된 증거가 된다.

α\alpha, β\beta의 역할: α와 β는 마치 '암호학적 서명'과 같은 역할을 한다. 이 값들은 CRS를 생성할 때 만들어져 공개되는데, 검증자는 A와 B가 동일한 witness를 사용해 일관성 있게 만들어졌는지를 확인하는 데 αβ라는 특별한 항을 사용한다. 만약 Prover가 다른 witness를 사용해 A와 B를 만들려고 시도하면, 이 αβ 항이 검증 방정식에서 불일치를 일으키면서 검증이 실패한다.

어떻게 일관성을 강제하나?
검증자는 다음 형태의 pairing 검증식을 사용한다:
여기서 e([α]1,[β]2)e([\alpha]_1, [\beta]_2)는 α와 β가 동시에 들어가야만 만족하는 고유한 항이다.
A와 B가 동일한 witness로부터 만들어졌을 때만 이 pairing 식이 성립한다.
왜냐하면 A와 B의 상수항에 각각 α, β를 포함시키고, αβ 항이 곱으로 pairing에 등장하도록 함으로써, 둘 다 동일한 witness 기반 구조여야 αβ 조합이 QAP 나머지 항과 정확히 맞아떨어지게 한다. 만약 다른 witness 집합을 사용하면 αβ 항이 QAP 잔차와 맞지 않아 검증이 실패하도록 한다.

r,s 의 역할: r과 s는 증명에 '무작위성'을 불어넣는 값이다. Prover는 증명을 생성할 때마다 새로운 r과 s를 무작위로 선택하여 사용한다. 따라서 동일한 비밀 증거를 사용하더라도 매번 다른 형태의 증명(A,B,C 원소들의 값이 달라짐)이 생성될 수 있다. 이는 제3자가 증명 자체만으로 어떤 증거가 사용되었는지 추론할 수 없도록 만들어 영지식성(Zero-knowledge)을 보장한다.

Proof 최종 정리

  1. πA∈G1π_A∈G_1: u(x)의 커밋
  • A=α+∑i=0maiui(x)+rδA=α+∑_{i=0}^ma_iu_i(x)+rδ
    • u(x)u(x) 다항식을 CRS의 선형 결합으로 지수에서 구성
    • [α]1[α]_1는 검증식 상수항
    • r[δ]1r[δ]_1는 영지식성(zero-knowledge)을 위한 블라인딩(blinding) 항, 같은 입력에 대해서도 매번 다른 증명을 생성하게 한다.
  1. πB∈G2π_B∈G_2: v(x)의 커밋
  • B=β+∑i=0maivi(x)+sδB=β+∑_{i=0}^ma_iv_i(x)+sδ
    • v(x) 다항식을 구성
    • 검증식 e([A]1,[B]2)e([A]_1, [B]_2)에서 u(x)v(x) 항을 만들기 위해 πA와 짝을 이루도록 G2 그룹에 위치.
    • [β]2는 [α]1과 함께 상수항을 형성
    • s[δ]2는 영지식성을 위한 또 다른 블라인딩 항
  1. πC∈G1π_C∈G_1: 제약 만족 + 블라인딩 상쇄

  • C1=[∑i=l+1mai(βui(x)+αvi(x)+wi(x))+h(x)t(x)δ+As+rB−rsδ]1C_1 = \left[ \frac{\sum_{i=l+1}^{m} a_i(\beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x)t(x)}{\delta} + As + rB - rs\delta \right]_1

    • h(x)t(x)δ\frac{h(x)t(x)}{\delta}: 핵심 제약식인 u(x)v(x)−y(x)=h(x)t(x)u(x)v(x) - y(x) = h(x)t(x)가 정확히 성립함을 인코딩
    • ∑i>ℓaiβui(x)+αvi(x)+wi(x)δ\sum_{i>\ell} a_i \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta}: 증인(witness)에 해당하는 와이어 값 aia_{i}가 u,v,w 다항식에 일관되게 사용되었음을 강제
    • As+rB−rsδAs+rB−rsδ: πA와 πB에 들어간 블라인딩 항 r,s가 검증식에서 정확하게 상쇄되도록 보정하는 역할

Verification

Groth16에서 verification의 핵심은 QAP 다항식 등식이 성립하는지를 확인하는 것이다. 이 등식은 다음과 같다.

A(x)⋅B(x)−C(x)=H(x)⋅T(x)A(x)⋅B(x)−C(x)=H(x)⋅T(x)

이 등식이 모든 게이트(제약 조건)에서 성립한다면, Prover가 올바른 witness를 사용했다는 것을 증명할 수 있다. 하지만 이 등식을 그대로 검증하기에는 너무 복잡하다. 따라서 Groth16은 이 등식을 페어링을 이용해 간단하게 만든다.

Verifier는 페어링의 성질 e(ga,gb)=e(g,g)abe(g^a, g^b) = e(g, g)^{ab}를 이용해 등식을 다음과 같이 변환한다.

e([A(x)]1,[B(x)]2)⋅e([C(x)]1,[1]2)−1=e([H(x)]1,[T(x)]2)e([A(x)]_1,[B(x)]_2)⋅e([C(x)]_1,[1]_2)^{−1}=e([H(x)]_1,[T(x)]_2)

이 복잡한 식에 α,β,γ,δ 같은 값들을 이용해 정리하고 압축한다. 페어링의 특성을 활용해 A,B,C 원소들이 witness와 public inputs에 대한 올바른 조합으로 만들어졌는지를 한 번에 검증할 수 있도록 설계된 것이다. 이 과정은 다음과 같은 최종적인 검증식으로 귀결되고, 아래의 식이 성립하면 증명을 통과한다.

e(A,B)=e(α,β)⋅e(∑i=1lPi,γ)⋅e(C,δ)e(A,B)=e(\alpha,\beta) \cdot e(\sum_{i=1}^{l}P_i,\gamma) \cdot e(C,\delta)

이 식에서는 총 4개의 페어링 연산이 사용된다.

  1. e(A,B)e(A,B): 증명 원소 A와 B에 대한 페어링
  2. e(α,β)e(α,β): CRS의 α와 β에 대한 페어링
  3. e(∑li=1Pi,γ)e(∑^{i=1}_lPi,γ): 공개 입력과 γ에 대한 페어링
  4. e(C,δ)e(C,δ): 증명 원소 C와 δ에 대한 페어링

수식의 우변에 있는 세 개의 페어링 연산 결과들은 일반 곱셈 연산으로 결합되어 최종적으로 좌변의 결과와 비교된다.

페어링과 선형 방정식
페어링 연산은 다음과 같은 성질을 가진다.
e(ga,hb)=e(g,h)abe(g^a,h^b)=e(g,h)^{ab}
이 성질 덕분에, 페어링은 그룹에서의 지수 연산(덧셈)을 타겟 그룹에서의 곱셈으로 바꿀 수 있다. 이러한 성질을 활용해서 곱셈 형태의 연산을 덧셈 형태로 변환하여 복잡한 검증을 단순화할 수 있다.

상세과정

1. 좌변

A=α+u(x)+rδA=α+u(x)+rδ
B=β+v(x)+sδB=β+v(x)+sδ

따라서 pairing e([A]1,[B]2)e([A]_1,[B]_2) 에는 다음 항들이 포함된다.

  • 핵심 상수항: e([α]₁, [β]₂)

  • QAP 핵심항: e([u(x)]₁, [v(x)]₂)

  • 블라인딩 교차항: e([rδ]1,[sδ]2)e([r\delta]_1, [s\delta]_2), e([A]₁,[sδ]2)e([A]₁,[s\delta]_2), e([rδ]1,[B]₂)e([r\delta]_1,[B]₂) 등 블라인딩 항과 QAP 항의 교차항

2. 우변

1) 핵심 상수항: e([α]₁, [β]₂)
프로토콜의 규칙을 정의하는 고정된 값. 신뢰 설정(Trusted Setup)에서 미리 계산되어 검증 키(Verification Key)에 포함된다. 이는 증명자가 임의로 조작할 수 없는 구조적 앵커 역할을 한다.

2) 공개 입력 부분: e(Q_pub, [γ]₂)
공개 입력(aia_i)이 올바른지 확인하는 부분. Verifier는 공개된 입력 값들(a0​,…,al​a_0​,…,a_l​)과 CRS의 일부인 γγ관련 항들을 결합하여 QpubQ_{pub}을 직접 계산한다. 이후 [γ]2[ \gamma ]_2와 페어링하여, 공개 입력이 증명과 일치하는지를 확인한다.

3) 제약 조건 및 블라인딩 상쇄 부분: e([C]₁, [δ]₂)
증명([C]₁)과 검증 키([δ]₂)의 페어링을 통해, QAP의 제약 조건을 검증하고 좌변의 블라인딩 교차항을 제거한다. [C]₁ 안에는 다음 세 가지가 포함되어 있다.

① QAP 나머지 항 복구: h(x)t(x)δ\frac{h(x)t(x)}{\delta}항이 [δ]2[\delta]_2와 만나 페어링 되면서 QAP의 핵심 조건인 h(x)t(x)h(x)t(x)가 복구된다.

② 증인(witness) 부분 검증: 증명자가 사용한 비밀 증인 값들이 일관성 있게 사용되었는지 확인하는 항이 포함되어 있다.

③ 블라인딩 상쇄 항: As+rB−rsδAs + rB - rsδ 항이 좌변에서 발생했던 모든 블라인딩 교차항과 정확히 반대 부호를 가지고 있어서, 최종적으로 모든 블라인딩 관련 항들이 완벽하게 상쇄된다.

3. 최종 결과

최종적으로 남는 것은:

  1. e([α]1,[β]2)e([\alpha]_1, [\beta]_2)상수항
  2. 공개 입력 블록
  3. h(x)t(x)h(x)t(x)를 통해 보장되는 u(x)v(x)−y(x)=h(x)t(x)u(x)v(x)−y(x)=h(x)t(x) 성립 조건

결론 : πC\pi_C의 +As+rB−rsδ+As+rB−rsδ 항은 단순한 꾸밈이 아니라, πA,πB\pi_A, \pi_B의 블라인딩으로 인해 좌변에 생기는 잔여항을 우변에서 정확히 상쇄시키기 위한 필수 구성 요소이다.

Groth16을 이용한 Prover/Verify 과정

Prover

  1. 입력: 공개 a1,…,aℓa1,…,aℓ, 증인 aℓ+1,…,amaℓ+1,…,am

  2. 무작위 r,s←Zpr,s←Z_p 선택.

  3. CRS 선형결합으로 u(x)=∑iaiui(x),v(x)=∑iaivi(x),y(x)=∑iaiwi(x)u(x)=∑_ia_iu_i(x), v(x)=∑_ia_iv_i(x), y(x)=∑_ia_iw_i(x) 를 지수에서 조립.

  4. A=α+u(x)+rδ,B=β+v(x)+sδA=α+u(x)+rδ,B=β+v(x)+sδ 계산.

  5. h(X)=(uv−y)/th(X)=(uv−y)/t 계산 → δh(x)t(x)δh(x)t(x) 조립.

  6. ∑i>ℓaiδβui(x)+αvi(x)+wi(x)∑_{i>ℓ}a_iδβu_i(x)+αv_i(x)+w_i(x) 조립.

  7. C=(5,6 결과)+As+rB−rsδAs+rB−rsδ

  8. 증명 출력:

    π=([A]1,[C]1,[B]2)π=([A]_1, [C]_1, [B]_2)

Verifier

  1. 공개 입력으로 Qpub:=∑i=0ℓai[γβui(x)+αvi(x)+wi(x)]1Q_{pub} := ∑_{i=0}^ℓa_i[γβu_i(x)+αv_i(x)+w_i(x)]_1 을 G1G_1에서 조립.

  2. 세 pairing 계산

    t1=e([A]1,[B]2),t2=e(Qpub,[γ]2),t3=e([C]1,[δ]2)t_1=e([A]_1,[B]_2),t_2=e(Q_{pub},[γ]_2),t_3=e([C]_1,[δ]_2).

  3. 사전저장 상수 t0=e([α]1,[β]2)t_0=e([α]_1,[β]_2)와 비교

  4. 검사 t1=?t0⋅t2⋅t3.t_1 =? t_0⋅t_2⋅t_3.

Reference

  1. Quadratic Arithmetic Programs: from Zero to Hero
  2. 영지식 증명: Linear PCP (QAP, R1CS, 피노키오, Groth16)
  3. Groth16: On the Size of Pairing-based Non-interactive Arguments
profile
omin
이전 포스트

[ZK Study 01] Pinocchio Protocol

다음 포스트

[ZK Study 03] KZG Commitment

0개의 댓글