# ECC Range proof

In ECC, the proof showing that given $$G$$, $$x$$ and $$y$$ is in the range $$[-z,z]$$ is known as the range proof.

So, if: $$H=xG−yG$$ it is possible to prove that $$x−y$$ is in the range $$[−z,z]$$.

Could you explain how to apply this theory? Do you have a reference, please?

Is z fixed by the method or is it configurable?

Proving that $$-z\leq x-y\leq z$$ given $$C=xG-yG=(x-y)G$$ is the same as proving that $$0\leq a where $$a=z + x - y$$ and $$n=2z+1$$ given $$C'= aG = C + zG$$.

$$C'$$ can be considered a Pedersen commitment of the form $$aG+bH$$, except that there is no blinding factor $$b$$ set.

To prove that $$C'$$ is a Pedersen commitment to a value $$a$$ less than $$n$$, first you need to generate a number of components, a selection of which together can sum to any natural number less than $$n$$, but cannot sum to any value equalling or exceeding $$n$$. See this answer for a method.

Then you create a Pedersen commitment for each of those components, and demonstrate that the Pedersen commitment $$C'$$ is constructed as the addition of some selection of those component Pedersen commitments. To see how, see this answer.

• Thank you for your answer. I've understood the firs step: How to split a natural number x into components? I didn't understand very well the second step: especially the bullet proofs. Is it a brute force approach? Jul 1 at 16:33
• @PeterMacGonagan I don't know what you mean by brute force. Let's say you are proving a commitment is to a value less than 8, and you have components 1,2,4. When you declare each Pedersen commitment for each component, the commitment is blinded. But you use a ring signature to prove the first commitment is either to 0 or to 1. Then another ring signature to prove the second commitment is either to 0 or 2. Then another to prove the third commitment is to 0 or 4. Then the sum of these commitment can't equal or exceed 8. Search for "Borromean Ring Signature" to see how they are implemented. Jul 1 at 21:26
• Ok, I read the reference about Borromean Ring Signature and I think I understand how it works. I had misunderstood what range proof was for. My apologies. I thought that it was possible thanks to this theory to know if a point of an elliptic curve was included in a certain interval like for example between 1G and 2^64G. or even to know if a point was negative. But I think that it is not possible to know this information. Jul 3 at 12:40
• @PeterMacGonagan since $1-2^{64}$ is just about within the realm of where you would worry about the multiple of $G$ being brute-forced, normally you'd use a Pedersen commitment to represent the value so that the value is not brute-forceable. You can use the method I've discussed to prove that a curve point is between $1G$ and $2^{64}G$, but you would need to know the multiple of G prior to using a range proof to prove it is within the range. Jul 3 at 17:10
• If I understand correctly: we just compute $1G$ to $2^{64}G$ elliptic points and we just compare our elliptic point with theses values to know if we are in this interval or is there a trick that I don't see? Jul 4 at 13:04