老狼王のBlog

Appearance

承诺方案 ​

Pederson承诺 ​

离散对数下的Pederson承诺 ​

  1. 选择大素数p和生成元g、h，其中h=grmodph = g^r \; mod \; p，r是随机数。
  2. 承诺阶段：对消息m和随机数r，计算承诺值C=gm∗hrmodpC = g^m * h^r \; mod \; p。
  3. 打开阶段：公开(m, r)，验证者计算C′=gm∗hrmodp=CC' = g^m * h^r \; mod \; p = C是否成立。

椭圆曲线下的Pederson承诺 ​

  1. 选择椭圆曲线参数p、生成元G和随机数r。
  2. 承诺阶段：对消息m和随机数r，计算承诺值C=m∗G+r∗HC = m * G + r * H，其中H是椭圆曲线上的另一个点。
  3. 打开阶段：公开(m, r)，验证者计算C′=m∗G+r∗HC' = m * G + r * H是否等于C。

KZG承诺 ​

论文原文

多项式承诺的概念 ​

想象一下，你有一个非常复杂的数学函数（在这里是多项式 f(x)），你希望向别人证明关于这个函数的某些特定事实（比如“在 x=5 时，函数值是 10”），但你不想把整个函数的完整信息（所有系数）都告诉对方，因为可能太长或者涉及隐私。多项式承诺就是解决这个问题的密码学工具：

承诺阶段 (Commit)：你将你的多项式 f(x) “锁定”在一个加密的“信封”里，生成一个简短的、固定大小的“承诺值” C。你把这个 C 公开给验证者。此时，你已经“承诺”了 f(x)，无法再更改它（绑定性），但验证者无法从 C 看出 f(x) 的具体内容（隐藏性）。

打开/证明阶段 (Open/Prove)：之后，验证者可以要求你“打开”这个信封，证明 f(z) = y 对于某个特定的点 z 和值 y 成立。

验证阶段 (Verify)：你提供 y（即 f(z)）和一个简短的“证明” w。验证者利用公开的承诺 C、点 z、值 y、证明 w 以及一些公共参数，就能快速验证 y 是否确实是 f(x) 在 x=z 处的正确值。整个过程非常高效，且验证者无需知道 f(x) 的其他信息。

预备知识 ​

双线性配对 ​

双线性

这里要注意，G1G_1 和 G2G_2 是两个不同的生成元和群

可信设置 (Trusted Setup) ​

这是KZG的核心前提。需要预先生成一组公共参数（CRS - Common Reference String）。这个过程通常涉及一个或多个参与者共同生成一个秘密值 α，然后计算并公开一系列点： CRS = {g, αg, α²g, α³g, ..., α^d g} 其中 d 是你希望承诺的多项式的最大次数。秘密值 α 必须在生成后被彻底销毁。如果 α 被泄露，任何人都可以伪造任何证明，整个方案的安全性就崩溃了。

KZG承诺方案 ​

这里使用BLS12-381椭圆曲线。

承诺阶段Commit ​

假设证明者有一个次数不超过 dd 的多项式 f(x) = c₀ + c₁x + c₂x² + ... + cₙxⁿ。

证明者使用可信设置CRS生成的 α\alpha ，计算承诺值 CC 为： C = f(α)G_1 = (c₀ + c₁α + c₂α² + ... + cₙαⁿ)g 。

计算公开值 h = αG_2 。

这里的 G1G_1 和 G2G_2 是椭圆曲线上的基点。

这个 CC 就是 f(x)f(x) 的KZG承诺。它是一个椭圆曲线上的点，大小是固定的（一个群元素），无论 f(x)f(x) 有多复杂。

证明阶段Prove ​

验证者要求证明 f(z)=yf(z) = y。

则如果 f(z)=yf(z) = y，那么多项式 f(x)−yf(x) - y 在 x=zx = z 处有根。根据代数基本定理，这意味着 (x−z)(x - z) 可以整除 f(x)−yf(x) - y。因此，存在一个商多项式 q(x)q(x)，使得： f(x)−y=(x−z)∗q(x)f(x) - y = (x - z) * q(x)

证明者计算这个商多项式 q(x)q(x)。这可以通过多项式除法完成。

证明者计算证明 ww（也称为witness）： w=q(α)G1w = q(\alpha)G_1 。

验证阶段Verify ​

验证者拥有：(承诺 C = f(α)G_1，要验证的点 zz 和声称的值 yy，证明 w = q(α)G_1，CRS中的 G1G_1 、G2G_2 和 h=αG2h = \alpha G_2，双线性配对 ee)

验证者执行以下检查：

e(C−y∗G1,G2)≡e(w,h−z∗G2)e(C - y*G_1, G_2) \equiv e(w, h - z*G_2)

正确性证明 ​

  • 左边：

e(C−y∗G1,G2)=e(f(α)G1−y∗G1,G2)=e((f(α)−y)G1,G2)e(C - y*G_1, G_2) = e(f(\alpha)G_1 - y*G_1, G_2) = e((f(\alpha) - y)G_1, G_2)

  • 右边：

e(w,h−z∗G2)=e(q(α)G1,(α−z)G2)e(w, h - z*G_2) = e(q(\alpha)G_1, (\alpha - z)G_2)

  • 根据双线性性质和 f(α)−y=(α−z)∗q(α)f(\alpha) - y = (\alpha - z) * q(\alpha)：

    • 左边：

e((f(α)−y)G1,G2)=e(((α−z)∗q(α))G1,G2)=e((α−z)q(α)G1,G2)=e(q(α)G1,G2)(α−z)e((f(\alpha) - y)G_1, G_2) = e(((\alpha - z) * q(\alpha))G_1, G_2) = e((\alpha - z)q(\alpha)G_1, G_2) = e(q(\alpha)G_1, G_2)^{(\alpha - z)}

    • 右边：

e(q(α)G1,(α−z)G2)=e(q(α)G1,G2)(α−z)e(q(\alpha)G_1, (\alpha - z)G_2) = e(q(\alpha)G_1, G_2)^{(\alpha - z)}

  • 因此，左边 = 右边，验证通过。

如果等式成立，验证者就相信 f(z)=yf(z) = y。否则，证明无效。

如果 α\alpha 泄露该如何伪造证明 ​

对于攻击者，假设已知( α\alpha , C=f(α)∗G1C = f(\alpha)*G_1，W=q(α)∗G1W = q(\alpha)*G_1 )，不知道多项式f(x)f(x)

  1. 选择任一点 z′z' ，假设需要声称 f(z′)=yfakef(z') = y_{fake} 。
  2. 构造证明 WfakeW_{fake} , 从 WW 中可以知道 W=f(α)−yα−z∗G1W = \frac{f(\alpha) - y}{\alpha - z}*G_1 , 重写为 (α−z)∗W=(f(α)−y)∗G1(\alpha - z)*W = (f(\alpha) - y)*G_1 , 展开得到 (α−z)∗w=f(α)∗G1−y∗G1(\alpha - z) * w = f(\alpha)*G_1 - y*G_1 , 又因为 C=f(α)∗G1C = f(\alpha)*G_1 , 则又可以得到 (α−z)∗w=C−y∗G1(\alpha - z) * w = C - y*G_1 。 显然攻击者可以计算出 (α−z′)∗Wfake=C−yfake∗G1(\alpha - z') * W_{fake} = C - y_{fake}*G_1 , 这里 α\alpha 已知，z′z' 和 yfakey_{fake} 自选。这样可以计算出 Wfake=C−yfake∗G1α−z′W_{fake} = \frac{C - y_{fake}*G_1}{\alpha - z'}
  3. 这样，攻击者提交( z′z' , yfakey_{fake} , wfakew_{fake} )即可欺骗验证者。

Code ​

python
# 这里使用 https://github.com/ethereum/py_ecc/blob/main/py_ecc/bls12_381/bls12_381_curve.py
#         https://github.com/ethereum/py_ecc/blob/main/py_ecc/bls12_381/bls12_381_pairing.py

#type: ignore

from py_ecc.bls12_381.bls12_381_curve import (
    G1,
    G2,
    add,
    multiply,
    neg,
    is_on_curve,
    curve_order,  
)
from py_ecc.bls12_381.bls12_381_pairing import (
    pairing,
    final_exponentiate,
)
from sympy import Poly, Symbol

# 这里选择验证多项式 f(x) = x^3 + 2x + 3 
x = Symbol('x')
fx = Poly(x**3 + 2*x + 3, x)
# 1. 生成承诺

# 生成私钥alpha
import random
alpha = random.randrange(1, curve_order)  # alpha ∈ Fr

# 计算承诺C = f(alpha) * G1
C = multiply(G1, int(fx.subs(x, alpha)) % curve_order)

# 生成公开值h = alpha*G2
h = multiply(G2, alpha % curve_order)

# 2. 证明阶段
# 这里证明f(z) = y, 其中z = 5, y = f(5) = 5^3 + 2*5 + 3 = 138
z = 5
y = int(fx.subs(x, z)) % curve_order
# y = 140 
# z = 6
# 这里可以取消注释试一试提交错误的值会怎么样

# 计算商多项式 q(x) = (f(x) - f(z)) / (x - z)
fx_poly = Poly(fx, x)
g = Poly(x - z)

qx, _ = fx.div(g)

# 计算证明w = q(alpha) * G1
w = multiply(G1, qx.subs(x, alpha))

# 3. 验证阶段
# 验证者知道(C, G1, G2, h, z, y, w)
# 验证 e(C - y*G1, G2) == e(w, h - z*G2) 等价于 
# 验证 e(G2, C - y*G1) == e(h - z*G2, w) // 左右调换, 详见 bls12_381_pairing.py 里的定义
left = pairing(G2, add(C, neg(multiply(G1, int(y)))))
right = pairing(add(h, neg(multiply(G2, z))), w)
assert final_exponentiate(left) == final_exponentiate(right), "验证失败"
print("验证成功")

# --------------------------------------------------
# 伪造攻击
# 假设泄露了alpha
alpha_ = alpha

# 1. 伪造
y_fake = 99
z = 99

# 2. w_fake = (C - y_fake*G1) * mod_inverse(alpha - z)

# 计算 C - y_fake*G1
C_minus_yG1 = add(C, neg(multiply(G1, y_fake)))
# 计算 (alpha - z) 的模逆元
inv_alpha_minus_z = pow((alpha_ - z) % curve_order, -1, curve_order)
# w_fake = (C - y_fake*G1) * mod_inverse(alpha - z)
w_fake = multiply(C_minus_yG1, inv_alpha_minus_z)

# 3. 验证阶段
left_fake = pairing(G2, add(C, neg(multiply(G1, int(y_fake)))))
right_fake = pairing(add(h, neg(multiply(G2, z))), w_fake)
assert final_exponentiate(left_fake) == final_exponentiate(right_fake), "伪造验证失败"
print("伪造验证成功")

其他的一些多项式承诺方案对比 ​

几种常见的poly-commitment方案比较

Merkle承诺树 ​

1. 树生成 ​

假设有一组数据块 D=[d1,d2,d3,...,dn]D = [d_1, d_2, d_3, ..., d_n]，我们使用一个加密哈希函数 H（如 SHA-256）来构建 Merkle 树。

  1. 叶子节点：首先，对每个数据块计算哈希值，作为叶子节点：L_i = H(d_i) \quad \text{对于 } i = 1, 2, ..., n
  2. 内部节点：然后，逐层向上构建树。每个内部节点是其两个子节点哈希值的哈希：N_j = H(L_{2j-1} || L_{2j}) \quad \text{对于 } j = 1, 2, ..., \frac{n}{2}

CopyRight@ 2025 Klizz