scipr-lab / libsnark Goto Github PK

Hi,

I'm currently digging through libsnark with ASan enabled, and I might have found a stack-buffer-overflow in libsnark::SHA512_rng triggered by various test-cases.

undefined behaviour:

src/common/rng.tcc:53:13: runtime error: load of address 0x7fd2a506d488 with insufficient space for an object of type 'mp_limb_t'
0x7fd2a506d488: note: pointer points here
 b9 54 ea a1  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00
              ^
=================================================================

stack-bo:

=================================================================
==7314==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffee90be1a8 at pc 0x0000005a7cfb bp 0x7ffee90be0a0 sp 0x7ffee90be098
READ of size 8 at 0x7ffee90be1a8 thread T0
    #0 0x5a7cfa in libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> libsnark::SHA512_rng<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >(unsigned long) src/common/rng.tcc:53
    #1 0x410f98 in libsnark::knapsack_CRH_with_field_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::sample_randomness(unsigned long) src/gadgetlib1/gadgets/hashes/knapsack/knapsack_gadget.tcc:132
    #2 0x6dcce5 in libsnark::knapsack_CRH_with_field_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::sample_randomness(unsigned long) /usr/include/c++/5/bits/stl_bvector.h:830
    #3 0x6dcce5 in libsnark::knapsack_CRH_with_field_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::get_hash(std::vector<bool, std::allocator<bool> > const&) src/gadgetlib1/gadgets/hashes/knapsack/knapsack_gadget.tcc:98
    #4 0x7176a1 in libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::get_hash(std::vector<bool, std::allocator<bool> > const&) src/gadgetlib1/gadgets/hashes/knapsack/knapsack_gadget.tcc:208
    #5 0x718b8c in libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::hash_value_type libsnark::two_to_one_CRH<libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> > >(libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::hash_value_type const&, libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::hash_value_type const&) src/common/data_structures/merkle_tree.tcc:36
    #6 0x7198fd in libsnark::merkle_tree<libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> > >::merkle_tree(unsigned long, unsigned long) src/common/data_structures/merkle_tree.tcc:53
    #7 0x71bd0f in libsnark::set_commitment_accumulator<libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> > >::set_commitment_accumulator(unsigned long, unsigned long) src/common/data_structures/set_commitment.tcc:24
    #8 0xb3b218 in libsnark::r1cs_mp_ppzkpcd_keypair<libsnark::default_r1cs_ppzkpcd_pp> libsnark::r1cs_mp_ppzkpcd_generator<libsnark::default_r1cs_ppzkpcd_pp>(std::vector<libsnark::r1cs_pcd_compliance_predicate<libsnark::default_r1cs_ppzkpcd_pp::curve_A_pp::Fp_type>, std::allocator<libsnark::r1cs_pcd_compliance_predicate<libsnark::default_r1cs_ppzkpcd_pp::curve_A_pp::Fp_type> > > const&) src/zk_proof_systems/pcd/r1cs_pcd/r1cs_mp_ppzkpcd/r1cs_mp_ppzkpcd.tcc:240
    #9 0xb42768 in bool libsnark::run_r1cs_mp_ppzkpcd_tally_example<libsnark::default_r1cs_ppzkpcd_pp>(unsigned long, unsigned long, unsigned long, bool, bool, bool) src/zk_proof_systems/pcd/r1cs_pcd/r1cs_mp_ppzkpcd/examples/run_r1cs_mp_ppzkpcd.tcc:113
    #10 0xb53e10 in void test_tally<libsnark::default_r1cs_ppzkpcd_pp>(unsigned long, unsigned long, bool, bool) src/zk_proof_systems/pcd/r1cs_pcd/r1cs_mp_ppzkpcd/tests/test_r1cs_mp_ppzkpcd.cpp:18
    #11 0x406fa0 in main src/zk_proof_systems/pcd/r1cs_pcd/r1cs_mp_ppzkpcd/tests/test_r1cs_mp_ppzkpcd.cpp:30
    #12 0x7f77f982460f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2060f)
    #13 0x40ecc8 in _start (/home/daniel/code/git/libsnark/src/zk_proof_systems/pcd/r1cs_pcd/r1cs_mp_ppzkpcd/tests/test_r1cs_mp_ppzkpcd+0x40ecc8)

Address 0x7ffee90be1a8 is located in stack of thread T0 at offset 136 in frame
    #0 0x5a775f in libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> libsnark::SHA512_rng<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >(unsigned long) src/common/rng.tcc:22

  This frame has 4 object(s):
    [32, 40) 'iter'
    [96, 136) 'rval' <== Memory access at offset 136 overflows this variable
    [192, 256) 'hash'
    [288, 504) 'sha512'
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow src/common/rng.tcc:53 libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> libsnark::SHA512_rng<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >(unsigned long)
Shadow bytes around the buggy address:
  0x10005d20fbe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005d20fbf0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005d20fc00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005d20fc10: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005d20fc20: 00 00 00 00 f1 f1 f1 f1 00 f4 f4 f4 f2 f2 f2 f2
=>0x10005d20fc30: 00 00 00 00 00[f4]f4 f4 f2 f2 f2 f2 00 00 00 00
  0x10005d20fc40: 00 00 00 00 f2 f2 f2 f2 00 00 00 00 00 00 00 00
  0x10005d20fc50: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005d20fc60: 00 00 00 f4 f3 f3 f3 f3 00 00 00 00 00 00 00 00
  0x10005d20fc70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005d20fc80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
==7314==ABORTING

edit 2016/04/11: updated to human readable filenames and line numbers

Currently libsnark makes generous use of assert()s.

Any abnormal condition that may be triggered by bad external inputs should cause an (informative) exception, not an assert.

Likewise for abnormal conditions that can be triggered by violation of supposed invariants/preconditions/postconditions within the libsnark code, if those cannot be convincingly argued and maintained.

Because of their catastrophic failure mode, we should use assertions only for invariants/preconditions/postconditions that we can convincingly argued will always hold and be maintained.

(Common wisdom also says assertions should be used when the check is expensive, because they can be removed in release mode. But in practice, it seems everybody is being conservative and uses libsnark with assertions enabled.)

Tasks:

1. Decide on an assert convention (typing, information strings, etc.)
2. Convert asserts to throws, by the above guideline
3. Make sure our code is exception-safe in the superficial sense of memory leaks, locks etc.
4. Analyze and document how exception-safe are different classes, in terms of semantics (e.g., for an object of class foo, if one of its method raised an exception, is it safe to continue using it?)
5. In pertinent high-level functions (e.g., main()), add a default exception handler that informatively displays caught exceptions and aborts.

1+5 should make sure we don't lose valuable debug information (what's the error? what's the stacktrace?) compared to the current assertions.

One complication is the OpenMP parallelized loops. What's the right way to handle exceptions in these?
We can do a catch within the parallelized loop, store the exception info into variables, skip the payload of remaining iterations via continue, and when out of the loop - throw a new exception (losing type info...). That's tricky and tedious. Ditto for critical sections. Any better patterns?

I don't see why it needs one, a vector should be fine.

I would like to package libsnark for debian. But for that I need to package the dependencies as well.
Now what is the story behind "ate-pairing-change-curve.diff" ?
Could this change be pushed to upstream so that they can include it into a new release of ate-pairing?
That would be my preferred solution anyway.

at line 21, the include path hasn't been updated. The tcc file is at "gadgetlib1/examples/simple_example.tcc".

(bn128 again) If you attempt e(P, Q) where P or Q are points at infinity, an internal assumption (during the miller loop if I remember correctly) that the points are in the affine is violated, causing an assertion later. We should expect the pairing to return Fp12::one().

Libsnark currently uses long long and unsigned long long in many places. On native Windows build, these are 32-bit types (even on 64-bit Windows), which breaks compatibility (#26) and in some cases correctness (e.g., #13).

Convert all of these to C++11 fixed-width integer types: int64_t and uint64_t.

Except where they should be size_t instead (e.g., zcash/zcash#1240).

(Ongoing work by @radix42 and @joshuayabut.)

This should at least be documented. If it boolean constraints its outputs (either intentionally or accidentally) then this helps downstream users avoid unnecessary bitness constraints.

Libsnark should be used as a proper library, by doing make install and having applications use their own makefiles and link against libsnark.so (or libsnark.a).

But the bundled binaries are all built in-tree against the individual .o files, by the monolithic Makefile. Several users followed this example and developed their applications by modifying the libsnark src tree, which created a mess when rebasing to new upstream libsnark.

README.md now offers some (laconic) hints about using libsnark as proper library, but still no full example.

So, we should give a full example of an application that compiles outside src and properly links against libsnark.so. We should also give a recipe for moving existing code out of the source tree, if users want to use it as a template. Ideally this would consist just of copying the files and adding a boilerplate Makefile.

The user may want to synthesize the constraint system and pass it to the r1cs proving routines, instead of serializing the constraint system into the proving key, which leads to both higher disk usage and memory usage when it is loaded into memory.

zerocash_pour_ppzksnark/profiling/profile_zerocash_pour_gadget
and
zerocash_pour_ppzksnark/tests/test_zerocash_pour_ppzksnark

Where can I find missing libff on Ubuntu. It's hard to figure out from the code what is this library about...

Currently we have a bunch of #define flags fed by the makefile as g++ -D... arguments during the build. But after we build a library file (libsnark.a or libsnark.so), the information on choice of flags is lost. Later, if a user compiling against the libsnark library happens to use different flags, all bets are off. This is especially bad because some of our code is in .c files (so affeceted by the flags when compiling libsnark), and other is in .tcc files (so affected by the flags when compiling the user's app).

Let's save the flags into a libsnark_config.h file and #include it from all pertinent places in libsnark, instead of passing g++ -D arguments. Then, make install can then install it with the rest of the headers.

#include <common/default_types/ec_pp.hpp>
int main() {
    libsnark::Fr<default_ec_pp>::random_element(); //segfault
    return 0;

(The Makefile I used to compile the above is here: https://github.com/benma/libsnark/blob/6be0121cbeedefc2bffd4b89e7ef268a7da90efe/link_example/Makefile)

I have a very simple zkSNARK circuit here: https://github.com/ebfull/lightning_circuit

Doing a simple ./get-libsnark && make && ./test should suffice.

It works just fine and passes my test suite with ALT_BN128. However, if you change to BN128 (in the Makefile) it fails during verification. The proofs appear to generate fine though. (Obviously if the proofs are generated wrong it would explain why they fail same-coefficient checks.)

g++ -o src/gadgetlib2/variable.o   src/gadgetlib2/variable.cpp -c -MMD -std=c++11 -Wall -Wextra -Wno-unused-parameter -Wno-comment -Wfatal-errors -O2 -march=native -mtune=native -DUSE_ASM -DMONTGOMERY_OUTPUT -DCURVE_BN128 -Idepinst/include -Isrc -DBN_SUPPORT_SNARK -DNO_PROCPS -static -DSTATIC
src/gadgetlib2/variable.cpp: In member function ‘int gadgetlib2::FElem::getBit(unsigned int, const gadgetlib2::FieldType&)’:
src/gadgetlib2/variable.cpp:120:1: warning: control reaches end of non-void function [-Wreturn-type]
 }

The [https://github.com/scipr-lab/libsnark/blob/master/src/gadgetlib2/variable.cpp#L115](relevant code) is:

int FElem::getBit(unsigned int i, const FieldType& fieldType) {
    promoteToFieldType(fieldType);
    if (this->fieldType() == fieldType) {
        return elem_->getBit(i);
    }
}

The warning is correct: if this->fieldType() != fieldType then the behaviour is undefined. If this should be an assertion, make it one.

src/relations/variable.tcc:485:92: note: no known conversion for argument 1 from ‘const libsnark::linear_term<libsnark::Fp_model<4l, ((const libsnark::bigint<4l>&)(& libsnark::bn128_modulus_r))> >’ to ‘libsnark::linear_term<libsnark::Fp_model<4l, ((const libsnark::bigint<4l>&)(& libsnark::bn128_modulus_r))> >&’

Since the used curves are not designed to have a secure twist, and in any case the SNARK protocol has only (as far as I can see) been analysed under the assumption that all points are on the relevant curves, I strongly suspect that this is necessary for security.

For example:

alt_bn128_G1 alt_bn128_G1::operator-() const
{
    return alt_bn128_G1(this->X, -(this->Y), this->Z);
}

-G1::zero() thus has an invalid jacobian representation. I doubt any code outside of this will be reading Y without running to_affine_coordinates first (which overwrites the invalid Y coordinate) so this probably won't manifest as a bug elsewhere.

prepare-depends.sh will not work behind a corporate/school network due to the method of pulling projects via "git" instead of "https" for all projects that are pulled in this file (xbyak, ate-pairing, libsnark-supercop)

In algebra/fields/fp.hpp, the static members of the Fp_model template are declared as well as defined. This leads to a problem when we dynamically link against libsnark.so. We have code in the main executable which tries to access those static members, but when that code runs, it finds them all uninitialized, even though we've run the initialization method.

By #include-ing algebra/fields/fp.hpp in our code, the compiler seems to be creating another copy of all of the static members in our binary. Code in our binary therefore accesses its local copies, which are in the uninitialized state, i.e. num_bits is zero, because the init_alt_bn128_params() initializes the copy of the variable in libsnark.so, and not the copy in our binary.

Ideally, there should only be one copy of these variables in libsnark.so. Is there a trick to getting our code to use the ones inside libsnark.so instead of creating copies?

We are using gcc version 5.2.0.

The revision we are using is:

2474695678b3529841eced49ea97ca683e91996c

Could this have been fixed in a newer version?

The Tonelli-Shanks Algorithm used in Fp/Fp2 is currently unbounded, so an attack vector exists if someone provides you with a compressed curve point, and you attempt to decompress it, and the sqrt does not terminate. There are provable bounds on the cost for this algorithm that the curve parameters should be able to configure to prevent this kind of attack.

See http://stanford.edu/~jbooher/expos/sqr_qnr.pdf and https://eprint.iacr.org/2012/685.pdf.

See zcash/zcash#1073 as well.

The symptom (while building libzerocash):

cp src/reductions/r1cs_to_qap/r1cs_to_qap.tcc /home/firexware/Data-1/Documents/FireXware/la/libzerocash/./depinst/include/libsnark/reductions/r1cs_to_qap/r1cs_to_qap.tcc
mkdir -p /home/firexware/Data-1/Documents/FireXware/la/libzerocash/./depinst/include/libsnark/reductions/r1cs_to_qap
cp src/reductions/r1cs_to_qap/r1cs_to_qap.hpp /home/firexware/Data-1/Documents/FireXware/la/libzerocash/./depinst/include/libsnark/reductions/r1cs_to_qap/r1cs_to_qap.hpp
make: *** No rule to make target '(DEPINST)/lib/.exists', needed by 'install'.  Stop.

I think the bug is here, it's missing a $.

https://github.com/scipr-lab/libsnark/blob/master/Makefile#L267

make install installs headers to <prefix>/include/libsnark. By convention dependent project should include -I<prefix>/include only. However, this does not work, because libsnark headers includes other libsnark headers without libsnark prefix, e.g. https://github.com/scipr-lab/libsnark/blob/master/src/algebra/curves/alt_bn128/alt_bn128_g1.hpp#L11.

For us, ALT_BN128 r1cs proofs are 304 bytes in size, with point compression and binary serialization enabled.

I would like to try out a different Barreto-Naehrig pairing. How would I go about computing the curve parameters used in libsnark such as the Frobenius_coeffs, the ate_loop_count, the final_exponent, etc.? Is there software available for this somewhere? Thank you.

Recent research (https://ellipticnews.wordpress.com/2016/05/02/kim-barbulescu-variant-of-the-number-field-sieve-to-compute-discrete-logarithms-in-finite-fields/) suggests that a 448-bit field size may be necessary to achieve sufficient security.

In any case, it may be necessary to change BN128, and echoing #27 make it easier to change this field size later again.

Hi

I am playing with gadgetlib2 and have a weird issue: after converting it to an r1cs constraint system, the is_valid() function returns false.

The demo is using the Comparison_Gadget to compare two numbers (5 <=5`):

#include <iostream>

#include <gadgetlib2/gadget.hpp>
#include <gadgetlib2/integration.hpp>

using namespace libsnark;

int main() {
    typedef Fr<default_ec_pp> FieldT;

    gadgetlib2::initPublicParamsFromDefaultPp();
    auto pb = gadgetlib2::Protoboard::create(gadgetlib2::R1P);
    size_t size =  100;
    const gadgetlib2::PackedWord lhs;
    const gadgetlib2::PackedWord rhs;
    const gadgetlib2::FlagVariable less;
    const gadgetlib2::FlagVariable lessOrEqual;
    auto g = gadgetlib2::Comparison_Gadget::create(pb, 3, lhs, rhs, less, lessOrEqual);
    g->generateConstraints();
    pb->val(lhs) = 5;
    pb->val(rhs) = 5;
    g->generateWitness();
    assert(pb->isSatisfied());
    assert(pb->val(less) == 0);
    assert(pb->val(lessOrEqual) == 1);
    // translate constraint system to libsnark format.
    r1cs_constraint_system<FieldT> cs = get_constraint_system_from_gadgetlib2(*pb);
    // translate full variable assignment to libsnark format
    const r1cs_variable_assignment<FieldT> full_assignment = get_variable_assignment_from_gadgetlib2(*pb);
    // extract primary and auxiliary input
    const r1cs_primary_input<FieldT> primary_input(full_assignment.begin(), full_assignment.begin() + cs.num_inputs());
    const r1cs_auxiliary_input<FieldT> auxiliary_input(full_assignment.begin() + cs.num_inputs(), full_assignment.end());

    assert(cs.is_satisfied(primary_input, auxiliary_input));
    assert(cs.is_valid()); // FAILS
}

(The Makefile I used to compile the above is here: https://github.com/benma/libsnark/blob/6be0121cbeedefc2bffd4b89e7ef268a7da90efe/link_example/Makefile)

g++ main.cpp -o main -std=c++11 -L./lib -lsnark -lsupercop -lgmp -lgmpxx -I./include -I./include/libsnark -DCURVE_BN128
LD_LIBRARY_PATH=./lib ./main
main: main.cpp:35: int main(): Assertion `cs.is_valid()' failed.
Aborted (core dumped)

Even though the protoboard behaves correctly (see the three asserts after g->generateWitness();), the derived r1cs system is invalid. Interestingly, cs.is_satisfied also behaves as expected.

I am not sure whether I did something wrong in the setup / conversion, or if there is a bug in get_constraint_system_from_gadgetlib2 or in the implementation of is_valid().

The same happens if I try to convert the first example of the gadgetlib2 tutorial (

It doesn't happen this example:

I'd appreciate any hints.

Here's an error I'm getting from ./get-libsnark:

cp src/reductions/r1cs_to_qap/r1cs_to_qap.tcc /home/firexware/Data-1/Documents/FireXware/la/libzerocash/./depinst/include/libsnark/reductions/r1cs_to_qap/r1cs_to_qap.tcc
mkdir -p /home/firexware/Data-1/Documents/FireXware/la/libzerocash/./depinst/include/libsnark/reductions/r1cs_to_qap
cp src/reductions/r1cs_to_qap/r1cs_to_qap.hpp /home/firexware/Data-1/Documents/FireXware/la/libzerocash/./depinst/include/libsnark/reductions/r1cs_to_qap/r1cs_to_qap.hpp
mkdir -p /home/firexware/Data-1/Documents/FireXware/la/libzerocash/./depinst/lib
cp  /home/firexware/Data-1/Documents/FireXware/la/libzerocash/./depinst/lib/
cp: missing destination file operand after ‘/home/firexware/Data-1/Documents/FireXware/la/libzerocash/./depinst/lib/’
Try 'cp --help' for more information.
Makefile:268: recipe for target 'install' failed
make: *** [install] Error 1

We currently used (a subset of) supercop for the ADSNARK ppzksnark. It is fetched and compiled by prepare-depends.sh, resulting in ./depinst/lib/libsupercop.a. This is then make installed into $PREFIX/lib.

When trying to make libsnark a single libsnark.so including all dependencies, we noticed that supercop doesn't support that, because its internal qhasm routines haven't been adapted for position-independent code. We get errors like:

/usr/bin/ld: libsnark.a(sc25519_barrett.o): relocation R_X86_64_32S against crypto_sign_ed25519_amd64_51_30k_batch_MU3' can not be used when making a shared object; recompile with -fPIC
libsnark.a(sc25519_barrett.o): error adding symbols: Bad value

(See http://stackoverflow.com/a/9341970 for a discussion of such situations.)

Suggested actions:

1. For now, Document that building a dynamic library requires either linking apps using -lsupercop or building libsnark using NO_SUPERCOP=1.
2. In the planned makefile/CMake cleanup, have an explicit --enable-adsnark, off by default. Unless enabled, supercop is not even built.
3. Eventually, change the supercop asm routines to be PIC-compatible (at what cost in performance?).

I'm running Debian x86_64 trying to get libsnark to install completely, but been unable to get past this point ?

Any suggestions are appreciated.

Mel

https://github.com/scipr-lab/libsnark/blob/master/src/algebra/fields/fp2.hpp#L27 says F[p^3] where it should say F[p^2]. This is significant because I'm not sure how much to trust the rest of the comments in that file now (i.e. have they been changed from the corresponding ones in https://github.com/scipr-lab/libsnark/blob/master/src/algebra/fields/fp3.hpp ?)

We want to transition libsnark to CMake. The cmake branch mostly implements this, but its code lags a bit behind master.

We should finalize the CMake flags interface, and merge the cmake branch into master.

When finalizing the CMake flags, let's take the opportunity to remove all negations (e.g., NO_PT_COMPRESSION), and make sure all useful flags are expressed in a uniform way (currently some are Makefile proper flags and some are pass-through FEATUREFLAGS="-Dfoo".

I am trying to run the tutorial by running g++ src/gadgetlib2/examples/tutorial.hpp from the libsnark folder without success. I am working on Ubuntu 15, with g++-5.2.

The error is: tutorial.cpp:14:33: fatal error: gadgetlib2/gadget.hpp: No such file or directory.

If I change the line to a path relative to the cpp file e.g. #include "../gadget.hpp" then that error is fixed, but it starts to show the same error in a chain in the next file it finds pp.hpp:13:42: fatal error: common/default_types/ec_pp.hpp: No such file or directory

What am I doing wrong?

The source for the r1cs_ppzksnark proving system says:

The implementation instantiates (a modification of) the protocol of [PGHR13],
by following extending, and optimizing the approach described in [BCTV14].

1. What are the extensions and optimizations relative to BCTV14?
2. Do they affect interoperability?
3. Could they affect security?

From what I remember, these formats are different, which is a roadblock for using both at the same time in different contexts.

Why not thinking about adding Clang Support? the code is not clean enough, and have to be standardised, clang does not accept to compile it because of that.

Must of problems are "invalid operands to binary expression" because of mal-placements of templates/functions.

Clang is very powerful in case of code analysis and error reporting, and can help fining more bugs and fixing more problems and even optimizing the code.

Any Chances?

→ CXX=clang make all CURVE=BN128 LOWMEM=1 DEBUG=1
clang -o src/gadgetlib2/examples/tutorial.o   src/gadgetlib2/examples/tutorial.cpp -c -MMD -std=c++11 -Wall -Wextra -Wno-unused-parameter -Wno-comment -Wfatal-errors -O2 -march=native -mtune=native -DUSE_ASM -DMONTGOMERY_OUTPUT -DCURVE_BN128  -Idepinst/include -Isrc -DBN_SUPPORT_SNARK -DLOWMEM -fPIC -DDEBUG -ggdb3
In file included from src/gadgetlib2/examples/tutorial.cpp:17:
In file included from src/zk_proof_systems/ppzksnark/r1cs_ppzksnark/examples/run_r1cs_ppzksnark.hpp:33:
In file included from src/zk_proof_systems/ppzksnark/r1cs_ppzksnark/examples/run_r1cs_ppzksnark.tcc:18:
In file included from src/zk_proof_systems/ppzksnark/r1cs_ppzksnark/r1cs_ppzksnark.hpp:468:
src/zk_proof_systems/ppzksnark/r1cs_ppzksnark/r1cs_ppzksnark.tcc:375:32: fatal error: invalid operands to binary expression
      ('const Fr<libsnark::bn128_pp>' (aka 'const libsnark::Fp_model<4, &libsnark::bn128_modulus_r>') and 'libsnark::bn128_G2')
    G2<ppT> alphaA_g2 = alphaA * G2<ppT>::one();
                        ~~~~~~ ^ ~~~~~~~~~~~~~~
src/zk_proof_systems/ppzksnark/r1cs_ppzksnark/examples/run_r1cs_ppzksnark.tcc:70:43: note: in instantiation of function template specialization
      'libsnark::r1cs_ppzksnark_generator<libsnark::bn128_pp>' requested here
    r1cs_ppzksnark_keypair<ppT> keypair = r1cs_ppzksnark_generator<ppT>(example.constraint_system);
                                          ^
src/gadgetlib2/examples/tutorial.cpp:496:32: note: in instantiation of function template specialization 'libsnark::run_r1cs_ppzksnark<libsnark::bn128_pp>'
      requested here
    const bool bit = libsnark::run_r1cs_ppzksnark<libsnark::default_ec_pp>(example, test_serialization);
                               ^
src/algebra/fields/fp.hpp:103:14: note: candidate function not viable: no known conversion from 'libsnark::bn128_G2' to 'const libsnark::Fp_model<4,
      &libsnark::bn128_modulus_r>' for 1st argument
    Fp_model operator*(const Fp_model& other) const;
             ^
src/algebra/curves/bn128/bn128_g1.hpp:74:10: note: candidate template ignored: could not match 'bigint' against 'Fp_model'
bn128_G1 operator*(const bigint<m> &lhs, const bn128_G1 &rhs)
         ^
src/algebra/curves/bn128/bn128_g1.hpp:80:10: note: candidate template ignored: substitution failure [with m = 4]: deduced non-type template argument does
      not have the same type as the its corresponding template parameter ('bigint<bn128_r_limbs>' vs 'const bigint<4L> &')
bn128_G1 operator*(const Fp_model<m,modulus_p> &lhs, const bn128_G1 &rhs)
         ^
src/algebra/curves/bn128/bn128_g2.hpp:75:10: note: candidate template ignored: could not match 'bigint' against 'Fp_model'
bn128_G2 operator*(const bigint<m> &lhs, const bn128_G2 &rhs)
         ^
src/algebra/curves/bn128/bn128_g2.hpp:81:10: note: candidate template ignored: substitution failure [with m = 4]: deduced non-type template argument does
      not have the same type as the its corresponding template parameter ('bigint<bn128_r_limbs>' vs 'const bigint<4L> &')
bn128_G2 operator*(const Fp_model<m, modulus_p> &lhs, const bn128_G2 &rhs)
         ^
src/relations/variable.tcc:69:21: note: candidate template ignored: could not match 'variable<type-parameter-0-0>' against 'libsnark::bn128_G2'
linear_term<FieldT> operator*(const integer_coeff_t int_coeff, const variable<FieldT> &var)
                    ^
src/relations/variable.tcc:75:21: note: candidate template ignored: could not match 'variable<type-parameter-0-0>' against 'libsnark::bn128_G2'
linear_term<FieldT> operator*(const FieldT &field_coeff, const variable<FieldT> &var)
                    ^
src/relations/variable.tcc:184:21: note: candidate template ignored: could not match 'linear_term<type-parameter-0-0>' against 'libsnark::bn128_G2'
linear_term<FieldT> operator*(const integer_coeff_t int_coeff, const linear_term<FieldT> &lt)
                    ^
src/relations/variable.tcc:190:21: note: candidate template ignored: could not match 'linear_term<type-parameter-0-0>' against 'libsnark::bn128_G2'
linear_term<FieldT> operator*(const FieldT &field_coeff, const linear_term<FieldT> &lt)
                    ^
src/relations/variable.tcc:449:28: note: candidate template ignored: could not match 'linear_combination<type-parameter-0-0>' against 'libsnark::bn128_G2'
linear_combination<FieldT> operator*(const integer_coeff_t int_coeff, const linear_combination<FieldT> &lc)
                           ^
src/relations/variable.tcc:455:28: note: candidate template ignored: could not match 'linear_combination<type-parameter-0-0>' against 'libsnark::bn128_G2'
linear_combination<FieldT> operator*(const FieldT &field_coeff, const linear_combination<FieldT> &lc)
                           ^
src/algebra/knowledge_commitment/knowledge_commitment.tcc:66:29: note: candidate template ignored: could not match 'bigint' against 'Fp_model'
knowledge_commitment<T1,T2> operator*(const bigint<m> &lhs, const knowledge_commitment<T1,T2> &rhs)
                            ^
src/algebra/knowledge_commitment/knowledge_commitment.tcc:73:29: note: candidate template ignored: could not match
      'knowledge_commitment<type-parameter-0-0, type-parameter-0-1>' against 'libsnark::bn128_G2'
knowledge_commitment<T1,T2> operator*(const Fp_model<m, modulus_p> &lhs, const knowledge_commitment<T1,T2> &rhs)
                            ^
1 error generated.
make: *** [Makefile:226: src/gadgetlib2/examples/tutorial.o] Error 1

→ clang++ --version
clang version 3.8.1 (tags/RELEASE_381/final)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /usr/bin

Same command works with g++ without issues and compiles everything.

g++ (GCC) version: 6.1.1
system: Linux 4.6.4-1-ARCH #1 SMP PREEMPT Mon Jul 11 19:12:32 CEST 2016 x86_64 GNU/Linux

The bn128 G2 deserialization code does not ensure that the point is in the correct subgroup. This is resolved in Zcash (see zcash/zcash#1938) but is_well_formed and the deserialization code itself should be checking the order of the points it deserializes.

It's unclear to me how points outside the group affect the pairing.

Large constraint systems mean huge proving keys, and with point compression enabled, loading those keys takes several minutes. Right now you can only enable point compression across the board, and it could be tricky to refactor that. Perhaps it should be made into a global that can be selectively disabled/enabled by the end user?

Currently the binary serialization format (BINARY_OUTPUT) is not compatible across machine with different word size. This is documented, but should be fixed.

The format may be endianness-dependent as well.

One place that causes the machine-dependence is the bigint serialization ( operator<<(std::ostream &out, const bigint<n> &b) and operator>>(std::istream &in, bigint<n> &b) in src/algebra/fields/bigint.tcc), which just copies the internal array of mp_limb_t limbs. This is easily fixed.

Are there additional places?

./prepare_depends.sh does not prepare libprocps-dev

It would be super useful if there were a not-completely-trivial example circuit included.

E.g. the SHA256 compression function with 512+256 bits input and it accepts if the 256 bits matches the hash from the specific 512 bit input.

gadgetlib2_test.cpp does not include any of the "_UTEST.cpp" of the same folder, so none of the tests are actually run.

In the Makefile, those files are listed (

Thoughts?

In our r1cs witness, most of the variables are either zero or one. We should be able to make a FieldT smart pointer to reduce memory usage.

SHA512_rng() in rng.tcc contains this assert:

assert(GMP_NUMB_BITS == 64); // current Python code cannot handle larger values, so testing here for some assumptions.

This breaks some of the executables on 32-bit platforms (e.g., the src/zk_proof_systems/pcd/r1cs_pcd/r1cs_mp_ppzkpcd/tests/test_r1cs_mp_ppzkpcd test).

Can the assert be relaxed to <= 64?

Also, let's clarify the comment -- which Python code is it talking about, when we're deep in C++ land?

The #include directives assume that the directory ./src/ or the installed directory $(PREFIX)/include/libsnark (see Makefile L282 at 0b928a7b (latest on branch master)) are on the include path. This is non-standard and complicates detecting this library with GNU autoconf.

The zcash configure.ac L704-L718 at 108650a5 (latest on branch zc.v0.11.2.latest) demonstrates the difficulty of working around this issue for dependent programs that use autoconf:

# libsnark header layout is broken unless cpp's -I is passed with the
# libsnark directory, so for now we use this hideous workaround:
echo 'Hunting for libsnark include directory...'
[LIBSNARK_INCDIR="$(echo "$CPPFLAGS" | sed 's,^.*-I\([^ ]*/include\).*$,\1/libsnark,')"]
if test -d "$LIBSNARK_INCDIR"; then
   echo "Found libsnark include directory: $LIBSNARK_INCDIR"
else
    AC_MSG_ERROR(libsnark include directory not found)
fi

CPPFLAGS="-I$LIBSNARK_INCDIR $CPPFLAGS"

# Now check for libsnark compilability using traditional autoconf tests:
AC_CHECK_HEADER([libsnark/gadgetlib1/gadget.hpp],,AC_MSG_ERROR(libsnark headers missing))
AC_CHECK_LIB([snark],[main],LIBSNARK_LIBS=-lsnark, [AC_MSG_ERROR(libsnark missing)], [-lgmpxx])

libsnark makes implicit assertions about the machine word size. For example, TinyRAM with word size W requires 2W-bit native arithmetic and thus test_ram_ppzksnark fails on 32-bit machines. We should document this and have appropriate assertions in place.

Doing this would allow us to destroy those (large) vectors to free up memory for use in the remaining portions of the proving routines when they are no longer necessary.