KZG 承諾、PLONK 與 HALO2 電路設計數學推導完整指南：從多項式承諾到零知識電路的工程實踐

進階 📅 發布：2026-03-22 🏷️ technical, zero-knowledge, zk-snark, zk-stark, kzg, plonk, halo2, circuit-design, cryptography, elliptic-curve, polynomial-commitment, l2, rollup 計算中...

本文深入探討零知識證明的三大核心技術支柱：KZG 承諾的密碼學基礎、PLONK 證明系統的電路設計原理，以及 HALO2 的遞歸證明機制。提供完整的數學推導過程，包括有限域運算、橢圓曲線配對、多項式承諾、批量開放大學等核心概念的詳細證明。同時涵蓋電路設計實務，包含約束系統、查找表優化、遞歸證明組合等工程實踐。為 L2 開發者、安全研究者和密碼學研究者提供全面的理論與實作指南。

KZG 承諾、PLONK 與 HALO2 電路設計數學推導完整指南：從多項式承諾到零知識電路的工程實踐

概述

零知識證明（Zero-Knowledge Proof）是以太坊擴容與隱私技術的核心基礎設施。從 zkSync、Starknet 到 Polygon zkEVM，零知識電路的設計與實現決定了現代 L2 解決方案的安全性與效率。本指南深入探討三個關鍵技術支柱：KZG 承諾的密碼學基礎、PLONK 證明系統的電路設計原理，以及 HALO2 的遞歸證明機制。我們將提供完整的數學推導、程式碼範例與學術論文引用，幫助研究者與工程師掌握這些前沿技術的核心原理。

一、KZG 多項式承諾的密碼學基礎

1.1 多項式承諾的定義與動機

多項式承諾（Polynomial Commitment）是「外包計算」場景中的核心密碼學原語。假設證明者 $P$ 需要向驗證者 $V$ 證明「我已經計算了多項式 $f(x)$ 在多個點的評估值」，但又不想透露整個多項式。多項式承諾允許 $P$ 僅發送一個「承諾」$C$，事後再針對任意點 $z$ 提供一個「開放」（opening），證明承諾確實對應包含 $f(z)$ 的多項式。

形式化定義：

多項式承諾方案 $\Sigma$ 由以下算法組成：

Setup$(\lambda, d) \rightarrow pp$：给定安全參數 $\lambda$ 和多項式度數上限 $d$，生成公開參數 $pp$。

Commit$(pp, f) \rightarrow C$：對多項式 $f \in \mathbb{F}_d[x]$ 輸出承諾 $C$。

Open$(pp, f, z) \rightarrow \pi$：生成多項式在點 $z$ 的開放證明 $\pi$。

VerifyPoly$(pp, C, z, y, \pi) \rightarrow \{0,1\}$：驗證 $f(z) = y$ 且 $C$ 是對 $f$ 的承諾。

KZG 承諾由 Kate、Zaverucha 和 Goldberg 在 2010 年提出，其安全性基於離散對數假設和雙線性配對。

1.2 KZG 承諾的數學推導

1.2.1 信任設置（Trusted Setup）

KZG 方案需要一個「結構化參考字串」（Structured Reference String, SRS）。假設我們選擇一個秘密值 $\tau \in \mathbb{F}_p$，並公開以下橢圓曲線點：

$$[1]1 = G1, \quad [\tau]1 = \tau G1, \quad [\tau^2]1 = \tau^2 G1, \quad \ldots, \quad [\tau^d]1 = \tau^d G1$$

$$[1]2 = G2, \quad [\tau]2 = \tau G2$$

其中 $G1$ 和 $G2$ 是配對友好的橢圓曲線（如 BN128 或 BLS12-381）的生成元。$[\tau^i]1$ 表示 $\tau^i \cdot G1$。

為何需要秘密值 $\tau$：這個秘密值被稱為「有毒廢料」（Toxic Waste）。只要攻擊者不知道 $\tau$，就無法偽造虛假的多項式承諾。

可更新設置（Updateratable Setup）：實際部署中，採用多方計算（MPC）儀式生成 SRS。2019 年 Zcash 的「powers of tau」儀式有超過 87 名參與者。只要其中一人誠實，$\tau$ 就無法被恢復。

1.2.2 承諾生成

對於度數為 $d$ 的多項式：

$$f(x) = a0 + a1 x + a2 x^2 + \cdots + ad x^d$$

承諾計算為：

$$C = [f(\tau)]1 = a0 [1]1 + a1 [\tau]1 + a2 [\tau^2]1 + \cdots + ad [\tau^d]_1$$

這實際上是將多項式係數與 SRS 點的線性組合。承諾大小僅為一個 $\mathbb{G}_1$ 點（48-48 位元組）。

1.2.3 開放證明的推導

假設我們需要證明 $f(z) = y$。觀察到：

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

其中 $q(x) = \frac{f(x) - y}{x - z}$ 是多項式除法的商。

因此，開放證明需要：

計算商多項式 $q(x)$
承諾 $[q(\tau)]_1$

令 $w(x) = f(x) - y$，則：

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

多項式除法的計算複雜度為 $O(d)$。

1.2.4 驗證協議

驗證者收到：

承諾 $C$
點 $z$ 和聲稱值 $y$
開放證明 $[q(\tau)]_1$

驗證者檢查配對等式：

$$e\left(C - [y]1, [\tau]2\right) \stackrel{?}{=} e\left([q(\tau)]1, [\tau - z]2\right)$$

數學推導：若 $f(z) = y$，則：

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

在 $\mathbb{G}_1$ 中：

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

兩邊左乘配對：

$$e\left([f(\tau) - y]1, G2\right) = e\left([q(\tau)]1, [\tau - z]2\right)$$

展開左邊：

$$e\left([f(\tau)]1, G2\right) - e\left([y]1, G2\right) = e\left([q(\tau)]1, [\tau]2 - [z]_2\right)$$

利用雙線性性質 $e([a]1, [b]2) = e(G1, G2)^{ab}$：

$$e(G1, G2)^{f(\tau) - y} = e(G1, G2)^{q(\tau) \cdot (\tau - z)}$$

因此等式成立的條件是：

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

即 $f(z) = y$。

1.3 KZG 承諾的批量開放大學

當需要同時開放大多個點時，可以顯著優化效率。

批量開放大學：假設需要驗證 $k$ 個點 $z1, z2, \ldots, zk$ 對應值 $y1, y2, \ldots, yk$。

定義：

$$W(x) = \sum{i=1}^{k} \alpha^i \cdot \frac{f(x) - yi}{x - z_i}$$

其中 $\alpha$ 是驗證者選擇的隨機挑戰。

然後只需一個開放大學 $\piW$，驗證者計算每個 $f(zi)$ 並檢查。

1.4 KZG 在以太坊中的應用

1.4.1 EIP-4844 Blob 承諾

EIP-4844 將交易資料以 Blob 形式存儲在區塊中。每個 Blob 包含約 4096 個場（field element），編碼為有限域 $\mathbb{F}_p$ 上的向量。

承諾計算流程：

# 將 Blob 視為多項式
# 設 blob = [f_0, f_1, ..., f_{n-1}]，其中 n = 4096
# 構造多項式 f(x) = Σ f_i · L_i(x)
# 其中 L_i(x) 是拉格朗日基底多項式

def compute_blob_commitment(blob, srs):
    """
    計算 Blob 的 KZG 承諾
    blob: List[FieldElement]  # 4096 個元素
    srs: StructuredReferenceString  # 預先生成的 SRS
    """
    n = len(blob)
    
    # 計算每個拉格朗日基底在 τ 處的值
    lagrange_basis_at_tau = compute_lagrange_basis(srs.g1_powers, n)
    
    commitment = G1Point.identity()
    for i, value in enumerate(blob):
        commitment = commitment + lagrange_basis_at_tau[i] * value
    
    return commitment

資料可用性抽樣（Data Availability Sampling）：

class BlobDataAvailability:
    """
    KZG 承諾支援高效的数据可用性抽樣
    每個客戶端只需下載少量樣本即可驗證數據可用性
    """
    
    def sample(self, commitment, num_samples=16):
        """
        抽樣驗證數據可用性
        """
        # 選擇隨機抽樣點
        sample_indices = self.select_random_indices(num_samples)
        
        # 對每個抽樣點獲取數據和開放大學
        proofs = []
        for idx in sample_indices:
            value = self.get_blob_value(idx)
            proof = self.get_opening_proof(idx)
            proofs.append((idx, value, proof))
        
        return proofs
    
    def verify_samples(self, commitment, samples):
        """
        驗證抽樣
        只需 16 個樣本即可高概率確認全部數據可用
        """
        for idx, value, proof in samples:
            if not verify_kzg_opening(commitment, idx, value, proof):
                return False
        return True

1.4.2 Verkle 樹中的 KZG 承諾

Verkle 樹使用 KZG 承諾替代傳統的 Merkle 哈希：

class VerkleNode:
    """
    Verkle 樹節點
    每個節點存儲子節點值的 KZG 承諾
    """
    
    def __init__(self, width=256):
        self.width = width
        self.children = [None] * width
        self.commitment = None
    
    def insert(self, key, value):
        """插入鍵值對"""
        # 將 key 拆分為路徑
        path = self.key_to_path(key)  # 輸出 width 進制的路徑
        
        if len(path) == 0:
            self.commitment = self.commit_value(value)
        else:
            child_index = path[0]
            if self.children[child_index] is None:
                self.children[child_index] = VerkleNode(self.width)
            
            self.children[child_index].insert(path[1:], value)
            self.commitment = self.commit_subtree()
    
    def commit_subtree(self):
        """
        承諾整個子樹
        使用 KZG 承諾
        """
        # 收集所有子節點承諾
        child_commitments = []
        for i in range(self.width):
            if self.children[i] is not None:
                child_commitments.append(self.children[i].commitment)
            else:
                child_commitments.append(Commitment.zero())
        
        # 構造多項式並承諾
        polynomial = self.commitments_to_polynomial(child_commitments)
        return kzg_commit(polynomial)

1.5 KZG 承諾的學術參考

論文標題	作者	年份	核心貢獻
"Polynomial Commitments"	Kate, Zaverucha, Goldberg	2010	KZG 方案原創
"Constant-Size Commitments to Polynomials and Their Applications"	Kate, Goldberg	2010	批量開放大學
"Short Pairing-Based Non-Interactive Zero-Knowledge Proofs"	Groth	2010	配對基礎的 ZK 系統
"Practical SNARKs for Verification of Computation"	Ben-Sasson et al.	2013	Groth-Sahai 證明的實際應用

二、PLONK 證明系統深度解析

2.1 PLONK 概述

PLONK（Permutations over Lagrange-bases for Occult Non-interactive Arguments of Knowledge）是 2019 年由 Gabizon、Williamson 和 Ciobotaru 提出的通用零知識證明系統。PLONK 的核心創新包括：

通用且可更新的信任設置：不同於 Groth16 需要電路特定的 trusted setup，PLONK 只需一個電路大小上限的設置。

定制約束系統：PLONK 使用「自定義門」和「複製約束」的靈活架構。

多項式承諾架構：PLONK 的核心是對多項式進行約束和承諾。

2.2 PLONK 電路結構

PLONK 將計算轉換為由「門」（gates）和「線」（wires）構成的電路。

2.2.1 門約束

PLONK 使用三種基本門類型：

加法門：$qL \cdot a + qR \cdot b + qO \cdot c + qM \cdot a \cdot b + q_C = 0$

其中：

$a, b$ 是左輸入和右輸入
$c$ 是輸出
$qL, qR, qO, qM, q_C$ 是選擇器係數（selector coefficients）

乘法門：當 $qM = 1, qL = qR = qO = q_C = 0$ 時約束為 $a \cdot b = c$

常量門：當 $qL = 1, qM = qR = qO = 0$ 時約束為 $a + qC = 0$，即 $a = -qC$

2.2.2 複製約束

複製約束用於連接不同門的輸入/輸出，實現變數的重複使用。

class PlonkCircuit:
    """
    PLONK 電路結構
    """
    
    def __init__(self, num_gates, num_inputs):
        self.num_gates = num_gates
        self.num_inputs = num_inputs
        self.total_wires = num_gates * 3 + num_inputs  # 每個門3個wire + 公開輸入
        
        # 門約束選擇器
        self.q_left = [0] * num_gates
        self.q_right = [0] * num_gates
        self.q_output = [0] * num_gates
        self.q_mult = [0] * num_gates
        self.q_constant = [0] * num_gates
        
        # 複製約束
        self.copy_constraints = []
        
        # 公開輸入
        self.public_inputs = [0] * num_inputs
    
    def add_gate(self, gate_type, left_wire, right_wire, output_wire, constant=0):
        """
        添加門約束
        """
        idx = len(self.q_left)
        
        if gate_type == 'add':
            self.q_left[idx] = 1
            self.q_right[idx] = 1
            self.q_output[idx] = -1
            self.q_constant[idx] = constant
        elif gate_type == 'mul':
            self.q_mult[idx] = 1
            self.q_output[idx] = -1
        elif gate_type == 'constant':
            self.q_left[idx] = 1
            self.q_constant[idx] = -constant
        
        # 記錄wire連接
        # ...
    
    def copy(self, wire_a, wire_b):
        """
        添加複製約束：wire_a = wire_b
        """
        self.copy_constraints.append((wire_a, wire_b))

2.2.3 完整加法-乘法電路示例

def build_circuit_compute_z(x, y):
    """
    構造計算 z = (x + 2) * (y + 3) 的 PLONK 電路
    
    電路結構：
    gate_0: a_0 + 2 = t_0  (常數加法)
    gate_1: a_1 + 3 = t_1  (常數加法)
    gate_2: t_0 * t_1 = z  (乘法)
    
    變數映射：
    - a_0 = x (公開輸入)
    - a_1 = y (公開輸入)
    - t_0 = x + 2
    - t_1 = y + 3
    - z = (x + 2) * (y + 3)
    """
    circuit = PlonkCircuit(num_gates=3, num_inputs=2)
    
    # 門0：x + 2
    circuit.add_gate('add', left_wire=0, right_wire=None, output_wire=2, constant=2)
    
    # 門1：y + 3
    circuit.add_gate('add', left_wire=1, right_wire=None, output_wire=3, constant=3)
    
    # 門2：(x+2) * (y+3)
    circuit.add_gate('mul', left_wire=2, right_wire=3, output_wire=4)
    
    # 複製約束（實際電路中隱式處理）
    # wire_0 -> gate_0 的左輸入
    # wire_1 -> gate_1 的左輸入
    
    return circuit

2.3 PLONK 約束的數學推導

2.3.1 門約束多項式

對於包含 $n$ 個門的電路，定義以下多項式：

選擇器多項式：

$$qL(x) = \sum{i=0}^{n-1} qL[i] \cdot Li(x)$$

其中 $L_i(x)$ 是拉格朗日基底多項式：

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

其中 $\omega$ 是 $n$ 次單位根。

線多項式（每個見證值對應一個多項式）：

$$a(x) = \sum{i=0}^{n-1} ai \cdot L_i(x)$$

門約束可以寫成一個多項式等式：

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

約束成立的條件是：$g(\omega^i) = 0$ 對所有 $i = 0, 1, \ldots, n-1$。

2.3.2 複製約束的處理

複製約束將變數「連接」在一起。設複製約束形成置換 $\sigma$，定義置換多項式：

$$Z(x) = \prod{i=0}^{n-1} (x - \omega^i)^{vi}$$

其中 $v_i$ 是第 $i$ 個位置被使用的次數。

置換論證：PLONK 使用「grand product」論證驗證複製約束。

定義：

$$Z{\sigma}(x) = \prod{i=0}^{n-1} \frac{(x - \omega^i)}{(x - \sigma(\omega^i))}$$

可以證明，當 $Z_{\sigma}(\omega) = 1$ 時，複製約束成立。

2.4 PLONK 協議流程

2.4.1 承諾階段

Prover 輸入：(public_input, witness)
Prover 輸出：對多個多項式的承諾

步驟 1：計算所有門的見證值
   根據電路結構和公開輸入，計算每個門的所有線值

步驟 2：構造並承諾線多項式
   a(x), b(x), c(x) - 分別承諾
   計算商多項式並承諾

步驟 3：處理複製約束
   計算置換論證的 Z 多項式並承諾

2.4.2 挑戰階段

Verifier 發送隨機挑戰：

$x \in \mathbb{F}_p$：用於打開多項式
$\alpha \in \mathbb{F}_p$：用於約束線性化
$\beta, \gamma \in \mathbb{F}_p$：用於複製約束

2.4.3 開放大學

Prover 根據挑戰計算並開放大學：

def prover_protocol(circuit, witness, public_inputs, srs):
    """
    PLONK 證明者算法
    """
    n = circuit.num_gates
    
    # 1. 構造線多項式
    a_poly = Polynomial([witness.a[i] for i in range(n)])
    b_poly = Polynomial([witness.b[i] for i in range(n)])
    c_poly = Polynomial([witness.c[i] for i in range(n)])
    
    # 2. 承諾
    commit_a = kzg_commit(a_poly, srs)
    commit_b = kzg_commit(b_poly, srs)
    commit_c = kzg_commit(c_poly, srs)
    
    # 3. 計算置換論證
    Z_poly = compute_permutation_argument(a_poly, b_poly, c_poly, circuit.copy_constraints)
    commit_z = kzg_commit(Z_poly, srs)
    
    # 4. 接收驗證者挑戰
    beta, gamma = receive_challenges()
    
    # 5. 計算約束多項式
    # f(x) = q_L(x)a(x) + q_R(x)b(x) + q_O(x)c(x) + q_M(x)a(x)b(x) + q_C(x)
    # + (beta * x + gamma) * (a(x) + beta * sigma_a(x) + gamma) * ...
    
    constraint_poly = compute_constraint_poly(circuit, a_poly, b_poly, c_poly, 
                                              beta, gamma, sigma_poly)
    
    # 6. 計算商多項式
    Z_H(x) = x^n - 1
    quotient_poly = constraint_poly / Z_H(x)
    
    # 7. 承諾商多項式（分成多個部分）
    commit_t1, commit_t2, commit_t3 = split_and_commit(quotient_poly, srs)
    
    # 8. 接收驗證者隨機點 x
    x = receive_random_point()
    
    # 9. 計算並開放大學
    opening_proof = compute_opening_proof(a_poly, b_poly, c_poly, Z_poly, 
                                         t_polys, x, srs)
    
    return {
        'commit_a': commit_a,
        'commit_b': commit_b,
        'commit_c': commit_c,
        'commit_z': commit_z,
        'commit_t': [commit_t1, commit_t2, commit_t3],
        'opening_proof': opening_proof
    }

2.5 PLONK 的學術意義與實作

特性	PLONK	Groth16
信任設置	通用且可更新	電路特定
證明大小	~400 bytes	~128 bytes
驗證時間	O(1) 配對	O(1) 配對
證明時間	O(n log n)	O(n)
SRS 大小	O(n)	O(n)

PLONK 的實際實現包括：

Aztec Network 的 Noir 語言：使用 PLONK 作為後端
Zcash Halo：PLONK 的遞歸版本
Polygon Miden：基於 PLONK 的 zkEVM

2.6 PLONK 的學術參考

論文標題	作者	年份	核心貢獻
"PLONK: Permutations over Lagrange-bases for Oc- cert Non-interactive Arguments of Knowledge"	Gabizon et al.	2019	PLONK 原創
"Halo: Practical Homomorphic Lightweight Commitments"	Bootle et al.	2019	遞歸證明基礎
"Proof-Carrying Data from Accumulation Schemes"	Bunz et al.	2020	增量承諾

三、HALO2 遞歸證明系統

3.1 HALO2 概述

HALO2 是 Zcash 基金會開發的零知識證明系統，其核心創新是「增量承諾」（Accumulation）和「非同步遞歸」（Non-succinct Recursion）。HALO2 的設計目標是：

無需可信設置：完全透明化的設置
遞歸友好：支援高效的自引用證明
增量計算：透過 Accumulation 實現高效驗證

3.2 Accumulation 機制

3.2.1 問題動機

傳統零知識證明（如 Groth16）的驗證需要昂貴的配對運算。對於嵌套證明（如區塊鏈的遞歸驗證），這變得不可行。

傳統遞歸的問題：

驗證 SNARK 證明需要：
1. 驗證多個配對方程
2. 每個配對：~500ms（硬體優化後）
3. 若要驗證 1000 個嵌套證明：~500 秒

3.2.2 Accumulation 解決方案

HALO2 的核心思想是「增量驗證」：將驗證狀態儲存在承諾中，而非每次都重新驗證。

Accumulator 結構：

class Accumulator:
    """
    增量承諾累積器
    """
    
    def __init__(self):
        # 累積的虛擬機器狀態承諾
        self.vstate_commitment = None
        # 待處理的證明列表
        self.pending_proofs = []
    
    def accumulate(self, proof, verification_key):
        """
        增量累積一個新的證明
        """
        # 驗證證明（增量式）
        verified = self.incremental_verify(proof, verification_key)
        assert verified
        
        # 更新累積器狀態
        self.pending_proofs.append(proof)
        self.vstate_commitment = self.update_commitment(
            self.vstate_commitment, 
            proof
        )
    
    def get_accumulator(self):
        """
        返回累積器承諾
        可用於驗證所有已累積的證明
        """
        return self.vstate_commitment

數學推導：

設 $Ci$ 是第 $i$ 步的累積器承諾，$Pi$ 是第 $i$ 個證明。

累積更新公式：

$$C{i+1} = \text{Compress}(Ci, P_i)$$

其中 $\text{Compress}$ 是某個確定性的壓縮函數。

關鍵特性：

驗證 $n$ 個證明只需驗證最後一個累積器
每步驗證成本與單個證明相同
總成本從 $O(n)$ 降至 $O(1)$

3.3 HALO2 電路設計

3.3.1 區域佈局（Region Layout）

HALO2 的電路由「區域」（regions）組成，每個區域定義一個子電路。

class Halo2Chip:
    """
    HALO2 晶片設計
    """
    
    def configure(config):
        """
        配置晶片參數
        """
        return ChipConfig(
            inputs=256,
            degree=3,
            lookup_uses_simd=True,
            rotation_of_default_assigned=0
        )
    
    def expose_public(self, region, value, column, offset):
        """
        將值暴露為公開輸入
        """
        # ...
    
    def assign_table(self, lookup_table):
        """
        分配查找表
        """
        # ...

3.3.2 約束系統

HALO2 使用三種類型的約束：

普通約束：$qL \cdot a + qR \cdot b + qO \cdot c + qM \cdot a \cdot b + q_C = 0$

查找約束：利用查找表實現高效電路

排列約束：類似 PLONK 的複製約束

class PlonkConfig:
    """
    PLONK 約束配置
    """
    def __init__(self, selectors, fixed, advice, instance):
        self.q_l = selectors['q_l']
        self.q_r = selectors['q_r']
        self.q_o = selectors['q_o']
        self.q_m = selectors['q_m']
        self.q_c = selectors['q_c']
        self.q_lookup = selectors['q_lookup']
        
        self.fixed = fixed      # 固定列（電路配置）
        self.advice = advice    # advice 列（Prover witness）
        self.instance = instance  # 實例列（公開輸入）

3.4 HALO2 遞歸證明

3.4.1 遞歸證明的原理

遞歸證明允許將「驗證某個陳述的證明」作為電路的輸入，從而實現無限深度的證明組合。

class RecursiveProof:
    """
    HALO2 遞歸證明結構
    """
    
    def prove_recursive(self, inner_circuit, inner_instance, inner_proof, outer_circuit):
        """
        構造遞歸證明：證明"存在一個對 inner_circuit 的有效證明"
        
        這意味著：
        1. outer_circuit 將 inner_proof 作為 witness
        2. outer_circuit 執行 inner_proof 的驗證邏輯
        3. outer_proof 證明"inner_proof 驗證成功"
        """
        
        # 1. 準備內層電路的實例
        inner_instance_commitment = hash(inner_instance)
        
        # 2. 在外層電路中驗證內層證明
        outer_circuit.assign_proof(inner_proof)
        outer_circuit.constrain_verification(inner_proof, inner_instance_commitment)
        
        # 3. 構造外層證明
        outer_proof = outer_circuit.prove(outer_circuit.witness)
        
        return outer_proof

3.4.2 實際應用：區塊鏈驗證

class BlockVerificationCircuit:
    """
    驗證區塊狀態轉換的 HALO2 電路
    """
    
    def __init__(self):
        self.config = Halo2Chip.configure(...)
    
    def load_previous_state(self, state_commitment):
        """
        載入前一區塊狀態的承諾
        """
        self.assign('prev_state', state_commitment)
    
    def load_block(self, block_header, transactions):
        """
        載入新區塊數據
        """
        self.assign('block_number', block_header.number)
        self.assign('timestamp', block_header.timestamp)
        
        for i, tx in enumerate(transactions):
            self.assign_tx(i, tx)
    
    def verify_state_transition(self):
        """
        驗證狀態轉換的正確性
        """
        # 執行每筆交易
        for i in range(len(self.transactions)):
            self.execute_tx(i)
        
        # 驗證狀態根
        prev_state = self.get('prev_state')
        new_state = self.compute_merkle_root(self.state_tree)
        
        # 約束：new_state = update(prev_state, transactions)
        self.assert_equal(new_state, self.get('expected_state'))
    
    def prove(self, prev_state_commitment, block):
        """
        構造區塊驗證證明
        """
        self.load_previous_state(prev_state_commitment)
        self.load_block(block)
        self.verify_state_transition()
        
        return self.generate_proof()

3.5 HALO2 與其他系統的比較

特性	PLONK	HALO2	Starknet
信任設置	通用可更新	無需信任	無需信任
遞歸支援	理論支援	原生支援	有限支援
電路靈活性	高	高	中
驗證者效率	O(1)	O(1)	O(log n)
證明大小	~400 bytes	~600 bytes	~100 KB

3.6 HALO2 的學術參考

論文標題	作者	年份	核心貢獻
"Halo: Practical Lightweight Zero-Knowledge Commitments"	Bootle et al.	2019	HALO 原創
"Proof-Carrying Data without Succinct Verification"	Bowe et al.	2019	增量驗證
"Recursive Proof Composition"	Bootle et al.	2019	遞歸證明基礎

四、工程實踐：從電路設計到部署

4.1 電路開發流程

┌─────────────────────────────────────────────────────────────────┐
│                    零知識電路開發流程                              │
├─────────────────────────────────────────────────────────────────┤
│                                                                  │
│  1. 規格定義                                                     │
│     └─> 定義要證明的計算陳述                                      │
│                                                                  │
│  2. 電路設計                                                     │
│     └─> 將計算轉換為門約束和複製約束                              │
│                                                                  │
│  3. 見證生成                                                     │
│     └─> Prover 計算所有門的輸入輸出值                             │
│                                                                  │
│  4. 約束系統                                                     │
│     └─> 定義多項式約束                                            │
│                                                                  │
│  5. 承諾階段                                                     │
│     └─> 對多項式進行 KZG 承諾                                    │
│                                                                  │
│  6. 挑戰-回應                                                   │
│     └─> 與 Verifier 交互                                         │
│                                                                  │
│  7. 開放大學                                                     │
│     └─> 最終開放大學                                            │
│                                                                  │
└─────────────────────────────────────────────────────────────────┘

4.2 實際電路範例：範圍證明

from halo2 import Halo2, Circuit, plonk

class RangeProofCircuit(Circuit):
    """
    範圍證明電路
    證明：a ≤ x ≤ b
    """
    
    class Config:
        """
        電路配置
        """
        def __init__(self, num_bits):
            self.num_bits = num_bits
            self.lookup = True  # 啟用查找表
    
    def circuit(self, config,PUBLIC):
        """
        電路主體
        """
        # 1. 分配見證值
        x = config.assign_advice('x', self.x)
        a = config.assign_instance('a', self.a)
        b = config.assign_instance('b', self.b)
        
        # 2. 約束：x - a ≥ 0
        diff_low = self.subtract(x, a)
        self.range_check(diff_low, config, max_bits=self.num_bits)
        
        # 3. 約束：b - x ≥ 0
        diff_high = self.subtract(b, x)
        self.range_check(diff_high, config, max_bits=self.num_bits)
    
    def range_check(self, value, config, max_bits):
        """
        範圍檢查：value 在 [0, 2^max_bits) 範圍內
        """
        # 使用查找表實現位元檢查
        for i in range(max_bits):
            bit = self.extract_bit(value, i)
            # 約束：bit 必須是 0 或 1
            config.constrain(bit * (1 - bit) == 0)

4.3 電路優化技巧

4.3.1 查找表優化

class LookupOptimization:
    """
    查找表優化示例
    將昂貴的運算替換為查找表
    """
    
    def optimize_xor(self, a, b, num_bits=8):
        """
        使用查找表實現 XOR
        原本需要 8 個 AND + NOT 門
        使用查找表只需 1 次查找
        """
        # 預先計算 XOR 表
        xor_table = [a ^ b for a in range(2**4) for b in range(2**4)]
        
        # 使用查表而非門約束
        return self.lookup(xor_table, [a[:4], b[:4]])
    
    def optimize_merkle_root(self, path, depth=32):
        """
        Merkle 路徑驗證的查找表優化
        """
        # 將配對操作替換為查找表
        concat_table = self.precompute_hash_pairs(path, depth)
        
        # 使用查找表驗證
        for i in range(depth):
            left = self.lookup(concat_table, [path[i].sibling, path[i].direction])
            path[i+1] = self.hash(left, path[i].node)

4.3.2 複製約束優化

class CopyConstraintOptimization:
    """
    複製約束的批量優化
    """
    
    def batch_copy(self, wires_a, wires_b):
        """
        批量添加複製約束
        電路自動處理排列論證
        """
        # 只需一行代碼，底層自動生成 Z 多項式
        self.copy(wires_a, wires_b)
    
    def copy_with_permutation(self, groups):
        """
        對多個變數組進行置換約束
        組內可以任意排列
        """
        for group in groups:
            self.copy_permutation(group)

4.4 性能基準測試

def benchmark_circuits():
    """
    不同電路的性能基準測試
    """
    results = {}
    
    # 1. 範圍證明
    start = time.time()
    proof = prove_range(64)  # 64 位元範圍
    elapsed = time.time() - start
    results['range_proof_64bit'] = {'prove_time': elapsed, 'proof_size': len(proof)}
    
    # 2. Merkle 驗證
    start = time.time()
    proof = prove_merkle_verify(32)  # 32 層
    elapsed = time.time() - start
    results['merkle_verify_32'] = {'prove_time': elapsed, 'proof_size': len(proof)}
    
    # 3. 聚合簽名驗證
    start = time.time()
    proof = prove_aggregate_verify(100)  # 100 個簽名
    elapsed = time.time() - start
    results['agg_verify_100'] = {'prove_time': elapsed, 'proof_size': len(proof)}
    
    return results

# 基準測試結果（代表性數據）
"""
| 電路類型           | 約束數量 | 證明時間 | 驗證時間 | 證明大小 |
|-------------------|---------|---------|---------|---------|
| 範圍證明 (64 位)   | ~500    | ~0.5s   | ~3ms    | ~400B   |
| Merkle 驗證 (32)   | ~2,000  | ~2s     | ~3ms    | ~400B   |
| 聚合簽名 (100)     | ~50,000 | ~30s    | ~3ms    | ~400B   |
| SHA256 壓縮        | ~30,000 | ~20s    | ~3ms    | ~400B   |
"""

五、應用場景與實戰案例

5.1 zkEVM 中的電路設計

class ZkEvmCircuit:
    """
    zkEVM 的核心電路設計
    證明：EVM 執行結果的正確性
    """
    
    def execute_opcode(self, opcode, stack, memory):
        """
        執行單個 EVM 操作碼
        """
        if opcode == 'ADD':
            # 約束：a + b = c
            a = stack.pop()
            b = stack.pop()
            c = (a + b) % 2**256
            stack.push(c)
            
            self.constrain_eq(
                self.add(a, b),
                c
            )
        
        elif opcode == 'MUL':
            # 約束：a * b = c
            a = stack.pop()
            b = stack.pop()
            c = (a * b) % 2**256
            stack.push(c)
            
            self.constrain_eq(
                self.mul(a, b),
                c
            )
        
        elif opcode == 'SSTORE':
            # 約束：storage[key] = value
            key = stack.pop()
            value = stack.pop()
            
            # 更新狀態承諾
            new_root = self.update_storage(self.state_root, key, value)
            self.state_root = new_root
    
    def prove_execution(self, transactions):
        """
        構造交易執行的證明
        """
        self.initialize_state()
        
        for tx in transactions:
            self.load_transaction(tx)
            
            for opcode in tx.code:
                self.execute_opcode(opcode, self.stack, self.memory)
            
            self.update_state(tx)
        
        return self.generate_proof()

5.2 私有交易驗證

class PrivateTransactionProof:
    """
    私有交易的零知識證明
    證明：
    1. 發送者有足夠餘額
    2. 接收者地址有效
    3. 交易金額正確
    同時不暴露：
    - 發送者身份
    - 接收者身份
    - 交易金額
    """
    
    def prove_private_transfer(self, sender_balance, recipient, amount, 
                                commitment_tree, nullifier):
        """
        構造私有轉帳證明
        """
        circuit = PlonkCircuit(...)
        
        # 1. 驗證發送者餘額承諾存在
        sender_commitment = compute_commitment(sender_balance)
        circuit.constrain_exists_in_tree(
            sender_commitment,
            commitment_tree
        )
        
        # 2. 驗證 nullifier 的正確性
        # nullifier = hash(sender_secret, nonce)
        computed_nullifier = circuit.poseidon(
            sender_secret,
            nonce
        )
        circuit.constrain_eq(nullifier, computed_nullifier)
        
        # 3. 驗證轉帳後餘額非負
        new_balance = sender_balance - amount
        circuit.constrain_gte(new_balance, 0)
        
        # 4. 生成接收者承諾
        recipient_commitment = circuit.poseidon(recipient)
        
        # 5. 生成新的餘額承諾
        new_sender_commitment = circuit.poseidon(new_balance)
        new_recipient_commitment = circuit.poseidon(amount + recipient_balance)
        
        return circuit.prove()

六、總結與展望

6.1 技術發展趨勢

硬體加速：GPU/FPGA 加速證明生成，降低計算成本
遞歸證明聚合：多個證明聚合為單一證明
透明化設置：擺脫可信設置的限制
量子抗性：評估後量子替代方案

6.2 以太坊路線圖

根據以太坊基金會的規劃：

短期：Proto-Danksharding（EIP-4844）已部署，使用 KZG 承諾
中期：Full Danksharding 需要更高效的 KZG 批量開放大學
長期：與 PLONK/HALO2 類似的通用零知識電路將用於：
zkEVM 全面部署
私有智慧合約
去中心化身份驗證

6.3 學術論文索引

主題	關鍵論文	發表場所
KZG 承諾	"Polynomial Commitments" (Kate et al., 2010)	IACR CHES
PLONK	"PLONK" (Gabizon et al., 2019)	ePrint
HALO2	"Halo" (Bootle et al., 2019)	IEEE S&P
累積方案	"Proof-Carrying Data" (Bunz et al., 2020)	IEEE S&P
ZK 電路優化	"TurboPLONK" (ZKSync)	白皮書
zkEVM	"zkEVM Architecture" (Polygon, 2022)	白皮書

結論

KZG 承諾、PLONK 和 HALO2 構成了現代零知識證明系統的三大支柱。KZG 提供高效的多項式承諾機制；PLONK 的通用性和可更新設置使其成為工業應用的首選；HALO2 的增量驗證機制開啟了無限遞歸證明的大門。

理解這些技術的數學基礎對於：

L2 開發者：選擇適合的 zk 技術棧
安全研究者：評估電路的安全性假設
研究者：跟進零知識證明的最新進展

至關重要。隨著硬體加速和算法優化的持續進步，零知識證明將在區塊鏈隱私和擴容領域發揮越來越重要的作用。

數學符號表

符號	含義
$\mathbb{F}_p$	質數 $p$ 上的有限域
$e(\cdot, \cdot)$	雙線性配對
$[x]1, [x]2$	橢圓曲線點表示
$G1, G2$	配對群生成元
$\tau$	SRS 秘密值
$L_i(x)$	拉格朗日基底多項式
$Z_H(x)$	多項式 $x^n - 1$
$\omega$	$n$ 次單位原根

ZK Rollup 電路設計數學推導完整指南：從代數電路到 STARK/SNARK 證明系統的工程實踐 — 本文從密碼學數學基礎出發，系統性地推導代數電路（Arithmetic Circuits）、約束系統（Constraint Systems）、多項式承諾（Polynomial Commitments）等核心概念。深入分析 SNARK（Groth16、PLONK）和 STARK（FRI 協議）兩大主流證明系統的數學推導與工程實現差異。提供完整的數學公式推導、實際的電路設計範例（餘額轉帳、Merkle 樹更新、zkEVM）、以及電路優化策略。涵蓋 2026 年最新的 ZK Rollup 技術發展。
零知識證明完整技術指南：從基礎密碼學到以太坊應用實踐 — 零知識證明是現代密碼學最革命性的發明之一，允許一方在不透露任何額外信息的情況下向另一方證明某陳述的正確性。本文深入探討零知識證明的數學基礎、主流技術方案（zk-SNARKs、zk-STARKs、PLONK）、以及在以太坊生態系統中的實際應用，包括 ZK Rollup 技術架構、隱私保護應用與開發實踐。我們將從密碼學原語出發，逐步構建完整的零知識證明知識體系。
HALO2 與 PLONK 家族零知識證明系統深度工程實作指南：折疊方案、遞迴證明與電路設計實務 — HALO2 由 Electric Coin Company（Zcash 團隊）開發，其創新性地採用了「折疊方案」（Folding Scheme）來實現無需可信設置的遞迴證明組合。PLONK 及其衍生協議（UltraPLONK、TurboPLONK、Plonky2）則以其通用性和效率聞名。本文深入分析 HALO2 協議的核心原理、PLONK 家族的數學推導、以及實際電路設計的工程細節。涵蓋 IVC 增量可驗證計算、PLONK 置換論證與門約束系統、折疊方案數學推導、IPA 內積論證、HALO2 電路結構與約束定義、Rust HALO2 電路開發實務、PLONK 變體分析（UltraPLONK 查找表、Plonky2 Goldilocks 域優化）、以及 zkSync、Aztec 等項目的實際應用案例。同時探討電路安全性陷阱、驗證器安全最佳實踐與形式化驗證方法。
ZK-SNARKs 與 ZK-STARKs 以太坊實戰應用完整指南：從理論到部署的工程實踐 — 零知識證明技術在以太坊生態系統中的應用已從理論走向大規模實際部署。本文深入探討 ZK-SNARKs 和 ZK-STARKs 兩大主流證明系統在以太坊上的實際應用案例，提供可直接部署的智慧合約程式碼範例，涵蓋隱私交易、身份驗證、批量轉帳、AI 模型推理驗證等完整實作。
以太坊 Rollup 風險量化分析完整指南：從基礎風險模型到壓力測試框架 — Rollup 是以太坊 Layer 2 擴容策略的核心技術方案，TVL 已超過 500 億美元。然而 Rollup 技術架構的複雜性帶來了多維度的風險挑戰，包括智能合約漏洞、排序器中心化風險、數據可用性故障、以及跨層橋接風險等。本文從量化分析的視角，深入探討 Rollup 協議的風險模型建立方法、風險因子量化評估、以及壓力測試框架設計。

延伸閱讀與來源

Ethereum.org Developers 官方開發者入口與技術文件
EIPs 以太坊改進提案完整列表
Solidity 文檔智慧合約程式語言官方規格
EVM 代碼庫 EVM 實作的核心參考
Alethio EVM 分析 EVM 行為的正規驗證

這篇文章對您有幫助嗎？

請告訴我們如何改進：

0 人覺得有帮助

KZG 承諾、PLONK 與 HALO2 電路設計數學推導完整指南：從多項式承諾到零知識電路的工程實踐

概述

一、KZG 多項式承諾的密碼學基礎

1.1 多項式承諾的定義與動機

1.2 KZG 承諾的數學推導

1.2.1 信任設置（Trusted Setup）

1.2.2 承諾生成

1.2.3 開放證明的推導

1.2.4 驗證協議

1.3 KZG 承諾的批量開放大學

1.4 KZG 在以太坊中的應用

1.4.1 EIP-4844 Blob 承諾

1.4.2 Verkle 樹中的 KZG 承諾

1.5 KZG 承諾的學術參考

二、PLONK 證明系統深度解析

2.1 PLONK 概述

2.2 PLONK 電路結構

2.2.1 門約束

2.2.2 複製約束

2.2.3 完整加法-乘法電路示例

2.3 PLONK 約束的數學推導

2.3.1 門約束多項式

2.3.2 複製約束的處理

2.4 PLONK 協議流程

2.4.1 承諾階段

2.4.2 挑戰階段

2.4.3 開放大學

2.5 PLONK 的學術意義與實作

2.6 PLONK 的學術參考

三、HALO2 遞歸證明系統

3.1 HALO2 概述

3.2 Accumulation 機制

3.2.1 問題動機

3.2.2 Accumulation 解決方案

3.3 HALO2 電路設計

3.3.1 區域佈局（Region Layout）

3.3.2 約束系統

3.4 HALO2 遞歸證明

3.4.1 遞歸證明的原理

3.4.2 實際應用：區塊鏈驗證

3.5 HALO2 與其他系統的比較

3.6 HALO2 的學術參考

四、工程實踐：從電路設計到部署

4.1 電路開發流程

4.2 實際電路範例：範圍證明

4.3 電路優化技巧

4.3.1 查找表優化

4.3.2 複製約束優化

4.4 性能基準測試

五、應用場景與實戰案例

5.1 zkEVM 中的電路設計

5.2 私有交易驗證

六、總結與展望

6.1 技術發展趨勢

6.2 以太坊路線圖

6.3 學術論文索引

結論

延伸閱讀

數學符號表

相關文章

延伸閱讀與來源

這篇文章對您有幫助嗎？

評論

發表評論