ZKSwap团队解读零知识证明算法之(四)Bulletproofs:Arithmetic Circuits

Bulletproofs 的算法由 Circuits 转化到 inner productor,生成的证明的大小和算术电路的乘法门的个数 n 有关 。

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

一个是 Range proof:

第一讲: 理解零知识证明算法之Bulletproofs –Range Proof 1

第二讲: 理解零知识证明算法之Bulletproofs –Range Proof 2

第三讲: 理解零知识证明算法之Bulletproofs –Range Proof 3

另一个是 general arithmetic circuits,本编文章就来主要分享 Bulletproofs 在后者上的应用。

Arithmetic Circuits

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

ZKSwap团队解读零知识证明算法之(四)Bulletproofs:Arithmetic Circuits插图

Circuit 设计规则:

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

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

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

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

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

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

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

ZKSwap团队解读零知识证明算法之(四)Bulletproofs:Arithmetic Circuits插图1

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 有左输入,右输入和输出三个属性

最后,附上一张对比图:

ZKSwap团队解读零知识证明算法之(四)Bulletproofs:Arithmetic Circuits插图2

总结 以上可以看出,对数算术环路的满足性问题,不同的算法具有不同的电路描述方式。 Zk-snark 算法由 Circuits 转化到 QAP,最终生成的证据仅仅再几十个字节大小;

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

附录

1.Bulletproofs 论文:https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8418611

2.BCG+ 讲述了算术电路的另外一种描述形式 https://eprint.iacr.org/2017/1066.pdf

人已赞赏
新闻精选

狗狗币的前世今生:创始人们为何抛弃了他?

2021-6-5 10:48:53

新闻精选

HashKey:全面解析 DeFi 资产跨链现状与发展趋势

2021-6-5 10:49:13

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索