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

这篇文章主要介绍了区块链中的数学 — Accumulator(累加器) ,文中通过代码以及文档配合进行讲解,很详细,它对在座的每个人的研究和工作具有很经典的参考价值。 如果需要,让我们与区块链资料网一起学习。

https://www.interchains.cc/21556.html

区块链中的数学 — Accumulator(累加器)是很好的区块链资料,他说明了区块链当中的经典原理,可以给我们提供资料,区块链中的数学 — Accumulator(累加器)学习起来其实是很简单的,

不多的几个较为抽象的概念也很容易理解,之所以很多人感觉区块链中的数学 — Accumulator(累加器)比较复杂,一方面是因为大多数的文档没有做到由浅入深地讲解,概念上没有注意先后顺序,给读者的理解带来困难

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

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

写在前面

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

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

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 =g^a mod N$
  3. 删除元素:集合添加元素a,计算$root = root /g^a mod N$

举例说明: 只有一个元素a的时候,$root =g^a mod N$ 再次加入新元素$a_2,a_3$时,更新$root =root^{a_2a_3} mod N=g^{a_2a_3*a} mod N$

Accumulator成员证明:

假设要证明$a_2$确实在这个Accumulator之中,我们需要提供证明: $w = root /a_2 =g^{a*a_3} mod N$

很简单就是除掉$a_2$部分

Accumulator 验证: 验证者得到root, w和要验证的元素$a_2$,计算 $root’ =w^{a_2} mod N =?= root$

如果相等就证明$a_2$确实在累加器中。

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

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

接着上例,我们可以一次验证$a_2,a_3$, 都包含在Accumulator中。具体先计算 $w =g^{a_2a_3}$ 验证:$root’ =w^a mod N =?= root$

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

小结

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

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

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


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


相关阅读

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

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

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

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

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

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

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

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

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

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

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

部分转自网络,侵权联系删除www.interchains.cchttps://www.interchains.cc/21556.html

区块链毕设网(www.interchains.cc)全网最靠谱的原创区块链毕设代做网站 部分资料来自网络,侵权联系删除! 最全最大的区块链源码站 ! QQ3039046426
区块链知识分享网, 以太坊dapp资源网, 区块链教程, fabric教程下载, 区块链书籍下载, 区块链资料下载, 区块链视频教程下载, 区块链基础教程, 区块链入门教程, 区块链资源 » 区块链中的数学 — Accumulator(累加器)

提供最优质的资源集合

立即查看 了解详情