search

gnosis / dex-zksnarks

Code to generate snark proofs for batch auction result validation of the Gnosis d.exchange
46 stars 7 forks source link

Implement is negative using bitwise comparison #37

Closed fleupold closed 5 years ago

fleupold commented 5 years ago

https://travis-ci.org/gnosis/dex-zksnarks/builds/473875064 shows a lot of warnings about Coefficient larger than prime and change references on a polynomial. It turns out that these warnings are coming from the isNegative is implemented inside pepper.

Long term, we probably want to create a gadget for it (#36), but for the short term we can implement a bit wise comparison with p-1/2 in pepper.

josojo commented 5 years ago

Are you sure this is correct? Why is it to sufficient if we check that the input is smaller than the prime element?

Imagine we have 4 bits ( numbers 0-15) and we do mod 11 calculations. Then we calculate bitwise: 0-10 =0000-1010 = 0110 < 11=p-1/2, but still acutally 0-10 is negative.

josojo commented 5 years ago

I tried the following:

bool result, found = 0;
    for(index = 0; index < 254; index++) {
         if( (maxPositiveFieldBits[index] - fieldBits[index] == 1 && found !=1 ) {
            // maxPositiveField > field -> not negative
            found = 1;
        } else if (maxPositiveFieldBits[index] - fieldBits[index] != 0  && found !=1) {
            // maxPositiveField < field -> negative
            result = 1;
            found = 1;
        }
    }

but it gives in the e2etest exactly the same amout of constraints ...

Let's optimize these things later...