ZK Rollup 電路設計數學推導完整指南：從代數電路到 STARK/SNARK 證明系統的工程實踐

概述

零知識 Rollup（Zero-Knowledge Rollup，ZK Rollup）是以太坊最具前景的 Layer 2 擴容方案之一。透過將大量交易在鏈下執行並生成簡潔的零知識證明，ZK Rollup 能夠在保證以太坊主網安全性的前提下，將吞吐量提升數百倍乃至數千倍。截至 2026 年第一季度，zkSync Era、Starknet、Polygon zkEVM、Scroll 等主流 ZK Rollup 網路已累計處理超過 15 億筆交易，總鎖定價值（TVL）突破 180 億美元。

理解 ZK Rollup 的電路設計原理是掌握這項技術的核心關鍵。本文從密碼學數學基礎出發，系統性地推導代數電路（Arithmetic Circuits）、約束系統（Constraint Systems）、多項式承諾（Polynomial Commitments）等核心概念，並深入分析 SNARK 和 STARK 兩大主流證明系統的數學推導與工程實現差異。我們將提供完整的數學公式推導、實際的電路設計範例、以及優化策略，幫助讀者建立對 ZK Rollup 電路的深度理解。

第一章：零知識證明的數學基礎

1.1 計算複雜度理論回顧

在深入零知識證明之前，我們需要回顧一些關鍵的計算複雜度概念，這些概念是理解零知識證明可行性的理論基礎。

NP 類與 NP 完全問題：

定義：非確定性多項式時間（NP）類
語言 L ∈ NP 當且僅當存在多項式時間驗證算法 V 和多項式 p 使得：
x ∈ L ⟺ ∃w ∈ {0,1}* 使得 |w| ≤ p(|x|) 且 V(x,w) = 1

其中 w 稱為「證人」（Witness），V 稱為「驗證算法」

NP 類的直觀含義：
- 「容易驗證」（多項式時間）
- 「可能困難求解」（非多項式時間）

NP 完全問題：
問題 C 是 NP 完全的當且僅當：
1. C ∈ NP
2. 任何 NP 問題都可以在多項式時間內歸約到 C

重要例子：
- 布爾可滿足性（SAT）
- 電路可滿足性（Circuit-SAT）
- 哈密頓回路
- 0-1 整數線性規劃

1.2 算術電路的可滿足性

算術電路是描述 NP 問題的天然工具。給定一個算術電路 C 和輸入 x，我們可以問：是否存在一個秘密輸入 w 使得 C(x, w) = 0？

定義：算術電路

一個算術電路 C over field F 由以下組成：
- n 個輸入變量：x₁, x₂, ..., xₙ
- m 個乘法閘：g₁, g₂, ..., gₘ
- 1 個輸出變量：y

每個乘法閘的形式為：
gⱼ = (Σᵢ aᵢⱼ × vᵢ) × (Σᵢ bᵢⱼ × vᵢ)

其中 vᵢ 是前驅節點（輸入或其他閘）的值

電路可滿足性問題：
輸入：電路 C 和公開輸入 x
證人：秘密輸入 w
目標：驗證 C(x, w) = 0

實例：矩陣乘法電路

1.3 零知識證明的形式化定義

零知識證明（Zero-Knowledge Proof）是一種密碼學協議，它允許「證明者」（Prover）在不透露「證人」（Witness）的情況下，向「驗證者」（Verifier）證明某個陳述是正確的。

定義：零知識證明協議

一個零知識證明協議由三個 PPT（概率多項式時間）算法組成：

1. Gen(1^λ) → (pk, vk)
   - 生成證明密鑰 pk 和驗證密鑰 vk
   - 安全參數 λ 決定安全性級別

2. P(pk, x, w) → π
   - 證明者輸入：pk、公開輸入 x、秘密證人 w
   - 輸出：證明 π

3. V(vk, x, π) → {accept, reject}
   - 驗證者輸入：vk、公開輸入 x、證明 π
   - 輸出：接受或拒絕

零知識性必須滿足三個核心屬性：

屬性 1：完整性（Completeness）
若 x ∈ L 且 P 知道證人 w，則 V 恆接受：
Pr[V(vk, x, P(pk, x, w)) = accept] = 1

屬性 2：可靠性（Sounness）
若 x ∉ L，則任何作弊的證明者都無法說服 V：
Pr[V(vk, x, π*) = accept] ≤ negl(λ)

屬性 3：零知識性（Zero-Knowledge）
存在模擬器 Sim 使得輸出與真實證明不可區分：
{Sim(vk, x)} ≈ {P(pk, x, w)}

1.4 雙線性配對的數學原理

雙線性配對（Pairing）是構建高效零知識證明系統的核心密碼學原語。

定義：雙線性配對

設 G₁, G₂, Gₜ 是具有相同素數階 q 的循環群。
配對 e: G₁ × G₂ → Gₜ 滿足雙線性性：

1. 雙線性：e(a×P, b×Q) = e(P, Q)^{ab}，∀P ∈ G₁, Q ∈ G₂, a,b ∈ ℤₚ

2. 非退化：若 P 是 G₁ 的生成元，Q 是 G₂ 的生成元，則 e(P, Q) 是 Gₜ 的生成元

3. 可計算性：對於任意輸入，配對可以在多項式時間內計算

常用配對曲線：
- BLS12-381：用於以太坊 PoS BLS 簽章
- BN254：用於 EVM 操作
- BLS12-377, BW6-761：用於 ZK 系統

第二章：代數電路與約束系統

2.1 從布爾電路到算術電路

布爾電路限制：
- 只使用 AND, OR, NOT 閘
- 輸入為布爾值（0 或 1）
- 計算複雜度以閘的數量衡量

算術電路推廣：
- 使用加法和乘法閘 over field F
- 輸入為 field elements
- 更適合表示代數關係

轉換示例：布爾 AND 到算術

布爾邏輯：a ∧ b = a × b

算術電路表達：
x₁ = a
x₂ = b
x₃ = x₁ × x₂  // AND 閘

真值表驗證：
┌───────┬───────┬─────────┐
│   a   │   b   │  a × b  │
├───────┼───────┼─────────┤
│   0   │   0   │    0    │
│   0   │   1   │    0    │
│   1   │   0   │    0    │
│   1   │   1   │    1    │
└───────┴───────┴─────────┘

2.2 R1CS 約束系統

R1CS（Rank-1 Constraint System，一階約束系統）是以太坊 ZK-EVM 廣泛使用的約束表達方式。

定義：R1CS

一個 R1CS 實例由以下組成：
- m 個變量：v₀, v₁, ..., vₘ
- n 個約束：R₁, R₂, ..., Rₙ
- 每個約束是三個線性組合的乘積等式：

(Aᵢ · v) × (Bᵢ · v) = (Cᵢ · v)

其中：
- Aᵢ, Bᵢ, Cᵢ 是長度為 m+1 的向量
- v = (1, v₁, ..., vₘ) 是所有變量的向量
- · 表示內積

特殊變量：
- v₀ 恆定為 1
- v₁ 通常是公開輸入
- vₘ 是輸出變量

實例：橢圓曲線點加法約束

設 P = (x₁, y₁), Q = (x₂, y₂), R = P + Q = (x₃, y₃)

約束系統：
1. λ × (x₂ - x₁) = (y₂ - y₁)    // 斜率約束
2. x₃ = λ² - x₁ - x₂              // x 坐標約束
3. y₃ = λ × (x₁ - x₃) - y₁        // y 坐標約束

轉換為 R1CS：
約束 1:
A = [0, 1, -1, λ, 0]
B = [0, 0, 0, 1, 0]
C = [0, 0, 0, 0, 1]

實際上需要引入中間變量來消除二次項。

2.3 約束系統的合併與複製

電路深度問題：
直接實現 C = A × B 需要將 A, B 作為乘法閘的輸入

使用中間變量：
1. s₁ = A
2. s₂ = B
3. s₃ = s₁ × s₂  // C = s₁ × s₂

R1CS 表示：
約束 1:
A = [0, 1, 0, 0]
B = [0, 0, 1, 0]
C = [0, 0, 0, 1]

變量賦值：
v₁ = A
v₂ = B
v₃ = v₁ × v₂ = C

複製約束（Equality Constraints）：
有時需要強制兩個變量相等：
vᵢ = vⱼ

這可以通過添加約束：
(vᵢ - vⱼ) × 1 = 0

或使用 Hadamard 約束：
(1) × (vᵢ - vⱼ) = 0

2.4 Plonkish 電路約束

Plonk 算法使用的約束系統比 R1CS 更加靈活，支援固定數量的「複製約束」和自定義「查找表」。

Plonk 約束形式：

每個 Plonk 閘有以下形式：
qL × a + qR × b + qM × a × b + qO × c + qC = 0

其中：
- qL, qR, qM, qO, qC 是門選擇器（selector）係數
- a, b, c 是三個輸入 wire

常見閘類型：

1. 加法閘：qL = 1, qR = 1, qM = 0, qO = -1, qC = 0
   → a + b - c = 0

2. 乘法閘：qL = 0, qR = 0, qM = 1, qO = -1, qC = 0
   → a × b - c = 0

3. 常量乘法：qL = k, qR = 0, qM = 0, qO = -1, qC = 0
   → k × a - c = 0

Plonk 約束系統的優勢：
- 統一的閘類型簡化電路設計
- 複製約束提供更大的靈活性
- 查找表支援自定義運算

第三章：SNARK 系統的數學推導

3.1 KZG 多項式承諾

KZG（Kate-Zaverucha-Goldberg）承諾是以太坊即將採用的主要多項式承諾方案。

多項式承諾的定義：

承諾者對多項式 f(X) ∈ Fₚ[X] 生成承諾 C
驗證者可以要求證明者在特定點 x 上打開承諾
承諾者提供 (f(x), π)
驗證者檢查 π 來確認 f(x) 的正確性

KZG 承諾的設置：

1. 可信設置（Trusted Setup）
   選擇秘密值 τ ∈ Fₚ
   計算 Powers of Tau：
   G, τG, τ²G, ..., τᵗG
   
   公開參數：
   - [1]G, [τ]G, [τ²]G, ..., [τᵗ]G
   其中 [a]G = a × G

2. 承諾生成
   對於多項式 f(X) = Σᵢ aᵢ Xⁱ：
   C = Σᵢ aᵢ × [τⁱ]G = [f(τ)]G

3. 證明生成（Opening）
   在點 x 處打開：
   
   定義商多項式：
   q(X) = (f(X) - f(x)) / (X - x)
   
   證明：
   π = [q(τ)]G

4. 驗證
   檢查配對等式：
   e(C - [f(x)]G, G) = e(π, [τ]G - [x]G)
   
   等價於：
   e(C, G) = e([f(x)]G, G) × e(π, [τ - x]G)

3.2 Groth16 協議推導

Groth16 是最流行的 SNARK 協議之一，以其簡潔的證明大小著稱。

Groth16 三元組生成（Setup）：

給定 R1CS 約束系統 (Aᵢ, Bᵢ, Cᵢ) 和安全參數 λ：

1. 選擇橢圓曲線群 G₁, G₂, Gₜ 和配對 e: G₁ × G₂ → Gₜ
2. 選擇隨機值 α, β, γ, δ, τ ∈ Fₚ
3. 計算 CRS（Common Reference String）：

   α 相關：
   [α]₁, {[Aᵢ(τ)]₁}
   [β]₁, [β]₂, {Cᵢ(τ)}₁, {Cᵢ(τ)}₂
   
   δ 相關：
   {[τⁱ]₁}, {[τⁱ]₂} for i = 0,1,...,n

證明生成：

給定公開輸入 u 和秘密 witness w：
1. 計算 A = A₀(τ) + Σᵢ uᵢAᵢ(τ) + Σⱼ wⱼAⱼ(τ)
2. 計算 B = B₀(τ) + Σᵢ uᵢBᵢ(τ) + Σⱼ wⱼBⱼ(τ)
3. 計算 C = C₀(τ) + Σᵢ uᵢCᵢ(τ) + Σⱼ wⱼCⱼ(τ)
4. 添加 δ 修正：
   A' = A + H(τ) × δ
   B' = B + H(τ) × δ
   C' = C + α × H(τ) × δ + β × H(τ) × δ + H(τ)² × δ²

5. 最終證明：
   π = ([A']₁, [B']₂, [C']₁)

驗證：

給定驗證密鑰和證明 (πₐ, πᵦ, πᵧ)，驗證：
e(πₐ, πᵦ) = e([α]₁, [β]₂) × e(πᵧ, [γ]₂) × e([Σᵢ uᵢICᵢ(τ)]₁, [β]₂)

這個等式檢查約束是否被滿足。

3.3 PLONK 協議推導

PLONK（Permutations over Lagrange-bases for Oecumenical noninteractive arguments of Knowledge）是一種通用零知識證明協議。

PLONK 約束系統：

定義「副本約束」來連接不同閘之間的相同變量：

副本約束集合 E = {(i, j)} 表示 wire i 和 wire j 必須相等

多項式置換論證：

為每個 wire 定義兩個排列：
- σ: 將每個位置映射到其在「複製前」的位置
- σ': 將每個位置映射到其在「複製後」的位置

目標：證明存在置換 π 使得電路約束成立

具體步驟：

1. 計算 Grand Product Proof
   定義多項式：
   Z(X) = ∏ᵢ (Pᵢ(X) / Qᵢ(X))
   
   其中 Pᵢ, Qᵢ 是與約束相關的多項式

2. 使用 KZG 承諾來承諾 Z(X)

3. 在隨機點 ζ 處驗證：
   Z(ζ) = Z(ζ × ω) × F(ζ) / G(ζ)
   
   其中 ω 是 n 個 root of unity

PLONK 證明協議：

1. Preprocessing（預處理）
   - 設置驗證密鑰（包含置換多項式承諾）
   - 計算複製多項式承諾

2. 證明者階段
   - 計算 witness 多項式
   - 計算閘約束多項式
   - 計算副本約束多項式
   - 生成 Grand Product Proof

3. 驗證者階段
   - 隨機抽樣挑戰點
   - 驗證 KZG 承諾
   - 驗證閘約束
   - 驗證副本約束

3.4 Halo2 電路設計

Halo2 是 Zcash 實現的 PLONK 變體，是當前最流行的 ZK 電路設計框架之一。

Halo2 的核心特性：

1. 增量可驗證計算（IVC）
   - 允許將大電路分解為多個步驟
   - 每步只需驗證相鄰步驟的約束

2. 查找表
   - 原生支援電路外的查找操作
   - 常用於實現非代數操作

3. 自定義閘
   - 可定義任意數量的輸入
   - 靈活的約束表達

Halo2 佈局（Layout）：

Halo2 使用「佈局」來組織電路結構：

Chip：
- 定義特定功能的邏輯單元
- 如：ECDSA 驗證、Keccak 哈希

Config：
- 定義晶片之間的連接
- 定義佈局大小

實例：ECDSA 簽章驗證晶片

配置：
- 輸入：公鑰 P, 簽章 (r, s), 消息哈希 e
- 輸出：accept/reject
- 約束數量：~20,000 個 R1CS 約束

第四章：STARK 系統的數學推導

4.1 STARK 與 SNARK 的根本差異

SNARK vs STARK 特性對比：

┌─────────────┬────────────┬────────────┐
│    特性     │   SNARK    │   STARK    │
├─────────────┼────────────┼────────────┤
│  信任設置   │   需要     │   不需要   │
│  信任設置類型│ 可信設置   │   -        │
│  安全性假設 │   代數     │   Hash     │
│  證明大小   │  ~200-400B │  ~50-200KB │
│  驗證時間   │  ~3-10ms   │  ~10-50ms  │
│  證明者時間 │   中等     │    高      │
│  抗量子     │    否      │    是      │
│  電路通用性 │    是      │    是      │
└─────────────┴────────────┴────────────┘

安全性假設差異：

SNARK（基於配對）：
- 離散對數假設（Pairing-based）
- 代數群模型
- 可信設置泄露不影響安全性

STARK（基於哈希）：
- 隨機預言機模型
- 衝突抵抗 Hash 函數
- 量子計算假設下仍安全

4.2 STARK 的多項式交互式論證（PIE）

STARK 的核心是多項式交互式論證框架。

定義：多項式交互式論證

系統由以下組成：

1. 算術化（Arithmetization）
   - 將計算問題轉換為多項式約束
   - 定義執行追蹤（Execution Trace）
   - 定義約束多項式 C(X)

2. 低度測試（Low-Degree Testing）
   證明多項式 f(X) 的度數小於 d
   
   方法：
   - 隨機選擇直線 L
   - 在直線上進行 Reed-Solomon 測試
   - 使用 Feldman / IPA 驗證

3. 交互式子集和（Interactive Subset Sum）
   證明查詢集合的正確性
   
   方法：
   - 使用 Merkle 樹組織數據
   - 驗證者隨機選擇查詢位置
   - 證明者提供路徑證明

4. 最終消息（Final Message）
   驗證者發送隨機挑戰
   證明者發送所有證明

4.3 FRI 協議推導

FRI（Fast Reed-Solomon Interactive Oracle Proof of Proximity）是 STARK 實現低度測試的核心協議。

FRI 協議步驟：

1. 初始化
   - 選擇有限域 F 和擴展域 F_ext
   - 選擇 coset C = {g × ωⁱ | i = 0,1,...,n-1}
   - 其中 ω 是 n 個原根，g 是生成元

2. 第一輪
   - 令 f₀(X) = 原始多項式
   - 將 f₀(X) 在 coset C 上取值為 [f₀(c₀), ..., f₀(c_{n-1})]
   - 將序列一分為二：f₀,even 和 f₀,odd
   - 定義 f₁(X) = f₀,even(X²) + X × f₀,odd(X²)

3. 遞歸
   令 n_{i+1} = n_i / 2
   對 i = 1, 2, ..., 直到 n_k 足夠小
   
   在每輪：
   - 證明者發送 f_i 的 Commitment
   - 驗證者發送隨機挑戰 β_i
   - 下一輪多項式：
     f_{i+1}(X) = f_i,even(X²) + β_i × f_i,odd(X²)

4. 最終輪
   當 n_k 小於閾值時，直接發送 f_k 的所有係數

5. 驗證
   檢查：
   - 每輪的多項式度數 ≤ n_i/2
   - 最終多項式 f_k 的度數很小

定理：若 f₀ 的度數 < n，則 FRI 接受概率 ≥ 1 - δ
若 f₀ 的度數 ≥ n，則 FRI 接受概率 ≤ δ

其中 δ 是驗證者設置的 soundness 參數。

4.4 STARK 證明生成流程

STARK 證明生成完整流程：

步驟 1：算術化
- 將電路約束轉換為多項式約束
- 生成執行追蹤 T[0..m-1]
- 定義約束多項式 q₀(X), q₁(X), ...

步驟 2：Reed-Solomon 編碼
- 選擇域 F 和參數 n, D
- 對追蹤進行 RS 編碼：
  T̂(ωⁱ) = T[i] for i = 0, 1, ..., m-1
  對於 i ≥ m，填充使度數 < n

步驟 3：約束違反檢驗
- 計算組合多項式：
  C(X) = Σᵢ qᵢ(X) × (T̂(X + dᵢ) - 約束值)
  
- 令 D(X) = C(X) / Z(X)
  其中 Z(X) = ∏ (X - cᵢ) 是零化多項式

步驟 4：FRI 承諾
- 對 D(X) 進行 FRI 協議
- 生成 DEEP 組合

步驟 5：Merkle 證明
- 將所有查詢值組織為 Merkle 樹
- 對每個查詢位置提供路徑證明

步驟 6：最終輸出
- 所有 Merkle 根
- 所有 Merkle 路徑
- FRI 協議的最後消息

證明大小分析：
假設：
- n = 2¹⁴ = 16,384（追蹤長度）
- d = 2¹⁰（查詢數量）
- k = log₂(n) = 14（FRI 輪數）

估計大小：
- Merkle 樹：O(n) 個 field elements
- 查詢路徑：O(d × log n) 個 field elements
- FRI 最後消息：O(n^(1/2)) 個 field elements

第五章：ZK Rollup 電路設計實例

5.1 餘額轉帳電路

讓我們設計一個 ZK Rollup 帳戶餘額轉帳的電路。

電路規範：

公開輸入：
- 區塊根 Root_before（舊狀態根）
- 區塊根 Root_after（新狀態根）

私密輸入（Witness）：
- 發送者公鑰 P_s
- 接收者公鑰 P_r
- 發送者餘額 B_s（轉帳前）
- 接收者餘額 B_r（轉帳前）
- 簽章 σ
- 隨機數 nonce_s

公開輸出：
- 轉帳金額 amount
- 手續費 fee

約束系統：

1. 簽章驗證
   - Verify_Schnorr(σ, P_s, tx_hash) = 1
   
   約束：
   - 根據所使用的簽章方案添加約束

2. 餘額約束
   - B_s_before ≥ amount + fee
   - B_r_before ≥ 0
   - B_s_after = B_s_before - amount - fee
   - B_r_after = B_r_before + amount

3. 狀態更新約束
   - 驗證發送者在原狀態中的餘額
   - 驗證接收者在原狀態中的餘額
   - 計算新狀態根

4. 非負性約束
   - B_s_after ≥ 0
   - B_r_after ≥ 0

R1CS 表示（簡化版本）：

變量：
v₀ = 1（常數）
v₁ = amount（公開）
v₂ = fee（公開）
v₃ = B_s_before
v₄ = B_r_before
v₅ = B_s_after
v₆ = B_r_after
v₇ = 簽章相關變量
...

約束：
(1) v₃ = amount + fee + v₅  // 發送者餘額守恆
(2) v₄ + amount = v₆           // 接收者餘額守恆
(3) v₅ × 1 = v₅               // 非負（需要特殊處理）
(4) v₆ × 1 = v₆               // 非負
(5) 簽章約束

5.2 Merkle 樹更新電路

狀態管理是 ZK Rollup 的核心，Merkle 樹更新約束是關鍵。

Merkle 樹約束：

參數：
- 樹深度 d = 30
- 每個節點為 32 bytes（以太坊）

輸入：
- 舊根 Root_old
- 新根 Root_new
- 路徑節點：sibling₀, sibling₁, ..., sibling_{d-1}
- 葉節點值：leaf

輸出：
- 驗證路徑正確性
- 驗證根更新正確性

約束：

1. 計算葉節點哈希
   leaf_hash = Hash(leaf)

2. 遞歸計算每層的父節點：
   設 path_bit₀, path_bit₁, ..., path_bit_{d-1} 為路徑位元
   
   對於 i = 0 到 d-1：
   若 path_bitᵢ = 0：
     parentᵢ = Hash(0 || nodeᵢ || siblingᵢ)
   若 path_bitᵢ = 1：
     parentᵢ = Hash(1 || siblingᵢ || nodeᵢ)
   
   其中 node₀ = leaf_hash
   nodeᵢ₊₁ = parentᵢ

3. 約束根匹配
   Root_new = node_d

4. 約束與原根的關係
   Root_old = recompute_root(leaf, path, path_bits)

電路複雜度：
- 每層需要 2 個哈希約束
- 總約束數：2 × d = 60 個哈希
- 以 Keccak-256 為例：~60 × 2700 = 162,000 個 R1CS 約束

優化策略：
- 使用 Poseidon 哈希（ZK-友好）
- 約束數量降至 ~60 × 30 = 1,800 個
- 節省約 90% 的約束

5.3 批量轉帳電路

批量轉帳電路設計：

目標：驗證 N 筆轉帳交易

電路參數：
- N = 最大交易數（如 1000）
- 每筆交易需要驗證簽章、更新餘額、更新 Merkle 樹

電路結構：

1. 交易驗證模組（重複 N 次）
   - 驗證簽章
   - 提取公鑰
   - 讀取餘額
   - 驗證餘額足夠

2. 餘額更新模組（重複 N 次）
   - 更新發送者餘額
   - 更新接收者餘額
   - 累積手續費

3. Merkle 樹更新模組（重複 N 次）
   - 更新葉節點
   - 重新計算路徑
   - 最終根計算

4. 聚合驗證
   - 驗證所有約束
   - 生成單個證明

約束數量估計：

假設：
- 每筆轉帳：簽章(3000) + 餘額更新(100) + Merkle(30) = ~3,130 約束
- 1000 筆轉帳：~3,130,000 約束

證明生成時間（使用高效 prover）：
- 假設每秒處理 10,000 約束
- 總時間：~5.2 分鐘

實際優化後（使用 Batch normalization）：
- 每筆轉帳：~500 約束
- 1000 筆轉帳：~500,000 約束
- 證明時間：~50 秒

5.4 zkEVM 電路設計

zkEVM 電路是用於驗證 EVM 執行正確性的零知識電路。

zkEVM 架構：

┌─────────────────────────────────────────────────────────────┐
│                     zkEVM Circuit Layer                     │
├──────────────┬──────────────┬──────────────┬────────────────┤
│  Bytecode    │   Execution   │   MIPS      │   State      │
│  Circuit     │   Trace       │   Trap      │   Update     │
│              │   Circuit     │   Circuit   │   Circuit    │
└──────────────┴──────────────┴──────────────┴────────────────┘

各層職責：

1. Bytecode Circuit
   - 驗證合約字節碼的正確性
   - 驗證程序計數器（PC）的有效性
   - 約束數量：~500,000

2. Execution Trace Circuit
   - 驗證 EVM 操作序列的正確性
   - 約束每個 opcode 的執行
   - 約束數量：取決於交易複雜度

3. MIPS Trap Circuit
   - 處理 precompile 調用
   - 處理系統合約
   - 約束數量：~200,000

4. State Update Circuit
   - 驗證狀態讀寫的正確性
   - 約束記憶體、堆疊、存儲
   - 約束數量：~1,000,000

EVM 操作約束示例：ADD 操作

opcode ADD：
- 功能：a + b = c (mod 2^256)
- gas_cost = 3

約束：
1. 讀取堆疊：pop a, pop b
2. 計算：c = a + b (mod 2^256)
3. 溢出標誌：overflow = (a + b) / 2^256
4. 寫入堆疊：push c
5. 扣除 Gas：gas' = gas - 3
6. PC 遞增：pc' = pc + 1

R1CS 表示：
constraint_1: (a + b) - c - overflow × 2^256 = 0
constraint_2: gas' + 3 - gas = 0
constraint_3: pc' - pc - 1 = 0

第六章：電路設計優化策略

6.1 約束優化技術

技術 1：複製約束減少

問題：大量相等約束導致約束數膨脹

解決方案：使用 PLONK 風格的複製約束
- 使用單個置換論證代替多個等式約束
- 節省：每個相等約束節省 1 個乘法約束

技術 2：查找表

問題：某些操作（如位運算）在 field 上代價高昂

解決方案：使用查找表
- 預先計算常用值
- 使用복數約束替代計算約束
- 節省：複雜操作可節省 50-90%

技術 3：自定義 Gate

問題：標準乘法/加法閘不夠靈活

解決方案：定義具有多個輸入的自定義閘
- 例：橢圓曲線加法閘
- 減少閘之間的連接數
- 節省：可減少 20-40% 的約束數

技術 4：批量歸一化

問題：中間變量增加約束數

解決方案：批量處理多個操作
- 減少中間變量數量
- 使用 SIMD 風格約束
- 節省：可減少 30-50% 的約束數

6.2 Prover 效率優化

技術 1：並列化

策略：
- 使用多核 CPU/GPU 並列計算約束多項式
- 使用 SIMD 指令加速 field 運算
- 對 independent 約束分組並行處理

收益：
- 8 核 CPU：~4-5x 加速
- 高端 GPU：~10-20x 加速

技術 2：快速 FFT

策略：
- 使用 FFT 進行多項式插值
- 使用混合基 FFT 優化
- 使用 Cooley-Tukey 演算法

收益：
- FFT 複雜度：O(n log n)
- 實例：n = 2²⁰，FFT 比直接計算快 ~1000x

技術 3：承諾優化

策略：
- 使用 Kate-Zaverucha-Goldberg (KZG) 承諾
- 使用 Batch 承諾減少通信開銷
- 使用 Vector 承諾優化存儲

收益：
- 承諾大小：恆定 ~48 bytes
- 承諾時間：O(n log n)

6.3 電路安全性審計

審計重點：

1. Soundness 漏洞
   - 約束系統是否完整
   - 是否存在繞過約束的方式
   
   檢查方法：
   - 窮舉測試小實例
   - 形式化驗證約束系統

2. Zero-Knowledge 泄露
   - Witness 是否被部分暴露
   - 約束是否泄露了私有資訊
   
   檢查方法：
   - 確認所有 witness 都在 commitment 中
   - 檢查是否存在「鬆弛」約束

3. 約束正確性
   - 約束是否正確實現所需功能
   - 是否存在溢位、精度丟失等問題
   
   檢查方法：
   - 符號執行約束系統
   - 對比參考實現

常見漏洞模式：

1. 缺少範圍約束
   問題：未限制變量取值範圍
   後果：可通過構造特殊輸入繞過約束
   
2. 複製約束不完整
   問題：某些相等關係未被約束
   後果：狀態不一致

3. 溢出未處理
   問題：field 運算結果可能溢出
   後果：結果錯誤

結論

本文從數學基礎出發，系統性地分析了 ZK Rollup 電路設計的核心原理與工程實踐。主要內容包括：

數學基礎：我們回顧了計算複雜度理論、NP 類問題、以及零知識證明的形式化定義，為理解電路設計提供了理論基礎。

代數電路與約束系統：詳細介紹了從布爾電路到算術電路的轉換、R1CS 約束系統、以及 PLONKish 電路的設計方法。

SNARK 系統：深入推導了 KZG 多項式承諾、Groth16 協議、以及 PLONK 協議的數學原理與實現細節。

STARK 系統：分析了 STARK 與 SNARK 的根本差異、FRI 協議的多項式交互式論證框架、以及 STARK 證明生成的完整流程。

實例設計：提供了餘額轉帳、Merkle 樹更新、批量轉帳、以及 zkEVM 電路的詳細設計範例。

優化策略：總結了約束優化、Prover 效率優化、以及電路安全性審計的最佳實踐。

參考來源

1. Gennaro, R., et al. "Quadratic Span Programs and Succinct NIZKs without PCPs." EUROCRYPT 2013.

1. Groth, J. "On the Size of Pairing-based Non-interactive Arguments." EUROCRYPT 2016.

1. Gabizon, A., et al. "PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge." EUROCRYPT 2020.

1. Ben-Sasson, E., et al. "STARKs: Low-degree testing in polynomial time and applications to STARK." IACR 2021.

1. Halo2 Specification. Zcash Foundation.

https://zcash.github.io/halo2/

1. zkEVM Specification. Ethereum Foundation.

https://github.com/privacy-scaling-explorations/zkevm-specs

1. Vitalik Buterin. "An approximate introduction to how zk-SNARKs are possible."

https://vitalik.ca/general/2021/01/26/snarks.html

標籤

zk-rollup, circuit-design, snark, stark, zk-snark, zk-stark, polynomial-commitment, halo2, plonk, cryptography

難度

advanced

相關文章

• ZK-SNARKs 與 ZK-STARKs 以太坊實戰應用完整指南
• Halo2 PLONK ZK 證明系統深度工程實作指南
• 以太坊零知識證明完整技術指南
• ZK 電路數學推導完整指南