注册
关闭
区块链大帝

区块链大帝

发布于 2019-12-19 阅读数 4494

理解零知识证明算法之Bulletproofs:Arithmetic Circuits

前言

 

Bulleproofs算法有两个方面的应用。

一个是Range proof:

第一讲:https://www.8btc.com/media/530155

第二讲:https://www.8btc.com/media/532874

第三讲:https://www.8btc.com/media/534000

一个是general arithmetic circuits。

本编文章就来主要分享Bulletproofs在后者上的应用。

 

Arithmetic Circuits

了解ZK-SNARK算法应该都知道算术环路的概念,下面一张图展示了zk-snark算法中,算术环路的设计规则(以V神的x3 + x + 5 = 37为例)。

理解零知识证明算法之Bulletproofs:Arithmetic Circuits

Circuit设计规则:

1.由乘法门和加法门组成,每个门固定两个输入一个输出;

2.不标记通过加法门连接乘法门的线,如图中绿线,仅起到连接作用;

3.同一条线直接或间接连接多个乘法门,仅表示为一条有效的线,为了方便理解,用紫色虚线表示其连接关系;

4.MulGate处的取值为图中红色字体所示

5.黄色线条为有效连接线

6.橙色线条表示MulGate对应的一阶约束

那Bulletproofs算法的算术环路的设计规则是什么样的呢?我们看看下图(仍以V神的x3 + x + 5 = 37为例)。

理解零知识证明算法之Bulletproofs:Arithmetic Circuits

Circuit设计规则:

1.由乘法门和加法门组成,每个门固定两个输入一个输出;

2.不标记加法门

3.不标记有常量的乘法门

4.红色字体表示乘法门的索引

5.黄色字体表示乘法门的输入和输出

6.橙色线条表示乘法门对应的一阶约束

7.蓝色线条表示相邻乘法门间的一致性约束

因此,一个完整有效的算数电路应该满足:

1.每个乘法门对应的的约束成立

2.乘法门之间的一致性约束成立

Zk-snark的算术电路通过R1CS满足了上述两个条件。

1.每个R1CS表示一个乘法门的约束

2.相邻乘法门的输出是下一个乘法门的输入,如图中的y,sym_1,sym_2

Bulletproofs的算术环路以通过以下两种方式满足上述两个条件:

1.每个乘法门对应的约束成立

2.上个乘法门的输出等于下个乘法门的输入。

看起来两个算法的证明一个算术电路有效的思想是一样,但是由于两个电路的标注规则不同,就产生两个不同的约束结果。

Zk-snark算法以valid wires为基本要素,每个wire有左输入,右输入,和输出三个属性

Bulletproofs算法以valid Mulgate为基本要素,每个Mulgate有左输入,右输入和输出三个属性

最后,附上一张对比图:

理解零知识证明算法之Bulletproofs:Arithmetic Circuits

总结

以上可以看出,对数算术环路的满足性问题,不同的算法具有不同的电路描述方式。

Zk-snark算法由Circuits转化到QAP,最终生成的证据仅仅再几十个字节大小;

Bulletproofs的算法由Circuits转化到inner productor,生成的证明的大小和算术电路的乘法门的个数n有关O(log(n*Q ),电路越大,证据越大

附录

1.Bulletproofs 论文:chrome-extension://cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html?file=https%3A%2F%2Feprint.iacr.org%2F2017%2F1066.pdf

2.BCG+ 讲述了算术电路的另外一种描述形式 chrome-extension://cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html?file=https%3A%2F%2Feprint.iacr.org%2F2016%2F263.pdf

  • 0
区块链大帝
区块链大帝

0 条评论