RSA accumulator

rsa-acc.js

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');
}