using the library to test if a secret is within range

[pranavkirtani88]

Can I use the library to test if a secret is within range. for example age>18 etc.
if so how would I write such a code?

[omershlo]

Hi,
First of all - i strongly recommend to use Rust library and not js library. This library was written as a proof of concept and in terms of performance and security Rust is much much better. you can check out KZen bulletproof implementation: https://github.com/KZen-networks/bulletproofs and there are others as well (depend on what you try to achieve) .

About your question: to use bulletproof to show that a number x is within interval (a<x<b) given a commitment to x : the prover is doing a bulletproof for range b such that the verifier can check that the Pedersen commitment is to a number x<b . Then the verifier is computing a commitment to d = -(b-a) and add it to the original Pedersen commitment from the prover. The verifier sends the commitment and the opening of it to the prover that check its valid. The prover is doing another bulletproof for the new commitment showing that the committed value x + d is smaller than a.

I think this can be a nice addition to a library. The protocol is straight forward.

Would you like to give it a try yourself?
I suggest:

• move to KZen bulletproofs library
• you open an issue to make interface for js / wasm: we have a guy for that
• you open an issue with the above protocol (let me know if you want to give it a try yourself )

[pranavkirtani88]

Thanks @omershlo ,
I would love to try this by my self,I am new to bulletproofs and I am doing this as a part of Proof of concept as well.I am new to the area of ZKP. is there any code i can reuse to do the commitment from the verifier side for calculating d and then to send x+d from the prover to verifier

[pranavkirtani88]

It would be better if you add the feature to this library.

[omershlo]

sure,
I have a code for pedersen commitment : https://github.com/KZen-networks/curv/blob/master/src/cryptographic_primitives/commitments/pedersen_commitment.rs

I have no problem take it but be aware that do to time constraints it will take some time (super busy at the moment). If this is a PoC I strongly encourage you to give it a go (I will review), Rust is much better suited for bulletproof and cryptography in general and the library in KZen repo will allow you to do it very easily.
In any case - please open issues in https://github.com/KZen-networks/bulletproofs :)

[pranavkirtani88]

Thanks @omershlo
I will give it a shot while you are adding the feature

[omershlo]

Hi,
about the protocol - this can actually be done non interactively with only one range proof:

1. prover commits to a values a<x<b
2. prover generates a pedersen commitment to a value a
3. prover generates a range proof to commitment that is commitment from 1 minus commitment from 2
4. prover sends range proof together with the opening of the commitment from 2

[pranavkirtani88]

Hi @omershlo ,

So how would this look?
for example step1:
Currently the following line of code is used in the library

const pedCom1 = utils.ec.g.mul(x1.toString(Consts.HEX)).add(utils.ec.g.mul((r0.multiply(r1)).toString(Consts.HEX)));

How do I modify this to achieve the above steps?

[pranavkirtani88]

Does this look correct?
const x1 = turnToBig(3) // turns number to bigInt
const start=turnToBig(2) //start is a
console.log(x1)
const r0 = pickRandom(Consts.q);
const r1 = pickRandom(Consts.q);
//to prove a<x<b
//1. prover commits to a values a<x<b
const pedCom1 = utils.ec.g.mul(x1.toString(Consts.HEX)).add(utils.ec.g.mul((r0.multiply(r1)).toString(Consts.HEX)));
console.log("pedCom1",pedCom1)
///PedersenCommitment
//2. prover generates a pedersen commitment to a value a
const pedComOfa = utils.ec.g.mul(start.toString(Consts.HEX)).add(utils.ec.g.mul((r0.multiply(r1)).toString(Consts.HEX)));
//3. prover generates a range proof to commitment that is commitment from 1 minus commitment from 2

const {A,S,T1,T2,tauX,miu,tX,L,R,aTag,bTag} = rangeBpProver(x1,pedCom1.subtract(pedComOfa),r0,r1);
//4. prover sends range proof together with the opening of the commitment from 2

const result10 = rangeBpVerifier(r0,r1,pedCom1.subtract(pedComOfa),A,S,T1,T2,tauX,miu,tX,L,R,aTag,bTag);

[omershlo]

I think you got the general idea. pay attention that this library and in general bulletproofs will work for powers of 2. see my protocol in ZenGo-X/bulletproofs#16.
It is possible of course to use it for any interval but it will cost a few more range proofs (unless there is some black magic that we can think of to reduce the number of range proofs)

[pranavkirtani88]

Hi @omershlo ,
Here is what I have added , let me know if this looks correct. I added a function turnToBig which turns number to BigInteger

I am simply taking difference between number and start point and then calculate proof for that.

const x1 = turnToBig(6)
const start=turnToBig(4)
const r0 = pickRandom(Consts.q);
const r1 = pickRandom(Consts.q);
const difference=x1.subtract(start);
const pedCom1 =utils.ec.g.mul(difference.toString(Consts.HEX)).add(utils.ec.g.mul((r0.multiply(r1)).toString(Consts.HEX)));

var {A,S,T1,T2,tauX,miu,tX,L,R,aTag,bTag} = rangeBpProver(difference,pedCom1,r0,r1);
const result10 = rangeBpVerifier(r0,r1,pedCom1,A,S,T1,T2,tauX,miu,tX,L,R,aTag,bTag);

[omershlo]

two comments:

1. you need to write the verification part as well. when you do you will notice that you should convince the verifier that pedcom1 is a commitment to x1 minus commitment to start. that's easy to do. follow the steps in add interface for zero knowledge interval proof ZenGo-X/bulletproofs#16
2. To make the range proof work you should make the start and end value one of the following (2,4,8,16,32,64,128,256) [a power of 2]

[pranavkirtani88]

How do you achieve subtraction of commitments?
pedCom1 is a EC point . do I just subtract EC points of the two commitments?

[omershlo]

exactly. but you need to send the verifier both commitment and the opening of the commitment to the start value so that he can make sure you did not cheat with the subtraction

[pranavkirtani88]

This is what I got so far, But the proof is failing. is it because of the wrong random values?

const x1 = turnToBig(4)
const start=turnToBig(2)
const r0 = pickRandom(Consts.q);
const r1 = pickRandom(Consts.q);
const r2 = pickRandom(Consts.q);
const r3 = pickRandom(Consts.q);
const difference=x1.subtract(start);
const zero=BigInteger(0);
// prover proves that they have x1
const pedCom1 =utils.ec.g.mul(x1.toString(Consts.HEX)).add(utils.ec.g.mul((r0.multiply(r1)).toString(Consts.HEX)));

// prover will generate a commitment of start
const pedComstart=utils.ec.g.mul(start.toString(Consts.HEX)).add(utils.ec.g.mul((r0.multiply(r1)).toString(Consts.HEX)));

//prover subtracts second commitment from first
const negCom=pedComstart.neg(pedComstart)
const pedComDiff=pedCom1.add(negCom);

var {A,S,T1,T2,tauX,miu,tX,L,R,aTag,bTag} = rangeBpProver(difference,pedComDiff,r0,r1);
const result10 = rangeBpVerifier(r0,r1,pedComDiff,A,S,T1,T2,tauX,miu,tX,L,R,aTag,bTag);

if(result10 == false){} //abort
console.log(result10)

[pranavkirtani88]

ok, Finally got it, Took a bit of math to do it. here is algorithm to what I did

pedcom1= gx+g(r2r3)
pedcomstart= ga +g*(r0r1)
pedcomdiff= g(x-a) +g*((r2-r0)(r3-r1))
g(x-a) +g*((r2-r0)(r3-r1))
gx-ga +g(r2r3-r2r1-r0r3+r0r1)
gx -ga + g*(r2r3)-g(r2r1)- g(r0r3) +g(r0*r1)

gx+g(r2r3)-ga+g*(r0r1)-g(r2r1)-g(r0r3)
gx+g*(r2r3)-ga+g*(r0r1)-(g(r2r1)+g(r0*r3))

pedcom1-ga+g(r0r1)-(g(r2r1)+g(r0*r3))

The Prover only sends the peddersen commitment for x1 and the random values he used.

The verifier does the rest of the calculation based on the above formula

This works I tested it

Raised a pull request with the code

[omershlo]

your alg looks good overall. few comments:

1. why you are using two random values in a pedersen com? why not define r_x = r2r3 and r_a = r0r1 ?
2. The prover should send the com to x as you mentioned and only the random value he used for the com to a (just to make sure you don't send to randomness r_x).
3. the range proof should be for range b-a (just make sure this is indeed the case).

I will check your pr after you answer this points :)

[pranavkirtani88]

1. why you are using two random values in a pedersen com? why not define r_x = r2r3 and r_a = r0r1 ?
   ------ Actually r2 and r3 are random values used for the first pedcom using x and sent to verifier along with pedom, the second pedcom is calculated by verifier using r0 and r1 which are verifier random values and the formula ga+g(r0r1)-(g(r2r1)+g(r0*r3)) . since we are subtracting the second pedcom from first we also subtract r2 from r0 and r3 from r1.

Followed the steps mentioned on stackoverflow question I posted
https://crypto.stackexchange.com/questions/67504/subtracting-one-pederssen-commitment-from-another

2. The prover should send the com to x as you mentioned and only the random value he used for the com to a (just to make sure you don't send to randomness r_x).
   ------Refer to answer for 1

3. the range proof should be for range b-a (just make sure this is indeed the case).
   -----I noticed that it was not working for x<b.This has been fixed and added to PR. This involves a second proof generated by prover to prove that x<b

[omershlo]

regarding point 3: one range proof is enough. after all the subtractions the prover suppose to have one pedcom for value x-a and then the range proof suppose to be for range b-a. that's it.

[pranavkirtani]

The problem with that is b-a needs to be to the power of 2. which really limits it. for example if I want to calculate number between 16 and 64 . both start and end are to the power of 2, this can be implemented easily with the current PR. however 64-16 becomes 48. which is not a number to the power of 2.
Therefore I had to write a separate proof for x<b.

[omershlo]

I see. I thought that b-a be a power of two is the only condition.
how do you solve it if that's not the case? one range proof shows that x<b , how do you make sure that x>a ? you send another proof that x-a is smaller than b and use the fact that this shows that x-a > 0 ?

[pranavkirtani]

Well,I follow the below steps:

1. prover send pedcom for x, with random values r2 and r3.
2. verifier calculates (x-a) pedcom . using the algorith shown above.
   subtracted_pedcom=pedcom1-ga+g(r0r1)-(g(r2r1)+g(r0r3))
   This is effectively pedom of x minus pecom of a
3. verifier sends this subtracted_pedcom back to prover. prover generates a proof that shows x>a
4. prover also generates a separate proof for x<b and sends to verifier with the opening
5. the verifier verifies both the proofs.

[omershlo]

sounds right (up to the point of using too much randomness we discussed and making it non interactive). But we are in the world of proof of concept and what you are doing is working and its secure. I will merge :)

[pranavkirtani]

Great! , should I close this issue?