category
Pedersen承诺允许我们使用单个椭圆曲线点对任意大的向量进行编码,同时可以选择隐藏有关向量的任何信息。
它允许我们在不透露矢量本身的情况下对矢量进行声明。
动机
当我们讨论防弹零知识证明时,它们通常采用“我有两个内积为的向量”的形式。这可能看起来很基本,但你实际上可以使用这种机制来证明非常重要的主张。我们稍后再谈。
但为了使这样的证明有效,向量不能只存在于证明者的头脑中——否则证明者可以随意改变它们。它们必须是现实世界中的数学实体。一般来说,证明者不想只将这两个向量传递给验证者,但他们仍然需要向验证者“传递一些东西”,以表示他们已经选择了一对向量并且无法更改它。
这就是佩德森承诺进入画面的地方。
在内积论证中,证明者为两个向量提供了两个承诺,然后提供了一个证明,证明所承诺的向量具有一定的内积。
先决条件
我们假设读者已经熟悉椭圆曲线点加法和标量乘法,以及点“在曲线上”的含义
从符号上讲,大写字母是椭圆曲线点,小写字母是有限域元素。
我们说A它是一个椭圆曲线(EC)点,a是一个有限域元,aA是有限域元和EC点之间的点乘。该表达式A + B表示椭圆曲线点加法。
传统承诺
当我们设计智能合约中的commit-release函数时,它们通常采用以下形式
$$\text{commitment} = \mathsf{hash}(\text{value}, \text{salt}) $$
其中,\( \text{salt} \)这是一个随机值,用于防止攻击者进行暴力猜测。
例如,如果我们进行投票,选择的数量是有限的,因此可以通过尝试所有投票来猜测投票选择,看看哪些哈希匹配。
在佩德森承诺的情况下,盐变量的学术术语是致盲因素。因为它是随机的,所以攻击者“失明”,无法猜测所提交的值。
因为“承诺”的值无法被对手猜到,所以我们说这个承诺方案是隐藏的。
在揭示阶段,提交者揭示了价值和盐,因此另一方(或智能合约)可以验证它是否与原始承诺相匹配。不可能获得另一个可以导致相同承诺的对\((\text{value}, \text{salt}) \),所以我们说这个方案是绑定的——提交者不能在事后更改(即绑定到)他们的承诺值。
产生哈希的一对\((\text{value}, \text{salt})\)称为开口。说某人“知道承诺的开端”意味着他们知道(价值、盐)。揭示\((\text{value}, \text{salt})\)意味着开启承诺。
在讨论佩德森的承诺时,知道开始和开始承诺是有区别的。我们通常想证明我们知道开口,但不一定要打开它。
术语概述
- 隐藏承诺不允许对手知道提交者选择了什么值。这通常是通过包含攻击者无法猜测的随机项来实现的。
- 一个令人眼花缭乱的术语是使承诺无法猜测的随机数。
- 一个开口是将计算到承诺的值。
- 绑定承诺不允许提交者计算具有不同值的哈希。也就是说,他们找不到哈希值相同的两个(值、盐)对。
佩德森承诺
Pedersen承诺的行为与前面描述的commit-level方案非常相似,除了它们使用椭圆曲线组而不是加密哈希函数。
在离散对数假设下,给定椭圆曲线点V和U,我们无法计算x其中\(V=xU\)。也就是说,我们不知道它们的离散对数关系,即需要向U自身添加多少次才能得到V。
我们仍然称之为的离散对数,即使我们无法计算它,因为我们知道它的存在。所有(加密)椭圆曲线点都有离散对数,即使它们无法计算。
从这个意义上讲,椭圆曲线点乘的行为类似于哈希函数。只要我们只允许曲线顺序内的开口,它们就具有约束力。
然而,如果离散对数的范围很小,并且受到应用程序上下文(如投票选择)的限制,那么离散对数可能会变得难以猜测。
我们可以通过以下方式做出佩德森承诺:
$$ \text{commitment} = vG + sB $$
其中v是我们提交的值,s是盐(或致盲因子),B是另一个椭圆曲线点,提交者不知道B和G之间的离散对数关系。
我们应该强调,尽管离散对数是未知的,但点G和B是公开的,验证者和提交者都知道。
为什么提交者必须不知道和之间的离散对数关系
假设提交者知道这一点b使B = bG
在这种情况下,他们可以打开承诺
$$ \text{commitment} = vG + sB $$
与(v’, s’)他们最初承诺的价值不同。
以下是提交者如何作弊,如果他们知道这是的离散对数。
$$B = bG$$
提交者可以重写承诺方程式:
$$\begin{align*}
\text{commitment} &= vG + sB \\
&= vG + s(bG) \ \text{(substituting 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 Commitments只是一个使用不同哈希函数的普通提交揭示,那么有什么意义呢?
这个方案有几个优点。
佩德森承诺是加性同态的
给定一个点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承诺,我们可以将这些承诺加在一起,仍然有一个有效的开口。
佩德森承诺允许证明者对承诺价值的总和提出索赔。
我们可以在一个点中编码任意数量的点
我们使用G和B的例子也可以被认为是一个没有盲术语的二维向量承诺。但是我们可以添加任意数量的椭圆曲线点\([G₁, G₂, …, Gₙ]\),并提交任意数量的标量。(这里,\(G_1\)、\(G_2\)等表示同一组中的不同点,而不是不同组的生成器)。
佩德森矢量承诺
我们可以将上述方案更进一步,提交一组值,而不是一个值和一个令人眼花缭乱的术语。
矢量承诺方案
假设我们有一组随机椭圆曲线点
(我们不知道的离散对数),我们做以下操作:
\(C = \underbrace{v_1G_1 + v_2G_2 + … + v_nG_n}_\text{committed vector} + \underbrace{sB}_\text{blinding term}\)
由于提交者不知道任何\(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。所有点都需要伪随机选择。这仅仅是为了表示“这个椭圆曲线点的向量与这个场元素的向量相一致,而另一个EC点的向量则与另一个场元素的矢量相一致。”
我们可以提交的向量数量没有实际的上限。
读者练习:如果我们在添加两个向量之前对它们使用相同的\(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, y)\)进行哈希运算。否则,如果-值没有落在曲线上,则递增直到它落在。因为提交者没有生成点,所以他们不知道自己的离散日志。
练习:调整以下代码以生成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 # for bn128, y^2 = x^3 + 3
seed = "RareSkills"
x = int(sha256(seed.encode('ascii')).hexdigest(), 16) % field_mod
entropy = 0
vector_basis = []
# modify the code below to generate n points
while not has_sqrtmod_prime_power((x**3 + b) % field_mod, field_mod, 1):
# increment x, so hopefully we are on the curve
x = (x + 1) % field_mod
entropy = entropy + 1
# pick the upper or lower point depending on if entropy is even or odd
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)
# new x value
x = int(sha256(str(x).encode('ascii')).hexdigest(), 16) % field_mod
print(vector_basis)
在任何时候,都不应该通过拾取标量然后将其与生成器相乘来生成点,因为这会导致离散对数已知。您需要选择
通过哈希函数伪随机地计算曲线点的值,并确定它是否在曲线上。
可以从生成器(其具有已知的离散对数1)开始并生成其他点。
读者练习:假设我们将一个值向量提交给点
以及
.的离散对数
已知,但离散对数
尚不清楚。我们暂时忽略这个令人眼花缭乱的术语。提交者可以打开两个不同的向量吗?为什么或为什么不呢?
使用RareSkills了解更多信息如果您想学习零知识证明,请查看我们的ZK训练营。
- 登录 发表评论
- 14 次浏览
最新内容
- 1 week ago
- 1 week 2 days ago
- 1 week 3 days ago
- 1 week 4 days ago
- 1 week 4 days ago
- 1 week 4 days ago
- 1 week 4 days ago
- 1 week 4 days ago
- 1 week 4 days ago
- 1 week 4 days ago