An accumulator allows Bob to add values onto a fixed-length digest, and to provide proof of the values added, without revealing them within the accumulated value. In this case we will use a basic ECC method to make commitments to data elements.
ECC accumulators with Node.js |
Method
We will use a secp256k1 curve and a hash of SHA-256, and where the private key value will be used to add and delete data entities on the accumulator. Initially, we create a random secret key value (\(sk\)) and then a public key of:
\(pk= sk.G_1\)
and where \(G_1\) is the base point on the \(\mathbb{G}_1\) group. We can then initialise the accumulator from the base point on the \(\mathbb{G}_1\) group:
\(a_0=G_1\)
To add \(y_1\), we add to the accumulator with:
\(a_1=(y_1+sk).a_0\)
To add \(y_2\), we add to the accumulator with:
\(a_2=(y_2+sk).a_1 = (y_2+sk) (y_1+sk). a_0 \)
To remove \(y_1\) from \(a_2\):
\(a_3=a_2 . \frac{1}{y_1+sk} = \frac{ (y_1+sk).a_0 . (y_2 + sk) } {y_1+sk} = (y_2+sk) . a_0 \)
The code in Node.js to add \(e\) and which is a hash of a message (\(msg\)) onto the secret key of \(sk\) is:
acc = acc.multiply(e.add(sk).mod(n))
This takes the current accumulator value (\(acc\)) and multiplies by \(e+sk\). The reason that we have methods for the arithmetic operations, is that we are dealing with Big Integers, and which have a much greater scope than our integer data types. To remove this hash:
acc = acc.multiply(e.add(sk).mod(n).modInverse(n))
and where \(n\) is the order of the curve. This takes the current accumulator value (\(acc\)) and divides by \(e+sk\).
Coding
The outline code in the following adds to message, and then verifies they have been added. We will then delete the second value, and prove that it does not exist. Finally we will prove that a value does not exist, and that has never existed on the accumulator:
const {Accumulator, Prover} = require('./ecc-acc/index') const ec = require('ecurve') const curve = ec.getCurveByName('secp256k1') const hash = 'sha256' const accumulator = new Accumulator(curve, hash) const prover = new Prover(curve, hash) msg1 = '1' msg2 = '3' var args = process.argv; if (args.length>1) msg1=args[2]; if (args.length>2) msg2=args[3]; witness = accumulator.add(msg1) rtn=accumulator.verify(witness) console.log("== Adding data to accumulator ==="); console.log("Adding: ",msg1," Verified:\t",rtn); prover.update(witness) witness = accumulator.add(msg2) rtn=accumulator.verify(witness) console.log("== Adding data to accumulator ==="); console.log("Adding: ",msg2," Verified:\t",rtn); console.log("\nNow deleting ",msg2) witness = accumulator.del(witness) console.log("== Deleting data to accumulator ==="); console.log("Deleting: ",msg2," Verified:\t",rtn); prover.update(witness) witness = prover.prove(msg2) rtn=accumulator.verify(witness) console.log("Does element exist:\t", rtn); console.log("\nDeleting bob123") witness = prover.prove('bob123') rtn=accumulator.verify(witness) console.log("Does element exist:\t", rtn);
A sample run:
== Adding data to accumulator === Adding: Bob Verified: true == Adding data to accumulator === Adding: Alice Verified: true Now deleting Alice == Deleting data to accumulator === Deleting: Alice Verified: true Does element exist: false Deleting bob123 Does element exist: false