CRS = (\sigma_G, \sigma_H)
* $$\begin{aligned} \sigma\_G &:= \left( \[\alpha]\_G, \[\beta]\_G, \[\delta]\_G, {\[x^i]G}{i=0}^{n-1}, \right. \ & \quad \left{ \left\[ \frac{\beta v\_i(x) + \alpha w\_i(x) + y\_i(x)}{\gamma} \right]G \right}{i=m-1}^{m}, \ & \quad \left{ \left\[ \frac{\beta v\_i(x) + \alpha w\_i(x) + y\_i(x)}{\delta} \right]G \right}{i=1}^{m-2}, \ & \quad \left. \left{ \left\[ \frac{x^i t(x)}{\delta} \right]G \right}{i=0}^{n-2} \right) \end{aligned}$$ * $$\sigma\_H := \left( \[\beta]\_H, \[\gamma]\_H, \[\delta]\_H, {\[x^i]H}{i=0}^{n-1} \right)$$ ### 증명(Proof)\pi = ([A]_1, [C]_1, [B]_2)
Groth16 증명 시스템에서 $$A, B, C$$는 Prover가 생성하는 최종 증명 $$\pi$$를 이루는 핵심 구성 요소이다. 이 값들은 단순한 숫자가 아니라, 증명에 사용된 witness를 직접 드러내지 않으면서도 해당 계산이 올바르게 수행되었음을 인코딩하는 **타원곡선 그룹 원소**들이다. 이러한 A, B, C를 만드는 과정에서는 신뢰 설정에서 선택된 비밀 파라미터 $$\alpha, \beta, \sigma, r, s$$ 등이 중요한 역할을 하며, 이 값들은 CRS/SRS 안에 암호학적으로 숨겨진 형태로 존재한다.[A]_1 = [\alpha + \sum a_iu_i(\chi) + r\delta]_1
[B]_2 = [\beta + \sum a_iv_i(\chi) + s\delta]_2
[C]1 = \left[ \frac{\sum{i=l+1}^{m} a_i(\beta u_i(\chi) + \alpha v_i(\chi) + w_i(\chi)) + h(\chi)t(\chi)}{\delta} + As + rB - rs\delta \right]_1
* **A, B, C의 역할**: A, B, C는 증명자가 생성하는 최종 증명의 **세 가지 핵심 그룹 원소**이다. 이 값들은 계산 **QAP에서 얻은 다항식** $$A(x), B(x), C(x)$$를 비밀 평가점 $$\chi$$에서 계산한 결과에 랜덤 값을 섞어서 만든 것이다. 이를 통해 Prover의 witness를 직접 드러내지 않으면서 "계산이 올바르게 수행했다."는 것을 검증자에게 보여주는 압축된 증거가 된다. * $$\alpha, \beta$$**의 역할**: $$\alpha, \beta$$는 Prover가 임의의 A, B를 조작하지 못하게 묶어주는 바인딩 파라미터 역할을 한다. 신뢰 설정에서 비밀 스칼라 $$\alpha, \beta$$를 선택하고, 이에 대응하는 그룹 원소 $$\[\alpha]\_1, \[\beta]\_1$$ 등이 CRS/SRS에 포함되지만, 스칼라 값 자체는 폐기된다. 검증자는 A와 B가 동일한 witness를 사용해 일관성 있게 확인하기 위해 $$\alpha \beta$$라는 특별한 항을 사용한다. * 최종 검증 식에서는 $$e(\[A]\_1, \[B]\_2) = e(\[\alpha]\_1, \[\beta]\_2) + ...$$ 와 같이 구성되어 있다. 여기서 $$e(\[\alpha]\_1, \[\beta]\_2)$$는 사실상 $$\alpha\beta$$가 들어가야만 만족하는 고유항이다. 따라서 Prover가 서로 다른 witness로부터 A와 B를 만들려 하면 이 $$\alpha\beta$$항이 맞지 않아 검증 방정식이 깨지고, 검증은 실패하게 된다. * $$r, s$$**의 역할**: $$r$$과 $$s$$는 증명에 **무작위성**을 불어넣는 값이다. Prover는 증명을 생성할 때마다 새로운 $$r$$과 $$s$$를 무작위로 선택하여 사용한다. 따라서 동일한 비밀 증거를 사용하더라도 매번 다른 형태의 증명이 생성될 수 있다. 이는 제 3자가 증명 자체만으로 어떤 증거가 사용되었는지 추론할 수 없도록 만들어 영지식성을 보장한다. **Proof 최종 정리** 1. $$\pi\_A \in G\_1: u\_i$$ 다항식들의 선형 결합에 대한 커밋 * $$\[A]1 = \[\alpha + \sum{i=0}^{m} a\_i u\_i(x) + r\delta]\_1$$ * 여기서 $$\sum\_{i=0}^{m} a\_i u\_i(x)$$는 QAP의 $$A(x)$$ 다항식을 비밀 평가점 $$\chi$$에서 계산한 값에 해당하며, Prover는 CRS에 있는 $$\[u\_i(x), \alpha, \delta]\_1$$들을 선형 결합해서 이 값을 커밋한다. * $$\[\alpha]\_1$$는 $$\[\beta]\_2$$와 함께 $$e(\[\alpha]\_1, \[\beta]\_2)$$ 항을 만들기 위한 상수 기준점 역할을 한다. * $$r\[\delta]\_1$$는 각 증명마다 새로 선택되는 블라인딩 항으로, 같은 witness에 대해서도 매번 다른 $$\[A]\_1$$이 나오도록 하여 영지식성을 보장한다. 2. $$\pi\_B \in G\_2: v\_i$$ 다항식들의 선형 결합에 대한 커밋 * $$\[B]2 = \[\beta + \sum{i=0}^{m} a\_i v\_i(x) + s\delta]\_2$$ * $$\sum\_{i=0}^{m} a\_i v\_i(x)$$는 QAP의 $$B(x)$$ 다항식을 비밀 평가점 $$\chi$$에서 계산한 값에 해당하며, Prover는 CRS에 있는 $$\[v\_i(x)]\_2, \[\beta]\_2, \[\delta]\_2$$를 선형 결합해서 $$\[B]\_2$$를 만든다. * $$\[A]\_1 \in G\_1$$와 $$\[B]\_2 \in G\_2$$는 페어링 $$e(\[A]\_1, \[B]\_2)$$에서 $$A(x)B(x)$$ 항이 나타나도록 짝을 이루는 구조이다. * $$\[\beta]\_2$$는 $$\[\alpha]\_1$$와 함께 $$e(\[\alpha]\_1, \[\beta]\_2)$$ 상수항을 형성해, $$A$$와 $$B$$가 같은 witness에 대해 일관되게 생성되었는지를 체크하는 기준점이 된다. * $$\[\beta]\_2$$는 $$\[\alpha]\_1$$과 함께 상수항을 결성 * $$\[\delta]\_1$$ 역시 각 증명마다 새로 선택되는 블라인딩 항으로, $$\[B]\_2$$에 무작위성을 부여하여 영지식성을 보장한다. 3. $$\pi\_C \in G\_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$$ * $$\frac{h(x)t(x)}{\delta}$$: 핵심 제약식인 $$u(x)v(x) - w(x) = h(x)t(x)$$가 성립함을 인코딩하는 부분이다. 제약이 만족되지 않으면 적절한 $$h(x)$$를 만들 수 없고, 이 항이 올바르게 구성될 수 없다. * $$\sum\_{i > l} a\_i \frac{\beta u\_i(x) + \alpha v\_i(x) + w\_i(x)}{\delta}$$: 공개 입력 인덱스 $$i\leq l$$ 를 제외한 witness 인덱스에 대해, 같은 와이어 값 $$a\_i$$가 $$u\_i, v\_i, w\_i$$ 다항식에 일관되게 사용되었음을 강제한다. 이 항의 각 조각은 이미 CRS에 포함되어 있어 Prover는 선형 결합만 할 수 있다. * $$As + rB - rs\delta$$: $$\[A]\_1$$과 $$\[B]\_2$$에 들어간 블라인딩 항 $$r, s$$로 인해 생기는 추가 항들이 최종 검증식에서 정확히 소거되도록 조정하는 부분이다. 이 조합 덕분에 증명은 여전히 무작위성을 포함하지만, 검증자가 보는 페어링 방정식에서는 $$r, s$$에 의존하는 항이 상쇄된다. ### Verification Groth16에서 Verification의 핵심은 **QAP로 표현된 다항식 등식이 성립하는지**를 확인하는 것이다. QAP 제약은 원래 다음과 같은 다항식 등식으로 나타난다.A(x)B(x) - C(x) = H(x)T(x)
이 등식이 모든 게이트(제약 조건)에서 성립한다면, Prover가 올바른 **witness**를 사용했다는 것을 증명할 수 있다. 하지만 이 등식을 그대로 검증하기에는 비효율적이기 때문에 Groth16은 이 등식을 페어링을 이용해 간단하게 만든다. Verifier는 페어링의 성질 $$e(g^a, g^b) = e(g, g)^{ab}$$를 이용하면, $$A(x)B(x) - C(x) = H(x)T(x)$$를 대략 다음과 같은 형태의 페어링 관계로 인코딩할 수 있다.e([A(x)]_1, [B(x)]_2) ⋅ e([C(x)]_1, [1]_2)^{-1} = e([H(x)]_1, [T(x)]_2)
이 복잡한 식에 $$\alpha, \beta, \gamma, \delta$$ 같은 값들을 이용해 정리하고 압축한다. 페어링의 특성을 활용해 $$A, B, C$$ 원소들이 witness와 public inputs에 대한 올바른 조합으로 만들어졌는지를 한 번에 검증할 수 있도록 설계된다. 이 과정은 다음과 같은 최종적인 검증식으로 귀결되고, 아래의 식이 성립하면 증명을 통과한다.e(A, B) = e(\alpha, \beta) \cdot e\left( \sum_{i=1}^{l} P_i, \gamma \right) \cdot e(C, \delta)
여기서 * $$A \in G\_1, B \in G\_2, C \in G\_1$$는 Prover가 제출한 **증명 원소**, * $$e(\alpha, \beta)$$는 실제로 $$e(\[\alpha]\_1, \[\beta]\_2)$$를 의미하며, * $${P\_i}$$는 **공개 입력을 반영**하도록 미리 CRS/검증키에 포함된 그룹 원소들, * $$\gamma, \delta$$ 역시 검증키에 포함된 $$\[\gamma]\_2, \[\delta]\_2$$에 대응하는 기호이다. 이 식에서는 **총 4번의 페어링 연산**이 사용된다. 1. $$e(A, B)$$: 증명 원소 $$A$$와 $$B$$에 대한 페어링 2. $$e(\alpha, \beta)$$: CRS이 $$\alpha$$와 $$\beta$$에 대한 페어링 3. $$e\left( \sum\_{i=1}^{l} P\_i, \gamma \right)$$: 공개 입력과 $$\gamma$$에 대한 페어링 4. $$e(C, \delta)$$: 증명 원소 $$C$$와 $$\delta$$에 대한 페어링 수식의 우변에 있는 세 개의 페어링 연산 결과들은 일반 곱셈 연산으로 결합되어 최종적으로 좌변의 결과와 비교된다. 이 최종 검증식이 성립하면, Verifier는 "비밀 평가점 $$\chi$$에서 QAP 등식이 성립하며, 따라서 Prover가 올바른 witness를 사용했다."고 받아들이게 된다. > **페어링과 선형 방정식** 페어링 연산은 다음과 같은 성질을 가진다. > > $$e(g^a, h^b) = e(g, h)^{ab}$$ 이 성질 덕분에, 페어링은 그룹에서의 지수 연산(덧셈)을 타겟 그룹에서의 곱셈으로 바꿀 수 있으며, **곱셈 형태의 연산을 덧셈 형태로 변환**하여 복잡한 검증을 단순화할 수 있다. #### 상세 과정 1. **좌변**A = \alpha + u(x) + r\delta
B = \beta + v(x) + s\delta
따라서 pairing $$e(\[A]\_1, \[B]\_2)$$에는 다음 항등이 포함된다. * 핵심 상수항: $$e(\[\alpha]\_1, \[\beta]\_2)$$ * QAP 핵심항: $$e(\[u(x)]\_1, \[v(x)]\_2)$$ * 블라인딩 교차항: $$e(\[r\delta]\_1, \[s\delta]\_2), e(\[A]\_1, \[s\delta]\_2), e(\[r\delta]\_1, \[B]\_2)$$ 등 블라인딩 항과 QAP 항의 교차항 2. **우변** 1\) **핵심 상수항:** $$e(\[\alpha]\_1, \[\beta]\_2)$$ 프로토콜의 규칙을 정의하는 고정 상수 값이다. 신뢰 설정(Trusted Setup)에서 미리 계산되어 검증 키(Verification Key)에 포함되며, 증명자가 임의로 조작할 수 없는 구조적 앵커 역할을 한다. 2\) **공개 입력 부분:** $$e(Q\_{pub}, \[\gamma]\_2)$$ 공개 입력 $$a\_i$$가 올바른지 확인하는 항이다. Verifier는 공개된 입력 값들 $$(a\_0, ..., a\_l)$$과 CRS에 포함된 $$\gamma$$관련 항들을 이용해 $$Q\_{pub}$$을 직접 계산한 뒤, 이를 $$\[\gamma]\_2$$와 페어링한다. 이 페어링 결과가 증명 안에 들어 있는 값과 일치하는지를 확인함으로써 공개 입력이 정확히 반영되었는지 검증한다. 3\) **제약 조건 및 블라인딩 상쇄 부분**: $$e(\[C]\_1, \[\delta]\_2)$$ 증명 $$\[C]\_1$$과 검증 키 $$\[\delta]\_2$$의 페어링을 통해 QAP의 제약 조건을 확인하고 동시에 좌변에 섞여 있던 블라인딩 교차항들을 제거한다. $$\[C]\_1$$ 안에는 아래 세 가지가 포함되어 있어야 한다. * QAP 나머지 항 복구: $$\frac{h(x)t(x)}\delta$$항이 $$\[\delta]\_2$$와 만나 페어링 되면서 QAP의 핵심 조건인 $$h(x)t(x)$$ 항이 제대로 복구된다. * 증인(witness) 부분 검증: 증명자가 사용한 비밀 증인 값들이 회로/제약식과 일관성 있게 사용되었는지 확인하는 항이 포함된다. * 블라인딩 상쇄 항: $$As + rB - rs\delta$$ 형태의 항이 좌변에서 발생했던 모든 블라인딩 교차항과 정확히 반대 부호를 가지도록 설계되어 있어, 최종적으로는 블라인딩 관련 항등이 완전히 상쇄 3. **최종 결과** 최종적으로 남는 것은 * $$e(\[\alpha]\_1, \[\beta]\_2)$$ 상수항 * 공개 입력 블록 * $$h(x)t(x)$$를 통해 보장되는 $$u(x)v(x) - w(x) = h(x)t(x)$$ 성립 조건 > 결론적으로 $$\[C]\_1$$의 $$As + rB + rs\delta$$ 항은 단순한 꾸밈이 아니라, $$\[A]\_1, \[B]\_2$$의 블라인딩으로 인해 좌변에 생기는 잔여항을 우변에서 정확히 상쇄시키기 위한 필수 구성 요소이다. ### Groth16 Prover/Verifier 전체 과정 #### Prover 1. 입력: 공개 $$a\_1, ..., a\_l$$, 증인 $$a\_l+1, ..., a\_m$$ 2. 무작위 $$r, s \leftarrow \mathbb{Z}\_p$$ 선택 3. CRS 선형결합으로 $$u(x) = \sum\_i a\_i u\_i(x), \quad v(x) = \sum\_i a\_i v\_i(x), \quad y(x) = \sum\_i a\_i w\_i(x)$$를 지수에서 조립 4. $$A = \alpha + u(x) + r\delta, \quad B = \beta + v(x) + s\delta$$ 계산 5. $$h(X) = (uv - y)/t$$ 계산 $$\to \delta h(x)t(x)$$ 조립 6. $$\sum\_{i > \ell} a\_i \delta \beta u\_i(x) + \alpha v\_i(x) + w\_i(x)$$ 조립 7. $$C=$$ (5, 6 결과) $$+ As + rB - rs\delta$$ 8. 증명: * $$\pi = \left( \[A]\_1, \[C]\_1, \[B]\_2 \right)$$ #### Verifier 1. 공개 입력으로 $$Q\_{pub} := \sum\_{i=0}^{\ell} a\_i \[\gamma \beta u\_i(x) + \alpha v\_i(x) + w\_i(x)]\_1$$을 $$G\_1$$에서 조립 2. 세 pairing 계산 $$t\_1 = e(\[A]\_1, \[B]2), \quad t\_2 = e(Q{pub}, \[\gamma]\_2), \quad t\_3 = e(\[C]\_1, \[\delta]\_2)$$ 3. 사전 정수 상수 $$t\_0 = e(\[\alpha]\_1, \[\beta\[\_2)$$와 비교 4. 검사 $$t\_1 \stackrel{?}{=} t\_0 \cdot t\_2 \cdot t\_3$$ ### 결론 Groth16은 복잡한 계산을 R1CS→QAP 다항식 등식으로 변환한 뒤, 신뢰 설정에서 만든 CRS와 페어링을 이용해 그**룹 원소 세 개짜리 짧은 증명과 네 번의 페어링 검증으로 모든 제약을 한 번에 체크하는 zk-SNARK 프로토콜**이다. Trusted setup에서 숨겨진 $$\alpha, \beta, \gamma, \delta, \chi$$와 증명 단계의 랜덤 값들을 통해, $$A, B, C$$안에 **올바른 제약조건, 공개 입력, witness 일관성 검증 항, 블라인딩 상쇄 항을** 동시에 인코딩하고 최종 검증식 하나로 이를 모두 확인할 수 있도록 설계된다. 이로인해 Groth16은 독성 폐기물(toxic waste)을 신뢰해야 한다는 전제가 필요하지만 **짧은 증명 크기와 빠른 검증**으로 인해 현재까지 많이 쓰이는 zk-SNARK 중 하나이다. ### Reference 1.