Interfaces for Relations and SNARKs for these relations

Last update: Dec 26, 2022

Overview

SNARK and Relation Traits

The arkworks ecosystem consists of Rust libraries for designing and working with zero knowledge succinct non-interactive arguments (zkSNARKs). This repository contains efficient libraries that describe interfaces for zkSNARKs, as well as interfaces for programming them.

This library is released under the MIT License and the Apache v2 License (see License).

WARNING: This is an academic proof-of-concept prototype, and in particular has not received careful code review. This implementation is NOT ready for production use.

Directory structure

This repository contains two Rust crates:

ark-snark: Provides generic traits for zkSNARKs
ark-relations: Provides generic traits for NP relations used in programming zkSNARKs, such as R1CS

Overview

This repository provides the core infrastucture for using the succinct argument systems that arkworks provides. Users who want to produce arguments about various problems of interest will first reduce those problems to an NP relation, various examples of which are defined in the ark-relations crate. Then a SNARK system defined over that relation is used to produce a succinct argument. The ark-snark crate defines a SNARK trait that encapsulates the general functionality, as well as specific traits for various types of SNARK (those with transparent and universal setup, for instance). Different repositories within the arkworks ecosystem implement this trait for various specific SNARK constructions, such as Groth16, GM17, and Marlin.

Build guide

The library compiles on the stable toolchain of the Rust compiler. To install the latest version of Rust, first install rustup by following the instructions here, or via your platform's package manager. Once rustup is installed, install the Rust toolchain by invoking:

rustup install stable

After that, use cargo, the standard Rust build tool, to build the libraries:

git clone https://github.com/arkworks-rs/snark.git
cd snark
cargo build --release

Tests

This library comes with comprehensive unit and integration tests for each of the provided crates. Run the tests with:

cargo test --all

License

The crates in this repo are licensed under either of the following licenses, at your discretion.

Apache License Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

Unless you explicitly state otherwise, any contribution submitted for inclusion in this library by you shall be dual licensed as above (as defined in the Apache v2 License), without any additional terms or conditions.

Acknowledgements

This work was supported by: a Google Faculty Award; the National Science Foundation; the UC Berkeley Center for Long-Term Cybersecurity; and donations from the Ethereum Foundation, the Interchain Foundation, and Qtum.

An earlier version of this library was developed as part of the paper "ZEXE: Enabling Decentralized Private Computation".

Comments

Fix the `outline_lcs`
After careful debugging, it appears that the current implementation of outline_lcs has two serious problems:

It does not correctly create additional constraints. All the additional constraints should be LC * 1 = V where V is the new witness variable. In the end, all of them are V * 1 = V.

It does not increase the count of num_linear_combinations correctly. So that in Marlin, when the next step wants to pad the matrices to be square, the new linear combinations go to the wrong linear combination entry, causing the outer check to fail.

This PR fixes these two problems and will close this issue in Marlin: https://github.com/arkworks-rs/marlin/issues/56
opened by weikengchen 30
Rework `ConstraintSystem` API to improve ergonomics
Currently the API for writing constraints in r1cs-core is very generic: ConstraintSystem is a trait that downstream users can implement and customize, and it must be threaded throughout the gadget interfaces in r1cs-std and beyond. It also requires users to explicitly set namespaces, which, together with the previous point, makes constraint-generating code very verbose, and often obscures (relatively simple) logic.

In this (WIP) PR I'm trying out a different and hopefully more ergonomic approach. The high-level diff is as follows: The ConstraintSystem trait is replaced with a single ConstraintSystem struct that is meant to be used for all purposes: generating constraints in a SNARK setup, generating witnesses during proving, debugging, etc. This leads to the following changes:

We can store a (wrapper around) Rc<RefCell<ConstraintSystem<F>>> in gadgets that represent variables, such as FieldGadget. This means that we no longer have to pass &mut CS to every function that could possibly generate a constraint, and furthermore means that we can overload arithmetic operators for these gadgets.

By default constraints are automatically given unique names, so that we don't have to call cs.ns(|| "blah") whenever we need to create a constraint. Note that if one wants to explicitly create a namespace, one can still invoke cs.enter_namespace() and then cs.leave_namespace().

To generate a LinearCombination, users don't explicitly generate one themselves. Instead, they register the linear combination with a ConstraintSystem by doing cs.new_lc(my_lc), and get back a Variable::SymbolicLc in return.

This latter design of ConstraintSystem enables a centralized implementation of (optional) optimizations such as

swapping the A and B matrices (useful for Groth16),

balancing the number of non-zero entries in A and B, (useful for Marlin and Fractal) and

"outlining" common linear combinations to reduce the number of non-zero entries in a constraint matrix (useful for Marlin and Fractal)

One concern is the debuggability of constraints generated under this new API because namespacing is automatic. Suggestions would be appreciated. Maybe compiler techniques would be a good starting point here.

Looking for feedback on the initial design. Note that the scope of the PR is massive, because we need to re-architect the r1cs-std, crypto-primitives and dpc crates =/.

CC @kobigurk @gakonst @paberr @ValarDragon

TODOs:

[ ] Check equality of ConstraintSystemRefs when two different gadgets interact, and figure out the appropriate mechanism for checking equality (https://github.com/scipr-lab/zexe/pull/186#issuecomment-612672369)

[ ] Improve debuggability: approach 1 vs inline a stacktrace or some such?
opened by Pratyush 22
Ask for suggestions about encrypted input and output for groth16

Hi, I am a student learning zkSNARK with your library. And I want to implement the following situation.

The client C uses the server S to compute a function, e.g, x^3 + x = y. S will generate groth16 proof for its computation result. Currently, I have realized the proof and verify functions for plaintext x and y. Howerver, C doesn't want S to know its x and y. So C may encrypt x to E(x) and decrypt E(y) received from S.

Do you think it's a reasonable or practical situation? Is there any encryption schemes which support the combination between encryption and zkSNARK? I have searched for a long time, but have no idea how to implement it. I am not sure whether homomorphic encryption can support this situation. Could you give me any suggestions?

Thanks a lot! Looking forward to your reply.

opened by amyzx 20

Add x86_64 asm codegen for PrimeField mul and square

I was able to achieve a 1.7x speedup on 6-limb mul_assign against my previous pull request #163, bringing the total speedup to about 1.84x. This is achieved with a generic code-generation script utilising build.rs that generates x64 assembly utilising the mulxq, adoxq and adcxq instructions for 2 up to 8 limbs.

~Update: was able to extend work to 18 limbs, achieving 1.34x speedup on Fp832. May be worth looking into translating the old square_in_place into assembly, but this is a significant amount of work.~

Update: Put behind feature. Build with:

RUSTFLAGS="--emit=asm -C target-feature=+bmi2,+adx" cargo +nightly bench/test/build --features asm

Next steps: more limbs with less data movement using kilic's strategy. Extend strategy to square_in_place.

Details

I implemented the assembly version of square_in_place as applying mul_assign to itself. That's because the goff squaring formula is not really good, while the original squaring formula requires twice the number of registers and hence goes beyond the scope of this PR, and may in fact be slower in the end, as this PR takes massive advantage of the add and carry chains present in mul_assign.

Update: I cleaned up the messy build.rs by creating a standalone subcrate and importing the generate function.

Future work

Currently, the maximum number of limbs supported is 8, and could be possibly be extended by current methods to about 10 for mul and 11 for squaring. However, going beyond that may require additional work to optimally move data to and from registers into memory (i.e. L1 cache). One should study how a compiler would reason about this to write a reasonable code generation procedure script to do this.

Edit: our data movement is extremely suboptimal. https://raw.githubusercontent.com/kilic/fp/master/generic/x86_arithmetic.s is able to achieve 149ns on 13 limbs, whereas we achieve 190ns. There's a lot to learn here.

We are also somehow still trailing behind MCL, probably the gold-standard for pairings. Here are the benchmarks, run on a similar i7-7700 to mine. Although our Fp performance totally outclasses it, everything else is lagging behind. It manages to achieve a staggering ~0.7ms BLS12_381 pairing (?). Their webassembly target achieves a sickening 3.5ms on my Chrome browser.

I suspect there could be bottlenecks in adc, sbb, negate. Negate is much slower than sub_assign. This I suspect could be fixed with a little more inline assembly, since it's unclear the compiler knows how to do adc. In particular, the modulus can be hard-coded for negate. Assuming we can shave of 3ns per add/sub, we can probably improve performance by another 5%. (Given this, it may indeed be worthwhile to write a procedural macro and do a cleanup. This may turn out not to be possible. But it is worth trying.)

Areas for Improvement

This however does not explain the discrepancy. Looking at the benchmarks more carefully, for BLS12_381, Fq12 mul is ~6800ns, whereas for MCL it is ~3000ns. We're better for Miller loop, 413us vs 527us (but not the precomputed Miller loop (fixed Q in G12) - 405us (which are we using?)). Nonetheless, those timings were for the BN curve, so really we need to improve the Miller loop (7500Mq) down to about 350us.

But this makes it apparent that the significant weakness is in the final exponentiation (9000Mq). We must get timings down from 850us down to 414us, a 2x speedup. Part of this is probably due to our slow Fq inverse timings. This is clear also by examining pairing formulas, where the number of field ops for the final exponentiation should be roughly similar to the Miller loop, but for us the former has a timing double the latter. I estimate fixing this could give another 35% boost to our pairings.

G2 should also be fixed - 25% slowdown - 2.7us vs 2.1us. for add, 1.85us vs 1.49us for double. Our mul assign is apparently ~3x slower (930us vs 360us).

G1 add 529us vs MCL's 472us. Suggests, as suspected, some inefficiency (probably from the very slow Fq doubling). Our G1 doubling beats it however. Should investigate why. Mul is 25% slower (v.s. 154us), but should be fixable with standalone pippenger.

MCL also implements GLV.

I will try to study MCL and obtain more detailed and up to date benchmarks for it.

Main results: 384-bit mul_assign

bls12_377::fq::bench_fq_mul_assign                               51,780       30,340            -21,440  -41.41%   x 1.71
bls12_381::fq::bench_fq_mul_assign                               52,143       30,280            -21,863  -41.93%   x 1.72
sw6::fr::bench_fr_mul_assign                                     50,664       30,005            -20,659  -40.78%   x 1.69

384-bit square_in_place:

bls12_377::fq::bench_fq_square                                   43,704       30,089            -13,615  -31.15%   x 1.45
bls12_381::fq::bench_fq_square                                   44,295       31,291            -13,004  -29.36%   x 1.42
sw6::fr::bench_fr_square                                         42,764       30,561            -12,203  -28.54%   x 1.40

256-bit mul_assign:

bls12_377::fr::bench_fr_mul_assign                               25,583       16,173             -9,410  -36.78%   x 1.58
bls12_381::fr::bench_fr_mul_assign                               27,166       17,113            -10,053  -37.01%   x 1.59

256-bit square_in_place:

bls12_377::fr::bench_fr_square                                   21,929       15,620             -6,309  -28.77%   x 1.40
bls12_381::fr::bench_fr_square                                   24,908       16,834             -8,074  -32.42%   x 1.48

384-bit G1:

 bls12_377::ec::g1::bench_g1_add_assign                           1,048,201    755,061          -293,140  -27.97%   x 1.39 
 bls12_377::ec::g1::bench_g1_add_assign_mixed                     749,362      529,950          -219,412  -29.28%   x 1.41 
 bls12_377::ec::g1::bench_g1_double                               535,695      418,700          -116,995  -21.84%   x 1.28 
 bls12_377::ec::g1::bench_g1_mul_assign                           269,918      202,057           -67,861  -25.14%   x 1.34
 bls12_381::ec::g1::bench_g1_add_assign                           1,059,324    769,470          -289,854  -27.36%   x 1.38 
 bls12_381::ec::g1::bench_g1_add_assign_mixed                     758,426      534,781          -223,645  -29.49%   x 1.42 
 bls12_381::ec::g1::bench_g1_double                               539,424      419,918          -119,506  -22.15%   x 1.28 
 bls12_381::ec::g1::bench_g1_mul_assign                           274,129      206,160           -67,969  -24.79%   x 1.33 
 bls12_381::ec::g1::bench_g1_rand                                 274,444      204,898           -69,546  -25.34%   x 1.34

384-bit pairings:

 bls12_377::pairing::pairing::bench_pairing_final_exponentiation  1,292,296    1,087,830        -204,466  -15.82%   x 1.19 
 bls12_377::pairing::pairing::bench_pairing_full                  2,235,430    1,845,299        -390,131  -17.45%   x 1.21 
 bls12_377::pairing::pairing::bench_pairing_miller_loop           631,072      510,977          -120,095  -19.03%   x 1.24
 bls12_381::pairing::pairing::bench_pairing_final_exponentiation  1,072,725    847,028          -225,697  -21.04%   x 1.27 
 bls12_381::pairing::pairing::bench_pairing_full                  1,871,067    1,472,014        -399,053  -21.33%   x 1.27 
 bls12_381::pairing::pairing::bench_pairing_miller_loop           546,691      413,627          -133,064  -24.34%   x 1.32

SW6 (updated)

sw6::fq::bench_fq_mul_assign                               253,632               189,117               -64,515  -25.44%   x 1.34
sw6::fq::bench_fq_square                                   208,612               192,834               -15,778   -7.56%   x 1.08
sw6::ec::g1::bench_g1_add_assign                           4,087,676             3,464,448            -623,228  -15.25%   x 1.18 
sw6::ec::g1::bench_g1_add_assign_mixed                     2,888,104             2,429,125            -458,979  -15.89%   x 1.19 
sw6::ec::g1::bench_g1_double                               2,608,558             2,417,105            -191,453   -7.34%   x 1.08 
sw6::ec::g1::bench_g1_mul_assign                           1,758,755             1,576,919            -181,836  -10.34%   x 1.12
sw6::pairing::pairing::bench_pairing_final_exponentiation  8,648,924             7,737,242            -911,682  -10.54%   x 1.12 
sw6::pairing::pairing::bench_pairing_full                  95,098,636            85,313,158         -9,785,478  -10.29%   x 1.11 
sw6::pairing::pairing::bench_pairing_miller_loop           86,559,010            77,266,953         -9,292,057  -10.73%   x 1.12

Full results

 bls12_377::ec::g1::bench_g1_add_assign                           1,048,201    755,061          -293,140  -27.97%   x 1.39 
 bls12_377::ec::g1::bench_g1_add_assign_mixed                     749,362      529,950          -219,412  -29.28%   x 1.41 
 bls12_377::ec::g1::bench_g1_double                               535,695      418,700          -116,995  -21.84%   x 1.28 
 bls12_377::ec::g1::bench_g1_mul_assign                           269,918      202,057           -67,861  -25.14%   x 1.34 
 bls12_377::ec::g1::bench_g1_rand                                 267,739      202,269           -65,470  -24.45%   x 1.32 
 bls12_377::ec::g2::bench_g2_add_assign                           4,612        3,798                -814  -17.65%   x 1.21 
 bls12_377::ec::g2::bench_g2_add_assign_mixed                     3,232        2,703                -529  -16.37%   x 1.20 
 bls12_377::ec::g2::bench_g2_double                               2,158        1,877                -281  -13.02%   x 1.15 
 bls12_377::ec::g2::bench_g2_mul_assign                           1,102,020    937,104          -164,916  -14.96%   x 1.18 
 bls12_377::ec::g2::bench_g2_rand                                 1,080,859    922,946          -157,913  -14.61%   x 1.17 
 bls12_377::fq12::bench_fq12_add_assign                           133          131                    -2   -1.50%   x 1.02 
 bls12_377::fq12::bench_fq12_double                               126          114                   -12   -9.52%   x 1.11 
 bls12_377::fq12::bench_fq12_inverse                              25,742       28,005              2,263    8.79%   x 0.92 
 bls12_377::fq12::bench_fq12_mul_assign                           6,874        5,566              -1,308  -19.03%   x 1.23 
 bls12_377::fq12::bench_fq12_square                               4,723        3,882                -841  -17.81%   x 1.22 
 bls12_377::fq12::bench_fq12_sub_assign                           119          116                    -3   -2.52%   x 1.03 
 bls12_377::fq2::bench_fq2_add_assign                             17           16                     -1   -5.88%   x 1.06 
 bls12_377::fq2::bench_fq2_double                                 17           20                      3   17.65%   x 0.85 
 bls12_377::fq2::bench_fq2_inverse                                13,930       18,062              4,132   29.66%   x 0.77 
 bls12_377::fq2::bench_fq2_mul_assign                             249          191                   -58  -23.29%   x 1.30 
 bls12_377::fq2::bench_fq2_sqrt                                   127,995      96,823            -31,172  -24.35%   x 1.32 
 bls12_377::fq2::bench_fq2_square                                 231          227                    -4   -1.73%   x 1.02 
 bls12_377::fq2::bench_fq2_sub_assign                             19           19                      0    0.00%   x 1.00 
 bls12_377::fq::bench_fq_add_assign                               10           10                      0    0.00%   x 1.00 
 bls12_377::fq::bench_fq_double                                   9,108        9,111                   3    0.03%   x 1.00 
 bls12_377::fq::bench_fq_from_repr                                59           38                    -21  -35.59%   x 1.55 
 bls12_377::fq::bench_fq_into_repr                                32           31                     -1   -3.12%   x 1.03 
 bls12_377::fq::bench_fq_inverse                                  13,708       17,631              3,923   28.62%   x 0.78 
 bls12_377::fq::bench_fq_mul_assign                               51,780       30,340            -21,440  -41.41%   x 1.71 
 bls12_377::fq::bench_fq_negate                                   13           14                      1    7.69%   x 0.93 
 bls12_377::fq::bench_fq_repr_add_nocarry                         8            10                      2   25.00%   x 0.80 
 bls12_377::fq::bench_fq_repr_div2                                6            6                       0    0.00%   x 1.00 
 bls12_377::fq::bench_fq_repr_mul2                                5            13                      8  160.00%   x 0.38 
 bls12_377::fq::bench_fq_repr_num_bits                            4            3                      -1  -25.00%   x 1.33 
 bls12_377::fq::bench_fq_repr_sub_noborrow                        9            11                      2   22.22%   x 0.82 
 bls12_377::fq::bench_fq_sqrt                                     77,501       54,993            -22,508  -29.04%   x 1.41 
 bls12_377::fq::bench_fq_square                                   43,704       30,089            -13,615  -31.15%   x 1.45 
 bls12_377::fq::bench_fq_sub_assign                               11           11                      0    0.00%   x 1.00 
 bls12_377::fr::bench_fr_add_assign                               7            7                       0    0.00%   x 1.00 
 bls12_377::fr::bench_fr_double                                   10,316       5,832              -4,484  -43.47%   x 1.77 
 bls12_377::fr::bench_fr_from_repr                                31           22                     -9  -29.03%   x 1.41 
 bls12_377::fr::bench_fr_into_repr                                20           19                     -1   -5.00%   x 1.05 
 bls12_377::fr::bench_fr_inverse                                  7,516        5,451              -2,065  -27.47%   x 1.38 
 bls12_377::fr::bench_fr_mul_assign                               25,583       16,173             -9,410  -36.78%   x 1.58 
 bls12_377::fr::bench_fr_negate                                   10           7                      -3  -30.00%   x 1.43 
 bls12_377::fr::bench_fr_repr_add_nocarry                         6            7                       1   16.67%   x 0.86 
 bls12_377::fr::bench_fr_repr_div2                                4            4                       0    0.00%   x 1.00 
 bls12_377::fr::bench_fr_repr_mul2                                4            7                       3   75.00%   x 0.57 
 bls12_377::fr::bench_fr_repr_num_bits                            4            3                      -1  -25.00%   x 1.33 
 bls12_377::fr::bench_fr_repr_sub_noborrow                        6            8                       2   33.33%   x 0.75 
 bls12_377::fr::bench_fr_sqrt                                     30,712       22,193             -8,519  -27.74%   x 1.38 
 bls12_377::fr::bench_fr_square                                   21,929       15,620             -6,309  -28.77%   x 1.40 
 bls12_377::fr::bench_fr_sub_assign                               8            7                      -1  -12.50%   x 1.14 
 bls12_377::pairing::pairing::bench_pairing_final_exponentiation  1,292,296    1,087,830        -204,466  -15.82%   x 1.19 
 bls12_377::pairing::pairing::bench_pairing_full                  2,235,430    1,845,299        -390,131  -17.45%   x 1.21 
 bls12_377::pairing::pairing::bench_pairing_miller_loop           631,072      510,977          -120,095  -19.03%   x 1.24 
 bls12_381::ec::g1::bench_g1_add_assign                           1,059,324    769,470          -289,854  -27.36%   x 1.38 
 bls12_381::ec::g1::bench_g1_add_assign_mixed                     758,426      534,781          -223,645  -29.49%   x 1.42 
 bls12_381::ec::g1::bench_g1_double                               539,424      419,918          -119,506  -22.15%   x 1.28 
 bls12_381::ec::g1::bench_g1_mul_assign                           274,129      206,160           -67,969  -24.79%   x 1.33 
 bls12_381::ec::g1::bench_g1_rand                                 274,444      204,898           -69,546  -25.34%   x 1.34 
 bls12_381::ec::g2::bench_g2_add_assign                           4,660        3,785                -875  -18.78%   x 1.23 
 bls12_381::ec::g2::bench_g2_add_assign_mixed                     3,267        2,691                -576  -17.63%   x 1.21 
 bls12_381::ec::g2::bench_g2_double                               2,175        1,871                -304  -13.98%   x 1.16 
 bls12_381::ec::g2::bench_g2_mul_assign                           1,116,571    936,037          -180,534  -16.17%   x 1.19 
 bls12_381::ec::g2::bench_g2_rand                                 1,084,845    919,647          -165,198  -15.23%   x 1.18 
 bls12_381::fq12::bench_fq12_add_assign                           130          125                    -5   -3.85%   x 1.04 
 bls12_381::fq12::bench_fq12_double                               126          112                   -14  -11.11%   x 1.12 
 bls12_381::fq12::bench_fq12_inverse                              24,139       25,376              1,237    5.12%   x 0.95 
 bls12_381::fq12::bench_fq12_mul_assign                           6,199        4,687              -1,512  -24.39%   x 1.32 
 bls12_381::fq12::bench_fq12_square                               4,118        3,150                -968  -23.51%   x 1.31 
 bls12_381::fq12::bench_fq12_sub_assign                           119          120                     1    0.84%   x 0.99 
 bls12_381::fq2::bench_fq2_add_assign                             18           20                      2   11.11%   x 0.90 
 bls12_381::fq2::bench_fq2_double                                 17           19                      2   11.76%   x 0.89 
 bls12_381::fq2::bench_fq2_inverse                                14,351       18,160              3,809   26.54%   x 0.79 
 bls12_381::fq2::bench_fq2_mul_assign                             225          162                   -63  -28.00%   x 1.39 
 bls12_381::fq2::bench_fq2_sqrt                                   124,951      83,086            -41,865  -33.51%   x 1.50 
 bls12_381::fq2::bench_fq2_square                                 177          142                   -35  -19.77%   x 1.25 
 bls12_381::fq2::bench_fq2_sub_assign                             19           19                      0    0.00%   x 1.00 
 bls12_381::fq::bench_fq_add_assign                               10           10                      0    0.00%   x 1.00 
 bls12_381::fq::bench_fq_double                                   9,240        9,062                -178   -1.93%   x 1.02 
 bls12_381::fq::bench_fq_from_repr                                59           39                    -20  -33.90%   x 1.51 
 bls12_381::fq::bench_fq_into_repr                                32           31                     -1   -3.12%   x 1.03 
 bls12_381::fq::bench_fq_inverse                                  14,949       17,811              2,862   19.15%   x 0.84 
 bls12_381::fq::bench_fq_mul_assign                               52,143       30,280            -21,863  -41.93%   x 1.72 
 bls12_381::fq::bench_fq_negate                                   14           14                      0    0.00%   x 1.00 
 bls12_381::fq::bench_fq_repr_add_nocarry                         8            10                      2   25.00%   x 0.80 
 bls12_381::fq::bench_fq_repr_div2                                6            6                       0    0.00%   x 1.00 
 bls12_381::fq::bench_fq_repr_mul2                                6            13                      7  116.67%   x 0.46 
 bls12_381::fq::bench_fq_repr_num_bits                            4            4                       0    0.00%   x 1.00 
 bls12_381::fq::bench_fq_repr_sub_noborrow                        9            11                      2   22.22%   x 0.82 
 bls12_381::fq::bench_fq_sqrt                                     61,857       38,010            -23,847  -38.55%   x 1.63 
 bls12_381::fq::bench_fq_square                                   44,295       31,291            -13,004  -29.36%   x 1.42 
 bls12_381::fq::bench_fq_sub_assign                               11           10                     -1   -9.09%   x 1.10 
 bls12_381::fr::bench_fr_add_assign                               7            7                       0    0.00%   x 1.00 
 bls12_381::fr::bench_fr_double                                   10,284       5,845              -4,439  -43.16%   x 1.76 
 bls12_381::fr::bench_fr_from_repr                                31           22                     -9  -29.03%   x 1.41 
 bls12_381::fr::bench_fr_into_repr                                20           19                     -1   -5.00%   x 1.05 
 bls12_381::fr::bench_fr_inverse                                  7,600        5,440              -2,160  -28.42%   x 1.40 
 bls12_381::fr::bench_fr_mul_assign                               27,166       17,113            -10,053  -37.01%   x 1.59 
 bls12_381::fr::bench_fr_negate                                   10           8                      -2  -20.00%   x 1.25 
 bls12_381::fr::bench_fr_repr_add_nocarry                         6            7                       1   16.67%   x 0.86 
 bls12_381::fr::bench_fr_repr_div2                                4            5                       1   25.00%   x 0.80 
 bls12_381::fr::bench_fr_repr_mul2                                4            7                       3   75.00%   x 0.57 
 bls12_381::fr::bench_fr_repr_num_bits                            4            3                      -1  -25.00%   x 1.33 
 bls12_381::fr::bench_fr_repr_sub_noborrow                        7            8                       1   14.29%   x 0.88 
 bls12_381::fr::bench_fr_sqrt                                     27,321       19,871             -7,450  -27.27%   x 1.37 
 bls12_381::fr::bench_fr_square                                   24,908       16,834             -8,074  -32.42%   x 1.48 
 bls12_381::fr::bench_fr_sub_assign                               8            7                      -1  -12.50%   x 1.14 
 bls12_381::pairing::pairing::bench_pairing_final_exponentiation  1,072,725    847,028          -225,697  -21.04%   x 1.27 
 bls12_381::pairing::pairing::bench_pairing_full                  1,871,067    1,472,014        -399,053  -21.33%   x 1.27 
 bls12_381::pairing::pairing::bench_pairing_miller_loop           546,691      413,627          -133,064  -24.34%   x 1.32 
 sw6::ec::g1::bench_g1_add_assign                                 4,185,546    4,048,507        -137,039   -3.27%   x 1.03 
 sw6::ec::g1::bench_g1_add_assign_mixed                           2,963,674    2,836,688        -126,986   -4.28%   x 1.04 
 sw6::ec::g1::bench_g1_double                                     2,624,621    2,602,247         -22,374   -0.85%   x 1.01 
 sw6::ec::g1::bench_g1_mul_assign                                 1,795,032    1,730,592         -64,440   -3.59%   x 1.04 
 sw6::ec::g1::bench_g1_rand                                       1,798,136    1,731,877         -66,259   -3.68%   x 1.04 
 sw6::ec::g2::bench_g2_add_assign                                 4,600        3,771                -829  -18.02%   x 1.22 
 sw6::ec::g2::bench_g2_add_assign_mixed                           3,206        2,663                -543  -16.94%   x 1.20 
 sw6::ec::g2::bench_g2_double                                     2,140        1,863                -277  -12.94%   x 1.15 
 sw6::ec::g2::bench_g2_mul_assign                                 1,098,494    935,481          -163,013  -14.84%   x 1.17 
 sw6::ec::g2::bench_g2_rand                                       1,076,092    915,453          -160,639  -14.93%   x 1.18 
 sw6::fq3::bench_fq3_add_assign                                   75           62                    -13  -17.33%   x 1.21 
 sw6::fq3::bench_fq3_double                                       50           55                      5   10.00%   x 0.91 
 sw6::fq3::bench_fq3_inverse                                      50,737       42,375             -8,362  -16.48%   x 1.20 
 sw6::fq3::bench_fq3_mul_assign                                   2,121        2,046                 -75   -3.54%   x 1.04 
 sw6::fq3::bench_fq3_sqrt                                         3,321,726    3,201,614        -120,112   -3.62%   x 1.04 
 sw6::fq3::bench_fq3_square                                       1,696        1,645                 -51   -3.01%   x 1.03 
 sw6::fq3::bench_fq3_sub_assign                                   67           66                     -1   -1.49%   x 1.02 
 sw6::fq6::bench_fq6_add_assign                                   144          114                   -30  -20.83%   x 1.26 
 sw6::fq6::bench_fq6_double                                       96           96                      0    0.00%   x 1.00 
 sw6::fq6::bench_fq6_inverse                                      58,863       50,288             -8,575  -14.57%   x 1.17 
 sw6::fq6::bench_fq6_mul_assign                                   7,118        6,819                -299   -4.20%   x 1.04 
 sw6::fq6::bench_fq6_square                                       5,248        4,976                -272   -5.18%   x 1.05 
 sw6::fq6::bench_fq6_sub_assign                                   131          127                    -4   -3.05%   x 1.03 
 sw6::fq::bench_fq_add_assign                                     22           19                     -3  -13.64%   x 1.16 
 sw6::fq::bench_fq_double                                         16,932       17,126                194    1.15%   x 0.99 
 sw6::fq::bench_fq_from_repr                                      245          248                     3    1.22%   x 0.99 
 sw6::fq::bench_fq_into_repr                                      138          132                    -6   -4.35%   x 1.05 
 sw6::fq::bench_fq_inverse                                        50,218       38,487            -11,731  -23.36%   x 1.30 
 sw6::fq::bench_fq_mul_assign                                     242,531      240,596            -1,935   -0.80%   x 1.01 
 sw6::fq::bench_fq_negate                                         24           22                     -2   -8.33%   x 1.09 
 sw6::fq::bench_fq_repr_add_nocarry                               14           14                      0    0.00%   x 1.00 
 sw6::fq::bench_fq_repr_div2                                      15           7                      -8  -53.33%   x 2.14 
 sw6::fq::bench_fq_repr_mul2                                      9            13                      4   44.44%   x 0.69 
 sw6::fq::bench_fq_repr_num_bits                                  4            3                      -1  -25.00%   x 1.33 
 sw6::fq::bench_fq_repr_sub_noborrow                              17           17                      0    0.00%   x 1.00 
 sw6::fq::bench_fq_sqrt                                           526,690      518,031            -8,659   -1.64%   x 1.02 
 sw6::fq::bench_fq_square                                         208,952      210,092             1,140    0.55%   x 0.99 
 sw6::fq::bench_fq_sub_assign                                     19           19                      0    0.00%   x 1.00 
 sw6::fr::bench_fr_add_assign                                     10           10                      0    0.00%   x 1.00 
 sw6::fr::bench_fr_double                                         9,174        9,065                -109   -1.19%   x 1.01 
 sw6::fr::bench_fr_from_repr                                      58           38                    -20  -34.48%   x 1.53 
 sw6::fr::bench_fr_into_repr                                      32           31                     -1   -3.12%   x 1.03 
 sw6::fr::bench_fr_inverse                                        13,712       17,668              3,956   28.85%   x 0.78 
 sw6::fr::bench_fr_mul_assign                                     50,664       30,005            -20,659  -40.78%   x 1.69 
 sw6::fr::bench_fr_negate                                         13           14                      1    7.69%   x 0.93 
 sw6::fr::bench_fr_repr_add_nocarry                               8            10                      2   25.00%   x 0.80 
 sw6::fr::bench_fr_repr_div2                                      6            6                       0    0.00%   x 1.00 
 sw6::fr::bench_fr_repr_mul2                                      5            13                      8  160.00%   x 0.38 
 sw6::fr::bench_fr_repr_num_bits                                  4            3                      -1  -25.00%   x 1.33 
 sw6::fr::bench_fr_repr_sub_noborrow                              9            11                      2   22.22%   x 0.82 
 sw6::fr::bench_fr_sqrt                                           77,926       54,407            -23,519  -30.18%   x 1.43 
 sw6::fr::bench_fr_square                                         42,764       30,561            -12,203  -28.54%   x 1.40 
 sw6::fr::bench_fr_sub_assign                                     11           10                     -1   -9.09%   x 1.10 
 sw6::pairing::pairing::bench_pairing_final_exponentiation        8,881,217    8,317,250        -563,967   -6.35%   x 1.07 
 sw6::pairing::pairing::bench_pairing_full                        97,824,713   86,015,907    -11,808,806  -12.07%   x 1.14 
 sw6::pairing::pairing::bench_pairing_miller_loop                 88,591,942   77,475,292    -11,116,650  -12.55%   x 1.14

opened by jon-chuang 19

program crash when the number of constraints is too large

Hello. I use LibZEXE to build a large zk project of more than 10 million constraints. However, even on a 256GB memory machine, the program crashes during create_random_proof(). Emperically, the largest circuit I can create proof for is around 5 million constraints. I feel like libzexe is not very memory-efficient. Do you have any suggestions on saving memory when building and creating proof for extremely large circuits? Thanks!

opened by brucechin 18
Goff for mul_assign + field implementation macro + cheaper into_repr

Added goff (for mul_assign only) + macros to simplify code Have not added requirements on the prime fields/alternate montgomery multiplication for primes not satisfying requirements (https://hackmd.io/@zkteam/modular_multiplication)

opened by jon-chuang 16

Pedersen hash doesn't seem to work with bls12-377 curve

When using a Pedersen hash (primitive and gadget) with the following parameters:

pub type CRH = PedersenCRH<bls12_377::G1Projective, CRHWindow>;

#[derive(Clone, PartialEq, Eq, Hash)]
pub struct CRHWindow;

impl PedersenWindow for CRHWindow {
    const WINDOW_SIZE: usize = 128;
    const NUM_WINDOWS: usize = 8;
}

pub type CRHGadget = PedersenCRHGadget<bls12_377::G1Projective, bls12_377::Fq, bls12_377::G1Gadget>;

pub type CRHGadgetParameters = <CRHGadget as FixedLengthCRHGadget<CRH, bls12_377::Fq>>::ParametersGadget;

The gadget and the primitive output different points even when given the same input. The tests crh_works and crh_primitive_gadget_test fail. Weirdly enough, the tests pass with Jujub.

T-bug

opened by brunoffranca 15

Replace many impls of `(Add|Mul|AddAssign|MulAssign)` with derive macros

The derive macros defer to the versions implemented on Self-type references. This eliminates a lot of the impl boilerplate (& might go away when Rust figures out how to to autoref/deref on operators).

Hopefully this also serves as inspiration for extension of the approach to Sub, Neg ...

opened by huitseeker 14
Add point compression + canonical serialization for `AffineCurve` elements
This is one of the critical missing pieces for this library. A sketch of the design I have in mind is to make CanonicalSerialize and CanonicalDeserialize traits:

pub trait CanonicalSerialize { type Output: Iterator<Item = u8> fn serialize(&self) -> Output; } pub trait CanonicalDeserialize: CanonicalSerialize { fn deserialize(&Self::Output) -> Self; }

The idea would then be to implement these directly for the final instantiated curves, e.g. for Bls12_381_G1. (I don't see an easy way to have a generic implementation that works for all base fields.)
opened by Pratyush 14
Mixed-radix FFT & Recursive SNARKs example
This PR builds & depends on #177.

Motivation for the mixed-radix FFT

The radix-2 FFT that currently comes with zexe only works for a number of constraints + inputs below 2^TWO_ADICITY of the Fr field one is proving on (considering Groth16). For MNT6-753 that means we can have a maximum of 2^15 (constraints+inputs). Unfortunately, this is not enough to verify another Groth16 proof in a circuit.

The mixed-radix FFT allows to increase this number to 2^15*5^2 for MNT6-753 using a small subgroup with base 5 and power 2, which is more than enough for the previous motivational example.

Other implementations

Inspired by https://github.com/o1-labs/snarky/pull/107, which adds a mixed-radix FFT to libfqfft, I added a mixed-radix FFT to zexe's FFT implementation. It turned out that ginger-lib implemented the same mixed-radix FFT concurrently here: https://github.com/ZencashOfficial/ginger-lib/pull/34

The main difference to the ginger-lib implementation is that they split up the two FFTs into separate structs, while I followed Snarky's example and put both of them into the single EvaluationDomain struct we have right now.

Preliminary results

I already ran some examples using recursive SNARKs on the MNT4/6-753 curves and here are some results:

MNT6_753 curve, 151,138 constraints, mixed-radix FFT Average setup time: 80.412886252 seconds Average proving time: 54.170403498 seconds MNT4_753 curve, 276,480 constraints, radix-2 FFT Average setup time: 104.938389255 seconds Average proving time: 83.827640713 seconds

While the numbers are not directly comparable, they suggest that the mixed-radix FFT (at least for this subgroup) doesn't add a substantial overhead. However, I also want to implement more comparable benchmarks (see TODOs).

TODOs

Since we might want to add other FFT variants in the future (e.g., using the radix-2 with multiple cosets), I still want to do the following improvements before this is ready to merge:

[x] Split up the two FFT variants while avoiding code duplication (so something similar to what ginger-lib did).

[x] Add benchmarks for the FFT variants

More feedback welcome. :)
opened by paberr 13

Prepare Zexe for recursion

Updated. This is a bundle of changes to prepare Zexe for recursion. This PR consists of several independent changes:

Add the CycleEngine, which some of us may have heard of. This is to represent a cycle of pairing-friendly curves.

/// A cycle of pairing-friendly elliptic curves.
pub trait CycleEngine:
    Sized
    + 'static
    + Copy
    + Debug
    + Sync
    + Send
where
    <Self::E2 as PairingEngine>::G1Projective: MulAssign<<Self::E1 as PairingEngine>::Fq>,
    <Self::E2 as PairingEngine>::G2Projective: MulAssign<<Self::E1 as PairingEngine>::Fq>,
{
    type E1: PairingEngine;
    type E2: PairingEngine<
        Fr = <Self::E1 as PairingEngine>::Fq,
        Fq = <Self::E1 as PairingEngine>::Fr,
    >;
}

Add a prepared verifier inNIZKVerifierGadget and implement it for Groth16 and GM17.
Add a new trait ToConstraintFieldGadget and implement it for a number of group and field types.

pub trait ToConstraintFieldGadget<ConstraintF: PrimeField> {
    fn to_field_gadgets<CS: ConstraintSystem<ConstraintF>>(
        &self,
        cs: CS,
    ) -> Result<Vec<FpGadget<ConstraintF>>, SynthesisError>;
}

opened by weikengchen 12

Build Failed: use of unstable library feature 'array_from_fn'

Summary of Bug

error[E0658]: use of unstable library feature 'array_from_fn'
   --> /root/.cargo/git/checkouts/algebra-7e23afa68841b66e/d3e888d/serialize/src/impls.rs:415:22
    |
415 |         let result = core::array::from_fn(|_| {
    |                      ^^^^^^^^^^^^^^^^^^^^
    |
    = note: see issue #89379 <https://github.com/rust-lang/rust/issues/89379> for more information

For more information about this error, try `rustc --explain E0658`.
error: could not compile `ark-serialize` due to previous error
warning: build failed, waiting for other jobs to finish...
error: build failed

Version

commit f6df807ea8e3051980bc79e8706b8a9b03f48b1c Update ark-snark to ark-algebra (#366)

Steps to Reproduce

Run build with cargo build --release

Please suggestion a solution for this issue as I am new to Rust and Arkworks. Thank you!

opened by yuquan1210 5

Toward non-cryptographer developer-ready arkworks-rs
Summary

This is a general-purpose issue talking about the possibility of making arkworks-rs easier to be used by general developers.

Problem Definition

There has been a lot of work in DSL for zkVM/zkEVM. I always have doubts and feel that writing in Rust directly can be beneficial.

Many research articles talk about the benefits of DSL, but this very website, called "GitHub", basically shows that DSL often has low adoption.

Instead of building a language that requires a separate compilation stage, we see a lot of success in providing SDK on a mature language.

Microsoft Visual Studio: MFC/ATL/WTL

Minecraft has a lot of success in third-party plugins, thanks to Forge and Fabric

And probably the best evidence is that many people who watched this repo or starred this repo deploy ZK applications in Rust.

So, I think arkworks-rs has a special space in the ZKP application development area. A long-term, and probably more HCI-related topic, is to make this library easier to be used by new developers.

For the record, the first step is probably just ark-simple-names which imports ark-relations/r1cs and replace names to some simpler ones.

Proposal

Have some to-do items to gradually improve usability.

For Admin Use

[x] Not duplicate issue

[x] Appropriate labels applied

[ ] Appropriate contributors tagged

[ ] Contributor assigned/self-assigned

T-design D-hard P-medium
opened by weikengchen 1
Fast-track constraint system assembly for the prover
Summary

The LC inlining time seems to be taking a significant portion of the proof generation. Yet, we know that the result can be cached or included in the proving key with some care. In that case, we may allow the prover to finish the construction of the constraint system in a fast-track manner.

This is also important for hardware-software codesign.

Problem Definition

See if there is a systematic way to allow the prover to get some precomputation from the indexer, so it can save the time in constraint assembly and LC inlining.

Proposal

Make the LC result serializable. Think about a general-purpose framework for loading the prover parameters from files.

For Admin Use

[x] Not duplicate issue

[x] Appropriate labels applied

[x] Appropriate contributors tagged

[x] Contributor assigned/self-assigned

D-hard T-performance P-medium
opened by weikengchen 0
Revisiting `transform_lc_map`
Summary

I may hire someone to do a pass over transform_lc_map to see if we can make it faster.

See the following breakdown.

Start: Groth16::Prover ··Start: Constraint synthesis ··End: Constraint synthesis ....................................................25.365s ··Start: Inlining LCs ··End: Inlining LCs ............................................................59.181s ··Start: R1CS to QAP witness map ··End: R1CS to QAP witness map .................................................28.268s ··Start: Compute C ··End: Compute C ...............................................................48.037s ··Start: Compute A ··End: Compute A ...............................................................3.444s ··Start: Compute B in G1 ··End: Compute B in G1 .........................................................2.373s ··Start: Compute B in G2 ··End: Compute B in G2 .........................................................5.497s ··Start: Finish C ··End: Finish C ................................................................9.339µs End: Groth16::Prover ...........................................................172.293s Proof generation for one proof: 178.148426339

Problem Definition

The time transform_lc_map takes seems to be too high. In addition, we may want to see if it can be made parallel.

Proposal

Get a professional analysis of this code.

For Admin Use

[x] Not duplicate issue

[x] Appropriate labels applied

[x] Appropriate contributors tagged

[x] Contributor assigned/self-assigned

D-hard T-performance P-medium
opened by weikengchen 3
Toward application-specific reduction such as TurboPlonk and Halo2
Summary

We may need to get some clarity in how to enable arkworks-rs to support a large class of Plonk implementation and their variants.

Problem Definition

Implementing a specific version of Plonk, or providing a standard implementation like zk-Garage efforts (https://github.com/ZK-Garage/plonk), does not actually appeal to me very much.

I see a trend that different applications and systems will design different Plonk. For example, Rescue can be very efficient if the powering is made into a customized gate type. For example, twisted Edwards curve operations can be made efficient as well.

Customized gates are basically using FFT to exchange for fewer MSM. It also has a lot to do with sparsity when Lagrange bases are used.

The current use of TurboPlonk already goes beyond the notion of "gates". For example, one can add binary checking over existing wires of a gate, by playing with the polynomials. Halo2 can also do this as well.

This leads to a question:

What would be a (Turbo)Plonk interface that would be suitable for a large number of Plonk variants?

Proposal

This would just be the beginning and followup of #155 discussion.

First, we probably should start with finding a way to have Halo2 in arkworks-rs, as it has a very comprehensive implementation of PLONKish, and our work would be mostly filling in gadgets, i.e., instead of "r1cs-std" we would have "plonkish-std".

This is likely going to be a separate implementation, since Halo2 does not need to, and probably should not, be built over arkworks-rs since it already has its own foundation. So, a question is: how stable or finalized Halo2 is? (@daira)

Second, Jordi Baylina (@jbaylina) has been working on polynomial identity language (PIL) which seems to be closer to the different Plonk variants that are not plonkish, which is here: https://github.com/0xpolygonhermez/pilcom

This is a step that arkworks-rs needs to go sooner or later.

For Admin Use

[x] Not duplicate issue

[x] Appropriate labels applied

[x] Appropriate contributors tagged

[x] Contributor assigned/self-assigned

T-feature T-design D-hard P-medium
opened by weikengchen 3
`PartialOrd` for `Variable` violates `transitivity` and `duality` properties
Summary of Bug

PartialOrd for Variable violates transitivity and duality properties.

This code prints both 0<1 and 1<0.

See playground for example:

one is Some(Less) than zero zero is Some(Less) than one

Version

v0.3.0 8bb375e51be184d495c82969bd1d9a3f8fe7d27a

Steps to Reproduce

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=51b860bb4a8854d6636e740e8be1c9ce
opened by BoyuanFeng 0

Releases(v0.3.0)

v0.3.0(Jun 6, 2021)

Source code(tar.gz)
Source code(zip)

Interfaces for Relations and SNARKs for these relations

Related tags

Overview

SNARK and Relation Traits

Directory structure

Overview

Build guide

Tests

License

Acknowledgements

Comments

Motivation for the mixed-radix FFT

Other implementations

Preliminary results

TODOs

Summary of Bug

Version

Steps to Reproduce

Summary

Problem Definition

Proposal

For Admin Use

Summary

Problem Definition

Proposal

For Admin Use

Summary

Problem Definition

Proposal

For Admin Use

Summary

Problem Definition

Proposal

For Admin Use

Summary of Bug

Version

Steps to Reproduce

Releases(v0.3.0)

v0.3.0(Jun 6, 2021)

Owner

arkworks

Making composability with the Zeta DEX a breeze, FuZe provides CPI interfaces and sample implementations for on-chain program integration.

IBC modules and relayer - Formal specifications and Rust implementation

Diem’s mission is to build a trusted and innovative financial network that empowers people and businesses around the world.

Fast and efficient ed25519 signing and verification in Rust.

A safe implementation of the secure remote password authentication and key-exchange protocol (SRP), SRP6a and legacy are as features available.

Retrieving SSH and GPS keys from GitHub and GitLab

Terabethia - A Bridge and Messaging Protocol between Ethereum and the Internet Computer.

A guide for Mozilla's developers and data scientists to analyze and interpret the data gathered by our data collection systems.

Diem’s mission is to build a trusted and innovative financial network that empowers people and businesses around the world.

Complete Ethereum and Celo wallet implementation and utilities in Rust

Library with support for de/serialization, parsing and executing on data-structures and network messages related to Bitcoin

Fiddi is a command line tool that does the boring and complex process of checking and processing/watching transactions on EVM compatible Blockchain.

Selendra is a multichains interoperable nominated Proof-of-Stake network for developing and running Substrate-based and EVM compatible blockchain applications.

Confidential credit scores and loan disbursal, powered by zkSNARKs and NEAR Protocol

A fast, simple and powerful open-source cross platform utility tool for generating strong, unique and random passwords

An extensible and practical demonstration of constructing evm-based sandwich attacks built with ethers-rs and Huff language.

Simple node and rust script to achieve an easy to use bridge between rust and node.js

A simple and secure rust command-line tool to protect your text by encrypting and decrypting it using the robust AES-256 algorithm.

reth-indexer reads directly from the reth db and indexes the data into a postgres database all decoded with a simple config file and no extra setup alongside exposing a API ready to query the data.