ecc-acc

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)$.

Setup

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

Tutorial

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)

API Reference

Classes

Accumulator

Prover

Typedefs

BigInt : Object

Curve : Object

Point : Object

Update : Object

Witness : Object

WitnessUpdate : Object

Accumulator

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>

new Accumulator(curve, H, [c])

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

Param	Type	Description
curve	Curve	An object containing the curve parameters.
H	String | function	The name of a hash algorithm or a function that returns a digest for an input String or Buffer.
[c]	BigInt	An optional secret. If not provided, a random secret is generated.

accumulator.add(d) ⇒ Promise.<WitnessUpdate>

Add an element to the accumulation.

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

Param	Type	Description
d	Data	The element to add.

accumulator.del(witness) ⇒ Promise.<Update>

Delete an element from the accumulation.

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

Param	Type	Description
witness	Witness | WitnessUpdate	A witness of the element's membership.

accumulator.verify(witness) ⇒ Promise.<Boolean>

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.

Param	Type	Description
witness	Witness | WitnessUpdate	A witness of the element's membership.

accumulator.prove(d) ⇒ Promise.<Witness>

Compute a proof of membership for an element.

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

Param	Type	Description
d	Data	The element to prove.

Prover

Kind: global class

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

new Prover(curve, H)

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.

Param	Type	Description
curve	Curve	An object containing the curve parameters.
H	String | function	The name of a hash algorithm or a function that produces a digest for an input String or Buffer.

prover.update(updateOrWitness)

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

Kind: instance method of Prover

Param	Type	Description
updateOrWitness	Update | WitnessUpdate	An update or witness.

prover.prove(d) ⇒ Promise.<Witness>

Compute a proof of membership for an element.

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

Param	Type	Description
d	Data	The element to prove.

prover.verify(updateOrWitness) ⇒ Promise.<Boolean>

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.

Param	Type	Description
updateOrWitness	Witness | WitnessUpdate	An update or witness.

BigInt : Object

Kind: global typedef

Curve : Object

Kind: global typedef

Point : Object

Kind: global typedef

Update : Object

Kind: global typedef
Properties

Name	Type	Description
d	String | Buffer	The element.
z	Point	The current accumulation.
Q	Point	The public component.
i	Number	The index.

Witness : Object

Kind: global typedef
Properties

Name	Type	Description
d	String | Buffer	The element.
v	Point	The previous accumulation.
w	Point	The previous accumulation raised to the secret value.

WitnessUpdate : Object

Kind: global typedef
Properties

Name	Type	Description
d	String | Buffer	The element.
z	Point	The current accumulation.
v	Point	The previous accumulation.
w	Point	The previous accumulation raised to the secret value.
Q	Point	The public component.
i	Number	The index.