Accumulator

Pairing-based ECC accumulator — a constant-size commitment to a set, constant-size membership witnesses, and a zero-knowledge membership proof that hides which element is held.

The accumulator package implements the pairing-based accumulator of eprint 2020/777, together with the zero-knowledge proof of knowledge from section 7 of that paper. Its own package doc states the scope limit up front: only the membership-witness case is implemented. Non-membership witnesses, and the accumulator initialisation those would require, are deliberately absent — Accumulator.New simply sets the initial value to the G1 generator.

The value proposition

Three properties, and they are the entire reason to reach for this instead of a Merkle tree or a plain list:

• The accumulator is one curve point regardless of how many elements it holds. On BLS12-381 that is a 48-byte compressed G1 point; Accumulator.MarshalBinary returns 60 bytes with its BARE framing, at 1 element and at 5000 alike.
• A membership witness is one curve point plus its element. MembershipWitness.MarshalBinary is 92 bytes, again independent of set size.
• The membership proof hides the element. A verifier learns that the prover holds a valid witness for some accumulated element, not which one.

That last property is what makes this a privacy-preserving revocation mechanism. An issuer accumulates one element per valid credential and publishes the accumulator. A holder proves its credential is still accumulated without identifying the credential, and therefore without being linkable across presentations. Revocation is a Remove by the manager.

When not to use it

Only the holder of the SecretKey can mutate the set or issue a witness — Add, Remove, AddElements, Update, and MembershipWitness.New all take *SecretKey. If you need a publicly-updatable set, or set membership without a trusted manager, this is the wrong tool. If you need non-membership proofs, they are not implemented. If you need proofs cheaper than a multi-pairing per verification, look elsewhere.

Also note the operational cost: every update invalidates every outstanding witness. See the witness staleness warning below before committing to this design.

Types

Everything here is over a pairing curve — in practice curves.BLS12381(&curves.PointBls12381G1{}). The accumulator value lives in G1; the public key lives in G2.

Every one of these types implements MarshalBinary() ([]byte, error) and UnmarshalBinary([]byte) error — the encoding is BARE (git.sr.ht/~sircmpwn/go-bare). Note that all fields are unexported, so binary marshalling is the only way to move these values across a process boundary; there is no JSON codec and no field access.

Keys

Accumulator operations

Witnesses

Witness staleness is the hard part

Zero-knowledge membership proof

The proof protocol from section 7 of the paper. Unlike the witness check, this hides y. It is a three-move sigma protocol compiled with Fiat-Shamir, and — unusually — verification is expressed as recomputing the challenge and comparing it, not as a Verify method.

Full lifecycle

Membership proof end to end

Grounded in accumulator/proof_test.go (TestMembershipProof) and accumulator/witness_test.go (Test_Membership, Test_Membership_Batch_Update).

package main

import (
	"fmt"

	"github.com/sonr-io/crypto/accumulator"
	"github.com/sonr-io/crypto/core/curves"
)

func main() {
	curve := curves.BLS12381(&curves.PointBls12381G1{})

	// --- Manager setup -----------------------------------------------------
	sk, err := new(accumulator.SecretKey).New(curve, []byte("32-plus-bytes-of-real-entropy..."))
	if err != nil {
		panic(err)
	}
	pk, err := sk.GetPublicKey(curve)
	if err != nil {
		panic(err)
	}

	// Application data is hashed into set elements.
	elements := []accumulator.Element{
		curve.Scalar.Hash([]byte("credential-3")),
		curve.Scalar.Hash([]byte("credential-4")),
		curve.Scalar.Hash([]byte("credential-5")),
		curve.Scalar.Hash([]byte("credential-6")),
	}

	acc, err := new(accumulator.Accumulator).WithElements(curve, sk, elements)
	if err != nil {
		panic(err)
	}

	// --- Issue a witness (manager only, needs sk) --------------------------
	wit, err := new(accumulator.MembershipWitness).New(elements[3], acc, sk)
	if err != nil {
		panic(err)
	}

	// The plain witness check reveals which element is held. Use it for
	// self-diagnosis, not as a privacy-preserving presentation.
	if err := wit.Verify(pk, acc); err != nil {
		panic(err)
	}

	// --- Zero-knowledge membership proof -----------------------------------
	// Both sides must derive identical ProofParams.
	params, err := new(accumulator.ProofParams).New(curve, pk, []byte("proof-params/v1"))
	if err != nil {
		panic(err)
	}

	mpc, err := new(accumulator.MembershipProofCommitting).New(wit, acc, params, pk)
	if err != nil {
		panic(err)
	}
	challenge := curve.Scalar.Hash(mpc.GetChallengeBytes())
	proof := mpc.GenProof(challenge)

	// Verifier: it has acc, pk, params, the proof, and the challenge.
	final, err := proof.Finalize(acc, params, pk, challenge)
	if err != nil {
		panic(err)
	}
	if final.GetChallenge(curve).Cmp(challenge) != 0 {
		panic("membership proof rejected")
	}
	fmt.Println("membership proved without revealing which element")

	// --- Manager revokes and adds ------------------------------------------
	additions := []accumulator.Element{curve.Scalar.Hash([]byte("credential-7"))}
	deletions := []accumulator.Element{curve.Scalar.Hash([]byte("credential-5"))}

	// Note: this mutates acc in place and also returns it.
	_, coefficients, err := acc.Update(sk, additions, deletions)
	if err != nil {
		panic(err)
	}

	// --- Holder refreshes its now-stale witness ----------------------------
	if _, err := wit.BatchUpdate(additions, deletions, coefficients); err != nil {
		panic(err)
	}
	if err := wit.Verify(pk, acc); err != nil {
		panic(err) // would fail without the BatchUpdate above
	}
}

Note that a fresh ProofParams per presentation is fine and is what the test does — proof params are public and only need to agree between the two parties for that one exchange.

Catching up across epochs

MultiBatchUpdate takes three parallel outer slices, one entry per epoch, and errors with "a, d, c should have same length" if they disagree. From Test_Membership_Multi_Batch_Update:

_, coeffs1, _ := acc.Update(sk, adds1, dels1)
_, coeffs2, _ := acc.Update(sk, []accumulator.Element{}, dels2)
_, coeffs3, _ := acc.Update(sk, []accumulator.Element{}, dels3)

a := [][]accumulator.Element{adds1, {}, {}}
d := [][]accumulator.Element{dels1, dels2, dels3}
c := [][]accumulator.Coefficient{coeffs1, coeffs2, coeffs3}

if _, err := wit.MultiBatchUpdate(a, d, c); err != nil {
	panic(err)
}
if err := wit.Verify(pk, acc); err != nil {
	panic(err)
}

Caveats

On ordering: the additions and deletions slices a holder passes to BatchUpdate enter only as products, so their internal order is irrelevant — but they must be the same sets the manager passed to Update. The []Coefficient slice is different: it is evaluated as a polynomial by index, so it must be passed exactly as Update returned it, unreordered and untruncated.