This is an implementation of a cryptographic accumulator over elliptic curves.

Features:

• Constant time accumulation: Updating the accumulation does not require access to all previously accumulated values.
• Constant size accumulation: Components of the accumulation are constant size.
• Trustless proofs: An untrusted prover may compute a witness of membership for any accumulated element without knowledge of any sensitive information.
• Constant time witness updates: Trustless witness updates are $O(n^2)$.

$ git clone https://github.com/johnoliverdriscoll/ecc-acc
$ cd ecc-acc
$ npm install

There are two classes in this module. The first is Accumulator, which represents a trusted party that is able to add and delete elements from an accumulation as well as verify an element's membership. Constructing an accumulator requires the parameters for an elliptic curve and an optional secret (a random secret is generated if you do not give it one).

// Import an underlying elliptic curve.
const curve = require('@noble/curves/secp256k1')
// An algorithm used to map data to elements in Z_q.
const hash = 'SHA-256'
// Construct a trusted accumulator.
const accumulator = new Accumulator(curve, hash)

The next class is Prover, which represents an untrusted party that is able to compute proofs of membership for elements that have been accumulated. The prover does not require knowledge of the secret stored by the accumulator.

// Construct an untrusted prover.
const prover = new Prover(curve, hash)

When adding an element, the accumulator returns a witness that can be used to verify its membership later.

// Add an element.
const d1 = '1'
const u1 = await accumulator.add(d1)
// Verify the result.
assert(await accumulator.verify(u1))

The object returned from Accumulator.add contains information that the prover requires to compute witnesses. Pass it to Prover.update.

// Update the prover with the result.
await prover.update(u1)

Subsequent additions of elements invalidate the previously returned witnesses.

// Add a new element.
const d2 = '2'
const u2 = await accumulator.add(d2)
// Verify the result.
assert(await accumulator.verify(u2))
// Demonstrate that the witness for d1 is no longer valid.
assert(await accumulator.verify(u1) === false)

As long as the prover is kept updated, it can compute valid witnesses for any accumulated element.

// Update the prover with the result.
await prover.update(u2)
// Compute a new witness for d1.
const w1 = await prover.prove(d1)
// Verify the result.
assert(await accumulator.verify(w1))

An element can be deleted from the accumulator, which invalidates its witness.

// Delete d1 from the accumulator.
const u3 = await accumulator.del(w1)
// Demonstrate that the original witness is no longer valid.
assert(await accumulator.verify(w1) === false)

The prover must be updated after a deletion as well.

// Update prover with the result.
await prover.update(u3)
// Compute a new witness for d2.
const w2 = await prover.prove(d2)
// Verify the result.
assert(await accumulator.verify(w2))

It will not, however, be able to prove the membership of deleted elements.

// Compute a new witness for the deleted element.
const w3 = await prover.prove(d1)
// Demonstrate that the new witness is not valid either.
assert(await accumulator.verify(w3) === false)

Accumulator

Prover

BigInt : Object

Curve : Object

Point : Object

Update : Object

Witness : Object

WitnessUpdate : Object

Kind: global class

• Accumulator
  • new Accumulator(curve, H, [c])
  • .add(d) ⇒ Promise.<WitnessUpdate>
  • .del(witness) ⇒ Promise.<Update>
  • .verify(witness) ⇒ Promise.<Boolean>
  • .prove(d) ⇒ Promise.<Witness>

Creates a new Accumulator instance. An Accumulator is a trusted party that stores a secret and can modify the accumulation of member elements.

Add an element to the accumulation.

Kind: instance method of Accumulator
Returns: Promise.<WitnessUpdate> - A witness of the element's membership.

Delete an element from the accumulation.

Kind: instance method of Accumulator
Returns: Promise.<Update> - The updated public component.

Verify an element is a member of the accumulation.

Kind: instance method of Accumulator
Returns: Promise.<Boolean> - True if element is a member of the accumulation; false otherwise.

Compute a proof of membership for an element.

Kind: instance method of Accumulator
Returns: Promise.<Witness> - A witness of the element's membership.

Kind: global class

• Prover
  • new Prover(curve, H)
  • .update(updateOrWitness)
  • .prove(d) ⇒ Promise.<Witness>
  • .verify(updateOrWitness) ⇒ Promise.<Boolean>

Creates a prover. A Prover is an untrusted party that receives update information from the Accumulator and can compute witnesses for elements based on that information.

Update membership data. This must be called after any element is added or deleted from the accumulation.

Kind: instance method of Prover

Compute a proof of membership for an element.

Kind: instance method of Prover
Returns: Promise.<Witness> - A witness of the element's membership.

Verify an element is a member of the accumulation.

Kind: instance method of Prover
Returns: Promise.<Boolean> - True if element is a member of the accumulation; false otherwise.

Kind: global typedef

Kind: global typedef

Kind: global typedef

Kind: global typedef
Properties

Kind: global typedef
Properties

Kind: global typedef
Properties