-
-
Save jb55/32bc914b047b8e03d6820cd0b2a1b457 to your computer and use it in GitHub Desktop.
RSA accumulator
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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