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

  • blocksight
  • 更新于 2021-04-19 12:44
  • 阅读 6989

RSA Accumulator非成员证明,能够进行假如用Accumulator纪录一个UTXO 集合,证明某个UTXO不存在等场景。

写在前面

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

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

RSA累加器非成员证明

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

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

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

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

举例说明: 令$ a_1=5,a_2 = 13,a_3 = 17,pi = 5 13 17 = 1105, root=g^{pi} =g^{1105}\ mod\ N$

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

证明 $w = (g^a,b)=(g^{158},-1)$

验证阶段:

$g^{a_4a} root^b = g^{7158} root^{-1} = 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不存在等场景。 关于累加器还有其他类型不再多说了, 在区块链中的应用也值得期待!。

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


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


相关阅读

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

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

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

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

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

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

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

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

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

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

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

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
blocksight
blocksight
江湖只有他的大名,没有他的介绍。