理解零知识证明算法Bulletproofs（四）：Arithmetic Circuits

本文作者江小白，来自安比技术社区的小伙伴，本系列文章将对 Bulletproof 算法在 Range Proof 和 general arithmetic circuits 上的应用展开介绍。

一个是 general arithmetic circuits。

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

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

Circuit设计规则：

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

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

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

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

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

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

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

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

最后，附上一张对比图：

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

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

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

附录

1. Bulletproofs 论文：https://eprint.iacr.org/2017/1066.pdf

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

封面图片来源：Sergi Kabrera on Unsplash

长按二维码添加微信进群讨论零知识证明

info@secbit.io

安比（SECBIT）实验室