PLONK 與 Halo2 約束系統完整數學推導指南：從代數基礎到電路設計的深度實作

概述

PLONK（Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge）和 Halo2 是當代零知識證明領域最重要的兩個證明系統。PLONK 由 Aztec Network 團隊於 2020 年提出，採用通用可信設置（Universal Trusted Setup）設計，大幅簡化了電路部署流程。Halo2 由 Zcash 團隊開發，採用遞歸證明（Recursive Proof）架構，無需可信設置即可實現高效的證明聚合。這兩個系統已被廣泛應用於以太坊 Layer 2（zkSync Era、Aztec）、隱私協議（Aztec Network、Railgun）和企業區塊鏈解決方案中。

本文從密碼學家和工程師的雙重視角出發，提供 PLONK 和 Halo2 約束系統的完整數學推導。我們將從橢圓曲線和配對的代數基礎開始，逐步推導約束系統的核心機制，包括多項式承諾、置換論證和查詢論證。同時，我們將提供完整的電路設計範例，涵蓋算術約束、查找表約束和自訂約束的實現方法。

第一部分：代數基礎與密碼學假設

1.1 橢圓曲線群結構

PLONK 和 Halo2 的安全性建立在橢圓曲線離散對數問題（ECDLP）的困難性之上。理解這些代數結構是掌握約束系統推導的前提。

橢圓曲線定義：

在有限域 $\mathbb{F}_p$ 上定義的橢圓曲線 $E$ 由以下魏爾斯特拉斯方程給出：

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

其中 $a, b \in \mathbb{F}_p$ 且 $4a^3 + 27b^2 \neq 0 \pmod{p}$，$p$ 為大質數。

曲線上的所有點（包括無窮遠點 $\mathcal{O}$）構成一個阿貝爾群 $(E(\mathbb{F}_p), +)$，滿足：

• 封閉性：任意兩點相加仍在曲線上
• 結合律：$(P + Q) + R = P + (Q + R)$
• 單位元：$\mathcal{O} + P = P$
• 逆元：$P + (-P) = \mathcal{O}$
• 交換律：$P + Q = Q + P$

標量乘法：

對於點 $P \in E(\mathbb{F}_p)$ 和整數 $k$，標量乘法定義為：

$$[k]P = \underbrace{P + P + \cdots + P}_{k \text{ times}}$$

標量乘法可透過二分法（Double-and-Add）高效計算：

def scalar_multiply(k: int, P: Point) -> Point:
    """標量乘法：k * P"""
    result = Point.INFINITY
    addend = P
    
    while k > 0:
        if k & 1:
            result = point_add(result, addend)
        addend = point_double(addend)
        k >>= 1
    
    return result

def point_double(P: Point) -> Point:
    """點加倍：2P"""
    if P == Point.INFINITY:
        return Point.INFINITY
    
    # 斜率 λ = (3x₁² + a) / (2y₁)
    lam = ((3 * P.x * P.x + CURVE_A) * mod_inverse(2 * P.y, P)) % P
    
    x3 = (lam * lam - 2 * P.x) % P
    y3 = (lam * (P.x - x3) - P.y) % P
    
    return Point(x3, y3)

def point_add(P: Point, Q: Point) -> Point:
    """點加法：P + Q"""
    if P == Point.INFINITY:
        return Q
    if Q == Point.INFINITY:
        return P
    
    if P.x == Q.x:
        if P.y == Q.y:
            return point_double(P)
        else:
            return Point.INFINITY  # P + (-P) = O
    
    # 斜率 λ = (y₂ - y₁) / (x₂ - x₁)
    lam = ((Q.y - P.y) * mod_inverse(Q.x - P.x, P)) % P
    
    x3 = (lam * lam - P.x - Q.x) % P
    y3 = (lam * (P.x - x3) - P.y) % P
    
    return Point(x3, y3)

1.2 配對（Pairing）基礎

配對是 PLONK 中 KZG 承諾方案的核心密碼學原語。Ate 配對允許我們驗證群元素之間的特定代數關係。

雙線性映射定義：

一個雙線性配對 $e: \mathbb{G}1 \times \mathbb{G}2 \to \mathbb{G}_T$ 滿足：

1. 雙線性：$e(a \cdot g1, b \cdot g2) = e(g1, g2)^{ab}$ 對所有 $a, b \in \mathbb{Z}_p$
2. 非退化性：$e(g1, g2) \neq 1{\mathbb{G}T}$
3. 可計算性：存在高效算法計算 $e$

在 PLONK 中，我們通常使用 BN254 曲線，其配對定義如下：

• $\mathbb{G}1$: $E(\mathbb{F}p)$ 的 $r$ 階子群，生成元為 $G$
• $\mathbb{G}2$: $E'(\mathbb{F}{p^2})$ 的 $r$ 階子群，生成元為 $H$
• $\mathbb{G}T$: $\mathbb{F}{p^{12}}$ 的 $r$ 階乘法子群

class BN254Pairing:
    """
    BN254 配對實現
    使用 optimal Ate 配對算法
    """
    
    def __init__(self):
        # BN254 曲線參數
        self.p = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001
        self.r = 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47
        
        # 生成元
        self.G1 = Point(1, 2)  # G1 生成元
        self.G2 = (Point_Fp2(0, 1), Point_Fp2(0, 1))  # G2 生成元
    
    def pairing(self, P: G1Point, Q: G2Point) -> Fp12:
        """
        雙線性配對 e(P, Q)
        
        使用 Miller 算法的優化版本
        """
        # 預計算
        naf_P = self._naf_representation(P)
        
        # Miller 循環
        f = Fp12(1)
        Q_neg = self._point_negate(Q)
        R = Q
        
        for i in range(len(naf_P) - 1, -1, -1):
            f = f * f
            f = f * self._ell_step(R, R, P)
            R = self._point_double(R)
            
            if naf_P[i] == 1:
                f = f * self._ell_step(R, Q, P)
                R = self._point_add(R, Q)
            elif naf_P[i] == -1:
                f = f * self._ell_step(R, Q_neg, P)
                R = self._point_add(R, Q_neg)
        
        # 最終指數
        return self._final_exponentiation(f)
    
    def _ell_step(self, R: Point, Q: G2Point, P: G1Point) -> Fp12:
        """
        Miller 算法的橢圓曲線加倍步驟中的線性化計算
        計算用於配對的線性化因子
        """
        # 省略詳細實現
        pass
    
    def _final_exponentiation(self, f: Fp12) -> Fp12:
        """
        最終指數化
        將 Miller 算法的輸出轉換為唯一的配對值
        """
        # 分塊指數
        f = f ** ((self.p - 1) // self.r)
        f = f * f ** (self.p * (self.p - 1) // self.r + self.p // 6)
        f = f ** ((self.p + 1) // 3)
        
        return f

配對在約束驗證中的應用：

配對使得我們能夠驗證多項式關係而不需要知道多項式的全部係數。給定承諾 $[f]1$、$[g]1$、$[h]1$ 和點 $u \in \mathbb{F}p$，我們可以透過配對驗證 $f(u) \cdot g(u) = h(u)$：

$$e([f]1, [g]2) = e([h]1, [1]2) \iff f(u) \cdot g(u) = h(u)$$

這個性質是 PLONK 約束驗證的基礎。

第二部分：PLONK 約束系統數學推導

2.1 約束系統定義

PLONK 的約束系統將電路的正確執行表示為一組多項式約束。電路由三種基本約束組成：

門約束（Gate Constraints）：

電路中的每個門（左輸入 $a$、右輸入 $b$、輸出 $c$）必須滿足：

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

其中 $qL, qR, qO, qM, q_C$ 為選擇器多項式（Selector Polynomials），定義門的類型：

• 加法門：$qM = 0, qC$ 為加數
• 乘法門：$qL = qR = qO = 0, qC = 0$
• 常數門：$qM = 0, qC$ 為常數

連線約束（Wire Constraints）：

電路的連線必須滿足一致性約束：每個連線的輸出必須等於下一個門的輸入。

2.2 多項式承諾方案（KZG）

KZG（Kate-Zaverucha-Goldberg）承諾是 PLONK 的核心組成部分。它允許承諾者對多項式進行承諾，而驗證者可以抽查任意點的承諾正確性。

承諾生成：

設 $f(x) = \sum{i=0}^{n-1} fi x^i$ 為次數 $d < n$ 的多項式。選擇 trusted setup：

$$\{[s^i \cdot G1\}{i=0}^{n-1}, [s^i \cdot G2]{i=0}^{n-1}\}$$

其中 $s$ 為秘密隨機數（"有毒廢料"），在設置後必須被丟棄。

對多項式 $f$ 的承諾為：

$$[f]1 = \sum{i=0}^{n-1} fi \cdot [s^i \cdot G1] = f(s) \cdot G_1$$

class KZGCommitment:
    """
    KZG 多項式承諾方案
    """
    
    def __init__(self, setup_powers_G1, setup_powers_G2):
        self.powers_G1 = setup_powers_G1  # [G, sG, s²G, ..., s^{n-1}G]
        self.powers_G2 = setup_powers_G2  # [H, sH, s²H, ..., s^{n-1}H]
        self.p = len(setup_powers_G1)
        
    def commit(self, f: Polynomial) -> G1Point:
        """
        對多項式 f(x) 生成承諾
        [f]₁ = f(s) · G₁
        """
        n = min(len(f.coeffs), self.p)
        
        commitment = G1Point.INFINITY
        for i in range(n):
            commitment = point_add(
                commitment,
                scalar_multiply(f.coeffs[i], self.powers_G1[i])
            )
        
        return commitment
    
    def open(self, f: Polynomial, u: FieldElement) -> Tuple[G1Point, Fp]:
        """
        在點 u 處打開多項式
        返回承諾和評估值
        """
        # 計算 f(u)
        y = f.evaluate(u)
        
        # 計算商多項式 q(x) = (f(x) - f(u)) / (x - u)
        # 這需要多項式除法
        diff = Polynomial([y])  # 常數多項式 f(u)
        numerator = f - diff
        quotient = numerator.divide_by_linear(u)
        
        # 承諾商多項式
        proof = self.commit(quotient)
        
        return proof, y
    
    def verify(self, commitment: G1Point, proof: G1Point, 
               u: FieldElement, y: FieldElement) -> bool:
        """
        驗證開啟證明
        驗證 f(s) = y 且 (f(x) - y) / (x - u) = q(x)
        
        通過配對驗證：
        e(commitment - y·G, H) = e(proof, s·H - u·H)
        """
        # commitment - y·G
        left_input = point_add(
            commitment,
            scalar_multiply(-y, G1_GENERATOR)
        )
        
        # s·H - u·H = (s - u)·H
        right_input = point_sub(
            self.powers_G2[1],  # s·H
            scalar_multiply(u, self.powers_G2[0])  # u·H
        )
        
        # 驗證配對相等
        return pairing_check(left_input, right_input)

批量開啟（Batch Opening）：

為提高效率，PLONK 使用 Kate 批量開啟技術同時驗證多個多項式在同一點的承諾。

設有 $t$ 個多項式 $f1, \ldots, ft$ 和點 $u$，我們需要驗證 $fi(u) = yi$。

建構批量開啟多項式：

$$F(x) = \sum{i=1}^{t} \alpha^i \cdot (fi(x) - y_i)$$

其中 $\alpha$ 為隨機挑战。

商多項式：

$$Q(x) = \frac{F(x)}{x - u}$$

驗證只需一個配對檢查：

$$e([F]1, H) = e([Q]1, [s]2 - [u]2)$$

def batch_open(
    commitments: List[G1Point],
    polys: List[Polynomial],
    point: FieldElement,
    values: List[FieldElement],
    alpha: FieldElement
) -> Tuple[G1Point, G1Point]:
    """
    批量開啟多個多項式
    """
    # 建構聚合多項式 F(x)
    F = Polynomial.zero()
    
    for i, (f, y) in enumerate(zip(polys, values)):
        diff = Polynomial([y])  # 常數多項式 f(u)
        F = F + (f - diff) * (alpha ** i)
    
    # 承諾 F
    F_commitment = kzg.commit(F)
    
    # 計算商多項式 Q
    numerator = F
    denominator = Polynomial([-point, 1])  # x - u
    Q = numerator.divide(denominator)
    
    # 承諾 Q
    Q_proof = kzg.commit(Q)
    
    return F_commitment, Q_proof

def batch_verify(
    commitments: List[G1Point],
    point: FieldElement,
    values: List[FieldElement],
    alpha: FieldElement,
    F_commitment: G1Point,
    Q_proof: G1Point
) -> bool:
    """
    驗證批量開啟
    """
    # 計算期望的 commitment
    expected_F = G1Point.INFINITY
    for i, (c, y) in enumerate(zip(commitments, values)):
        # c - y·G
        adjusted = point_add(c, scalar_multiply(-y, G1_GENERATOR))
        # α^i · (c - y·G)
        scaled = scalar_multiply(alpha ** i, adjusted)
        expected_F = point_add(expected_F, scaled)
    
    # 驗證配對相等
    left = point_sub(F_commitment, expected_F)
    right = point_sub(powers_G2[1], scalar_multiply(point, powers_G2[0]))
    
    return pairing_check(left, right)

2.3 置換論證（Permutation Argument）

置換論證是 PLONK 實現電路連線約束的核心機制。它允許證明者聲稱兩個列表是同一多項式的置換重排，而驗證者可以高效地檢查這個聲稱。

問題定義：

設有兩個列表 $a = (a1, \ldots, an)$ 和 $b = (b1, \ldots, bn)$，證明者聲稱 $b$ 是 $a$ 的某一置換 $\sigma$ 作用後的結果：

$$bi = a{\sigma(i)}, \quad \forall i \in [n]$$

Zcash 置換論證：

Zcash 團隊提出的置換論證使用累積乘積（Grand Product）來驗證置換關係。

定義累積乘積：

$$Z0 = 1, \quad Zi = \prod{j=1}^{i} \frac{aj - b{\sigma(j)}}{aj - a_{j+1}}$$

其中 $a{n+1}$ 定義為特殊值（通常是 0 或 $a1$ 的某種變換）。

最終條件：$Z_n = 1$。

推導過程：

設 $a' = (a1, a2, \ldots, an, a{n+1})$，其中 $a{n+1} = a1$。

定義連續比值：

$$ri = \frac{a'i - bi}{a'i - a'_{i+1}}$$

如果 $bi = a'{\sigma(i)}$，則：

$$\prod{i=1}^{n} ri = \prod{i=1}^{n} \frac{a'i - a'{\sigma(i)}}{a'i - a'{i+1}} = \prod{i=1}^{n} \frac{a'i - a'{\sigma(i)}}{a'i - a'{\sigma(i)+1}} = 1$$

因為分子和分母是相同的集合，只是順序可能不同。

class PermutationArgument:
    """
    PLONK 置換論證實現
    """
    
    def __init__(self, n: int, alpha: FieldElement):
        self.n = n
        self.alpha = alpha
        self.F = Field(n)  # 有限域
    
    def prove_permutation(
        self,
        a: List[FieldElement],
        b: List[FieldElement],
        sigma: List[int]
    ) -> Tuple[List[FieldElement], G1Point]:
        """
        證明 b 是 a 的置換
        
        輸出：Z 列表和 Z 的承諾
        """
        assert len(a) == len(b) == len(sigma) == self.n
        
        # 定義 a'：將 a 的最後一個元素設為第一個元素
        a_prime = a.copy()
        a_prime.append(a[0])
        
        # 計算 Z_0 = 1
        Z = [self.F.one()]
        
        # 遞推計算 Z_i
        for i in range(self.n):
            numerator = a_prime[i] - b[i]
            denominator = a_prime[i] - a_prime[i + 1]
            r_i = numerator * denominator.inverse()
            
            z_i = Z[i] * r_i
            Z.append(z_i)
        
        # 最後一個 Z 值應該為 1
        assert Z[-1] == self.F.one(), "Permutation check failed"
        
        # 承諾 Z 多項式
        # 將 Z 視為多項式在點 1, 2, ..., n+1 的取值
        Z_poly = self._values_to_polynomial(Z)
        Z_commitment = kzg.commit(Z_poly)
        
        return Z, Z_commitment
    
    def verify_permutation(
        self,
        a_commitment: G1Point,
        b_commitment: G1Point,
        Z_commitment: G1Point,
        challenges: Tuple[FieldElement, FieldElement]
    ) -> bool:
        """
        驗證置換論證
        """
        beta, gamma = challenges
        
        # 驗證 Z_0 = 1 和 Z_n = 1
        # 這通過在端點約束多項式來實現
        
        # 驗證遞推關係
        # 需要檢查 (Z_{i+1} - Z_i) * (a_i + β * σ_i + γ) - (a_i - b_i) = 0
        
        # 這通過建構複合多項式並驗證來實現
        pass
    
    def _values_to_polynomial(
        self, 
        values: List[FieldElement]
    ) -> Polynomial:
        """
        將列表值轉換為拉格朗日多項式
        使用拉格朗日插值
        """
        n = len(values)
        
        # 創建拉格朗日基
        coeffs = [self.F.zero()] * n
        
        for i in range(n):
            # 計算拉格朗日基 L_i(x)
            numerator = Polynomial([self.F.one()])
            denominator = self.F.one()
            
            for j in range(n):
                if i != j:
                    # (x - ω^j)
                    numerator = numerator * Polynomial([-self.F.omega(j), self.F.one()])
                    denominator = denominator * (self.F.omega(i) - self.F.omega(j))
            
            lagrange_i = numerator * denominator.inverse()
            
            # 添加到總和
            for k in range(n):
                coeffs[k] = coeffs[k] + values[i].value * lagrange_i.coeffs[k]
        
        return Polynomial(coeffs)

2.4 查詢論證（Lookup Argument）

PLONK 支持查找表約束，允許電路使用預定義的查找表。這對於實現非零知識友好操作（如位元運算、查表）特別有用。

揀（Lookup）問題：

給定表 $T = (t1, \ldots, tm)$ 和輸入序列 $f = (f1, \ldots, fn)$，證明每個 $f_i$ 都出現在表 $T$ 中：

$$fi \in \{t1, \ldots, t_m\}, \quad \forall i \in [n]$$

PLONK 查找論證：

PLONK 採用「承諾的乘積」方法來實現查找論證。

定義輔助序列：

$$hi = \prod{j=1}^{i} \frac{fj - tj + \gamma}{fj - f{j+1} + \gamma}$$

其中 $f_{n+1} = 0$。

定義查找表序列：

$$gi = \prod{j=1}^{i} \frac{tj + \gamma}{tj - t_{j+1} + \gamma}$$

其中 $t_{m+1} = 0$。

class LookupArgument:
    """
    PLONK 查找論證實現
    """
    
    def __init__(self, table: List[FieldElement]):
        self.table = table
        self.m = len(table)
    
    def prove_lookup(
        self,
        f: List[FieldElement],
        gamma: FieldElement
    ) -> Tuple[FieldElement, FieldElement]:
        """
        證明 f 中的所有值都在表中
        
        返回：乘積值 h_n 和 g_n
        """
        assert all(v in self.table for v in f), "All values must be in table"
        
        # 擴展表：添加一個 0 值
        t_extended = self.table + [self.F.zero()]
        
        # 計算 h_n
        h_product = self.F.one()
        f_extended = f + [self.F.zero()]
        
        for i, f_i in enumerate(f_extended[:-1]):
            numerator = f_i - t_extended[i] + gamma
            denominator = f_i - f_extended[i + 1] + gamma
            h_product = h_product * numerator * denominator.inverse()
        
        # 計算 g_n（表累積乘積）
        g_product = self.F.one()
        for i in range(self.m):
            numerator = t_extended[i] + gamma
            denominator = t_extended[i] - t_extended[i + 1] + gamma
            g_product = g_product * numerator * denominator.inverse()
        
        return h_product, g_product
    
    def verify_lookup(
        self,
        h_n: FieldElement,
        g_n: FieldElement,
        f_commitment: G1Point,
        table_commitment: G1Point,
        gamma: FieldElement
    ) -> bool:
        """
        驗證查找論證
        """
        # 驗證 h_n = g_n
        # 這保證了 f 中的每個值都出現在表中
        
        # 實際驗證需要將承諾與值結合
        return h_n == g_n

第三部分：Halo2 約束系統推導

3.1 Halo2 核心概念

Halo2 是 Zcash 團隊開發的零知識證明系統，其核心創新是採用「遞歸證明」（Recursive Proof）架構，無需可信設置即可實現高效的證明聚合。

與 PLONK 的主要區別：

Halo2 的多項式承諾：

Halo2 使用基於內積論證（Inner Product Argument）的多項式承諾方案，稱為「多項式封裝」（Polynomial Encapsulation）。

3.2 內積論證

內積論證允許證明者聲稱兩個向量 $\mathbf{a}, \mathbf{b} \in \mathbb{F}_p^n$ 的內積為 $c$：

$$c = \sum{i=0}^{n-1} ai \cdot b_i$$

Pedersen 承諾：

對向量 $\mathbf{a}$ 的 Pedersen 承諾為：

$$[\mathbf{a}] = \sum{i=0}^{n-1} ai \cdot G_i$$

其中 $G_i$ 為固定的多個生成元。

內積論證協議：

證明者 -> 驗證者：
1. 發送 commitment [a] 和 [b]
2. 對於 i = 0 到 log(n)-1：
   - 將向量對半劃分：a_L, a_R, b_L, b_R
   - 發送 commitment [a_L], [a_R], [b_L], [b_R]
   - 驗證者發送隨機 challenge x
   - 證明者計算：
     a' = a_L + x * a_R
     b' = b_L + x^{-1} * b_R
     c' = c - x * (a_L · b_R + a_R · b_L)
   - 繼續下一輪
3. 最後一輪，發送 a_n, b_n
4. 驗證 c_n = a_n * b_n

class InnerProductArgument:
    """
    Halo2 內積論證實現
    """
    
    def __init__(self, G: List[G1Point]):
        self.G = G  #  генератор向量
        self.n = len(G)
        self.log_n = int(math.log2(self.n))
    
    def prove(
        self,
        a: List[FieldElement],
        b: List[FieldElement],
        transcript: Transcript
    ) -> InnerProductProof:
        """
        證明 <a, b> 的知識
        """
        assert len(a) == len(b) == self.n
        
        # 初始化
        a_vec = a.copy()
        b_vec = b.copy()
        G_vec = self.G.copy()
        
        # 初始內積
        c = sum(ai * bi for ai, bi in zip(a, b))
        
        # 存儲證明
        L = []
        R = []
        
        # 迭代折疊
        for i in range(self.log_n):
            # 將向量對半劃分
            n_half = len(a_vec) // 2
            a_L, a_R = a_vec[:n_half], a_vec[n_half:]
            b_L, b_R = b_vec[:n_half], b_vec[n_half:]
            G_L, G_R = G_vec[:n_half], G_vec[n_half:]
            
            # 從轉錄中獲取 challenge
            x = transcript.get_challenge()
            x_inv = x.inverse()
            
            # 計算折疊後的向量
            a_next = [a_L[i] + x * a_R[i] for i in range(n_half)]
            b_next = [b_L[i] + x_inv * b_R[i] for i in range(n_half)]
            G_next = [G_L[i] + x * G_R[i] for i in range(n_half)]
            
            # 計算 L 和 R（用於驗證）
            # L = <a_R, b_L> + <a_L, b_R> * x
            L_i = sum(a_R[i] * b_L[i] for i in range(n_half))
            L_i = L_i + sum(a_L[i] * b_R[i] for i in range(n_half)) * x
            
            # R = <a_R, b_R>  (在最後計算)
            
            L.append(self._commit(L_i, G_R))  # 簡化
            R.append(self._commit(sum(a_R[i] * b_R[i] for i in range(n_half)), G_L))
            
            # 更新內積
            c = c - x * L_i
            
            # 折疊
            a_vec = a_next
            b_vec = b_next
            G_vec = G_next
        
        return InnerProductProof(
            c=c,
            a_final=a_vec[0],
            b_final=b_vec[0],
            L=L,
            R=R
        )
    
    def verify(
        self,
        proof: InnerProductProof,
        commitment_a: G1Point,
        commitment_b: G1Point,
        transcript: Transcript
    ) -> bool:
        """
        驗證內積論證
        """
        a = proof.a_final
        b = proof.b_final
        c = proof.c
        G = self.G.copy()
        
        # 遞歸驗證
        for i in range(self.log_n - 1, -1, -1):
            x = transcript.get_challenge()
            x_inv = x.inverse()
            
            # 逆折疊
            # 恢復上一輪的 commitment
            pass
        
        # 最終驗證
        # c = a * b
        return c == a * b

3.3 Halo2 查詢論證

Halo2 使用「洗牌論證」（Shuffle Argument）和「查找論證」的組合來實現電路約束。

查找表約束：

Halo2 的查找表實現使用「固定基數組」（Lookup Table）結構，將表值分為多個"columns"，每列可以包含多個值。

class Halo2LookupTable:
    """
    Halo2 查找表約束
    """
    
    def __init__(self, columns: List[List[FieldElement]]):
        """
        初始化查找表
        
        columns: 表的列，每列為 FieldElement 列表
        """
        self.columns = columns
        self.num_columns = len(columns)
        self.num_rows = len(columns[0])
        
        # 確保所有列長度相同
        assert all(len(col) == self.num_rows for col in columns)
    
    def arrange(
        self,
        inputs: List[List[FieldElement]]
    ) -> Tuple[List[FieldElement], List[List[FieldElement]]]:
        """
        將輸入排列為與表相同的格式
        
        返回：(已填充的輸入, 選擇向量)
        """
        arranged = []
        selectors = []
        
        for row_idx in range(self.num_rows):
            for col_idx in range(self.num_columns):
                table_value = self.columns[col_idx][row_idx]
                arranged.append(table_value)
                
                # 檢查這個行是否匹配輸入
                if row_idx < len(inputs[col_idx]):
                    selectors.append(self.F.one() if arranged[-1] == inputs[col_idx][row_idx] else self.F.zero())
                else:
                    selectors.append(self.F.zero())
        
        return arranged, selectors
    
    def prove_lookup(
        self,
        arranged: List[FieldElement],
        selectors: List[FieldElement]
    ) -> Tuple[FieldElement, FieldElement]:
        """
        證明查找約束
        
        使用洗牌論證確保排列正確
        """
        # 這裡需要使用完整的 Halo2 約束系統
        # 簡化版本
        pass

第四部分：電路設計範例

4.1 算術約束電路

以下是使用 Halo2 API 實現基本算術約束的完整範例：

"""
Halo2 電路設計範例：基本算術運算
"""

from halo2 import *

class ArithmeticCircuit(Circuit):
    """
    基本算術電路
    
    實現：
    - 加法：c = a + b
    - 乘法：d = e * f
    - 混合：out = (x + y) * z
    """
    
    class Config:
        """電路配置"""
        def __init__(self, meta: ChipMetadata):
            # 配置旋轉（advices）
            self.a = Column(Advice)
            self.b = Column(Advice)
            self.c = Column(Advice)
            self.d = Column(Advice)
            self.e = Column(Advice)
            self.f = Column(Advice)
            self.out = Column(Advice)
            
            # 配置常數列
            self.constant = Column(Constant)
            
            # 配置選擇器
            self.sel_add = Selector()
            self.sel_mul = Selector()
            self.sel_complex = Selector()
            
            # 配置排列
            meta.enable Equality(self.a)
            meta.enable Equality(self.b)
            meta.enable Equality(self.c)
            meta.enable Equality(self.d)
            meta.enable Equality(self.e)
            meta.enable Equality(self.f)
            meta.enable Equality(self.out)
    
    def without_gates(&self) -> bool:
        """這個電路需要門約束"""
        return False
    
    def configure(meta: ChipMetadata, config: Config) -> Config:
        """配置電路"""
        return config
    
    def synthesize(
        self, 
        gate: Gate, 
        config: Config, 
        challenges: Tuple[Field, ...]
    ) -> None:
        """綜合電路"""
        a = config.a
        b = config.b
        c = config.c
        d = config.d
        e = config.e
        f = config.f
        out = config.out
        
        # 加法約束：c = a + b
        gate.add_gate(
            "add",
            [a, b, c],
            config.sel_add,
            lambda a, b, c: a + b - c  # a + b - c = 0
        )
        
        # 乘法約束：d = e * f
        gate.add_gate(
            "mul",
            [e, f, d],
            config.sel_mul,
            lambda e, f, d: e * f - d  # e * f - d = 0
        )
        
        # 混合約束：out = (x + y) * z
        # 需要額外的臨時變量
        gate.add_gate(
            "complex",
            [config.a, config.b, config.e, config.out],
            config.sel_complex,
            lambda x, y, z, out: (x + y) * z - out
        )

class RangeCheckCircuit(Circuit):
    """
    範圍檢查電路
    
    證明一個值在 [0, 2^n) 範圍內
    """
    
    class Config:
        def __init__(self, meta: ChipMetadata, bits: int):
            self.value = Column(Advice)
            self.bits = [Column(Advice) for _ in range(bits)]
            self.constant = Column(Constant)
            
            for bit in self.bits:
                meta.enable Equality(bit)
    
    def configure(meta: ChipMetadata, config: Config, bits: int) -> Config:
        """配置範圍檢查電路"""
        
        # 每個位元必須為 0 或 1
        for i, bit_col in enumerate(config.bits):
            # 約束：bit * (1 - bit) = 0
            meta.create_gate(
                f"bit_check_{i}",
                [bit_col],
                lambda bit: bit * (bit - 1)
            )
        
        return config
    
    def synthesize(
        self,
        gate: Gate,
        config: Config,
        challenges: Tuple[Field, ...]
    ) -> None:
        """將值分解為位元"""
        value = config.value
        
        # 將值分解為二進制
        remaining = value
        for i, bit_col in enumerate(config.bits):
            bit = remaining % 2
            gate.copy(bit_col, bit)
            remaining = remaining // 2
        
        # 最後，remaining 應該為 0
        gate.assert_zero(remaining)

class SHA256CompressionCircuit(Circuit):
    """
    SHA-256 壓縮函數電路
    
    展示如何使用查表約束優化非零知識友好操作
    """
    
    # SHA-256 常數
    K = [...]  # 64 個初始常數
    
    class Config:
        def __init__(self, meta: ChipMetadata):
            # 消息和狀態列
            self.message = [Column(Advice) for _ in range(16)]
            self.state = [Column(Advice) for _ in range(8)]
            
            # 臨時變量
            self.temp = [Column(Advice) for _ in range(64)]
            
            # 查表
            self.xor_table = LookupTable("xor")
            self.ch_table = LookupTable("ch")
            self.maj_table = LookupTable("maj")
    
    def configure(meta: ChipMetadata, config: Config) -> Config:
        """配置 SHA-256 電路"""
        
        # 初始化 XOR 查表
        for a in range(2):
            for b in range(2):
                config.xor_table.insert([a, b], a ^ b)
        
        # 初始化 Ch 和 Maj 查表
        for e, f, g in itertools.product(range(2), repeat=3):
            config.ch_table.insert([e, f, g], (e & f) ^ (~e & g))
            config.maj_table.insert([e, f, g], (e & f) ^ (e & g) ^ (f & g))
        
        return config
    
    def synthesize(
        self,
        gate: Gate,
        lookup: Lookup,
        config: Config,
        challenges: Tuple[Field, ...]
    ) -> None:
        """綜合 SHA-256 壓縮"""
        
        # 初始化工作變量
        a, b, c, d, e, f, g, h = config.state[:8]
        
        # 64 輪迭代
        for i in range(64):
            # Σ1(e) = ROTR(e,6) ^ ROTR(e,11) ^ ROTR(e,25)
            sum1 = self._rotr(e, 6) ^ self._rotr(e, 11) ^ self._rotr(e, 25)
            
            # Ch(e, f, g) = (e & f) ^ (~e & g)
            ch = lookup.query(config.ch_table, [e, f, g])
            
            # Temp1 = h + Σ1 + Ch + K[i] + w[i]
            temp1 = h + sum1 + ch + Field(self.K[i]) + config.message[i % 16]
            
            # Σ0(a) = ROTR(a,2) ^ ROTR(a,13) ^ ROTR(a,22)
            sum0 = self._rotr(a, 2) ^ self._rotr(a, 13) ^ self._rotr(a, 22)
            
            # Maj(a, b, c) = (a & b) ^ (a & c) ^ (b & c)
            maj = lookup.query(config.maj_table, [a, b, c])
            
            # Temp2 = Σ0 + Maj
            temp2 = sum0 + maj
            
            # 更新狀態
            h = g
            g = f
            f = e
            e = d + temp1
            d = c
            c = b
            b = a
            a = temp1 + temp2
        
        # 輸出最終哈希
        for i in range(8):
            gate.copy(config.state[i], [a, b, c, d, e, f, g, h][i])

4.2 自訂約束範例

以下是一些實際應用中的自訂約束範例：

"""
實際應用中的自訂約束範例
"""

class VerkleTreeCommitmentCircuit(Circuit):
    """
    Verkle 樹承諾電路
    
    展示如何在零知識電路中實現向量承諾
    """
    
    class Config:
        def __init__(self, meta: ChipMetadata, width: int):
            # 承諾和驗證
            self.commitment = Column(Advice)
            self.point = Column(Advice)
            
            # 多項式評估值
            self.values = [Column(Advice) for _ in range(width)]
            self.proof = [Column(Advice) for _ in range(width)]
            
            # 查表：用於多項式評估
            self.poly_eval_table = LookupTable("poly_eval")
    
    def configure(meta: ChipMetadata, config: Config, width: int) -> Config:
        """配置 Verkle 承諾電路"""
        
        # 計算 ω^i（根的冪）
        # 這些是電路常數
        powers = [G1_GENERATOR * (F.s(ω) ** i) for i in range(width)]
        
        # 約束：承諾 = Σ values[i] * powers[i]
        # 這是一個線性約束，可以高效實現
        
        return config
    
    def synthesize(
        self,
        gate: Gate,
        config: Config,
        challenges: Tuple[Field, ...]
    ) -> None:
        """驗證 Verkle 承諾"""
        
        commitment = config.commitment
        values = config.values
        
        # 計算承諾
        computed = sum(
            v * G1_GENERATOR * F.s(ω) ** i
            for i, v in enumerate(values)
        )
        
        # 約束承諾相等
        gate.assert_equal(commitment, computed)
        
        # 驗證多項式承諾（Kate 方案）
        # 使用查表實現指數運算


class PrivateBalanceTransferCircuit(Circuit):
    """
    私密餘額轉帳電路
    
    展示如何在零知識電路中實現私密交易
    """
    
    class Config:
        def __init__(self, meta: ChipMetadata):
            # 輸入承諾
            self.input_commit = Column(Advice)
            self.input_nullifier = Column(Advice)
            self.input_balance = Column(Advice)
            self.input_nonce = Column(Advice)
            
            # 輸出承諾
            self.output_commit = Column(Advice)
            self.output_balance = Column(Advice)
            self.output_public_key = Column(Advice)
            
            # 範圍證明
            self.balance_bits = [Column(Advice) for _ in range(64)]
            
            # 簽章
            self.signature = Column(Advice)
            self.message_hash = Column(Advice)
            
            # 查表
            self.merkle_tree = MerkleTreeConfig()
    
    def configure(meta: ChipMetadata, config: Config) -> Config:
        """配置私密轉帳電路"""
        
        # 範圍檢查：餘額不能為負
        for bit_col in config.balance_bits:
            gate.add_gate(
                "range_check",
                [bit_col],
                lambda bit: bit * (bit - 1)
            )
        
        return config
    
    def synthesize(
        self,
        gate: Gate,
        config: Config,
        challenges: Tuple[Field, ...]
    ) -> None:
        """驗證私密轉帳"""
        
        # 1. 驗證 Merkle 樹路徑
        # 確認 input_commit 在承諾樹中
        path_valid = verify_merkle_path(
            config.merkle_tree,
            config.input_commit,
            config.merkle_path,
            config.merkle_root
        )
        gate.assert_one(path_valid)
        
        # 2. 驗證 Nullifier
        # nullifier = hash(private_key, nonce)
        expected_nullifier = poseidon_hash(
            config.output_public_key,
            config.input_nonce
        )
        gate.assert_equal(config.input_nullifier, expected_nullifier)
        
        # 3. 驗證餘額範圍
        # 將 balance 分解為位元
        balance = config.input_balance - config.output_balance
        for i, bit_col in enumerate(config.balance_bits):
            bit = balance >> i & 1
            gate.copy(bit_col, bit)
        
        # 4. 驗證承諾
        # input_commit = hash(nullifier, balance)
        expected_input_commit = poseidon_hash(
            config.input_nullifier,
            config.input_balance
        )
        gate.assert_equal(config.input_commit, expected_input_commit)
        
        # output_commit = hash(new_nullifier, new_balance)
        new_nullifier = poseidon_hash(
            config.output_public_key,
            config.input_nonce + 1
        )
        expected_output_commit = poseidon_hash(
            new_nullifier,
            config.output_balance
        )
        gate.assert_equal(config.output_commit, expected_output_commit)
        
        # 5. 驗證簽章
        verify_eddsa_signature(
            config.signature,
            config.message_hash,
            config.output_public_key
        )


class ZKMLInferenceCircuit(Circuit):
    """
    ZK 機器學習推論電路
    
    展示如何在零知識電路中驗證神經網路推論
    """
    
    class Config:
        def __init__(self, meta: ChipMetadata, layers: List[int]):
            # 輸入和輸出
            self.input = [Column(Advice) for _ in range(layers[0])]
            self.output = [Column(Advice) for _ in range(layers[-1])]
            
            # 權重和偏置（作為電路常數或承諾）
            self.weights = []
            self.biases = []
            
            # 臨時變量
            self.tmp = []
            
            # 激活函數查表
            self.relu_table = LookupTable("relu")
            self.sigmoid_table = LookupTable("sigmoid")
    
    def configure(
        meta: ChipMetadata, 
        config: Config, 
        layers: List[int]
    ) -> Config:
        """配置 ZKML 電路"""
        
        # 初始化 ReLU 查表
        for x in range(2**16):  # 假設 16 位定點數
            config.relu_table.insert([x], max(0, x))
        
        return config
    
    def synthesize(
        self,
        gate: Gate,
        lookup: Lookup,
        config: Config,
        challenges: Tuple[Field, ...]
    ) -> None:
        """執行神經網路推論"""
        
        activations = config.input
        
        # 遍歷每一層
        for layer_idx in range(len(config.weights)):
            weights = config.weights[layer_idx]
            bias = config.biases[layer_idx]
            
            # 矩陣乘法 + 偏置
            new_activations = []
            for j in range(len(weights)):
                weighted_sum = bias[j]
                for i in range(len(activations)):
                    weighted_sum += activations[i] * weights[i][j]
                
                new_activations.append(weighted_sum)
            
            # 應用激活函數（最後一層除外）
            if layer_idx < len(config.weights) - 1:
                activations = []
                for val in new_activations:
                    # 使用 ReLU 查表
                    activated = lookup.query(config.relu_table, [val])
                    activations.append(activated)
            else:
                activations = new_activations
        
        # 約束輸出
        for i in range(len(config.output)):
            gate.assert_equal(config.output[i], activations[i])


class AggregatedSignatureCircuit(Circuit):
    """
    聚合簽章驗證電路
    
    展示如何使用零知識證明驗證多個 BLS 簽章
    """
    
    class Config:
        def __init__(self, meta: ChipMetadata, num_signatures: int):
            # 消息和公鑰
            self.messages = [Column(Advice) for _ in range(num_signatures)]
            self.public_keys = [Column(Advice) for _ in range(num_signatures)]
            
            # 聚合簽章
            self.aggregated_signature = Column(Advice)
            
            # 查表：用於配對計算
            self.g1_table = LookupTable("g1_mul")
            self.g2_table = LookupTable("g2_mul")
    
    def synthesize(
        self,
        gate: Gate,
        lookup: Lookup,
        config: Config,
        challenges: Tuple[Field, ...]
    ) -> None:
        """驗證聚合 BLS 簽章"""
        
        # 聚合簽章驗證
        # e(agg_sig, G2) = ∏ e(H(msg_i), pk_i)
        
        # 左邊：BLS12-381 配對
        # e(agg_sig, G2)
        
        # 右邊：消息哈希和公鑰的配對乘積
        # 這需要多個配對，可以用查表優化
        
        # 約束所有消息哈希正確
        for i in range(len(config.messages)):
            expected_hash = poseidon_hash(config.messages[i])
            gate.assert_equal(expected_hash, config.messages[i])
        
        # 驗證聚合
        # 這是一個複雜的多配對約束
        # 需要使用特殊的聚合技術

第五部分：實際部署考量

5.1 電路設計最佳實踐

選擇約束類型：

約束類型選擇指南：

┌────────────────┬──────────────┬────────────────┬─────────────────┐
│ 約束類型        │ 約束數量      │ 證明時間        │ 適用場景        │
├────────────────┼──────────────┼────────────────┼─────────────────┤
│ 簡單算術        │ 低           │ 快             │ 加減乘除        │
│ 多項式          │ 中           │ 中             │ 複雜數學        │
│ 查表            │ 高           │ 中             │ 位元運算、S盒   │
│ 自訂電路        │ 可變         │ 可變           │ 特殊需求        │
└────────────────┴──────────────┴────────────────┴─────────────────┘

優化技巧：

class CircuitOptimizer:
    """
    電路優化工具
    """
    
    def __init__(self, circuit: Circuit):
        self.circuit = circuit
    
    def optimize_constraints(self) -> Circuit:
        """優化約束數量"""
        
        # 1. 合併相似約束
        merged = self._merge_similar_gates()
        
        # 2. 消除冗餘變量
        reduced = self._eliminate_redundant_vars(merged)
        
        # 3. 使用查表替代複雜計算
        table_optimized = self._replace_with_lookups(reduced)
        
        return table_optimized
    
    def _merge_similar_gates(self) -> Circuit:
        """合併具有相同結構的門"""
        # 如果多個門具有相同的選擇器模式
        # 可以合併為單個門
        pass
    
    def _eliminate_redundant_vars(self, circuit: Circuit) -> Circuit:
        """消除冗餘變量"""
        # 消除只在等式一側出現的變量
        pass
    
    def _replace_with_lookups(self, circuit: Circuit) -> Circuit:
        """使用查表替代複雜約束"""
        # 識別可查表化的計算
        # 例如：SHA-256 S盒、橢圓曲線運算等
        pass

5.2 安全性考量

class SecurityChecker:
    """
    電路安全性檢查工具
    """
    
    def check_soundness(self, circuit: Circuit) -> List[str]:
        """
        檢查電路的健全性
        
        確保約束足以防止作弊
        """
        issues = []
        
        # 1. 檢查未約束的變量
        unconstrained = self._find_unconstrained_vars()
        if unconstrained:
            issues.append(f"未約束的變量: {unconstrained}")
        
        # 2. 檢查弱約束
        weak_constraints = self._find_weak_constraints()
        if weak_constraints:
            issues.append(f"弱約束可能導致攻擊: {weak_constraints}")
        
        # 3. 檢查查表大小
        small_lookups = self._find_small_lookups()
        if small_lookups:
            issues.append(f"小型查表可能洩露資訊: {small_lookups}")
        
        return issues
    
    def check_zero_knowledge(self, circuit: Circuit) -> List[str]:
        """
        檢查零知識性質
        
        確保電路不會洩露私有輸入
        """
        issues = []
        
        # 1. 檢查公共輸出
        public_outputs = circuit.get_public_outputs()
        private_inputs = circuit.get_private_inputs()
        
        for output in public_outputs:
            if output in private_inputs:
                issues.append(f"私有輸入直接作為公開輸出: {output}")
        
        # 2. 檢查範圍證明
        missing_range_checks = self._find_missing_range_checks()
        if missing_range_checks:
            issues.append(f"缺少範圍證明: {missing_range_checks}")
        
        return issues

結論

PLONK 和 Halo2 代表了當代零知識證明技術的最高水平。本文提供了這兩個系統的完整數學推導，從基礎的橢圓曲線代數到複雜的約束系統設計。

理解這些底層原理對於開發高效、安全的零知識應用至關重要。隨著這些技術的不斷成熟和優化，我們可以預期它們在區塊鏈隱私、擴容和企業應用中的廣泛採用。

未來的發展方向包括：

• 更高效的遞歸證明聚合
• 硬體加速支援
• 標準化的電路描述語言
• 自動化的電路生成工具

標籤

technical, zero-knowledge, plonk, halo2, privacy, circuit-design, cryptography, mathematical-derivation, constraint-system, zk-snark

難度

advanced

參考文獻

1. Gabizon, A. et al. (2023). "PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge." IEEE S&P 2023.
2. Bunz, B. et al. (2020). "Proofs for Inner Products and Succinct Polynomial Evaluation." Eurocrypt 2020.
3. Zcash Foundation. (2024). "Halo2 Design Documentation." Retrieved fromzcash.github.io/halo2.
4. Aztec Network. (2024). "PLONK by Hand." Technical Blog.
5. Bootle, J. et al. (2020). "Bulletproofs: Short Proofs for Confidential Transactions." IEEE S&P 2018.
6. Kate, A. et al. (2010). "Constant-Size Commitments to Polynomials and Their Applications." Asiacrypt 2010.
7. Groth, J. et al. (2016). "On the Size of Pairing-based Non-interactive Arguments." Eurocrypt 2016.