# Groth16

## **1. R1CS와 QAP: 계산을 검증 가능한 수학 문제로 변환하는 작업**

### **1.1. 1단계: 모든 계산을 덧셈과 곱셈으로 분해하기 (Arithmetic Circuit)**

첫 번째 단계는 증명하려는 프로그램을 간단한 연산 단위인 'gate'들의 연결, 즉 **Arithmetic Circuit**으로 변환하는 것입니다. 수행되는 모든 복잡한 연산(논리 연산, 조건문, 반복문 등)은 근본적으로 수많은 덧셈과 곱셈 연산의 조합으로 표현할 수 있습니다.

$x^3 + x + 5 == 35$ 라는 계산을 증명하려는 경우를 예로 들어보겠습니다. (Prover는 $x=3$ 이라는 비밀을 알고 있습니다.) 이 계산은 다음과 같은 일련의 간단한 gate로 분해됩니다.

> $gate 1: sym1 = x * x$
> $gate 2: y = sym1 * x$
> $gate 3: sym2 = y + x$
> $gate 4: out = sym2 + 5$
> $gate 5: out == 35$ (제약 조건)

계산 과정을 단순 연산의 흐름으로 표현한 것을 Arithmetic Circuit라고 합니다. **Prover는 이제 이 회로의 각 gate가 올바르게 계산되었음을 증명해야 합니다.**

### **1.2. 2단계: 제약 행렬 (A, B, C) 및 벡터 방정식 (R1CS: Rank-1 Constraint System)**

R1CS는 Arithmetic Circuit의 모든 gate의 제약 조건을 단 하나의 통일된 벡터 방정식 형태로 표현하는 방법입니다. ($(a · s) * (b · s) - (c · s) = 0$) Arithmetic Circuit의 각 gate는 여전히 개별적인 계산 단계로, 각 gate는 곱셈 또는 덧셈으로 형태가 다릅니다.

#### 1. Solution Vector ($s$)
계산에 사용된 모든 변수들을 하나의 긴 벡터로 만듭니다. 이 벡터는 전체 계산의 상태를 담고 있으며, Prover는 이 벡터의 모든 값을 알고 있습니다.

$s = [1, x, out, sym1, y, sym2]$ (여기서 $1$은 상수항을 위한 dummy 변수, $x$는 비밀 입력(witness), $out$은 공개 출력입니다.) Prover가 $x=3$을 알고 있다면, 올바른 solution vector는 $s = [1, 3, 35, 9, 27, 30]$이 됩니다.

### 2. 각 gate를 벡터 방정식으로 변환

각 gate에 대해, 변수들을 '선택'하여 곱셈 또는 덧셈 관계를 표현하는 세 개의 벡터 $a$, $b$, $c$를 만듭니다. 이제 제약 행렬 (A, B, C)로 변환합니다. 예를 들어 $gate 1: sym1 = x * x$는 다음과 같이 표현됩니다.
> $a = [0, 1, 0, 0, 0, 0]$ (벡터 $s$에서 $x$를 선택)
> $b = [0, 1, 0, 0, 0, 0]$ (벡터 $s$에서 $x$를 선택)
> $c = [0, 0, 0, 1, 0, 0]$ (벡터 $s$에서 $sym1$을 선택)

**모든 gate를 이런 방식으로 변환하면, gate 수만큼의 벡터 $(a_i, b_i, c_i)$ 쌍들이 생겨납니다. 이것이 바로 R1CS입니다.**

$(a · s) * (b · s) = (c · s)$ 관계가 성립하며 ($(x) * (x) = (sym1)$) 모든 gate에 대해 이 작업을 반복하여 행렬 $A$, $B$, $C$를 만듭니다. 각 행렬의 행 하나가 gate 하나를 의미합니다. 결국 이 모든 것을 종합하면, R1CS는 다음 방정식을 만족하는 $s$ 벡터가 존재함을 보이는 문제입니다. $(A · s) ◦ (B · s) - (C · s) = 0$ (여기서 ◦는 원소별 곱셈입니다.)

여전히 gate 수만큼의 방정식을 모두 확인해야 하므로 매우 비효율적입니다.

### **1.3. 3단계: 수많은 제약 조건을 단 하나의 다항식으로 압축하기 (QAP: Quadratic Arithmetic Program)**

QAP는 R1CS의 수많은 제약 조건들을 단 하나의 다항식 나눗셈 문제로 압축하는 단계입니다. (다항식 등식으로 변환하는 작업 수행)
> "만약 $n$ 개의 서로 다른 지점에서 두 $d$ 차 다항식이 같은 값을 가진다면, 그리고 $n > d$라면, 두 다항식은 사실상 같은 다항식이다."라는 원리를 이용합니다.

#### 과정

1. 좌표 부여: R1CS의 각 제약(gate)에 임의의 x좌표를 부여합니다. (예: gate 1은 $x=1$, gate 2는 $x=2$, ...)
2. 행렬을 다항식으로 변환: Lagrange interpolation을 사용하여 R1CS 행렬 $A, B, C$의 각 열을 다항식으로 변환합니다. (예: 행렬 $A$의 $j$ 번째 열은 $A_j(x)$라는 다항식이 됩니다. 이 다항식은 $x=k$에서 $A_{kj}$ 값을 가집니다.)
3. 전체 다항식 정의: solution vector $s$의 각 원소 $s_j$를 계수로 사용하여 전체 다항식을 정의합니다. (다항식 결합)
> $A(X) = Σ s_j·A_j(X)$
> $B(X) = Σ s_j·B_j(X)$
> $C(X) = Σ s_j·C_j(X)$

만들어진 $A(X), B(X), C(X)$ 다항식들은 $X=k$에서 평가하면, 정확히 k번째 R1CS 제약의 내적 값과 같아집니다. ($A(k) = a_k · s$, $B(k) = b_k · s$, $C(k) = c_k · s$)

4. Target polynomial $T(X)$: 모든 제약 조건의 x좌표(1, 2, ...)를 근으로 갖는 다항식을 정의합니다. (하나의 다항식 등식으로...)
> $T(X) = (X-1)(X-2)...(X-n)$

5. QAP 최종 형태: R1CS의 모든 제약 조건 $(A·s)◦(B·s) - (C·s) = 0$이 만족된다는 것은, 다항식 $P(X) = A(X)·B(X) - C(X)$가 모든 제약 지점 (1, 2, ...)에서 0이 된다는 의미와 같습니다. 이는 곧 $P(X)$가 $T(X)$로 나누어떨어짐을 의미합니다. ($A(X)·B(X) - C(X) = H(X) · T(X)$)

Prover는 이제 "나는 solution vector $s$를 알고 있고, 그 $s$를 사용해 만든 다항식 $A(X), B(X), C(X)$가 위 등식을 만족하게 하는 quotient polynomial $H(X)$를 계산할 수 있다"는 것을 증명하면 됩니다.

수많은 제약 조건이 단 하나의 다항식 나눗셈 문제로 바뀌게 된 것을 확인할 수 있습니다.

## **2. NIZK (Non-Interactive Zero-Knowledge)**

QAP라는 수학적 문제를 증명해야 합니다. 비밀 정보($s$)를 숨기고, Verifer와의 대화 없이 증명하는 것이 NIZK의 역할이며, **Trusted Setup** 을 통해 생성된 **CRS(Common Reference String)** 를 사용합니다.

이전 과정에서 복잡한 계산 문제를 $A(X)·B(X) - C(X) = H(X)·T(X)$라는 단 하나의 다항식 등식 문제(QAP)로 변환했습니다. Prover는 이제 이 등식을 만족시키는 다항식 $A(X), B(X), C(X), H(X)$를 알고 있음을 증명해야 합니다.

### **Trusted Setup**
CRS는 투명한 절차를 통해 생성되어야 합니다. 만약 CRS를 만드는 과정에 악의가 개입되면 시스템 전체가 붕괴될 수 있기 때문입니다. 이 절차를 Trusted Setup 또는 Ceremony 라고 부릅니다.

Groth16에서는 다음과 같은 비밀값들이 사용됩니다.

> $τ$ (tau): 다항식이 평가될 비밀값
> $α$ (alpha), $β$ (beta): 증명의 일관성을 확인하고 영지식성을 부여하는 데 사용되는 비밀값
> $δ$ (delta), $γ$ (gamma): 증명을 무작위화하고 검증 방정식을 완성하는 데 사용되는 비밀값

이 값들은 아주 강력한 난수 생성기를 통해 무작위로 선택됩니다.

생성이 끝나면 사용된 비밀값들은 **반드시 영구적으로 폐기**되어야 합니다. 이를 toxic waste 처리라고 합니다. 만약 이 비밀값들이 유출되면 누구나 가짜 증명을 만들 수 있어 시스템 전체의 신뢰가 무너집니다.

### **CRS의 역할**
Prover가 증명을 던져주면, Verifer는 그것만 보고 참/거짓을 판단할 수 있는 시스템입니다. Prover와 Verifer 사이에 메시지를 주고받는 상호작용 없이 가능하게 하려면 두 참여자가 사전에 공유하는 무언가가 필요한데, 이것이 바로 CRS입니다.

CRS는 비밀값($τ$ 등)에서의 다항식 평가를 암호화된 형태로 담고 있습니다. 예를 들어, proving key에는 $[τ⁰]₁, [τ¹]₁, ..., [τⁿ]₁$와 같은 값들이 포함됩니다. (여기서 $[...]₁$는 elliptic curve group G₁의 한 점으로 변환되었을 의미)
따라서 증명키 pk에 $[τ⁰]₁, [τ¹]₁, ..., [τⁿ]₁$가 들어있다는 것은, Prover가 비밀 $τ$를 전혀 모르지만 $τ$의 1차부터 n차까지의 거듭제곱에 해당하는 암호화된 값들을 모두 가지고 있다는 의미입니다. 이를 통해 어떤 $n-1$차 다항식 $P(X)$라도 $τ$에서 평가한 값 $[P(τ)]₁$를 계산할 수 있게 되는 것입니다.
> 생성된 비밀값들을 이용해 Proving Key와 Verification Key를 만드는데, 이 둘을 합쳐 CRS라고 부릅니다.

Prover는 Proving Key, Verifer는 Verification Key를 가지고 있습니다. Prover는 어떻게 비밀 witness `w`를 숨기면서 QAP 등식을 증명할까요?

$A(X)·B(X) - C(X) = H(X)·T(X)$

Prover는 이 등식이 비밀 지점 $τ$에서 성립함을 보여야 합니다.

1. **Prover의 계산:**
- Prover는 자신의 비밀 witness $w$를 이용해 다항식 $A(X), B(X), C(X), H(X)$를 계산합니다.
- Proving key $pk$에 있는 $[τ⁰]₁, [τ¹]₁, ...$ 등 암호화된 값들을 이용해, 이 다항식들을 $τ$에서 평가한 값의 암호화된 버전, 즉 $[A(τ)]₁$, $[B(τ)]₂$, $[C(τ)]₁$, $[H(τ)]₁$를 계산합니다.
- Prover는 $τ$가 무엇인지 전혀 모르지만, 다항식이 계수들의 선형 결합이라는 점과 elliptic curve 연산의 homomorphic 성질 덕분에 $[P(τ)]₁$를 계산할 수 있습니다.
$P(X) = p₀ + p₁X + ...$ → $[P(τ)]₁ = p₀[τ⁰]₁ + p₁[τ¹]₁ + ...$

계산된 값들을 조합하여 최종 증명 $π$를 만듭니다.

2. **Verifer의 역할:**
- Verifer는 증명 $π$와 verification key $vk$를 이용해 단 하나의 pairing 등식을 확인합니다.
- 이 등식은 $A(τ)·B(τ) - C(τ) = H(τ)·T(τ)$라는 관계가 암호화된 상태에서 성립하는지를 확인합니다.

### Toxic Waste

CRS 생성이 완료되면, 사용된 모든 비밀값($τ$, $α$, $β$, $δ$, $γ$)은 **반드시, 영구적으로 파괴되어야 합니다.** 만약 단 한 명이라도 이 비밀값을 알게 되면, QAP의 `H(X)`를 마음대로 조작하여 가짜 증명을 무한정 만들어낼 수 있게 됩니다.

실제 시스템에서는 **Multi-Party Computation (MPC)** 방식을 사용합니다. Zcash 등이 이를 활용합니다. 여러 참여자가 각자 비밀 조각을 만들고, 자신의 조각으로 CRS를 업데이트한 뒤 자신의 비밀 조각을 파기합니다. **참여자 중 단 한 명이라도 정직하게 자신의 비밀 조각을 파기했다면, 전체 비밀값은 그 누구도 알 수 없게 되어** 시스템의 신뢰가 보장됩니다.

## **3. Groth16 증명의 구성: 3개의 그룹 원소**

증명의 목표는 $A(X)·B(X) - C(X) = H(X)·T(X)$라는 QAP 등식이 비밀 지점 $τ$에서 성립함을 보이는 것입니다. Prover는 이 등식을 만족시키는 다항식 $A(X), B(X), C(X), H(X)$를 알고 있지만, 이를 그대로 제출할 수는 없습니다.

Groth16은 이 4개 다항식의 정보를 **3개의 elliptic curve 위의 점** $π = ([A]₁, [C]₁, [B]₂)$ 안에 암호학적으로 "압축"하여 제출합니다. 이 3개의 점은 단순한 데이터가 아니라, 검증 방정식과 만났을 때 비로소 의미를 갖는 cryptographic commitment입니다.

### **3.1. [A]₁와 [B]₂?**

$[A]₁$와 $[B]₂$는 QAP 등식의 핵심인 $A(X)$와 $B(X)$ 다항식에 대한 commitment입니다. 이 두 다항식은 Prover의 비밀 witness $w$의 정보를 가장 많이 포함하고 있습니다.

**[A]₁ (G₁ group의 점): $A(X)$에 대한 commitment**

Prover는 다음의 계산을 통해 $[A]₁$를 생성합니다. 이 모든 계산은 proving key(pk)에 포함된 암호화된 값들을 이용한 선형 결합으로 수행됩니다.

$A₁ = α + A(τ) + r·δ$

- $A(τ)$: Prover가 알고 있는 solution vector $s$를 이용해 계산한 다항식 $A(X)$를 비밀 지점 $τ$에서 평가한 값입니다. 이것이 **증명의 핵심 내용**입니다.

- $α$: Trusted Setup 시 생성된 비밀값 $α$입니다. 이 항은 **Knowledge-of-Coefficient Attack** 을 방어하고, 증명의 일관성을 강제하는 역할을 합니다. 만약 이 항이 없다면, 악의적인 Prover가 기존의 유효한 증명을 약간만 수정하여 다른 증명을 위조할 수 있습니다.

- $r·δ$: 영지식성을 보장하기 위한 **randomization** 항입니다.
- $δ$: Trusted Setup 시 생성된 비밀값입니다.
- $r$: Prover가 증명을 생성할 때마다 새로 뽑는 임의의 난수입니다.
- 이 항 때문에, 동일한 증명이라도 생성할 때마다 $[A]₁$의 값은 계속 바뀝니다. 따라서 Verifer는 $[A]₁$ 자체를 보고는 $A(τ)$에 대한 어떤 정보도 얻을 수 없습니다. (완벽한 영지식성)

**[B]₂ (G₂ group의 점): $B(X)$에 대한 commitment**

$[B]₂$는 $[A]₁$와 거의 동일한 구조를 가지지만, 결정적으로 **서로 다른 elliptic curve group G₂**의 원소를 사용합니다.

$B₂ = β + B(τ) + s·δ$

- $β$, $s$: $α$, $r$과 유사한 역할을 하는 G₂ 상의 비밀값과 난수입니다.

- **G₁과 G₂를 나누는 이유**: 이것이 바로 다음 학습 주제인 **pairing**을 사용하기 위한 핵심적인 설계입니다. Pairing 함수 $e(G₁, G₂)$는 서로 다른 두 group의 원소를 입력으로 받습니다. $[A]₁$와 $[B]₂$를 서로 다른 group에 둠으로써, 검증 단계에서 이 둘을 pairing하여 지수부의 곱셈 $A(τ)·B(τ)$를 효과적으로 계산할 수 있게 됩니다.

### **3.2. [C]₁?**

$[C]₁$은 $[A]₁$와 $[B]₂$가 **정직하게 계산되었음을 보증**하는 역할을 합니다. $[A]₁$와 $[B]₂$가 증명의 핵심 내용을 담고 있다면, $[C]₁$이 없다면, Prover는 $A(X)$와 $B(X)$를 QAP 등식과 전혀 상관없는 값으로 만들어도 Verifer를 속일 수 있습니다.

$[C]₁$의 구조는 언뜻 보면 매우 복잡하지만, 그 목표는 단 하나입니다: **검증 방정식에서 모든 불필요한 항들을 깨끗하게 소거하고, QAP 등식의 본질만 남기는 것.**

$C₁$는 다음과 같은 요소들의 선형 결합으로 이루어집니다.

$C₁ = s·A(τ) + r·B(τ) + r·s·δ + L(x, τ) + H(τ)·T(τ)$
(실제 공식은 이보다 더 복잡하며, 비밀값 $γ$, $δ$ 등으로 나누고 곱하는 과정이 포함됩니다.)

- $s·A(τ)$와 $r·B(τ)$: $[A]₁$와 $[B]₂$를 만들 때 사용된 난수 $r$, $s$가 서로 교차되어 곱해진 항입니다. 검증 방정식에서 $e([A]₁, [B]₂)$를 계산하면 $r·δ·B(τ)$와 $s·δ·A(τ)$ 같은 "garbage term"들이 생겨나는데, $[C]₁$에 이 항들이 포함되어 있어 정확히 상쇄됩니다.
- $r·s·δ$: $[A]₁$와 $[B]₂$의 randomization 항끼리의 곱으로 인해 생기는 garbage term $r·s·δ²$를 상쇄하기 위한 항입니다.
- $L(x, τ)$: 공개 입력 $x$에 대한 다항식 평가값입니다. QAP의 $C(X)$ 항 중 공개 입력 부분을 담당합니다.
- $H(τ)·T(τ)$: **QAP의 핵심**입니다. Quotient polynomial $H(X)$를 비밀 지점 $τ$에서 평가한 값입니다. Prover는 자신이 올바른 $H(X)$를 알고 있음을 $[C]₁$ 안에 포함시켜 증명합니다.

**3개의 점에 담긴 의미는 다음과 같이 정리할 수 있습니다.**
- **[A]₁**: Witness의 정보가 담긴 $A(X)$의 암호화된 평가 (영지식성 포함)
- **[B]₂**: Witness의 정보가 담긴 $B(X)$의 암호화된 평가 (영지식성 포함, pairing을 위해 다른 group 사용)
- **[C]₁**: $A(X)$와 $B(X)$가 QAP를 만족하는 quotient polynomial $H(X)$와 일관성을 가짐을 증명하는 정교한 보조 증명

## **4. Groth16 검증 단계: 단 하나의 방정식, 3번의 Pairing**

### **검증의 목표**

Verifer의 목표는 Prover가 제출한 3개의 점 $π = ([A]₁, [C]₁, [B]₂)$이 정말로 QAP 등식 $A(X)·B(X) - C(X) = H(X)·T(X)$를 비밀 지점 $τ$에서 만족시키는 유효한 증거인지를 확인하는 것입니다.

#### **4.1. Pairing**

검증 방정식을 이해하기 전에, **pairing**에 대해 먼저 알아야 합니다.

Pairing $e$는 서로 다른 두 group(G₁, G₂)의 원소를 입력받아, 제3의 group(Gᴛ, target group)의 원소로 mapping하는 함수입니다.
> $e: G₁ × G₂ → Gᴛ$

**Bilinearity:**
> $e([a]₁, [b]₂) = e(a·G₁, b·G₂) = e(G₁, G₂)^{(a·b)}$
> $e([a]₁ + [c]₁, [b]₂) = e([a]₁, [b]₂) · e([c]₁, [b]₂)$

$a$와 $b$라는 값을 직접 알지 못하고, 그 값들이 암호화된 형태인 $[a]₁$과 $[b]₂$만 가지고 있습니다. 그럼에도 불구하고, pairing을 통해 지수 상에서의 곱셈 결과인 $e(G₁, G₂)^{(a·b)}$를 계산해낼 수 있습니다. $[A]₁$와 $[B]₂$에 담긴 비밀 다항식 평가값 $A(τ)$와 $B(τ)$의 곱을 검증이 가능해집니다.

#### **4.2. 검증 방정식**

Groth16의 검증 방정식을 단계별로 접근해보겠습니다.

> **$e(A, B) = e(α, β) · e(L(x), γ) · e(C, δ)$**

**1. 좌변(LHS): Witness의 주장을 계산**

좌변은 $e(A, B)$입니다. Prover가 제출한 $[A]₁$와 $[B]₂$를 pairing하는 과정입니다. 3장에서 정의한 대로 각 항을 대입해 봅시다.

> $A = α + A(τ) + r·δ$
> $B = β + B(τ) + s·δ$

Pairing의 bilinear 성질을 이용해 $e(A, B) = e([α + A(τ) + rδ]₁, [β + B(τ) + sδ]₂)$를 전개하면, 지수부에서는 각 항들이 곱셈으로 연결됩니다.

$e(A, B)$의 지수부 = $αβ + αB(τ) + αsδ + A(τ)β + A(τ)B(τ) + A(τ)sδ + rδβ + rδB(τ) + rsδ²$

복잡해 보이지만, 여기서 확인하고 싶은 **항 $A(τ)B(τ)$** 가 들어있음을 알 수 있습니다. 나머지는 증명을 위해 추가된 "auxiliary term" 또는 "garbage term"입니다.

**2. 우변(RHS): QAP의 나머지 부분을 구성하고 auxiliary term을 상쇄**

우변은 $e(α, β) · e(L(x), γ) · e(C, δ)$입니다. 이 부분은 좌변의 auxiliary term들을 정확히 상쇄하고, QAP 등식의 나머지 부분($C(τ)$와 $H(τ)T(τ)$)을 만들어내는 역할을 합니다.

- **$e(α, β)$:** 이 항은 좌변의 $αβ$ 항과 정확히 일치합니다. Verification key에 $[α]₁$와 $[β]₂$가 포함되어 있어 Verifer가 계산할 수 있습니다.

- **$e(L(x), γ)$:** 이 항은 공개 입력 $x$와 관련된 부분입니다. $L(x)$는 공개 입력 $x$와 관련된 QAP 다항식 부분을 $τ$에서 평가한 값입니다. Verifer는 verification key와 $x$를 이용해 $[L(x, τ)]₁$를 계산할 수 있고, 이를 $[γ]₂$와 pairing합니다. 이 결과는 QAP 등식의 $C(X)$ 부분 중 일부를 담당합니다.

- **$e(C, δ)$:** 이 항은, 3장에서 보았듯이, Prover가 제출한 $C$는 좌변에서 발생한 모든 auxiliary term들을 상쇄하고 QAP 등식을 완성하는 데 필요한 정보를 담고 있습니다.

> $C = (sA(τ) + rB(τ) + rsδ)/γ + (L(x, τ) + H(τ)T(τ))/δ$

$e(C, δ)$를 계산하면, 지수부에서 $δ$가 곱해지므로 $γ$로 나누었던 항들은 다시 살아나고 $δ$로 나누었던 항은 $δ$가 약분됩니다.

> $e(C, δ)$의 지수부 ≈ $(sA(τ) + rB(τ) + rsδ)·δ/γ + H(τ)T(τ)$

실제로는 $α$, $β$와 결합된 항들도 모두 포함되어 좌변의 모든 auxiliary term들을 정확히 상쇄시킵니다.

**3. 최종 결과**

좌변과 우변을 비교해 봅시다.

$LHS 지수부: A(τ)B(τ) + [αβ + αB(τ) + ... + rsδ²]$
$RHS 지수부: [αβ] + [L(x, τ)·γ] + [C·δ]$

$C$ 덕분에, $[...]$ 안에 들어있는 모든 auxiliary term들은 양변에서 정확히 일치하여 소거됩니다. 결국 남는 것은 다음과 같은 등식의 지수 버전입니다.

> $A(τ)B(τ) = L(x, τ) + H(τ)T(τ)$

이는 QAP의 일부인 $C(τ)$를 $L(x, τ)$로 표현한 것이므로, 최종적으로 우리가 증명하고자 했던 QAP 등식과 동치가 됩니다.

> $A(τ)B(τ) - C(τ) = H(τ)T(τ)$

**단 하나의 pairing 방정식을 확인하는 것만으로, Prover가 비밀 witness를 알고 있으며, 그로부터 유도된 모든 다항식들이 QAP 관계를 올바르게 만족함을 수학적으로 확신할 수 있게 됩니다. 이것이 Groth16 검증의 핵심입니다.**

#### **4.3. 연산 효율성**

- **Constant time verification:** 검증 과정에서 수행되는 pairing 연산의 횟수(3회)는 증명하려는 회로의 크기($n$, $m$)와 전혀 상관이 없습니다. 회로가 아무리 커져도 검증 시간은 거의 일정하게 유지됩니다. 이것이 "succinct(간결한)"의 의미입니다.

- **공개 입력 처리 (MSM):** 유일하게 검증 시간이 늘어나는 부분은 공개 입력 $x$의 크기 $l$에 비례하는 $L(x, τ)$ 계산입니다. 하지만 이 계산은 **Multi-Scalar Multiplication (MSM)** 이라는 최적화된 알고리즘을 사용하며, $l$개의 일반적인 elliptic curve 덧셈을 하는 것보다 훨씬 빠릅니다.