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

概述

零知識證明（Zero-Knowledge Proof）是現代密碼學最具革命性的技術之一，其中 ZK-SNARKs（Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge）與 ZK-STARKs（Zero-Knowledge Scalable Transparent Arguments of Knowledge）是區塊鏈領域最廣泛應用的兩大零知識證明系統。本文深入分析這兩種系統的數學推導與電路設計原理，為工程師提供從理論到實踐的完整技術指南。

ZK-SNARKs 以其簡潔的證明大小和快速驗證特性著稱，廣泛應用於 zkRollup、隱私保護、身份驗證等場景。ZK-STARKs 则以其透明性（無需可信設置）和量子抵抗特性脫穎而出，代表了零知識證明技術的未來發展方向。

第一章：密碼學基礎理論

1.1 離散對數問題

離散對數問題（Discrete Logarithm Problem, DLP）是 ZK-SNARKs 與 ZK-STARKs 安全的數學基石。設 $G$ 為一個有限循環群，階為 $q$（通常為大質數），$g$ 為群的生成元。對於給定的 $h \in G$，離散對數問題是找到唯一的整數 $x \in \mathbb{Z}_q$ 使得：

$$h = g^x$$

在傳統計算機上，解決離散對數問題的最好已知算法具有指數時間複雜度 $O(\sqrt{q})$，這使得在足夠大的有限域上，離散對數問題實際上是不可行的。這一假設构成了大多數零知識證明系統的安全性基礎。

橢圓曲線密碼學（Elliptic Curve Cryptography, ECC）是離散對數問題在區塊鏈中的實際應用場景。定義在有限域 $\mathbb{F}_p$ 上的橢圓曲線 $E$ 由以下方程給出：

$$y^2 = x^3 + ax + b \pmod{p}$$

其中 $4a^3 + 27b^2 \neq 0 \pmod{p}$ 確保曲線是非奇異的。曲線上的點集合，加上無窮遠點 $\mathcal{O}$，形成一個阿貝爾群，群的運算規則如下：

點加法：對於兩個不同的點 $P = (x1, y1)$ 和 $Q = (x2, y2)$，它們的和 $R = P + Q = (x3, y3)$ 由以下公式給出：

$$x3 = \lambda^2 - x1 - x_2 \pmod{p}$$

$$y3 = \lambda(x1 - x3) - y1 \pmod{p}$$

其中斜率 $\lambda$ 為：

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

倍點運算：當 $P = Q$ 時，使用以下公式：

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

$$x3 = \lambda^2 - 2x1 \pmod{p}$$

$$y3 = \lambda(x1 - x3) - y1 \pmod{p}$$

1.2 雙線性映射

雙線性映射（Bilinear Mapping）是 ZK-SNARKs 系統中的核心密碼學工具。設 $\mathbb{G}1$、$\mathbb{G}2$ 和 $\mathbb{G}T$ 為三個同構的循環群，階均為大質數 $p$。雙線性映射 $e: \mathbb{G}1 \times \mathbb{G}2 \rightarrow \mathbb{G}T$ 滿足以下性質：

雙線性：對於所有 $g1 \in \mathbb{G}1$、$g2 \in \mathbb{G}2$ 和 $a, b \in \mathbb{Z}_p$：

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

非退化性：如果 $g1$ 是 $\mathbb{G}1$ 的生成元，$g2$ 是 $\mathbb{G}2$ 的生成元，則 $e(g1, g2)$ 是 $\mathbb{G}_T$ 的生成元。

可計算性：存在有效算法計算 $e(g1, g2)$。

最常用的雙線性映射來自於配對密碼學（Pairing-based Cryptography），基於橢圓曲線上的 Weil 配對或 Tate 配對。對於一條橢圓曲線 $E/\mathbb{F}_p$，其 $r$ 撓曲群（ torsion subgroup）滿足配對的條件。

1.3 密碼學假設

ZK-SNARKs 的安全性基於以下幾個計算假設：

離散對數假設（DL假設）：給定 $g, g^x \in \mathbb{G}$，計算 $x$ 在計算上是不可行的。

指數假設（Exp假設）：給定 $g, g^x, g^{x^2}, \ldots, g^{x^d}$，計算 $g^{x^{d+1}}$ 在計算上是不可行的。

決策線性假設（DLIN假設）：給定均勻隨機的 $g^a, g^b, g^c, g^{ax}, g^{by}, g^{c(x+y)} \in \mathbb{G}$，判斷 $x+y=0$ 是否成立是困難的。

知識離散對數假設（KDLP）：這是 ZK-SNARKs 證明「知識」的核心假設。它聲稱對於任何能夠計算 $g^x$ 的算法，存在一個「提取器」可以輸出 $x$。

第二章：多項式承諾

2.1 KZG 多項式承諾

KZG（Kate-Zaverucha-Goldberg）多項式承諾是 ZK-SNARKs 中最廣泛使用的多項式承諾方案之一。它允許證明者對一個多項式 $f(x)$ 產生一個承諾，驗證者後續可以要求證明者在特定點 $z$ 的值 $f(z)$ 的正確性，同時確保證明者無法偽造答案。

設置階段：首先需要一個可信設置（Trusted Setup）來產生系統參數。設 $\tau$ 為一個隨機的秘密值（稱為「有毒廢料」，toxic waste），僅在設置期間存在，隨後必須被銷毀。系統參數包括：

$$g, g^\tau, g^{\tau^2}, \ldots, g^{\tau^d} \in \mathbb{G}_1$$

$$h, h^\tau, h^{\tau^2}, \ldots, h^{\tau^d} \in \mathbb{G}_2$$

其中 $g$ 和 $h$ 分別是 $\mathbb{G}1$ 和 $\mathbb{G}2$ 的生成元。

承諾階段：對於一個次數不超過 $d$ 的多項式 $f(x) = \sum{i=0}^{d} ai x^i$，其 KZG 承諾為：

$$C = g^{f(\tau)} = \prod{i=0}^{d} (g^{\tau^i})^{ai}$$

這個承諾是一個群元素，可以作為多項式的簡潔表示。

打開證明：要證明多項式 $f(z) = v$，證明者首先計算商多項式：

$$q(x) = \frac{f(x) - v}{x - z}$$

這是可行的，因為 $f(z) = v$ 意味著 $f(x) - v$ 可被 $(x - z)$ 整除。然後證明者計算 $q(x)$ 的承諾：

$$Q = g^{q(\tau)}$$

這個 $Q$ 就是打開證明。驗證者可以通過驗證以下等式來確認正確性：

$$e(C, h) = e(Q, h^{\tau - z}) \cdot e(g^v, h)$$

推導過程如下：

$$e(Q, h^{\tau - z}) \cdot e(g^v, h) = e(g^{q(\tau)}, h^{\tau - z}) \cdot e(g^v, h)$$

$$= e(g, h)^{q(\tau)(\tau - z) + v} = e(g, h)^{(f(\tau) - v)/(\tau - z) \cdot (\tau - z) + v}$$

$$= e(g, h)^{f(\tau)} = e(C, h)$$

2.2 批量開啟與聚合

KZG 承諾支持批量打開多個點，顯著提高效率。假設要證明多個點 $(z1, v1), (z2, v2), \ldots, (zk, vk)$，定義多項式：

$$I(x) = \prod{i=1}^{k} (x - zi)$$

$$h(x) = \sum{i=1}^{k} \frac{f(x) - vi}{x - zi} \cdot \frac{1}{\prod{j \neq i} (zi - zj)}$$

可以驗證 $h(zi) = \frac{f'(zi)}{\prod{j \neq i} (zi - z_j)}$，其中 $f'(x)$ 是 $f(x)$ 的導數。

2.3 透明設置方案

相對於 KZG 需要可信設置，Bulletproofs 和 FRI 等方案提供了透明設置（Transparent Setup），不需要可信的 CRS。FRI（Fast Reed-Solomon Interactive Oracle Proof of Proximity）協議是 ZK-STARKs 的核心組件，後續章節會詳細介紹。

第三章：約束系統與電路設計

3.1 R1CS 約束系統

R1CS（Rank-1 Constraint System）是將計算轉換為零知識證明最常用的中間表示形式。在 R1CS 中，每個計算步驟被表示為一組二次方程：

$$\langle \mathbf{a}i, \mathbf{z} \rangle \cdot \langle \mathbf{b}i, \mathbf{z} \rangle = \langle \mathbf{c}_i, \mathbf{z} \rangle \quad \forall i$$

其中 $\mathbf{z}$ 是包含所有輸入、輸出和中間變數的向量，$\mathbf{a}i$、$\mathbf{b}i$、$\mathbf{c}_i$ 是每個約束的係數向量。

電路轉換示例：以簡單的乘法電路 $c = a \times b$ 為例：

1. 引入中間變數 $w$ 表示乘積
2. 約束：$w = a \times b$
3. R1CS 形式：$(0 \cdot a + 1 \cdot w + 0 \cdot \text{others})^2 = (1 \cdot a + 0 \cdot w + 0 \cdot \text{others}) \cdot (0 \cdot a + 1 \cdot b + 0 \cdot \text{others})$

更複雜的電路可以透過組合多個 R1CS 約束來構建。典型的 ZK 電路可能包含數百萬個約束。

3.2 電路設計最佳實踐

變數優化：減少變數數量可以顯著降低電路規模。技巧包括：

• 合併冗餘計算
• 重用中間值
• 選擇適當的變數表示（例如，使用二進制表示還是一元表示）

約束優化：

• 避免過度約束
• 使用組合約束減少數量
• 選擇高效的密碼學原語

安全性考量：

• 確保電路正確性
• 防止側信道攻擊
• 驗證輸入範圍和有效性

3.3 Circom 電路範例

Circom 是最流行的 ZK 電路設計語言之一。以下是一個簡單範圍證明電路的實現：

pragma circom 2.0.0;

template RangeProof(n) {
    signal input in;
    signal input bit[n];
    signal output out;

    // 約束：bit 是二進制
    for (var i = 0; i < n; i++) {
        bit[i] * (1 - bit[i]) === 0;
    }

    // 約束：in = sum(bit[i] * 2^i)
    var sum = 0;
    for (var i = 0; i < n; i++) {
        sum += bit[i] * (1 << i);
    }
    in === sum;

    out <== 1;
}

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

這個電路證明輸入 in 可以用 8 位二進制表示，即 $0 \leq in < 256$。

第四章：Groth16 協議詳解

4.1 協議概述

Groth16 是由 Jens Groth 在 2016 年提出的一種 zk-SNARK 協議，至今仍是最廣泛使用的零知識證明方案之一。其名稱源於「非交互式」和「零知識」的組合特性。

Groth16 的核心特點包括：

• 極小的證明大小（僅 3 個群元素）
• 快速的驗證時間（僅需 2 個配對運算）
• 基於 QAP（Quadratic Arithmetic Program）轉換

4.2 數學推導

QAP 轉換：首先將計算問題轉換為 QAP。給定一個函數 $f: \mathbb{F}^np \rightarrow \mathbb{F}^mp$，目標是構造多項式組使得：

$$f(\mathbf{x}) = 0 \iff \exists \mathbf{z}: \bigcupi (Ai(\mathbf{z}) \cdot Bi(\mathbf{z}) - Ci(\mathbf{z}) = 0)$$

其中 $Ai(\mathbf{z})$、$Bi(\mathbf{z})$、$C_i(\mathbf{z})$ 是多項式。

可信設置：

1. 選擇隨機值 $\alpha, \beta, \delta, \gamma, \tau \in \mathbb{F}^*_p$
2. 計算 CRS：

$$\sigma = \left( \alpha, \beta, \delta, \gamma, \{ \tau^i \}{i=0}^{d}, \{ \beta \cdot Ai(\tau), \alpha \cdot Ai(\tau), Bi(\tau) \}{i=0}^{n}, \{ \frac{Ci(\tau)}{\delta} \}_{i=0}^{n} \right)$$

證明生成：

给定见证 $\mathbf{w}$（隱私輸入），計算：

1. $A = \alpha + \sum{i=0}^{n} ai \cdot A_i(\tau) + r \delta$
2. $B = \beta + \sum{i=0}^{n} ai \cdot B_i(\tau) + s \delta$
3. $h(\mathbf{x}) = \frac{\sum{i=0}^{n} ai \cdot Ai(\mathbf{x}) \cdot \sum{i=0}^{n} ai \cdot Bi(\mathbf{x}) - \sum{i=0}^{n} ai \cdot C_i(\mathbf{x})}{\delta}$
4. $H = h(\tau) + t \delta$
5. 最終證明 $\pi = (A, B, H)$

驗證過程：

$$e(A, B) = e(\alpha, \beta) \cdot e(\gamma, \frac{\sum{i \in I{pub}} ai \cdot Ci(\tau)}{\gamma}) \cdot e(\delta, H)$$

其中 $I_{pub}$ 是公開輸入的索引集合。

4.3 安全性分析

Groth16 的安全性基於以下假設：

• 離散對數假設：確保攻擊者無法從 CRS 中恢復秘密
• q-DLOG 假設：確保無法從承諾中提取多項式係數
• 知識soundness：透過提取器論證證明

知識 Soundness：如果驗證者接受一個證明，則存在一個提取器可以恢復對應的見證。這是透過模擬 CRS 和提取器技術來形式化證明的。

第五章：PLONK 協議與 Universal Setup

5.1 PLONK 協議概述

PLONK（Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge）是由 Gabizon、Williamson 和 Ciobotaru 於 2019 年提出的zk-SNARK 協議。其主要創新點包括：

• Universal Setup：只需一次可信設置，即可支持任意大小的電路
• 客製化門檻：允許設計特殊的密碼學門檻（如配對友好的橢圓曲線運算）
• 更簡單的結構：相比 Groth16，PLONK 具有更清晰的概念框架

5.2 協議詳解

電路表示：PLONK 使用「門」（gates）的概念，每個門定義輸入和輸出之間的關係。定義三種多項式：

• $q_L(x)$：左輸入選擇器
• $q_R(x)$：右輸入選擇器
• $q_M(x)$：乘法選擇器
• $q_O(x)$：輸出選擇器
• $q_C(x)$：常數項

門約束為：

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

其中 $a(x), b(x), c(x)$ 是表示電線值的拉格朗日多項式。

置換論證：PLONK 使用置換論證（Permutation Argument）來確保電線連接的正確性。這允許任意電路拓撲結構。

可信設置：

$$CRS = \left( g^{\tau^i}, g^{\alpha \tau^i}, g^{\beta \tau^i}, g^{\gamma \tau^i} \right)_{i=0}^{d}$$

5.3 PLONK 變體

TurboPLONK 和 UltraPLONK：引入更多客製化門檻，進一步優化特定運算的電路效率。

Sonic：PLONK 的前身，提供 universal setup 但效率較低。

Marlin：另一種 universal zk-SNARK，採用不同的多項式承諾方案。

第六章：FRI 協議與 ZK-STARKs

6.1 FRI 協議原理

FRI（Fast Reed-Solomon Interactive Oracle Proof of Proximity）協議是構建 ZK-STARKs 的核心組件。與需要可信設置的 KZG 不同，FRI 提供完全透明的設置。

核心思想：FRI 證明給定的向量 $f$ 接近於一個次數小於 $D$ 的多項式。驗證者並不需要讀取整個向量，而是透過隨機查詢和多項式折疊來高效驗證。

Oracle 設定：

1. 將向量 $f \in \mathbb{F}^{2^k}$ 視為在某個大域上的函數
2. 定義 $f$ 的 Reed-Solomon 編碼：$RS(f) = \text{Encode}(f)$，這是 $f$ 在更大域上的插值多項式

折疊階段：

1. 驗證者選擇隨機權重 $\alpha \in \mathbb{F}$
2. 證明者計算折疊後的向量：

$$f_1(i) = f(2i) + \alpha \cdot f(2i+1)$$

1. 遞迴地對 $f_1$ 重複過程，直到次數足夠小

驗證：最終驗證最后階段的多項式確實具有小次數，並沿著驗證路徑檢查折疊的正確性。

6.2 ZK-STARKs 架構

ZK-STARKs（Zero-Knowledge Scalable Transparent Arguments of Knowledge）由 Ben-Sasson、Goldreich、Hamburger、Pike、Ron-Zewi、Succinct 和 Tirazu 等人於 2018 年提出。

核心組成部分：

1. 代數中介表示（AIR）：將計算表示為代數中繼程式
2. 多項式 IOP：使用交互式 Oracle 證明協議
3. FRI：底層的多項式接近證明
4. Merkle 樹：用於 commitment 和隨機查詢

證明生成流程：

1. 將計算轉換為約束系統
2. 生成 Witness（滿足約束的秘密輸入）
3. 使用多項式承諾方案對 witness 進行承諾
4. 執行 FRI 協議證明多項式接近性
5. 生成最終的 STARK 證明

6.3 安全性與特性

透明性：ZK-STARKs 不需要可信設置，所有隨機性來自公開的隨機信標。這消除了「有毒廢料」的風險。

量子抵抗：FRI 和 STARK 的底層假設是 Reed-Solomon 編碼的解碼困難性，這被認為是量子抵抗的。

可擴展性：STARK 的驗證時間是對數級別的，適合大規模計算的驗證。

證明大小：STARK 證明比 SNARK 證明大，但隨著底層優化正在快速改進。

第七章：以太坊部署與實踐

7.1 驗證合約設計

在以太坊上部署 ZK 驗證合約需要特別注意 Gas 優化。以下是配對驗證的核心 Solidity 代碼：

// EVM 上的配對驗證優化實現
library Pairing {
    struct G1Point {
        uint256 X;
        uint256 Y;
    }
    
    struct G2Point {
        uint256[2] X;
        uint256[2] Y;
    }
    
    function neg(G1Point memory p) internal pure returns (G1Point memory) {
        return G1Point(p.X, uint256(0) - p.Y % SECP256K1_Q);
    }
    
    function addition(G1Point memory p1, G1Point memory p2) 
        internal view returns (G1Point memory) {
        uint256[3] memory input;
        input[0] = p1.X;
        input[1] = p1.Y;
        input[2] = p2.X;
        input[3] = p2.Y;
        
        uint256[2] memory result;
        assembly {
            if iszero(staticcall(sub(gas(), 2000), 7, input, 0x80, result, 0x40)) {
                revert(0, 0)
            }
        }
        return G1Point(result[0], result[1]);
    }
    
    function pairingCheck(G1Point[] memory p1, G2Point[] memory p2) 
        internal view returns (bool) {
        require(p1.length == p2.length);
        
        uint256[] memory input = new uint256[](p1.length * 6);
        
        for (uint i = 0; i < p1.length; i++) {
            input[i * 6 + 0] = p1[i].X;
            input[i * 6 + 1] = p1[i].Y;
            input[i * 6 + 2] = p2[i].X[1];
            input[i * 6 + 3] = p2[i].X[0];
            input[i * 6 + 4] = p2[i].Y[1];
            input[i * 6 + 5] = p2[i].Y[0];
        }
        
        uint256[1] memory result;
        assembly {
            if iszero(staticcall(sub(gas(), 2000), 8, input, mul(p1.length, 0xC0), result, 0x20)) {
                revert(0, 0)
            }
        }
        return result[0] == 1;
    }
}

7.2 Gas 優化策略

預編譯合約：以太坊提供了預編譯合約（Precompiled Contracts）用於橢圓曲線運算：

• 0x06: ecrecover（橢圓曲線簽名恢復）
• 0x07: SHA2-256 雜湊
• 0x08: RIPEMD-160 雜湊
• 0x09: 身份函數
• 0x05: 模指數運算
• 0x08-0x0a: BN128 配對

批量驗證：透過將多個證明批量驗證，可以顯著降低每個證明的平均 Gas 成本。

遞迴驗證：使用遞迴 STARK 可以在單次交易中驗證多個證明。

7.3 實際應用案例

zkRollup：ZK-Rollup 使用 ZK 證明來驗證 Layer 2 交易的正確性。典型實現包括：

• zkSync：使用 Plonky2（PLONK 的優化變體）
• StarkNet：使用 ZK-STARKs
• Polygon zkEVM：使用 zkSNARK
• Scroll：使用 zkEVM

隱私保護：AZTEC、zk.money 等項目使用 ZK 證明來實現隱私交易。

身份驗證：Quadrata、Worldcoin 等項目使用 ZK 證明實現身份認證。

第八章：性能優化與未來發展

8.1 證明生成優化

硬體加速：GPU 和 FPGA 可以加速 ZK 證明生成。主流實現包括：

• GPU 加速的 FFT
• 專用硬體加速器

並行化：將約束系統分解為可以並行處理的子系統。

承諾優化：使用不同的多項式承諾方案來平衡安全性和效率。

8.2 最新的 ZK 協議進展

Plonky2：由 Polygon Zero 開發，結合了 FRI 和 PLONK 的優勢，實現更快的證明生成。

Halo2：由 Electric Coin Company（Zcash 團隊）開發，使用遞迴組合來實現 universal setup。

Nova：使用折疊方案（folding scheme）來簡化遞迴證明。

Polynomial IOP：新的多項式 IOP 協議持續改進證明大小和驗證效率。

8.3 電路設計框架對比

結論

ZK-SNARKs 與 ZK-STARKs 代表了零知識證明技術的兩個重要發展方向。ZK-SNARKs 以其高效的驗證和簡潔的證明成為當前區塊鏈擴容的主流選擇，而 ZK-STARKs 以其透明性和量子抵抗特性代表著未來的發展趨勢。

理解這些技術的數學原理對於工程師設計和實現高效、安全的零知識應用至關重要。從離散對數問題到多項式承諾，從 R1CS 約束系統到具體的電路設計，每個環節都需要仔細考量安全性、效率和可用性之間的權衡。

隨著技術的持續發展，我們可以期待看到更多創新的 ZK 協議和更廣泛的實際應用場景。對於以太坊生態系統而言，ZK 技術將在 Layer 2 擴容、隱私保護和去中心化身份等領域發揮越來越重要的作用。

參考資源

• Groth, J. (2016). On the Size of Pairing-based Non-interactive Arguments.
• Kate, A., Zaverucha, G. M., & Goldberg, I. (2010). Constant-Size Commitments to Polynomials and Their Applications.
• Ben-Sasson, E., et al. (2018). STARKs: Transparent and Succinct Non-interactive Arguments of Knowledge.
• Gabizon, A., Williamson, Z. J., & Ciobotaru, O. (2019). PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge.
• Ethereum Foundation. (2026). EIP-196: Precompiled contracts for addition and scalar multiplication on the elliptic curve alt_bn128.