Witness Updates

This is a brief primer on updating witnesses to an accumulator (in the specific case of membership witnesses).

Preliminaries

A witness is just an accumulator, nothing more or less. So let's consider some witness w, which is just an accumulator for a set of elements U.

For this witness to be useful, we have to describe it relative to another accumulator a (whose set we'll call capital A).

Note that there is a discrepancy between U and A, namely some set of elements T equal to the set difference A - U. If we described this witness relative to a different accumulator a', this set difference would be a different result T'.

Relative Witnesses

Now we have a natural way of describing witness w as a tuple (a, T), consisting of an accumulator and a set of elements. We say that w tracks the elements T with respect to a.

I could give you w and a to prove to you that T is in the accumulator set of a, and you would verify this claim by checking w.add(T) == a (a simplification, but this is the gist of it). These proofs are what witnesses are useful for.

For a witness w in our code, we say that U are the untracked_elems and T are the tracked_elems with respect to some accumulator.

Witness Updates

Let's move to a real-world setting, where I have a global accumulator a (whose set is A) and some witness w tracking elements T w.r.t. a. (As before, the untracked elements are some set U.)

I might have w because I'm a user with a UTXO x, and when I spend the x, I need to prove that it's in the set of a. Here, T = {x}.

Or I might have w because I'm a bridge node (in our parlance), and I'm responsible for keeping UTXOs x_1, x_2, ..., x_n valid for several users. Here, T = {x_1, x_2, ..., x_n}.

Either way, I'm listening for additions and deletions to a in the network (e.g. new blocks being published by blockchain miners). If these changes occur, my witness w = (a, T) is no longer valid with respect to the new accumulator a', and a witness update may be required.

When a set of changes (additions or deletions to a) come in, we can categorize them as follows:

1. Tracked additions: New accumulator elements that this user/bridge wants its witness to track (e.g. someone creates and sends me a UTXO).

2. Tracked deletions: Deleted accumulator elements that this user or bridge's witness has been tracking (e.g. I spend a UTXO).

3. Untracked additions: New accumulator elements that this user/bridge doesn't care about (e.g. someone creates a UTXO and sends it to a user that isn't me).

4. Untracked deletions: Deleted accumulator elements that this user/bridge doesn't care about (e.g. someone that isn't me spends a UTXO).

In cases (1) and (2), we actually don't need to update the witness w.

Proof: Recall that the current accumulator set of w is U = A - T. After some tracked additions and deletions, we have A' - T' = (A + T_add - T_delete) - (T + T_add - T_delete) = A - T = U as desired.

Cases (3) and (4) require an update, since A changes while T remains constant. The accumulator paper has more details on the witness update, but essentially it requires the new accumulator a' = acc, the current T = tracked_elems, the untracked_additions, and the untracked_deletions.