3
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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? $\endgroup$
    – PeterMacGonagan
    Jul 1, 2022 at 16:33
  • $\begingroup$ @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. $\endgroup$
    – knaccc
    Jul 1, 2022 at 21:26
  • $\begingroup$ 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. $\endgroup$
    – PeterMacGonagan
    Jul 3, 2022 at 12:40
  • $\begingroup$ @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. $\endgroup$
    – knaccc
    Jul 3, 2022 at 17:10
  • $\begingroup$ 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? $\endgroup$
    – PeterMacGonagan
    Jul 4, 2022 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.