# Set non-inclusion with accumulation schemes

Let $\mathbf{G} \in \mathbb{G}^n$ be your public parameters. The accumulator is initialized as $A_0 = \langle (1, 0, 0, \cdots), \mathbf{G} \rangle$.

The goal of this construction is to allow you to insert vectors of elements $\mathbf{a_i} \in \mathbb{F}^n$ into an accumulator $A_i$ in step $i$ to produce a new accumulator $A_{i+1}$ and then later when the accumulator is in state $A_m$ we should be able to demonstrate for a _range_ of steps that the accumulator in each step $A_j$ had a vector $\mathbf{a_j}$ inserted that did _not_ contain the element $v \in \mathbb{F}^n$.

## Insertion

Insertion of $\mathbf{a_i}$ to $A_i$ can be done by computing $\mathbf{b_i}$ as the coefficients of the polynomial $\prod_j (X - \mathbf{a_i}_j)$. We compute $P_i = \langle \mathbf{b}, \mathbf{G} \rangle$ and then compute $h = H(A_i, P_i)$. The new accumulator becomes $A_{i + 1} = [h] A_i + P_i$.

## Non-membership for a range $j, ...$

Create a recursive (IVC) proof which has as its base case the state $(A_j, S_j = \langle (1, 0, 0, \cdots), \mathbf{G} \rangle)$. We do the following process in each step $i \geq j$. Witness $P_{i}$ for the insertion for that step, and given that our claim is that $v$ was not present in $\mathbf{a_i}$, then $P_i$ should be a vector commitment to the coefficients of a polynomial that does not have a root at $v$. This means that this polynomial evaluates at $v$ to a _nonzero_ value $\alpha_i$. Thus, $P'_i = P_i - [\alpha_i] \mathbf{G}_0$ is a commitment to a polynomial that _does_ have a root at $v$. In each step of the proof, we witness $\alpha_i$ and compute

$$
\begin{array}{ll}
h = H(A_i, P_i) \\
h' = H(S_i, P'_i)
\end{array}
$$

and output the new state $$(A_{i+1}, S_{i + 1}) = ([h] A_i + P_i, [h'] S_i + P'_i)$$

Given an IVC proof that this has been performed for many steps, we arrive at state $(A_m, S_m)$. Now, given that $A_m$ is the expected value of the accumulator, if $S_m$ is a commitment to the coefficients of a polynomial that has $v$ as a root then with high probability our claim is satisfied. This latter condition can be demonstrated by either revealing the coefficients or using a PCS/SNARK to evaluate $S_m$ at $v$ to see that it equals zero.

## Properties of this Construction

1. We can start a non-membership proof for $v$ at any point in the history of the accumulator (the start of the range) and make progress on it with each insertion step vector $\mathbf{a_i}$ via IVC. We can discard old step vectors $\mathbf{a_i}$ and old accumulator states and keep only the current state.
2. The proof at the end is really simple and efficient.
3. Each IVC step just involves a couple hash operations and a constant number of group operations.
4. The accumulator does not grow in size as insertions happen, and verifying non-membership proofs does not require history of insertions to be maintained. In theory, all old history is pointless once all IVC proofs that may need to demonstrate these claims over old insertion steps have been created.

In short, this is an ideal accumulator for set non-membership if you'll know what you want to check non-membership of well in advance of a later state of the accumulator. It doesn't work so well in the case where you want to retroactively check non-membership for arbitrary values, since this requires you to know of and recreate the history of the insertions into the accumulator for the range you want.

## Notes

Obviously this can be adapted for use in set inclusion, which is simpler. The conditions just change, though there are more efficient methods of accomplishing the same thing using append-only Merkle trees.