ZK-SNARK 數學推導完整指南：從零知識證明到 Groth16、PLONK、STARK 系統的深度數學分析

概述

零知識證明（Zero-Knowledge Proof，ZKP）是現代密碼學最具革命性的創新之一，而 ZK-SNARK（Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge）則是其中最廣泛應用的構造方案。截至 2026 年第一季度，ZK-SNARK 已被廣泛部署於 zkRollup（zkSync Era、Starknet、Polygon zkEVM、Polgnolly）、隱私協議（Tornado Cash、Aztec、Railgun）、身份驗證系統等場景。

本文從數學基礎出發，完整推導 Groth16、PLONK 與 STARK 三大主流 ZK 系統的底層原理，涵蓋橢圓曲線密碼學、配對函數、多項式承諾、LPC 證明系統等核心技術，同時提供 Circom 與 Noir 電路開發的實戰程式碼範例。

第一章：密碼學基礎與數學框架

1.1 離散數學基礎

1.1.1 群論基本定義

零知識證明的數學根基建立在抽象代數之上。設 $(G, +)$ 為一個阿貝爾群（Abelian Group），滿足：

群公理

封閉性：$\forall a, b \in G: a + b \in G$

結合律：$\forall a, b, c \in G: (a + b) + c = a + (b + c)$

單位元：$\exists 0 \in G: \forall a \in G: a + 0 = 0 + a = a$

逆元：$\forall a \in G: \exists (-a) \in G: a + (-a) = (-a) + a = 0$

交換律：$\forall a, b \in G: a + b = b + a$

有限域（Finite Field）

有限域 $\mathbb{F}_p$（其中 $p$ 為質數）定義為：

• 加法運算封閉於 $\mathbb{F}_p$
• 乘法運算封閉於 $\mathbb{F}p^* = \mathbb{F}p \setminus \{0\}$
• 特性：$\forall a \in \mathbb{F}_p^*: a^{p-1} = 1 \mod p$（費馬小定理）

1.1.2 橢圓曲線密碼學

橢圓曲線 $E$ 定義於有限域 $\mathbb{F}_p$ 上：

$$E: y^2 = x^3 + ax + b \mod p$$

其中判別式 $\Delta = 4a^3 + 27b^2 \neq 0 \mod p$ 確保曲線無奇點。

群運算（Point Addition）

設 $P = (x1, y1)$、$Q = (x2, y2)$ 為曲線上兩點，$R = P + Q = (x3, y3)$：

當 $P \neq Q$（不同點相加）：

$$\lambda = \frac{y2 - y1}{x2 - x1} \mod p$$

$$x3 = \lambda^2 - x1 - x_2 \mod p$$

$$y3 = \lambda(x1 - x3) - y1 \mod p$$

當 $P = Q$（倍點運算）：

$$\lambda = \frac{3x1^2 + a}{2y1} \mod p$$

$$x3 = \lambda^2 - 2x1 \mod p$$

$$y3 = \lambda(x1 - x3) - y1 \mod p$$

橢圓曲線的階（Order）

曲線上的點集合 $E(\mathbb{F}p)$ 形成一個有限阿貝爾群，其階 $n = |E(\mathbb{F}p)|$。以太坊使用的 BN254 曲線定義如下：

1.2 雙線性配對函數

1.2.1 配對的數學定義

雙線性配對（Pairing）是 ZK-SNARK 的核心密碼原語。設 $G1$、$G2$ 為兩個 $n$ 階循環群，$G_T$ 為目標群，則 Tate 配對（或 Weil 配對）定義為：

$$e: G1 \times G2 \to G_T$$

雙線性特性

1. 雙線性：$\forall a, b \in \mathbb{Z}_n: e(aP, bQ) = e(P, Q)^{ab} = e(abP, Q) = e(P, abQ)$
2. 非退化性：$\exists P \in G1, Q \in G2: e(P, Q) \neq 1{GT}$
3. 可計算性：配對運算可在多項式時間內完成

1.2.2 配對在 ZK-SNARK 中的應用

驗證鑰嵌（Verification Key）結構

Groth16 系統中，驗證者需要檢查以下配對等式：

$$e(A, B) = e(\piA, \piB) \cdot e(\piC, \piD)$$

其中 $A, \piA \in G1$，$B, \piB \in G2$，這正是利用了配對的雙線性特性。

Miller 算法

配對計算的核心是 Miller 算法。對於點 $P \in G1$、$Q \in G2$，計算 $f_{P,Q}(Q)$ 的步驟：

def miller_loop(P, Q, n):
    """
    Miller 算法計算橢圓曲線配對
    
    參數:
        P: G1 群上的點
        Q: G2 群上的點
        n: 群的階
    
    返回:
        Miller 線性化結果
    """
    m = P  # 初始化為 P
    f = 1  # 累積因子初始化為 1
    
    # 二進制展開
    for i in range(log2(n), -1, -1):
        f = f * f * line_func(m, m, Q)  # 倍點線性函數
        m = m + m  # 倍點
        
        if (n >> i) & 1:  # 如果第 i 位為 1
            f = f * line_func(m, P, Q)  # 加點線性函數
            m = m + P  # 加點
    
    return f

1.3 密碼學假設

1.3.1 離散對數假設

離散對數問題（DLP）

給定有限域 $\mathbb{F}_p$ 上的生成元 $g$ 和元素 $h = g^x$，計算 $x$ 的難度即離散對數問題。

已知最佳演算法：通用生日攻擊 $O(\sqrt{n})$，Pollard's Kangaroo $O(\sqrt{n})$

橢圓曲線離散對數問題（ECDLP）

給定橢圓曲線 $E$ 上的生成元 $G$ 和點 $Q = xG$，計算 $x$ 的難度。

安全性：BN254 曲線使用 ~128 位的安全等級，相當於 RSA-3072。

1.3.2 配對友好曲線假設

Decisional Diffie-Hellman 假設（DDH）

在群 $G$ 中，給定 $(g, g^a, g^b, g^c)$，判斷 $c = ab \mod n$ 是否成立的難度。

然而，配對的存在使得 DDH 在配對友好曲線上不再成立：

$$e(g^a, g^b) = e(g, g)^{ab} = e(g^{ab}, g)$$

這是為何配對只能用於驗證而非重新加密。

1.3.3 ZK-SNARK 安全假設

第二章：Arithmetization 與電路設計

2.1 約束系統數學形式化

2.1.1 Rank-1 約束系統（R1CS）

約束系統是將計算轉換為代數約束的核心方法。R1CS（Rank-1 Constraint System）要求每個約束為以下形式：

$$\left(\sum{i=1}^{n} ai \cdot xi\right) \cdot \left(\sum{i=1}^{n} bi \cdot xi\right) = \sum{i=1}^{n} ci \cdot x_i$$

其中 $xi$ 為 wire（電線）變數，$ai, bi, ci$ 為係數。

矩陣表示

將所有約束堆疊為三個稀疏矩陣 $(A, B, C)$：

$$A \cdot \vec{x} \circ B \cdot \vec{x} = C \cdot \vec{x}$$

其中 $\circ$ 表示 Hadamard 乘積（逐元素乘積）。

約束數量複雜度

2.1.2 從計算到約束的轉換

範例：模擬 $y = x^2 + 3$

步驟 1：建立中間變數

s1 = x * x      // s1 = x^2
y  = s1 + 3     // y = x^2 + 3

步驟 2：轉換為 R1CS 約束

約束 1（乘法約束）：$s_1 \cdot 1 = x \cdot x$

約束 2（線性約束）：$y \cdot 1 = s_1 + 3$

在 R1CS 中寫為：

class R1CSConstraint:
    def __init__(self, A, B, C):
        """
        初始化 R1CS 約束
        
        參數:
            A, B, C: 稀疏向量，表示約束係數
        """
        self.A = A  # 左乘向量
        self.B = B  # 右乘向量  
        self.C = C  # 結果向量

# x^2 + 3 的約束
# 約束 1: x * x = s1
constraint1 = R1CSConstraint(
    A=[('x', 1)],      # x * 1
    B=[('x', 1)],      # x * 1
    C=[('s1', 1)]      # s1 * 1
)

# 約束 2: s1 + 3 = y
constraint2 = R1CSConstraint(
    A=[('s1', 1), ('one', 3)],  # s1 + 3
    B=[('one', 1)],             # 1
    C=[('y', 1)]                # y
)

2.2 多項式執行

2.2.1 QAP 轉換

將 R1CS 轉換為多項式執行（Polynomial Execution）的核心思想是：將離散的約束點「多項式化」。

拉格朗日插值法

给定 $n$ 個點 $(xi, yi)$，構造次數 $< n$ 的多項式 $P(x)$ 使得 $P(xi) = yi$：

$$P(x) = \sum{i=1}^{n} yi \cdot \prod{j \neq i} \frac{x - xj}{xi - xj}$$

從約束到多項式

設約束數量為 $m$，選擇點 $1, 2, \ldots, m+1$ 作為插值點。

對每個矩陣行 $k$：

$$Ak(x) = \text{interpolate}\left(\{(i, A{k,i})\}_{i=1}^{m+1}\right)$$

$$Bk(x) = \text{interpolate}\left(\{(i, B{k,i})\}_{i=1}^{m+1}\right)$$

$$Ck(x) = \text{interpolate}\left(\{(i, C{k,i})\}_{i=1}^{m+1}\right)$$

驗證者需要檢查：

$$H(x) \cdot Z(x) = A(x) \cdot B(x) - C(x)$$

其中：

$$A(x) = \sum{i=1}^{n} ai \cdot A_i(x)$$

$$B(x) = \sum{i=1}^{n} bi \cdot B_i(x)$$

$$C(x) = \sum{i=1}^{n} ci \cdot C_i(x)$$

$$Z(x) = \prod_{i=1}^{m}(x - i)$$

$$H(x) = \frac{A(x) \cdot B(x) - C(x)}{Z(x)}$$

2.2.2 約束系統複雜度分析

2.3 電路設計最佳實踐

2.3.1 約束優化策略

信號複製 vs 約束複製

約束複製：增加約束數量

// 約束複製示例
signal input a;
signal b <== a;  // 編譯為約束: a = b
signal c <== b;  // 編譯為約束: b = c
// 總共 2 個約束

信號複製：僅增加信號數量

// 信號複製示例
signal input a;
signal b <-- a;  // 無約束拷貝
signal c <-- b;   // 無約束拷貝
// 總共 0 個約束

查找表優化

對於非代數操作（如位運算），使用查找表可顯著減少約束數量：

template Xor3() {
    signal input a;
    signal input b;
    signal input c;
    signal output out;
    
    // 3-bit XOR 的查表實現
    // 比逐位 XOR 減少約束數量
    var lc1 = a + 2*b + 4*c;
    var lc2 = 1 + lc1;
    
    // 使用 Multiplexer 節省約束
    out <== (lc2)*(lc2 - 1)/2;
}

2.3.2 乘法深度優化

乘法深度影響了證明生成時間。優化策略包括：

平行化約束

// 原始：順序乘法，深度為 3
signal x1 <== a * b;
signal x2 <== x1 * c;
signal x3 <== x2 * d;

// 優化：並行乘法，深度為 1
signal t1 <== a * b;
signal t2 <== c * d;
signal x3 <== t1 * t2;

約束重寫

利用恆等式減少乘法：

// 原始：4 個乘法
// (a + b) * (c + d) = a*c + a*d + b*c + b*d

// 使用恆等式：3 個乘法
// (a + b) * (c + d) = (a + b)*c + (a + b)*d
signal sum1 <== a + b;
signal sum2 <== c + d;
signal t1 <== sum1 * sum2;  // 1 個乘法
// 但需要額外約束展開

第三章：Groth16 系統深度數學推導

3.1 Groth16 系統架構

Groth16 是 2016 年由 Jens Groth 提出的非互動式零知識論證系統，是目前最高效的 ZK-SNARK 構造之一。其核心思想是將 QAP 問題轉換為「知識假設」（Knowledge Assumption）。

3.1.1 系統參數

信任設置（Trusted Setup）

Groth16 需要一個「有毒廢物」（Toxic Waste）設置階段：

選擇隨機種子 $\tau \in \mathbb{F}_p$ 並保密。

計算 $\tau$ 的冪：

$$\tau^0, \tau^1, \tau^2, \ldots, \tau^{n+4}$$

其中 $n$ 為 QAP 約束數。

結構化參考字串（Structured Reference String, SRS）

$$\text{SRS} = \left(\frac{g^{\tau^i}}{g^{\alpha \tau^i}}{g^{\beta \tau^i}}{g^{\delta \tau^i}}\right)_{i=0}^{n}, \frac{g^{\alpha \cdot \delta \cdot \tau^i}}{\delta}$$

SRS 分為：

• 證明金鑰（Proving Key）：用於生成證明
• 驗證金鑰（Verification Key）：用於驗證證明

3.1.2 數學推導

步驟 1：約束多項式

設 QAP 產生的多項式為：

$$A(x) = \sum{i=0}^{n} ai \cdot \alpha_i(x)$$

$$B(x) = \sum{i=0}^{n} bi \cdot \beta_i(x)$$

$$C(x) = \sum{i=0}^{n} ci \cdot \gamma_i(x)$$

步驟 2：計算承諾

prover 計算：

$$A = \sum{i=0}^{n} ai \cdot G_i^{\alpha + \tau^i} = g^{\alpha \cdot A(\tau) + A(\tau) \cdot \tau}$$

$$B = \sum{i=0}^{n} bi \cdot H_i^{\beta + \delta \cdot \tau^i} = h^{\beta \cdot B(\tau) + B(\tau) \cdot \delta \cdot \tau}$$

$$C = \sum{i=0}^{n} ci \cdot G_i^{\delta \cdot \tau^i} = g^{\delta \cdot C(\tau)}$$

步驟 3：計算 $H$ 承諾

$$H(\tau) = \frac{A(\tau) \cdot B(\tau) - C(\tau)}{Z(\tau)}$$

其中 $Z(\tau) = \prod_{i=1}^{m}(\tau - i)$。

$$\pi_H = g^{\delta \cdot H(\tau)}$$

3.1.3 證明結構

Groth16 證明由三個群元素組成：

$$\pi = (\piA, \piB, \piC) \in G1 \times G2 \times G1$$

其中：

$$\piA = g^{\alpha + \sum{i=0}^{n} a_i \cdot \tau^i}$$

$$\piB = h^{\beta + \sum{i=0}^{n} b_i \cdot \tau^i}$$

$$\pi_C = g^{\frac{A(\tau) \cdot B(\tau) - C(\tau)}{Z(\tau)} \cdot \delta}$$

3.2 驗證過程數學推導

3.2.1 驗證等式推導

驗證者需要確認以下等式成立：

$$e(\piA, \piB) = e(g^{\alpha}, h^{\beta}) \cdot e\left(g^{\delta \cdot \frac{A(\tau) \cdot B(\tau) - C(\tau)}{Z(\tau)}}, h^{\delta}\right) \cdot e\left(\sum{i \in \text{input}} ai \cdot g^{\delta \cdot \gamma_i(\tau)}}, h^{\delta}\right)$$

展開左邊：

$$e(\piA, \piB) = e\left(g^{\alpha + A(\tau) \cdot \tau}, h^{\beta + B(\tau) \cdot \tau}\right)$$

利用配對雙線性：

$$= e(g, h)^{\alpha \cdot \beta} \cdot e(g, h)^{\alpha \cdot B(\tau) \cdot \tau} \cdot e(g, h)^{A(\tau) \cdot \tau \cdot \beta} \cdot e(g, h)^{A(\tau) \cdot B(\tau) \cdot \tau^2}$$

右邊：

$$= e(g, h)^{\alpha \cdot \beta} \cdot e(g, h)^{\delta \cdot \left(\frac{A(\tau) \cdot B(\tau) - C(\tau)}{Z(\tau)} + \sum{i \in \text{input}} ai \cdot \frac{\gamma_i(\tau)}{Z(\tau)}\right) \cdot \tau}$$

令 $\frac{Z(\tau)}{\tau^2} = \frac{\prod_{i=1}^{m}(\tau - i)}{\tau^2} \approx \tau^{m-2}$（當 $\tau$ 足夠大時）

最終驗證簡化為：

$$e(\piA, \piB) = e(g^{\alpha}, h^{\beta}) \cdot e(\piC, h^{\delta}) \cdot e(g^{\delta \cdot A{\text{pub}}(\tau)}, h^{\delta})$$

3.2.2 驗證算法實現

def groth16_verify(vk, pi, public_inputs):
    """
    Groth16 驗證算法
    
    參數:
        vk: 驗證金鑰
        pi: 證明 (A, B, C)
        public_inputs: 公開輸入
    
    返回:
        True 如果驗證通過，否則 False
    """
    # 計算公開輸入的多項式
    A_pub = sum(public_inputs[i] * vk.gamma_abc[i] for i in range(len(public_inputs)))
    
    # 驗證等式 1: e(A, B) = e(alpha, beta) * e(C, delta) * e(A_pub, delta)
    lhs = pairing(pi.A, pi.B)
    
    term1 = pairing(vk.alpha, vk.beta)
    term2 = pairing(pi.C, vk.delta)
    term3 = pairing(g ** A_pub, vk.delta)
    
    rhs = term1 * term2 * term3
    
    return lhs == rhs

def pairing(P, Q):
    """
    橢圓曲線 Tate 配對計算
    使用 Miller 算法優化實現
    """
    return miller_loop(P, Q, n)

3.3 Groth16 的複雜度分析

3.3.1 效率指標

3.3.2 安全性分析

知識 soundness

Groth16 的知識 soundness 基於 $q$-Slogan 假設：

给定 SRS 和挑戰 $c$，無法在不知道 witness 的情況下構造有效的證明。

零知識性

Groth16 通過引入隨機遮罩 $\rhoA, \rhoB, \rho_C$ 實現完美零知識：

$$\piA = g^{\alpha + A(\tau) + \rhoA \cdot \delta}$$

$$\piB = h^{\beta + B(\tau) + \rhoB \cdot \delta}$$

$$\piC = g^{C(\tau) + A(\tau) \cdot B(\tau) \cdot \rhoC + \rhoA \cdot \rhoB \cdot \delta - \rhoA \cdot B(\tau) - \rhoB \cdot A(\tau)}$$

第四章：PLONK 系統深度數學推導

4.1 PLONK 系統架構

PLONK（Permutations over Lagrange-bases for Oecumenical & Universal Non-interactive arguments of Knowledge）是由 Ariel Gabizon、Zachary Williamson 和 Oana Ciobotaru 於 2019 年提出的通用零知識證明系統。

4.1.1 核心創新

4.1.2 約束系統：Custom Gate + Copy Constraints

客製化門約束

PLONK 允許定義任意形狀的門約束：

$$qL \cdot a + qR \cdot b + qO \cdot c + qM \cdot a \cdot b + q_C = 0$$

其中 $q$ 為選擇器多項式（Selector Polynomials）。

拷貝約束（Copy Constraints）

拷貝約束通過置換論證（Permutation Argument）實現：

將所有 wire 標記為：

• $a_i$：左輸入
• $b_i$：右輸入
• $c_i$：輸出

拷貝約束要求 $wi = w{\sigma(i)}$ 對於置換 $\sigma$。

4.2 多項式承諾

4.2.1 KZG 承諾

KZG（Kate-Zaverucha-Goldberg）承諾是 PLONK 的核心組件。

承諾計算

给定多項式 $f(x) = \sum{i=0}^{d} fi \cdot x^i$，承諾為：

$$\text{comm}f = g^{f(\tau)} = \prod{i=0}^{d} (g^{\tau^i})^{f_i}$$

其中 $\tau$ 為 SRS 的秘密指數。

承諾者需要證明：

1. $f(s) = t$（evaluation proof）
2. $f$ 的次數 $\leq d$（degree bound）

4.2.2 開啟協議（Opening Protocol）

單點開啟

为了证明 $f(u) = v$，prover 計算：

$$h(x) = \frac{f(x) - f(u)}{x - u}$$

並開啟 $h$ 在 $\tau$ 處。

def kzg_open_commit(comm_f, f, u, v):
    """
    KZG 開啟協議
    
    參數:
        comm_f: f 的承諾
        f: 多項式函數
        u: 開啟點
        v: 期望值 f(u)
    
    返回:
        開啟證明 π
    """
    # 構造商多項式
    h_coeffs = divide_polynomials(f.coeffs, [1, -u])
    # h(x) = (f(x) - v) / (x - u)
    
    # 承諾 h
    pi = commit(h_coeffs)
    
    return pi

def kzg_verify_open(vk, comm_f, u, v, pi):
    """
    KZG 開啟驗證
    """
    # 驗證 e(comm_f / g^v, g) = e(pi, g^u / g)
    lhs = pairing(comm_f / g**v, g)
    rhs = pairing(pi, g**u)
    
    return lhs == rhs

4.3 PLONK 協議流程

4.3.1 協議步驟

設置階段

1. 選擇公開隨機點 $u \in \mathbb{F}_p$（challenge）
2. Prover 計算：

• 約束多項式 $a(x), b(x), c(x)$
• 選擇器多項式 $qL(x), qR(x), qO(x), qM(x), q_C(x)$
• 拷貝約束論證 $\pi_{\sigma}$

Commit 階段

Prover 對以下多項式進行承諾：

• $a(x), b(x), c(x)$
• $z(x)$（拷貝約束論證）
• $t(x)$（最終約束多項式）

驗證階段

驗證者檢查：

1. 拷貝約束：$z(\omega^i) \cdot z(\omega^{i+1}) = \text{relation}(a, b, c)$
2. 門約束：$qL a + qR b + qO c + qM a b + q_C = 0$
3. $t(x) = 0$ 在所有根處

4.3.2 數學推導

最終約束多項式

$$t(x) = \frac{(qL \cdot a + qR \cdot b + qO \cdot c + qM \cdot a \cdot b + qC) \cdot ZH(x)}{\prod_{i=1}^{n}(x - \omega^i)}$$

其中 $Z_H(x) = x^n - 1$。

Prover 計算

def plonk_prover(witness, circuit):
    """
    PLONK 證明生成
    
    參數:
        witness: 見證數據 (a, b, c)
        circuit: 電路描述
    """
    # 步驟 1: 計算約束多項式
    a_poly = evaluate_polynomial(witness.a)
    b_poly = evaluate_polynomial(witness.b)
    c_poly = evaluate_polynomial(witness.c)
    
    # 步驟 2: 拷貝約束論證
    z_poly = compute_copy_argument(witness, circuit.permutations)
    
    # 步驟 3: 計算目標多項式
    t_poly = compute_quotient(
        a_poly, b_poly, c_poly,
        circuit.selectors
    )
    
    # 步驟 4: 承諾所有多項式
    comm_a = kzg_commit(a_poly)
    comm_b = kzg_commit(b_poly)
    comm_c = kzg_commit(c_poly)
    comm_z = kzg_commit(z_poly)
    comm_t = kzg_commit(t_poly)
    
    return Proof(
        comm_a=comm_a,
        comm_b=comm_b,
        comm_c=comm_c,
        comm_z=comm_z,
        comm_t=comm_t,
        evaluations=[...]
    )

4.4 PLONK 的複雜度分析

4.4.1 效率指標

4.4.2 與 Groth16 的比較

第五章：STARK 系統深度數學推導

5.1 STARK 系統架構

STARK（Scalable Transparent Arguments of Knowledge）是由 Eli Ben-Sasson 等人於 2018 年提出的零知識證明系統，其最大特點是「透明設置」（Transparent Setup）——不需要信任設置。

5.1.1 核心特性

5.1.2 與 SNARK 的比較

5.2 FRI 協議

5.2.1 低度測試（Low-Degree Test）

STARK 的核心是 FRI（Fast Reed-Solomon Interactive Oracle Proof of Proximity）協議，用於測試多項式的度數。

Reed-Solomon 碼

给定多項式 $f(x)$ 在域 $\mathbb{F}$ 上，構造長度為 $n$ 的 Reed-Solomon 碼字：

$$\text{RS}(f) = (f(\omega^0), f(\omega^1), \ldots, f(\omega^{n-1}))$$

其中 $\omega$ 為 $n$ 階原根。

度數測試思想

若 $f$ 的次數 $< d$，則 $\text{RS}(f)$ 接近某個低次多項式。FRI 透過反覆折半查詢來驗證這個性質。

5.2.2 FRI 協議推導

步驟 1：初始度數測試

给定代碼字 $f0 = (f0[0], f0[1], \ldots, f0[n-1])$，其中 $n = 2^k$。

選擇隨機挑戰 $\alpha_0 \in \mathbb{F}$。

定義兩個折半多項式：

$$f1^{even}(x) = \frac{f0(x) + f_0(\gamma \cdot x)}{2}$$

$$f1^{odd}(x) = \frac{f0(x) - f_0(\gamma \cdot x)}{2 \cdot x}$$

其中 $\gamma$ 為固定常數（通常為費馬域中的平方根）。

步驟 2：遞歸

選擇 $f1$ 為 $f1^{even}$ 或 $f1^{odd}$，取決於隨機硬幣 $\beta0 \in \{0, 1\}$。

新的代碼字長度減少一半：$n_1 = n/2$。

重複步驟直到長度為 $m$（通常 $m = 128$ 或 $256$）。

步驟 3：最終測試

在最終層，驗證 $f_k$ 是否為低次多項式。

def fri_commit(f_0, num_queries=40):
    """
    FRI 承諾協議
    
    參數:
        f_0: 初始多項式代碼字
        num_queries: 查詢次數
    
    返回:
        承諾路徑和查詢證明
    """
    layers = [f_0]  # 儲存每層代碼字
    challenges = []  # 儲存隨機種子
    positions = []  # 儲存查詢位置
    
    n = len(f_0)
    k = int(math.log2(n))
    
    # 承諾階段
    for i in range(k):
        # 選擇查詢位置
        pos = random_position(n)
        positions.append(pos)
        
        # 計算下一層
        f_next = fri_fold(f_0, challenges[-1] if challenges else None)
        layers.append(f_next)
        
        n = n // 2
    
    # 查詢階段
    proofs = []
    for pos in positions:
        proof = extract_merkle_proof(layers, pos)
        proofs.append(proof)
    
    return FRIProof(layers, challenges, proofs)

def fri_fold(f, beta):
    """
    FRI 折半函數
    
    f_even = (f(x) + f(-x)) / 2
    f_odd  = (f(x) - f(-x)) / (2x)
    """
    n = len(f)
    f_even = [(f[i] + f[i ^ (n//2)]) // 2 for i in range(n//2)]
    f_odd = [(f[i] - f[i ^ (n//2)]) // (2 * i if i > 0 else 1) for i in range(n//2)]
    
    # 根據 beta 選擇
    return [f_even[i] + beta * f_odd[i] for i in range(n//2)]

5.3 STARK 約束與見證

5.3.1 約束系統

STARK 使用代數中間表示（Algebraic Intermediate Representation, AIR）。

約束定義

對於計算的每一步 $i$，定義約束：

$$Ci(f0[i], f1[i], \ldots, f{m-1}[i]) = 0$$

其中 $f_j$ 為追踪寄存器。

邊界約束

$$Bj(fj[0]) = \text{input}_j$$

$$B'j(fj[n]) = \text{output}_j$$

5.3.2 多項式化

將約束轉換為低次多項式：

轉換步驟

1. 定義約束多項式 $C(x0, x1, \ldots, x_{m-1})$
2. 構造複合多項式 $P(x) = C(f0(x), f1(\omega \cdot x), \ldots)$
3. 約束要求 $P(\omega^i) = 0$ 對所有 $i$

示例：Fibonacci 序列

追踪：$(f0[i], f1[i])$

約束：

• $f0[i+1] = f1[i]$
• $f1[i+1] = f0[i] + f_1[i]$

轉換為：

$$C(x, y) = (y - f0(\omega^{-1} \cdot x)) \cdot (x + y - f1(\omega^{-1} \cdot x))$$

5.4 STARK 完整協議

5.4.1 協議流程

┌─────────────────────────────────────────────────────────────────┐
│                      STARK 協議流程                              │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  1. Prover: 計算見證多項式 f_0, f_1, ..., f_{m-1}               │
│                                                                 │
│  2. Prover → Verifier: 發送 f_j 在 2^k 點上的值                 │
│     (使用 Merkle 樹組織)                                        │
│                                                                 │
│  3. Verifier → Prover: 發送隨機挑戰 r_0, r_1, ..., r_{k-1}     │
│                                                                 │
│  4. Prover: 計算約束多項式 C(x)                                │
│                                                                 │
│  5. Prover → Verifier: 執行 FRI 協議                           │
│     - 證明 C(x) 是低次的                                        │
│     - 邊界約束驗證                                              │
│                                                                 │
│  6. Verifier: 驗證 FRI 證明                                    │
│     - 查詢 Merkle 證明                                          │
│     - 驗證低次假設                                              │
│                                                                 │
│  7. Verifier: 輸出 accept/reject                              │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

5.4.2 安全性分析

訊息複雜度

$$O(n \cdot \log n) + O(k \cdot \log n)$$

其中 $n$ 為執行追蹤長度，$k$ 為 FRI 深度。

查詢複雜度

典型設定：$128$ 到 $256$ 次查詢

安全參數：$\lambda = 128$ bits

soundness 錯誤

$$\epsilon = \frac{1}{|\mathbb{F}|} + \frac{\delta^k}{q}$$

其中 $\delta$ 為接近性參數，$q$ 為查詢次數。

第六章：電路開發實戰

6.1 Circom 電路開發

6.1.1 Circom 語法與約束

Circom 是最廣泛使用的 ZK 電路描述語言。編譯器將 .circom 檔案轉換為 R1CS 約束系統。

// 範例：ZKP 身份驗證電路
pragma circom 2.0.0;

include "../circomlib/circuits/comparators.circom";

// 比較兩個輸入是否相等
template IsEqual() {
    signal input in[2];
    signal output out;
    
    // 輸出為 1 當且僅當 in[0] == in[1]
    component isz = IsZero();
    isz.in <== in[1] - in[0];
    out <== 1 - isz.out;
}

// 範圍檢查：確認輸入在 [0, 2^n) 範圍內
template RangeCheck(n) {
    signal input in;
    signal input max;
    
    component lessThan = LessThan(n);
    lessThan.in[0] <== in;
    lessThan.in[1] <== max;
    
    lessThan.out === 1;
}

// 主電路：多重身份驗證
template IdentityVerifier() {
    signal input age;
    signal input country;
    signal input salary;
    
    // 約束 1: 年齡 >= 18
    component ge18 = GreaterEqThan(32);
    ge18.in[0] <== age;
    ge18.in[1] <== 18;
    ge18.out === 1;
    
    // 約束 2: 國家為允許列表（假設 country 為 0-3）
    // 這個約束實際上不需要，因為 signal input 已經限制了範圍
    
    // 約束 3: 工資範圍檢查（防止過度暴露）
    component rangeCheck = RangeCheck(32);
    rangeCheck.in <== salary;
    rangeCheck.max <== 10000000;  // 最大 1000 萬
    
    // 約束 4: 複合條件
    // 輸出為 1 當且僅當 age >= 18 且 salary < 1000 萬
    component isValid = AND();
    isValid.a <== ge18.out;
    isValid.b <== rangeCheck.out;
}

template AND() {
    signal input a;
    signal input b;
    signal output out;
    
    out <== a * b;
}

template GreaterEqThan(n) {
    assert(n <= 252);
    signal input in[2];
    signal output out;
    
    component isz = IsZero();
    
    var e = in[0] - in[1];
    
    isz.in <== e;
    
    out <== 1 - isz.out;
}

6.1.2 約束優化實例

// 不良設計：約束爆炸
template BadDesign() {
    signal input a;
    signal input b;
    signal input c;
    signal input d;
    signal output out;
    
    // 4 個獨立的乘法約束
    signal t1 <== a * b;
    signal t2 <== c * d;
    signal t3 <== t1 * t2;
    signal t4 <== t3 * a;
    signal t5 <== t4 * b;
    signal t6 <== t5 * c;
    signal t7 <== t6 * d;
    
    out <== t7;
}

// 優化設計：最小化約束
template OptimizedDesign() {
    signal input a;
    signal input b;
    signal input c;
    signal input d;
    signal output out;
    
    // 只用 1 個乘法約束
    signal t <== a * b + c * d;
    
    // 輸出約束（不是乘法約束）
    out <== t;
}

6.2 Noir 電路開發

6.2.1 Noir 語法

Noir 是 Aztec 開發的 ZK-SNARK 語言，設計更加現代化。

// 範例：範圍證明電ircuit
use dep::std;

// 範圍證明函數
fn range_proof(private_value: Field, min: Field, max: Field) -> bool {
    // 使用 std::collections::range 庫
    let in_range = (private_value >= min) & (private_value <= max);
    in_range
}

// Pedersen 承諾
fn pedersen_commit(value: Field, randomness: Field) -> (Field, Field) {
    // 使用 Pedersen 承諾
    let commitment = std::hash::pedersen_hash([value, randomness]);
    (commitment, randomness)
}

// 範例：零知識餘額證明
struct BalanceProof {
    min_balance: Field,  // 最小餘額（隱藏）
    commitment: Field,    // 承諾
    range_proof: bool,   // 範圍證明
}

fn prove_balance(
    private_balance: Field,
    required_minimum: Field
) -> BalanceProof {
    // 生成隨機盲因子
    let randomness = std::random::new();
    
    // 計算 Pedersen 承諾
    let (commitment, _) = pedersen_commit(private_balance, randomness);
    
    // 生成範圍證明
    let range_ok = range_proof(private_balance, required_minimum, Field::max_value());
    
    BalanceProof {
        min_balance: required_minimum,  // 只暴露最小值
        commitment,
        range_proof: range_ok,
    }
}

// 驗證函數
fn verify_balance(proof: BalanceProof) -> bool {
    // 驗證範圍證明
    let range_valid = proof.range_proof;
    
    // 驗證承諾結構
    let commitment_valid = proof.commitment != Field::zero();
    
    range_valid & commitment_valid
}

6.2.2 複雜邏輯電路

// 範例：ZKP 拍賣系統
struct AuctionInput {
    private_bid: Field,      // 隱藏投標
    public_reserve: Field,   // 公開保留價
    auction_end: Field,      // 拍賣結束時間
}

struct AuctionOutput {
    winner_commitment: Field,
    winning_bid: Field,      // 只在拍賣結束後公開
    is_valid: bool,
}

fn verify_auction_bid(
    input: AuctionInput,
    current_time: Field,
    previous_winner: AuctionOutput
) -> AuctionOutput {
    // 約束 1: 投標時間有效
    let time_valid = current_time < input.auction_end;
    
    // 約束 2: 投標高於保留價
    let above_reserve = input.private_bid > input.public_reserve;
    
    // 約束 3: 投標高於前一個勝出者
    let higher_than_winner = input.private_bid > previous_winner.winning_bid;
    
    // 約束 4: 投標為正數
    let positive_bid = input.private_bid > 0;
    
    // 合併所有約束
    let all_constraints = time_valid & above_reserve & higher_than_winner & positive_bid;
    
    // 生成新的勝出者承諾
    let randomness = std::random::new();
    let (new_commitment, _) = pedersen_commit(input.private_bid, randomness);
    
    AuctionOutput {
        winner_commitment: new_commitment,
        winning_bid: input.private_bid,
        is_valid: all_constraints,
    }
}

第七章：信任設置與安全考量

7.1 信任設置機制

7.1.1 Groth16 的有毒廢物問題

Groth16 的信任設置需要生成「有毒廢物」——秘密隨機種子 $\tau$。如果攻擊者知道 $\tau$，他們可以偽造任意證明。

信任設置流程

class TrustedSetup:
    def __init__(self, n, curve='BN254'):
        """
        Groth16 信任設置
        
        參數:
            n: 約束數量
            curve: 橢圓曲線
        """
        # 選擇秘密隨機種子（必須在設置後銷毀）
        self.tau = Secrets.random(curve.p)  # 有毒廢物
        self.alpha = Secrets.random(curve.p)
        self.beta = Secrets.random(curve.p)
        self.gamma = Secrets.random(curve.p)
        self.delta = Secrets.random(curve.p)
        
        # 生成 SRS
        self.srs = self._generate_srs(n)
        
        # 銷毀有毒廢物
        self._toxic_waste_destroy()
    
    def _generate_srs(self, n):
        """
        生成結構化參考字串
        """
        g = curve.G1.generator()
        h = curve.G2.generator()
        
        srs_g = []
        srs_h = []
        
        for i in range(n + 5):
            srs_g.append(g ** (self.tau ** i))
            srs_h.append(h ** (self.tau ** i))
        
        # 添加 alpha、beta 項
        srs_alpha_g = [g ** (self.alpha * (self.tau ** i)) for i in range(n + 5)]
        srs_beta_g = [g ** (self.beta * (self.tau ** i)) for i in range(n + 5)]
        srs_beta_h = [h ** (self.beta * (self.tau ** i)) for i in range(n + 5)]
        
        return SRS(
            g=srs_g,
            h=srs_h,
            alpha_g=srs_alpha_g,
            beta_g=srs_beta_g,
            beta_h=srs_beta_h,
        )
    
    def _toxic_waste_destroy(self):
        """銷毀所有秘密值"""
        self.tau = None
        self.alpha = None
        self.beta = None
        self.gamma = None
        self.delta = None

7.1.2 多方計算（MPC）設置

為了解決有毒廢物問題，採用多方計算設置：

GG20 設置協議

每個參與者 $Pi$ 貢獻一個隨機值 $\taui$，最終的秘密為：

$$\tau = \sum{i=1}^{n} \taui$$

即使任何單一參與者無法獲得完整的 $\tau$，攻擊者需要腐化所有參與者才能恢復秘密。

class MPCSetup:
    def __init__(self, num_participants, n):
        self.participants = num_participants
        self.n = n
        self.contributions = []
        
    def contribute(self, participant_id, tau_i):
        """
        參與者貢獻隨機值
        """
        # 計算部分 SRS
        partial_srs = self._compute_partial_srs(tau_i)
        
        # 添加到貢獻列表
        self.contributions.append({
            'participant': participant_id,
            'srs': partial_srs
        })
        
        return partial_srs
    
    def aggregate(self):
        """
        聚合所有貢獻
        """
        # 乘積所有部分 SRS
        aggregated_srs = self._multiply_contributions()
        return aggregated_srs
    
    def verify_contribution(self, contribution):
        """
        驗證貢獻的有效性
        """
        # 確保貢獻不是單位元
        # 確保貢獻是正確形成的
        return True  # 簡化實現

7.2 安全最佳實踐

7.2.1 電路安全審計清單

7.2.2 常見漏洞與防範

約束遺漏

// 漏洞：缺少約束
template VulnerableMul() {
    signal input a;
    signal input b;
    signal output out;
    
    // 漏洞：out 沒有約束！
    out <== a;  // 應該是 out <== a * b
}

// 修復：添加完整約束
template SecureMul() {
    signal input a;
    signal input b;
    signal output out;
    
    out <== a * b;  // 這會生成完整的乘法約束
}

剩餘約束攻擊

某些構造會留下「剩餘空間」，允許攻擊者插入隱藏邏輯。

防範措施：使用統一的約束模板，審計每個門的約束。

結論

ZK-SNARK 數學推導的完整理解需要掌握密碼學、代數與電腦科學的多學科知識。本文從數學基礎出發，完整推導了 Groth16、PLONK 與 STARK 三大主流系統的核心原理。

關鍵要點回顧

未來發展方向

• 聚合證明：將多個證明聚合為單一證明（Proof Aggregation）
• **增量可驗證計算」（IVC）：支援遞歸電路
• **硬體加速`：GPU/FPGA 加速證明生成
• **形式化驗證`：數學證明電路正確性

掌握這些數學原理，是構建安全、高效 ZK 應用的基礎。

參考文獻

密碼學基礎

1. Groth, J. (2016). "On the Size of Pairing-based Non-interactive Arguments." EUROCRYPT 2016.
2. Kate, A., Zaverucha, G. M., & Goldberg, I. (2010). "Constant-Size Commitments to Polynomials and Their Applications." ASIACRYPT 2010.
3. Ben-Sasson, E., et al. (2018). "STARKs: Lagging Through the Complexity of the Check." IACR Cryptology ePrint Archive.

電路設計

1. Parno, B., Howell, J., Gentry, C., & Raykova, M. (2013). "Pinocchio: Nearly Practical Verifiable Computation." IEEE S&P 2013.
2. Wahby, R. S., et al. (2018). "Doubly-Efficient ZKSNARKs Without Trusted Setup." IEEE S&P 2018.

PLONK 系統

1. Gabizon, A., Williamson, Z. J., & Ciobotaru, O. (2019). "PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge." IACR Cryptology ePrint Archive.

實現與工具

1. Ethereum Foundation. "Circom Documentation." https://docs.circom.io
2. Aztec. "Noir Documentation." https://noir-lang.org
3. StarkWare Industries. "STARK Math." https://starkware.co