Bulletproofs and Rangeproof (Node.js)Bulletproofs were created in 2017 by Stanford’s Applied Cryptography Group (ACG) [paper]. They define a zero-knowledge proof and where a value can be checked to see it lies within a given range. The name of "bulletproofs" is defined as they are short like a bullet, and with bulletproof security assumptions. In the following we define the size of the bit vector and then check to see if a value is in that range - a range proof. If the bit vector is 8 bits long, then we will prove that the value lies between 0 and 255. A value larger than this will fail. The test is thus whether \(x \in [0,2^{n} - 1]\), and where \(n\) is the number of bits in the bit vector. |
Method
A confidential transaction can be made private by using the Pedersen Commitment. If the value we want to keep secret is \(x\) then if we take a point on the elliptic curve (\(H\)), we get a public key point of:
\(T_x=xH\)
If \(x\) is a small value, then this will not hide the value of \(x\) as Eve could simply compute of the low values of \(x\) and brute force the value of \(T_x\).
The Pedersen Commit can then be used to hide the value of \(x\) by adding a random value (\(r\)). Now we pick another point (\(G\)) and a large random value (\(r\)). Now the commitment (\(C(x,r)\)) becomes:
\(C(x,r) = xH + rG\)
Now we cannot determine \(x\) as we would need \(r\). If Bob saves this transaction, he could keep \(r\) in his wallet, and then reveal to someone when required.
The value of \(x\) is thus know as the blinding value. Let’s say that we have a transaction value of \(v\), we can now define this as a point on the elliptic curve (H) as:
\(C = v \times H\)
If we have three transactions (\(v_1\), \(v_2\) and \(v_3\)), we can create a sum total of:
\(\text{Total} = v_1 \times H + v_2 \times H+ v_3 \times H= (v_1+v_2+v_3) \times H\)
We can thus determine the sum of the transactions. But we could eventually find-out the values of \(v_1\), \(v_2\) and \(v_3\), as they would always appear as the same value when multiplied by G. We can now add a blinding factor by adding a second point on another elliptic curve (H) and a private key (r).
A transaction value is then (as defined as a Pedersen Commitment):
\(v \times H + r \times G\)
Let’s say that Bob has two input values (v1 and v2) and one output value (v3), and where v3= v1+v2. We can then create a blinding factor for each transaction:
\((ri_1 \times G + vi_1 \times H) + (ri_2 \times G + vi_2 \times H) = (ro_3 \times G + vo_3 \times H)\)
Then:
\(ri_1 + ri_2 = ro_3\)
In this case if we can prove this, we have proven that the inputs are equal to the outputs.
Within Bulletproofs, we implement a range proof, and where we prove that \(x \in [0,2^{n} - 1]\), and where \(n\) is the number of bits in the bit vector.
Outline
The following is the code [taken from here]:
/*###############################################################################################*/ /*################################ Prover ##################################################*/ /*###############################################################################################*/ const util = require('util'); function rangeBpProver(x1,pedCom1,r0,r1){ const crypto = require('crypto'); const BigInteger = require('big-integer'); const Consts = require('./consts'); const utils = require('./utils'); const pickRandom = utils.pickRandom; const modulo = utils.modulo; const moduloPow = utils.moduloPow; const moduloAddq = utils.moduloAddq; const moduloSubq = utils.moduloSubq; const moduloMulq = utils.moduloMulq; const moduloMul = utils.moduloMul; const aL = []; const aR = []; const SL = []; const SR = []; const alpha = pickRandom(Consts.q); const rho = pickRandom(Consts.q); const gVector = []; const hVector = []; var gRand; var hRand; const H = utils.ec.g.mul((r0.toString(Consts.HEX))); let v = 0; while(v< Consts.upperBoundNumBits){ gRand = utils.ec.g.x.fromRed().toString(16).concat(BigInteger(v).toString(Consts.HEX)); hRand = H.x.fromRed().toString(16).concat(BigInteger(v).toString(Consts.HEX)); gVector[v] = utils.ec.g.mul(modulo(BigInteger(crypto.createHash('sha256').update(gRand).digest('hex'),Consts.HEX),Consts.q).toString(Consts.HEX)); hVector[v] = H.mul(modulo(BigInteger(crypto.createHash('sha256').update(hRand).digest('hex'),Consts.HEX),Consts.q).toString(Consts.HEX)); v++; } var A = H.mul(alpha.toString(Consts.HEX)); var S = H.mul(rho.toString(Consts.HEX)); let i = 0; while(i< Consts.upperBoundNumBits){ aL[i]=x1.shiftRight(i).mod(2).and(BigInteger(1)); aR[i]= moduloSubq(aL[i],BigInteger(1)); A = A.add(gVector[i].mul(aL[i].toString(Consts.HEX))).add(hVector[i].mul(aR[i].toString(Consts.HEX))); //A = A.add(Q.mul(aL[i].toString(Consts.HEX))).add(Q.mul(aR[i].toString(Consts.HEX))); SL[i] = pickRandom(Consts.q); SR[i] = pickRandom(Consts.q); S = (S).add(gVector[i].mul(SL[i].toString(Consts.HEX))).add(hVector[i].mul(SR[i].toString(Consts.HEX))); //S = (S).add(Q.mul(SL[i].toString(Consts.HEX))).add(Q.mul(SR[i].toString(Consts.HEX))); i++; } const y_str = crypto.createHash('sha256').update(A.x.fromRed().toString(16).concat(S.x.fromRed().toString(16))).digest('hex'); const z_str = crypto.createHash('sha256').update(A.x.fromRed().toString(16).concat(S.x.fromRed().toString(16).concat(y_str))).digest('hex'); const y = BigInteger(y_str,Consts.HEX); const z = BigInteger(z_str,Consts.HEX); const zSquared = moduloPow(z,2,Consts.q); const zCubed = moduloPow(z,3,Consts.q); var t0 = modulo(modulo(zSquared,Consts.q).multiply(modulo(x1,Consts.q)),Consts.q); var t0Part1; var t0Part2; var t0Part3; var t1 = BigInteger(0); var t1Part1; var t1Part2; var t1Part3; var t1Part4; var t1Part5; var t1Part6; var t1Part7; var t1Part8; var t2 = BigInteger(0); var t2Part1; var t2Part2; var t2Part3; var yi = []; let s = 0; while(s< Consts.upperBoundNumBits){ yi[s] = moduloPow(y,s,Consts.q); t0Part1 = modulo(modulo(z,Consts.q).multiply(modulo(yi[s],Consts.q)),Consts.q); t0Part2 = modulo(modulo(zSquared,Consts.q).multiply(modulo(yi[s],Consts.q)),Consts.q); t0Part3 = modulo(modulo(zCubed,Consts.q).multiply(moduloPow(BigInteger(2),s,Consts.q)),Consts.q); t0 = moduloSubq(moduloSubq(moduloAddq(t0,t0Part1),t0Part2),t0Part3); //t0 = modulo(modulo(modulo(t0.add(t0Part1),Consts.q).subtract(t0Part2),Consts.q).subtract(t0Part3),Consts.q); //t0 = t0.add(z.multiply(yi[i]).add(zSquared.multiply(yi[i]).multiply(-1)).add(zCubed.multiply(BigInteger(2).pow(i)).multiply(-1))); t1Part1 = modulo(aR[s].add(z),Consts.q); t1Part2 = modulo(modulo(t1Part1,Consts.q).multiply(modulo(yi[s],Consts.q)),Consts.q); t1Part3 = modulo(modulo(SL[s],Consts.q).multiply(modulo(t1Part2,Consts.q)),Consts.q); t1Part4 = moduloSubq(aL[s],z); //t1Part4 = modulo(aL[i].subtract(z),Consts.q); t1Part5 = modulo(modulo(SR[s],Consts.q).multiply(modulo(yi[s],Consts.q)),Consts.q); t1Part6 = modulo(modulo(t1Part4,Consts.q).multiply(modulo(t1Part5,Consts.q)),Consts.q); t1Part7 = modulo(modulo(zSquared,Consts.q).multiply(moduloPow(BigInteger(2),s,Consts.q)),Consts.q); t1Part8 = moduloMulq(t1Part7,SL[s]); t1 = moduloAddq(moduloAddq(moduloAddq(t1,t1Part3),t1Part6),t1Part8); // t1 = modulo(modulo(t1.add(t1Part3),Consts.q).add(t1Part6),Consts.q); t2Part1 = modulo(modulo(SR[s],Consts.q).multiply(modulo(yi[s],Consts.q)),Consts.q); t2Part2 = modulo(modulo(SL[s],Consts.q).multiply(modulo(t2Part1,Consts.q)),Consts.q); t2 = modulo(t2.add(t2Part2),Consts.q); //t1 = t1.add((SL[i].multiply((aR[i].add(z)).multiply(yi[i]))).add((aL[i].subtract(z)).multiply(SR[i].add(yi[i])))); //t2 = t2.add(SL[i].multiply(SR[i].multiply(yi[i]))); s++; } const tau1 = pickRandom(Consts.q); const tau2 = pickRandom(Consts.q); const T1 = utils.ec.g.mul(t1.toString(Consts.HEX)).add(H.mul(tau1.toString(Consts.HEX))); const T2 = utils.ec.g.mul(t2.toString(Consts.HEX)).add(H.mul(tau2.toString(Consts.HEX))); //fiat shamir for verifier challenge: const concatStrings = T1.x.fromRed().toString(16).concat(T2.x.fromRed().toString(16)).concat(H.x.fromRed().toString(16)); const temp = crypto.createHash('sha256').update(concatStrings).digest('hex'); const xFiatShamirChall = modulo(BigInteger(temp,Consts.HEX),Consts.q); const xFiatShamirChallSquared = moduloPow(xFiatShamirChall, 2,Consts.q); //(A * B) mod C = (A mod C * B mod C) mod C const tauPart1 = modulo(modulo(tau1,Consts.q).multiply(modulo(xFiatShamirChall,Consts.q)),Consts.q); const tauPart2 = modulo(modulo(tau2,Consts.q).multiply(xFiatShamirChallSquared),Consts.q); const tauPart3 = modulo(modulo(zSquared,Consts.q).multiply(modulo(r1,Consts.q)),Consts.q); const tauX = modulo(modulo(tauPart1.add(tauPart2),Consts.q).add(tauPart3),Consts.q); const miuPart1 = modulo(modulo(rho,Consts.q).multiply(modulo(xFiatShamirChall,Consts.q)),Consts.q); const miu = modulo(alpha.add(miuPart1),Consts.q); var Lp = []; var LpPart1; var Rp = []; var RpPart1; var RpPart2; var RpPart3; var RpPart4; var tX = BigInteger(0); var tXPart1; var j = 0; while(j< Consts.upperBoundNumBits){ //(A + B) mod C = (A mod C + B mod C) mod C LpPart1 = modulo(modulo(SL[j],Consts.q).multiply(modulo(xFiatShamirChall,Consts.q)),Consts.q); //Lp[j] = modulo(modulo(aL[j].subtract(z),Consts.q).add(LpPart1),Consts.q); Lp[j] = moduloAddq(moduloSubq(aL[j],z),LpPart1); //Lp[j] = aL[j].subtract(z).add(SL[j].multiply(xFiatShamirChall)); RpPart1 = modulo(modulo(SR[j],Consts.q).multiply(modulo(xFiatShamirChall,Consts.q)),Consts.q); RpPart2 = modulo(modulo(zSquared,Consts.q).multiply(moduloPow(BigInteger(2),j,Consts.q)),Consts.q); RpPart3 = modulo(modulo(aR[j].add(z),Consts.q).add(RpPart1),Consts.q); RpPart4 = modulo(modulo(yi[j],Consts.q).multiply(modulo(RpPart3,Consts.q)),Consts.q); Rp[j] = modulo(RpPart4.add(RpPart2),Consts.q); //Rp[j] = (yi[j].multiply(aR[j].add(z).add(SR[j].multiply(xFiatShamirChall)))).add(zSquared.multiply(BigInteger(2).pow(j))); tXPart1 = modulo(modulo(Lp[j],Consts.q).multiply(modulo(Rp[j],Consts.q)),Consts.q); tX = modulo(tX.add(tXPart1),Consts.q); //tX = tX.add(Lp[j].multiply(Rp[j])); j++; } const transcript1 = tauX.toString(Consts.HEX).concat(miu.toString(Consts.HEX)).concat(tX.toString(Consts.HEX)); const NIchallenge1 = crypto.createHash('sha256').update(transcript1).digest('hex'); const nic1 = modulo(BigInteger(NIchallenge1,Consts.HEX),Consts.q); let k=0; var P = utils.ec.g.mul(nic1.toString(Consts.HEX)).mul(tX.toString(Consts.HEX)); //var P = utils.ec.g.mul(0); var hiTag = []; var yiInv = []; while(k=1){ L[j]= utils.ec.g.mul('0'); //init R[j]=utils.ec.g.mul('0'); //init cL=BigInteger(0); cR=BigInteger(0); i1=0; while (i1 var t0 = BigInteger(0); var t0Part1; var t0Part2; var t0Part3; let j = 0; while(j< Consts.upperBoundNumBits){ t0Part1 = modulo(modulo(z,Consts.q).multiply(modulo(yi[j],Consts.q)),Consts.q); t0Part2 = modulo(modulo(zSquared,Consts.q).multiply(modulo(yi[j],Consts.q)),Consts.q); t0Part3 = modulo(modulo(zCubed,Consts.q).multiply(moduloPow(BigInteger(2),j,Consts.q)),Consts.q); //t0 = modulo(modulo(modulo(t0.add(t0Part1),Consts.q).subtract(t0Part2),Consts.q).subtract(t0Part3),Consts.q); t0 = moduloSubq(moduloSubq(moduloAddq(t0,t0Part1),t0Part2),t0Part3); j++; } // fiat shamir challenge line 50 const concatStrings = T1.x.fromRed().toString(16).concat(T2.x.fromRed().toString(16)).concat(H.x.fromRed().toString(16)); const temp = crypto.createHash('sha256').update(concatStrings).digest('hex'); const xFiatShamirChall = modulo(BigInteger(temp,Consts.HEX),Consts.q); const xFiatShamirChallSquared = moduloPow(xFiatShamirChall,2,Consts.q); const eq63LeftSide = (utils.ec.g.mul(tX.toString(Consts.HEX))).add(H.mul(tauX.toString(Consts.HEX))); const eq63RightSide = (utils.ec.g.mul(t0.toString(Consts.HEX))).add(pedCom1.mul(zSquared.toString(Consts.HEX))).add(T1.mul(xFiatShamirChall.toString(Consts.HEX))).add(T2.mul(xFiatShamirChallSquared.toString(Consts.HEX))); if(eq63LeftSide.x.fromRed().toString(16)!=eq63RightSide.x.fromRed().toString(16)){result10=false;} if(eq63LeftSide.y.fromRed().toString(16)!=eq63RightSide.y.fromRed().toString(16)){result10=false;} //inner product proof: // P const transcript1 = tauX.toString(Consts.HEX).concat(miu.toString(Consts.HEX)).concat(tX.toString(Consts.HEX)); //33 const NIchallenge1 = crypto.createHash('sha256').update(transcript1).digest('hex'); const nic1 = BigInteger(NIchallenge1,Consts.HEX); //line 62 : var P = utils.ec.g.mul(nic1.toString(Consts.HEX)).mul(tX.toString(Consts.HEX)).add(H.mul(((Consts.q).subtract(miu)).toString(Consts.HEX))) P = P.add(A).add(S.mul(xFiatShamirChall.toString(Consts.HEX))); var hExponent = []; let k = 0; while(k< Consts.upperBoundNumBits){ hExponent[k] = moduloAddq(moduloMulq(z,yi[k]),moduloMulq(zSquared,moduloPow(BigInteger(2),k,Consts.q))); P = P.add(gVector[k].mul(((Consts.q).subtract(z)).toString(Consts.HEX))).add(hiTag[k].mul(hExponent[k].toString(Consts.HEX))); k++; } var Ptag = P; const nPad = Consts.upperBoundNumBits; var nTag = nPad/2; var i2; var transcript; var NIchallenge; var x; var xinv; var xSquare; var xSquareInv; var gVectorTag= gVector; var hVectorTag = hiTag; j = 0; while(nTag>=1){ transcript = L[j].x.fromRed().toString(16).concat(R[j].x.fromRed().toString(16)).concat(H.x.fromRed().toString(16)); NIchallenge = crypto.createHash('sha256').update(transcript).digest('hex'); x = BigInteger(NIchallenge,Consts.HEX); xinv = x.modInv(Consts.q); xSquare = moduloPow(x,2,Consts.q); xSquareInv = xSquare.modInv(Consts.q); gVector = gVectorTag; hiTag = hVectorTag; gVectorTag = []; hVectorTag = []; i2=0; while (i2 256){console.log("error: upper bound should be <256bits");return;} if(padSize>0){console.log("error: range works only for powers of 2 for now");return;} // const x1 = pickRandom(BigInteger(2).pow(Consts.upperBoundNumBits)); var args = process.argv; if (args.length>1) message=args[2]; const x1=BigInteger(message); const r0 = pickRandom(Consts.q); const r1 = pickRandom(Consts.q); const pedCom1 = utils.ec.g.mul(x1.toString(Consts.HEX)).add(utils.ec.g.mul((r0.multiply(r1)).toString(Consts.HEX))); const {A,S,T1,T2,tauX,miu,tX,L,R,aTag,bTag} = rangeBpProver(x1,pedCom1,r0,r1); const result10 = rangeBpVerifier(r0,r1,pedCom1,A,S,T1,T2,tauX,miu,tX,L,R,aTag,bTag); if(result10 == false){} //abort str="Value:"+message str+="\nBits:"+Consts.upperBoundNumBits str+="\nProof:"+result10 str+="\nR0: "+r0 str+="\nR1: "+r1 str+="\nPed com: "+pedCom1.x+", "+pedCom1.y str+=util.format("\n\nChallenge") str+=util.format("\nA: %s, %s",A.x,A.y) str+=util.format("\nS: %s, %s",S.x,S.y) str+=util.format("\nT1: %s, %s",T1.x,T1.y) str+=util.format("\nT2: %s, %s",T2.x,T2.y) str+=util.format("\nTaux: %s",tauX) str+=util.format("\nMiu: %s",miu) str+=util.format("\ntX: %s",tX) str+=util.format("\n\nIPP (Inner product proof)") str+=util.format("\naTag: %s",aTag) str+=util.format("\nbTag: %s",bTag) str+=util.format("\nL[0]: %s, %s",L[0].x,L[0].y) str+=util.format("\nR[0]: %s, %s",R[0].x,R[0].y) str+=util.format("\nL[1]: %s, %s",L[1].x,L[1].y) str+=util.format("\nR[1]: %s, %s",R[1].x,R[1].y) str=str.replace("<","lt;") str=str.replace(">","gt;") console.log(str) } controller() module.exports = { controller, };
A sample run is:
Value:128 Bits:4 Proof:false R0: 1.1824692793311763e+76 R1: 4.240133259900473e+76 Ped com: 68119130198504538834379955525603971000788069048233759713490825825127164003644, 51220078235203101089612418110015071369556315242440243843324708243413012612998 Challenge A: 19110614949710245228550808498917172492581441670020642335880570542435616991171, 55181656154658274394879974072341835840269121084776816307418531831181614870091 S: 38947793637093928990177204447428440964382703980081341002880063642615033973581, 77300232897177946139059592400965522391932419817312998429121737527765154039432 T1: 26045048044069343013032983046593652559227436982880673388370675918032934382434, 76207401378654274186219132229361043019705452538065285629759988631157399033452 T2: 109468214682091997854008174863163211059590584892653822904095070378332519331954, 86640221792101495033916998160947918274072598882693982709290319697020996801637 Taux: 21119936003448097665272896760812432647754321931748082711088720156058040909216 Miu: 97822483036319224835438138323726249524909899770368623230486794623484895043049 tX: 5019271808078520249764680465700420187244125916152676035299748521794749963872 IPP (Inner product proof) aTag: 17087222763525367134095279024575454796683881316217889813554465309658883096891 bTag: 52320303634529228557255981988194311411535018420318841517830916203824383831286 L[0]: 870247247096461317857281204741727870809401464519486453675744641503998033798, 74867421472366630988957423998594298310814602352853526219171288546210722596769 R[0]: 73699541622994332878408518052140832496122474448911758437576915353942946358965, 83042006817917134264618523365719861831989081804473271489580165742231885431392 L[1]: 106839663194368298929869973662228289115178670942910164077507081098607436710035, 87250207070619012527586431184627825171593886630974351027776838892470678015169 R[1]: 80647853534663966114520015568460799783557110565369836632642133131311559595699, 27942902794302065429418606801482870587705435059683822216637334447319326024563
The public parameters are [1]:
- l: cardinality of the subgroup of the elliptic curve used (Ed25519)
- N: bitsize of the elements whose range one wants to prove (N = 64)
- M: number of proofs to aggregate
- G: the base point of the subgroup of the elliptic curve used
- H: another generator of the subgroup of the elliptic curve used whose discrete log wrt G is not known and hard to find
- Gi: a list of M*N generators of the subgroup of the elliptic curve used whose discrete log wrt any other generator is not known and hard to find
- Hi: a list of M*N generators of the subgroup of the elliptic
The committed to values are [1]:
- v: the values to hide (and are in the range \(0 \le v_j \le 2^N\))
- gamma: hiding values
The bulletproof is [1]:
- V: a vector of curve points, Pedersen commitments to v[i] with hiding values gamma[i]
- A: a curve point, vector commitment to aL and aR with hiding value alpha
- S: a curve point, vector commitment to sL and sR with hiding value rho
- T1: a curve point, Pedersen commitment to t1 with hiding value tau1
- T2: a curve point, Pedersen commitment to t2 with hiding value tau2
- taux: a scalar, hiding value related to T1, T2, V and t
- mu: a scalar, hiding value related to A and S
- L: a vector of curve points of size log2(M*N) computed in the inner product protocol
- R: a vector of curve points of size log2(M*N) computed in the inner product protocol
- a: a scalar computed in the inner product protocol
- b: a scalar computed in the inner product protocol
- t: a scalar, inner product value to be verified