KZG 承諾代數驗證完整指南:從多項式承諾到以太坊 Blob 驗證

KZG 承諾是以太坊邁向去中心化與可擴展性的核心密碼學原語。本文從代數視角完整解析 KZG 承諾的密碼學原理、承諾生成與驗證的數學推導、以及在以太坊中的實際部署。讀者將深入理解為何 KZG 承諾能夠實現「大小固定、驗證快速」的承諾方案。

KZG 承諾代數驗證完整指南:從多項式承諾到以太坊 Blob 驗證

概述

KZG 承諾(Kate-Zaverucha-Goldberg 承諾)是以太坊邁向去中心化與可擴展性的核心密碼學原語。2024 年 3 月的 Cancun-Dencun 升級中,EIP-4844 正式引入 Blob 攜帶機制,使 KZG 承諾成為以太坊共識層與執行層的關鍵技術支柱。Blob 資料的可用性驗證、Proto-Danksharding 的實現、以及未來 Full Danksharding 的願景,都依賴於 KZG 承諾的數學特性與驗證效率。

本文從代數視角完整解析 KZG 承諾的密碼學原理、承諾生成與驗證的數學推導、以及在以太坊中的實際部署。讀者將深入理解為何 KZG 承諾能夠實現「大小固定、驗證快速」的承諾方案,以及其與其他多項式承諾方案(如 IPA、FRI)的技術權衡。


第一部分:多項式承諾的數學基礎

1.1 為什麼需要多項式承諾?

定義 1.1.1(承諾方案):

一個密碼學承諾方案包含兩個階段:

承諾階段:

揭示階段:

安全性要求:

┌─────────────────────────────────────────────────────────────┐
│                 承諾方案安全性要求                            │
├─────────────────────────────────────────────────────────────┤
│                                                               │
│  隱藏性(Hiding):                                          │
│  - 承諾 c 不洩露關於 x 的任何信息                            │
│  - 即使面對惡意驗證者也不能推斷 x                           │
│                                                               │
│  約束性(Binding):                                         │
│  - 承諾者無法將承諾改變為另一個值 x'                       │
│  - 即 commitment(x) = commitment(x') 意味着 x = x'          │
│                                                               │
│  額外特性(多項式承諾專有):                                 │
│  - 承諾者可以證明 f(z) = y                                  │
│  - 驗證者可在不揭示整個多項式的情況下驗證                    │
│                                                               │
└─────────────────────────────────────────────────────────────┘

定義 1.1.2(多項式承諾):

一個多項式承諾方案允許承諾者:

  1. 承諾一個多項式 $f(X)$
  2. 在稍後證明在某個點 $z$ 的值為 $f(z) = y$
  3. 驗證者可以檢查證明的正確性,無需看到整個多項式

1.2 KZG 承諾的直覺動機

問題:假設 $f(X)$ 是一個 $d$ 次多項式

KZG 承諾的核心思想:

┌─────────────────────────────────────────────────────────────┐
│                 KZG 承諾核心思想                             │
├─────────────────────────────────────────────────────────────┤
│                                                               │
│  承諾者:                                                     │
│  1. 將多項式 f(X) = Σ aᵢXⁱ 承諾                            │
│  2. 承諾 = g^{f(τ)} = Π g^{aᵢτⁱ}                           │
│     其中 τ 是秘密值                                          │
│                                                               │
│  證明者(證明 f(z) = y):                                    │
│  1. 計算商多項式 q(X) = (f(X) - y) / (X - z)                │
│  2. 承諾 q(X)                                                 │
│  3. 發送證明 π = g^{q(τ)}                                   │
│                                                               │
│  驗證者:                                                     │
│  1. 檢查 e(commit, g) = e(proof, τ - z) · e(g^y, g)        │
│  2. 這個等式在 τ 未知的情況下也可驗證!                      │
│                                                               │
└─────────────────────────────────────────────────────────────┘

1.3 雙線性配對的數學基礎

定義 1.3.1(雙線性配對):

設 $G1, G2, GT$ 為具有相同素數階 $p$ 的循環群。一個雙線性配對 $e: G1 \times G2 \to GT$ 滿足:

  1. 雙線性: $e(a \cdot g1, b \cdot g2) = e(g1, g2)^{ab}$
  1. 非退化: $e(g1, g2) \neq 1$
  1. 可計算: 存在高效算法計算 $e$

在 BN254 曲線上的實現:

以太坊使用的 BN254 曲線提供有效的配對計算:

BN254 配對參數:
- G₁: E(Fp) 上階為 p 的子群
- G₂: E'(Fp²) 上階為 p 的子群
- 配對: e: G₁ × G₂ → Gₜ

配對計算時間:~3ms(單次配對)

第二部分:KZG 承諾的完整代數推導

2.1 承諾生成

定理 2.1.1(KZG 承諾):

設 $f(X) = \sum{i=0}^{d} ai X^i$ 是一個 $d$ 次多項式,$g$ 是 $G_1$ 的生成元。KZG 承諾為:

$$c = [f(\tau)]1 = g^{f(\tau)} = g^{\sum{i=0}^{d} ai \tau^i} = \prod{i=0}^{d} ([ \tau^i ]1)^{ai}$$

其中 $\tau$ 是信任設置的秘密值。

推導:

給定信任設置:

$$SRS = ([\tau^0]1, [\tau^1]1, \ldots, [\tau^d]1, [\tau^0]2, \ldots)$$

承諾計算:

$$c = \prod{i=0}^{d} ([ \tau^i ]1)^{ai} = [\sum{i=0}^{d} ai \tau^i]1 = [f(\tau)]_1$$

2.2 證明生成:多項式除法視角

定理 2.2.1(開啟證明):

要證明 $f(z) = y$,我們需要計算:

$$q(X) = \frac{f(X) - y}{X - z}$$

這是有效的,因為 $f(z) = y$ 意味著 $(X - z)$ 整除 $(f(X) - y)$。

開啟證明:

$$\pi = [q(\tau)]_1 = g^{q(\tau)}$$

代碼實現:

"""
KZG 承諾方案實現
"""

from dataclasses import dataclass
from typing import List, Tuple

@dataclass
class KZGCommitment:
    """KZG 承諾方案"""
    # 信任設置(SRS)
    powers_of_tau: List[int]  # [τ⁰, τ¹, τ², ..., τ^d] 在 G₁ 中
    
    def commit(self, coefficients: List[int]) -> int:
        """
        承諾多項式 f(X) = Σ aᵢXⁱ
        
        返回:c = g^{f(τ)} = Π (τⁱ)^{aᵢ}
        """
        commitment = 0
        for i, coeff in enumerate(coefficients):
            # commitment += coeff * tau^i
            commitment += coeff * self.powers_of_tau[i]
        return commitment
    
    def open(self, coefficients: List[int], z: int, y: int) -> Tuple[int, int]:
        """
        開啟多項式在點 z 的值
        
        計算:
        q(X) = (f(X) - y) / (X - z)
        
        返回:(c, proof) 其中 c 是承諾,proof 是開啟證明
        """
        commitment = self.commit(coefficients)
        
        # 計算商多項式 q(X) 的係數
        # 使用多項式長除法
        quotient = self._polynomial_divide(coefficients, z, y)
        
        # 承諾 q(X)
        proof = self.commit(quotient)
        
        return commitment, proof
    
    def _polynomial_divide(
        self, 
        coeffs: List[int], 
        z: int, 
        y: int
    ) -> List[int]:
        """
        計算 (f(X) - y) / (X - z)
        
        其中 f(X) = Σ aᵢXⁱ
        
        恆等式:
        f(X) - y = (X - z) · q(X)
        
        比較係數可得:
        q(X) = Σ bᵢXⁱ
        其中 b_{d-1} = a_d
        b_{i-1} = a_i + z · b_i (從高次到低次)
        """
        d = len(coeffs) - 1
        quotient = [0] * d
        
        # 最高次係數直接複製
        quotient[d - 1] = coeffs[d]
        
        # 從高次到低次計算
        for i in range(d - 1, 0, -1):
            quotient[i - 1] = (coeffs[i] + z * quotient[i]) % self.p
        
        # 最後驗證 f(z) = y
        reconstructed_y = sum(coeffs[i] * (z ** i) for i in range(len(coeffs))) % self.p
        assert reconstructed_y == y, f"f(z) = {reconstructed_y}, expected {y}"
        
        return quotient

2.3 驗證等式的數學推導

定理 2.3.1(開啟驗證):

給定承諾 $c = [f(\tau)]1$、證明 $\pi = [q(\tau)]1$ 和點 $z$,驗證者檢查:

$$e(c / g^y, [\tau]2) = e(\pi, [\tau]2 / [z]_2)$$

數學推導:

由承諾生成和開啟證明定義:

$$c = g^{f(\tau)}, \quad \pi = g^{q(\tau)}, \quad y = f(z)$$

根據多項式除法:

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

將 $X = \tau$ 代入:

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

兩邊取 $g$ 的冪:

$$g^{f(\tau) - y} = g^{(\tau - z) \cdot q(\tau)}$$

$$g^{f(\tau)} \cdot g^{-y} = (g^{\tau})^{q(\tau)} \cdot (g^{z})^{-q(\tau)}$$

$$c \cdot g^{-y} = ([q(\tau)]1, [\tau]2) \cdot ([\tau - z]_2)^{-q(\tau)}$$

這給出配對等式:

$$e(c / g^y, [\tau]2) = e(\pi, [\tau - z]2)$$

驗證算法:

def verify_opening(
    commitment,
    y,
    z,
    proof,
    G1_generator,
    G2_generator,
    tau_G2,
    pairing
) -> bool:
    """
    驗證 KZG 開啟證明
    
    檢查:e(c / g^y, [τ]₂) = e(proof, [τ - z]₂)
    """
    # 左邊:e(c, [τ]₂) / e(g^y, [τ]₂)
    left = pairing(pairing(commitment, tau_G2), pairing(G1_generator, tau_G2) ** (-y))
    
    # 右邊:e(proof, [τ - z]₂)
    right = pairing(proof, tau_G2 - z * G2_generator)
    
    return left == right

2.4 多個開啟的批量驗證

定義 2.4.1(批量開啟):

假設要同時開啟 $k$ 個點 $z1, z2, \ldots, zk$,對應值為 $y1, y2, \ldots, yk$。

聚合證明技術:

定義聚合多項式:

$$A(X) = \prod{i=1}^{k} (X - zi)$$

定義目標多項式:

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

其中 $\alpha$ 是隨機挑战,$\alpha^i$ 是其冪。

單個聚合證明:

$$\pi{agg} = [q{agg}(\tau)]_1$$

其中:

$$q{agg}(X) = \sum{i=1}^{k} \alpha^i \cdot \frac{f(X) - yi}{X - zi}$$

驗證等式:

$$e(c \cdot g^{-\sum \alpha^i yi}, [\tau]2) = e(\pi{agg}, \prod{i=1}^{k} [\tau - zi]2)$$

效率改進:

方法配對數通信量
分別驗證 k 個$2k$$O(k)$
批量驗證$2$$O(1)$

第三部分:KZG 承諾在以太坊的應用

3.1 EIP-4844 Blob 數據可用性

定義 3.1.1(Blob):

EIP-4844 引入 Blob-Carrying Transactions,每個區塊最多可包含 6 個 Blob(目標 3 個)。

┌─────────────────────────────────────────────────────────────┐
│                 Blob 數據結構                              │
├─────────────────────────────────────────────────────────────┤
│                                                               │
│  Blob = 4096 Field Elements                                 │
│  每個 Field Element = 32 bytes                              │
│  總大小:4096 × 32 = 128 KB                                │
│                                                               │
│  每個 Blob 被編碼為多項式:                                   │
│  f(X) = Σ field_element[i] · X^i, i = 0, ..., 4095         │
│                                                               │
│  承諾 = KZG commitment of f(X)                             │
│                                                               │
└─────────────────────────────────────────────────────────────┘

3.2 Blob 承諾生成

步驟 1:數據編碼

def blob_to_polynomial(blob: bytes) -> List[int]:
    """
    將 Blob 數據轉換為多項式
    
    每 32 bytes 為一個 field element
    """
    field_elements = []
    for i in range(0, len(blob), 32):
        field_elements.append(int.from_bytes(blob[i:i+32], 'little'))
    return field_elements  # 長度 = 4096

def compute_blob_commitment(blob: bytes) -> bytes:
    """
    計算 Blob 的 KZG 承諾
    
    1. 將 Blob 轉換為多項式 f(X)
    2. 計算 commitment = KZG.Commit(f)
    3. 返回 commitment(作為區塊頭的一部份)
    """
    coeffs = blob_to_polynomial(blob)
    commitment = kzg.commit(coeffs)
    return commitment.to_bytes(48, 'little')  # G1 點,48 bytes

步驟 2:Commitment 與 Proof

@dataclass
class KZGProof:
    """KZG 開啟證明"""
    commitment: bytes  # 48 bytes
    proof: bytes       # 48 bytes
    z: bytes           # 32 bytes(點座標)
    y: bytes           # 32 bytes(多項式值)

def compute_proof(blob: bytes, z: int) -> KZGProof:
    """
    為 Blob 數據計算 KZG 開啟證明
    
    用於數據可用性抽樣(DAS)
    """
    coeffs = blob_to_polynomial(blob)
    y = evaluate_polynomial(coeffs, z)
    
    commitment = kzg.commit(coeffs)
    proof = kzg.open(coeffs, z, y)
    
    return KZGProof(
        commitment=commitment.to_bytes(48, 'little'),
        proof=proof.to_bytes(48, 'little'),
        z=z.to_bytes(32, 'little'),
        y=y.to_bytes(32, 'little')
    )

3.3 數據可用性抽樣(DAS)

定義 3.3.1(數據可用性抽樣):

節點不需要下載完整的 Blob 數據,只需隨機抽樣少量數據即可高概率確認數據可用。

抽樣協議:

┌─────────────────────────────────────────────────────────────┐
│                 DAS 抽樣流程                                │
├─────────────────────────────────────────────────────────────┤
│                                                               │
│  1. 節點隨機選擇 k 個 Field Element 索引:                   │
│     z₁, z₂, ..., zₖ ∈ {0, 1, ..., 4095}                    │
│                                                               │
│  2. 向網路請求這些索引的數據片段:                          │
│     - 節點 A:「我需要 z₁ 位置的數據」                      │
│     - 節點 B:「這裡是數據片段 + KZG 證明」                  │
│                                                               │
│  3. 驗證每個片段:                                          │
│     e(proof, [τ]₂) = e(commitment / g^y, [τ - z]₂)         │
│                                                               │
│  4. 如果所有 k 個驗證通過:                                  │
│     - 數據以概率 1 - (1/4096)^k 可用                        │
│     - 當 k = 16 時,概率 > 99.6%                            │
│                                                               │
└─────────────────────────────────────────────────────────────┘

效率分析:

假設有 $n$ 個 Blob,節點抽樣 $k$ 個元素:

3.4 KZG 承諾在共識層的集成

共識層 Commitment:

// 區塊結構中的 KZG commitment
type BeaconBlockBody struct {
    // ... 其他欄位 ...
    
    // KZG 承諾列表
    BlobKzgCommitments []BlobKZGCommitment `json:"blob_kzg_commitments"`
}

// BlobKZGCommitment 是 G1 點的壓縮表示
type BlobKZGCommitment [48]byte

驗證器職責:

  1. 承諾驗證: 確認 Blob 的 KZG 承諾與區塊頭中的承諾匹配
  2. DAS 抽樣: 參與數據可用性抽樣網路
  3. 證明發布: 為抽樣請求提供數據片段和證明

第四部分:KZG 承諾的安全性分析

4.1 信任假設

定理 4.1.1(KZG 安全性):

KZG 承諾方案的安全性基於以下假設:

  1. 離散對數假設(DLOG): 在 $G1$ 和 $G2$ 上計算離散對數是困難的
  1. 配對安全性: 雙線性配對不存在有效算法來區分 $e(g^a, h^b)$ 和隨機元素
  1. 信任設置假設: 至少有一個信任設置參與者是誠實的

信任設置的安全性:

如果攻擊者知道 $\tau$,可以:

防禦:

4.2 約束性證明

定理 4.2.1(約束性):

如果存在一個 PPT 攻擊者 $\mathcal{A}$ 可以為多項式 $f$ 構造兩個不同的開啟 $(z, y1, \pi1)$ 和 $(z, y2, \pi2)$ 使得驗證通過,則可以構造一個 PPT 算法解決 DLOG 問題。

證明概要:

假設攻擊者能夠構造衝突的開啟。則:

$$e(c / g^{y1}, [\tau]2) = e(\pi1, [\tau - z]2)$$

$$e(c / g^{y2}, [\tau]2) = e(\pi2, [\tau - z]2)$$

將兩式相除:

$$e(g^{y2 - y1}, [\tau]2) = e(\pi2 / \pi1, [\tau - z]2)$$

這給出:

$$[\tau - z]{G2} \cdot [\pi2 / \pi1]{G1} = [y2 - y1]{GT}$$

這蘊含了 $\tau$ 的信息,可以用於計算離散對數。

4.3 與其他承諾方案的比較

特性KZGIPA(內積論證)FRI
承諾大小48 bytes48 bytesO(log n)
證明大小48 bytesO(log n)O(log² n)
驗證時間1 次配對O(log n) hashO(log² n)
信任設置需要透明透明
量子安全
適用場景Blob DA通用計算STARKs

第五部分:Proto-Danksharding 實現

5.1 架構概述

┌─────────────────────────────────────────────────────────────┐
│            Proto-Danksharding 架構                         │
├─────────────────────────────────────────────────────────────┤
│                                                               │
│  執行層(Execution Layer):                                  │
│  - 驗證交易有效性                                            │
│  - 執行狀態轉換                                              │
│  - 生成 Blob 數據                                            │
│                                                               │
│  共識層(Consensus Layer):                                  │
│  - KZG 承諾驗證                                              │
│  - Blob 數據可用性抽樣                                        │
│  - 分叉選擇                                                  │
│                                                               │
│  數據可用性層:                                               │
│  - 節點抽樣 Blob 數據                                        │
│  - 重建完整 Blob                                             │
│                                                               │
└─────────────────────────────────────────────────────────────┘

5.2 完整交易流程

步驟 1:交易構造

type BlobTransaction struct {
    // 標準 EVM 交易欄位
    To    common.Address
    Value *big.Int
    Data  []byte
    
    // Blob 相關欄位
    BlobVersionedHashes []common.Hash  // KZG 承諾的哈希
    BlobProofs          []KZGProof      // 每個 Blob 的開啟證明
    MaxFeePerBlobGas    *big.Int        // Blob 費用上限
}

步驟 2:承諾發布

func (b *BlobTransaction) CommitBlobs() error {
    for i, blob := range b.Blobs {
        // 1. 編碼 Blob 為多項式
        coeffs := blobToPolynomial(blob)
        
        // 2. 計算 KZG 承諾
        commitment := kzg.Commit(coeffs)
        
        // 3. 計算版本化哈希(版本 + commitment 的哈希)
        versionedHash := computeVersionedHash(commitment)
        
        // 4. 存儲承諾用於後續驗證
        b.BlobVersionedHashes[i] = versionedHash
    }
    return nil
}

步驟 3:區塊提議者職責

func (beacon *BeaconNode) ProcessBlobTransaction(tx *BlobTransaction) error {
    // 1. 驗證版本化哈希
    for i, hash := range tx.BlobVersionedHashes {
        if !isValidVersionedHash(hash) {
            return ErrInvalidVersionedHash
        }
    }
    
    // 2. 驗證 KZG 承諾
    for i, blob := range tx.Blobs {
        proof := tx.BlobProofs[i]
        
        // 驗證 commitment 與 versioned hash 匹配
        expectedHash := computeVersionedHash(proof.Commitment)
        if expectedHash != tx.BlobVersionedHashes[i] {
            return ErrCommitmentMismatch
        }
    }
    
    // 3. 發布 Blob 到網路(用於 DAS)
    broadcastBlob(blob, proof)
    
    return nil
}

第六部分:未來 Full Danksharding

6.1 Full Danksharding 的願景

定義 6.1.1(Full Danksharding):

Full Danksharding 將實現完整的資料可用性分片,目標是:

6.2 KZG 承諾的擴展

Danksharding 承諾結構:

┌─────────────────────────────────────────────────────────────┐
│                 Danksharding 承諾層級                       │
├─────────────────────────────────────────────────────────────┤
│                                                               │
│  Level 0: 單個 Field Element                                │
│  Level 1: 單個 Blob (4096 Field Elements)                   │
│  Level 2: 多個 Blob 的聚合承諾                              │
│                                                               │
│  聚合承諾:                                                   │
│  C_agg = Σ w_i · C_i                                        │
│                                                               │
│  其中 w_i 是權重係數,用於平衡不同 Blob 的貢獻               │
│                                                               │
└─────────────────────────────────────────────────────────────┘

多項式抽樣:

def danksharding_sample(blob_commitments, num_samples=16):
    """
    從多個 Blob 中抽樣驗證數據可用性
    
    使用 KZG 承諾的多項式特性
    """
    samples = []
    
    for _ in range(num_samples):
        # 1. 隨機選擇一個 Blob
        blob_idx = random.randint(0, len(blob_commitments) - 1)
        
        # 2. 隨機選擇一個 Field Element 索引
        element_idx = random.randint(0, 4095)
        
        # 3. 請求該點的數據和證明
        sample = request_sample(
            blob_commitments[blob_idx],
            element_idx
        )
        
        # 4. 驗證樣本
        if not verify_sample(sample):
            return False
        
        samples.append(sample)
    
    # 至少 16 個樣本全部有效,數據以 >99.6% 概率可用
    return True

結論

KZG 承諾是以太坊現代化升級的核心密碼學構建塊。其關鍵特性包括:

  1. 承諾大小固定:48 bytes,與多項式階數無關
  2. 驗證效率高:只需一次配對計算
  3. 代數安全性:基於離散對數和雙線性配對假設
  4. 工程成熟:已有優化實現,部署於主網

從 EIP-4844 的 Proto-Danksharding 到未來 Full Danksharding,KZG 承諾將繼續在以太坊的數據可用性與擴展方案中發揮關鍵作用。理解其數學原理與驗證機制對於深入掌握以太坊技術演進至關重要。


參考文獻

KZG 原始論文

EIP-4844

密碼學基礎

以太坊實現


本網站內容僅供教育與資訊目的,不構成任何投資建議或推薦。

延伸閱讀與來源

這篇文章對您有幫助嗎?

評論

發表評論

注意:由於這是靜態網站,您的評論將儲存在本地瀏覽器中,不會公開顯示。

目前尚無評論,成為第一個發表評論的人吧!