什么是Pedersen承诺及其工作原理

Pedersen 承诺允许我们用一个椭圆曲线点来编码任意大的向量，同时可以选择性地隐藏与该向量相关的任何信息。

它允许我们对一个向量进行声明，而无需透露向量本身。

动机

当我们讨论 Bulletproof 零知识证明时，它们通常是“我有两个向量的内积是 $v$”的形式。这看起来很简单，但实际上我们可以利用这一机制证明非常非平凡的声明。稍后我们将讨论这个问题。

但是，要让这样的证明有效，向量不能只是存在于证明者的脑海里——否则，证明者可以随意更改它们。它们必须是真实世界中的数学实体。一般来说，证明者不想只是将两个向量传递给验证者，但他们仍然需要“传递某种东西”给验证者，以表明他们已经选择了一对向量并且无法更改它。

这就是 Pedersen 承诺的作用所在。

在内积论证中，证明者提供两个 承诺 给两个向量，然后提供一个证明，证明所承诺的向量具有特定的内积。

前提条件

我们假设读者已经熟悉 椭圆曲线点加法 和标量乘法，以及点“在曲线上的”含义。

在符号上，大写字母表示椭圆曲线点，小写字母表示有限域元素。

我们说 $A$ 是一个椭圆曲线（EC）点，$a$ 是一个 有限域 元素，而 $aA$ 是有限域元素 $a$ 和 EC 点 $A$ 之间的点乘。表达式 $A + B$ 表示椭圆曲线点加法。

传统承诺

当我们在智能合约中设计承诺揭示函数时，它们通常是以下形式

$$ \text{commitment} = \mathsf{hash}(\text{value}, \text{salt}) $$

其中 $\text{salt}$ 是一个随机值，用于防止攻击者通过暴力猜测 $\text{value}$。

例如，如果我们承诺一票，选择的选项有限，因此投票选择可以通过尝试所有的投票并查看哪个哈希值匹配来猜测。

在 Pedersen 承诺的情况下，salt 变量的学术术语是 blinding factor（盲因子）。因为它是随机的，攻击者被“盲目”而无法猜测所承诺的值。

由于对手无法猜测“承诺”值，我们可以说这一承诺方案是 hiding（隐藏的）。

在揭示阶段，承诺者揭示值和盐，这样另一方（或智能合约）就可以验证其是否与原始承诺匹配。无法获取另一对 $(\text{value}, \text{salt})$，从而产生相同的承诺，因此我们说该方案是 binding（绑定的）——承诺者在事后不能更改（即被绑定）他们承诺的值。

导致哈希的 $(\text{value}, \text{salt})$ 对被称为 opening（揭示值）。说某人“知道承诺的揭示”意味着他们知道 (value, salt)。揭示 $(\text{value}, \text{salt})$ 意味着 打开 这个承诺。

在讨论 Pedersen 承诺时，知道 揭示和 打开 承诺之间有区别。我们通常想证明我们 知道 揭示，但不必 打开 它。

术语总结

• 一个 hiding（隐藏的）承诺不允许敌手知道承诺者选择了什么值。这通常通过包含一个对攻击者无法猜测的随机项来实现。
• 一个 blinding（盲因子）项是使承诺无法猜测的随机数。
• 一个 opening（揭示）是将计算结果与承诺相等的值。
• 一个 binding（绑定的）承诺不允许承诺者用不同的值计算哈希。也就是说，他们无法找到两个哈希为相同值的 (value, salt) 对。

Pedersen 承诺

Pedersen 承诺的行为与前面描述的承诺-揭示方案非常相似，只是它们使用的是椭圆曲线群而不是加密哈希函数。

在离散对数假设下，给定椭圆曲线点 $V$ 和 $U$，我们无法计算 $x$ 使得 $V = xU$。也就是说，我们不知道它们的 离散对数关系 ，即需要将 $U$ 自身加几次才能得到 $V$。

即使我们无法计算 $x$，我们仍然称其为 $U$ 的离散对数，因为我们知道它是存在的。所有（加密的）椭圆曲线点都有离散对数，即使这些对数无法计算。

从这个意义上讲，椭圆曲线点乘法像哈希函数一样行为。只要我们只允许在曲线阶内的揭示，它们就是绑定的。

然而，如果离散对数的范围很小，并且受应用上下文（如投票选择）的限制，则离散对数可能变得可以猜测。

我们可以通过以下方式进行隐藏的 Pedersen 承诺：

$$ \text{commitment} = vG + sB $$

其中 $v$ 是我们要承诺的值，$s$ 是盐（或盲因子），$B$ 是另一个椭圆曲线点，承诺者不知道 $B$ 和 $G$ 之间的离散对数关系。

我们应该强调，尽管离散对数未知，点 $G$ 和 $B$ 是公共的，且对验证者和承诺者都是已知的。

为什么承诺者必须不知道 $B$ 和 $G$ 之间的离散对数关系

假设承诺者知道 $b$ 使得 $B = bG$。

在这种情况下，他们可以将承诺揭示为

$$ \text{commitment} = vG + sB $$

到与他们最初承诺的值不同的 $(v’, s’)$。

如果承诺者知道 $b$ 是 $B$ 的离散对数，他们就可以作弊。 $$ B = bG $$

承诺者可以重写承诺方程： $$ \begin{align} \text{commitment} &= vG + sB \\ &= vG + s(bG) \ \text{（替换B = bG）} \\ &= (v + sb)G \end{align} $$

承诺者选择一个新的值 $v’$并计算 $s’$：

$$ \begin{align} v’ + s’b = v + sb \\ s’ = \frac{v + sb - v’}{b} \end{align} $$

然后，证明者将 $(v’, s’)$ 提交为伪造的揭示。

这是可行的，因为 $$ \begin{align} \text{commitment} &= v’G + \frac{v + sb - v’}{b} B \\ \text{commitment} &= v’G + (v + sb - v’)G \\ \text{commitment} &= \cancel{v’G} + vG + s(bG) - \cancel{v’G} \\ \text{commitment} &= vG + sB \\ \text{commitment} &= \text{commitment} \\ \end{align} $$ 因此，承诺者必须不知道他们所使用的椭圆曲线点之间的离散对数关系。

实现这一点的一种方法是让验证者提供椭圆曲线点给承诺者。然而，更简单的方法是通过伪随机地选择椭圆曲线点，以随机透明的方式进行选择。给定一个随机的椭圆曲线点，我们不知道它的离散对数。

例如，我们可以从生成器点开始，对 $x$ 和 $y$ 值进行哈希处理，然后用它来种子伪随机但确定性的搜索下一个点。

Pedersen 承诺有什么用？

看起来 Pedersen 承诺只是一个普通的承诺-揭示，使用不同的哈希函数，那么有什么意义？

这个方案有几个优点。

Pedersen 承诺是加法同态的

给定一个点 $G$，我们可以将两个承诺相加 $a_1G + a_2G = (a_1 + a_2)G$。

如果我们包含随机的盲因子项，我们仍然可以通过将盲因子项加在一起并提供给验证者来进行有效的揭示。让 $C_1$ 和 $C_2$ 是承诺。现在考虑当我们将 $C_1 + C_2$ 相加时会发生什么：

$$ \begin{aligned} C_1 &= a_1G + s_1B \\ C_2 &= a_2G + s_2B \\ C_3 &= C_1 + C_2 \\ \pi &= s_1 + s_2 \\ \text{committer reveals…} \\ &(a_1, a_2, \pi) \\ \text{and the verifier checks…} \\ C_3 &\stackrel{?}{=} a_1G + a_2G + \pi B \end{aligned} $$

或者，验证者可以检查

$$ C_3 = (a_1 + a_2)G + \pi B $$

常规哈希（如 SHA-256）无法以这种方式相加。

给定两个使用相同椭圆曲线点进行的 Pedersen 承诺，我们可以将两个承诺相加，并且仍然可以为它们保留有效的揭示。

Pedersen 承诺允许证明者对承诺值的和做出声明。

我们可以在一个点中编码任意数量的点

我们使用 $G$ 和 $B$ 的例子，也可以被视为没有盲因子的二维向量承诺。但我们可以添加任意数量的椭圆曲线点 $[G₁, G₂, …, Gₙ]$ 并承诺任意多个标量。（此处，$G_1$、$G_2$等表示同一群中的不同点，而不是不同群的生成元）。

Pedersen 向量承诺

我们可以进一步推进上述方案，承诺一组值，而不是一个值和一个盲因子。

向量承诺方案

假设我们有一组随机的椭圆曲线点 $(G₁,…,Gₙ)$（我们不知道它们的离散对数），我们可以做以下操作：

$$ C = \underbrace{v_1G_1 + v_2G_2 + … + v_nGn}\text{承诺的向量} + \underbrace{sB}_\text{盲因子} $$

这让我们承诺 $n$ 个值到 $C$ 并用 $s$ 隐藏它。

由于承诺者不知道任何 $G_i$ 的离散对数，他们也不知道 $C$ 的离散对数。因此，这个方案是绑定的：他们只能揭示 $(v₁,…,vₙ)$ 来随后生成 $C$，无法生成另一个向量。

向量承诺可以组合

我们可以将两个 Pedersen 向量承诺相加，以得到一个对两个向量的承诺。但这仍然只允许承诺者揭示原始向量。重要的实现细节是，我们必须使用不同的椭圆曲线点进行承诺。

$$ \begin{align} C_1 &= v_1 G_1 + v_2 G_2 + \ldots + v_n G_n + r B \\ C_2 &= w_1 H_1 + w_2 H_2 + \ldots + w_n H_n + s B \\ C_3 &= C_1 + C_2 \end{align} $$

通过将 $C_1$ 和 $C_2$ 相加，我们实际上承诺了一个更大的大小为 $2n$ 的向量。

这里，$rB$ 和 $sB$ 是盲因子项。即使承诺者承诺零向量，承诺仍然会看起来像一个随机点。

承诺者稍后将揭示原始向量 $(v₁…vₙ)$ 和 $(w₁…wₙ)$ 及盲因子 $r + s$。这是绑定的：他们不能揭示另一对向量和盲因子项。

我们使用 $(G₁,…,Gₙ)$ 来承诺一个向量，而使用 $(H₁,…,Hₙ)$ 进行另一个向量，并不意味着 $G$ 点之间有特殊关系，$H$ 点之间有特殊关系。所有的点都需要伪随机选择。这仅仅是记号上的方便，表示“这个椭圆曲线点的向量与这个字段元素的向量对应，而另一个椭圆曲线点的向量与另一个字段元素的向量对应。”

我们可以承诺的向量数量没有实际上的上限。

读者练习： 如果我们在将这两个向量相加之前，使用相同的 $G₁…Gₙ$ 来承诺，承诺者如何能揭示出 $C_3$ 中两个不同的向量？举个例子。使用不同的点集合 $H₁…Hₙ$ 如何防止这种情况？

读者练习： 如果承诺者尝试在向量内切换相同的元素，会发生什么？

例如，他们承诺：

$$ C_1 = v_1G_1 + v_2G_2 + \ldots + v_nG_n + rB $$

但用前两个元素交换来揭示：

$$[v_2, v_1, v_3, …, v_n]$$

也就是说，他们交换了前两个元素，其他人保持不变。假设向量 $G₁…Gₙ$ 没有改变顺序。

透明生成随机点

我们如何生成这些随机的椭圆曲线点？一个显而易见的解决方案是使用一个可信设置，但这不是必需的。通过以透明的方式随机选择这些点，承诺者可以设定点，使他们无法知道其离散对数。

他们可以选择生成点，混合一个公开选择的随机数，然后哈希该结果（并取模字段模数）以获得另一个值。如果结果的 $x$ 值在椭圆曲线上，则用该值作为下一个生成点，并再次哈希 $(x, y)$ 对。否则，如果 $x$ 值不落在曲线上，则增加 $x$，直到它在曲上。由于承诺者不是生成这些点，因此他们不知道它们的离散对数。

练习： 调整以下代码以生成 n 个拥有未知离散对数的点：

from py_ecc.bn128 import is_on_curve, FQ
from py_ecc.fields import field_properties
field_mod = field_properties["bn128"]["field_modulus"]
from hashlib import sha256
from libnum import has_sqrtmod_prime_power, sqrtmod_prime_power

b = 3 # 对于 bn128, y^2 = x^3 + 3
seed = "RareSkills"

x = int(sha256(seed.encode('ascii')).hexdigest(), 16) % field_mod 

entropy = 0

vector_basis = []
## 修改下面的代码以生成 n 个点
while not has_sqrtmod_prime_power((x**3 + b) % field_mod, field_mod, 1):
    # 增加 x，因此希望我们在曲线上
    x = (x + 1) % field_mod
    entropy = entropy + 1

## 取决于 entropy 是偶数还是奇数，选择上点或下点
y = list(sqrtmod_prime_power((x**3 + b) % field_mod, field_mod, 1))[entropy & 1 == 0]
point = (FQ(x), FQ(y))
assert is_on_curve(point, b), "sanity check"
vector_basis.append(point)

## 新的 x 值
x = int(sha256(str(x).encode('ascii')).hexdigest(), 16) % field_mod 
print(vector_basis)

在任何时候都不应通过选择标量然后将其与生成元相乘来生成点，因为这会导致离散对数已知。你需要通过哈希函数伪随机（随机）选择曲线点的 $x$ 值，并确定它是否在曲线上。

可以从生成元开始（其离散对数为 1），然后生成其他点。

读者练习： 假设我们将值向量承诺在点 $G_1$ 和 $G_2$ 上。$G_1$ 的离散对数是已知的，但 $G_2$ 的离散对数不是已知的。我们目前忽略盲因子。承诺者能否揭示两个不同的向量？为什么或为什么不？

了解更多可以访问 RareSkills，如果你希望 学习零知识证明。

• 原文链接： rareskills.io/post/peder...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～