# NIZK

{% hint style="warning" %}
**목표 : 영지식 증명을 실용적으로 만드는 핵심 개념인 비상호작용성이 무엇인지, 그리고 어떻게 달성되는지 알아본다.**
{% endhint %}

처음 Web3에 대해 공부할 때 내 모든 자산 정보와 거래 내역이 모두에게 공개된다는 것에 약간의 거부감이 든 적이 있을 것이다. 하지만 잘 생각해보면 우리가 지금 일상에서 접하는 모든 거래, 온라인 서비스에서도 내가 아는 정보를 직접 제공해야 한다. 물론 상대에게 내가 정당한 사용자라는 것을 증명하기 위한 가장 쉬운 방법이 직접 정보를 제공하는 것이지만 그 과정에서 민감한 데이터를 노출하게 된다. 온라인 상이라면 다양한 방법을 통해 제 3자에게 데이터를 탈취당할 위험도 존재한다.

이런 문제를 해결하기 위해 나타난 개념이 바로 ZK Proof(Zero-Knowledge Proof) 영지식 증명이다. 영지식 증명은 내가 아는 정보를 직접 공개하지 않으면서 내가 그 정보를 가지고 있음을 증명하기 위한 기술이라고 할 수 있다.

영지식 증명의 속성은 다음과 같다.

1. **완전성 (Completeness)**: 어떤 명제가 참이라면, 그것을 증명할 수 있어야 한다.
2. **건전성 (Soundness)**: 어떤 명제가 거짓이라면, 증명자가 어떠한 거짓말을 통해 검증자에게 조건이 참임을 납득시킬 수 없다.
3. **영지식성 (Zero-Knowledge)**: 검증자는 명제의 참, 거짓 여부 이외에 어떠한 정보도 얻을 수 없다.

영지식 증명의 종류는 크게 두종류로 나눌 수 있다.

1. **대화형 영지식 증명(IZK, Interactive Zero-Knowledge Proof)**
2. **비대화형 영지식 증명(NIZK, Non-Interactive Zero-Knowledge Proof)**

### 상호작용 영지식 증명

<figure><img src="/files/wgjPxDTRe2OFJgIfutsx" alt=""><figcaption></figcaption></figure>

위 그래프는 상호작용 영지식 증명의 흐름을 간략하게 요약한 그래프이다.

위 그래프와 같은 상호작용을 통한 영지식 증명은 몇가지 한계점이 존재한다.

1. 통신 비용 및 오버헤드 : 검증을 반복하는 과정에서 수십, 수백건에 달하는 메시지를 주고받아야 한다.
2. 높은 지연시간 : 각 라운드는 증명자의 응답을 기다렸다가 검증자가 챌린지를 보내야해서 시간이 많이 소요된다.
3. 검증자의 실시간 검증 필요 : 검증자가 증명자의 커밋 메시지를 실시간으로 받아서 챌린지값을 생성해 주어야 하기 때문에 항상 온라인 상태를 유지해야 한다. 따라서 오프라인 환경이나 비동기 환경에서는 사용할 수 없다.
4. 증명의 재사용 불가 : 증명자와 검증자 사이의 검증과정에서 무작위 챌린지 값을 생성하기 때문에 해당 검증 과정은 일회성 검증이 된다. 같은 증명자와 검증자 사이에서도 다시 증명하려면 전 과정을 처음부터 다시 진행해야 한다.
5. 낮은 확장성 : 블록체인이나 공개 검증 시스템과 같이 하나의 증명을 많은 노드가 검증해야 하는 경우 모든 노드가 증명자와 일일이 상호작용하는 것이 사실상 불가능하다.

### 비상호작용 영지식 증명

이러한 한계점을 극복하기 위해서 상호작용 없이 한번의 데이터 전송으로 영지식 증명을 할 수 있는 비상호작용 영지식 증명(NIZK)가 등장했다. NIZK는 다시 크게 두가지로 나눌 수 있다. 이 두가지에 대해 자세히 알아보자.

1. CRS 방식
2. 랜덤 오라클 방식

#### CRS란?

<figure><img src="/files/t6blsRWjD9Zab4YpSF5i" alt=""><figcaption></figcaption></figure>

CRS의 핵심 기능은 검증자의 랜덤 챌린지 값을 미리 생성해두는 것이다. 상호작용 증명에서는 검증자가 무작위 값을 보내 증명자를 테스트하지만 NIZK에서는 CRS가 그 역할을 대신하여 상호작용 없이 검증을 할 수 있도록 한다.

CRS는 신뢰 설정(Trusted Setup)이라는 과정을 통해 생성된 군 원소(group element)들의 집합으로 나타낼 수 있다. 이 과정에서 `α, β, γ, δ, x`와 같은 아무도 모르는 비밀값들이 무작위로 선택되며 CRS는 바로 이 비밀값들이 암호화된 형태로 구성된다.

#### 신뢰 설정이 필요한 이유

신뢰 설정 과정에서는 CRS를 생성하기 위해 아무도 모르는 **비밀 파라미터**를 무작위로 생성한다. CRS는 바로 이 비밀 파라미터들을 암호화한 결과를 말한다.

시스템의 보안은 **이 초기 비밀 파라미터들을 아는 사람이 아무도 없어야 유지된다.** 만약 이 비밀값들이 안전하게 파기되지 않고 누군가에게 유출된다면 그 사람은 시스템의 암호학적 제약을 우회하여 **거짓 증명**을 생성할 수 있게된다.

#### 신뢰설정 예시

신뢰 설정을 시작해보자.

$$
\text{setup}(1^\lambda) = gp
$$

우선 Field에서 비밀 값 $$\tau$$를 선택한다.

$$
\tau \xleftarrow{} \mathbb{F}\_p
$$

이후 $$\tau$$값을 이용해서 글로벌한 파라미터를 생성한다.

$$
gp = { g, g^\tau, g^{\tau^2}, g^{\tau^3}, \dots, g^{\tau^d} }
$$

모든 값을 생성한 후에는 $$\tau$$를 삭제해야 한다.

### 신뢰 설정 방식

신뢰 설정 문제를 해결하기 위해 크게 두 가지 방식이 사용된다.

#### 단일 주체 신뢰 설정 (Single-Party Trusted Setup)

가장 간단한 방식으로 시스템 개발자와 같이 신뢰할 수 있는 단일 주체가 비밀 파라미터를 생성하고 이를 이용해 CRS를 계산한 뒤 사용했던 비밀 파라미터를 안전하게 파기하는 방식이다.

* **장점**: 과정이 간단하고 빠르다.
* **단점**: **중앙화된 신뢰**를 요구한다. 사용자는 해당 주체가 정말로 비밀 파라미터를 완벽하게 파기했음을 믿어야만 성립된다. 만약 해당 주체가 악의적이거나 실수로 정보를 유출했다면 시스템 전체가 위험에 처할 수 있다.

#### 다자간 계산(MPC) 신뢰 설정 (Multi-Party Computation Trusted Setup)

단일 주체에 대한 과도한 신뢰 문제를 해결하기 위해 고안된 방식으로 **여러 명**이 협력하여 CRS를 생성한다. Zcash와 같은 대규모 프로젝트에서 사용하는 방식이다.

* **작동 원리**:
  1. 첫 번째 참여자가 자신의 비밀값을 이용해 CRS의 초기 값을 생성한다. 그 후 자신의 비밀값은 즉시 파기한다.
  2. 두 번째 참여자는 첫 번째 참여자가 만든 결과물을 받아 다시 **자신만의 비밀값**을 추가로 적용하여 CRS를 업데이트한다. 그 후 자신의 비밀값도 즉시 파기한다.
  3. 이 과정을 수십, 수백 명의 참여자가 반복하면 된다.
* **장점**: **참여자 중 단 한 명이라도 정직하게 자신의 비밀값을 파기했다면** 전체 CRS 생성에 사용된 최종 비밀 정보는 누구도 알 수 없게 된다. 시스템의 보안을 깨려면 행사에 참여한 **모든 참여자가 서로 담합**해야 한다. 참여자 수가 많아질수록 담합은 사실상 불가능해져서 보안의 수준이 높아진다.
* **단점**: MPC의 구현과 계산에 있어서 많은 비용과 시간이 필요하다. 또한 MPC 신뢰 설정에 참여하는데에 적절한 보상이 없다면 참가자 수가 줄어들고 이에 따라 보안 수준이 떨어질 수 있다.

### 증명자 (Prover)의 CRS 적용 심층 분석

증명자의 목표는 단순히 비밀 정보(witness)를 숨기는 것을 넘어, 그 비밀 정보를 **CRS라는 규칙에 따라 암호학적으로 검증 가능한 증명으로 재구성**하는 것이다.

#### **목표: 비밀의 암호학적 구조화**

증명자가 가진 비밀값은 그 자체로는 단순한 숫자들의 나열일 뿐이다. 증명자는 이 숫자들을 사용하여 검증자가 특정한 수학적 관계(QAP 방정식)를 만족하는지 확인할 수 있는 데이터를 만든다. 해당 데이터를 이용해서 원래 숫자를 절대로 역산할 수 없는 데이터를 증명 `π`라고 한다.

#### **핵심 연산: 강제된 선형 결합 (Linear Combination)**

증명자가 CRS를 사용하는 핵심 방식은 **선형 결합이다**. 이것이 왜 중요하냐면 CRS는 증명자에게 비밀 파라미터 `α, x` 등의 원본 값을 주지 않고 오직 그것들이 암호화된 군 원소만을 제공하기 때문이다.

타원 곡선 군에서 증명자가 할 수 있는 연산은 두 가지뿐이다.

* **스칼라 곱셈**: $$a \* \[P]\_1 = \[aP]\_1$$ (점 P를 a번 더하기)
* **점 덧셈**: $$\[P]\_1 + \[Q]\_1 = \[P+Q]\_1$$ (두 점을 더해 새로운 점 만들기)

이 두 연산의 조합이 바로 선형 결합이다. CRS는 증명자가 자신의 비밀값을 계수로 사용하여 CRS가 제공하는 군 원소들을 더하고 곱하는 것 외에는 다른 어떤 연산도 할 수 없도록 한다.

#### **적용 예시 (Groth16) - 단계별 계산 과정**

Groth16 증명의 첫 번째 요소인 $$\[A]\_1$$의 생성 과정을 단계별로 살펴보자.

* **계산 절차**:

  1. **다항식 항 계산**: 증명자는 먼저 $$\sum a\_i u\_i(x)$$에 해당하는 군 원소를 계산해야 한다. $$u\_i(x)$$는 $$x$$에 대한 다항식이므로 $$u\_i(x) = \sum\_{k=0}^{n-1} c\_{i,k} x^k$$ 형태로 표현된다. 따라서 증명자는 다음을 계산하면 된다. $$\[\sum a\_i u\_i(x)]*1 = \sum*{i=0}^{m} a\_i \cdot \[u\_i(x)]\_1$$&#x20;

     (이때 $$\[u\_i(x)]\_1$$는 CRS에 있는 $$\[x^k]\_1$$*들을* $$\[x^k]*1$$*의 계수* $$c*{i,k}$$로 선형 결합하여 미리 계산되어 있을 수 있다.)
  2. **랜덤값 항 계산**: 영지식성을 위해 랜덤값 $$r$$을 선택하고 CRS에서 $$\[\delta]\_1$$를 가져와 스칼라 곱셈을 수행한다.&#x20;

     $$\[r\delta]\_1 = r \cdot \[\delta]\_1$$
  3. **최종 결합**: 위에서 계산한 모든 군 원소들과 CRS의 $$\[\alpha]\_1$$를 모두 더한다(점 덧셈).

     $$\[A]\_1 = \[\alpha]\_1 + \[\sum a\_i u\_i(x)]\_1 + \[r\delta]\_1$$

     이 과정을 통해 비밀값 $$a\_i$$와 랜덤값 $$r$$이 CRS의 구조 안에 안전하게 인코딩된 최종 증명 요소 $$\[A]\_1$$가 완성된다. $$\[B]\_2$$와 $$\[C]\_1$$ 역시 유사한 선형 결합 과정을 통해 계산된다.

### 검증자 (Verifier)의 CRS 적용 심층 분석

검증자의 목표는 증명자가 만든 증명을 해체하거나 내부를 들여다보지 않고, CRS를 이용해 **무결성을 확인**하는 것이다.

#### **목표: 구조적 무결성 검증**

검증자는 증명자의 비밀값을 전혀 알지 못한다. 검증자가 할 수 있는 것은 오직 증명자가 제출한 증명과 공개된 CRS의 일부(검증 키)가 **미리 약속된 수학적 관계를 만족하는지** 확인하는 것뿐이다. 이 관계가 성립한다면 완전성(Completeness)에 의해 그 증명은 유효한 비밀값으로부터 생성되었음이 보장된다.

#### **핵심 연산: 페어링을 통한 관계 검증**

검증의 핵심 도구는 **빌리니어 페어링이다**. 페어링 연산 $$e(\[X]\_1, \[Y]\_2)$$는 검증자에게 숨겨진 지수 값들의 곱셈( $$X \cdot Y$$)에 접근할 수 있게 해준다. 검증자는 이 창구를 통해 증명자가 만든 각 증명 요소들( $$\[A]\_1$$, $$\[B]\_2$$, $$\[C]\_1$$)이 올바른 곱셈 관계를 가지고 있는지 확인한다.

#### **적용 예시 (Groth16) - 검증 방정식의 의미**

Groth16의 최종 검증 방정식은 다음과 같다. (수식의 `+`는 군 $$\mathbb{G}\_T$$에서의 곱셈을 의미한다.)

$$
e(\[A]\_1, \[B]\_2) = e(\[\alpha]\_1, \[\beta]\_2) \cdot \left( \prod{i=0}^{l} e\left(\[\dots]\_1, \[\gamma]\_2\right)^{a\_i} \right) \cdot e(\[C]\_1, \[\delta]\_2)
$$

각 항의 의미는 다음과 같다.

* **좌변** $$e(\[A]\_1, \[B]\_2)$$: 증명자가 자신의 비밀값과 QAP의 입력 다항식들을 결합하여 만든 두 핵심 증명 요소의 관계를 나타낸다. 지수 공간에서 이는 $$A \cdot B$$에 해당하며 **QAP의 핵심인 곱셈 관계**와 **증인 일관성**을 모두 담고 있는 항이다.
* **우변 첫 번째 항** $$e(\[\alpha]\_1, \[\beta]\_2)$$: 검증 키에 포함된 CRS의 일부. 이는 증명자가 $$\[A]\_1$$과 $$\[B]\_2$$를 만들 때 각각 $$\alpha$$와 $$\beta$$를 정직하게 포함시켰는지를 확인하는 **기준점(benchmark)** 역할을 한다. 이 항이 일치해야만 증인 일관성이 보장된다.
* **우변 두 번째 항** : 공개된 정보(statement $$a\_i$$)와 관련된 부분. 검증자는 이 부분을 직접 계산하여 방정식에 반영한다.
* **우변 세 번째 항** $$e(\[C]\_1, \[\delta]\_2)$$: 증명자가 QAP의 출력 및 나머지 항들을 모두 합친 $$\[C]\_1$$의 유효성을 검증하는 부분이다.

### 결론

검증자는 자신이 가진 CRS의 일부(검증 키)와 공개된 정보를 이용해 방정식의 **정답**을 구성하고 증명자가 제출한 증명 조각들이 이 정답과 일치하는지를 페어링 연산을 통해 확인함으로써 전체 계산의 정당성을 검증한다.


---

# 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/nizk.md?ask=<question>
```

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.