3

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

Related to: Proving that two points on elliptic curve are within range

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?

PeterMacGonagan
  • 31
  • 3

1 Answers1

1

Proving that $-z\leq x-y\leq z$ given $C=xG-yG=(x-y)G$ is the same as proving that $0\leq a<n$ 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.

knaccc
  • 4,732
  • 1
  • 16
  • 30
  • 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? – PeterMacGonagan Jul 01 '22 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. – knaccc Jul 01 '22 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. – PeterMacGonagan Jul 03 '22 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. – knaccc Jul 03 '22 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? – PeterMacGonagan Jul 04 '22 at 13:04
  • @PeterMacGonagan Computing $2^{64}$ EC points would be infeasible. I don't think you've understood what I've described. The point of splitting up $n$ into a small number of components is to make this an efficient proof. – knaccc Jul 04 '22 at 13:26
  • For simplicity, I'll take a much smaller number. If you set $n_{max}=2^{8}-1$ , it's possible to express each number between $1G$...$2^{8}G$ as the sum of $2^{i}$: $n=\sum_{i=0}^{7} \alpha_i ; 2{i}$. So, by example $84 = 0b1010100 = 4 + 16 + 64$ I can compute each $2^i= {1,2,4,...,128}$. In fact, with such small $n_{max}$, I could compute each number =${0,1,2,3,...255}$ – PeterMacGonagan Jul 05 '22 at 08:58
  • Suppose I've got a number $\gamma$, with 'your' method, can you explain what's the trick to know, if it's between $[0,255]$? From what I understand (or doesn't) is that I must compute each combinations of ${1,2,4,...128}$ and look for equality with $\gamma$... it doesn't seem to be very efficient. – PeterMacGonagan Jul 05 '22 at 08:58
  • Suppose $\gamma = 84 = 0b1010100 = 4 + 16 + 64$, could you explain 'your' method apply to this gamma? Could you do the same with, by example, $\gamma= 400 = 0b110010000=16+128+256$ ? This value is outside the interval $[0...2^{8}-1]$. So, it's not possible to represent it with our "components" $2^{i} = [1,2,...128]$ – PeterMacGonagan Jul 05 '22 at 09:02
  • @PeterMacGonagan If my EC point $P=84G$, and the max allowed value is 127, I first declare 7 Pedersen commitments, each of which I claim is to one of the powers of 2, or to the value zero. Then I provide a proof that the Pedersen commitments sum to my declared EC point $P$. Finally, I use ring signatures to prove that each of the 7 Pedersen commitments really were to either 0 or the correct power of 2. Now, the verifier knows for sure that $P$ cannot be $400G$, because there is no possible addition of those 7 powers of 2 that can get up to 400. – knaccc Jul 05 '22 at 14:18