区块链数据存储的“密码学黑科技”

时隔许久，这一次，我将从CRYPTO 2019大会上一篇有趣的论文开始，简单介绍一下密码学中累加器对于区块链扩容的价值和意义”

今年作为发起人代表参加美密大会，很高兴看到区块链相关的研究工作占据了相当大的份额：

除了Blockchain workshop和单独的“SNARKs and Blockchains” Session外参考文献中用到比特币白皮书，“零知识”、“Proofs of storage”、“Memory Hard functions and Privacy Amplification”等其他session也有很多区块链相关的研究。作品发表。

在 CRYPTO 2019 收录的所有论文中，我认为最有趣的一篇是“Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains”[1]，作者是斯坦福大学的 Dan Boneh、Benedikt Bünz 和 Ben Fisch。

接下来，我将从本文开始，探讨一下Accumulator的前世今生，以及这项技术对于区块链扩容的价值和意义。

背景介绍

中本聪在设计比特币时，通过区块大小和区块生成时间，将比特币的吞吐量限制在一个很低的水平（1MB/10min）。 一个重要的考虑因素是存储空间的限制。

即便如此，比特币自创世块以来所有交易和区块的区块链历史已经超过200GB，并且还在以每月4-5GB的速度增长； 比特币网络的未花费交易集合（UTXO）的大小也接近1亿，占用超过6GB的空间。

作为区块链2.0的代表，支持智能合约的以太坊的“世界状态”更大。

以太坊现在有超过 8000 万个地址，仅仅存储这些地址的基本信息（每个地址至少需要 100B 来保存账户地址、余额、nonce、状态根等）就已经需要将近 10GB 的内存。 如果算上智能合约的代码和内部状态，占用的空间会多出十倍以上。

以上数据仅在用户数量较少且共识吞吐量小于20Kbps时（基于简单的转账交易，最大不超过30TPS - Conflux在测试网络条件下可以达到9.38Mbps的共识吞吐量20 Mbps[2 ]) 的情况下。

如果要将区块链的吞吐量提升到上千TPS的水平（相当于Visa），存储需要承受高两个数量级的压力； 如果要支持上亿用户大规模使用智能合约，地址数量恐怕要超过十亿，对应的状态存储至少是现在的几十倍.

因此，区块链历史和状态的存储问题是继共识算法之后区块链扩展道路上的又一绊脚石。

在传统的分布式计算和分布式数据库场景中，可以通过磁盘阵列（RAID）和云存储技术以低成本实现高可靠性的大规模数据存储。

但是，这些设计的前提是每个提供服务的节点都是可信的，只有没有拜占庭错误的宕机风险参考文献中用到比特币白皮书，即没有恶意攻击。

为了在拜占庭错误的前提下实现高可靠性，以比特币为代表的区块链采用了各个节点（本文中的节点是指参与共识全节点的“全节点”——“轻节点不是节点”）存储完整的数据解决方案（类似于 RAID 1）。

因此，区块链网络中的所有交易历史，实际上都会保存几千份甚至几万份，以高成本实现高可靠性。

此外，当新节点加入时，需要几天的时间来下载并验证自创世块以来的所有历史数据，这无形中提高了新节点加入的门槛，降低了区块链系统的去中心化程度。

学术界和工业界早就注意到区块链上存储成本高、扩容难等问题，并提出了许多降低区块链上数据存储成本的建议。

其中，广泛流传着各种分片、侧链、多链甚至跨链方案。

这些方案的基本原理是将区块链上的地址、交易和状态按照一定的方式进行分组。 每组节点只负责处理和验证整个网络中的一部分交易，因此它们只需要存储与自己分组对应的部分。 数据。

共识分片（或分组）方案的优点是简单易懂，技术实现起来也比较简单。 而这类方案的缺点也很明显：无论是哪种分片或分组，都不可避免地会影响区块链系统的安全性，因为每一笔交易都不再被所有节点验证和存储——除非每个参与者区块链共识同时运行多个节点，保证每一组至少有一个节点。

但是，如果需要共识的参与者有能力和资源同时维护多个节点，势必会显着降低整个区块链系统的去中心化程度。

无状态区块链和会员证明

另一个降低存储成本的解决方案是使用密码学实现的“无状态区块链”。

以UTXO模型为例，节点验证一笔交易是否合法其实非常简单。 只需要交易发起方证明交易的所有输入都在当前UTXO集合中，交易金额和签名合法即可。

验证一笔交易的金额和签名是否合法非常容易，所以关键在于交易发起者向验证者提供“输入是当前UTXO集合中的一个元素”的成员证明（membership proof）。

如果验证者（节点）持有一个当前的UTXO集合，那么交易的发起者只需要提供币的来源作为交易输入（通常是收到这笔钱的交易的哈希值），验证者就可以进行校验用于其自己的 UTXO 集合中的条目。 在这里，验证者维护一组 UTXO 就足够了，但不是必需的。

例如，验证者只保存当前UTXO集合的默克尔树根节点（Merkle Root，即存储在默克尔树根节点的哈希值）。 为了证明交易的合法性，交易的发起方可以对输入自带一个标准的默克尔树成员证明（Merkle Proof）。

证明包括从成员叶节点到树根的整个路径中涉及的所有中间节点的哈希值。

当然，Merkle Root 本身并不足以替代 UTXO。

因为Merkle Proof的长度比较长，至少是原始输入长度的三十、四十倍（取决于Merkle Tree的高度和宽度），这意味着同样的共识吞吐量会大大降低TPS；

其次，更新UTXO集需要重新计算Merkle Root，根据交易输出（接收方地址）插入新数据往往需要几乎整个Merkle Tree和UXTO集数据。

因此，为了更新当前UTXO对应的Merkle Root，共识节点要么在本地保存大量数据，要么在使用时向其他节点索取所需数据。

这时候就轮到我们这次要说的密码累加器（Cryptographic Accumulator）了。

基于 RSA 的密码累加器

密码累加器最早由 Josh Benaloh 和 Michael de Mare 提出。 原论文《One-way accumulators: A decentralized alternative to digital sinatures (extended abstract)》[3]发表于1993年的欧洲密码学会议（EUROCRYPT）。 这篇论文最初是为了解决区块链上的数据可访问性问题而写的。

正确的！ 你没看错！ 1993 年的论文解决了一个区块链问题！

正在解决的问题实际上源自1991年的一篇论文。 那篇论文首先提出了一个字面意义上的“区块链”[4]——没有共识算法、工作量证明等，只是为文件提供时间戳功能。

十多年后，区块链被中本聪同志作为比特币的基础[5]。

顺便说一句，工作量证明的想法实际上是在 1990 年代初提出来打击垃圾邮件的，尽管中本聪在比特币白皮书中为此引用了 2002 年的一篇论文。

改进的累加器方案

Dan Boneh、Benedikt Bünz 和 Ben Fisch 的工作（以下简称 BBF 方案）今年发表在 CRYPTO 上，在非成员证明和验证速度上都取得了显着的改进。

使用 BBF 累加器方案，可以实现无状态的区块链。

仍然以UTXO模型的区块链为例，每次节点验证交易是否合法时，UTXO聚合器可以更新：首先使用交易本身附带的“交易输入属于当前UTXO集合的成员证书” 》从当前UTXO聚合器中删除对应的输入，然后根据交易的输出添加对应的条目，以获得新的UTXO集合的聚合器。

在整个上述过程中，节点不需要使用任何其他交易信息（Merkle Tree 做不到），因此它们只需要维护一个当前 UTXO 的聚合器（摘要），而无需在 UTXO 中存储任何元素。 真的是鹅妹啊！

此外，当处理整个区块中的许多交易时，不需要单独更新每个交易，而是可以在处理完所有交易后更新 UTXO 聚合器一次。

除了大大提高效率之外，该属性只需稍作修改即可实现类似于 Mimblewimble 的匿名性。 真的是鹅妹啊！

看到这里，是不是迫不及待想要用“新欢”Accumulator 取代“旧爱”Merkle Tree？

等一下，上面只说了蓄能器好的一面，还是等看完下一段冷静下来再做决定。

密码累加器的局限性

上面提到的基于RSA的累加器具有结构简单、性能优良（至少看起来是这样）的优点，但是在实际实现中还是有很多必须注意的地方。

总之，选择过程相当复杂，难以理解，一不小心就会出错。 技术细节请参考相关论文。

第三，累加器工程实现复杂困难，远不如Merkle Tree简单可靠。

Merkle Tree 的结构足够简单，向训练有素的程序员解释它只需不到十分钟。 即使是更复杂的 Merkle Patricia Trie 也只需要不到半天的时间，编写一个正确实现的功能也只需要不到一天的时间。

而如果想给密码学背景不深的程序员讲解累加器的原理和参数选择的逻辑，然后再讲解BBF方案中使用的简短的非交互证明系统，最后实现一个累加器，恐怕半年的时间不够——而且编写的代码几乎肯定是有问题的。

最后，RSA 假说是一个可以被量子计算机攻击的经典例子。

近年来，量子计算的发展如火如荼，取得了诸多里程碑式的成就：谷歌上个月刚刚宣布实现“量子至上”，IBM也在朝着“量子优势”迈进，还有很多其他微软和中国等巨头。 BATH 正在开发量子计算。

因此，基于RSA假说实现的累加器的寿命从诞生的那一刻起就进入了倒计时状态——根据量子摩尔定律估计，2048位的RSA算法可以使用50年以上。

那么除了基于RSA的累加器，还有没有其他方式实现累加器呢？

事实上，有。 今年早些时候，麻省理工学院数字货币研究所的 Thaddeus Dryja 发表了一篇论文，题为《Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set》[6]，即使用一组不同大小的 Merkle Trees 来实现累加器的功能可以用来扩展 UTXO 模型的区块链存储容量。

Utreexo实现的累加器功能和性能比BBF方案略差。 主要优点是结构简单易懂，实现起来也很方便。

然而，即使有一个方便的累加器也不足以直接用于无状态区块链。

累加器的一个重要特征是它的证明必须用累加器的当前状态更新，这类似于默克尔树——默克尔证明只对固定的默克尔根有效，如果默克尔根更新，则证明必须重做。

也就是说，即使有了累加器，UTXO 的成员资格证明或账户状态对应数据也必须随着区块链的增长不断更新。 仅由用户自己离线存储会员证明是不可行的。

蓄能器与区块链的未来

虽然现有的密码累加器方案并不完善，也没有现成的工业级代码可供我们直接使用，但是BBF方案仍然向我们展示了累加器的巨大潜力和光明前景。

至少在采用累加器之后，希望共识节点之间在存储上实现分工协作，每个节点只需要存储一部分数据。

对于涉及到节点本地没有存储的数据的交易，可以选择不打包。 其他节点打包后，只需要验证相应的证明，更新累加器的状态即可。 这足以在很大程度上缓解节点的存储压力。

对于以状态更新证明的问题，根据现有的BBF方案，可以向存储所有交易数据的第三方服务商（类似以太坊的Archive Node）提供证明服务，并收取费用。

至于是否可以通过更好的结构来降低生成和更新证明的成本，使得没有节点需要存储完整的数据（尤其是随时间线性增长的交易历史）？

这个问题留给密码学家继续研究。 除了帮助区块链扩展存储容量，密码累加器还可以用在“交互式预言机证明”（IOP，Interactive Oracle Proofs）系统中，帮助提高证明效率。

典型的IOP系统如零知识证明的zk-STARK和Ligero方案在使用BBF方案的累加器后可以显着缩短证明长度和验证时间。

众所周知，目前的零知识证明系统没有被大规模使用的主要原因之一就是效率太低。 密码累加器有望推动零知识证明更接近实用。

相信在不久的将来，来自 1990 年代的密码累加器技术将继续发展，工业级的开源代码实现将会出现，最终成为我们工具箱中的强大新武器。

事实上，在密码学领域，还有很多被埋没多年的累加器等“黑科技”。 为了让这些“黑科技”不再被埋没，有梦想的少年们来搞密码学~

参考：

[1] 丹·博内、本尼迪克特·邦兹、本·菲施。 用于 IOP 和无状态区块链的累加器批处理技术。 加密货币 2019。

[2] 李辰星，李培伦，周东，徐伟，龙凡，姚明。 Conflux：具有接近最佳吞吐量延迟的去中心化区块链。 在提交。

[3] 乔什·贝纳洛、迈克尔·德马雷。 单向累加器：数字签名的一种去中心化替代方案（扩展摘要）。 欧洲密码 1993。

[4] S.哈伯，WS 斯托内塔。 如何为数字文档加时间戳。 Journal of Cryptology，第 3 卷，第 2 期，第 99-111 页，1991 年。

[5] 中本聪。 比特币：一种点对点的电子现金系统。 2008.

[6] 撒迪厄斯·德里亚。 Utreexo：一种针对比特币 UTXO 集优化的基于哈希的动态累加器。