区块链中的数学-RSA累加器非成员证明

blocksight 2021-04-26 10:27:33 阅读数:17

本文一共[544]字,预计阅读时长:1分钟~
区块 数学 rsa 累加 累加器

写在前面

上一篇介绍了累加器与RSA Accumulator, 累加器可以实现集合成员证明,还可以做非成员证明用途,本节继续介绍RSA累加器的非成员证明部分。

本文基础是上文,所有相同符号含义不变,建议先行阅读!

RSA累加器非成员证明

非成员证明(Non-Membership Witness)是证明一个元素不在该集合中。一般说来,正向证明(在集合中)比较容易,反向证明(不在集合中)相对难度大些。

原理:**假设集合中有三个元素,时,root = mod N要证明元素不在集合内,需要证明不是pi = 的(素)因子,即pi,互质。**贝祖定理(Bézout's identity)派上用场了。关于贝祖定理,之前历史文章也有提到,这里再简介一下:

贝祖定理:****ax + by = m (x, y)有整数解时当且仅当m是(a, b)的最大公因数的倍数。也就是说:ax + by = 1 ,(x, y)有整数解时当且仅当(a, b)互质。反之相对于a.b亦然!

那么,我们目标变成,找到一组数<a,b>使得a + b pi = 1 即可证明不在root表示的accumulator内.

举例说明:***令 =5, = 13, = 17,pi = 5 13 * 17 = 1105, root = mod N

令 = 7, 生成7不在累加器集合中的证明:***158 7 + (-1)*1105 = 1 即(a = 158, b = -1)

证明 w =

验证阶段:

= g

区块链应用

无状态客户端(stateless client)

区块链系统由于数据只增加不减的特性,导致数据量存储问题随着时间增加愈发明显, 现在的区块链系统中只有全节点(Full node)储存了所有数据,轻节点(Light Client)对于交易是否合法的验证需要对整个区块链状态(State)的了解,所以目前所有共识以及验证都是由全节点完成。

Stateless Client很早(2013)就是区块链的一个研究与发展方向,比特币论坛也称为Storageless Client,是对SPV轻节点一种改进,简而言之就是一个不需要储存所有State,却能参与交易验证的角色(而不是像SPV轻节点只能做概率性有效性验证)。

RSA Accumulator应用

区块链现有的merkle tree方案存在一些Stateless Client的障碍。例如以太坊,三个merkle state root纪录所有state,假设现在有一个只存header的无状态客户端,我们可以透过提供多个merkle proof来向他证明多个storage的值,间接证明一个交易是合法的。但merkle root 并没有stateless update的特性,无法在不知道所有state的情况下,靠其他方提供proof来进行状态root的更新。简言之,即使知道交易合法,也并不能更新state root以便进行下一个交易的验证。

换成RSA Accumulator,理论上就能拥有stateless client参与交易的验证的能力:**提交交易给一个stateless client,同时附上所有一个交易会用到的所有State对应的证明(还可以利用证明聚合,减少proof大小)。**在无状态节点收到请求时,利用这些witness来验证该交易。在接受了交易后,更新本地的accumulator。

理论归理论,现实很骨感!实际工程中,应用中考虑的问题很多,比如产生证明增加了计算量,需要权衡。

无状态客户端维护一个RSA Accumulator。这需要不断地监听以太坊的交易或者让全节点广播交易时候,就会附上witness,增加了通信量。

给节点角色分工增加了复杂度,全节点可能作为Data Provider&witness provider ,还有专门做验证的节点,甚至专门的stateless client交互所需要的Accumulator节点。看起来很好,需要一步步实践验证!

小结

RSA Accumulator非成员证明,能够进行假如用Accumulator纪录一个UTXO 集合,证明某个UTXO不存在等场景。****关于累加器还有其他类型不再多说了, 在区块链中的应用也值得期待!。

好了,下一篇继续介绍零知识证明其他内容!。

欢迎关注&在看, 疑问请留言!

相关阅读:

区块链中的数学(七十一) 累加器与RSA Accumulator

区块链中的数学(六十九) Kate承诺批量证明

区块链中的数学(六十七) 多项式知识和承诺

区块链中的数学(六十六) Pedersen 密钥分享

区块链中的数学(六十五) 密码学承诺--Pedersen承诺

区块链中的数学(六十三) 不经意传输协议

区块链中的数学(十二) RSA加解密算法

区块链中的数学(六十一) BLS m of n门限签名

区块链中的数学(五十九) BLS密钥聚合

Schnorr签名与椭圆曲线 Schnorr签名与椭圆曲线

区块链中的数学(三十七) Uniwap核心算法解析(中)

版权声明:本文为[blocksight]所创,转载请带上原文链接,感谢。 https://learnblockchain.cn/article/2439