Quasi-Commutative Accumulators

[bhgomes]

Quasi-commutative accumulators have the following property:

h(h(acc, x), y) = h(h(acc, y), x)

where acc is the accumulated value. In general, these can be used to build zero-knowledge sets (rather than zero-knowledge ordered sets like Merkle Trees).

One possible idea for a ZKP-friendly quasi-commutative accumulator is just elliptic-curve scalar multiplication:

x * (y * G) = y * (x * G)

where G is the accumulated value. The proof protocol for this accumulator is the following:

struct Proof {
    witness: Group,
    accumulator: Group,
}

fn prove_membership(item: Scalar, proof: Proof) -> bool {
    Group::scalar_mul(proof.witness, item) == proof.accumulator
}

In order to generate the proof for a given item, someone with access to all the items multiplies all the items except the one they want to prove into one (secret) witness.

fn generate_proof(base: Group, item: Scalar, other_items: &[Scalar]) -> Proof {
    let mut witness = other_items.iter().fold(base, Group::scalar_mul);
    Proof { accumulator: Group::scalar_mul(witness, item), witness }
}

[bhgomes]

A set of pairing-based accumulators to take a look at: https://eprint.iacr.org/2021/638.pdf.