---
title: Accumulator
description: 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.
sidebar:
label: Accumulator
order: 3
icon: list-checks
---
The `accumulator` package implements the pairing-based accumulator of
[eprint 2020/777](https://eprint.iacr.org/2020/777.pdf), 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](#witness-staleness-is-the-hard-part) 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.
| Type | Definition | Notes |
| --- | --- | --- |
| `Element` | `curves.Scalar` | A set member. Callers hash application data into it, e.g. `curve.Scalar.Hash([]byte("credential-id"))`. |
| `Coefficient` | `curves.Point` | Batch-update polynomial coefficients published by the manager alongside an `Update`. |
| `Accumulator` | struct, unexported `value curves.Point` | The set commitment. |
| `SecretKey` | struct, unexported `value curves.Scalar` | The manager's alpha. |
| `PublicKey` | struct, unexported `value curves.PairingPoint` | `alpha · G2`. |
| `Delta` | struct, unexported `d curves.Scalar`, `p curves.Point` | Witness-update material. See the caveat — you cannot build one. |
| `MembershipWitness` | struct, unexported `c curves.Point`, `y curves.Scalar` | A holder's witness for element `y`. |
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
:::warning[SecretKey.New is a bare hash of the seed]
`SecretKey.New` is `sk.value = curve.Scalar.Hash(seed)` and always returns a nil error. It
does not check seed length or entropy. A short or predictable seed yields a guessable alpha,
and alpha is total control over the set. Feed it at least 32 bytes from a CSPRNG, or a
properly derived key — see [Key derivation](/symmetric/key-derivation).
:::
## Accumulator operations
:::danger[Every mutator mutates the receiver in place]
`Add`, `AddElements`, `Remove`, `Update`, `WithElements`, and `New` all assign to
`acc.value` and then return the same pointer. The returned `*Accumulator` is **not** a new
object — it is the receiver. This idiom compiles cleanly and reads like a functional API:
```go
newAcc, _, err := acc.Update(sk, additions, deletions) // newAcc == acc
```
but `acc` has already changed. If you need the previous state — to serve an older epoch, or
to roll back — call `MarshalBinary()` **before** the mutation and keep the bytes.
`MembershipWitness.New`, `ApplyDelta`, `BatchUpdate`, and `MultiBatchUpdate` behave the same
way on their receivers.
:::
## Witnesses
### Witness staleness is the hard part
:::danger[Updating the set invalidates every outstanding witness]
The witness for element `y` is `1/(y + alpha) · V`, defined *relative to a specific
accumulator value*. The moment the manager adds or removes anything, `V` changes and every
holder's `Verify(pk, acc)` against the new accumulator fails. This is not a bug; it is
inherent to the construction, and it is the dominant operational cost of deploying it.
The manager must therefore publish, for each update, the `[]Coefficient` returned by
`Update` along with the exact `additions` and `deletions` element lists. Holders call
`BatchUpdate(additions, deletions, coefficients)` to move their witness forward. A holder
that misses epochs uses `MultiBatchUpdate` with the per-epoch slices.
Consequences you must design for:
- Coefficients and element lists are **not secret**, but they *do* reveal exactly which
elements were added and removed. Batch your updates if that leakage matters.
- A holder that skips an epoch and cannot obtain that epoch's coefficients can never repair
its witness without the manager reissuing via `MembershipWitness.New`.
- `AddElements` returns no coefficients at all. Use `Update` — even with an empty deletion
slice — whenever witnesses are outstanding.
- A stale witness does not report itself as stale. `Verify` returns the generic
`"invalid result"` from the failed pairing check, which is indistinguishable from a forged
witness. Track the accumulator epoch alongside the witness in your own state.
:::
## 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
Derive a `SecretKey` from a strong seed and publish the `PublicKey`.
`new(Accumulator).WithElements(curve, sk, elements)` and publish the accumulator bytes.
For each holder, `new(MembershipWitness).New(element, acc, sk)` and deliver the witness
bytes privately. This step needs the secret key.
The holder builds `ProofParams`, runs `MembershipProofCommitting`, hashes
`GetChallengeBytes()` into a challenge, and sends the challenge plus `GenProof(challenge)`.
The verifier calls `Finalize` then `GetChallenge`, and accepts iff the recomputed
challenge equals the one it was given.
The manager calls `Update(sk, additions, deletions)` and publishes the new accumulator,
the element lists, and the coefficients.
Every holder calls `BatchUpdate(additions, deletions, coefficients)`, then can prove again
against the new accumulator.
### Membership proof end to end
Grounded in `accumulator/proof_test.go` (`TestMembershipProof`) and
`accumulator/witness_test.go` (`Test_Membership`, `Test_Membership_Batch_Update`).
```go membership.go
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`:
```go catchup.go
_, 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
:::danger[ApplyDelta is unreachable from outside the package]
`ApplyDelta(delta *Delta)` is exported, but `Delta`'s fields are unexported and the only
constructors — `evaluateDelta` and `evaluateDeltas` — are unexported. No exported function
anywhere in the package returns a `*Delta`. From another package you can therefore obtain one
only by `UnmarshalBinary`-ing bytes that some in-package code produced, and no in-package code
hands them to you. Treat `ApplyDelta` as an internal helper and use `BatchUpdate` /
`MultiBatchUpdate`, which construct the delta for you.
:::
:::warning[Remove does not check membership]
`Remove` applies `1/(y + alpha)` unconditionally. Removing an element that was never added
yields a mathematically valid but semantically meaningless accumulator, and every outstanding
witness silently stops verifying with no diagnostic. The package keeps no member list — the
manager must track set contents itself.
:::
:::warning[No length or duplicate checks on batch inputs]
`BatchAdditions`, `BatchDeletions`, and `Update` accept whatever elements you pass, including
duplicates. Adding the same element twice multiplies the accumulator by `(y + alpha)` twice,
and one `Remove` will not undo both.
:::
:::note[Non-membership is not implemented]
The paper's non-membership witnesses require a different accumulator initialisation
(`V0 = product(y + alpha) · P` over a designated set). This package's `New` sets `V0` to the
plain G1 generator and its own doc comment flags this as the reason non-membership is out of
scope. Do not attempt to derive non-membership proofs from this API.
:::
:::info[There is no MembershipProof.Verify]
Verification is a two-call sequence — `Finalize` then `GetChallenge` — followed by a scalar
comparison you write yourself. Forgetting the comparison, or comparing against a challenge
the *prover* supplied without deriving it from a transcript you control, defeats the proof.
The prover's challenge in the test is `curve.Scalar.Hash(mpc.GetChallengeBytes())`; a verifier
that wants soundness against a chosen-challenge prover should recompute the challenge from the
proof transcript rather than trusting a transmitted scalar.
:::
:::warning[A revoked holder gets a cryptic error, not a clean rejection]
`BatchUpdate` inverts `product(yD_i - y)` over the deletion list. If the holder's own element
`y` appears in `deletions`, that product is zero and the call fails with
`"no inverse exists"`. That is the revoked-credential path, and it surfaces as an internal
arithmetic error rather than a "you were revoked" signal. Handle it explicitly.
:::
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.