近期，在收听区块链Zero Knowledge Podcast时，我了解到了RSA Accumulator的概念。经过一番搜索，我发现这是一个既有趣又充满数学深度的主题。由于其优越的验证特性，RSA Accumulator在从Stateless Client到Plasma以及UTXO模型的扩容讨论中频繁出现。因此，今天我将整理自己的学习笔记，其中涉及的一些数学概念较为复杂，我将尽量简化阐述。
Merkle Tree
要理解Accumulator，首先要从Merkle Tree说起。大家可能对Merkle Tree有所了解，它是一种通过层层哈希，最终用固定大小的哈希值（Merkle Root）来表示一个特定的键值表的数据结构。
最顶层的root值本身并不能证明任何东西，必须与Merkle Proof（Merkle Branch）结合才能达到验证的效果。例如，在下面的例子中，若要证明绿色方块的确存在于Merkle Tree中，你需要提交所有黄色方块的价值给验证者，让他们尝试一层层哈希，直到验证root值。
Merkle Proofs (from ethereum blog)
在比特币中，区块头会包含该区块所有交易的Merkle Root，因此一个只存储区块头的Light Client可以向全节点询问一个交易是否被包含在某个区块中，全节点可以利用Merkle Proof来证明其回答的正确性。以太坊中更广泛地使用了Merkle Tree，以便智能合约能够全面掌握当前状态。在每个区块中，除了tx root以外，还包含state root和receipt root，这使得以太坊可以通过Merkle Proof来验证包含用户余额、智能合约运行结果等查询的结果。
Accumulator
密码学中的Accumulator是一个单向成员函数。它回答一个查询，即一个潜在的候选者是否为集合的成员，而不泄露集合中的单个成员。
在密码学中，Accumulator指的是一个能够在不暴露所有群集元素的情况下，配合证明确保某个元素在一个群集之中的函数。正如我们之前看到的Merkle Tree，它也可以作为Accumulator的一种，因为通过已知的Merkle Root和Merkle Branch作为证明，我们就能证明一个元素的存在。
注：在严格的密码学定义中，proof需要是固定大小的，而Merkle Tree不符合这一要求，但接下来我们仍会继续用大家熟悉的Merkle Tree进行比较。
RSA Accumulator
接下来，我们将直接探讨RSA Accumulator。
其基本数学非常简单，我们通过一个质数g作为基底，再配合一个选择好的N = p * q，其中p和q都是秘密的大质数。
N Value Setup
首先需要介绍N的选择。N由两个秘密质数相乘而来，如果有人知道其组成，就可以破解RSA Accumulator的验证。因此，在选择N时，可以选择相信公开宣布已销毁p和q的N值，或者选择RSA2048这种目前技术难以分解的大数。另一种可行的方法是通过所谓的Class Group来创建N，但这需要涉及许多复杂的数学，有兴趣的人可以参考这篇论文。
Initiation and Membership Witness
当我们选定了基底g并想要创建一个Accumulator，放入数字a时，就进行g^a次方运算，得到AccumulatorA。
A = g^a mod N
若要向Accumulator中加入新的成员，就继续执行次方运算。例如，我们接着想要加入a_2和a_3，那么我们的Accumulator就会变为：
A = A^(a_2 * a_3) mod N = g^(a_2 * a_3 * a) mod N
若要证明a_2确实在这个Accumulator中，我们需要提供的witness是Accumulator扣除a_2的部分，验证则是试算w^a_2是否等于Accumulator的值。
w = g^(a * a_3) mod N
verify: A = w^a_2 mod N
也可以直接看最直观的数字例子（先忽略mod N）：
Adding and Verifying in RSA Accumulator
我们可以发现，无论Accumulator已经存储了多少东西，都可以通过在只知道Accumulator当前的root value的情况下，以O(1)的复杂度加入元素。这样的Accumulator称为Dynamic Accumulator，更广泛地说，就是能够随意Update这个Accumulator。
Aggregating Proofs
除此之外，我们还可以将多个想要验证的值合并在一起生成一个witness。例如，在下面的例子中，我们可以一次性验证5和13都在Accumulator中。这种将多个witness合并为一的特性称为累加性(Aggregating)。而有效地一次性生成或验证多个witness则称为批次性(Batching)。这两者都是Merkle Tree不具备的。
...
（以下内容省略，保持原文结构不变）...End Game
这是我第一次撰写这样具有学术内涵的文章，很多数学概念还是决定不详细展开，以免出现错误或理解上的偏差，所以最后整理出来的内容可能并不完美。这也是我第一次认真追踪了许多Ethereum Research的文章，尽管很多部分还是看不懂，但能够慢慢跟上讨论进度的感觉还是不错的。
我认为Stateless Client相对容易理解，所以这篇文章主要讨论了RSA Accumulator与Stateless Client之间的关系。不过RSA Accumulator在Plasma Cash中也是一个重要的讨论点，但因为我对于Plasma的理解不够深入，所以没有进一步研究，欢迎其他专家来补充。
最后，推荐想要更全面理解RSA Accumulator的朋友可以参考Benedikt Bünz的介绍。他就是与Podcast受邀人Ben Fisch一起发表了上面那篇Paper的人。他对Accumulator如何应用于UTXO set上进行了全面的剖析，相信大家看完都会有所收获。
Benedikt Bünz on RSA Accumulators
最后还是要感谢大家耐心阅读，希望对您有所帮助。如果有疑问或发现我写错的地方，也欢迎留言讨论指正。
标签: 数字货币
