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

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

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

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

(图片来自：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无关）证明，然后记录更新的状态。

以这种方式操作的示例系统包括 Rollup 、 Coda 、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成本对比：

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

“Pantry式RAM虽然昂贵，但它提供了独特的功能，它能够将RAM的完整状态从一个证明传递到另一个证明。这使得能够在持久状态、递归可验证状态机执行和其他有用的应用程序上进行计算。不幸的是，哈希函数的高成本（在约束条件下）限制了可用于计算的Pantry式RAM操作的数量，特别是对于大型RAM。而使用批处理RSA累加器构造，就可以解决这一问题。”

代码实现：根据研究者表示，他们已实施了一个包含多精度运算、RSA累加器以及Merkle树的Rust代码库，总共涉及的代码大约有10000行。（ https://github.com/alex-ozdemir/bellman-bignat ）

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

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

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

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

约束计数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提案的身影了。

本周的精彩内容就到这里啦，下周再见～