隐私加密系列|详解Bulletproofs零知识证明协议的工作原理

  • 时间:
  • 浏览:40
  • 来源:区块链技术网

在这篇文章中,我将解释Bulletproofs零知识证明协议的工作原理,并讨论我们正在使用Bulletproofs构建的隐私资产协议和隐私智能合约语言。

背景知识

零知识范围证明是隐私交易系统(例如比特币机密交易,链上的隐私资产和许多其他协议)的关键组成部分。范围证明允许验证者确保隐私值(如资产金额)是非负的。这防止用户通过隐私使用负数伪造价值。由于每笔交易都涉及一个或多个范围证明,因此在证明大小和验证时间方面,它们的效率是交易性能的关键。

承诺(Commitment)-对消息m的承诺Com(m)隐藏了,这意味着它没有显示m。它也具有约束力,这意味着如果您对m作出承诺,则无法将其打开给其他消息m’。在Bulletproofs的上下文中,承诺是指Pedersen承诺,它具有加性同态的附加属性,这意味着仅当a + b = c时Com(a)+ Com(b)= Com(c)。

零知识证明(Zero-knowledge proof)-一个证明某个陈述是真的,而不透露该陈述的秘密。通常通过对声明所涉及的秘密作出承诺,并与证据共享承诺。

零知识范围证明(Zero-knowledge range proof)-一个秘密值在一定范围内(从0到2^n-1)的证明。证据通常与对秘密价值的承诺共享,以便能够得到验证。

内积(Inner product)-两个向量按项相乘的总和。

表示法:例如a,2 ^ n(这是n长度向量2 ^ 0、2 ^ 1,...,2 ^ {n-1})和0 ^ n(即 n长度向量0s)。内积表示为c = <a,b>,其中a和b是相同长度的向量,c是标量。

范围证明(Range Proof)

奥列格·安德列夫(Oleg Andreev)的Bulletproofs范围证明协议的程式化插图

我们想证明以下陈述:0≤v <2 ^ n

我们知道,如果这是真的,则v必须是长度为n的二进制数。例如,如果n = 4和v = 3(我们正在检查3是否在0到2 ^ 4_1的范围内),那么这意味着v必须能够分解为4的位表示形式。位长(如果实际上在范围内):

我们希望以内积的形式来表示这一声明,因为Bulletproof引入了非常高效的内积证明,我们将在下一节中讨论这一点。

如果v_bits实际上是位表示形式,则v应该等于v_bits和向量2^n(它是n长度向量2^0,2^1,...,2^{n-1})的内积。v我们可以通过在下图中添加检查1来做到这一点。

另外,我们需要确保v_bits实际上仅由位组成(没有其他讨厌的数字,例如5或-1000……那是不好的!)我们可以通过在下图中添加检查2来做到这一点。

接下来,我们使用挑战标量将这两个语句组合起来,并向它们添加盲因子。这背后的数学并不困难-只是乏味-最终以c=<a,b>的形式给出了一个内部乘积语句。也就是说,我们得到一个语句,如果该语句是真的,那么我们知道v在0到2^n的范围内。您可以按照一步一步的数学来说明如何在我们的范围证明注释中创建该语句。

内积证明(Inner Product Proof)

在范围证明部分,我提到我们的目标是以内积的形式创建一个语句,以提高效率。让我们更详细地讨论什么是内积,以及如何能够有效地证明内积!

内积证明是证明c是向量a和向量b的内积,即c=<a,b>。

这可能有助于了解内积是什么:

然后我们得到一个随机挑战标量x,我们用它来组合a和b的hi和lo两部分来创建a,这也给了我们一个新的c,b'>。

内积证明是如何达到这种效率的直觉是,在每一步中,它都将a和b向量的大小减半。因此它需要log(n)个步骤,因为在许多步骤之后,a和b的长度是1(基本情况)。

因此,如果我们从原始的a和b向量及其乘积c开始,则可以将每个向量划分为hi和lo的一半:

然后我们得到一个随机挑战标量x,我们用它来组合a和b的hi和lo两部分来创建a'和b',这也给了我们一个新的c'=<a',b'>。

在做数学运算以扩展c’时,请注意c’的前两个项与c相同!因此,我们可以简化要相对于c编写的c’的表达式,以及可以称为术语L和R的表达式:

在每一轮中,证明者将L和R发送给验证者,并使用a’,b’,c’作为a,b,c重复下一轮。注意在每一步如何将向量a和b的长度减半!

经过log(n)步骤后,我们得出一个基本情况,其中a均为长度1。然后不再需要进行压缩,证明者可以简单地发送a,c 验证者。

验证者现在具有基本情况的标量a,c',以及每个log(n)步骤的标量L和R。然后验证者可以从基本情况开始逆转该过程。他们可以通过检查c’= a’* b’来轻松验证基本情况。他们可以通过使用该步骤中的c’,L,R来验证c的计算,从而在每个更高的步骤中检查计算是否正确完成,直到完成所有检查为止。

聚合范围证明(Aggregated Range Proof)

聚合范围证明对性能很好,因为它们允许m方生成其单个语句的聚合证明(m范围证明),这样聚合证明比m单个范围证明更小,验证速度更快。创建聚合证明的协议比创建单个范围证明稍微复杂一些,并且需要涉及各方的多方计算。在我们的实现中,我们使用一个集中的经销商来协调m个参与方之间的通信。

约束系统证明(Constraint System Proof)

约束系统是两种约束的集合:

约束系统非常强大,因为它们可以表示任何可有效验证的程序。零知识约束系统证明是对某个秘密输入满足约束系统中所有约束的证明,而无需透露那些秘密输入是什么。例如我们可以创建一组约束(“gadget”),强制某些输出是某些输入的有效置换。我们称之为shuffle gadget。在一个只有两个输入和两个输出的简单shuffle gadget中,我们可以将可能的状态表示为:

如果我们得到一个随机标量x,那么我们可以用一个方程的形式来表示这个需求:(a-x)*(B-x)=(C-x)*(D-x)。由于根置换时多项式的相等性,我们知道如果方程适用于随机x,那么{a,B}必须在任意顺序上等于{C,D}。当我们在约束系统中实现此2-shuffle gadget时,它看起来像这样:

在第6行中,我们得到挑战标量x。在第8行和第10行中,我们做了两个乘法约束:(A-x)*(B-x)=input_mul和(C-x)*(D-x)=output_mul。在第12行中,我们做了一个线性约束:input_mul-output_mul=0,它约束input_mul=output_mul。

Cloak

隐私资产计划的目标是使资产价值和资产类型保持隐藏的交易,从而允许进行多资产交易,其中外部观察者无法推断正在进行的交易,但可以验证交易的正确性。Cloak是使用Bulletproofs构建的机密资产计划。

Cloak专注于一件事:证明某些具有不同资产类型的价值已正确地从投入转移到产出。Cloak确保每种资产类型的价值保持平衡(以使一种类型不会相互转化),数量不会溢出组订单(换句话说禁止负数量)并且数量和资产类型均应保密。Cloak没有指定如何验证传输或哪种分类帐表示这些传输:这些都留在围绕Cloak构建的协议中进行定义。

Cloak使用“shuffle”、“merge”、“split”和“range proof”等小工具的集合构建一个约束系统,这些小工具组合在一个称为“cloaked transaction”的小工具下。所有小工具的布局仅由输入和输出的数量决定,而不受资产的实际值影响。这样所有相同大小的事务都无法区分。例如对于区块链的验证者或查看者来说,这就是3输入3输出掩蔽事务的样子:

这就是3输入3输出cloaked transaction对于试图证明输入为$5,¥3,¥4,输出为¥3,¥6,$3的事务有效性的验证者来说的样子。请注意相同类型($)的资产是如何分组、合并在一起,然后拆分和重新排列为目标金额的:

事实证明Cloak具有惊人的效率:与仅需要范围证明的单资产交易(例如针对比特币的隐私交易建议)相比,支持已发行资产所需的其他约束和小工具所占比重不足20%乘数。并且由于内积证明,对证明大小的影响几乎为零。这说明了Cloak协议中每个小工具所需的乘数:

ZkVM

ZkVM的目标是制造一种允许隐私性的智能合约语言。它以以前的智能合约语言工作为基础,旨在在安全环境中运行并输出确定性日志的表达语言。它使用Cloak来验证加密的资产流是否正确,并使用Bulletproofs约束系统证明来添加约束,以约束操作值和正确执行智能合约。

总结

希望本文能帮助您了解Bulletproofs零知识证明协议的工作原理,以及我们根据该协议构建的内容。

相关文章阅读:

隐私加密系列|详解Bulletproofs与Mimblewimble两者的关系

隐私加密系列|欺诈证明和SPV(轻量级)客户-说起来容易做起来难吗?

隐私加密系列|MuSig Schnorr签名方案

隐私加密系列|Mimblewimble的核心无脚本脚本(Scriptless Scripts)

猜你喜欢

土耳其里拉暴跌过半,总统埃尔多安向议会提交加密货币法案

在全球疫情还未结束的大背景下,土耳其经济出现了严重通货膨胀,土耳其里拉今年更是一开年币值就开始溜滑梯。较之年初,土耳其里拉近日对美元贬值幅度一度超过50%。

2021-12-27

加密货币世界最有权势的四个亿万富翁

加密货币交易所FTX的香港办公室里,有高级的金融白领也有十几岁的青少年。

2021-12-22

加密货币钱包的这些知识你知道几个?

对于存储区块链资产的钱包,还有不少人没搞懂,尤其是地址、公钥、密码、私钥、助记词、Keystore等专有名词,让人一头雾水。可是,如果不搞清楚这些概念,很可能会造成区块链资产的损失。

2021-12-17

明年加密货币行情走势如何?应该如何决策

任何东西的价格的搜集最强有力的信号,我已经人性化的意志。作为一个社会,我们利用货币形式作为生产维持我们的事物所花费的能量的抽象。价格告诉我们多少能量可以平衡给定商品或服务的供需。当社会扭曲定价信号时,供需就会变得不平衡,从而导致能源浪费。浪费了足够的能量,文明就会堕落;希望被一个新的社会结构所取代,该结构组织得当,以更好的方式节约能源。随着加密货币当前和未来的所有令人兴奋的发展,我们绝不能忽视当前令人兴奋的最重要的因素......BOOLMARKET(市场)。

2021-12-15

2022年加密行业深度研究报告

我们为什么要了解这件事? 或许你是众多 “千禧一代 “和 “X世代 “中的一名投资者,这一代的人常说 “只有奇迹降临 “才有可能能退休,因为大家都在担忧不断飙升的公债,不稳定的通货膨胀率,以及加息的时候不知道会面临什么样的问题。如果你是他们中的一员,那么对你来说,加密货币就是这个时代洪流之下的救生筏。

2021-12-13