mt logoMyToken
总市值:
0%
恐慌指数:
0%
币种:--
交易所 --
ETH Gas:--
EN
USD
APP
Ap Store QR Code

Scan Download

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

收藏
分享

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

一个是 Range proof:

第一讲:

第二讲:

第三讲:

另一个是 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

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

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

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

附录

1.Bulletproofs 论文:

2.BCG+ 讲述了算术电路的另外一种描述形式

原创文章,作者:CoinKaola,如若转载,请注明出处:https://www.coinkaola.co/news/210142/

免责声明:本文版权归原作者所有,不代表MyToken(www.mytokencap.com)观点和立场;如有关于内容、版权等问题,请与我们联系。
相关阅读

华盛顿关于数字美元的选择

过去两周国会就数字美元举行的听证会被视为推进普惠金融的机会。这是一个崇高的目标,但我们要现实一点:说到底还是权力问题。拜登总统在上周的七国集团(G7)会议上呼吁建立联盟,以对抗中国的“一带一路”贸易规划,这与华盛顿对数字美元日益增长的兴趣有直接联系。中国央行的数字货币是其国际抱负的核心,一些人担心它会对美元作为世界储备货币的地位构成威胁。华盛顿的许多人认为,美元的主导地位体现在它赋予美国监管机构的执法权力上。美国监管机构能够追踪和控制美国银行的资金流入和流出,赋予它们制裁流氓行为和遏制犯罪活动的独特能力。问题在于,这种对货币权力的监督方式与金融包容性是对立的。以身份识别和跟踪为核心的这种模式给穷人带来了沉重的负担,他们通常无法使用身份识别系统、信用评分和其他手段来证明自己有资格获得银行服务。此外,正如听证会上的发言者所强调的那样,当有了通过单一中央账本管理的央行数字货币,政府能够监控和控制每个人的交易时,就有了对更广泛的隐私侵犯的合理担忧。因此,值得注意的是,有两个人表示支持数字美元:前商品和期货交易委员会主席、数字美元基金会创始人克里斯托弗·吉安卡洛和威拉米特大学法学院教授罗汉·格雷

矿业与碳排放矛盾的缩影:纽约州该选择环境还是比特币?

撰文: Scott Chipolina

从雅典到去中心化金融,了解DeFi的发展之路

好久不见~烤仔的 DeFi 课堂上课铃再次打响,这系列我们将一同解构 DeFi,尝试从更多的角度还原它真实的面貌。