零知識證明系統數學推導完整指南：從電路約束到 Kate 承諾的深度工程實踐

概述

零知識證明（Zero-Knowledge Proof，ZKP）是現代密碼學與區塊鏈技術中最具革命性的領域之一。在以太坊生態系統中，ZK-SNARKs 和 ZK-STARKs 已被廣泛應用於 Layer 2 擴容、隱私交易、身份驗證等場景。然而，要真正掌握這些技術的工程實踐，必須深入理解其底層的數學原理。

本文從電路約束系統的視角出發，系統性地推導 PLONK 和 Halo2 兩種主流 ZK 證明系統的核心算法。我們將涵蓋：

• 算術電路的表示與約束
• 多項式承諾與 Kate 承諾的代數結構
• 約束系統的矩陣表示與驗證
• 實際的 Solidity 驗證合約實現

這些內容對於理解 zkSync、Polygon zkEVM、Starknet 等主流 ZK Rollup 的技術原理至關重要。

第一章：算術電路與約束系統基礎

1.1 從計算到電路

零知識證明的第一步是將待證明的計算轉換為算術電路。算術電路由以下元素組成：

電路元件：

• 輸入線（Input Wires）：接收公開或私人輸入
• 乘法閘（Multiplication Gates）：執行乘法運算 $c = a \times b$
• 加法閘（Addition Gates）：執行加法運算 $c = a + b$
• 常量（Constants）：電路中的固定係數

約束類型：

在 PLONK 等通用約束系統中，主要使用兩類約束：

R1CS (Rank-1 Constraint System):
  - 形式: Q_L · a + Q_R · b + Q_O · c + Q_M · a · b = 0
  - 其中 Q_* 為係數向量

Gates:
  - 乘法約束: (a) × (b) - (c) = 0
  - 加法約束: (a) + (b) - (c) = 0
  - 線性約束: Q_L · a + Q_R · b + Q_O · c + Q_C = 0

1.2 約束系統的矩陣表示

令 $n$ 為電路中變量的數量（包括公開輸入、私人輸入和中間結果），$m$ 為約束的數量。

約束矩陣：

每個約束可以表示為一個三次多項式方程：

$$(ai) \cdot (bi) \cdot q{M,i} + (ai) \cdot q{L,i} + (bi) \cdot q{R,i} + (ci) \cdot q{O,i} + q{C,i} = 0$$

其中：

• $ai, bi, c_i$ 是第 $i$ 個約束中三條線的值
• $q{L,i}, q{R,i}, q{O,i}, q{M,i}, q_{C,i}$ 是該約束的係數

將所有約束堆疊，形成三個稀疏矩陣 $A, B, C \in \mathbb{F}^{m \times n}$ 和一個常數向量 $k \in \mathbb{F}^m$：

$$\begin{pmatrix} A \end{pmatrix}{i,j} \cdot xj + \begin{pmatrix} B \end{pmatrix}{i,j} \cdot xj + \begin{pmatrix} C \end{pmatrix}{i,j} \cdot xj + q_{C,i} = 0$$

1.3 電路到多項式的轉換

令 $\omega$ 為 $m$ 次單位根：$\omega^j$ 是 $m$ 個不同的值，滿足 $\omega^m = 1$。

拉格朗日基底：定義拉格朗日基多項式 $L_i(X)$：

$$Li(X) = \prod{j \neq i} \frac{X - \omega^j}{\omega^i - \omega^j}$$

性質：

$$L_i(\omega^j) = \begin{cases} 1 & \text{若 } i = j \\ 0 & \text{若 } i \neq j \end{cases}$$

將約束寫成多項式：令 $A(X), B(X), C(X)$ 為定義在 $\omega^0, \omega^1, ..., \omega^{m-1}$ 上的多項式：

$$A(X) = \sum{i=0}^{m-1} ai \cdot L_i(X)$$

類似的定義 $B(X), C(X)$。

約束條件可寫成：

$$qM(X) \cdot A(X) \cdot B(X) + qL(X) \cdot A(X) + qR(X) \cdot B(X) + qO(X) \cdot C(X) + q_C(X) = 0$$

在所有 $\omega^i$ 處取值均為零，因此存在商多項式 $H(X)$：

$$H(X) = \frac{qM(X) A(X) B(X) + qL(X) A(X) + qR(X) B(X) + qO(X) C(X) + qC(X)}{\prod{i=0}^{m-1} (X - \omega^i)}$$

第二章：多項式承諾系統

2.1 承諾的概念

多項式承諾允許證明者：

1. 對多項式 $f(X)$ 生成「承諾」$C$
2. 稍後「打開」承諾，證明 $f(z) = y$ 對某個 $z$ 成立

安全性要求：

• 隱藏性（Hiding）：承諾不洩露多項式資訊
• 約束性（Binding）：無法打開為不同的多項式或不同的值

2.2 Kate 承諾（KZG）

Kate 承諾是 Plonky、Plonk 等系統的基礎。其安全性基於 $q$-SDH（$q$-Strong Diffie-Hellman）假設。

可信設置（Trusted Setup）：

令 $\mathbb{G}$ 為橢圓曲線群，$G$ 為生成元。選擇秘密值 $\tau \in \mathbb{F}_p$（$p$ 為曲線階數）：

$$G0 = G, \quad G1 = \tau \cdot G, \quad G2 = \tau^2 \cdot G, \quad ..., \quad Gd = \tau^d \cdot G$$

公開參數：$\left([1]{\mathbb{G}}, [\tau]{\mathbb{G}}, [\tau^2]{\mathbb{G}}, ..., [\tau^d]{\mathbb{G}}\right)$

承諾計算：

對於多項式 $f(X) = \sum{i=0}^{d} fi \cdot X^i$：

$$\text{Commit}(f) = \sum{i=0}^{d} fi \cdot [\tau^i]{\mathbb{G}} = [f(\tau)]{\mathbb{G}}$$

這利用了指數的線性性：$f(\tau) = \sumi fi \tau^i$。

批量承諾優化：

由於 $\mathbb{G}$ 是加法群，可以對多個多項式批量承諾：

$$\text{Commit}(f1, f2, ..., fk) = \sumj \left(\sumi r{i,j} \cdot fi(\tau)\right) \cdot Gj$$

其中 $r_{i,j}$ 是隨機係數，用於維持隱藏性。

2.3 Kate 承諾的代數推導

承諾的性質證明：

令 $C = [f(\tau)]_{\mathbb{G}}$ 為對 $f(X)$ 的承諾。

要證明 $f(z) = y$：

1. 計算商多項式：$q(X) = \frac{f(X) - y}{X - z}$
2. 承諾 $q(X)$：$Q = [q(\tau)]_{\mathbb{G}}$
3. 驗證者檢查：$[f(\tau)]{\mathbb{G}} - y \cdot [1]{\mathbb{G}} = (\tau - z) \cdot Q$

驗證等式基於：

$$f(\tau) - y = (\tau - z) \cdot q(\tau)$$

這是代數基本定理的直接應用：如果 $f(z) = y$，則 $(X - z)$ 整除 $(f(X) - y)$。

2.4 Kate 承諾的 Solidity 實現

// Kate 承諾驗證合約（概念實現）

contract KZGVerifier {
    // 橢圓曲線參數（BN128）
    struct G1Point {
        uint256 x;
        uint256 y;
    }
    
    struct G2Point {
        uint256[2] x;
        uint256[2] y;
    }
    
    // 預編譯合約地址
    address constant PRECOMPILE_ADD = 0x06;
    address constant PRECOMPILE_MUL = 0x07;
    address constant PRECOMPILE_PAIRING = 0x08;
    
    // 驗證 Kate 承諾
    // 證明: f(z) = y given C = [f(τ)]
    function verifyKZGProof(
        G1Point memory commitment,    // C = [f(τ)]
        G1Point memory z_point,       // [z]
        G1Point memory y_point,       // [y]
        G1Point memory quotient,      // Q = [q(τ)]
        G2Point memory tau_minus_z    // [τ - z]_2
    ) internal view returns (bool) {
        // 驗證: e(C - y, [1]_2) = e(Q, [τ - z]_2)
        
        G1Point memory left = _pointSub(commitment, y_point);
        
        // 使用配對檢查
        // e(left, [1]_2) ?= e(quotient, tau_minus_z)
        return _pairingCheck(
            left.x, left.y,          // left = C - y
            tau_minus_z.x, tau_minus_z.y,  // right = τ - z
            quotient.x, quotient.y    // quotient = Q
        );
    }
    
    function _pairingCheck(
        uint256 a1x, uint256 a1y,
        uint256 a2x, uint256 a2y,
        uint256 b1x, uint256 b1y
    ) internal view returns (bool) {
        uint256[24] memory input;
        
        // G1 點
        input[0] = a1x;
        input[1] = a1y;
        
        // G2 點（τ - z）
        input[2] = a2x;
        input[3] = a2y;
        input[4] = a2x;  // 實際需要正確的 G2 座標
        input[5] = a2y;
        
        // 第二對
        input[6] = b1x;
        input[7] = b1y;
        input[8] = 0;    // [1]_2 的 x 座標
        input[9] = 0;    // [1]_2 的 y 座標
        input[10] = 0;
        input[11] = 0;
        input[12] = 0;
        input[13] = 0;
        input[14] = 0;
        input[15] = 0;
        input[16] = 0;
        input[17] = 0;
        input[18] = 0;
        input[19] = 0;
        input[20] = 0;
        input[21] = 0;
        input[22] = 0;
        input[23] = 0;
        
        uint256 gas = 100000;
        uint256 result;
        
        assembly {
            result := staticcall(gas, PRECOMPILE_PAIRING, input, 0x300, input, 0x20)
        }
        
        return result == 1;
    }
}

第三章：PLONK 約束系統深度解析

3.1 PLONK 的約束結構

PLONK（Permutation Arguments over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge）是一種通用的零知識證明系統，其約束結構如下：

約束類型：

1. 加法/乘法約束：標準的 R1CS 約束
2. 置換約束（Permutation）：驗證電線之間的連接關係
3. 公共輸入約束：將某些線標記為公開輸入

PLONK 約束方程：

$$(ai \cdot q{L,i} + bi \cdot q{R,i} + ci \cdot q{O,i}) \cdot q{M,i} + q{C,i} = 0$$

其中 $q_*$ 為選擇器多項式（Selector Polynomials），用於選擇在每個位置執行哪種約束。

3.2 置換論證（Permutation Argument）

PLONK 的核心創新是有效驗證電線之間的「連線」。這透過置換論證實現。

問題描述：

令 $\omega1, ..., \omegan$ 為 $n$ 個電路的「左輸入」位置，$\omega'1, ..., \omega'n$ 為對應的「右輸入」位置。

要證明：電線連接是正確的，即存在一個置換 $\sigma$ 使得每條左輸出連接到正確的右輸入。

Grand Product 論證：

定義累積多項式：

$$Z(X) = \prod{i=1}^{n} \frac{(X - \omegai)}{(X - \sigma(\omega_i))}$$

其中 $\sigma$ 是連接關係的置換。

性質：

$$Z(\sigma(\omegai)) = Z(\omegai) \cdot \frac{\omegai}{\sigma(\omegai)}$$

驗證者檢查：

1. $Z(1) = 1$
2. $Z(\omega_{n+1}) = 1$（封閉性）
3. 在每個 $\omega_i$ 處，$Z$ 的值正確遞增

3.3 PLONK 約束矩陣的實際構造

# PLONK 約束矩陣構造示例

class PLONKConstraintSystem:
    """
    PLONK 約束系統構造
    """
    
    def __init__(self, num_wires, num_constraints):
        self.n = num_wires
        self.m = num_constraints
        
        # 約束矩陣（稀疏表示）
        self.q_left = [0] * self.m   # Q_L
        self.q_right = [0] * self.m   # Q_R
        self.q_out = [0] * self.m    # Q_O
        self.q_mul = [0] * self.m    # Q_M
        self.q_const = [0] * self.m  # Q_C
        
        # 置換映射
        self.permutation = list(range(self.n))
        
        # 公開輸入
        self.public_inputs = []
    
    def add_constraint(self, idx, a, b, c, q_l=0, q_r=0, q_o=0, q_m=0, q_c=0):
        """
        添加約束: q_l * a + q_r * b + q_o * c + q_m * a * b + q_c = 0
        
        特殊情況：
        - 乘法: q_m = 1, q_l = q_r = q_o = q_c = 0
        - 加法: q_l = q_r = 1, q_o = -1, q_m = q_c = 0
        """
        self.q_left[idx] = q_l
        self.q_right[idx] = q_r
        self.q_out[idx] = q_o
        self.q_mul[idx] = q_m
        self.q_const[idx] = q_c
    
    def add_gate(self, idx, gate_type, wires):
        """
        添加標準門
        
        gate_type: 'mul', 'add', 'const'
        wires: (a, b, c) 三元組
        """
        a, b, c = wires
        
        if gate_type == 'mul':
            # 乘法約束: a * b - c = 0
            self.add_constraint(idx, a, b, c, q_m=1, q_o=-1)
        elif gate_type == 'add':
            # 加法約束: a + b - c = 0
            self.add_constraint(idx, a, b, c, q_l=1, q_r=1, q_o=-1)
        elif gate_type == 'const':
            # 常量約束: c - value = 0
            self.add_constraint(idx, a, b, c, q_l=1, q_o=-1)
    
    def set_permutation(self, mapping):
        """
        設置電線連接置換
        
        mapping[i] = j 表示第 i 條線連接到第 j 條線
        """
        assert len(mapping) == self.n
        self.permutation = mapping
    
    def to_polynomials(self):
        """
        將約束轉換為多項式
        """
        # 定義域（n 個元素）
        domain = [self.omega ** i for i in range(self.n)]
        
        # 插值約束係數為多項式
        self.Q_L = self._interpolate(self.q_left, domain)
        self.Q_R = self._interpolate(self.q_right, domain)
        self.Q_O = self._interpolate(self.q_out, domain)
        self.Q_M = self._interpolate(self.q_mul, domain)
        self.Q_C = self._interpolate(self.q_const, domain)
        
        # 插值置換為多項式
        self.sigma = self._interpolate(self.permutation, domain)
        
        return {
            'selectors': [self.Q_L, self.Q_R, self.Q_O, self.Q_M, self.Q_C],
            'permutation': self.sigma
        }
    
    def _interpolate(self, values, domain):
        """
        拉格朗日插值
        """
        n = len(domain)
        coeffs = [0] * n
        
        for i in range(n):
            # 計算拉格朗日基 L_i
            numerator = 1
            denominator = 1
            
            for j in range(n):
                if i != j:
                    numerator = multiply(numerator, self.omega ** (j if j < i else j))
                    denominator = multiply(denominator, domain[i] - domain[j])
            
            coeff = multiply(values[i], divide(numerator, denominator))
            coeffs[i] = coeff
        
        return coeffs

3.4 PLONK 證明流程

證明者視角：

PLONK 證明流程：

1. 電路翻譯
   - 將計算翻譯為約束
   - 構造約束矩陣 Q_*, σ

2. 見證賦值
   - 為所有電線賦值
   - 驗證所有約束滿足

3. 多項式承諾
   - 將約束和見證寫成多項式
   - 對所有多項式生成 Kate 承諾

4. 隨機挑戰
   - 接收驗證者的隨機挑戰 β, γ

5. 置換論證
   - 構造累積乘積 Z(X)
   - 承諾 Z(X)

6. 開放大挑戰點
   - 評估所有多項式在隨機點 ζ
   - 開啟對應承諾

7. 最終檢查
   - 驗證者使用配對檢查等式

驗證者視角：

class PLONKVerifier:
    """
    PLONK 驗證器
    """
    
    def __init__(self, crs):
        self.crs = crs  # 公共參考字符串
    
    def verify_proof(self, proof, public_inputs):
        """
        驗證 PLONK 證明
        """
        # 1. 解析承諾
        C_a, C_b, C_c = proof.commitments['wire']
        C_S1, C_S2, C_S3 = proof.commitments['selector']
        C_Z = proof.commitments['permutation']
        C_T = proof.commitments['quotient']
        
        # 2. 接收驗證者挑戰
        beta = proof.challenges['beta']
        gamma = proof.challenges['gamma']
        alpha = proof.challenges['alpha']
        zeta = proof.challenges['zeta']
        
        # 3. 計算線性組合
        # L(X) = (a + βX + γ)(b + βk₁X + γ)(c + βk₂X + γ)
        
        # 4. 驗證置換約束
        Z_alpha = self._evaluate_at(C_Z, zeta)
        Z_omega_alpha = self._evaluate_at(C_Z, zeta * omega)
        
        # 驗證: Z(ωζ) = Z(ζ) * (L(ζ) + γ) / (L(ωζ) + γ)
        L_zeta = self._compute_L(zeta, beta, gamma)
        L_omega_zeta = self._compute_L(zeta * omega, beta, gamma)
        
        expected_Z_omega = Z_alpha * L_zeta / L_omega_zeta
        
        assert Z_omega_zeta == expected_Z_omega, "Permutation check failed"
        
        # 5. 驗證約束方程
        # H(ζ) * Z(ζ) = (整數多項式約束)
        
        return True
    
    def _compute_L(self, x, beta, gamma):
        """
        計算線性組合 L(X)
        """
        # L(X) = (a + βX + γ)(b + βk₁X + γ)(c + βk₂X + γ)
        return (self.a_eval + beta * x + gamma) * \
               (self.b_eval + beta * self.k1 * x + gamma) * \
               (self.c_eval + beta * self.k2 * x + gamma)

第四章：Halo2 約束系統深度解析

4.1 Halo2 的創新設計

Halo2 是 Zcash 團隊開發的零知識證明系統，其核心創新包括：

1. 遞歸證明組合：無需可信設置
2. 查找表：原生支持電路查詢
3. 自引用約束：同一多項式可多次使用

4.2 配置（Configuration）與佈局（Layout）

Halo2 使用「虛擬機」風格的配置：

class Halo2Config:
    """
    Halo2 電路配置
    """
    
    def __init__(self, k, num_rows):
        self.k = k                    # 電路容量參數，2^k 行
        self.n = 2 ** k              # 總行數
        self.num_rows = num_rows     # 實際使用的行數
        self.num_advice = 3          # Advice 列數
        self.num_selector = 1        # 選擇器列數
        self.num_fixed = 2           # Fixed 列數
        
        # 列定義
        self.columns = {
            'advice': [f'advice_{i}' for i in range(self.num_advice)],
            'fixed': [f'fixed_{i}' for i in range(self.num_fixed)],
            'selector': [f'sel_{i}' for i in range(self.num_selector)],
            'instance': [],  # 公開輸入
            'equality': []   # 等式約束
        }
        
        # 排列（Permutation）
        self.permutation = PermutationConfig(
            cols=self.columns['advice'] + self.columns['fixed']
        )
        
        # 查找表
        self.lookups = []
    
    def add_lookup(self, input_exprs, table_exprs):
        """
        添加查找約束
        """
        self.lookups.append({
            'input': input_exprs,
            'table': table_exprs
        })

4.3 約束系統的 Halo2 表示

Halo2 的約束分為三類：

1. 門約束（Gate Constraints）：

每個「門」定義一個多項式約束：

class Gate:
    """
    Halo2 門定義
    """
    
    def __init__(self, name, polynomials, selectors):
        self.name = name
        self.polynomials = polynomials  # 約束多項式
        self.requiredSelectors = selectors  # 需要的選擇器
    
    def constraints(self, advice, fixed, selectors):
        """
        評估約束
        
        返回: 約束表達式列表
        """
        constraints = []
        
        for i, poly in enumerate(self.polynomials):
            if self.requiredSelectors[i]:
                # 只在選擇器為 1 時啟用
                selector = selectors[self.requiredSelectors[i]]
                constraints.append(poly(advice, fixed) * selector)
            else:
                constraints.append(poly(advice, fixed))
        
        return constraints

2. 排列約束（Permutation Constraints）：

確保某些列形成一個「排列」：

def permutation_argument(perm, cols):
    """
    排列論證
    
    確保 cols 中的值形成 perm 指定的排列
    """
    n = len(cols[0])
    
    # 1. 構造累積乘積
    Z = [1]  # Z[0] = 1
    for i in range(1, n + 1):
        numerator = 1
        denominator = 1
        for col in cols:
            numerator *= (f"alpha_{i}" - col[i-1])
            denominator *= (f"alpha_{i}" - col[perm[i-1]])
        Z.append(Z[-1] * numerator / denominator)
    
    # 2. 驗證 Z[n] = 1
    assert Z[n] == 1, "Permutation failed"
    
    # 3. 返回 Z(X) 和 Z(ωX)
    return Z

3. 查找約束（Lookup Constraints）：

def lookup_argument(input_values, table_values):
    """
    查找論證
    
    證明 input_values 中的每個值都在 table_values 中
    """
    n = len(input_values)
    m = len(table_values)
    
    # 1. 構造乘積
    # 對於每個 input[i]，找到對應的 table index
    
    # 2. 使用 "Vanishing Fragment" 技巧
    # 定義多項式 F(X) = ∏(X - table_j)
    # 對於 input[i]，F(input[i]) = 0
    
    # 3. 構造承諾
    return {
        'f_commit': commit(F),
        'table_commit': commit(table_values)
    }

4.4 Halo2 的遞歸證明

Halo2 的核心優勢是可以「證明證明」：

class RecursiveProof:
    """
    遞歸證明組合
    """
    
    def __init__(self, inner_circuit, outer_circuit):
        self.inner = inner_circuit
        self.outer = outer_circuit
    
    def create_recursive_proof(self, instance):
        """
        創建遞歸證明
        
        步驟：
        1. 為內部電路創建證明
        2. 將證明作為外部電路的 advice 輸入
        3. 驗證外部證明
        """
        # 步驟 1: 創建內部電路的證明
        inner_proof = self._prove_inner(instance)
        
        # 步驟 2: 準備外部電路的輸入
        # 內部電路的公開輸入，成為外部電路的實例列
        outer_instance = inner_proof.public_inputs
        
        # 內部電路的驗證鑰，作為外部電路的常量
        outer_constants = inner_proof.verification_key
        
        # 步驟 3: 創建外部電路
        outer_circuit = self._build_outer_circuit(
            instance=outer_instance,
            constants=outer_constants,
            advice=inner_proof.proof
        )
        
        # 步驟 4: 創建外部證明
        outer_proof = self._prove_outer(outer_circuit)
        
        return outer_proof
    
    def _build_outer_circuit(self, instance, constants, advice):
        """
        構建外部電路

        外部電路的職責是：
        1. 驗證 advice 是有效的內部證明
        2. 驗證內部公開輸入等於 instance
        """
        outer = Halo2Config(k=18, num_rows=65536)
        
        #advice 列用於存放內部證明
        outer.columns['advice'] = advice
        
        # 實例列存放內部公開輸入
        outer.columns['instance'] = instance
        
        # 固定列存放驗證鑰
        outer.columns['fixed'] = constants
        
        # 添加約束：驗證內部證明
        outer.add_gate('verify_inner_proof', 
                      polynomials=[
                          # 驗證advice 是有效的內部證明
                          verify_proof_constraint(advice, constants),
                          # 驗證實例匹配
                          instance[0] - advice.instance_hash
                      ],
                      selectors=[True, True])
        
        return outer

4.5 Halo2 與 PLONK 的比較

第五章：Kate 承諾的工程實現

5.1 預編譯合約介面

以太坊的 BN128 曲線預編譯合約支持 Kate 承諾的驗證：

// Kate 承諾驗證介面

interface IKZG {
    // 驗證多項式承諾
    function verifyKZGProof(
        bytes calldata proof,
        bytes calldata publicInputs
    ) external view returns (bool);
    
    // 批量驗證
    function verifyBatchKZGProof(
        bytes[] calldata proofs,
        bytes calldata publicInputs
    ) external view returns (bool);
}

// G1 點操作
library G1 {
    function pointToBytes(G1Point memory p) internal pure returns (bytes memory) {
        return abi.encodePacked(p.x, p.y);
    }
    
    function bytesToPoint(bytes memory b) internal pure returns (G1Point memory p) {
        require(b.length == 64);
        assembly {
            p.x := mload(add(b, 32))
            p.y := mload(add(b, 64))
        }
    }
    
    // 點加法
    function add(G1Point memory a, G1Point memory b) internal view returns (G1Point memory c) {
        uint256[4] memory input;
        input[0] = a.x;
        input[1] = a.y;
        input[2] = b.x;
        input[3] = b.y;
        
        uint256[2] memory result;
        
        assembly {
            if iszero(staticcall(sub(gas(), 2000), 0x06, input, 0x80, result, 0x40)) {
                revert(0, 0)
            }
            c.x := mload(result)
            c.y := mload(add(result, 32))
        }
    }
    
    // 標量乘法
    function mul(G1Point memory p, uint256 s) internal view returns (G1Point memory result) {
        uint256[2] memory input;
        input[0] = p.x;
        input[1] = p.y;
        
        uint256[2] memory output;
        
        assembly {
            if iszero(staticcall(sub(gas(), 2000), 0x07, input, 0x60, output, 0x40)) {
                revert(0, 0)
            }
            result.x := mload(output)
            result.y := mload(add(output, 32))
        }
    }
}

5.2 實際的 ZK 驗證合約

// 簡化版 PLONK 驗證合約

contract PLONKVerifier {
    using G1 for G1Point;
    
    // 驗證關鍵
    G1Point[] public powersOfTau;  // [τ^i] for i = 0..n
    G2Point public tauG2;           // [τ]_2
    G2Point public betaG2;          // [β]_2
    
    // 電路參數
    uint256 public n;                // 約束數量
    uint256 public numInputs;        // 公開輸入數量
    
    // 驗證函數
    function verify(
        // 承諾
        G1Point memory com_a,
        G1Point memory com_b,
        G1Point memory com_c,
        G1Point memory com_z,
        G1Point memory com_t,
        
        // 開啟值
        uint256[4] memory a_zeta,    // A(ζ), A(ωζ), B(ζ), B(ωζ)
        uint256[4] memory b_zeta,
        uint256 c_zeta,
        uint256 z_zeta,
        uint256 t_lo_zeta,
        uint256 t_mid_zeta,
        uint256 t_hi_zeta,
        
        // 公開輸入
        uint256[] memory inputs,
        
        // 驗證者挑戰
        uint256 beta,
        uint256 gamma,
        uint256 alpha,
        uint256 zeta,
        
        // 證明
        G1Point memory proof_z1,
        G1Point memory proof_z2
    ) public view returns (bool) {
        
        // 1. 驗證 Z(ζ) 的開啟
        require(verifyOpening(
            com_z, zeta, zeta * OMEGA, z_zeta, proof_z1, proof_z2
        ), "Z opening failed");
        
        // 2. 驗證 A, B, C 的開啟
        require(verifyOpening(
            com_a, zeta, zeta * OMEGA, a_zeta[0], proof_z1, proof_z2
        ), "A opening failed");
        
        require(verifyOpening(
            com_b, zeta, zeta * OMEGA, b_zeta[0], proof_z1, proof_z2
        ), "B opening failed");
        
        // 3. 計算約束方程左邊
        // L = (a + β·σ_a·X + γ)(b + β·σ_b·X + γ)(c + γ) - z(ωX)·(1 + γ) + ...
        
        // 4. 驗證商多項式
        uint256 t_zeta = t_lo_zeta + t_mid_zeta * zeta^n + t_hi_zeta * zeta^(2n);
        uint256 zeta_n = pow(zeta, n);
        
        // 約束多項式應該整除 t(X)
        uint256 lhs = computeConstraintLHS(a_zeta, b_zeta, c_zeta, z_zeta, beta, gamma, alpha, zeta);
        
        uint256 rhs = t_zeta * denominator(zeta, n);
        
        require(lhs == rhs, "Constraint check failed");
        
        // 5. 驗證公共輸入
        for (uint i = 0; i < numInputs; i++) {
            require(inputs[i] == a_zeta[i], "Public input mismatch");
        }
        
        return true;
    }
    
    function verifyOpening(
        G1Point memory com,
        uint256 x,
        uint256 x_omega,
        uint256 value,
        G1Point memory proof_l,
        G1Point memory proof_r
    ) internal view returns (bool) {
        // 驗證 e(C - [v], [1]_2) = e([d], [τ - x]_2)
        
        G1Point memory left = G1.sub(com, G1.mul(G1.Generator(), value));
        
        // 使用配對檢查
        return pairingCheck(
            left,                // C - [v]
            tauG2.x, tauG2.y,    // [τ]
            proof_l,             // [d]
            x                    // x
        );
    }
    
    function computeConstraintLHS(
        uint256[4] memory a_vals,
        uint256[4] memory b_vals,
        uint256 c_zeta,
        uint256 z_zeta,
        uint256 beta,
        uint256 gamma,
        uint256 alpha,
        uint256 zeta
    ) internal pure returns (uint256) {
        // 計算 (a + β·σ_a·X + γ)(b + β·σ_b·X + γ)(c + γ)
        uint256 sigma_a = 1;  // 實際需要電路特定的 σ_a
        uint256 sigma_b = 1;  // 實際需要電路特定的 σ_b
        
        uint256 term1 = (a_vals[0] + beta * sigma_a * zeta + gamma) % FIELD;
        uint256 term2 = (b_vals[0] + beta * sigma_b * zeta + gamma) % FIELD;
        uint256 term3 = (c_zeta + gamma) % FIELD;
        
        uint256 product = term1 * term2 % FIELD;
        product = product * term3 % FIELD;
        
        // 加上 z(ωζ) 項和 alpha 因子
        uint256 z_omega_zeta = 1;  // 實際需要計算
        uint256 term4 = z_omega_zeta * (1 + gamma) % FIELD;
        
        return (product - term4) % FIELD;
    }
}

第六章：實際應用案例

6.1 zkSync Era 的電路設計

zkSync Era 使用類似 PLONK 的約束系統，其電路結構如下：

// zkSync 風格的電路約束示例

contract ZKSyncRAM {
    /*
     * 簡化的 RAM 讀寫電路
     * 證明：正確執行了 memory read/write 操作
     */
    
    // 狀態
    uint256 public pc;           // 程序計數器
    uint256 public memorySize;   // 內存大小
    
    // Witness 結構
    struct Witness {
        uint256[] readAddresses;
        uint256[] readValues;
        uint256[] writeAddresses;
        uint256[] writeValues;
        uint256[] readMasks;      // 標識每個週期是否為讀操作
    }
    
    // 約束：內存讀操作的一致性
    function constrainMemoryConsistency(Witness memory w) internal pure {
        uint256 n = w.readAddresses.length;
        
        for (uint i = 0; i < n; i++) {
            if (w.readMasks[i] == 1) {
                // 讀取的地址必須在有效範圍內
                assert(w.readAddresses[i] < memorySize);
                
                // 找到最近的寫入值
                uint256 lastWrite = 0;
                for (uint j = 0; j < i; j++) {
                    if (w.writeAddresses[j] == w.readAddresses[i]) {
                        lastWrite = w.writeValues[j];
                    }
                }
                
                // 讀取值必須等於最後寫入的值
                assert(w.readValues[i] == lastWrite);
            }
        }
    }
    
    // 約束：寫操作的地址有效性
    function constrainWriteOperation(Witness memory w) internal pure {
        for (uint i = 0; i < w.writeAddresses.length; i++) {
            // 寫入地址必須有效
            assert(w.writeAddresses[i] < memorySize);
            
            // 不能寫入到代碼區域
            assert(w.writeAddresses[i] >= CODE_SIZE);
        }
    }
}

6.2 Starknet 的 AIR 約束

Starknet 使用代數中間表示（AIR），其約束定義如下：

# Starknet AIR 約束示例

class StarknetAIR:
    """
    Starknet 的代數中間表示約束
    """
    
    def __init__(self, trace_length):
        self.trace_length = trace_length
        self.constraints = []
    
    def add_constraint(self, name, expr):
        """
        添加約束
        
        expr: 表達式，可以是：
        - f(next_trace, current_trace, public_input) = 0
        - f(next_trace, current_trace) = f(next_trace', current_trace')
        """
        self.constraints.append({
            'name': name,
            'expression': expr
        })
    
    def build_quotient_polynomial(self):
        """
        構造商多項式
        
        約束: g_i(trace) = 0 for all i
        
        商多項式: Q(X) = ∏ g_i(X) / Z(X)
        
        其中 Z(X) = X^n - 1 是消失多項式
        """
        Q = 1
        for constraint in self.constraints:
            g = constraint['expression']
            Q = Q * g
        
        # 除以消失多項式
        Z = self._vanishing_polynomial()
        return Q / Z
    
    def generate_fri_layers(self, polynomial):
        """
        生成 FRI 證明層
        """
        layers = [polynomial]
        
        while len(layers[-1]) > 2:
            # 選擇下一層的分支點
            beta = self._sample_challenge()
            
            # 壓縮：f_even(X^2) + beta * f_odd(X^2)
            current = layers[-1]
            even = current[0::2]  # 偶數項
            odd = current[1::2]   # 奇數項
            
            next_layer = [even[i] + beta * odd[i] for i in range(len(even))]
            layers.append(next_layer)
        
        return layers
    
    def verify_fri_proof(self, proof, challenges):
        """
        驗證 FRI 證明
        """
        # 最後一層應該是簡單的
        last_layer = proof[-1]
        assert len(last_layer) <= 2
        
        # 驗證最後一層是低次多項式
        final_value = evaluate_at_merkle_commitment(last_layer, challenges[-1])
        
        # 向前驗證每層
        for i in reversed(range(len(proof) - 1)):
            expected = proof[i + 1]
            claimed = self._fold_layer(proof[i], challenges[i])
            
            assert expected == claimed
        
        return True

結論

零知識證明系統的數學基礎構成了現代區塊鏈隱私和擴容技術的基石。透過本文的深度分析，我們涵蓋了：

1. 算術電路與約束系統：將計算問題轉換為多項式約束
2. 多項式承諾與 Kate 承諾：提供可驗證的多項式承諾機制
3. PLONK 約束系統：通用零知識證明的約束表達
4. Halo2 約束系統：支持遞歸證明和查找表的創新設計
5. 工程實現：從 Solidity 驗證合約到實際應用案例

這些技術的持續演進正在推動 zkEVM、ZK Rollup 和隱私保護應用的快速發展。理解這些底層原理對於構建安全、高效的 ZK 應用至關重要。

參考資源：

1. Kate, Zaverucha, Goldberg - "Constant-Size Commitments to Polynomials and Their Applications"
2. Gabizon, Williamson, Ciobotaru - "PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge"
3. Zcash Halo2 Design Documentation
4. Ethereum Foundation - "ZK EVM Documentation"
5. StarkWare - "STARK Math"

代碼參考：

1. matter-labs/zksync (zkSync Era)
2. 0xPolygonZero/plonky2 (Polygon zkEVM)
3. matter-labs/era-boojum (Bojum prover)