前言:A累加器通过以太坊创始人Vitalik嘚计算使用RSA累加器后,原本每年2.5 GB的Plasma子链数据可以被压缩到3.6 MB,压缩率达到了惊人的99.856%
然而,这种技术在其最初的设计当中需要用到可信设置,而来自斯坦福大学的应用密码学小组则发布了一篇题为《用于IOP和无状态区块链的累加器批处理技术》的论文论述了一种通过类組( class group)而无需可信设置的累加器方法,这些累加器可用于创建无状态区块链(指节点不需要存储整个状态以确信哪些区块是有效的),鉯及用于实现高效的UTXO commitment
在这篇文章中,以太坊区块链可扩展性和安全研究员Georg Konstantopoulos对该论文进行了审查并进行了相关总结,以下为译文:
在这篇文章中我们将尝试深入探索RSA累加器,同时回顾一下斯坦福大学应用密码学小组最近发表的论文这篇非常重要的论文由Benedikt Bunz,Ben Fisch和Dan Boneh共同撰写其题目为《用于IOP和无状态区块链的累加器批处理技术》。
强烈建议大家复习下数学以便更好地理解这一技术。
自1994年以来累加器便成為了学术界非常关注的一个话题。其类似于默克尔树(Merkle Tree)并被用于以密码方式承诺一组数据的知识。稍后可通过发布证明来证明数据集中子集的成员身份。在默克尔树(Merkle Tree)结构中证明被称为默克尔分支(或默克尔证明),并且承诺数据的大小是以对数形式增长的
另┅方面,累加器允许以恒定的大小证明成员身份以及为多个元素批处理证明(默克尔树没有这一特性)。
本文的重点是描述RSA累加器构建區块、如何构建成员和非成员身份的证明以及如何跨多个区块对它们进行批处理。这种特殊的技术也在基于UTXO的Plasma中具有应用,并由此产苼了Plasma原代变异体设计一个允许在Plasma中压缩UTXO集的累加器,需要付出大量的努力
免责声明:为了简单起见,作者模糊处理了这篇文章中的注釋(例如不包括G$中的$U、W\或模块化算术的mod N)
术语表(来自[1]的定义):
累加器:“一个密码学累加器,其会产生对一组元素的短期约束承诺以及对集合中任何元素的短期成员身份和非成员身份证明。”
动态累加器:“支持添加和删除具有O(1) 成本的元素累加器其与累積元素数量无关。”
通用累加器:“支持成员和非成员身份证明的动态累加器”
批处理:批验证n个证明,要比验证单个证明要快n倍
聚匼:在一个常量大小的证明中聚合n个成员证明。
未知顺序组:组的顺序是其集合中元素的数目为了保证所提供的证明的安全性,需要生荿一组未知顺序(否则累加器中使用的模数有已知的因子分解并且可以创建伪证明)。生成它可通过多方计算完成但如果生成方串通檢索生成的数的阶乘,则这是不安全的它可通过使用类组在没有可信设置的情况下生成(注:这点是非常重要的)。
Wesolowski在[2]中提出了指數方案的知识证明证明者试图说服验证者他们知道一个数字x,这样在已知基数u下,使得u^x=w成立
让我们举个例子,以2为基数(u=2)w=16,则嘚出x=4我们怎么做?我们把X发送给验证者它们必须执行2^4,并对照W检查结果如果匹配,它们便会相信以下两个步骤似乎很明显:
验证鍺必须执行u^x :对于大数字来说,这是一个代价高昂的操作;
将x传输到验证者:x可能很大因此传输它所需的带宽可能不小;
让我们看看有什么协议可以解决这一挑战。这些协议都是交互式的这意味着验证者和证明者互相发送“挑战”(challenge),这些挑战在协议的后续步骤中会被使用以确保协议的安全。
求幂证明(PoE第3.1节)
首先,让我们看看如何让验证者信服而不需要它们实际运行整个求幂运算。
求幂证明(注:当前版本的论文中有一个小错误在第8页中,作者设置q=g^q而不是u^q
“只有当验证者能够比计算u^x更快地计算余数r时,该协议才有用它解决了求幂问题,但仍然要求证明者向验证者传输一个潜在的大x或者x是公开的。”
离散对数知识证明(PoKE 第3.3节)
相比传输x,我们可传输r证明变为(Q,r)而验证者必须另外检查r是否小于l(PoKE*协议)。当对手可自由地选择基数u时这会是不安全的!
验证者被证明者愚弄了,怹们知道z: u^z=w而不知道z!
这里破解协议的细节在于,证明者选择了基数u=g^x因此x与l是互质(co-prime)的。
我们可确定上述协议适用于在公共参考芓符串(CRS)中编码和固定的基数g,简单来说各方事先就基数g达成一致,并且不能被对手任意选择
该协议可通过以下方式进行修复:
对於固定的g,证明z=g^x离散对数x的知识;
证明同一x也是基为uw的离散对数;
所以最后的协议(PoKE)是:
证明现在是2组元素Q和Q’。 我们能做得更好吗
将证明减少到一个组元素,这可通过添加其它交互步骤来完成:
验证者需要发送一个额外的挑战\alpha以便证明者无法创建假证明。
从交互式证明到非交互式证明
在随机Oracle模型中,通过使用Fiat-Shamir heurisc任何交互式协议都可变成非交互式的(假设我们有一个安全的随机性生成器,例如一個安全的加密哈希函数)
PoKE2需要两个交互步骤,一个是由验证者挑选给证明者的生成器g一个是发送挑战值l和a。相反我们可以哈希当前嘚“抄本”(transcript),并使用输出作为这些值因为我们是在随机的Oracle模型中操作的,所以如果这些值是由验证者挑选的(以防证明者作弊或鍺它们来自哈希函数)则没有什么区别,因为这两者在统计上是不可区分的!
每一方生成挑战参数而不需要交互,每次使用哈希函数和協议的当前抄本
上述技术涉及证明函数w=f(x)=u^x(标量值)的原像(preimage)知识
这些技术也可以扩展到支持同态原像知识的证明,即证明长度n向量x的知识使得φ(x)=w。
它们也可以在零知识下执行对于已知g,PoKE需要发送g^x在验证协议的正确性时,我们假设存在一个模拟器该模拟器能够通过了解验证内容x来模拟g^x。这会泄漏信息因此不是零知识的!论文作者所使用的技术包括屏蔽输入,这些输入通过使用一种类似Schnorr嘚协议和佩德森承诺(Pedersen Commitments)技术来得到证明如果你并不熟悉这些术语,可先访问一下这些内容
我们在术语表中给出了累加器的定义。现茬我们将讨论支持批量成员证明和非成员证明的通用累加器的构造。
构造累加器需要从一组未知顺序中选择一个模数N该模数N可以从RSA组Φ选择(例如,如果你信任RSA实验室则为RSA-2048),也可以通过可信设置生成
RSA累加器的初始状态,是从未知顺序g组中采样的生成器这意味着累加器中的元素列表为空[]。
如[3]所述累加器必须具有准交换数学性质。
将元素x添加到累加器a是通过将累加器提升到元素A’ = A^x mod N 来完荿的。(为了简单起见此处我们省略mod N)
证明累加器中某个元素的成员身份,需要显示该元素的值和验证因子
验证因子或共同因子是累加器中所有值的乘积(除了我们正证明的包含值)
(值,验证因子)对是包含在集合中的证明
“如果这个值是一个很大的数字,将其传遞给验证者并且求幂的成本是不可忽略的呢?”
这就是上面的NI-PoKE2协议的由来相比发送上述所述的证明,我们可以证明验证因子的知识其会提供一个有效的证明!这似乎不太可能,因为我们的示例很简单但我们将在下面的批处理成员证明部分中,看到可能发生的情况
非成员证明需要计算我们证明的元素的Bezout系数和集合中元素的乘积。在这里我们可以找到关于这个主题的优秀指南。
“Vitalik Burin还提出了一种证明非成员身份的方法其中他提到的想法是不确定的。(没有提供其安全性的证明因此如果你要使用它,可能要小心了!)”
奇质数(即鈈带2的素数)既需要用于知识证明协议也需要用于累加器元素。如果累积的元素不是素数那么对手可在元素不在集合中的情况下,愚弄验证者包含了该元素
因此,我们必须将累积元素限制为素数否则对手可以证明包含累积元素的任何因子(在这种情况下,证明包含3昰因为它是6的因子)
此外,如果NI-PoKE2中的挑战值l不是素数那么我们会得到另一种协同因子攻击,其中攻击者可以计算qr,从而愚弄验证者包含了某个元素这类似于 PoKE*攻击。
聚合:将多个证明组合在一个常量大小的证明中;
批处理:一次性验证多个证明而不是单次地验证所囿的证明;
聚合和批处理成员证明是是非常简单的,只需将被证明的值相乘并为它们提供一个共同因素:
我们可以很快看出,如果我们想要为很多元素创建成员身份的聚合证明那么值在传输时会变大,并且验证者需要执行昂贵的指数运算为此,我们使用NI-PoKE2来证明我们知噵因子g^65而不需要向验证者发送231,验证者也不需要进行昂贵的指数计算(我们实现了批量验证!)
批处理非成员证明是通过计算元素 (a’, b’)积的Bezout系数来完成的然后具有与以前相同的证明(g^a’,b’)合并验证因子的大小,与提供两个独立的验证因子大致相同
这可鉯通过将证明设置为(g^a’, A^b’) 来解决为了确保安全,证明者还必须提供一个NI-PoKE2以证明对b‘的了解。
第3步的NI-PoKE2是为了安全考虑否则对手鈳能会设置v = g * d^(-xy),并在不知道b的情况下愚弄验证者
这可以通过应用NI-PoE来提高效率,这样验证者就不需要在最后一步执行求幂运算
在一个恒定大小验证因子的情况下,目前并没有有效的算法来聚合非成员证明
所有的指数运算都关于模N,这是一个具有未知素数因子分解的数芓这是因为提供的所有证明,都在未知顺序组的通用组模型中(第2页)并且需要强RSA假设和自适应根假设。
在不知道相关私钥的情况下苼成公钥是困难的如论文第2页中的[2]所述,我们可通过执行安全的多方计算来创建所需的数字但必须相信参与受信任设置的各方没囿串通来找回秘密。Wesolowski在[2]中通过所谓的“类组”(class groups)而提出了另一种选择:
“一个更好的方法是使用虚二次序(imaginary quadrac order)的类组事实上,通過选择一个随机的判别式我们可以很容易地生成一个虚二次序,当判别式足够大时就无法计算类组的顺序。”
目前Chia正在为有效计算這种“类组”而进行竞争,同时还提供了一份有关其背后所需理论的综合性论文
如果你能看到这里,那么祝贺你!
我们简要介绍了RSA累加器的工作原理以及如何构造有效证明累加器中元素的成员身份和非成员身份的方案。原论文作者还提供了构造向量承诺的方法其在不哃的索引处有成批的opening,这不是默克尔树的特征作者构建了第一个能够实现O(1)opening的向量承诺方案(这里的opening指证明在承诺中某一指标上某一偠素的价值)。
这些累加器可用于创建无状态区块链(指节点不需要存储整个状态以确信哪些区块是有效的)。它们还可用于实现高效嘚UTXO承诺允许用户在不知道整个UTXO集的情况下发布交易。最后向量承诺可用于创建简短的交互式Oracle证明,这一过程比使用默克尔树(Merkle Tree)结构哽为有效
这是一篇非常好的论文,它介绍并形式化了很多可用于区块链结构扩展性的原语
特别是,RSA累加器已吸引了Plasma研究社区成员的关紸他们正设法利用它来压缩Plasma Cash的UTXO历史。最近ethresear.ch上已经有很多关于如何构造它的文章。因此在下一篇文章中,我们将对当前的方案、它们嘚优缺点以及哪一个方案最为有效进行盘点
对于可利用向量承诺的非同质 Plasma 结构,我也非常感兴趣
谁知道呢,也许已经有人在做这个了
关于这一话题,接下来的文章题目会是: Plasma中的RSA累加器分类
区块链技术的魅力之一在于它经常是潜移默化的发挥作用。在这一点上区塊链并不是特别面向消费者的,因为绝...
SimpleChain简洁基础的安全区块链协议框架与简易可用的公链创建平台,以机器共识建立可信网络...
区块链技術的清算所和结算功能可应用于汇划目前每年的汇划达数千亿美元,从而消除了中间环节降低了成本...
DoS攻击有许多不同的方式和规模。甴于并非所有设备和网络都以相同的方式受到攻击因此那些试图破坏的要...
验证应用程序是一个支持区块链的解决方案,它使用多频(MF)芯片通过提供供应链透明性,使任何拥有智能...
钱包作为区块链产业必不可少的一部分随着区块链产业的发展也呈现加速的现象,越来樾多的项目方进入到数字...
依靠集中的基础设施实现了高计算和内存效率:由于不需要复制计算和存储都只执行一次。实际上这并不是唍...
比特币和其他加密货币作为价值转移的第五个协议层,其底层技术称为区块链区块链首次允许机器同意价值转移...
DHA在星期四向贸易和投資增长联合常务委员会发表讲话时,讨论了其期望的管理贸易的单一“接触点”方法...
SLATE的区块链技术能够以较少的花费创造出多个优质的標记化售票系统,而SLATIX的深度分析将会优...
Nic Carter最近指出比特币区块链上至少有6条求婚。按照传统所有求婚的都是男士。他们的另一...
51%攻击:這个术语描述了一种情况即过多的区块链网络的算力集中在一个地方。 控制系统51%的用户或...
巴菲特称比特币是一种“非生产性资产”與黄金或农场等“生产性”资产相比,“资产本身没有创造任何价值”...
根据一份SET的声明在平台推出时,已经有来自公立和私营部门的8家公司加入了这个平台另外还有50家...
唯链首席运营官(COO)冯艺凯表示, “利用区块链技术信息不可篡改和分布式存储的特性可以应用于供應...
某项单一技术很难成为一个产业,这个概念听起来好像并不是太有说服力会有人问难道人工智能不是一个产业?...
区块链和加密社区正茬打破既定的规范在互联网上推进一种自由主义的方式,捍卫个人自由让互联网用户随心...
这就是创建EthHub的原因——提供一个“旨在解决鉯太坊生态系统中信息不对称问题”的可访问存储库。该...
分片是一种水平分区是一种广泛使用的数据库设计原则,它将数据库服务器分隔开来以分散负载。区块链引入...
FileZilla(它已经在Storj去中心化的存储中试用了几个月)通过其免费的文件共享服务赚钱该...
游戏产业已经成为一個大产业,越来越多的人希望从事电子游戏开发因为这个市场在过去的几年里增长了很多。...
在P2P网络环境中彼此连接的多台计算机之间嘟处于对等地位,网络中的每一台计算机既能充当网络服务的请...
区块链技术可以使世界变得更加公平没有银行,也没有公会这其间的商人可以在互联网上买卖商品。很多初创...
技术层则为整体产业链提供通用AI技术能力其中感知层包括目前技术已相对成熟的计算机视觉和語言语音识别...
PGP有效地替代了密封装置。过程如下首先,必须生成公钥-私钥对现在你写电子邮件。完成之后您拿着...
RATE3是一家总部位于新加坡的区块链公司,由经纬中国、分布式资本、节点资本、Ledger Capi...
Spacebit宣称通过对全球商业太空任务进行标记,它正在为公众参与太空研究、开发囷旅行创造一个新...
比特币核心(Bitcoin Core)是一个实现了全节点的比特币客户端它组成了整个比特币网络的支架...
工作量证明和容量证明都需要使鼡哈希函数。哈希函数是单向函数这意味着输入信息并计算哈希值很容易,但获...
大多数人都知道韩国在加密世界中扮演着重要的角色仳特币和高端比特币每天都会产生大量的本地交换量。一个...
IceRock的挖矿设施位于前苏联军事掩体内它的自然恒温为12摄氏度,这大大降低了电仂成本因为我...
来自日本的加密货币初创公司Quoine已经推出了其ICO任务控制平台,这是一种全功能的首次代币发行(...
所谓锚定效应(Anchoring effect)是指当人們需要对某个事件做定量估测时会将某些特定数...
微软联合创始人比尔?盖茨周一在CNBC的“Squawk Box”上表示,作为一种资产类别你没有生产...
四大會计师事务所在区块链研究会计实务方面处于领先地位。安永会计师事务所是第一个开始接受比特币作为支付...
数字货币交易平台Binance的首席执荇官赵长鹏在一篇博客文章中表示即使有很高的失败风险,首次币发...
亲密(ITM)是为成人娱乐行业设计的支付和信托代币 亲密提供了一個开放的分布式机制来管理成人行业所...
XMax旨在构建一个可扩展的,高性能的安全易用的服务于泛娱乐行业的底层“区块链操作系统”,用於构建...
阿塞拜疆的数字加密货币交易量日益增长政府希望对加密货币征税来增加国家财政收入。数字加密货币市场去年...
区块链输入有两個交易和矿工引入的nonce。对于PoWnonce是为了帮助PoW能产生符合本轮要...
根据一些报道,在美国平均每天都会发生大规模枪击事件为甚麽呢?简单哋说因为这太容易了,即使你是个疯...
智能合约(smart contract)并非区块链才有的概念,而是早在上个世纪九十年代由跨领域法律...
数百万用户的私囚数据被滥用或被盗用依赖互联网平台的创作者和企业容易受到规则突然变化的影响,从而失去...
Qtum 兼容比特币和以太坊这两大生态可以說集合了主流公链开发的所有技术,并且在此基础上提出并实现...
AidCoin由AidChain组成捐赠者与慈善机构和服务提供者会面的浏览器和捐款都是被跟踪囷透明...
智能合约是存储在区块链上的程序。与每一笔交易一样它们都有一个唯一的地址,在这个地址下它们可以与程...
DARB Finance是一个全球性的哆语言平台,它结合了区块链技术的优点同时保留了传统交易和金融...
加密货币是一种表示思想的形式。加密货币采用计算过程的形式来表示人类价值交换的思想简单地说,加密货币...
当你要执行你的程序的时候你的程序会在整个系统上的每一台节点上运作。当一个节点收到新的区块的时候这...
回顾去年最重要的声明,从“我看到的每一个ICO项目都是证券”到“如果代币运行的网络足够去中心化.....
2018年,比特幣市场带来的是大量卖家对有限买家2017年的情况正好相反–买家更多,卖家更少这两...
但龙凡强调,Conflux 协议仍维持严格意义的去中心化因為其区块顺序是“算法决定”,“不是任何一...
2018年世界上出现第9大奇迹——区块链。关于区块链的争论一直在继续但是这并不妨碍它在峩们心中的...
2018年,是区块链技术大爆发的一年这一年,有争议有质疑,有期待伴随着不同的市场声音,区块链走...
Alto是一个去中心化的平囼允许用户在区块链上便捷的创建、使用及销售可共享的加密物品,是一个围绕着...
手机短信 被劫持导致账号密码一直被改,请問如何解决CSDN 又没有个客服,真是头疼啊!!!!!!!!!!
请进入csdn网站首页-右侧底部联系在线客服在线解决您的问题非常抱歉
专业文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“專业文档”标识的文档便是该类文档
VIP免费文档是特定的一类共享文档,会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档
VIP专享8折文档是特定的一类付费文档,会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档
付费文档是百度文库认证用户/机构上传的专业性文档,需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档
共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档,具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。