Allow verification with coefficients > p

[fleupold]

The following program currently does not allow verifier setup:

#include <stdint.h>

struct In { int in; };
struct Out { int out; };

void compute(struct In *input, struct Out *output){
    int pow = 1;
    int index;
    for (index = 0; index < 256; index++) {
        pow = pow * 2;
    }
    output->out = pow;
}

/pepper_compile_and_setup_V.sh fails with the following error:

pepper_verifier_overflow: ../thirdparty/libsnark/depends/libff/libff/algebra/fields/bigint.tcc:55: libff::bigint<n>::bigint(const __mpz_struct*) [with long int n = 4l]: Assertion `((k)->_mp_size < 0 ? -1 : (k)->_mp_size > 0) == 0' failed.
./pepper_compile_and_setup_V.sh: line 35: 68344 Aborted                 bin/pepper_verifier_$1 setup $2 $3

The assertion fails when we try to instantiate the FieldT coefficients during libsnark constraint system creation pepper_verifier.cpp. The coefficients are read into mpz_t variables from the .qap file and are as such not bound. However field elements in libsnark have to be numbers mod p.

In the program above pow becomes 2^256 and thus larger than p (~2^254). In order for the program to compile, we need to take the coefficients modulo p before turning them into field elements.

The use case I'm needing this for is computing the integer representation of a 256bit array (sha256 output). I'm using a similar loop as the one above. The result will be checked against a public input using assert_zero(sumOfBit - input->hash).

Maybe it's worth printing a warning to let the user know they are overflowing p. Yet, libsnark will implicitly do all calculations mod p without warning the user (so I'm not sure if this is needed for constants/coefficiants).

I also adjusted the indentation in the file and added brackets around all if/else statements (having one line if statements without brackets is very prone to errors when commenting out a line or adding code in a hurry, e.g. Apple’s TLS bug).

[maxhowald]

I'll merge this, since it seems to be consistent with what libsnark does, but as you seem to have guessed, this may produce unexpected output at times.

In the example you gave, 2^256 is the expected output, but 2^256 mod p (or 2^256 plus any multiple of p) will also cause the verifier to accept.

Adding the assert_zero() checks sounds like a good way to work around this for your application, but that might not be possible in all cases.

A warning or error from the compiler is a good idea, but it would require the compiler to know the field size p. In theory, the compilation to constraints is independent of this value. Perhaps the right place for this warning is actually in pepper_verifier.cpp somewhere. For example, warn if the reduction modulo p you have added actually changes the value passed to libsnark.

[fleupold]

Yes that’s a good idea. Let me add a warning there, before you merge.

_{Sent with GitHawk}