洒脱喜一周评丨RSA累加器成SNARK系统降本利器,DEX等应用或成最大受益者

洒脱喜 发布在 链头条 技术指南 182649

导读:这周我们重点分享由斯坦福大学密码学教授Dan Boneh等人撰写的新论文《利用有效集累加器的扩展可验证计算》,探讨RSA累加器对SNARK系统的潜在改进。

而在硬核技术文章周选部分,我们还会看到零知识证明系统概述、分片区块链的安全性和可扩展性、智能合约类型差异的内容。

另外,上周以太坊2.0规范0.1版本正式发布,比特币改进提案Taproot / Schnorr也即将准备就绪,目前已进入开发者反馈阶段。

time to improve written by hand

(图片来自:tuchong.com)

以下是上周内容的精选回顾,enjoy ~

 

我们知道,区块链系统普遍面临着可扩展性问题,而链上(on-chain)工作显然是昂贵的,因此很多项目方转向了链外(off-chain)技术。

而可验证外包(Verifiable outsourcing)系统,可以将大量计算卸载到远程服务器,但要求远程服务器提供一个简洁的证明(称为SNARK)以证明其正确执行了计算。我们可以在多个区块链系统中找到这些方法的实际应用,这些区块链系统使用可验证的外包来处理链外的大量交易。

这将链上工作简化为验证一个简洁证明,它可以确认交易处理是否是正确完成的。

近期,来自斯坦福大学的密码学大牛教授Dan Boneh,联合其学生Alex Ozdemir和Riad S. Wahby发布了一篇题为《利用有效集累加器的扩展可验证计算》的论文,在这项研究工作中,他们结合现有技术和新技术,从而实现了在SNARK系统内部的RSA累加器,并使用它作为Melkle树结构的替换。

实验表明,与现有使用Merkle树来提交当前状态的方法相比,新提出的系统可以显著降低成本。

原论文链接:https://eprint.iacr.org/2019/1494.pdf

1、1 简介

可验证外包(Verifiable outsourcing)是可使弱客户端将计算外包给强大服务器的一种技术。服务器返回计算结果及表示计算正确完成的证明。而证明必须要简明扼要,这意味着它必须要简短,且核实要便宜。

可验证外包在许多情况下都是相关的,包括弱物联网设备、可穿戴设备和低功耗设备。

最近,可验证外包技术已被部署在区块链环境当中。在这些系统中,一批k交易(比如k=1000)外包给一个不受信任的服务器(称为聚合器aggregator)进行处理。聚合器(1)验证交易是否有效(例如正确签名),(2) 计算由这些交易产生的更新全局状态,并(3)生成一个简洁的证据,其证明聚合器正确执行了步骤(1)和(2)。

更新后的状态和简洁的证明随后被发送到区块链。在这种方法中,链上(昂贵的)工作被减少到仅验证(快速的,所需时间与交易数k无关)证明,然后记录更新的状态。

以这种方式操作的示例系统包括RollupCoda、Matter以及Zexe

上述过程被称为状态更新的可验证外包,更详细地说,状态是来自某个universe X的一组元素S = {x1,..., xM} 。而区块链(或低功耗设备)仅存储S的简洁摘要,例如,Merkle树的根,其叶包含S的元素。而不受信任但功能强大的聚合器,会存储完整的元素组S。

在处理上述一批交易时,聚合器更新S以生成新的集合S',然后为这个S'计算一个新的Merkle摘要,它会负责将其发送给区块链进行验证和记录。

聚合器的证明(proof)确立了它的开始状态S与当前摘要一致,正确应用交易会产生结束状态S',并且新摘要与S'一致。而这里需要的简洁证明就是SNARK。

Merkle树是累加器的一个例子,而累加器是一个密码学原语,它允许一个人提交一个集合S,然后证明一个元素x是集合S的一个成员。尽管Merkle树结构在当今的通用可验证状态更新应用中被广泛应用,但根据研究表明,当S是中等或者非常大时(比如| s |≥210)时,Merkle树并不是大批量状态更新的最佳选择。

特别是,研究者证明了用RSA累加器替换Merkle树,可显著提高证明时间和可达计算量。

以下是这一论文研究的具体贡献:

  1. 为RSA累加器定义了一个新的操作,并称之为MultiSwap,它为批验证状态更新提供精确的顺序语义;
  2. 综合现有及新的技术,有效地在SNARKs环境下实现MultiSwap(RSA累加器),其利用了操作RSA累加器的最新进展;
  3. 在两种情况下运用了这种技术,第一个是在名为Rollup的链外批处理技术下,第二个是具有持久状态的通用RAM抽象;
  4. 对提出的技术进行了实验评估,将RSA累加器实现与Merkle树在两个基准上进行了比较;
 

1、2 关于累加器(Accumulator)

密码学累加器可以将值的集合(例如vector、集合或多集合)以一个简洁摘要的形式呈现。

这个摘要是有约束力的(binding)的,这非正式地意味着,在计算上不可能对摘要所表示的集合进行含糊其辞的表达。

此外,累加器允许成员身份的简洁证明,在某些情况下,还允许非成员身份。

而Merkle树,就是一个最著名的vector累加器。回顾一下,它是一种二叉树结构,它将vector存储在子叶的标签当中,与此树的内部节点关联的标签,是将抗碰撞哈希H应用于子标签的连接结果;

更新子叶的标签是密切相关的:给定旧值的成员证明,通过将旧叶替换为新叶,然后沿路径计算哈希来计算新摘要。

Merkle树不支持简洁的非成员证明。

对于包含 2^m个值的vector,验证k个成员证明的成本是H的k·m次评估,k个子叶更新的成本是2·k·m次评估。而成员证明和更新是无法成批保存的。

而关于RSA累加器,我们可以看这篇《深入探索“区块链瘦身大法”RSA累加器》。

注意:这项研究工作的重点是SNARK型零知识证明,其也兼容Zaatar、Ligero、Bulletproofs、Sonic和Aurora,但不兼容STARK或建立在GKR和CMT上的系统,例如vRAM、Hyrax以及Libra。

1、3 MultiSwap的应用

在论文中,研究者还讨论了MultiSwap的两个应用,其中一个是针对智能合约的可验证外包:以太坊等区块链系统实现了智能合约,而这种方法的一个主要的实际限制在于,计算、存储和网络流量对于智能合约来说非常昂贵的,而其中一个解决方案就是Rollup,它是可验证计算的一个实例。

智能合约将检查交易的工作委托给不受信任的聚合器,然后检查此工作的证明是正确的。为此,用户提交交易γi发送给聚合器,而不是直接发送给智能合约。

聚合器将这些交易组合成批 {γi},然后生成一个证明π,证明验证批处理并更新全局状态的计算Ψ。最后,聚合器将相关信息提交给智能合约。对于智能合约来说,检查此证明,要比单独验证每笔交易要便宜得多。

下图显示了使用Merkle和MultiSwap的Rollup成本对比:

66

而另一个应用,则是高效持久RAM,论文中提到:

“Pantry式RAM虽然昂贵,但它提供了独特的功能,它能够将RAM的完整状态从一个证明传递到另一个证明。这使得能够在持久状态、递归可验证状态机执行和其他有用的应用程序上进行计算。不幸的是,哈希函数的高成本(在约束条件下)限制了可用于计算的Pantry式RAM操作的数量,特别是对于大型RAM。而使用批处理RSA累加器构造,就可以解决这一问题。”
代码实现:根据研究者表示,他们已实施了一个包含多精度运算、RSA累加器以及Merkle树的Rust代码库,总共涉及的代码大约有10000行。(https://github.com/alex-ozdemir/bellman-bignat

而关于MultiSwap的实现,研究者们还进行了实验评估,并将其与Merkle树构造进行了比较,下图为比较结果:

p1

约束计数v.互换数量,“Merkle m”表示为有2^m个子叶的Merkle树

p2

在10^9数量约束(constraints)条件下可验证的操作数(数字越高,代表越好)

p3

约束计数v.交易数量,“Merkle m”表示为有2^m个子叶的Merkle树

p4

约束计数v.交易数量,“Merkle m”表示为有2^m个子叶的Merkle树。色带表示根据写入负载的变化,从0%到100%

 

1、4 讨论和结论

研究者表示,他们已证明在中大型可验证状态应用中,RSA累加器要比Merkle树构造的成本更低。

有两个注意事项:首先,RSA累加器需要可信设置,而实际上,大多数SNARK构造都需要一个可信设置,所以这不是一个很大的负担。此外,部署者也可以通过使用多方计算生成RSA模块来降低信任要求。避免可信设置的一个猜想替代方案是使用虚二次阶 类群(class group of imaginary quadratic order)。

另外,探索有效的约束实现会是他们未来的工作重点。

洒脱喜简评:这一研究在理论上可有效降低使用Rollup类可验证外包技术的区块链系统成本,而且相关代码已经开源,同时论文作者Alex Ozdemir也在积极维护代码库,去中心化交易所(DEX)等应用或许会是最直接的受益者,个人浅见,在未来几年,DEX可能会迎来飞速的发展。
 

二、硬核技术文章一周精选

 

2、1 寒武纪密码学证明大爆发,数十个零知识证明系统该如何选

StarkWare公司的联合创始人兼首席科学家Eli Ben-Sasson教授在这篇文章中概述了近20个零知识证明系统,并给出了他对这些证明系统的看法,其表示:
  1. 对称CI系统可以对任何字段进行算术运算,从而提高效率;
  2. 只有对称系统才是合理的后量子安全系统;
  3. 新的不对称假设,对于金融基础设施而言,会是具有更高风险的基础;
  4. 非对称电路专用系统(Groth16)最短,它要比所有非对称通用系统和所有对称系统都要短。
其总结道:
“需要非对称密码假设的系统,它们会导致证明时间更短,但证明成本更高,它们具有较新的假设,这些假设是易受量子计算影响的,其中有很多是不透明的,而只依赖对称假设的系统,这使得它们在计算上是高效、透明,且可能是后量子安全的,而根据Lindy效应来看,它们也可能是最经得起未来考验的。”
文章链接:https://www.8btc.com/article/544357
洒脱喜简评:没有完美的零知识证明系统,有的只有权衡,就代码成熟度来看,目前SNARK可能会是最佳的选择,上面我们提到的研究也是针对SNARK进行的,而STARK则具有更好的可扩展性特性,但其还处于探索的早期阶段。

2、2 干货 | 基于委员会的分片区块链中的安全性和可扩展性

来自ConsenSys Layer 2可扩展性研究员John Adler的一篇技术文章(中文版由haiki & 阿剑翻译),文章旨在以一种简单易懂的方式,剖析分片区块链中安全性与可扩展性之间的紧张关系。

文章总结称:

“基于委员会的分片需要无状态的执行(其本身还没有被证明是可行的),加上错误性证明和数据可用性证明。然而,当考虑到交易的传播,我们发现可扩展性只有将方案的安全性移到 p2p 网络层才可以实现,这对于抵御恶意对手方是很脆弱的。我们是否能跨越这个障碍依旧是一个开放的研究问题。”
文章链接:https://www.8btc.com/media/543951
洒脱喜简评:分片方案看似能解决可扩展性三难困境,但在落地过程中会遇到一大堆难题,这需要研究者们花费大量的精力去一一克服。

2、3 技术分析 :以太坊、比特币和比特币现金上的智能合约有什么差异

文章重点介绍了ETH、BTC以及BCH这三个平台上智能合约之间的突出区别,其中以太坊是功能最广泛且是最常用的智能合约平台。而比特币通过其无状态脚本(Script)系统提供了更基本的智能合约版本,此无状态系统验证效率更高,但功能较少。比特币现金与比特币具有相同的基础,但是增加了新功能,试图在有效验证和有用的智能合约之间折衷。

文章链接:https://www.8btc.com/media/545117

洒脱喜简评:在智能合约方面,以太坊的功能最多,其步子迈得也最大,比特币则是以“求稳”的原则向效率和隐私性方向缓步前进,而BCH则是处在两者之间,三者采取了不同的路径,也可能会迎来不同的结果。
 

三、主流区块链项目技术进展

 

3、1 以太坊2.0规范0.1版本最终版发布!距离2.0年中上线迈出关键一步

以太坊2.0协调员Danny Ryan上周正式发布了以太坊2.0规范0.1的最终版本。

据悉,这一版本集中在将IETF BLS标准集成到eth2规范当中,开发者还表示会在2-3月进行一些修订工作。

链接:https://www.8btc.com/article/545177

洒脱喜简评:此前根据Justin Drake的说法,以太坊2.0第0阶段的非官方截止日期为7月30日,目前看这个预期时间点是较为靠谱的,6月-7月的可能性较大。

3、2 Pieter Wuille:增强比特币隐私性的Taproot / Schnorr提案即将准备就绪

比特币代码维护者Pieter Wuille近期在一次报告演讲中表示,增强比特币隐私性的Taproot / Schnorr提案即将准备就绪,目前已进入开发者反馈阶段,等待反馈完毕后,提案将进入实施阶段。

https://bitcoinops.org/en/newsletters/2020/01/08/

洒脱喜简评:比特币的Taproot / Schnorr提案的开发终于进入尾声阶段,由于0.20.0版本的core预计将在减半时间点(5月)前后正式发布,这些大改动的提案不太可能会被纳入,那我们只能期待在下一个版本0.21.0才能看到Taproot / Schnorr提案的身影了。
本周的精彩内容就到这里啦,下周再见~

本文链接:https://www.8btc.com/article/546107
转载请注明文章出处

评论(1)
登录 账号发表你的看法,还没有账号?立即免费 注册