ZK-SNARKs 與 ZK-STARKs 數學推導與電路設計完整指南：從代數基礎到工程實現

概述

零知識證明（Zero-Knowledge Proof，ZKP）是現代密碼學最具革命性的技術之一，尤其在區塊鏈領域扮演著核心角色。ZK-SNARKs（Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge）和 ZK-STARKs（Zero-Knowledge Scalable Transparent Arguments of Knowledge）是兩種最廣泛應用的零知識證明系統。本文從工程師視角深入分析這兩種證明系統的數學推導、密碼學基礎、電路設計原理，以及在以太坊上的實際工程實現。透過本文，讀者將能夠理解零知識證明的深層數學原理，並掌握將這些技術應用於實際系統的能力。

零知識證明技術的發展正在重塑區塊鏈的多个面向：隱私保護、擴容驗證、計算完整性證明等。對於希望在這些領域深入的開發者和研究者而言，系統性地理解 ZK-SNARKs 和 ZK-STARKs 的數學基礎是必備的能力。本文將提供完整的數學推導，涵蓋從最基本的密碼學假設到完整的證明系統構造。

一、密碼學基礎理論

1.1 離散對數問題與雙線性映射

理解零知識證明的安全性需要首先掌握離散對數問題（Discrete Logarithm Problem）這一核心密碼學假設。

離散對數問題的數學定義：

令 G 為一個階為大質數 p 的循環群，g 為 G 的生成元。對於任意元素 h ∈ G，離散對數問題是找到唯一的整數 x ∈ Z_p，使得：

h = g^x (mod p)

離散對數問題的困難性體現在：已知 g、p 和 h，計算 x 在計算上是不可行的。對於傳統計算機，這種計算的複雜度 是指數級的；對於量子計算機，Shor 算法可以在多項式時間內解決這個問題，這也是後量子密碼學備受關注的原因。

雙線性映射（雙線性配對）：

雙線性映射是構建 ZK-SNARKs 的核心密碼學原語。設 G1、G2 和 GT 為三個相同階 p 的循環群。一個雙線性映射 e: G1 × G2 → GT 滿足以下特性：

雙線性（Bilinearity）：
對於所有 a, b ∈ Z_p 和所有 P ∈ G1, Q ∈ G2：
e(P^a, Q^b) = e(P, Q)^ab

非退化性（Non-degeneracy）：
如果 P 是 G1 的生成元，Q 是 G2 的生成元，
則 e(P, Q) 是 GT 的生成元（即 e(P, Q) ≠ 1）

可計算性（Computability）：
存在有效算法計算 e(P, Q) 對於所有 P ∈ G1, Q ∈ G2

在 ZK-SNARKs 中，最常用的配對基於橢圓曲線。BLS12-381 曲線是一個廣泛使用的選擇，其安全性相當於約 128 位對稱加密。

1.2 多項式承諾方案

多項式承諾（Polynomial Commitment）是 ZK-SNARKs 的核心組件，允許證明者對多項式做出承諾，而驗證者可以在之後驗證多項式在特定點的取值，而無需了解整個多項式。

Kate-Zaverucha-Goldberg（KZG）多項式承諾：

KZG 承諾是一種基於配對的承諾方案，其構造如下：

系統參數生成：
1. 選擇橢圓曲線 G1, G2，階為素數 p
2. 選擇生成元 g1 ∈ G1, g2 ∈ G2
3. 選擇秘密值 τ ∈ Z_p（來自可信設置）
4. 計算 Powers of Tau：g1^τ, g1^τ², ..., g1^τ^d
5. 發布承諾CRS（Common Reference String）

對多項式 f(x) = a₀ + a₁x + a₂x² + ... + a_d x^d 承諾：
C(f) = g1^{f(τ)} = g1^{a₀} × g1^{a₁τ} × ... × g1^{a_d τ^d}

驗證多項式在點 z 的取值 y = f(z)：
1. 證明者計算商多項式 q(x) = (f(x) - f(z)) / (x - z)
2. 證明者發布 π = g1^{q(τ)}
3. 驗證者檢查：e(C(f), g2) = e(π, g2^{τ} - g2^{z}) × e(g1^{f(z)}, g2)

KZG 承諾的關鍵特性是：承諾大小是 O(1)（一個橢圓曲線點），證明大小也是 O(1)，驗證只需要 O(1) 次配對運算。這使得 KZG 極其適合區塊鏈應用。

1.3 算術電路與約束系統

將計算問題轉換為零知識證明需要首先將計算錶述為算術電路或約束系統的形式。

算術電路的數學表示：

算術電路是由加法門和乘法門組成的有向無環圖。一個計算函數 f: F^n → F^m 可以表示為電路 C：

電路 C = (V, G, W)
其中：
- V = {v₁, ..., v_n, v_{n+1}, ..., v_{n+k}} 是變數集合
  （輸入變數 + 輸出變數）
- G = {g₁, ..., g_m} 是門集合
- W: G → V × V × V 指定每個門的輸入輸出

電路的計算：
每個門計算：
  v_out = v_in1 ⊕ v_in2 或 v_in1 ⊗ v_in2

R1CS（Rank-1 Constraint System）：

R1CS 是一種流行的約束表示方式，廣泛用於 ZK-SNARKs 電路設計。一個 R1CS 由三個向量 A、B、C 和一個解向量 Z 組成：

R1CS 約束條件：
<A, Z> · <B, Z> = <C, Z>

其中：
- Z = [1, w_1, w_2, ..., w_n] 是解向量
  （1 是常數項，w_i 是變數值）
- A, B, C 是係數矩陣

範例：z = x × y
設 Z = [1, x, y, z]

A = [0, 1, 0, 0]  // x · 1
B = [0, 0, 1, 0]  // y · 1
C = [0, 0, 0, 1]  // z · 1

驗證：
<A, Z> × <B, Z> = x × y = z = <C, Z>

R1CS 的優勢在於其簡潔性：每個約束只需要簡單的向量點積和乘法運算，非常適合在零知識證明中表述計算。

二、ZK-SNARKs 數學推導

2.1 Groth16 協議的完整推導

Groth16 是最廣泛使用的 ZK-SNARKs 協議之一，其安全性基於離散對數和配對的困難性。

協議設置階段：

Groth16 設置分為兩個階段：

階段一：結構化參考字串（SRS）生成
1. 選擇安全參數 λ
2. 生成素數階 p 的橢圓曲線群 G₁, G₂, G_T
3. 選擇秘密值 τ ∈ Z_p
4. 計算：
   α, β, δ, γ, τ ∈ Z_p^*
   α, β, δ, γ 必須獨立於 τ

5. 生成 G₁ 中的點：
   [α]_1 = α × G₁
   [β]_1 = β × G₁
   [δ]_1 = δ × G₁
   [τ^i]_1 = τ^i × G₁ for i = 0, ..., d

6. 生成 G₂ 中的點：
   [β]_2 = β × G₂
   [γ]_2 = γ × G₂
   [δ]_2 = δ × G₂
   [τ^i]_2 = τ^i × G₂ for i = 0, ..., d

階段二：電路特定設置
對於特定電路 C，計算：
   V_i = [τ^i]_1 for i = 0, ..., n  // 驗證key
   W_i = [τ^i]_1 for i = 0, ..., n  // 證明key
   [α]_1, [β]_1, [δ]_1, [γ]_2 等

證明生成過程：

輸入：
- 電路 C 的 R1CS 表示
- 私密輸入（witness）w = (x, a, b, ...)
- 證明密鑰 (PK)

證明步驟：
1. 計算 R1CS 解向量 Z = [1, x, w, ...]

2. 計算多項式：
   A(z) = Σ A_i(z) · Z_i
   B(z) = Σ B_i(z) · Z_i
   C(z) = Σ C_i(z) · Z_i
   
   其中 A_i, B_i, C_i 是 R1CS 矩陣對應的多項式

3. 確保約束滿足：
   計算 h(z) = A(z) × B(z) - C(z)
   h(z) 必須可以被 z × (z-1) × ... × (z-d) 整除
   
4. 計算商多項式：
   h(z) = t(z) × Z_H(z)
   其中 Z_H(z) = z^d - 1

5. 隨機盲化：
   選擇隨機數 r, s ∈ Z_p
   A' = A(r) + r·δ
   B' = B(s) + s·δ
   h' = h(r) + s·δ + r·s·δ

6. 計算承諾：
   π_A = [A']_1
   π_B = [B']_2
   π_C = [C']_1
   π_H = [h']_1
   π_K = [K(r, s)]_1  // 線性組合承諾

7. 最終證明：
   π = (π_A, π_B, π_C, π_H, π_K)

驗證過程：

輸入：
- 驗證密鑰 (VK)
- 公共輸入 x
- 證明 π

驗證步驟：
1. 計算驗證多項式在 τ 處的值：
   這需要配對運算來「打開」承諾

2. 配對驗證：
   e(π_A, π_B) = e([α]_1 + Σ x_i·[w_i]_1 + [δ]·π_H, [β]_2)
               × e([γ]^{-Σ x_i·[w_i]_1}, [δ]^{-1})
               × e(π_C, [1]_2)

3. 檢查約束：
   如果所有配對相等，則證明有效

驗證複雜度：
- 需要 3 次配對運算
- 配對運算時間約為 10-20ms（現代硬體）

2.2 PLONK 與 UltraPLONK 協議

PLONK（Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge）是一種通用的零知識證明協議，與 Groth16 相比具有更靈活的電路設計。

PLONK 的核心思想：

PLONK 與 Groth16 的主要區別：

1. 信任設置：
   Groth16: 電路特定，每次電路變更需要新設置
   PLONK: 通用設置，電路變更無需新設置

2. 約束表達：
   Groth16: 電路需要轉換為 R1CS
   PLONK: 電路使用自定義門約束，更加靈活

3. 多項式承諾：
   Groth16: KZG 承諾
   PLONK: 同樣使用 KZG，但增加了查找和排列約束

PLONK 的約束系統引入了「排列」（Permutation）約束，這使得電路設計更加直觀：

PLONK 約束系統：

門約束：
Q_L · a + Q_R · b + Q_O · c + Q_M · a·b + Q_C = 0

排列約束：
對於選擇器 σ，確保：
σ(a) = b, σ(b) = c, σ(c) = a
即 (a, b, c) 是 (σ(a), σ(b), σ(c)) 的一個排列

這些約束可以表達為：
(σ(x) - x) · (σ(y) - y) · (σ(z) - z) = 0

2.3 電路設計實踐

將實際計算轉換為零知識證明電路需要謹慎的電路設計。以下是以 zk-SNARK 電路設計常見的計算模式：

範例：範圍證明（Range Proof）：

範圍證明用於證明一個值落在特定範圍內，而不透露具體值。這在金融應用中非常常見。

範圍證明電路設計（以 8 位元為例）：

目標：證明 0 ≤ x < 256（即 x 可以用 8 位元表示）

電路約束：
1. 位元分解：
   x = Σ b_i · 2^i, 其中 b_i ∈ {0, 1}
   
   約束：b_i · (1 - b_i) = 0  // 每個 b_i 是二元值
   
2. 邊界證明：
   計算 x' = 255 - x
   
   約束：x' = Σ b'_i · 2^i  // x' 的位元分解
   
3. 最終約束：
   x + x' = 255  // 證明 x 在範圍內

資源消耗：
- 乘法門數量：~50 個
- 證明大小：~500 bytes
- 驗證時間：~5ms

範例：Merkle 樹驗證：

Merkle 樹驗證是零知識證明中最常見的電路之一，用於證明某個元素是 Merkle 樹的成員。

Merkle 樹驗證電路設計：

目標：證明 value 在 Root 為根的 Merkle 樹中

電路約束：
1. 路徑驗證：
   對於路徑上的每個節點：
   - 計算 hash(left || right)
   - 與下一層的節點比較
   
2. 雜湊約束：
   使用 Poseidon 或 Pedersen 雜湊函數
   約束：hash(input) = output

資源消耗（深度為 20 的 Merkle 樹）：
- 乘法門數量：~500 個
- 證明大小：~1 KB
- 證明時間：~30 秒（軟體實現）

三、ZK-STARKs 數學推導

3.1 STARKs 的核心優勢

ZK-STARKs 相較於 ZK-SNARKs 具有幾個關鍵優勢：

ZK-SNARKs vs ZK-STARKs 對比：

═══════════════════════════════════════════════════════════════════════
特性              ZK-SNARKs                ZK-STARKs
──────────────────────────────────────────────────────────────────────
可信設置          需要（Trusted Setup）      不需要
透明性            需要可信儀式              完全透明
密碼學假設        離散對數 + 配對           哈希函數
量子計算抗性      無                        有
證明大小          小（~200 bytes）          大（~100 KB）
驗證時間          快（~10ms）               較慢（~50ms）
證明生成          較快                     較慢
──────────────────────────────────────────────────────────────────────

ZK-STARKs 不需要可信設置的優勢使其更適合無法組織多方計算儀式的應用場景。其基於哈希函數的安全性假設也更為簡潔，減少了潜在的密碼學弱點。

3.2 FRI 協議詳細推導

FRI（Fast Reed-Solomon Interactive Oracle Proof of Proximity）是 STARKs 的核心組件，用於證明多項式的「接近性」。

FRI 協議的直覺解釋：

傳統多項式檢驗的問題：
- 驗證者需要讀取整個多項式：O(n) 複雜度
- 這對於大型多項式是不可行的

FRI 的解決方案：
1. 將多項式「折疊」成較小的多項式
2. 隨機選擇折疊點
3. 遞歸驗證折疊後的多項式
4. 最終只需要驗證一個小的多項式

FRI 協議的數學推導：

FRI 協議步驟：

1. 初始化：
   - 選擇代數碼 C = Reed-Solomon(FF, D, R)
   - D: 定義域（例如：所有 2^k 次單位根）
   - R: 恢復率（例如：4）
   - 多項式 f 的度 < |D|/R

2. 第一次折疊：
   - 證明者將 f(x) 拆分為偶數和奇數部分：
     f(x) = f_even(x²) + x · f_odd(x²)
     
   - 驗證者隨機選擇挑戰點 α₁ ∈ F
   - 證明者計算：
     f_1(x) = f_even(x) + α₁ · f_odd(x)
     
   - 注意：deg(f_1) < deg(f)/2

3. 遞歸步驟：
   對 i = 1, 2, ..., log(deg(f))：
   - 證明者將 f_i(x) 拆分為偶數/奇數部分
   - 驗證者選擇隨機挑戰 α_{i+1}
   - 證明者計算 f_{i+1}(x)
   - 證明者提交 f_{i+1} 的 commitments

4. 最終層：
   當 deg(f_k) 很小時（例如 < 16）
   - 證明者直接發布 f_k 的所有係數
   - 驗證者直接檢查

5. 正確性驗證：
   - 驗證者檢查每層的折疊一致性
   - 使用 Reed-Solomon 解碼器驗證「接近性」

FRI 的安全性證明：

FRI 安全性分析：

Soundness Error：
- 每輪選擇 α 的失敗概率：1/|F|
- 總失敗概率：< log(deg(f))/|F|
- 對於 |F| ≈ 2^256，soundness 錯誤可以忽略

Completeness：
- 對於正確的多項式，協議總是成功
- 證明者可以通過簡單計算完成每輪

提款攻擊防禦：
- 攻擊者需要預測所有隨機種子
- 概率：|F|^{-log(deg(f))} ≈ 2^{-256}

3.3 AIR（Algebraic Intermediate Representation）

AIR 是 StarkWare 開發的 STARK 電路表示方法，廣泛用於 Cairo 等語言中。

AIR 的約束定義：

AIR 約束表示：

過渡約束（Transition Constraints）：
- 定義狀態轉換的代數關係
- 形式：P(registers[i], registers[i+1]) = 0

邊界約束（Boundary Constraints）：
- 定義特定步驟的狀態要求
- 形式：constraint(registers[i]) = value

範例：簡單計數器

// 初始化
registers[0] = 0;

// 過渡約束
registers[1] = registers[0] + 1;

// 邊界約束
const STEPS = 100;
boundary(registers[STEPS]) = 100;

3.4 STARK 電路設計範例

以下是一個使用 AIR 設計的真實電路範例：zk-SNARK 驗證電路。

範例：驗證 Groth16 證明

AIR 約束設計：

1. 配對檢查約束：
   對於每個配對 e(A, B)：
   - 計算曲線運算 A + B
   - 驗證結果是否匹配目標

2. 多項式約束：
   對於電路中的每個門：
   - 表達為約束：Q_L · a + Q_R · b + Q_M · a·b + Q_O · c + Q_C = 0
   
3. 排列約束：
   確保變數正確排列
   σ(registers) = target

資源消耗（的真實 STARK 電路）：
- 追蹤數量：~1000
- 證明大小：~100-200 KB
- 證明時間：~2-5 分鐘（軟體）
- 驗證時間：~50ms

四、工程實現指南

4.1 Circom 電路開發

Circom 是最流行的 zk-SNARKs 電路編譯器之一，使用領域特定語言描述電路。

Circom 電路範例：範圍證明

pragma circom 2.0.0;

template RangeProof(nBits) {
    signal private input in;
    signal output out;
    
    // 位元分解
    component bits[nBits];
    for (var i = 0; i < nBits; i++) {
        bits[i] = IsZero();
        bits[i].in <-- (in >> i) & 1;
        
        // 約束每個位元為二元
        bits[i].out * (1 - bits[i].out) === 0;
    }
    
    // 重構數字
    signal sum;
    sum <== 0;
    for (var i = 0; i < nBits; i++) {
        sum += bits[i].out * (1 << i);
    }
    
    // 約束輸入等於重構值
    sum === in;
    
    // 輸出（可選）
    out <-- in;
}

component main {public [in]} = RangeProof(8);

4.2 Noir 語言框架

Noir 是 Aztec Network 開發的零知識證明語言，目標是簡化 zk-SNARKs 的開發。

Noir 電路範例：

fn main(
    secret x: Field,
    y: Field,
) -> pub Field {
    // 約束：x * x = y
    constrain x * x == y;
    
    // 範圍證明
    // Noir 內建範圍證明支持
    constrain x > 0;
    constrain x < 100;
    
    // 返回公開值
    y
}

// 編譯
// nargo compile

// 生成證明
// nargo prove

// 驗證證明
// nargo verify

4.3 以太坊上的實際部署

在以太坊上部署零知識證明電路需要考慮 Gas 成本優化。

以太坊上的證明驗證成本分析（2026 年）：

═══════════════════════════════════════════════════════════════════════
證明類型            驗證 Gas         部署 Gas        總成本
──────────────────────────────────────────────────────────────────────
Groth16             ~170,000        ~400,000        ~$3,000-5,000
PLONK (KZG)         ~200,000        ~350,000        ~$2,500-4,000
STARK               ~500,000+       ~1,000,000+     ~$10,000+
═══════════════════════════════════════════════════════════════════════

Solidity 驗證合約範例：

// Groth16 驗證器合約簡化版
contract Groth16Verifier {
    // 驗證函數
    function verify(
        uint256[2] memory a,
        uint256[2][2] memory b,
        uint256[2] memory c,
        uint256[2] memory input
    ) public view returns (bool) {
        // 配對驗證
        // 這是一個簡化的版本
        // 實際實現需要完整的預編譯合約調用
        
        uint256[24] memory inputPoints = [
            input[0], input[1],
            a[0], a[1], b[0][0], b[0][1],
            b[1][0], b[1][1], c[0], c[1],
            // ... 更多點
        ];
        
        // 調用 snarkv 預編譯合約
        // 0x06 是 BN254 配對地址
        return ICicleVerify.verify(a, b, c, input);
    }
}

4.4 性能優化策略

零知識證明生成是計算密集的任務，以下是常見的優化策略：

性能優化技術：

1. 電路優化：
   - 減少門數量
   - 優化約束表達
   - 使用高效密碼學原語

2. 證明系統選擇：
   - 選擇適合的證明系統
   - 考慮證明大小 vs 生成時間權衡

3. 硬體加速：
   - GPU 加速證明生成
   - FPGA/ASIC 專用晶片
   
4. 批量處理：
   - 批量驗證多個證明
   - 共享預計算

5. 遞歸證明：
   - 合併多個證明為一個
   - 減少驗證次數

五、應用場景分析

5.1 隱私交易

零知識證明最著名的應用是隱私交易，如 Tornado Cash 和 Aztec Network。

隱私交易協議設計：

存款流程：
1. 用戶生成隨機密鑰 sk
2. 計算承諾 C = hash(sk, secret)
3. 將 ETH 存入合約
4. 合約存儲 Commitment{C}

提款流程：
1. 用戶生成零知識證明
   - 證明知道 sk 使得 C 在 Merkle 樹中
   - 不透露具體是哪個 C
   
2. 提交提款請求 + 證明
3. 合約驗證證明
4. 驗證通過後，向新地址轉帳

安全性：
- 存款和提款之間的鏈接被切斷
- 監控者無法確定資金來源

5.2 ZK-Rollup 擴容

ZK-Rollup 使用零知識證明來驗證 L2 交易的正確性，實現區塊鏈擴容。

ZK-Rollup 架構：

L2 執行：
1. Sequencer 收集交易
2. 在 L2 VM 中執行交易
3. 計算新狀態根和證明
4. 將交易數據 + 證明提交到 L1

L1 驗證：
1. L1 合約驗證 ZK 證明
2. 驗證狀態轉換的有效性
3. 更新 L1 上的狀態根

資源效率：
- L1 只存儲：
  • 狀態根（32 bytes）
  • ZK 證明（~500 bytes）
  • 壓縮的交易數據
  
- L2 處理全部交易
- 成本分攤到所有交易

5.3 身份驗證

零知識證明可以用於構建安全的身份驗證系統。

ZK 身份驗證範例：

場景：證明年齡 ≥ 18 歲，而不透露具體年齡

電路設計：
1. 輸入：出生日期 timestamp
2. 計算：當前年份 - 出生年份 = 年齡
3. 約束：年齡 ≥ 18
4. 輸出：布爾值（true/false）

證明生成：
- 用戶端計算年齡
- 生成 ZK 證明年齡 ≥ 18
- 不透露實際年齡

驗證：
- 驗證者只檢查證明有效性
- 無法得知用戶具體年齡

六、結論與未來展望

ZK-SNARKs 和 ZK-STARKs 代表了零知識證明技術的兩個重要分支，各有其優勢和適用場景。ZK-SNARKs 提供了最小的證明大小和最快的驗證速度，適合區塊鏈上的驗證場景；ZK-STARKs 提供了透明性和量子計算抗性，適合對安全性有更高要求的應用。

隨著硬體加速技術的發展和證明系統的優化，零知識證明的應用將會更加普及。從隱私保護到區塊鏈擴容，從身份驗證到計算驗證，零知識證明正在成為區塊鏈技術棧中不可或缺的組成部分。

開發者和研究者應該持續關注這個快速發展的領域，特別是：

• 更高效的證明系統（如 Lasso、Jolt）
• 硬體加速技術
• 標準化和互操作性
• 與 AI 的結合（zkML）

參考資源

1. Groth, J. (2016). "On the Size of Pairing-based Non-interactive Arguments."
2. Ben-Sasson, E., et al. (2018). "STARKs: Validiating Data Availability and Computation."
3. Kate, A., Zaverucha, G., & Goldberg, I. (2010). "Constant-Size Commitments to Polynomials and Their Applications."
4. Gabizon, A., et al. (2019). "PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge."
5. Ethereum Foundation. (2026). "Zero-Knowledge Proofs Documentation."

風險聲明

本文僅供教育目的。零知識證明技術的實現涉及複雜的密碼學，實際應用前請諮詢專業安全審計。