区块链中的数学 -- Accumulator(累加器)

本文描述了累加器的概念和性质，具体说明RSA累加器实现过程。可以看出Accumulator具有一些比merkle证明有优势的地方，比如聚合证明,证明大小不随着集合元素的增加而增加等。 实际应用实现中RSA累加器还会有一些前置处理操作，比如将原始数据映射到选定素数域上的值等。

上一篇介绍了merkle承诺原理， 最近几篇的主题围绕密码学承诺，可以来一个总结了。
有一个比喻说的很好，承诺就像把一封信放在保险箱内上锁并发给接收方，由于保险箱在接收方，发送方已无法修改信的内容，同时保险箱钥匙在发送方手中，信件的内容不会被接收方看到，起到隐藏的作用！

本文介绍一种与密码学承诺紧密关联的技术 --- Accumulator(累加器),近两年在区块链无状态领域提到较多！

Accumulator(累加器)

在密码学中，累加器是单向成员散列函数。它允许用户证明潜在的元素是某个集合的成员，而不必透露集合中的单个成员。这一概念于1993年由J.Benaloh和M.de Mare正式提出，根据这个定义，Merkle tree也可以当作简单Accumulator的一种。后续也有对累加器含义做了一些扩展，感兴趣可自行查阅！

累加器分为动态和静态两种类型：

动态累加器：
当有元素加入或者移除时，承诺和对应的证明可以进行有效更新，是指更新的代价应与已累加的元素数量无关
静态累加器：
当有元素加入或者移除时，承诺和对应的成员证明需总体重新生成，且无法进行有效更新。

一般通用累加器都是动态累加器，同时支持集合内成员证明和非成员证明两部分。我们以常用的RSA累加器为例进行说明。

RSA accumulator

为什么叫做RSA累加器呢？因为实现过程与RSA算法相近，安全假设也一样。

Accumulator 创建：

1. setup: 选择一个质数g作为基底，再秘密选择两个大质数相乘得到 N = p * q
2. 加入元素：集合添加元素a,计算root=ga mod N
3. 删除元素：集合添加元素a,计算root=root/ga mod N

举例说明：
只有一个元素a的时候，root=ga mod N
再次加入新元素a2​,a3​时，更新root=roota2​∗a3​ mod N=ga2​∗a3​∗a mod N

Accumulator成员证明:

假设要证明a2​确实在这个Accumulator之中，我们需要提供证明：
w=root/a2​=ga∗a3​ mod N

很简单就是除掉a2​部分

Accumulator 验证:
验证者得到root, w和要验证的元素a2​，计算
root′=wa2​ mod N=?=root

如果相等就证明a2​确实在累加器中。

可以看到，不管当前Accumulator已经存放的多少元素，都可以通过在只知道Accumulator当前root值的情况下，以O(1)的复杂度加入元新的元素。所以说属于动态累加器。

聚合证明（Aggregating Proofs):
还有一种情况能否同时验证多个元素属于该累加器集合？是可以的。
思路是把多个想要验证的值，合并在一起产生一个witness（即上文中的w）。

接着上例，我们可以一次验证a2​,a3​, 都包含在Accumulator中。具体先计算 w=ga2​a3​
验证：root′=wa mod N=?=root

我们把能同时整合多个witness为一的特性称为累加性 (Aggregating)，而有效率的同时验证多个witness则称为批次性 (Batching)，在Kate承诺批处理中，有过类似的处理。

本文描述了累加器的概念和性质，具体说明RSA累加器实现过程。可以看出Accumulator具有一些比merkle证明有优势的地方，比如聚合证明,证明大小不随着集合元素的增加而增加等。
实际应用实现中RSA累加器还会有一些前置处理操作，比如将原始数据映射到选定素数域上的值等。

好了，关于RSA累加器，下一篇继续介绍非成员证明和在区块链中应用部分。

本文参考：
https://www.cs.purdue.edu/homes/ninghui/papers/accumulator_acns07.pdf

原文链接：https://mp.weixin.qq.com/s/3JqXXbt0HYwKmWC2SBk2HA
欢迎关注公众号：blocksight

区块链中的数学--Merkle树承诺 merkle承诺

区块链中的数学 - Kate承诺batch opening Kate承诺批量证明

区块链中的数学 - 多项式承诺 多项式知识和承诺

区块链中的数学 - Pedersen密钥共享 Pedersen 密钥分享

区块链中的数学 - Pedersen承诺 密码学承诺--Pedersen承诺

区块链中的数学 - 不经意传输 不经意传输协议

区块链中的数学 - RSA算法加解密过程及原理 RSA加解密算法

区块链中的数学 - BLS门限签名 BLS m of n门限签名

区块链中的数学 - BLS密钥聚合 BLS密钥聚合

Schorr签名与椭圆曲线 Schorr签名与椭圆曲线

区块链中的数学-Uniwap自动化做市商核心算法解析 Uniwap核心算法解析（中）

• 发表于 12小时前
• 阅读 ( 27 )
• 学分 ( 0 )
• 分类：入门/理论