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为例)。
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://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8418611
2.BCG+ 讲述了算术电路的别的一种描述形式 https://eprint.iacr.org/2017/1066.pdf
视野开拓
根据1940年体制史观,可以发现安倍晋三内阁所实行的经济政策,并非“摆脱战后体制”,而是对战争时期及战后体制的复归。其基本方向是,否定市场的作用,强化国家对经济活动的干预。而这正是1940年体制的特点。第13页-《战后日本经济史》