KZG承诺

论文原文

预备知识

双线性配对

这里要注意，配对的 ${\mathbb{G}}_1$ 和 ${\mathbb{G}}_2$ 是两个不同的群

可信设置 (Trusted Setup)

需要预先生成一组公共参数字符串（CRS - Common Reference String）。这个过程通常涉及一个或多个参与者共同生成一个秘密值（MPC） $\alpha$，然后计算并公开一系列点： $\overrightarrow{CRS}=\{g,\alpha g,{\alpha }^{2}g,{\alpha }^{3}g,...,{\alpha }^{d}g,h,\alpha h\}=\{G_0,G_1,G_2...G_d,H_0,H_1\}$, 以下简记为 $\overrightarrow{G}$ 和 $\overrightarrow{H}$, 其中 $d$ 支持是你希望承诺的多项式的最大次数, $g\in {\mathbb{G}}_1,h\in {\mathbb{G}}_2$,既生成元。秘密值 $\alpha$ 必须在生成后被彻底销毁（Toxic waste）。如果 $\alpha$ 被泄露，任何人都可以伪造任何证明，整个方案的安全性就崩溃了。

根据椭圆曲线离散对数的困难性定理，在嵌入到多项式后，给定 $g$ 和 $\alpha g$，计算 $\alpha$ 是不可行的。

KZG承诺方案

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

承诺阶段Commit

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

计算承诺值:

$$C=c_0{G}_0+c_1{G}_1+...+c_n{G}_n=f(\alpha )g$$

既显然，证明者用他不知道的一个值 $\alpha$ 来对多项式进行承诺，满足了绑定性与隐藏性。

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

证明阶段Prove

验证者提供一个 $z$ ，要求证明 $f(z)=y$。

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

1. 证明者计算这个商多项式 $q(x)=\frac{f(x)-y}{x-z}$，记为 $q(x)=b_0+b_{1}x+b_2{x}^2+...+b_m{x}^m$。

2. 证明者计算证明 $\omega$（也称为witness 或者 $\pi$ ）： $w=b_0{G}_0+b_1{G}_1+...+b_m{G}_m=q(\alpha )g$ 。

验证阶段Verify

验证者拥有：(承诺 $C=f(\alpha )g$，要验证的点 $z$ 和声称的值 $y$，证明 $\omega =q(\alpha )g$，CRS中的 $G_0$ 、$H_0$ 和 $H_1=\alpha h$，双线性配对 $e$)

验证者执行以下检查：

$$e(C-y\cdot g,h)\equiv e(\omega ,H_1-z\cdot h)$$

正确性证明

• 左边：

$$e(C-y\cdot g,h)=e(f(\alpha )g-y\cdot g,h)=e((f(\alpha )-y)g,h)$$

• 右边：

$$e(\omega ,H_1-z\cdot h)=e(q(\alpha )g,(\alpha -z)h)$$

• 根据双线性性质和 $f(\alpha )-y=(\alpha -z)\cdot q(\alpha )$：

• • 左边：

$$e((f(\alpha )-y)g,h)=e(((\alpha -z)\cdot q(\alpha ))g,h)=e((\alpha -z)q(\alpha )g,h)=e(g,h{)}^{q(\alpha )(\alpha -z)}$$

• • 右边：

$$e(q(\alpha )g,(\alpha -z)h)=e(g,h{)}^{q(\alpha )(\alpha -z)}$$

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

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

优化

由于 ${\mathbb{G}}_2$ 是复数域的，运算较复杂，故而可以优化为如下形式 :

$$e(C+z\cdot \omega -y\cdot g,h)\equiv e(\omega ,H_1)$$

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

对于攻击者，假设已知( $\alpha$ , $C=f(\alpha )\cdot g$，$W=q(\alpha )\cdot g$ )，不知道多项式$f(x)$

1. 选择任一点 $z^{\prime }$ ，假设需要声称 $f(z^{\prime })=y_{fake}$ 。
2. 构造证明 $W_{fake}$ , 从 $W$ 中可以知道 $W=\frac{f(\alpha )-y}{\alpha -z}\cdot g$ , 重写为 $(\alpha -z)\cdot W=(f(\alpha )-y)\cdot g$ , 展开得到 $(\alpha -z)\cdot w=f(\alpha )\cdot g-y\cdot g$ , 又因为 $C=f(\alpha )\cdot g$ , 则又可以得到 $(\alpha -z)\cdot w=C-y\cdot g$ 。 显然攻击者可以计算出 $(\alpha -z^{\prime })\cdot W_{fake}=C-y_{fake}\cdot g$ , 这里由于 $\alpha$ 和 $C$ 已知，$z^{\prime }$ 和 $y_{fake}$ 自选。从而可以计算出 $W_{fake}=\frac{C-y_{fake}\cdot g}{\alpha -z^{\prime }}$
3. 这样，攻击者提交( $z^{\prime }$ , $y_{fake}$ , $w_{fake}$ )即可欺骗验证者。

Code

Details

# 这里使用 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 里的定义 pairing(G2,G1)
# 如果觉得验证慢的话可以直接 import 
# https://github.com/ethereum/py_ecc/tree/main/py_ecc/optimized_bls12_381
# 但是注意其他的相关运算也要换成里面的函数，比如 multiply, add, neg 等等
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("伪造验证成功")

批处理

假设 P 有两个多项式 $f_1(x)$ 和 $f_2(x)$，它们的承诺分别是 $C_1$ 和 $C_2$。需要证明 $f_1(z)=y_1$ 和 $f_2(z)=y_2$。以下给出一个聚合证明。

1. V 发送随机数 $r\to$ P
2. P 计算 $q(x)=f_1(x)+r\ast f_2(x)$ 与 $\omega =q(\alpha )g$
3. V 计算 $C_g=C_1+r\ast C_2$, $y_g=y_1+r\ast y_2$
4. V 验证 $e(C_g-y_g\ast g,h)\equiv e(\omega ,H_1-z\ast h)$