Cryptographic Accumulator

下面通过实例演示一下 Alice 往 Accumulator 中加入元素 \(X=\{x_1,x_2,x_3\}=\{3, 5, 11\}\) （注：由于这里的元素本身就是素数，下面省略了把元素转换为某种素数表达的过程） ，并向 Bob 证明元素 \(x_1,x_2,x_3\) 确实存在于 Accumulator 中。

首先确定好参数 \(g, p, q\) ，一旦计算完 \(N=p\cdot q\) ，就丢弃掉 \(p,q\) ，这是一个 Trusted Setup 步骤。也就是说，需要一个可信任的第三方来完成这个 Setup 步骤， \(p,q\) 不能让 Alice 知道，否则 Alice 可能构造一些假的 witness。因为 RSA Accumulator 是基于 Strong RSA assumption ，如果 \(p,q\) 泄露了，就不满足 Strong RSA assumption 的前提了，构造假 witness 会变得可行。

Alice 进行下面计算：

1. 往 Accumulator 加入 \(3\) 时，计算 \(root_1 = g^3 \pmod N\) ，
   
2. 再往 Accumulator 加入 \(5\) 时，计算 \(root_2 = root_1^5 \pmod N = g^{3 \times 5} \pmod N\) ，
   
3. 再往 Accumulator 加入 \(11\) 时，计算 \(root_3 = root_2^{11} \pmod N = g^{3 \times 5 \times 11} \pmod N\) ，
   

最终得到的 \(acc_X = root_3 = g^{3 \times 5 \times 11} \pmod N\)

Alice 还要计算每个元素的 witness： \[\begin{aligned} w_1 &= g^{ x_2 \times x_3} \pmod N = g^{ 5 \times 11} \pmod N \\ w_2 &= g^{ x_1 \times x_3} \pmod N = g^{ 3 \times 11} \pmod N \\ w_3 &= g^{ x_1 \times x_2} \pmod N = g^{ 3 \times 5} \pmod N \end{aligned}\]

Bob 验证 \[acc_X \stackrel{?}{=} w_i^{x_i}\] 是否成立，如果成立则说明 \(x_i\) 在这个 Accumulator 中，比如，如果 \(acc_X = w_1^{x_1}\) 成立则说明 \(x_1\) 在 Accumulator 中。

注：计算所有元素的 witness 是比较耗时间的，时间复杂度为 \(O(n^2)\) ，Dan Boneh 等在论文 Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains 中提出一种名为 RootFactor 的分治算法可以把时间复杂度降低为 \(O(n \log n)\) 。

RSA Accumulator 加入元素的运算是在整数模 \(N\) 乘法群 \((\mathbb{Z}/N\mathbb{Z})^*\) 上的运算。这个群的 Order 为 Euler's totient function \(\phi(n)=(p-1)(q-1)\) ，由于 \(p,q\) 生成后就会被弃掉，所以没人知道 \(\phi(n)=(p-1)(q-1)\) 是多少（除非有办法把合数 \(N\) 重新分解为两个素数的乘积，但分解大整数是个数学难题，目前没有有效算法）。RSA Accumulator 中所谓的 Unknown Order Group 就是指整数模 \(N\) 乘法群 \((\mathbb{Z}/N\mathbb{Z})^*\) 。

前面提到过，加入元素到 RSA Accumulator 中前，要先把元素转换为它的素数表达。因为，如果加入到 RSA Accumulator 中的元素不是素数，则攻击者可以伪造元素的 witness，这个元素不在 RSA Accumulator 中，但它的 witness 却可以通过校验，下面进行举例说明。

假设 Accumulator 中直接保存了 \(X=\{5,6,11\}\) （注：这其中的元素 \(6\) 并不是素数），即 \[acc_X = g^{5 \times 6 \times 11} \pmod N = g^{330} \pmod N\] 那么攻击者可以提供一个假证明 \[w=g^{110} \pmod N\] 来证明元素 \(3\) 存在于 Accumulator 中。因为验证者计算 \[acc_X = \left(g^{110}\right)^3 \pmod N\] 会确实成立的。但事实上 \(3\) 并不存在于 Accumulator 中，这样攻击者成功地欺骗了验证者。

2007 年，Jiangtao Li 等在论文 Universal Accumulators with Efficient Nonmembership Proofs 中提出了证明某元素不存在于某 Accumulator 中的方法。

给定 RSA Accumulator \(acc_X\) 其中加入了集合 \(S\) 的所有元素，元素 \(x\) 不属于 Accumulator 的 witness 的计算如下：

1. \(s^{*} \leftarrow \prod_{s \in S}s\)
   
2. \(a,b \leftarrow Bezout(x, s^*)\)
   
3. \(d \leftarrow g^a\)
   

则 \(x\) 不属于 Accumulator 的 witness 就是二元组 \(\{d, b\}\)

有了 witness，证明 \(x\) 不属于 Accumulator 的过程如下，检测 \[d^x acc_X^b \stackrel{?}{=} g\] 是否成立，如果成立则 \(x\) 不属于 Accumulator。

为什么这种方法可以证明 \(x\) 不属于 \(S\) 呢？背后的原理是对于任何 \(x \notin S\) ， \(gcd(x, \prod_{s \in S}s)=1\) 一定成立，从而由 Bézout's identity 可知， \(a \times x + b \times \prod_{s \in S}s = 1\) 一定有解，这里把它的解做为了 \(x \notin S\) 的证据。