celo-org / celo-bls-snark-rs

Implements SNARK-friendly BLS signatures
https://celo.org
Apache License 2.0
84 stars 21 forks source link

Point compression logic in G2 is wrong #149

Closed kobigurk closed 4 years ago

kobigurk commented 4 years ago

Currently, we do:

half = (p-1)/2
c1 > half => 1
c1 == half && c0 > half => 1
else 0

This is wrong - for y = c1*u + c0, -y is -c1*u - c0. The only situation where c1 == -c1 is when c1=0, not when c1=half, and so the logic should be changed to:

half = (p-1)/2
c1 > half => 1
c1 == 0 && c0 > half => 1
else 0

This is equivalent to the upstream logic of checking y > -y:

y = c1*u + c0
-y = -c1*u - c0

c1 > -c1 => 1
c1 == -c1 && c0 > -c0 => 1
else 0

It's equivalent since for any element in the field f > -f <=> f > half. This is because the numbers in the field are arranged as such:

half = (p-1)/2
c1 > -c1 <=> c1 > half, so all the numbers of [half+1, 2*half] satisfy that
c1 = 0 <=> c1 == -c1, because it has to satisfy 2*c1 == 0 (mod p), which can only happen for c1 == 0`, and then c0 > -c0 is equivalent to c0 > half for the same reasons.