最近在听区块链Zero Knowledge Podcast的时候听到了RSA Accumulator的介绍，搜寻之后发现是个有趣，也略微复杂很多数学的主题，由于它更佳的验证特性，从Stateless Client到Plasma以及UTXO模型扩容中都有被讨论。因此今天就来整理一下自己的学习纪录，其中有些数学太过艰涩难懂，我就收录简单的部分。

Merkle Tree

要了解Accumulator还得从Merkle tree说起。相信大家对于Merkle tree都有一定程度的了解，就是一层一层的Hash，最后用固定大小的杂凑值(Merkle root)来表示一个特定的key value table。

最顶端这个root值不能独自证明什么，必须要搭配着Merkle proof(Merkle branch)来达到「验证」的效果。像下图中的例子，若是要证明绿色方块的值确实在这个merkle tree中，你需要同时提交所有黄色方块的值给验证者，让他们试着一层一层Hash上来，看看是不是跟root值一样。

Merkle Proofs (fromethereum blog)

在比特币中，一个区块会在区块头中会附上该区块所有交易的merkle root，因此一个只存区块头的Light Client可以向全节点(full node)询问一个交易是否被包含在某个区块中，全节点可以利用merkle proof来证明自己回答的正确性。以太坊中更广泛的使用merkle tree，为了让智能合约对current state有全盘掌握，在每个区块中除了tx root以外，还含有state root 以及receipt root。这使得以太可以透过merkle proof来验证包含用户余额、智能合约运行等等查询的结果。

Accumulator

A cryptographic accumulator is a one-way membership function. It answers a query as to whether a potential candidate is a member of a set without revealing the individual members of the set.

在密码学中，Accumulator指的是一个能够在不暴露所有群集元素的情况下，配合证明(proof)确保某个元素在一个群集之中的函数。我们刚刚所看的Merkle tree就可以当作Accumulator的一种，因为透过已知merkle root情况下，配合merkle branch作为proof，我们就能证明一个元素的存在。

注：严谨的密码学定义中，会要求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之中，我们需要提供的witnessw就是Accumulator扣除了a_2的部分，验证则是试算w^ a_2是否等于Accumulator的值

w = g^(a * a_3) mod Nverify: 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不具备的。

接续上面的例子，我们可以用一个w 验证两个element。

Non-Membership Witness

RSA Accumulator除了能够的验证一个element在一个Accumulator中外，也能够进一步给出非成员证明(non-membership witness)，及证明一个数字不存在此Accumulator中。验证方法会需要用到贝祖定理(Bézout's identity)：

ax + by = m (x, y)有整数解时若且唯若m是(a, b)的最大公因数d的倍数。也就是说：ax + by = 1 (x, y)有整数解时若且唯若(a, b)互质。

用上面的例子来看，假如果们要证明数字7不是1105因数，根据贝祖定理，我们只要找到一组满足7a + 1105b = 1的整数解即可。完整的过程如下：

non-membership proof with RSA Accumulator

同样基于贝祖定理，V神在这篇讨论文中介绍了另一个验证方式。沿用上一个例子，若是要证明x不在集合当中，我们需要找到一个值r满足:

0 < r < x A * g^r为g^x的整数次方

以下是简单的证明，表达这个验证方式跟我们刚刚使用的方式是等效的

Vitalik 的验证方式证明

能够进行非成员验证的Accumulator称为Universal Accumulator，一般的merkle tree是无法达成的(必须要有特殊排序才行)。这是个很好用的特性，假如我们用Accumulator纪录一个UTXO set，我们就可以使用非成员证明来证明在特定区块高度，某个UTXO不存在。

Proof of Knowledge Schemes

现在我们已经知道RSA如何进行验证，基本上就是次方的运算。但这在实践上有个困难点，因为若是结合了许多要验证的值的话，x的大小会线性成长，因此我们不会直接提供x，而是需要再透过其他proof of knowledge scheme来间接完成。

我们可以把问题简化成：已知u ^ x = w，如何在不实际运算u^x的情况下验证这件事情。以下我们举一个简单例子：Proof of Exponentiation。

Proof of Exponentiation

透过这个Scheme，最后proof大小上会因为x/B的步骤而限缩。而验证时，虽然需要Verifier自己算出r = x mod B，不过在RSA的使用情境中会比算次方快上许多。

在Georgios Konstantopoulos的A Deep Dive on RSA Accumulator这篇文章中更仔细的介绍了不同Proof of Knowledge Scheme如何配合RSA Accumulator进行membership以及non-membership的验证，就留给对数学更有兴趣的人自己看啦。

Conclusion on RSA Accumulators

最后我们来整理一下RSA Accumulator所有的好处，其中我觉得最重要的是以下两点，它在我们接下来要讨论的Stateless Client中至关重要。

Proof大小不随验证成员数增加。 不需知道所有State也能进行更新。

Stateless Client

现在的区块链网路中只存在储存了所有资讯的全节点(Full node)，以及需要与全节点连线才能运作的Light Client。这是因为对于交易是否合法的验证需要涉及对整个区块链状态(State)的了解，所以目前所有共识以及验证都是由全节点完成。

Stateless Client其实是一个从2013年开始就开始被比特币讨论的主题（当时比特币论坛称为Storageless Client），简而言之就是一个「不需要储存所有State，却能参与交易验证」的角色。如果真的有了Stateless Client，网路中的矿工节点以及认证交易的节点，将不再需要花大量的记忆体存所有的帐户余额资讯。

Applying RSA Accumulator

区块链现有的merkle tree架构存在一些Stateless Client的障碍。我们以ETH为例，merkle state root 纪录了所有state的现状，假设现在有一个只存区块头的Stateless Client，我们可以透过提供多个merkle proof来向他证明多个storage的值，接着进一步证明一个交易是合法的。但merkle root 并没有stateless update的特性，无法在不知道所有state的情况下，靠着我们提供给他的proof来进行state root的更新。也就是说他即使知道我们交易合法，也并不能更新state root接着进行下一个交易的验证。

若我们能把merkle tree换成RSA Accumulator，理论上就能真正有stateless client参与「交易的验证」：我们若是要提交交易给一个stateless client，我们就必须附上所有一个交易会动用到的所有State对应的witness，另一个好消息是我们还可以透过aggregating特性将这个proof变为constant size。在节点收到我们的请求时，他可以快速利用这些witness来验证并且决定要不要采信该交易。在接受了我们交易后，client也可以快速的update accumulator并接着进行验证。

Stateless Clients in the Ecosystem

在一个使用者与stateless client的互动模式中，我们将整个验证过程的成本从「Node储存State花费的空间」转嫁到了「使用者计算witness」上。我们可以认真思考一下，这究竟对使用者是一个多大的负担

首先要产生对应的witness，代表使用者必须要维护一个RSA Accumulator。这意味着不断地监听以太坊的交易，并且不断的更新自己的Accumulator，这显然是一个不合理的要求。

不过也别忘了，网路中还是存在许多的全节点，使用者与全节点的互动不需要有任何改变，因为全节点知晓一切，这可能会让使用者最终还是选择将交易提交给全节点当中，而全节点就担任了联络stateless client的角色，当它知道它的广播对象是stateless的时候，就会附上witness交给这些节点验证。

有另外一个值得思考的问题就是，究竟整个以太网路中，有多少节点是专注于「交易验证」，有多少则专注于「给应用层进行查询和沟通」。有了stateless的选项之后，我们可以让专门做验证的节点以及矿工节点变为stateless，而全节点可能演变成一个Data Provider的角色，提供给应用层进行余额等等查询，也可以是一个witness provider ，为使用者维护要与stateless client沟通所需要的Accumulator。这是一个更为健康的生态系，不同的节点若能在一个网路中真正各司其职，相信将会是stateless client能创造最大的价值。

所以，一起期待RSA Accumulator以及Stateless Client的未来吧！

End Game

这是第一次撰写这么学术内涵的文章，很多数学看来看去还是决定不要放上来免得打错或理解错很尴尬，所以最后写出来也就不太难了xD。这也是第一次认真的追了很多Ethereum Research 的文章，虽然很多部分还是看不懂，但能够慢慢Follow上讨论进度的感觉还是不错的。

个人觉得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

最后还是谢谢大家有耐心看完，希望对你有帮助。如果有疑虑或是发现我写错的，也欢迎留言讨论指教啦！

Reference

The Stateless Client Concept

Accumulators, scalability of UTXO blockchains, and data availability

History, state, and asynchronous accumulators in the stateless model

RSA Accumulators for Plasma Cash history reduction