scipr-lab / libsnark

C++ library for zkSNARKs
Other
1.81k stars 572 forks source link

"Verifier" and "affine verifier" give different results for groth snark #109

Open imeckler opened 6 years ago

imeckler commented 6 years ago

In short, r1cs_gg_ppzksnark_affine_verifier_weak_IC and r1cs_gg_ppzksnark_online_verifier_weak_IC do not agree with each other.

How to reproduce

The easiest way to see this is to edit zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark/tests/test_r1cs_gg_ppzksnark.cpp to use mnt6 as follows.

#include <cassert>
#include <cstdio>

#include <libff/common/profiling.hpp>
#include <libff/common/utils.hpp>

#include <libff/algebra/curves/mnt/mnt4/mnt4_pp.hpp>
#include <libff/algebra/curves/mnt/mnt6/mnt6_pp.hpp>

#include <libsnark/common/default_types/r1cs_gg_ppzksnark_pp.hpp>
#include <libsnark/relations/constraint_satisfaction_problems/r1cs/examples/r1cs_examples.hpp>
#include <libsnark/zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark/examples/run_r1cs_gg_ppzksnark.hpp>

using namespace libsnark;

template<typename ppT>
void test_r1cs_gg_ppzksnark(size_t num_constraints,
                         size_t input_size)
{
    libff::print_header("(enter) Test R1CS GG-ppzkSNARK");

    const bool test_serialization = true;
    r1cs_example<libff::Fr<ppT> > example = generate_r1cs_example_with_field_input<libff::Fr<ppT> >(num_constraints, input_size);
    const bool bit = run_r1cs_gg_ppzksnark<ppT>(example, test_serialization);
    assert(bit);

    libff::print_header("(leave) Test R1CS GG-ppzkSNARK");
}

int main()
{
    libff::mnt6_pp::init_public_params();
    libff::start_profiling();

    test_r1cs_gg_ppzksnark<libff::mnt6_pp>(1000, 100);
}

I couldn't figure out how to turn assertions on so I also edited test_affine_verifier in zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark/examples/run_r1cs_gg_ppzksnark.tcc to print out the two results, and indeed they disagree.

test_affine_verifier(const r1cs_gg_ppzksnark_verification_key<ppT> &vk,
                     const r1cs_gg_ppzksnark_primary_input<ppT> &primary_input,
                     const r1cs_gg_ppzksnark_proof<ppT> &proof,
                     const bool expected_answer)
{
    libff::print_header("R1CS GG-ppzkSNARK Affine Verifier");
    const bool answer = r1cs_gg_ppzksnark_affine_verifier_weak_IC<ppT>(vk, primary_input, proof);
    printf("answer = %d, expected_answer = %d\n", answer, expected_answer);
    assert(answer == expected_answer);
}

A clue as to what's going on

I had the two verifiers print out the QAP value (which they check against gamma_ABC_g from the verification key). The two are inverse to each other:

r1cs_gg_ppzksnark_affine_verifier_weak_IC

QAP
c0/c1:
c0/c1/c2:
213077754533926158863536625239923388455486701487823975577622739473855729857419121898678281
263665482303626436607844819755284215630116336514836821792876463828315141713955789127815997
56908332736912441542181392477909075490303219678104456268910727801248029873968978442699817
c0/c1/c2:
433125277222172647228195794413172024784015775736623220223706725018030874628074313024434793
410726939046464025021866266004641445353517670530300776607301657096842210030370595020527809
323242293655770957175007285897503042084840550240134706560282994865337636962437038304621604

r1cs_gg_ppzksnark_online_verifier_weak_IC:

QAP
c0/c1:
c0/c1/c2:
213077754533926158863536625239923388455486701487823975577622739473855729857419121898678281
263665482303626436607844819755284215630116336514836821792876463828315141713955789127815997
56908332736912441542181392477909075490303219678104456268910727801248029873968978442699817
c0/c1/c2:
42797008947088678525153455239876426761109102816200295329561010721133772679334177535528344
65195347122797300731482983648407006191607208022522738945966078642322437277037895539435328
152679992513490368578341963755545409460284328312688808992984740873827010344971452255341533

You can see that the affine result's c1 is minus 1 times the regular verifier's result's c1, which since these values are unitary means they are inverse. So, it seems something is getting inverted somewhere it shouldn't be.