BTCV高分资讯 > 数字货币 > 他山之石|实现无状态以太网“凯特多项式承诺”

他山之石|实现无状态以太网“凯特多项式承诺”

作者:高分资讯来源:高分资讯 数字货币 2020年07月28日

技术突破是推动区块链工业向前发展的引擎。中国区块链研究所和链新闻都是关注区块链和密码学领域技术发展前沿的组织。为此,他们联合推出了“他山之石”栏目,介绍了世界上最值得关注的区块链技术进步以及在金融等行业的最新应用分析和趋势,以期为中国区块链行业“攻玉”提供借鉴和思考。

本文从技术角度介绍了一种凯特多项式承诺的密码方案,用于研究和实现无状态以太网。

原标题:《【他山之石】Kate 多项式承诺(polynomial commitments)》

作者:丹克拉德费斯特,埃瑟伦基金会研究员

汇编:中国砌块连锁研究所

本文已获作者授权,中文区域翻译起始权已由连文和毕安中国区块链研究所获得

在本文中,我们将介绍由凯特、扎弗鲁查和戈德堡提出的承诺方案1。然而,作为一篇介绍性的文章,本文并不打算对数学或密码学进行严格而完整的阐述。

该方案通常被称为“凯特多项式承诺方案”,是一种多项式承诺方案。它支持验证者计算对多项式的承诺,多项式可以通过其属性在任何后续位置打开:验证者需要证明多项式在某个位置的值等于声明的值。

一旦验证者将承诺值(椭圆曲线点)发送给验证者,相应的多项式就不能再改变,因此命名为“承诺”。验证者只能提供多项式的有效证明;如果你试图作弊,要么你得不到证明,要么证明会被检查者拒绝。

初步知识强烈建议不熟悉有限域、椭圆曲线和配对的读者提前阅读Vitalik Buterin关于椭圆曲线配对的文章。

与默克尔树的比较如果读者熟悉默克尔树,我希望能更直观地展示默克尔树和凯特承诺的区别。用密码学家的话来说,默克尔树是一个向量承诺:你可以使用深度为D的默克尔树来计算向量

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

(即一系列固定长度的元素)。你也可以用默克尔的证明和哈希证明位于I的元素ai是向量的一部分。

事实上,我们可以通过默克尔树得到多项式的承诺:n次多项式p(X)只是一个函数

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

其中pi是多项式的系数。

通过设置ai=pi并计算其系数的默克尔根,可以容易地获得n=2d-1次多项式。证明的评估意味着验证者想要告诉验证者对于某个z,p (z)=y。在这点上,验证者可以将所有pi值发送给验证者,然后验证者计算p (z)确实等于Y.

当然,这是一个非常低级的多项式承诺,但是它可以帮助我们理解它的优点。请注意以下属性:

1.承诺大小是一个单一的散列(默克尔根)。安全的加密哈希通常需要256位,即32字节。

2.为了证明一个评估,验证者需要发出所有pi来证明大小与多项式的次数成线性关系,并且验证者需要执行线性运算(通过计算,

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

在z位置找到多项式的值)。

3.该方案不隐藏多项式。验证者以非隐藏的方式发送完整的多项式和每个系数。

接下来,让我们讨论一下凯特方案使用这些指标能达到什么效果。

承诺大小是椭圆群的一个群元素,它支持配对。例如,BLS12_381有48个字节。证明了其大小不受多项式大小的影响,也是一个群元素。为了检查多项式次数和大小的影响,总是需要将两个组相乘一次并对两辆车进行配对。该方案基本实现了隐藏多项式——。事实上,会有无数的多项式凯特承诺完全一样。然而,完全隐藏还没有实现:如果你能猜出多项式(例如,当多项式很简单或者只有几组可能的多项式时),你就能找到承诺多项式。此外,任意求值的证明也可以组合成一个组元素。正是这些属性使得凯特方案在公共科学图书馆、SONIC和其他零知识证明系统中很受欢迎,并且它也可以在一般情况下用作向量承诺。这将在下面详细描述。

椭圆曲线和配对如上所述,我强烈推荐Vitalik Buterin关于椭圆曲线配对的文章,这篇文章介绍了理解这篇文章所需的所有预备知识,特别是有限域、椭圆曲线和配对。

假设G1和G2是两条配对为E的椭圆曲线:G1G2GT。G1和G2的阶数是p,发生器分别是g和h。用简化的符号,它们被写成

[x]1=xGG1和[x]2=xHG2

XFp是任意的。

可信设置(Trusted setup)假设可信设置完成,并且在某个秘密点s,当i=0时,验证者和验证者都可以获得[si]1和[si]2元素,n-1。

你可以这样理解这个秘密设置:用一台有气隙的计算机来计算随机数s,计算所有的组元素[si]x,然后通过电线发送这些元素(不是发送s),最后摧毁这台计算机。当然,这个方案并不完美,因为你必须相信计算机操作员不会通过秘密通信渠道获得秘密点S的值。

实际上,这通常是通过安全多方计算(MPC)来实现的,它允许一组计算机创建这个组元素,从而防止任何计算机获得秘密点S的值。要获得S,所有计算机需要联手(或同时被攻破)。

请注意,以下情况不会发生:仅选择随机组元素[s]1(其s未知),计算其他组元素,最后得到s。当s未知时,无法计算[s2]1。

现在,椭圆曲线加密基本上表明,它是不可能得到的S的实际值,通过组元素设置的信心。s是Fp中的一个数字,但是验证者不可能找出这个数字的实际值。验证者只能根据提供给他们的元素执行特定的计算。因此,验证者可以容易地计算c[si]1=csiG=[csi]1等。通过椭圆曲线乘法,还可以计算c[si]1d[SJ]1=(csidsj)g=[csidsj]1等。事实上,如果

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

是多项式,验证者可以计算:

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

有趣的是,当s未知时,几乎每个人都可以使用这个置信度设置在秘密点s找到多项式的值。除非他们得不到自然数输出,否则他们只能得到椭圆曲线点[p(s)]=p(s)G,但这是非常强大的。

凯特承诺,在凯特的承诺方案中,元素C=[p(s)]1是多项式p(X)的承诺。

也许你会问:验证者能否找到另一个具有相同承诺的多项式q(X)p(X),即[p(s)]1=[q(s)]1?假设这种情况存在。这意味着[p(s)-q(s)]1=[0]1,这意味着p(s)-q(s)=0。

目前,r(X)=p(X)-q(X)本身就是一个多项式。我们知道p(X)q(X)不是常数。众所周知,任何n次的非常数多项式最多可以有n个零:因为如果r(z)=0,r(X)可以被线性因子X-z整除;因为我们可以用一个线性因子来除每一个零,并且每一次除都会减少一次,所以次数不会超过^2

验证者不知道s,所以实现p(s)-q(s)=0的唯一方法是在尽可能多的位置实现p(X)-q(X)=0。然而,如上所述,因为验证者最多只能选择n个位置,所以成功的概率不高:因为n的值远小于曲线p的次数,所以他们不太可能选择点s来使p(X)=q(X)。为了感觉这个概率,假设采用当前可实现的最大置信度设置,其中n=228,并且将其与曲线阶数p 2 256进行比较:即使攻击者通过仔细设计使多项式q(X)至多等于p(X)n=228个点,该多项式将获得相同承诺(p(s)=q(s))的概率仅为。可能性极低。这实际上意味着攻击者无法达到他的意图。

到目前为止,我们已经证明了我们可以在秘密点s找到多项式的值,这使我们能够对一个唯一的多项式作出承诺。从某种意义上说,虽然有多个多项式具有相同的承诺C=[p(s)]1,但在实践中无法计算(密码学家称之为计算绑定)。

然而,如果不将多项式完全发送给验证者,我们仍然不能“打开”承诺。为了“打开”承诺,我们需要使用配对。如上所述,我们可以使用秘密元素来执行一些线性运算;例如,我们可以将[p(s)]1计算为对p(X)的承诺,或者将p(X)和q(X)的两个承诺相加,得到组合承诺p (x) q (x): [p (s)] 1 [q (s)] 1=[p (s)

现在我们不能将两个多项式相乘。否则,多项式的某些性质可以用来达到目的。尽管椭圆曲线本身不能做到这一点,但幸运的是,我们可以通过配对做到这一点:我们知道:

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

其中引入了一个新的符号[x]T=e(G,H)x。因此,尽管我们不能简单地将椭圆曲线中的两个域元素相乘,然后将乘积视为椭圆曲线元素(这是所谓同态加密的属性之一(FHE));椭圆曲线只是加法同态),但是如果我们在两条不同的曲线(一条在G1,一条在G2)中承诺它们,并且输出是一个G元素,我们可以将这两个域元素相乘。

这时,凯特证明的核心被触及了:记得我们之前提到过线性因子:如果多项式在z处为零,多项式可以被x-z整除。显然,反过来也是如此。——如果多项式可以被X-z整除,那么多项式在z处明显为零:被Xz整除意味着我们可以得到一些多项式q(X)的p (x)=(x-z)-q(X),并且多项式在x=z处明显为零。

现在我们必须证明p (z)=y。然后我们使用多项式p(X)-y——。因为多项式在z处明显为零,所以我们可以利用线性因子的知识。使q(X)等于多项式p(X)-y,除以线性因子X-z,即

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

这相当于q(X) (X-z)=p(X)-y.

凯特证明现在,由p(z)=y评估的凯特证明被定义为=[q(s)]1。对多项式p(X)的承诺定义为C=[p(s)]1。

验证者使用以下公式检查该证书:

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

请注意,验证者可以计算[s-z]2,因为[s-z]2只是来自可信设置的元素[s]2和z的组合,而z是多项式的求值点。类似地,[y]1可以通过将y作为声明值p(z)来计算。那么,为什么这个检查能使验证者相信p(z)=y;更准确地说,就是让验证者相信C承诺的多项式是y?

我们需要评估两个属性:正确性和可靠性。正确性意味着验证者能够执行我们定义的步骤,并且能够得到能够通过验证的证明。这通常并不难。可靠性意味着验证者不能证明“不正确”,也就是说,他不能说服验证者当y ' y,p(z)=y '时。

首先,在配对组中写出等式:

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

它的正确性现在应该是显而易见的,即方程q(X) (X-z)=p(X)-y,它需要在未知的随机点s进行评估。

那么,我们如何证明它的可靠性和验证者不能创造虚假证明呢?我们应该用多项式思维来思考这个问题。如果验证者根据我们的方法构造证明,它必须以某种方式用X-z除p(X)-y’。然而,p(z)-y '不是零,所以不能进行多项式除法,因为总是有余数。因此,这种方法显然不起作用。

在这一点上,我们必须尝试椭圆群:如果我们能计算出承诺C的一些椭圆群元素,结果会是什么?

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

显然,如果我们这样做,我们可以证明一切。直觉上,这很难实现,因为一些与S相关的值必须被索引,但是S是未知的。为了慎重证明,有必要提出配对密码假说,即q-SDH假说3。

现在,我们已经演示了如何证明多项式在某一点上的求值。请注意,这是值得注意的:通过只发送一个单独的组元素(例如,在BLS12_381中有48个字节),可以证明任意次数的多项式(假设228)在某个点包含某个值。在将默克尔树作为多项式承诺的一个小例子中,有必要发送228个元素和——个多项式的所有系数。

现在,我们必须更进一步,证明我们可以在任意个数的点上找到多项式的值,并且仍然只使用一个群元素。因此,我们需要引入另一个概念:插值多项式。假设有一系列的k值(z0,y0),(Z1,y1) … (ZK-1,yk-1):那么,一个小于k的多项式总是可以通过所有这些点。实现方法之一是使用拉格朗日插值多项式,它为多项式I(X)提供了一个清晰的公式:

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

现在,假设p(X)已经通过了所有的点。多项式p(X)-I(X)在z0,Z1,zk-1明显为零。这意味着它可以被所有线性因子(X-z0)、(x-Z1) … (x-ZK-1)整除。我们将所有因素组合成所谓的零多项式

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

你可以计算商数

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

请注意,这是可行的,因为p(X)-I(X)可以被Z(X)中的所有线性因子整除,所以它可以被整个Z(X)整除。

我们现在可以为求值(z0,y0),(Z1,y1)……(ZK-1,yk-1): =[q (s)] 1定义凯特多值证明——。请注意,这里仍然只有一个组元素。

现在,为了检查,检查器还必须计算插值多项式I(X)和零多项式Z(X)。由此,他们可以计算[Z(s)]2和[I(s)]1,从而验证配对方程

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

通过在配对组中写入等式,可以很容易地验证它是否可以用与单点Kate证明相同的方式来验证:

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

效果是惊人的:只要提供一个组元素,你就可以证明任何数量的评估可以达到100万次!只有48字节可以证明所有的评估!

凯特承诺用作向量承诺虽然凯特承诺方案被设计为多项式承诺,但它实际上可以成为非常好的向量承诺。向量承诺承诺向量A0.an-1,它提供了一种方法来证明你承诺人工智能给人工智能。它可以通过凯特的承诺方案来复制:让p(X)是一个多项式,其中所有的I都被视为p(i)=人工智能。我们现在有这样一个多项式,它可以通过拉格朗日插值多项式来计算:

他山之石 | 技术解读 Kate  多项式承诺,与默克尔树有何不同?

利用这个多项式,我们可以用一个群元素证明向量中任意数量的元素!这种方法的效率比默克尔树高得多:只需证明一个元素,一个默克尔证明将消耗n个散列!

延伸阅读

我们目前正在研究如何利用凯特的承诺创建一个无状态版本的以太博物馆。因此,我强烈建议在电子搜索论坛上搜索凯特,找到与当前研究相关的话题。

除了这篇文章之外,维塔利科对公共科学图书馆的介绍也很精彩,其中多项式承诺被广泛使用,凯特方案被作为主要例子。

1.https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf

2.这个结果经常被错误地引用为代数的基本定理。相反,代数的基本定理正好相反(只在代数闭域有效)。在复数数值中,每一个n次多项式都有n个线性因子。然而,尽管这里的简化结果对代数来说意义重大,但仍然缺少一个简明易懂的名称。

3.https://www.cs.cmu.edu/~goyal/ibe.pdf

资料来源:dankradfeist.de

标签: btcv