This is an implementation of a CL cryptographic accumulator over the RSA cryptosystem.

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

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

Constructing an accumulator requires generating an RSA key (a random key is generated if you do not give it one).

// Import rsa-acc.
const {Accumulator, Update} = require('rsa-acc')
// An algorithm used to map data to elements in Z_q.
const hash = 'SHA-256'
// Construct a trusted accumulator.
const accumulator = new Accumulator(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 d1w1 = await accumulator.add(d1)
// Verify the result.
assert(await accumulator.verify(d1w1))

Subsequent additions of elements invalidate the previously returned witnesses.

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

Previous witnesses can be updated using the witnesses returned from subsequent additions.

// Update the witness for d1.
const update = new Update(accumulator)
await update.add(d2w1)
const d1w2 = await update.update(d1w1)
// Verify the result.
assert(await accumulator.verify(d1w2))

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

// Delete d1 from the accumulator.
await accumulator.del(d1w2)
// Demonstrate that the element's witnesses are no longer valid.
assert(await accumulator.verify(d1w1) === false)
assert(await accumulator.verify(d1w2) === false)

Previous witnesses must be updated after a deletion as well.

// Update the witness for the remaining element.
const update = new Update(accumulator)
await update.del(d1w2)
const d2w2 = await update.update(d2w1)
// Demonstrate that the new witness is valid.
assert(await accumulator.verify(d2w2))

Accumulator

Witness

Update

BigInt : Object

Primes : Object

Kind: global class

• Accumulator
  • new Accumulator(H, [key])
  • .add(x) ⇒ Promise.<Witness>
  • .del(witness) ⇒ Promise.<BigInt>
  • .verify(witness) ⇒ Promise.<Boolean>
  • .prove(x) ⇒ 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 accumulator.

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

Delete an element from the accumulation.

Kind: instance method of Accumulator
Returns: Promise.<BigInt> - The new accumulation.

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.

Prove an element's membership.

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

Kind: global class

Creates a new Witness instance.

Kind: global class

• Update
  • new Update(accumulator)
  • .add(witness)
  • .del(witness)
  • .undoAdd(witness)
  • .undoDel(witness)
  • .update(witness) ⇒ Promise.<Witness>

Creates a new Update instance.

Absorb an addition to the update.

Kind: instance method of Update

Absorb a deletion to the update.

Kind: instance method of Update

Remove an addition from the update.

Kind: instance method of Update

Remove a deletion from the update.

Kind: instance method of Update

Update the witness. This must be called after each addition to or deletion from the accumulation for each remaining element before it may be successfully verified.

Kind: instance method of Update
Returns: Promise.<Witness> - An updated witness.

Kind: global typedef

Kind: global typedef
Properties