Given an accumulator digest, how to compute the membership proof of an element in the set?

[sshravan]

Assume that I have access to all the elements of the set. How do I accomplish [1-5]?

  let acc = Accumulator::<Rsa2048, &'static str>::empty();
  let acc = acc.add(&["dog"]); // A = {"dog"}
  let acc = acc.add(&["cat"]); // A = {"dog", "cat"}
  let acc = acc.add(&["cow"]); // A = {"dog", "cat", "cow"}

  // 1. Get Membership proof of "dog" given acc and all elements in A
  // 2. Get Non-Membership proof of "pig", given acc and all elements in A
  // 3. Get Batch Membership proof of "dog" and "cat",  given acc and all elements in A

  // 4. Verify Membership proof of "dog" using acc and proof from 1.
  // 5. Verify Batch Membership proof of "dog" and "cat" using acc and proof from 3.

I prefer not using the update_membership_witness.

Thanks in advance!

[whaatt]

Hey @sshravan, thanks for the question!

You can do (2) with just acc and the full set of elements (see here).

For the rest, I'm wondering why you don't want to use update_membership_witness. Can you explain your use case a little more?

[sshravan]

Hey! Thanks. Basically, I am looking for the MemWitCreate from page 14 that the library cites.

Here is my use case though: Assume that I have a trusted centralized accumulator manager that a client invokes to get the most up to date proof of an UTXO.

Hence the manager keeps track of the following:

Acc = {"dog", "cat", "cow"}  // Current UTXO set
Acc_digest = A // Current Digest of set Acc

Let's assume the following insertion sequence:

t = 1 Insert "cow"
t = 2 Insert "man"
t = 3 Insert "cat"
t = 4 Insert "dog"
t = 5 Delete "man"

At t = 5
current proof of "cow" = g ^ ("dog" * "cat") = w
Verify proof of "cow" = w.g^("cow") == A

Since the current proof of "cow" is dependent of the current elements in the set, I am not sure if keeping tracking of all add-delete since "cow" is the best way to go about, considering that my manager already saves the current set.

Hope it is clear.

[whaatt]

We don't have MemWitCreate exactly as described in the paper, but given the complete accumulator set, your centralized accumulator could easily compute the following:

// Disclaimer: Haven't actually tried compiling this...
// ... `acc` defined previously ...

let empty_acc = Accumulator::<Rsa2048, &'static str>::empty();
let cow_witness = Witness(empty_acc.add([... all elements except "cow" ...]));

// If you have other elements/witnesses in the batch, add them to the array below:
let cow_membership_proof = acc.prove_membership([("cow", cow_witness)]);

That said, in general the end-users would not have to "track all the add-deletes" if you used update_membership_witness. Rather, they'd call update_membership_witness for their personal elements each time a change to the accumulator is broadcast over the network. The changes can be discarded as soon as the witness is updated.

I don't know all the specifics of your use case, but note that in the example above, the centralized source of truth has to nearly regenerate the entire accumulator to determine cow_witness. This could be an expensive operation in general.

Let me know if this helps!

[sshravan]

Thanks a lot for the help! It makes sense. In my use case, client can go offline. Clients, instead syncing up with all the changes broadcast over the network, lazily query the manager for the latest proof of their UTXO.

On a different note, is there an equivalent of CreateAllMemWit (Page 16)? Is it compute_individual_witnesses?

[whaatt]

Yep! If you have a witness w for N elements, you can compute the witnesses for each individual element using w.compute_individual_witnesses([... elements ...]) in N log N time.