首页
要闻详情
图标图标

用小学数学理解Pedersen Commitment

2020-04-10 11:36:51
1388
有没有一种密码学技术,只要简简单单的加减乘除法等小学数学知识也能看懂呢?

LMGzOTqGxTrRHDHqcax08BSkpNF4g9nY3EWYw8S6.jpeg

引言

还记得高中数学老师的口诀么?为了让学生能记下繁杂的数学公式,高中数学老师们绞尽脑汁为我们想出了很多“流芳百世”又朗朗上口的口诀:

奇变偶不变,符号看象限

一正、二定、三相等

正余余正符号同,余余正正符号异

……

但是…相信大部分同学都和我一样,高中数学除了口诀其他什么都记不得,以至于工作后看到复杂的数学公式,一时间脑袋里只有数学老师的魔性口诀在回荡,想要理解数学公式背后的逻辑简直是天方夜谭,学习基于密码学的各种区块链技术时也只能望文兴叹,感慨书到用时方恨少。

那么有没有一种密码学技术,只要简简单单的加减乘除法等小学数学知识也能看懂呢?当然有,这个技术就是Confidential Transaction与Mimblewimble的组件之一——Pedersen Commmitment(佩德森承诺)。

 

一些数学规律

在讲解Pedersen Commitment之前,我们要对其中所用的数学规律进行定义,放心,所有的数学规律都是小学生也能看懂的。佩德森承诺满足以下定义:

1.等式两边相等。

2.结合律。

3.交换律。

4.因式分解(除法)很难,至少相对加法乘法而言

为了让小学生也能看懂,我们对上述定义进行举例说明:

等式两边相等:如果我们知道5*3=5+5+5=15,以及25-10=15,那么我们能够很轻易的得出5*3=5+5+5=15-10=30这个结果。

结合律:对于2*3*4=24这个例子,得出(2*3)*4=2*(3*4)=24也是很容易的;对于加减法也是同理。

交换律:已知2+3+4=9,我们能知道2+(3+4)=(2+3)+4=9,乘法则是2*3=3*2=6

因式分解很难:对于21*11,得出其结果为231是轻而易举的;但如果只知道231这项结果,要求出它是哪两个数字相乘,难度是直线上升的,不论对人还是计算机而言,因式分解都比乘法或加法要困难很多。

除了理解上述定义,我们还要具备一点点椭圆曲线密码学(ECC)的相关知识,只要知道椭圆曲线满足上述定律,并且因式分解相当困难即可(又称为离散对数问题),其他内容网络上数不胜数,这里就不再赘述了。

 

什么是Pedersen Commitment?

Pedersen Commitment是密码学中承诺方案的一种,于1992年被Torben Pryds Pedersen在“Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing”一文中提出。目前Pedersen Commitment主要搭配椭圆曲线密码学使用,其核心可以用一项公式表达:

C=r*G+v*H

上述公式中,C为承诺值,G、H为特定椭圆曲线上的生成点,r代表着盲因子,v则代表着原始信息。由于G、H为特定椭圆曲线上的生成点,所以r*G、v*H都可以看作是相应曲线上的公钥(r、v同理可以看作私钥),由于椭圆曲线密码学的离散对数问题,很难解出私钥内容。另外需要注意的是上述所有的数值都属于整数集(都是整数)。

在之前的文章中,我们提到了承诺方案主要目的是提供“针对双方的信息互换方案”,通过隐藏关键值来避免信息泄露。Pedersen Commitment也不例外,但不同于普通的承诺方案,其可以通过不揭露相关信息来达到确认双方是否拥有某一个相同的值。让我们继续举例说明:

小诸和小周都想在赤壁之战使用“火攻”计策,但彼此不清楚对方是否知道“火攻”这两字信息,他们又不希望“火攻”被其他人知道。为了确认他们彼此都有这项信息,他们进行了以下操作:

1、小诸和小周决定使用Pedersen Commitment方案,公式彼此都知道,并敲定了G、H两项椭圆曲线生成点的值,上述内容都是对外公开的。

2、小诸随机生成了一个数字作为自己的r值,这里假定他使用了31这个数字;同理小周也生成了自己的r值,为50。

3、小诸和小周计算自己相应的承诺值,小诸的承诺值=31*G+火攻*H;小周的承诺值=50*G+火攻*H。

4、小诸和小周彼此交换自己的承诺值,这一步虽然承诺值对外公开了,但由于椭圆曲线的特性,其他人想通过承诺值计算出“火攻”和r值的内容是非常困难的。

5、小诸和小周彼此计算承诺值的差,即:小诸承诺值-小周承诺值=(31*G+火攻*H)-(50*G+火攻*H)。

之前提到,椭圆曲线满足了交换律,结合律,等式两边相等等规律,基于椭圆曲线的Pedersen Comitment同样也符合上述规律,所以小诸和小周承诺值的差可以写作:31*G+火攻*H-50*G-火攻*H=(31-50)*G+(火攻-火攻)*H,由于火攻-火攻=0(这里假设火攻转化为了相应数字),所以这项等式可以进一步简化为:小诸-小周=(31-50)*G。

6、小诸和小周此时可以选择公开二者承诺值的差,如果差值是完全相等的,他们彼此就可以确定对方知道了“火攻”这个信息;反之如果差值是不相等,也就代表着双方有一方没有拥有正确的信息。

看见了吗?整个计算过程中没有复杂的公式,双方只要通过加减乘法和简单的等式两边相等原则,即可验证彼此的信息是否相同。当然,在实际应用中为了保证隐私,G与H的值都是非常大的数字,承诺的安全性也由此转移至椭圆曲线密码学的离散对数问题上。即使攻击者知晓了承诺值,目前想要通过承诺值解出信息几乎是不可能的。

 

它能用在哪些地方呢?

Pedersen Commitment同其他承诺方案一样可以用来隐藏特定的信息,并且如果确定彼此的信息正确无误后,Pedersen Commitment还可以省略传统承诺方案的揭盲过程,这种特性令其相比于承诺方案而言更适合需要匿名交易的加密货币场景。

正如开头所言,Confidential Transaction和Mimblewimble协议都使用了Pedersen Commitment方案,Monero、Zcash、Grin与Beam等项目都或多或少的采用了Pedersen Commitment,当然光凭承诺是不能满足隐私需求的,这些项目都基于Pedersen Commitment进行了或多或少的改进,例如Grin和Beam所用的Mimblewimble协议,除了采用承诺以外,还采用了Cut-through与Coin-join等技术;Zcash还使用了Pedersen Hash与大量的ZK-SNARKs相关技术。

但总的来说,考虑到应用难度,UTXO结构相比账户结构更适合以Pedersen Commitment来实施匿名方案。

对于采用了UTXO结构的Wisdom Chain而言,Pedersen Commitment将更容易部署和实施,再加上可验证的编程规则,将匿名方案作为规则定义至事务中后不仅可以随时调用,Pedersen Commitment本身简单易用的特性还能将其改造以适用不同的环境。相信随着Wisdom Chain的不断进步,我们将能看到Pedersen Commitment在Wisdom Chain上大展身手。

来源:金色财经

风险提示及免责声明

文章来源于金色财经,转载注明原文出处,此文观点与指股网无关,理性阅读,版权属于原作者若无意侵犯媒体或个人知识产权,请联系我们,本站将在第一时间删掉 ,指股网仅提供信息存储空间服务。