rsa-acc

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

Setup

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

Tutorial

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

API Reference

Classes

Accumulator

Witness

Update

Typedefs

BigInt : Object

Primes : Object

Accumulator

Kind: global class

• Accumulator
  • new Accumulator(H, [key])
  • .add(x) ⇒ Promise.<Witness>
  • .del(witness) ⇒ Promise.<BigInt>
  • .verify(witness) ⇒ Promise.<Boolean>
  • .prove(x) ⇒ Promise.<Witness>

new Accumulator(H, [key])

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
H	String | function	The name of a hash algorithm or a function that returns a digest for an input String or Buffer.
[key]	Primes | BigInt	Optional secret primes or public modulus. If no argument given, secret primes will be generated.

accumulator.add(x) ⇒ Promise.<Witness>

Add an element to the accumulator.

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

Param	Type	Description
x	String | Buffer	The element to add.

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

Delete an element from the accumulation.

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

Param	Type	Description
witness	Witness	Witness of element to delete.

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	A witness of the element's membership.

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

Prove an element's membership.

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

Param	Type	Description
x	String | Buffer	The element to prove.

Witness

Kind: global class

new Witness(x, nonce, w)

Creates a new Witness instance.

Param	Type	Description
x	Data	The element.
nonce	BigInt	Sums to a prime when added to H(x).
w	BigInt	The accumulation value less the element.

Update

Kind: global class

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

new Update(accumulator)

Creates a new Update instance.

Param	Type	Description
accumulator	Accumulator	The current accumulation.

update.add(witness)

Absorb an addition to the update.

Kind: instance method of Update

Param	Type	Description
witness	Witness	A witness of the element's addition.

update.del(witness)

Absorb a deletion to the update.

Kind: instance method of Update

Param	Type	Description
witness	Witness	A witness of the element's addition.

update.undoAdd(witness)

Remove an addition from the update.

Kind: instance method of Update

Param	Type	Description
witness	Witness	A witness of the element's addition.

update.undoDel(witness)

Remove a deletion from the update.

Kind: instance method of Update

Param	Type	Description
witness	Witness	A witness of the element's addition.

update.update(witness) ⇒ Promise.<Witness>

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.

Param	Type	Description
witness	Witness	The witness to update.

BigInt : Object

Kind: global typedef

Primes : Object

Kind: global typedef
Properties

Name	Type	Description
p	BigInt	The larger prime.
q	BigInt	The lesser prime.