拖更很久，这次从 CRYPTO 2019 会议上一篇很有意思的论文出发，简单地介绍一下密码学中的累加器（Accumulator）对于区块链扩容的价值和意义"
今年以赞助商代表的身份参加美密会，很欣喜地看到与区块链相关的研究工作已经占据了相当的份额：
除了一个 Blockchain workshop 和一个单独的 “SNARKs and Blockchains” Session 以外，在其他的 “Zero knowledge”“Proofs of storage”“Memory Hard functions and Privacy Amplification” 等几个 Session 也有不少与区块链相关的研究工作发表。
在 CRYPTO 2019 收录的所有论文中，我认为最有趣的一个是有斯坦福大学的 Dan Boneh， Benedikt Bünz 和 Ben Fisch 合作的《Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains》[1]。
接下来我就从这篇文章出发讨论一下 Accumulator 的前世今生以及该技术对于区块链扩容的价值和意义。
背景介绍
中本聪在设计比特币的时候，通过区块大小和出块时间将比特币的吞吐量限制在一个非常低的水平（1MB/10min），一个重要的考虑就是存储空间的限制。
即便如此，比特币从创始块以来所有交易和区块构成的区块链历史已经超过 200GB，且还在以每个月 4～5GB 的速度增长；比特币网络的未花费交易集合（UTXO）的大小也已接近一亿，占用空间超过 6GB。
作为区块链 2.0 的代表，支持智能合约的以太坊的“世界状态”则更为巨大。
以太坊现在有超过八千万个地址，仅仅是存储这些地址的基本信息（每个地址至少要约 100B 用来保存账户地址、余额、nonce、状态根（state root）等）就已经需要近 10GB 的空间了，算上智能合约的代码和内部状态则占用的空间还要再多十倍以上。
而上述数据仅仅是在用户数量不多、共识吞吐量不到 20Kbps**（以简单转账交易计算，最多不超过 30 TPS —— Conflux 在 20 Mbps 的测试网络条件下可以实现 9.38Mbps 的共识吞吐量 [2]）**的情况下得出的。
如果想要把区块链的吞吐量提升到数千 TPS （与 Visa 相当）的水平，则存储方面需要承受高两个数量级的压力；如果要支持上亿用户大规模使用智能合约，则地址数量恐怕要超过十亿，相应的状态存储也至少要比现在多几十倍。
因此，区块链历史和状态的存储问题是继共识算法以后又一个挡在区块链扩容之路上的拦路虎。
在传统的分布式计算和分布式数据库场景中，可以通过磁盘阵列（RAID）和云存储技术以较低成本实现高可靠性的大规模数据存储。
但是这些设计的前提是提供服务的各个节点都是可信的，只存在宕机的风险而不会出现拜占庭错误，即没有恶意的攻击。
以比特币为代表的区块链为了在有拜占庭错误的前提下实现高可靠性，采用了每个节点（本文中节点均指参与共识的“全节点” full node——“Light nodes aren’t nodes”）存储一份完整数据的方案（类似 RAID 1）。
因此，区块链网络中的所有交易历史实际上会被存储几千甚至上万份副本，获得极高可靠性的同时也付出了不菲的成本。
此外，新节点加入的时候必须耗费数天时间下载并验证自创始块以来所有的历史数据，变相抬高了新节点加入的门槛，降低了区块链系统的去中心性。
学术界和工业界早已注意到区块链上存储成本过高、扩容困难的问题，并提出了很多降低链上数据存储成本的提案。
其中流传比较广泛的是各种各样的分片（Sharding）、侧链、多链、甚至跨链方案。
这些方案的基本原理都是把区块链上的地址、交易和状态按照一定的方式分组，每组节点只负责处理和验证全网中的一部分交易，因而也只需要存储自己分组对应的那部分数据即可。
**共识分片（或者说分组）方案的优点是简单易懂，实现起来技术相对比较简单。**而这类方案的缺点也很明显：无论何种形式的分片或是分组，都必然会影响区块链系统的安全性，因为不再是每笔交易都被所有节点验证和存储了——除非区块链共识的每个参与者都同时运行多个节点，且保证在每个分组内都有至少一个节点。
不过如果要求共识的参与者们都有能力和资源同时维护很多节点，必然会显著降低整个区块链系统的去中心化程度。
无状态区块链与成员性证明
另一种降低存储成本的方案就是采用密码学技术实现的“无状态区块链”（Stateless Blockchain）。
以 UTXO 模型为例，节点验证一笔交易是否合法其实很简单，只需要交易的发起者证明作为交易的所有输入都在当前的 UTXO 集合中，且交易金额和签名都合法即可。
一笔交易的金额和签名是否合法非常容易检查，所以关键在于交易发起者向验证者提供“该输入是当前 UTXO 集合中的元素”的成员性证明（membership proof）。
如果验证者（节点）持有一份当前的 UTXO 集合，那么交易的发起者只需提供作为交易输入的币的来源（通常为收到这笔钱的交易的哈希值），验证者即可在自己的 UTXO 集合中检查是否有相应条目。这里验证者维护一份 UTXO 集合是充分但不必要的。
例如验证者只保存了当前的 UTXO 集合的默克尔树根节点（Merkle Root，既 Merkle Tree 的根节点处存储的哈希值），则交易的发起者为了证明交易的合法性，可以为每个输入附带一个标准的默克尔树的成员性证明（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]。
顺便提一下，工作量证明的想法其实也是上个世纪90年代初就被提出用于抵抗垃圾邮件的，尽管中本聪在比特币的白皮书里为此引用的是一篇 2002 年的论文。
改进的累加器方案
今年发表在 CRYPTO 上的 Dan Boneh，Benedikt Bünz 和 Ben Fisch 的工作（下称 BBF 方案）在非成员性证明和验证速度这两点都做出了重大改进。
使用 BBF 累加器方案，就可以实现一条无状态的区块链。
仍以 UTXO 模型的区块链为例，每次节点验证一笔交易合法后即可更新 UTXO 聚合器：先利用交易本身附带“交易输入属于当前 UTXO 集合”的成员性证明从当前 UTXO 聚合器中删除相应的输入，然后再按照交易的输出将相应条目加入后得到新 UTXO 集合的聚合器。
在上述整个过程中，节点都不需要用到任何其它交易的信息（Merkle Tree 可做不到这点），因此只需维护一个当前 UTXO 的聚合器（摘要）而不用存 UTXO 中的任何一个元素。实在是鹅妹子嘤²！
更进一步的，处理整个区块中的很多笔交易时，不需要对每笔交易单独进行一次更新，而是可以处理完所有交易以后一次性地更新 UTXO 聚合器。
这个性质除了可以大大提高效率外，稍加改动即可实现类似于 Mimblewimble 的匿名性。真的是太鹅妹子嘤了！
看到这里是不是已经迫不及待地想用 Accumulator 这个“新欢”换掉“旧爱” Merkle Tree 了？
且慢，上面还只说了累加器好的一面，还是等看完接下来这段以后冷静一下再做决定。
密码学累加器的局限
上面讲的基于 RSA 的累加器具有结构简单、性能优异（至少看上去是）的优点，但是实际实现起来还有很多必须注意的地方。
总之就是这个选取的过程相当复杂难懂，稍不小心就会出错。技术细节还请参考相关论文。
再次，在工程实现上累加器复杂且难度很高，远不如 Merkle Tree 简单可靠。
Merkle Tree 的结构足够简单，用不了十分钟就能给一个训练有素的程序员讲明白，即使是比较复杂的 Merkle Patricia Trie 也花不了半天功夫，再花个不到一天时间就足够写一个功能正确的实现了。
而如果要向没有深厚的密码学背景知识的程序员讲明白累加器的原理和参数选择的逻辑，再讲明白 BBF 方案里用到的简短非交互式证明系统，最终实现出一个累加器，恐怕半年时间都不够用——而且写出来的代码几乎可以肯定是有 bug 的。
最后， RSA 假设是一个经典的可被量子计算机攻击的例子。
近年来量子计算的发展如火如荼，取得了很多里程碑式的进展：Google 刚刚于上个月宣布实现了“量子霸权”，IBM 也在向着“量子优势”发力，其它还有很多巨头比如微软和国内的 BATH 都在发展量子计算。
因此，基于 RSA 假设实现的累加器从诞生的那一刻起生命就已经进入了倒计时的状态——按照量子摩尔定律估计，2048位的 RSA 算法大约也就还能再坚持五十多年了。
那么除了基于 RSA 的累加器以外，还有没有其它方式实现的累加器呢？
其实也是有的。今年早些时候 MIT 数字货币研究所的 Thaddeus Dryja 发表了一篇题为《Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set》的论文 [6]，就是用一组大小不同的 Merkle Tree 实现累加器的功能，可用于 UTXO 模型的区块链在存储方面扩容。
Utreexo 实现的累加器功能和性能比 BBF 方案略差，主要优势在于构造简单易懂，实现起来也很方便。
然而，即便是有了方便的累加器，直接用来做无状态区块链也还是不够的。
累加器的一个重要特性是其证明必须要随着当前的累加器状态而更新，这点与 Merkle Tree 类似——Merkle Proof 只对固定的 Merkle Root 有效，如果 Merkle Root 有更新的话证明必须重新做。
也就是说，即便用上累加器，UTXO 或者账户状态对应数据的成员性证明也必须随着区块链的增长而不断更新。只由用户自己离线存储一个成员性证明是不行的。
累加器与区块链的未来
尽管现有的密码学累加器方案还不完美，也没有现成的工业级的代码供我们直接使用，但是 BBF 方案依然向我们展现了累加器的巨大潜力和光明的前景。
至少采用累加器以后，有希望在共识节点之间实现存储上的分工合作，每个节点只需存储一部分数据。
对于涉及节点本地没有存储的数据的交易可以选择不打包，等别的节点打包以后只需验证相应的证明并更新累加器状态即可。这样已经足以在很大程度上缓解节点的存储压力了。
对于证明随状态更新的问题，按照现有的 BBF 方案可以先让存储了所有交易数据的第三方服务商（类似于以太坊的 Archive Node）收费提供代办证明的服务。
至于是否可以通过更好的构造降低生成和更新证明的成本，使得任何节点都不需要存储完整的数据（特别是随时间线性增长的交易历史）呢？
这一问题还要留给密码学家们继续研究。密码学累加器除了帮助区块链在存储方面扩容以外，还可以用在“交互式神谕证明”（IOP， Interactive Oracle Proofs）系统里，帮助提高证明的效率。
例如零知识证明的 zk-STARK 和 Ligero 方案等典型的 IOP 系统，使用 BBF 方案的累加器后均可以显著地缩短证明长度和验证时间。
众所周知，目前的零知识证明系统没有被大规模使用的一个主要原因就是效率太低。密码学累加器有望推动零知识证明向实用化更进一步。
相信在不远的将来，源自上世纪 90 年代的密码学累加器技术会继续进化，并出现工业级的开源代码实现，最终成为我们工具箱里一个功能强大的新武器。
其实，密码学领域里像累加器这样被埋没多年的“黑科技”还有很多。为了让这些“黑科技”不再被继续埋没，有梦想的少年们一起来搞密码学吧～
参考文献：
[1] Dan Boneh, Benedikt Bünz, Ben Fisch. Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains. CRYPTO 2019.
[2] Chenxing Li, Peilun Li, Dong Zhou, Wei Xu, Fan Long, Andrew Yao. Conflux: A Decentralized Blockchain with Near Optimal Throughput Latency. In submission.
[3] Josh Benaloh, Michael de Mare. One-way accumulators: A decentralized alternative to digital sinatures (extended abstract) . EUROCRYPT 1993.
[4] S. Haber, W.S. Stornetta. How to time-stamp a digital document. Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
[5] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. 2008.
[6] Thaddeus Dryja. Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set.
