写在前面
上一篇介绍了累加器与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核心算法解析（中）
