区块链中的数学 -- Accumulator(累加器)
source link: https://learnblockchain.cn/article/2373
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
区块链中的数学 -- Accumulator(累加器)
本文描述了累加器的概念和性质，具体说明RSA累加器实现过程。可以看出Accumulator具有一些比merkle证明有优势的地方，比如聚合证明,证明大小不随着集合元素的增加而增加等。 实际应用实现中RSA累加器还会有一些前置处理操作，比如将原始数据映射到选定素数域上的值等。
上一篇介绍了merkle承诺原理， 最近几篇的主题围绕密码学承诺，可以来一个总结了。
有一个比喻说的很好，承诺就像把一封信放在保险箱内上锁并发给接收方，由于保险箱在接收方，发送方已无法修改信的内容，同时保险箱钥匙在发送方手中，信件的内容不会被接收方看到，起到隐藏的作用！
本文介绍一种与密码学承诺紧密关联的技术 --- Accumulator(累加器),近两年在区块链无状态领域提到较多！
Accumulator(累加器)
在密码学中，累加器是单向成员散列函数。它允许用户证明潜在的元素是某个集合的成员，而不必透露集合中的单个成员。这一概念于1993年由J.Benaloh和M.de Mare正式提出，根据这个定义，Merkle tree也可以当作简单Accumulator的一种。后续也有对累加器含义做了一些扩展，感兴趣可自行查阅！
累加器分为动态和静态两种类型：
动态累加器：
当有元素加入或者移除时，承诺和对应的证明可以进行有效更新，是指更新的代价应与已累加的元素数量无关
静态累加器：
当有元素加入或者移除时，承诺和对应的成员证明需总体重新生成，且无法进行有效更新。
一般通用累加器都是动态累加器，同时支持集合内成员证明和非成员证明两部分。我们以常用的RSA累加器为例进行说明。
RSA accumulator
为什么叫做RSA累加器呢？因为实现过程与RSA算法相近，安全假设也一样。
Accumulator 创建：
- setup: 选择一个质数g作为基底，再秘密选择两个大质数相乘得到 N = p * q
- 加入元素：集合添加元素a,计算root=ga mod N
- 删除元素：集合添加元素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=ga2a3
验证：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 )
- 分类：入门/理论
Recommend
-
27
罗列了交易的几种情况算法流程 写在前面 上一节说了 Uniwap核心算法中的流动性管理 ， 主要核心内容已经讲完了，这一节说下实现相关内容，作为总...
-
26
本文简要概述了爱德华曲线方程和有限域K上点运算，在参数d不是k平方的情况下，是完备的，即没有异常点以及相同点操作也是一致的（对比之前的椭圆曲线点加法规则（有无穷远点，相同点操作异与不同点），这样的性质可以增强对侧信道攻击（si...
-
21
本文介绍了爱德华曲线运算的几何意义，引入了扭曲爱德华曲线。 写在前面 上一节说了 爱德华曲线基本方程和点运算规则 ，由于Edwards curve是新的...
-
28
Ed25519使用了扭曲爱德华曲线，签名过程和之前介绍过的Schnorr,secp256k1, sm2都不一样，最大的区别在于没有使用随机数，这样产生的签名结果是确定性的，即每次对同一消息签名结果相同。 写在前面 上一节...
-
56
本文主要说了EdDSA签名机制的发展及其优点 写在前面 上一节介绍了Ed25519签名机制，本节我们介绍爱德华签名更多内容。 Why EdDSA ？ 为什么要有爱德华签名机制？ 这就要从其发展历...
-
13
动态秘密共享方案可有效提高长周期密钥的安全性。本文介绍了典型的Amir Herzberg实现方案，默认情况下所有参与者都参与，恢复阶段只要大于或等于门限t个参与能够周期性地更新自己的密钥部分，就能达到目的，本质上是 n 个参与者...
-
9
双线性配对特性不仅可以用于签名构造，密钥协商等，还可以实现乘法的同态隐藏和校验。这一点在零知识证明项目中应用很多。另外需要说明的是，并非基于任何椭圆曲线都可以构造配对函数，对于能有效实现双线性对的椭圆曲线，称为pairing-fri...
-
8
区块链中的数学 - 不经意传输 | 登链社区 | 深入浅出区块链技术区块链中的数学 - 不经意传输
-
14
写在前面 上一篇介绍了不经意传输协议，原本打算本文写paillier加密及其同态，但是想想还是后面再说比较好，按循序渐进顺序，先介绍密码学承诺更自然些， 好了，进入正题 --- 密码学中的承诺！...
-
11
本文介绍密码学承诺的含义及性质，并对哈希承诺做了说明，关于hash函数的内在机制实际是比较复杂的，我们以黑盒的角度来学习了解它的性质，在区块链&密码学中，哈希函数占据了基础且重要的位置。 比如区块链中常用的sha256,keccak等哈希算法。...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK