承诺方案

Pederson承诺

离散对数下的Pederson承诺

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

椭圆曲线下的Pederson承诺

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

KGZ承诺

论文原文

多项式承诺的概念

想象一下，你有一个非常复杂的数学函数（在这里是多项式 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) 的其他信息。

预备知识

双线性配对

可信设置 (Trusted Setup)

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

KZG承诺方案

承诺阶段Commit

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

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

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

证明阶段Prove

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

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

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

证明者计算证明 $w$（也称为witness）： $w = q(\alpha)g$ 。

验证阶段Verify

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

验证者执行以下检查：

$e(C - y*g, g) \equiv e(w, (\alpha - z)g)$

正确性证明

• 左边：

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

• 右边：

$e(w, (\alpha - z)g) = e(q(\alpha)g, (\alpha - z)g)$

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

• • 左边：

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

• • 右边：

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

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

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