【密码学百科】承诺方案：Pedersen 承诺、向量承诺与多项式承诺

承诺方案（commitment scheme）是现代密码学协议中最基础也最关键的构件之一。它的直觉类比十分简单：设想你将一条消息写在纸上，放入一个密封的信封，然后将信封交给对方。对方在收到信封后无法得知其中的内容（隐藏性），而你在交出信封后也无法偷偷更换其中的消息（绑定性）。到了约定的时刻，你打开信封揭示消息，对方可以验证你确实没有更改过承诺的值。这一朴素的”先承诺、后揭示”机制，在零知识证明（zero-knowledge proof）、安全多方计算（secure multi-party computation, MPC）、区块链共识（blockchain consensus）、电子投票（e-voting）等几乎所有密码学协议中扮演着不可或缺的角色。

本文是密码学百科系列的第 44 篇。在前一篇对零知识证明系统的系统讲解基础上，本文将深入承诺方案的内部世界：从形式化定义与安全性模型出发，逐步介绍哈希承诺、Pedersen 承诺、ElGamal 承诺等经典方案，再拓展至 Merkle 树向量承诺与 KZG 多项式承诺等现代构造，最终展望基于格的承诺与函数承诺等前沿方向。

一、承诺方案的定义与安全性

先看一张图，把这一节的关键关系串起来。

flowchart LR
    A[消息] --> B[Commit]
    B --> C[承诺值]
    C --> D[Open]
    D --> E[验证]

一个承诺方案由三个算法组成。首先是设置算法 Setup(1^λ)，它接受安全参数 λ 并输出公共参数 pp。其次是承诺算法 Commit(pp, m; r)，它接受公共参数 pp、消息 m 以及随机数 r（也称盲化因子或开启因子），输出承诺值 c。最后是验证算法 Verify(pp, c, m, r)，它检查承诺值 c 是否确实是对消息 m 使用随机数 r 生成的，输出接受或拒绝。

承诺方案的安全性由两条核心性质刻画——隐藏性（hiding）与绑定性（binding）。

隐藏性要求：给定承诺值 c，任何敌手都无法从中提取关于消息 m 的有用信息。根据安全强度的不同，隐藏性又可进一步划分为两类。计算隐藏性（computational hiding）要求任何多项式时间敌手无法区分对两个不同消息的承诺；换言之，隐藏性的保证建立在敌手的计算能力有限这一假设之上。完美隐藏性（perfect hiding）则更为强大：即使是拥有无限计算能力的敌手也无法从承诺值中获得关于消息的任何信息。在信息论的意义上，完美隐藏性要求承诺值的分布与消息完全独立——对于任意两个不同的消息 m₀ 和 m₁，Commit(pp, m₀; r) 的分布与 Commit(pp, m₁; r) 的分布在统计上完全相同（其中 r 均匀随机选取）。

绑定性要求：承诺者在生成承诺值 c 之后，无法找到两组不同的消息-随机数对 (m₀, r₀) 和 (m₁, r₁) 使得 Commit(pp, m₀; r₀) = Commit(pp, m₁; r₁) = c。同样地，绑定性也有计算绑定性（computational binding）与完美绑定性（perfect binding）之分。计算绑定性假设敌手是多项式时间的，而完美绑定性（也称统计绑定性或无条件绑定性）要求即使是无限计算能力的敌手也无法打破。

一个深刻的不可能性结果是：承诺方案不可能同时满足完美隐藏性与完美绑定性。直觉上理解这一结论并不困难。完美隐藏性要求对于每个承诺值 c，存在多个合法的消息-随机数对可以开启它（否则敌手可以通过穷举找到唯一的消息）。然而，一旦存在多个合法的开启方式，承诺者就有可能在承诺之后选择开启为不同的消息，从而违反完美绑定性。因此，在设计承诺方案时，必须在隐藏性与绑定性之间做出取舍：要么选择完美隐藏 + 计算绑定（如 Pedersen 承诺），要么选择计算隐藏 + 完美绑定（如哈希承诺）。

除了隐藏性和绑定性之外，某些高级应用还需要承诺方案具备额外的性质。同态性（homomorphism）要求承诺值之间可以进行代数运算，使得 Commit(m₁) ⊕ Commit(m₂) = Commit(m₁ + m₂)，这在零知识证明中极为有用。可提取性（extractability）要求存在一个提取器（extractor），在知道特定”陷门”信息的情况下可以从承诺值中还原出消息，这在安全性证明中常被用到。可等化性（equivocability）要求在掌握陷门的条件下，可以将同一个承诺值开启为任意消息，这在模拟器（simulator）的构造中至关重要。

二、哈希承诺

哈希承诺（hash commitment）是概念上最简单也最直观的承诺方案。其构造方式如下：承诺者选择一个均匀随机的盲化因子 r，然后计算承诺值 c = H(m || r)，其中 H 是一个密码学哈希函数（cryptographic hash function），|| 表示串联（concatenation）。揭示阶段，承诺者公开 (m, r)，验证者重新计算 H(m || r) 并检查是否等于 c。

哈希承诺的安全性分析如下。绑定性依赖于哈希函数的抗碰撞性（collision resistance）：如果承诺者能找到 (m₀, r₀) ≠ (m₁, r₁) 使得 H(m₀ || r₀) = H(m₁ || r₁)，则等同于找到了哈希函数的一个碰撞。因此，只要哈希函数是抗碰撞的，绑定性就得到保证。事实上，哈希承诺甚至可以实现完美绑定性——如果将哈希函数建模为随机预言机（random oracle），那么对于每个承诺值 c，使得 H(m || r) = c 的 (m, r) 对唯一确定（以绝大概率成立）。隐藏性则依赖于哈希函数的单向性（one-wayness）或更准确地说是”隐藏”性质：给定 c = H(m || r)，在不知道 r 的情况下，敌手无法还原 m。这是计算隐藏性——拥有足够计算能力的敌手原则上可以穷举所有 (m, r) 对来找到匹配。需要特别注意的是，盲化因子 r 的使用是必要的：如果直接计算 c = H(m)，敌手可以对消息空间进行离线穷举，尤其当消息空间较小时（例如”是”或”否”），仅凭哈希值即可反推出消息。

哈希承诺的一个经典应用是公平掷币协议（coin flipping protocol）。假设 Alice 和 Bob 远程通信，需要共同生成一个公平的随机比特。协议流程为：(1) Alice 选择随机比特 a，计算承诺 c = H(a || r) 并发送给 Bob；(2) Bob 选择随机比特 b 并发送给 Alice；(3) Alice 揭示 (a, r)，Bob 验证 H(a || r) = c；(4) 双方约定最终结果为 a ⊕ b。由于承诺的绑定性，Alice 在步骤 (2) 收到 b 之后无法更改 a；由于承诺的隐藏性，Bob 在步骤 (2) 选择 b 时无法得知 a。因此，无论哪一方试图作弊，最终结果 a ⊕ b 对双方而言都是均匀随机的。

哈希承诺的主要优势在于实现简单、计算高效，并且可以基于任何安全的哈希函数（如 SHA-256、BLAKE3）构造。然而，它缺乏代数结构，不具备同态性——你无法在不揭示消息的情况下对两个承诺值进行有意义的运算。这一限制在需要对承诺值进行算术操作的高级协议（如零知识证明）中成为显著的瓶颈。

三、Pedersen 承诺

Pedersen 承诺（Pedersen commitment）由 Torben Pedersen 在 1991 年提出，是密码学中使用最为广泛的承诺方案之一。它基于离散对数假设（discrete logarithm assumption），在椭圆曲线群（elliptic curve group）上的实现尤为高效。

设 G 是一个阶为素数 p 的循环群，g 和 h 是 G 的两个生成元，且没有人知道 h 相对于 g 的离散对数（即不存在已知的 x 使得 h = g^x）。要对消息 m ∈ Z_p 进行承诺，承诺者随机选取盲化因子 r ←$ Z_p，计算承诺值 C = g^m · h^r。揭示阶段，承诺者公开 (m, r)，验证者检查 g^m · h^r 是否等于 C。

Pedersen 承诺的安全性分析如下。完美隐藏性：对于任意消息 m，当 r 在 Z_p 上均匀随机选取时，C = g^m · h^r 在群 G 上均匀分布。更准确地说，对于任意两个消息 m₀ 和 m₁，承诺值的分布完全相同，因为 r 的随机性完全掩盖了 m 的信息。这是信息论层面的隐藏性——即使敌手拥有无限的计算能力也无法区分。计算绑定性：如果承诺者能找到 (m₀, r₀) ≠ (m₁, r₁) 使得 g^{m₀} · h^{r₀} = g^{m₁} · h^{r₁}，则可以推出 g^{m₀ - m₁} = h^{r₁ - r₀}。当 m₀ ≠ m₁ 时，这意味着 h = g^{(m₀ - m₁)/(r₁ - r₀)}，从而计算出了 h 相对于 g 的离散对数，这与离散对数假设矛盾。因此，绑定性在计算意义上得到保证。

Pedersen 承诺最引人注目的性质是其加法同态性（additive homomorphism）。给定两个承诺 C₁ = g^{m₁} · h^{r₁} 和 C₂ = g^{m₂} · h^{r₂}，它们的乘积为 C₁ · C₂ = g^{m₁+m₂} · h^{r₁+r₂}，这恰好是对消息 m₁ + m₂ 使用随机数 r₁ + r₂ 的合法承诺。这意味着任何人都可以在不知道消息和随机数的情况下，仅通过操作承诺值来计算消息之和的承诺。同态性在零知识证明中有着极其重要的应用——证明者可以对承诺值进行线性组合，验证者可以检查这些线性关系是否成立，而无需了解底层的消息值。

此外，标量乘法也同样自然地工作：对于标量 k，有 C₁^k = g^{k·m₁} · h^{k·r₁}，这是对消息 k·m₁ 使用随机数 k·r₁ 的承诺。因此，Pedersen 承诺支持在承诺值上进行完整的线性运算。

在椭圆曲线群上实现 Pedersen 承诺时，群运算从模幂变为标量乘法：设 G、H 为椭圆曲线上的两个独立生成点（其离散对数关系未知），承诺值 C = mG + rH，其中 m, r ∈ Z_p。验证为检查 mG + rH = C。椭圆曲线实现在相同安全级别下所需的密钥长度远小于传统离散对数群，因此是目前的标准选择。

下面的 Python 代码演示了 Pedersen 承诺的基本操作以及同态加法性质：

import secrets
import hashlib

# 使用一个大素数阶的简化离散对数群进行演示
# 实际部署应使用椭圆曲线（如 Curve25519 或 Ristretto255）
p = 0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AACAA68FFFFFFFFFFFFFFFF
# 使用 Sophie Germain 对应的素数阶子群
q = (p - 1) // 2

# 选择两个独立的生成元
g = pow(2, (p - 1) // q, p)  # g 是阶为 q 的生成元
# h 通过哈希方式从 g 导出，确保离散对数关系未知（"nothing-up-my-sleeve"）
h_seed = hashlib.sha256(b"Pedersen-commitment-generator-h").digest()
h = pow(int.from_bytes(h_seed, 'big'), (p - 1) // q, p)
if h == 1:
    h = pow(3, (p - 1) // q, p)

def pedersen_commit(m, r):
    """Pedersen 承诺: C = g^m * h^r mod p"""
    gm = pow(g, m % q, p)
    hr = pow(h, r % q, p)
    return (gm * hr) % p

def pedersen_verify(C, m, r):
    """验证承诺"""
    return pedersen_commit(m, r) == C

def random_scalar():
    """生成随机标量"""
    return secrets.randbelow(q - 1) + 1

# --- 基本承诺与揭示 ---
m1, r1 = 42, random_scalar()
C1 = pedersen_commit(m1, r1)
print(f"消息 m1 = {m1}")
print(f"承诺 C1 = {hex(C1)[:24]}...")
print(f"验证结果: {pedersen_verify(C1, m1, r1)}")

m2, r2 = 58, random_scalar()
C2 = pedersen_commit(m2, r2)
print(f"\n消息 m2 = {m2}")
print(f"承诺 C2 = {hex(C2)[:24]}...")
print(f"验证结果: {pedersen_verify(C2, m2, r2)}")

# --- 同态加法演示 ---
# C1 * C2 应当等于 Commit(m1 + m2, r1 + r2)
C_product = (C1 * C2) % p
C_sum = pedersen_commit(m1 + m2, r1 + r2)
print(f"\n--- 同态加法验证 ---")
print(f"C1 * C2 mod p    = {hex(C_product)[:24]}...")
print(f"Commit(m1+m2, r1+r2) = {hex(C_sum)[:24]}...")
print(f"同态性成立: {C_product == C_sum}")

# --- 标量乘法演示 ---
k = 5
C1_k = pow(C1, k, p)
C_km = pedersen_commit(k * m1, k * r1)
print(f"\n--- 标量乘法验证 (k={k}) ---")
print(f"C1^{k} mod p       = {hex(C1_k)[:24]}...")
print(f"Commit({k}*m1, {k}*r1) = {hex(C_km)[:24]}...")
print(f"标量同态性成立: {C1_k == C_km}")

# --- 隐藏性演示: 相同承诺值对不同消息不可区分 ---
print(f"\n--- 隐藏性演示 ---")
r_a, r_b = random_scalar(), random_scalar()
C_a = pedersen_commit(0, r_a)
C_b = pedersen_commit(1, r_b)
print(f"Commit(0) = {hex(C_a)[:24]}... (不可从中判断消息为 0)")
print(f"Commit(1) = {hex(C_b)[:24]}... (不可从中判断消息为 1)")

Pedersen 承诺的推广形式——向量 Pedersen 承诺（vector Pedersen commitment）——允许对一个向量 (m₁, m₂, …, m_n) 进行承诺：选择 n+1 个独立生成元 g₁, g₂, …, g_n, h，承诺值为 C = g₁^{m₁} · g₂^{m₂} · … · g_n^{m_n} · h^r。向量 Pedersen 承诺在 Bulletproofs 等零知识证明系统中扮演核心角色。

四、ElGamal 承诺与变体

ElGamal 承诺（ElGamal commitment）与 ElGamal 加密密切相关。回顾 ElGamal 加密：给定生成元 g 和公钥 y = g^x，对消息 m 的加密为 (c₁, c₂) = (g^r, m · y^r)。如果我们将消息嵌入指数位置，即对 g^m 进行加密，就得到 ElGamal 承诺的基本形式：C = (g^r, g^m · y^r)。

ElGamal 承诺的绑定性源于离散对数假设（与 Pedersen 承诺类似），而隐藏性则源于判定性 Diffie-Hellman 假设（Decisional Diffie-Hellman, DDH）。与 Pedersen 承诺不同的是，标准 ElGamal 承诺提供的是计算隐藏性而非完美隐藏性。然而，ElGamal 承诺的一个重要优势在于其天然具备可等化性（equivocability）。如果模拟器知道秘密密钥 x，它可以将一个承诺值开启为任意消息——这在零知识证明的安全性证明（特别是模拟范式 simulation paradigm）中极为有用。

具体而言，可等化承诺（equivocable commitment）在安全性证明中的角色如下：在模拟的世界中，模拟器需要”先承诺、后决定”——即先生成一个承诺值（此时尚不知道要承诺什么消息），然后在获知消息后再将承诺”打开”为该消息。可等化性精确地赋予了模拟器这一能力。注意，可等化性只在掌握陷门的模拟器手中才能实现——对于不知道陷门的普通敌手，绑定性仍然成立。

ElGamal 承诺还可以通过多种方式进行变体和扩展。例如，在使用配对友好椭圆曲线（pairing-friendly elliptic curve）的场景中，可以构造支持双线性运算的承诺方案，这为更复杂的协议构造打开了大门。另一个重要的变体是 Fujisaki-Okamoto 承诺，它基于强 RSA 假设，在整数群上工作，适用于不依赖离散对数的场景。

五、Merkle 树与向量承诺

向量承诺（vector commitment）是承诺方案的一个重要推广：它允许承诺者对一个有序向量 (v₁, v₂, …, v_n) 进行承诺，生成一个简短的承诺值 C，并在之后能够针对任意位置 i 生成一个证明 π_i，使验证者仅凭 (C, i, v_i, π_i) 即可确信第 i 个位置的值确实是 v_i。理想的向量承诺方案要求承诺值的大小和每个位置证明的大小均为常数级别（与向量长度 n 无关），但在实践中，不同方案在证明大小、验证时间和计算效率之间存在各种权衡。

Merkle 树（Merkle tree）是最经典也最广泛部署的向量承诺方案。它由 Ralph Merkle 在 1979 年提出，仅依赖抗碰撞哈希函数，因此在后量子安全方面具有天然优势。

Merkle 树的构造如下：将 n 个元素放置在二叉树的叶节点上，每个内部节点的值等于其两个子节点值的哈希串联，即 node = H(left || right)。树根（root）就是整个向量的承诺值。要证明第 i 个元素属于该向量，只需提供从叶节点到根的路径上的所有兄弟节点（sibling node），这条路径称为 Merkle 证明（Merkle proof）或认证路径（authentication path）。验证者沿路径自底向上重新计算哈希值，检查最终结果是否与已知的树根一致。

Merkle 证明的大小为 O(log n)——对于一个包含 2²⁰（约一百万）个元素的向量，证明仅需 20 个哈希值，按 SHA-256 计算每个 32 字节，总共仅 640 字节。验证时间同样为 O(log n) 次哈希运算，极为高效。

Merkle 树在区块链中有着广泛而深刻的应用。比特币（Bitcoin）使用 Merkle 树将区块中的所有交易组织起来，区块头中仅存储 Merkle 根；轻客户端（light client）通过简单支付验证（Simplified Payment Verification, SPV）即可验证某笔交易是否包含在区块中，而无需下载完整的交易列表。以太坊（Ethereum）更进一步，使用 Merkle Patricia Trie（一种 Merkle 树与前缀树的混合结构）来承诺整个世界状态（world state）——每个账户的余额、合约代码和存储数据都被组织在这棵树中，状态根（state root）被包含在每个区块头中。这使得任何人都可以通过一条 Merkle 证明来验证任意账户在某个区块时刻的状态，而无需信任任何第三方。

然而，Merkle 树作为向量承诺也有其局限性。首先，证明大小为 O(log n) 而非常数级别，当需要打开大量位置时开销可观。其次，Merkle 树不具备同态性——你无法在不重建树的情况下对两个 Merkle 承诺进行有意义的代数运算。这些限制推动了研究者探索基于代数结构的向量承诺方案，如基于双线性配对的 Catalano-Fiore 向量承诺，以及后文将介绍的多项式承诺。

值得一提的是，Verkle 树（vector commitment tree）是近年来受到广泛关注的一种改进方案。它用代数向量承诺（通常是基于内积论证 Inner Product Argument 的方案）替换 Merkle 树中的哈希函数，从而将证明大小从 O(log n) 级别降低到接近常数的水平。以太坊社区正在积极推进将状态树从 Merkle Patricia Trie 迁移到 Verkle 树，以大幅减少状态证明的体积。

六、KZG 多项式承诺

多项式承诺（polynomial commitment）是承诺方案在多项式空间上的推广。它允许承诺者对一个多项式 f(X) 进行承诺，生成承诺值 C，然后在任意点 z 上生成一个证明 π，使验证者确信 f(z) = y，而无需看到整个多项式。多项式承诺是现代零知识证明系统（如 PLONK、Marlin、Groth16）的核心构件——在这些系统中，证明者将计算的正确性编码为多项式之间的等式关系，然后通过多项式承诺来证明这些等式在随机点上成立。

KZG 承诺（Kate-Zaverucha-Goldberg commitment）由 Aniket Kate、Gregory Zaverucha 和 Ian Goldberg 在 2010 年提出，是目前最广泛使用的多项式承诺方案。它基于双线性配对（bilinear pairing）和 q-SDH（q-Strong Diffie-Hellman）假设。

在深入 KZG 的构造之前，有必要建立双线性配对的最小必要背景。设 G₁、G₂ 和 G_T 是三个阶为素数 p 的循环群，双线性配对是一个映射 e: G₁ × G₂ → G_T，满足三条性质。第一，双线性（bilinearity）：对于所有 a, b ∈ Z_p，有 e(aP, bQ) = e(P, Q)^{ab}，其中 P ∈ G₁、Q ∈ G₂。第二，非退化性（non-degeneracy）：存在 P ∈ G₁ 和 Q ∈ G₂ 使得 e(P, Q) ≠ 1_{G_T}。第三，可计算性（computability）：存在高效算法计算 e。在实践中，配对通常在 BLS12-381 等配对友好椭圆曲线（pairing-friendly elliptic curve）上通过 Weil 配对或 Tate 配对的优化变体实现。配对的安全性基础在于 CDH（Computational Diffie-Hellman）假设：给定群元素 aP 和 bP，任何多项式时间敌手都无法计算 abP。配对将 G₁ 和 G₂ 上的离散对数困难性”映射”到 G_T 中——虽然配对允许进行一次受控的”乘法级”运算，但不会泄露底层的标量值。

为简化后续符号，我们引入括号记法：[x]₁ 表示 x·G₁（G₁ 生成元的 x 倍标量乘），[x]₂ 表示 x·G₂。双线性性质在此记法下可简洁地写为 e([a]₁, [b]₂) = e([1]₁, [1]₂)^{ab}。这一性质是 KZG 验证方程的核心——它允许验证者在不知道秘密值的情况下，通过配对运算检查多项式在该秘密点处的求值关系是否成立。

KZG 方案的安全性更精确地依赖于 q-SDH 假设：给定 ([1]₁, [s]₁, [s²]₁, …, [s^q]₁, [s]₂)，任何多项式时间敌手都无法输出一对 (c, [1/(s+c)]₁)。q-SDH 蕴含了 CDH 假设，是其在结构化参考字符串设置下的自然强化。直觉上，q-SDH 保证即使敌手拥有秘密点 s 的大量”编码”信息（以群元素的形式），仍无法据此逆向恢复 s 本身或构造新的合法求值证明。

KZG 的可信设置（trusted setup）通过 Powers of Tau 仪式实现。具体而言，需要生成结构化参考字符串 SRS = ([1]₁, [s]₁, [s²]₁, …, [s^d]₁, [1]₂, [s]₂)，其中 s 是一个必须在设置完成后被销毁的秘密值（也称”有毒废料” toxic waste），d 是所支持的最大多项式次数。如果任何人获知 s，他就可以伪造任意求值证明。实践中，这一安全性保证通过多方计算仪式（MPC ceremony）实现：N 个互不信任的参与者依次贡献随机性 s₁, s₂, …, s_N，最终的秘密值为 s = s₁ · s₂ · … · s_N，每个参与者只知道自己的份额。只要 N 个参与者中至少一个诚实地销毁了自己的 s_i，整体安全性就得以保证——这是 1-of-N 诚实假设。以太坊的 KZG 仪式吸引了超过 14 万名参与者，创造了迄今为止规模最大的可信设置仪式。

承诺阶段：对于多项式 f(X) = a₀ + a₁X + a₂X² + … + a_dX^d，承诺值为 C = [f(s)]₁ = a₀·[1]₁ + a₁·[s]₁ + a₂·[s²]₁ + … + a_d·[s^d]₁。承诺者无需知道 s 的值——它仅使用 SRS 中的公开群元素即可通过多标量乘法计算承诺值。承诺值是 G₁ 中的一个群元素，大小为常数（BLS12-381 曲线上约 48 字节）。

证明阶段：要证明 f(z) = v，承诺者计算商多项式 q(X) = (f(X) - v) / (X - z)。由于 f(z) = v，多项式 f(X) - v 在 X = z 处有一个根，因此除法是精确的（无余数）。证明值为 π = [q(s)]₁，同样是 G₁ 中的一个群元素，大小为常数。

验证阶段：验证者利用双线性配对检查以下等式：

e([f(s)]₁ - [v]₁, [1]₂) = e([q(s)]₁, [s - z]₂)

即 e(C - [v]₁, [1]₂) = e(π, [s]₂ - z·[1]₂)。展开来看，等式左侧为 e([f(s) - v]₁, [1]₂)，右侧为 e([q(s)]₁, [s - z]₂)。由双线性性质，等式成立当且仅当 f(s) - v = q(s)·(s - z)，即 q(X) 确实是 (f(X) - v)/(X - z)。验证仅需两次配对运算，时间为常数，与多项式的次数无关。

KZG 承诺的核心优势在于其承诺值和证明值均为常数大小，验证时间也为常数。这使其成为链上验证场景的理想选择——无论底层计算多么复杂（对应的多项式次数多高），链上验证者只需处理固定大小的数据和固定次数的运算。

批量开启（batch opening）是 KZG 的另一重要特性。如果需要在多个点 z₁, z₂, …, z_k 上同时证明 f(z_i) = y_i，承诺者可以生成一个聚合证明，大小仍为常数。具体方法是构造零化多项式 Z(X) = ∏(X - z_i)，然后计算商多项式 q(X) = (f(X) - I(X)) / Z(X)，其中 I(X) 是在给定点上与 f 一致的插值多项式。这种批量开启机制在 PLONK 等证明系统中被大量使用，以减少通信开销。

批量验证（batch verification）的工程价值值得深入分析。假设需要验证 k 个独立的 KZG 开启 (C_i, z_i, y_i, π_i)，朴素方法对每个开启独立执行配对检查，共需 2k 次配对运算。利用随机线性组合技巧（random linear combination trick），验证者选取随机挑战 γ ←$ Z_p，将 k 个验证方程聚合为一个：

e(∑ᵢ γⁱ(Cᵢ - [yᵢ]₁) + ∑ᵢ γⁱzᵢ·πᵢ,  [1]₂) = e(∑ᵢ γⁱ·πᵢ,  [s]₂)

由 Schwartz-Zippel 引理，若任何一个开启无效，则聚合方程以至多 k/p 的概率通过验证——对于 256 位素数域，该概率可忽略不计。聚合后仅需 2 次配对运算，加上 k 次 G₁ 标量乘法及一次多标量乘法（multi-scalar multiplication, MSM），摊余成本显著下降。

在 BLS12-381 曲线上的典型性能数据可量化这一收益：单次配对约 1.5ms，单次 G₁ 标量乘法约 0.05ms。朴素验证 k=64 个开启需 128 次配对，约 192ms；批量验证仅需 2 次配对加一次 64 点 MSM，约 7ms，加速比超过 27 倍。当 k=1024 时，朴素方案约 3072ms，批量方案约 55ms，加速比接近 56 倍。随着 k 增长，摊余成本趋近于每个开启仅一次标量乘法的开销。下表汇总了不同批量规模下的性能对比：

可以看到，批量验证的收益随 k 增长呈亚线性递增——配对开销被摊薄为常数，剩余开销由 MSM 主导，而 MSM 受益于 Pippenger 算法的亚线性加速。

工程实现中还有若干关键优化。第一，Pippenger MSM 算法：将 k 次独立标量乘法合并为一次 MSM 运算，复杂度从 O(k·log p) 降至 O(k·log p / log k)，对大规模批量验证有显著收益。第二，SRS 预计算：将 SRS 中的点预先转换为仿射坐标并构建窗口表（window table），加速后续标量乘法。第三，蒙哥马利批量逆元（Montgomery’s batch inversion）：当验证涉及多个除法时，将 k 次模逆运算减少为 1 次模逆加 3(k-1) 次模乘。这些优化在 arkworks、blst 和 gnark 等主流密码学库中均有成熟实现，是 KZG 从理论方案走向生产部署的关键工程基础。

KZG 承诺还具有加法同态性：给定 C₁ = [f₁(s)]₁ 和 C₂ = [f₂(s)]₁，有 C₁ + C₂ = [(f₁+f₂)(s)]₁，即两个承诺的群运算结果等于对多项式之和的承诺。这一性质在构造线性化（linearization）技术时非常关键。

KZG 方案的主要局限在于需要可信设置以及依赖双线性配对（不具备后量子安全性）。这些限制促使研究者开发了多种替代的多项式承诺方案，我们将在下一节中讨论。

在深入更多多项式承诺方案之前，有必要对本文已经介绍的三种核心承诺方案进行横向对比。下表从安全属性、密码学假设、代数结构和实际应用等维度展示了它们的关键差异：

个人观察： KZG 承诺在近几年的零知识证明系统中近乎「一统天下」——PLONK、Marlin、以太坊的 danksharding 都选择了它。这个现象值得深思。KZG 的胜出并非因为它在理论上最优雅（Pedersen 承诺的完美隐藏性在信息论层面更令人满意），而是因为它在「链上验证」这个特定约束下提供了无可匹敌的效率：常数大小的证明、常数时间的验证。这本质上是一场工程权衡——整个 ZK 生态在用「可信设置」这张门票，换取「链上验证可行性」这个入场资格。以太坊 KZG 仪式吸引了 14 万参与者，实际上是在用社会共识的方式化解密码学上的信任假设。这是一种务实的策略，但也意味着整个生态在押注「1-of-N 诚实假设在实践中足够可靠」。如果未来出现高效的透明多项式承诺（如 FRI 的进一步优化达到接近 KZG 的验证效率），这一格局可能会被重新改写。

七、其他多项式承诺

除了 KZG 之外，密码学社区还开发了多种多项式承诺方案，每种方案在透明性、证明大小、验证时间、密码学假设等方面各有取舍。

FRI（Fast Reed-Solomon Interactive Oracle Proof of Proximity）是 zk-STARKs 使用的核心多项式承诺方案。FRI 不需要可信设置（transparent），仅依赖抗碰撞哈希函数，因此具有后量子安全性。其基本思想是通过交互式的”折叠”（folding）过程，将对一个度为 d 的多项式的接近性测试（proximity test）递归地归约为对度为 d/2 的多项式的测试，直到度数降为常数。每一轮折叠中，验证者发送一个随机挑战，证明者据此将多项式的偶数项系数与奇数项系数线性组合。FRI 的证明大小为 O(log² d)（在使用 Merkle 树进行承诺时），验证时间为 O(log² d)。虽然证明不如 KZG 那样简洁（常数级），但其透明性和后量子安全性使其在许多场景中极具吸引力。近年来，Circle STARKs 和 DEEP-FRI 等改进进一步降低了证明大小和验证时间。

IPA（Inner Product Argument）是 Bulletproofs 使用的多项式承诺方案。它的基本构造如下：给定向量 Pedersen 承诺 C = ⟨a, G⟩ + rH（其中 a 是系数向量，G 是生成元向量），证明者要证明 C 打开为特定的内积值。IPA 通过递归的”对半折叠”过程，每一轮将向量维度减半，同时累积”左右交叉项”L_i 和 R_i。经过 log n 轮后，向量维度降为 1，证明由 (L₁, R₁, …, L_{log n}, R_{log n}) 以及最终的标量组成。IPA 的证明大小为 O(log n) 个群元素，不需要可信设置，但验证时间为 O(n)（需要重建所有生成元的线性组合）。Halo 项目提出了一种巧妙的摊销技术，将验证时间在递归证明的上下文中分摊到 O(log n)。

Dory 是一种相对较新的多项式承诺方案，由 Jonathan Lee 在 2021 年提出。它利用配对运算和对称双线性群上的内积论证来实现 O(log n) 大小的证明和 O(log n) 的验证时间，同时保持透明性（不需要可信设置，仅需公共参数的生成）。Dory 在 Prover 和 Verifier 效率之间取得了不错的平衡。

下表对比了四种主要多项式承诺方案的关键特性：

选择哪种多项式承诺方案取决于具体的应用场景。在以太坊等对链上验证成本极度敏感的环境中，KZG 的常数大小证明和常数验证时间使其成为首选。在强调透明性和后量子安全的应用中（如 StarkNet），FRI 是自然的选择。在需要无可信设置且计算资源相对充裕的场景中（如 Monero 的范围证明），Bulletproofs/IPA 提供了良好的权衡。

八、承诺方案在协议中的应用

承诺方案在现代密码学协议中无处不在。以下分几个关键领域概述其应用。

在零知识证明中，承诺方案是证明系统的底层基础设施。不同的证明系统选择不同类型的承诺方案，但核心模式一致：证明者先对关键数据进行承诺以”锁定”自己的陈述，然后在验证者的随机挑战下选择性地打开承诺以证明陈述的正确性。以下通过三个具体例子展示承诺方案如何嵌入证明系统。

第一个例子：Pedersen 承诺嵌入 Sigma 协议。Sigma 协议是最经典的零知识证明框架，其中证明者要证明自己知道某个承诺的开启方式（即知识证明，proof of knowledge）。考虑以下场景：证明者持有 Pedersen 承诺 C = mG + rH 的开启 (m, r)，需要向验证者证明自己确实知道 (m, r)，但不泄露这两个值。协议流程如下伪代码所示：

Sigma-Pedersen-Knowledge(C, m, r):
  -- 公共输入: C ∈ G（Pedersen 承诺）
  -- 证明者秘密: (m, r) ∈ Z_p × Z_p，满足 C = mG + rH

  [承诺步] 证明者:
    a, b ←$ Z_p                    -- 随机选取盲化标量
    A ← aG + bH                    -- 计算承诺的"同构副本"
    发送 A 给验证者

  [挑战步] 验证者:
    e ←$ Z_p                       -- 随机挑战
    发送 e 给证明者

  [响应步] 证明者:
    s_m ← a + e·m  (mod p)         -- 线性组合消息分量
    s_r ← b + e·r  (mod p)         -- 线性组合随机数分量
    发送 (s_m, s_r) 给验证者

  [验证] 验证者:
    检查 s_m·G + s_r·H == A + e·C  -- 利用同态性一步验证

验证方程的正确性可以直接展开验证：s_m·G + s_r·H = (a + e·m)G + (b + e·r)H = aG + bH + e(mG + rH) = A + eC。由于 Pedersen 承诺的完美隐藏性，模拟器可以在不知道 (m, r) 的情况下生成合法的交互记录——先选择 e 和 (s_m, s_r)，再反向计算 A = s_m·G + s_r·H - e·C，因此该协议是完美零知识的。此外，Pedersen 承诺的同态性使得验证方程可以直接在群元素层面进行检查，无需任何解密或开启操作。通过 Fiat-Shamir 变换（令 e = H(C || A)），该交互式协议可转化为非交互式知识证明（NIZK），这正是许多实际系统中采用的方式。

第二个例子：KZG 承诺嵌入 PLONK。PLONK 是目前最广泛部署的通用零知识证明系统之一，其核心流程高度依赖 KZG 多项式承诺。简化后的协议骨架如下：

PLONK-Prove(circuit, witness):
  -- 第一轮：承诺线路多项式
  a(X), b(X), c(X) ← 将 witness 编码为多项式（在子群 H 上插值）
  [a]₁ ← KZG.Commit(a(X))         -- 承诺左输入
  [b]₁ ← KZG.Commit(b(X))         -- 承诺右输入
  [c]₁ ← KZG.Commit(c(X))         -- 承诺输出
  发送 ([a]₁, [b]₁, [c]₁)

  -- 第二轮：承诺置换多项式 z(X)（编码线路连接约束）
  -- 第三轮：构造商多项式 t(X) = 约束多项式 / Z_H(X)
  [t]₁ ← KZG.Commit(t(X))
  发送 [t]₁

  -- 第四轮：在挑战点 ζ 处打开所有承诺
  发送 a(ζ), b(ζ), c(ζ), z(ζ), ... 及 KZG 批量开启证明 π

PLONK-Verify([a]₁, [b]₁, [c]₁, [t]₁, 求值, π):
  -- 检查约束方程在 ζ 处成立
  -- 验证 KZG 批量开启证明（2 次配对）

整个过程中，KZG 承诺的常数大小保证了证明的简洁性（约 400 字节），加法同态性支持了线性化步骤（将多个多项式的约束合并为对单一多项式在 ζ 处的单次检查），批量开启技术则将 5-6 个独立的求值证明聚合为一个配对检查，这正是前文所述批量验证技巧的直接应用。

第三个例子：Merkle 树承诺嵌入 STARK。STARK（Scalable Transparent ARgument of Knowledge）使用 Merkle 树作为其多项式承诺的底层组件。证明者首先将计算轨迹（execution trace）的每一列编码为一个多项式，在一个扩展域（如 Reed-Solomon 码域，扩展率通常为 2-8 倍）上对多项式进行求值，然后将所有求值结果组织为 Merkle 树并发送树根作为承诺。验证者通过 FRI 协议进行低度测试（low-degree test）：在每轮折叠中，验证者发送随机挑战，证明者返回折叠后的多项式的 Merkle 树承诺。验证者最终随机采样若干位置（通常 30-80 个，取决于目标安全级别），要求证明者提供这些位置的 Merkle 认证路径（authentication path）以验证一致性。每条认证路径包含从叶节点到根的 O(log n) 个兄弟哈希值，验证者沿路径自底向上重新计算哈希并检查是否与已承诺的树根吻合。Merkle 树的对数级证明大小虽不如 KZG 的常数级简洁，但完全避免了可信设置，且仅依赖抗碰撞哈希函数（如 Poseidon、BLAKE3），因此具备后量子安全性。在 StarkNet 和 zkSync Era（STARK 模式）等生产系统中，这一架构已被大规模验证。

这三个例子揭示了一个统一模式：承诺方案在证明系统中充当”信息锁定层”——证明者通过承诺将自己绑定到特定的数据上，验证者通过选择性开启来高效检查数据的正确性。下表从承诺类型、关键性质利用和性能特征三个维度对比了三种嵌入方式：

承诺方案的性质（同态性、证明大小、验证效率）直接决定了上层证明系统的性能特征。

在安全多方计算中，承诺方案用于确保参与者不会在协议执行过程中”反悔”。在 GMW 协议的输入承诺阶段，每个参与者首先对自己的输入进行承诺，随后才开始交互式的电路评估过程。这保证了参与者的输入在协议开始后不会被更改。在 Shamir 秘密共享的可验证版本（Verifiable Secret Sharing, VSS）中，承诺方案被用于验证分发者是否正确地生成了秘密份额——Feldman VSS 使用离散对数承诺，Pedersen VSS 使用 Pedersen 承诺。

在区块链与分布式系统中，承诺方案的应用涵盖多个层面。在共识层面，承诺-揭示模式（commit-reveal scheme）被用于防止矿工或验证者操纵随机数生成过程——参与者先承诺自己的随机贡献，等所有人都提交承诺后再揭示。在数据可用性层面，以太坊的 EIP-4844（proto-danksharding）使用 KZG 承诺来实现 blob 数据的承诺与采样验证：每个 blob 附带一个 KZG 承诺，验证者可以通过随机采样来概率性地确认数据确实可用。在隐私交易层面，Pedersen 承诺被用于隐藏交易金额——Confidential Transactions（机密交易）技术利用 Pedersen 承诺的同态性来验证”输入之和等于输出之和”这一守恒条件，而无需揭露具体金额。Monero 和 Mimblewimble 协议都采用了这一技术。

在电子投票中，承诺方案保证投票者在投票截止前无法得知其他人的投票（通过对选票的承诺实现隐藏性），同时也保证投票者在提交后无法更改自己的选票（通过绑定性实现）。在可验证的洗牌（verifiable shuffle）协议中，混合网络（mixnet）的每个节点需要证明自己对选票进行了有效的重新排列和重新加密，而不泄露排列方式，这同样依赖于承诺方案。

在可验证计算（verifiable computation）领域，客户端将计算任务外包给不可信的服务器，服务器返回结果及正确性证明。整个过程的核心是：服务器将计算过程编码为多项式约束，使用多项式承诺对执行轨迹进行承诺，然后在客户端指定的随机点上打开承诺以证明计算的正确性。这种模式使得客户端仅需进行远小于原始计算的验证工作，适用于云计算中的计算完整性保证。

九、前沿发展

承诺方案是密码学中最活跃的研究方向之一，近年来涌现了多个令人兴奋的前沿方向。

透明多项式承诺（transparent polynomial commitment）的研究旨在消除可信设置的需求，同时保持接近 KZG 的效率。除了上文提到的 FRI 和 Dory 之外，Ligero/Brakedown 等方案基于线性码（linear code）构造透明的多项式承诺，在大域上的效率颇具竞争力。Binius 是一种面向二进制域（binary field）的多项式承诺方案，它利用了二进制域上乘法的高效性（无进位），在处理位运算密集型计算时表现出色。这些方案的共同目标是在不牺牲后量子安全性的前提下，将证明大小和验证时间推向更优的渐近界。

基于格的承诺方案（lattice-based commitment）是后量子密码学的重要研究课题。传统的 Pedersen 承诺和 KZG 承诺都依赖离散对数或配对假设，在量子计算机面前不堪一击。基于格的承诺方案利用短整数解（Short Integer Solution, SIS）问题或学习误差（Learning With Errors, LWE）问题的困难性，在量子计算时代仍能提供安全保证。Ajtai 在 1996 年基于 SIS 问题提出的哈希函数本身就可以被视为一种格承诺方案，且具有加法同态性。近年来，基于模块格（module lattice）的承诺方案在效率上取得了显著进步，使得基于格的零知识证明系统（如 Dilithium 签名方案中隐含的 Fiat-Shamir with Aborts 技术）逐步走向实用。

函数承诺（functional commitment）是承诺方案的一个高度通用的推广。在函数承诺中，承诺者对一个函数 f 进行承诺，然后可以针对任意输入 x 证明 f(x) = y。多项式承诺是函数承诺的一个特例（函数限制为多项式），而向量承诺也可以被视为函数承诺的一个特例（函数是一个查找表）。更一般地，函数承诺可以支持线性函数、多线性函数甚至任意可计算函数。de Castro 和 Peikert 在 2023 年提出了基于格的函数承诺方案，支持对任意有界深度电路的承诺。函数承诺在可验证数据库（verifiable database）和零知识虚拟机（zkVM）中具有广阔的应用前景。

增量可验证计算（Incrementally Verifiable Computation, IVC）与承诺方案的结合是另一个活跃的研究方向。在 IVC 中，一个长期运行的计算可以在每一步生成一个简短的正确性证明，每个新证明包含对前一步证明的验证。Nova 和 SuperNova 等方案通过”折叠方案”（folding scheme）实现了高效的 IVC——折叠方案可以被视为一种特殊的承诺方案，它将两个”松弛的”R1CS 实例折叠为一个，而无需进行完整的 SNARK 证明。

可聚合承诺（aggregatable commitment）和可更新承诺（updatable commitment）也是重要的研究方向。可聚合承诺允许将多个独立的承诺值和证明压缩为一个聚合承诺和聚合证明，这在区块链扩容中极为有用——例如将多个 rollup 批次的证明聚合为一个链上验证。可更新承诺允许在不重新计算整个承诺的情况下更新向量中的某些位置，这对于动态数据结构（如区块链状态树）的维护至关重要。

最后，承诺方案与安全硬件（secure hardware）的结合也值得关注。可信执行环境（Trusted Execution Environment, TEE）如 Intel SGX 和 ARM TrustZone 可以提供物理层面的隐藏性保证，与密码学承诺方案形成互补。在某些对性能要求极高的场景中，可以用 TEE 替代或增强密码学承诺的隐藏性，从而大幅降低计算开销。

承诺方案从最初朴素的”信封”直觉发展到如今高度精密的代数构造，始终处于密码学理论与工程实践的交汇点。从零知识证明到区块链扩容，从安全多方计算到后量子密码学，承诺方案的创新持续推动着整个密码学生态的进步。随着量子计算的逼近和隐私保护需求的增长，我们有理由相信，承诺方案在未来十年中将继续发挥其作为密码学基石的核心作用。

密码学百科系列 · 第 44 篇

← 上一篇：零知识证明系统 | 系列目录 | 下一篇：不经意传输与 PIR →