什么是 “Pedersen 承诺”?

作者:RareSkills

来源:https://www.rareskills.io/post/pedersen-commitment

“Pedersen 承诺” 让我们可以使用一个椭圆曲线点来表示任意大的向量,同时可以选择隐藏关于这个向量的任何信息。它给了我们一个重要的元件,让我们可以证明用这个点来编码的向量,又不必暴露这个向量本身。

动机

在讨论 Bulletproot 零知识证明技术的时候,人们常常这样说:“我们有两个向量,它们的内积(inner product)是 c。” 似乎这很普通,但实际上,你可以用这个机制来证明非常复杂的陈述(claim)。我们后面展开说。

但为了让这样的证明系统可以工作,这些向量就不能只有证明者知道 —— 不然证明者就可以随意改变它们。它们必须是真实世界中的数学实体。一般来说,证明者肯定不想直接把这两个向量交给验证者,但依然需要 “传递一些东西” 给验证者,表示自己已经选定了一对向量,不能再改变了。

这就是我们需要 Pedersen 承诺的地方。

前置知识

我们假设读者已经熟悉了椭圆曲线点加法和点乘法,以及 “曲线上的一个点” 意味着什么。如果你还不了解,请参考我们的《零知识证明之书》的前面四章。

至于记号,我们用 [A] 来表示一个椭圆曲线(EC)点,用 a 表示一个有限域内的元素,而 a[A] 表示这个有限域元素 a 与椭圆曲线点 [A] 的点乘法。而表达式 [A] + [B] 表示这两个点的点加法

传统的承诺方案

在设计智能合约中的承诺揭晓函数时,我们通常使用这样的形式:

commit = hash(value, salt)

其中的 “salt(盐)” 是一个随机数值,用来阻止攻击者的暴力搜索猜测。比如说,如果我们是在承诺投出的一票,由于票的可选项是有限的,那么我们的票到底投给了谁,就可以通过尝试所有的选项、检查哈希值匹配来发现。(而加了盐,这样的暴力搜索就行不通了。)

盐在这种场景中的用法,有一个学术名词,叫做 “盲化(blinding)因子”。因为它是随机的,攻击者就仿佛失明了,猜不出被承诺的数值(上面式子中的 “value”)到底是什么。

因为攻击者无法通过 “诺言” 猜测出其背后的数值,我们就说这种承诺方案有藏匿效果

而揭晓数值的阶段,承诺者揭晓数值和盐(在文献中,它们叫做 “契机(opening)”),另一方(或者智能合约)可以验证它们跟原本的承诺相匹配。如果在同一承诺方案中不可能用另一对 (value, salt) 来获得相同的诺言,我们就说这种方案有绑定效果 —— 承诺者一旦揭晓诺言,就不可能再改变被承诺的数值(也即两者就绑定了)。

术语总结

  • 藏匿效果的承诺方案不允许敌手知晓承诺者选择的数值。这通常是通过加入一个攻击者无法猜测的随机数来实现的。
  • 盲化因子则是让被承诺的数值无法通过暴力搜索得出的随机数。在一些我们并不在乎零知识性(而只在乎简洁性)的场景中,可能不使用盲化因子。
  • 契机则是计算出诺言的数值(被承诺的数值和盐)。
  • 绑定效果的承诺方案不允许承诺者使用不相同的契机计算出相同的诺言。也就是说,他们不应能够找出两对 (value, salt),计算得出相同的诺言(在这里是哈希值)。

Pedersen 承诺

Pedersen 承诺方案的模式没有什么不同,只不过,它用的是椭圆曲线群,而不是密码学哈希函数。

在 “椭圆曲线上离散对数难解” 假设下,给定椭圆曲线点 [U] 和 [G],我们无法计算出能让 [U] = u[G] 的 u 。

用 Python 语言的代码来说,就是:

from py_ecc.bn128 import G1, multiply

u = 569723450 # chosen randomly
U = multiply(G1, u)

print(U, "cannot compute the discrete log of U")

我们说,u 是 [U] 的离散对数。即使我们并不能计算出 u,也依然管它叫 [U] 的离散对数,因为我们知道它存在。所有的(密码学)椭圆曲线点都有一个离散对数,即使我们无法计算出它。

在这个意义上,椭圆曲线点乘法就像一种哈希函数。它们是有绑定效果的,只要我们只允许在曲线阶数内的契机。

不过,虽然它有绑定效果,我们无法通过点反转出其离散对数,如果 u 的取值范围很小,我们就会遇到(跟上述投票案例)完全一样的问题。敌手可以通过遍历所有可能的 x、计算 x[G] 来猜测我们的 x 。

我们可以用下列方式实现 “Pedersen 式隐匿”:

commitment = v[G] + s[Q]

这里的 v 就是我们要承诺的数值,而 s 是盐(盲化因子);Q 是另一个椭圆曲线点,承诺者不知道其离散对数。

我们要强调的是,虽然它们的离散对数都是未知的,[G] 和 [Q] 都是公开的,验证者和承诺者都知晓。

为什么不能让承诺者知道 [Q] 的离散对数

假设承诺者知道 [Q] 背后的离散对数 [Q] = d[G] 。这会让承诺者可以找出两个拥有相同诺言的契机。原理如下。

[C] = v[G] + s[Q]
    = 10[G] + 15[Q]
    = 10[G] + 15[dG]
    
[C′] = 11[G] + (15d−1)[G] 

[C] = [C′]

读者可以手动为 d 代入任意数字,看看它是怎么工作的。

承诺者不能知道他们所用的椭圆曲线点的离散对数关系。

保证这一点的一个办法是,让验证者来为承诺者提供这个椭圆曲线点。不过,更简单的办法是,以随机且透明的办法选出一个椭圆曲线点,例如,伪随机地选出椭圆曲线点。给定一个随机的椭圆曲线点,我们就不知道其离散对数。

举个例子,我们可以从生成元([G])开始,哈希其 x 坐标值和 y 坐标值,然后喂入一个伪随机但确定的函数,用来寻找下一个点。

Pedersen 承诺有用在哪?

看起来 Pedersen 承诺只是使用另一种哈希函数的常规承诺方案,它有用在哪儿?

这个方案有许多好处。

同态可加

给定一个生成元 [G],我们可以将两个承诺加在一起:a[G] + b[G] = (a + b)[G] 。即使我们再加入随机盲化隐私,我们依然可以制作出有效的契机:

C1=a[G]+s1[Q]𝐶1=𝑎[𝐺]+𝑠1[𝑄]

C2=b[G]+s2[Q]𝐶2=𝑏[𝐺]+𝑠2[𝑄]

C3=C1+C2𝐶3=𝐶1+𝐶2

承诺揭晓(a,b,s1+s2)承诺揭晓(𝑎,𝑏,𝑠1+𝑠2)

验证者检查C3?=a[G]+b[G]+(s1+s2)[Q]验证者检查𝐶3?=𝑎[𝐺]+𝑏[𝐺]+(𝑠1+𝑠2)[𝑄]

常规的密码学哈希函数(比如 SHA256)是做不到这样的。

(在 Pedersen 承诺中)b[G] 和 s[Q] 在相加时不会彼此 “冲突”。

你看下面这个等式成立吗?

(a[G]+b[H]) + (c[G]+d[H]) = (a+c)[G] + (c+d)[H]

(这里的 [G] 和 [H] 都是未知离散对数的两个椭圆曲线点)。

你可以把椭圆曲线点理解成正交维度(orthogonal dimensions)上的一种线性组合(linear combination)的基(basis)。

当存在有限域元素 a1,a2,b1,b2𝑎1,𝑎2,𝑏1,𝑏2,以及椭圆曲线点 [G] 和 [H],且 [G] 不等于 [H] 、a1≠a2𝑎1≠𝑎2、b1≠b2𝑏1≠𝑏2,即使 a1[G]+b1[H]=a2[G]+b2[H]𝑎1[𝐺]+𝑏1[𝐻]=𝑎2[𝐺]+𝑏2[𝐻],依然不可能绕过离散对数难题而解出 (a1,a2,b1,b2)(𝑎1,𝑎2,𝑏1,𝑏2) 。

而且,当我们的椭圆曲线群的阶数足够大的时候,靠运气找出这样的匹配,更是渺茫。

换句话说,假设两个人计算各自的承诺 [C] = a[G] + b[H] 和 [C'] = a'[G] + b'[H],且 a≠a′𝑎≠𝑎′ 且 b≠b′𝑏≠𝑏′。只要 [G] 和 [H] 的离散对数未知,[C] 就不太可能等于 [C'] 。

Pedersen 承诺是 zk 友好的

为椭圆曲线上的加法和乘法制作电路相对容易,因为唯一要求是常规的算术运算;但常规的哈希函数却要用到比特位移(bitshifting)和异或运算(XOR),需要栋梁的约束才能编码成零知识证明的电路。

我们可以将任意多的点编码成一个点

我们使用 [G] 和 [Q] 的例子也可以认为是一个不设盲化因子的 2 维的向量承诺。但我们也可以加入任意多的椭圆曲线点 [G1,G2,…,Gn][𝐺1,𝐺2,…,𝐺𝑛],承诺任意多个标量。

Pedersen 向量承诺

我们把上述方案再推进一步,从而承诺一组数值,而不是一个数值和一个盲化因子。

向量承诺方案

假设我们有一组随机的椭圆曲线点([G1,G2,…,Gn][𝐺1,𝐺2,…,𝐺𝑛])(它们的离散对数我们全都不知道,那么我们可以这样做:

[C]=v1[G1]+v2[G2]+…+vn[Gn]+r[Q][𝐶]=𝑣1[𝐺1]+𝑣2[𝐺2]+…+𝑣𝑛[𝐺𝑛]+𝑟[𝑄]

这让我们可以用一个诺言 [C] 承诺许多个数值,并用 r 来藏匿。

因为承诺者并不知道任何一个生成元背后的离散对数,所以他们将无法知道 [C] 的离散对数。因此,这个方案有绑定效果:他们只能用 [v1,v2,…,vn][𝑣1,𝑣2,…,𝑣𝑛] 来产生诺言 [C],无法用另一组向量做到。

向量承诺可以聚合

我么可以把两个 Pedersen 向量承诺相加,得到一个对两个向量的诺言。承诺者依然可以用原本的向量来揭晓。这里有一个重要的实现细节,就是原本的两个向量承诺必须使用两组不同的椭圆曲线点来生成。

[C1]=v1[G1]+v2[G2]+…+vn[Gn]+r[Q][𝐶1]=𝑣1[𝐺1]+𝑣2[𝐺2]+…+𝑣𝑛[𝐺𝑛]+𝑟[𝑄]

[C2]=w1[H1]+w2[H2]+…+wn[Hn]+s[Q][𝐶2]=𝑤1[𝐻1]+𝑤2[𝐻2]+…+𝑤𝑛[𝐻𝑛]+𝑠[𝑄]

[C3]=[C1]+[C2][𝐶3]=[𝐶1]+[𝐶2]

这里,r[Q] 和 s[Q] 是盲化因子。即时承诺者没有承诺向量,整个诺言看起来依然像是一个随机的点。

承诺者后面可以揭晓原本的向量 [v1,v2,…,vn][𝑣1,𝑣2,…,𝑣𝑛] 和 [w1,w2,…,wn][𝑤1,𝑤2,…,𝑤𝑛],以及盲化因子 r + s。这也是有绑定效果的,无法用另一组向量和盲化因子产生相同的诺言。

我们给一组向量使用 [G1,G2,…,Gn][𝐺1,𝐺2,…,𝐺𝑛]、给另一组使用 [H1,H2,…,Hn][𝐻1,𝐻2,…,𝐻𝑛] 不暗示着这些 [G_i] 生成元和 [H_i] 生成元内部有什么特殊关系。所有这些点都需要伪随机地选出来。它们仅仅只是记号上的重合,便于我们直接说 “这些椭圆曲线点向量与这组有限域元素向量搭配,那些椭圆曲线点向量与那些有限域元素向量搭配”。

我们可以承诺的向量的数量是没有内在上限的。

考考读者:如果我们给两个承诺使用相同的生成元 [G1,G2,…,Gn][𝐺1,𝐺2,…,𝐺𝑛],然后再相加,承诺者如何为 [C3][𝐶3] 揭晓两组不同的向量?举个例子,使用另一组椭圆曲线点 [H1,H2,…,Hn][𝐻1,𝐻2,…,𝐻𝑛] 是不是可以避免这一点?

考考读者:如果承诺者在揭晓时调换被承诺的值的位置,会发生什么事?

举个例子,他承诺的是:

[C1]=v1[G1]+v2[G2]+…+vn[Gn]+r[Q][𝐶1]=𝑣1[𝐺1]+𝑣2[𝐺2]+…+𝑣𝑛[𝐺𝑛]+𝑟[𝑄]

然而公开的契机是:

[v2,v1,v3,v4,…,vn][𝑣2,𝑣1,𝑣3,𝑣4,…,𝑣𝑛]

也就是说,承诺者调换了前面两个元素的位置,但其它东西一切不变。假设向量 [G1,G2,…,Gn][𝐺1,𝐺2,…,𝐺𝑛] 是不可调换的。

透明地生成随机点

我们如何能生成这些随机的椭圆曲线点?一种显然的解决方案是使用一个受信任的启动设置,但这并不是必要的。承诺者可以通过透明地随机选出一些我们不知道其离散对数的点。

他们可以先选择生成元 [G],混合一个公开选出的随机数,然后哈希这个结果(需要对 field_modulus 取模),从而获得另一个数值。如果这个结果作为 x 值能够落在椭圆曲线上,那么就使用它作为下一个生成元,再次哈希它的 (x, y) 坐标值。相反,如果它作为 x 值,在椭圆曲线上没有对应点,那我们就递增 x 值,直到它有对应的椭圆曲线点。因为并不是由承诺者来生成这些点的,他们也不可能知道这些点的离散对数。这种算法的实现细节交给读者当作练习。

在任何情况下,都不应该通过乘法来生成一个点,因为这将导致我们知道其离散对数。你需要通过一个哈希函数来伪随机地得出一个 x 值,然后看看它是否落在椭圆曲线上。

从生成元 [G] 开始也是可以的(众所周知,其离散对数是 1),然后生成其它点。

留给读者的练习:假设我们用点 [G1] 和 [G2] 承诺了一个 2 维向量。[G1] 的离散对数已知,但 [G2] 的离散对数未知。(我们暂时忽略盲化因子)。承诺者能够使用另一个 2 维向量来揭晓这个承诺吗?为什么呢?

(完)


RareSkills 2024-06-07
https://www.btcstudy.org/2024/06/07/what-are-pedersen-commitments-and-how-they-work/

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇

您不能复制本页内容(。・_・。)ノI’m sorry~