多项式承诺 — KZG 与 Bulletproofs IPA

日期: 2026-11-20 方向: 密码学 / 经典原语 阶段: Phase 4 - 经典密码学 (Day 195-208) 标签: #密码学 #多项式承诺 #KZG #Bulletproofs #PLONK

---

今日目标

---

一、多项式承诺方案 (PCS)

1.1 形式化接口

Setup(λ, d) → srs              # public params for degree ≤ d
Commit(srs, p(X)) → C          # commit to polynomial p
Open(srs, p, z) → (y, π)       # y = p(z), π = proof
Verify(srs, C, z, y, π) → bool # verify y = p(z)

1.2 安全性质

• Hiding: 看 $C$ 学不到 $p$（可选）
• Binding: 一旦 commit，不能 open 到不同多项式
• Evaluation Binding: 不能在同点 $z$ open 出两个不同的 $y, y'$
• Knowledge Soundness: 能 prove 表示 prover 真的知道这个多项式

1.3 为什么 PCS 是 ZK 协议的核心

PLONK / Marlin / STARK / Halo2 几乎所有现代 SNARK 都是:

SNARK = IOP/PIOP + Polynomial Commitment Scheme

• 算术化把电路转成多项式约束
• PCS 把多项式 commit 上链（小）
• 验证者随机 challenge $z$，要求 prover 在 $z$ 处 open
• Fiat-Shamir 让协议非交互

PCS 的选择决定: proof size、verifier 时间、setup 性质。

---

二、KZG 多项式承诺 (Kate-Zaverucha-Goldberg 2010)

2.1 Trusted Setup (Powers of Tau)

选秘密 $\tau \in \mathbb{Z}_q$（必须销毁），公布: $$\text{srs}_1 = (g_1, \tau g_1, \tau^2 g_1, ..., \tau^d g_1) \in G_1^{d+1}$$ $$\text{srs}_2 = (g_2, \tau g_2) \in G_2^{2}$$

关键: $\tau$ 销毁后无人能反推。任何人知道 $\tau$ 即可破坏 binding（构造任意多项式的虚假 opening）。

实践:

• Eth KZG Ceremony (2023, 141k+ 参与者): 多方分布式 trusted setup
• "如果至少 1 方诚实销毁其份额，整个 setup 安全"

2.2 Commit

给定多项式 $p(X) = \sum_{i=0}^{d} a_i X^i$: $$C = p(\tau) \cdot g_1 = \sum_i a_i (\tau^i g_1)$$

注意: prover 不知道 $\tau$，但能计算 $p(\tau) g_1$ — 因为 $\tau^i g_1$ 在 srs 中。

2.3 Open at point $z$

声明 $p(z) = y$. 计算商多项式: $$q(X) = \frac{p(X) - y}{X - z}$$

(若 $p(z) = y$ 则 $X - z$ 整除 $p(X) - y$，$q$ 是 $d-1$ 次多项式)

Proof: $\pi = q(\tau) g_1$.

2.4 Verify

验证关系: $p(\tau) - y = q(\tau) (\tau - z)$

用 pairing 检查: $$e(C - y g_1, g_2) \stackrel{?}{=} e(\pi, \tau g_2 - z g_2)$$

展开: $$e((p(\tau) - y) g_1, g_2) = e(g_1, g_2)^{p(\tau) - y}$$ $$e(q(\tau) g_1, (\tau - z) g_2) = e(g_1, g_2)^{q(\tau)(\tau - z)}$$

若 $p(\tau) - y = q(\tau)(\tau - z)$ → 等式成立。

2.5 Multi-point Opening

要在多个点 $z_1, ..., z_k$ open，用商多项式: $$q(X) = \frac{p(X) - I(X)}{\prod (X - z_i)}$$

其中 $I(X)$ 是插值多项式。$\pi = q(\tau)g_1$ 单 G1 点即可。

---

三、KZG 安全性论证

3.1 Binding & Evaluation Binding

定理: KZG 在 $q$-SDH (Strong Diffie-Hellman) 假设下安全。

$q$-SDH 假设: 给定 $(g_1, \tau g_1, \tau^2 g_1, ..., \tau^q g_1, g_2, \tau g_2)$，难计算 $(c, \frac{1}{\tau + c} g_1)$ 对任意 $c \in \mathbb{Z}_q$.

证明思路: 假设攻击者能 open $C$ 到 $(z, y), (z, y')$ 不同值，得两个证明 $\pi, \pi'$: $$e(C - yg_1, g_2) = e(\pi, (\tau-z)g_2)$$ $$e(C - y'g_1, g_2) = e(\pi', (\tau-z)g_2)$$

相除得 $(y' - y)g_1 = (\pi - \pi')(\tau - z)$ → 攻击者计算 $\frac{1}{\tau-z}g_1$ → 解 $q$-SDH。

3.2 Trusted Setup 风险

若 $\tau$ 泄漏 → 攻击者可:

• Commit 到任意多项式 $p$
• 之后 open 到任意 $(z, y)$ — 通过造 $q(X) = (p(X) - y)/(X-z)$ 直接计算

→ Powers of Tau ceremony 必须确保 $\tau$ 蒸发。Eth ceremony 的"Cosmic Ray Test"：每参与者销毁后写日志声明。

---

四、Bulletproofs Inner Product Argument (IPA)

4.1 设计目标

• 无 trusted setup
• proof 长度 $O(\log n)$
• 但验证 $O(n)$（或 $O(\sqrt n)$ 通过精巧 batching）

4.2 内积论证

证明: 给定 $\vec{a}, \vec{b}$, $C = \langle \vec{a}, \vec{G} \rangle + \langle \vec{b}, \vec{H} \rangle + \langle \vec{a}, \vec{b} \rangle u$, 知道开承诺。

核心 trick (Bootle et al. 2016): 把长度 $n$ 内积折半: $$\vec{a} = (\vec{a}_L, \vec{a}_R), \vec{b} = (\vec{b}_L, \vec{b}_R)$$ $$\langle \vec{a}, \vec{b} \rangle = \langle \vec{a}_L, \vec{b}_L \rangle + \langle \vec{a}_R, \vec{b}_R \rangle$$

每轮把 $n$ 减半 → 共 $\log_2 n$ 轮 → 每轮发 2 个群元素 → 总 $2 \log n$ 元素。

4.3 用作多项式 PCS

把多项式 $p(X) = \sum a_i X^i$ commit 为 $C = \sum a_i G_i$（vector Pedersen）。

Open at $z$: prove $\sum a_i z^i = y$ — 即内积 $\langle \vec a, (1, z, z^2, ...) \rangle = y$.

用 IPA 证明此内积。proof size: $2 \log d$ 个 G1 群元素。

4.4 KZG vs IPA 对比

---

五、其他 PCS 简介

5.1 FRI (Fast Reed-Solomon IOP)

基于 Reed-Solomon code 距离测试 (FRI)。STARK 的核心。

• 无 trusted setup
• proof size $O(\log^2 n)$
• 后量子安全（仅依赖 hash + RS code）
• 但 prover 慢

5.2 Hyrax / Dory

中间形态: $O(\sqrt n)$ proof size, $O(\sqrt n)$ verifier。

5.3 Brakedown / Orion

基于线性码 + Merkle，无 trusted setup，prover 极快但 proof 大。

5.4 Plonky2/3 — 多 PCS 混合

Plonky2 用 FRI；Plonky3 模块化设计支持 swap PCS。

---

六、代码实现 — kzg.py

"""
kzg.py - 简化版 KZG 多项式承诺 (BLS12-381)
- Powers of Tau setup (NOT trustless — for demo only)
- Commit / Open / Verify single point
- Multi-point batch opening
"""
from __future__ import annotations
import secrets
from typing import List, Tuple

from py_ecc.bls12_381 import (
    G1, G2, multiply, add, neg, pairing, curve_order,
    Z1, Z2,
)
# We use field operations modulo curve_order
q = curve_order

# --------------------------- Polynomial helpers ---------------------------

def poly_eval(coeffs: List[int], x: int) -> int:
    """Horner: a0 + a1*x + ... + ad*x^d"""
    r = 0
    for c in reversed(coeffs):
        r = (r * x + c) % q
    return r

def poly_div(num: List[int], denom: List[int]) -> Tuple[List[int], List[int]]:
    """Polynomial long division mod q. Returns (quotient, remainder)."""
    num = num[:]  # copy
    if len(denom) == 0 or all(c == 0 for c in denom):
        raise ZeroDivisionError
    # remove leading zeros from denom
    while denom and denom[-1] == 0:
        denom = denom[:-1]
    if len(num) < len(denom):
        return [0], num
    quotient = [0] * (len(num) - len(denom) + 1)
    while len(num) >= len(denom):
        coef = num[-1] * pow(denom[-1], -1, q) % q
        deg_diff = len(num) - len(denom)
        quotient[deg_diff] = coef
        for i, c in enumerate(denom):
            num[deg_diff + i] = (num[deg_diff + i] - coef * c) % q
        while num and num[-1] == 0:
            num.pop()
    return quotient, num

def poly_sub(a, b):
    n = max(len(a), len(b))
    a = a + [0]*(n - len(a))
    b = b + [0]*(n - len(b))
    return [(x - y) % q for x, y in zip(a, b)]

# --------------------------- KZG Setup (TRUSTED) ---------------------------

class KZGSetup:
    """
    POWERS OF TAU
    For demo: we generate τ in process and immediately discard.
    In production: use a multi-party Ceremony output.
    """
    def __init__(self, max_degree: int):
        # WARN: in production, τ MUST come from a multi-party ceremony
        tau = secrets.randbelow(q)
        self.max_degree = max_degree
        # SRS in G1: [g, τg, τ²g, ..., τ^d g]
        self.srs_g1 = []
        cur = G1
        tau_pow = 1
        for i in range(max_degree + 1):
            self.srs_g1.append(multiply(G1, tau_pow))
            tau_pow = tau_pow * tau % q
        # SRS in G2: [g₂, τg₂]
        self.g2 = G2
        self.tau_g2 = multiply(G2, tau)
        # CRITICAL: discard τ
        del tau
        # set sentinel for tests (real ceremony has no shadow)
        self._discarded = True

    def commit(self, coeffs: List[int]) -> tuple:
        """C = p(τ) g₁ = Σ a_i (τⁱ g₁)"""
        assert len(coeffs) <= self.max_degree + 1
        result = None
        for c, gi in zip(coeffs, self.srs_g1):
            result = add(result, multiply(gi, c % q))
        return result

# --------------------------- Open / Verify ---------------------------

def kzg_open(setup: KZGSetup, coeffs: List[int], z: int) -> Tuple[int, tuple]:
    """
    Open p(X) at point z.
    Returns (y = p(z), π = q(τ)g₁) where q(X) = (p(X) - y) / (X - z).
    """
    y = poly_eval(coeffs, z)
    # numerator: p(X) - y
    num = coeffs[:]
    num[0] = (num[0] - y) % q
    # denominator: X - z = [-z, 1]
    quot, rem = poly_div(num, [(-z) % q, 1])
    # remainder should be 0 if y was correct
    assert all(r == 0 for r in rem), f"Non-zero remainder: {rem}"
    proof = setup.commit(quot)
    return y, proof

def kzg_verify(setup: KZGSetup, commitment: tuple, z: int, y: int, proof: tuple) -> bool:
    """
    Check: e(C - yG, G₂) == e(π, τG₂ - zG₂)
    i.e., e(p(τ)G - yG, G₂) == e(q(τ)G, (τ-z)G₂)
    """
    lhs_pt = add(commitment, neg(multiply(G1, y)))
    rhs_g2 = add(setup.tau_g2, neg(multiply(G2, z % q)))
    lhs_pairing = pairing(setup.g2, lhs_pt)
    rhs_pairing = pairing(rhs_g2, proof)
    return lhs_pairing == rhs_pairing

# --------------------------- Multi-point batch open ---------------------------

def lagrange_interp(points: List[Tuple[int, int]]) -> List[int]:
    """Given (z_i, y_i), return coeffs of unique min-deg poly through them."""
    n = len(points)
    result = [0] * n
    for i in range(n):
        zi, yi = points[i]
        # L_i(X) = Π_{j≠i} (X - z_j) / (z_i - z_j)
        Li = [1]
        denom = 1
        for j in range(n):
            if j == i: continue
            zj, _ = points[j]
            # multiply Li by (X - z_j)
            new_Li = [0] * (len(Li) + 1)
            for k, c in enumerate(Li):
                new_Li[k] = (new_Li[k] - c * zj) % q
                new_Li[k + 1] = (new_Li[k + 1] + c) % q
            Li = new_Li
            denom = denom * (zi - zj) % q
        inv_denom = pow(denom, -1, q)
        for k in range(len(Li)):
            result[k] = (result[k] + yi * Li[k] * inv_denom) % q
    return result

def kzg_open_multi(setup: KZGSetup, coeffs: List[int], zs: List[int]) -> Tuple[List[int], tuple]:
    """
    Open at multiple points. Single proof.
    Returns (ys, π).
    """
    ys = [poly_eval(coeffs, z) for z in zs]
    # vanishing poly Z(X) = Π(X - z_i)
    Z = [1]
    for z in zs:
        new_Z = [0] * (len(Z) + 1)
        for k, c in enumerate(Z):
            new_Z[k] = (new_Z[k] - c * z) % q
            new_Z[k + 1] = (new_Z[k + 1] + c) % q
        Z = new_Z
    # interpolation poly I(X) through (z_i, y_i)
    I = lagrange_interp(list(zip(zs, ys)))
    # q(X) = (p(X) - I(X)) / Z(X)
    num = poly_sub(coeffs, I)
    quot, rem = poly_div(num, Z)
    assert all(r == 0 for r in rem)
    proof = setup.commit(quot)
    return ys, proof

# --------------------------- Demo ---------------------------

if __name__ == "__main__":
    # 1. Setup for max degree 10
    print("Generating KZG setup (max_degree=10)...")
    setup = KZGSetup(max_degree=10)
    print("Setup done. τ has been discarded.")

    # 2. Commit to a polynomial: p(X) = 5 + 7X + 3X² + 2X⁵
    coeffs = [5, 7, 3, 0, 0, 2, 0, 0, 0, 0, 0]
    C = setup.commit(coeffs)
    print(f"Commitment to p(X): {C[0]}")

    # 3. Evaluate at z = 4
    z = 4
    expected = poly_eval(coeffs, z)
    print(f"p({z}) = {expected}")

    # 4. Open
    y, proof = kzg_open(setup, coeffs, z)
    assert y == expected
    print(f"Opened p({z}) = {y} with proof of size 1 G1 element")

    # 5. Verify
    assert kzg_verify(setup, C, z, y, proof)
    print("Verification: PASS")

    # 6. Try to forge open with wrong y
    fake_y = (y + 1) % q
    fake_proof = proof  # attacker can't recompute valid q(τ)
    assert not kzg_verify(setup, C, z, fake_y, fake_proof)
    print("Forged opening rejected: PASS")

    # 7. Multi-point batch open
    zs = [3, 5, 7]
    ys, batch_proof = kzg_open_multi(setup, coeffs, zs)
    print(f"Multi-point: p(3)={ys[0]}, p(5)={ys[1]}, p(7)={ys[2]}")
    # Verify each one (could be batched)
    for z, y in zip(zs, ys):
        single_y, single_proof = kzg_open(setup, coeffs, z)
        assert kzg_verify(setup, C, z, single_y, single_proof)
    print("Multi-point opens: PASS")

---

七、真实漏洞 / 事件

Eth KZG Ceremony: 4844 (proto-danksharding) blob 数据用 KZG commitment。141,000+ 参与者，每人贡献随机 + zk proof of contribution。即便 99.999% 参与者作弊，只要 1 人诚实销毁，整个 setup 安全。

---

八、协议应用 — Web3 中的 PCS

8.1 Eth 4844 Blob KZG

每 blob = 4096 个 BLS 标量 ≈ 128 KB. Commit 成 48 字节（KZG）。验证者:

1. 接收 blob + KZG commitment
2. 用 trusted setup 在随机点 open 验证
3. blob 数据本身 prune 掉 (~30 天后)，但 commitment 永久

L2 (Optimism, Arbitrum, zkSync) 用 blob 替代 calldata → 数据成本降 50-100×.

8.2 PLONK 中的 KZG 用途

PLONK 的多个多项式（wire / selector / permutation）每个 commit 成 1 个 G1 点，proof 总共 ~7-10 个 G1 + 几个 scalar = 几百字节。

---

九、常见陷阱

1. Trusted setup 单点失败: 用单方 setup → 该方持 τ 即可造假证明
2. Powers of Tau 长度不足: 多项式度数 > setup 时无法 commit
3. Domain mismatch: Lagrange basis 重复用错（FFT domain 不一致）
4. Verifier 不验 commitment 是否在子群: small subgroup attack
5. Proof 不绑定 challenge: Fiat-Shamir 不当 → grinding attack
6. Polynomial degree 与 SRS 不匹配: prover 用 d+1 度多项式但 SRS 仅支持 d
7. Pairing 库版本差异: Eth KZG 用 BLS12-381, 部分项目仍用 BN254 (~100 bit 安全, 不够)
8. Commitment 复用: 同 C 在多个上下文 → 可能被关联

---

十、关键速查

PCS 选择决策

需要多项式承诺?
├── 验证者必须极快/链上 → KZG
│   ├── 接受 trusted setup → ✓ Eth ceremony 已完成
│   └── 不接受 → IPA / FRI
│
├── 后量子保险 → FRI (基于 hash)
│
├── 证明者性能优先 → Brakedown / Orion
│
└── 通用 zkVM → Plonky3 (可切换 PCS)

性能数据 (BLS12-381)

---

十一、面试题

Q1: KZG 和 IPA 在 Web3 各自用在哪？为什么？ A:

• KZG: Eth 4844 blobs / PLONK / Aleo Marlin。需要 $O(1)$ verifier 速度（链上验证经济）。代价: trusted setup
• IPA: Halo2 / Zcash Orchard / Mina。无 trusted setup。代价: $O(\log n)$ proof + $O(n)$ verifier
• FRI: STARK / Plonky2。后量子安全 (only hash)。代价: proof 大

Q2: 为什么以太坊 4844 选 KZG 而非 IPA？ A: (1) Verifier 必须超快 (链上 gas 限制) → KZG 1 pairing vs IPA $O(n)$; (2) Trusted setup 已完成 (141k 参与者，社会成本一次性付完); (3) Pairing precompile (EIP-2537) 让链上验证可行; (4) Blob 大小 128KB 用 KZG 仅 48 B commit。

Q3: KZG ceremony 安全的前提是什么？ A: 至少一个参与者诚实销毁 τ 份额。每参与者输入 $\tau_i$，最终 $\tau = \prod \tau_i$。攻击者要恢复 $\tau$ 需所有 $\tau_i$. Eth ceremony 141k 参与者下，"all collude" 几乎不可能，且每人销毁后立即销毁机器/重启。

Q4: 如果 τ 被泄漏，影响什么？ A: 灾难。攻击者可:

• Commit 到任意多项式 $p$
• 之后 open 到任意 $(z, y)$ — 通过 $q(X) = (p(X) - y)/(X-z)$, $\pi = q(\tau)g_1$
• 即可造假 SNARK 证明、伪造 blob、伪造 PLONK proof
• → 破坏整个 Eth 4844、PLONK、Aleo 等所有依赖该 ceremony 的协议

防御: 多方 ceremony + 公开 transcript + 任何人可验证。

Q5: KZG open 一个点和 open 多个点有何成本差异？ A: 都是 1 个 G1 群元素的证明！秘密在于商多项式:

• Single point: $q(X) = (p(X) - y)/(X - z)$, 1 G1
• Multi-point: $q(X) = (p(X) - I(X))/Z(X)$ 其中 $Z(X) = \prod(X - z_i)$, 仍 1 G1
• Verifier: 单点 1 pairing 等式; 多点需 $I(X)$ + $Z(X)$ 在 srs 中评估，仍 1 个 pairing

→ KZG 的 multi-point 几乎免费，PLONK 利用此打包多个评估到 1 个 proof。

---

十二、明日预告

Day 204: Vector Commitment — 系统对比 Merkle vs KZG 作为向量承诺的设计权衡。批量开承诺、subvector commit、子线性 proof size。Verkle Tree 的前奏。