Skip to content

Instantly share code, notes, and snippets.

@syuhei176
Last active September 3, 2022 07:44
Show Gist options
  • Save syuhei176/791e1350fffafa8f74c462bedad6da0d to your computer and use it in GitHub Desktop.
Save syuhei176/791e1350fffafa8f74c462bedad6da0d to your computer and use it in GitHub Desktop.
RSA accumulator
const primeNumberList = require('prime-number/list')
const BigNumber = require('bignumber.js');
const utils = require('ethereumjs-util');
// const primeNumberList = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47];
BigNumber.config({
DECIMAL_PLACES: 2,
ROUNDING_MODE: BigNumber.ROUND_FLOOR
})
class RSAAccumulator {
constructor() {
this.rootValue = new BigNumber(1);
this.g = new BigNumber(3);
this.N = new BigNumber(1560);
}
push(p) {
this.rootValue = this.rootValue.times(new BigNumber(p));
console.log(this.rootValue, p)
}
root() {
return this.rootValue;
//return this.g.pow(this.rootValue);
}
proof(v, x) {
console.log('proof', v);
const h = this.g.pow(v);
console.log(1, h);
console.log(2, x);
const z = this.g.pow(BigNumber(v).times(x));
console.log(3);
const B = this.hash(h, z).mod(this.N);
console.log('x.div(B)', x.div(B));
const tmp1 = x.div(B).integerValue(BigNumber.ROUND_FLOOR);
console.log(4, h, '^', tmp1);
const b = this.g.pow(BigNumber(v).times(tmp1));
console.log(5, b);
return [b, z, x];
}
hash(h, z) {
const hash = '0x' + utils.sha256(h.toString(), z.toString()).toString('hex')
// console.log(hash);
return new BigNumber(hash);
}
/**
*
* @param {*} v
* @param {*} proof
* @param {*} root
* @param {*} rr
* @return if non inclusion return true
*/
verifyNonInclusion(v, proof, root, x, rr) {
if(rr <= 0 || rr >= v) throw new Error('invalid rr')
return this.verify(v, proof, root, x, rr);
}
/**
*
* @param {*} v
* @param {*} proof
* @param {*} root
* @return if inclusion return true
*/
verifyInclusion(v, proof, root, x) {
return this.verify(v, proof, root, x, 0);
}
verify(v, proof, root, x, rr) {
console.log('verify')
if(!root.plus(rr).eq(x.times(v))) return false;
const h = this.g.pow(v);
const B = this.hash(h, proof[1]).mod(this.N);
const r = x.mod(B);
return proof[0].pow(B).times(h.pow(r)).eq(proof[1]);
}
}
let acc = new RSAAccumulator();
acc.push(primeNumberList[2]);
acc.push(primeNumberList[5]);
acc.push(primeNumberList[7]);
acc.push(primeNumberList[8]);
acc.push(primeNumberList[10]);
acc.push(primeNumberList[11]);
acc.push(primeNumberList[15]);
acc.push(primeNumberList[17]);
acc.push(primeNumberList[18]);
acc.push(primeNumberList[19]);
acc.push(primeNumberList[20]);
const root = acc.root();
console.log('root', root.toString());
const remFor3 = getRem(root, primeNumberList[3]);
const remFor12 = getRem(root, primeNumberList[12]);
const proof3 = acc.proof(primeNumberList[3], root.plus(remFor3).div(primeNumberList[3]));
const proof3i = acc.proof(primeNumberList[3], root.div(primeNumberList[3]).integerValue(BigNumber.ROUND_FLOOR));
const proof5 = acc.proof(primeNumberList[5], root.div(primeNumberList[5]))
const proof12 = acc.proof(primeNumberList[12], root.plus(remFor12).div(primeNumberList[12]));
// non inclusion
// should be true
console.log('verify 3', acc.verifyNonInclusion(
primeNumberList[3], proof3, root, root.plus(remFor3).div(primeNumberList[3]), remFor3))
// should be false
console.log('verify 3', acc.verifyInclusion(
primeNumberList[3], proof3i, root, root.div(primeNumberList[3]).integerValue(BigNumber.ROUND_FLOOR)))
// inclusion
console.log('verify 5', acc.verifyInclusion(
primeNumberList[5], proof5, root, root.div(primeNumberList[5])))
// non inclusion
// should be true
console.log('verify 12', acc.verifyNonInclusion(
primeNumberList[12], proof12, root, root.plus(remFor12).div(primeNumberList[12]), remFor12))
function getRem(root, prime) {
for(var i = 0;i < prime;i++) {
if(root.plus(i).div(prime).isInteger()) {
return i;
}
}
throw new Error('remainder is not zero');
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment