zk-garage/plonk

A pure Rust PLONK implementation using arkworks as a backend.

PLONK

This is a pure rust implementation of various zkp components by the ZK-Garage team

About

This a library currently contains several modules

The plonk-core module is an implemention of the PLONK proving system, that leverages custom gates and lookups to significantly enhance performance and lower constraint count to optimise the generation of zero knowledge proofs. The backend of the plonk-core module is designed to be compatible with the arkworks suite. By leveraging the operations in arkworks we have optimised algebra and generic trait abstractions for curve types, allowing users to define their SNARK over different curves and, if applicabale, utilise embedded or pairing curves. The polynomial commitment scheme is also generic, which allows users to implement differing PCSs dependent upon particular needs.

The plonk-hashing module is set to contain several hashing algorithms, commencing with an optimised implementation of the Poseidon hashing algorithm generic for both plonk-style arithmetic representation and R1CS. Which will be extended but not limited to Reinforced Concrete and Blake2s.

The plonk-book is a module which contains a detailed overview of the working parts within a EC based ZKP system, with explanation of some of the characteristics particular to PLONK, e.g. Lagrange bases. There is a also a chapter on the construction of the PLONK algorithms, as well as an explanation of the implementations features and details specific to this repository.

Compile the Plonk book

First, you need to install mdbook command line tool used to create books with Markdown.

cargo install mdbook

You should also install Katex preprocessor which renders Latex equations into HTML at build time

cargo install --git "https://github.com/lzanini/mdbook-katex"

Then, you build the book as follows:

mdbook build

Last but not least, you can read the book by doing this command

mdbook serve --open

This will display the book in your default web browser after building it.

Join the effort

Please, if you're interested in collaborating, contributing or just discussing, you can join our Discord here: https://discord.gg/XWJdhVf37F

Features

This crate includes a variety of features which will briefly be explained below:

• parallel: Enables rayon and other parallelisation primitives to be used and speed up some of the algorithms used by the crate and it's dependencies.

• asm: Enables inline-assembly implementations for some of the internal algorithms and primitives used by the arkworks dependencies of the crate.

• trace: Enables the Circuit debugger tooling. This is essentially the capability of using the StandardComposer::check_circuit_satisfied function. The function will output information about each circuit gate until one of the gates does not satisfy the equation, or there are no more gates. If there is an unsatisfied gate equation, the function will panic and return the gate number.

• trace-print: Goes a step further than trace and prints each gate component data, giving a clear overview of all the values which make up the circuit that we're constructing. The recommended method is to derive the std output, and the std error, and then place them in text file which can be used to efficiently analyse the gates.

Documentation

There are two main types of documentation in this repository:

• Crate documentation. This provides info about all of the functions that the library provides, as well as the documentation regarding the data structures that it exports. To check this, please feel free to go to the documentation page or run make doc or make doc-internal.

• Notes. This is a specific subset of documentation which explains the key mathematical concepts of PLONK and how they work with mathematical demonstrations. To check it, run make doc and open the resulting docs, which will be located under /target/doc/plonk/index.html with your browser.

  Examples. Examples can be found in the examples folder. Run them, e.g., via cargo run --example simple_circuit.

Performance

Benches taken running: RUSTFLAGS='-C target-cpu=native' cargo bench with an AMD Ryzen 7 3700X These benches use the Bls12-381 curve.

Using KZG10 commitments:

Compile:
2^5         [    17.632 ms      17.669 ms      17.696 ms]
2^6         [    22.666 ms      22.702 ms      22.747 ms]
2^7         [    29.618 ms      29.653 ms      29.719 ms]
2^8         [    47.467 ms      47.556 ms      47.609 ms]
2^9         [    65.458 ms      65.786 ms      66.174 ms]
2^10        [    97.172 ms      97.514 ms      97.897 ms]
2^11        [   167.89  ms     168.17  ms     168.41  ms]
2^12        [   314.51  ms     314.65  ms     314.78  ms]
2^13        [   526.59  ms     527.63  ms     529.18  ms]
2^14        [ 1.0238     s   1.0253     s   1.0272     s]
2^15        [ 2.0029     s   2.0088     s   2.0143     s]
2^16        [ 3.7727     s   3.7846     s   3.7955     s]
2^17        [ 6.7340     s   6.7523     s   6.7700     s]
2^18        [13.584      s  13.613      s  13.640      s]

Prove:
2^5         [    16.172 ms      16.208 ms      16.264 ms]
2^6         [    21.676 ms      21.712 ms      21.748 ms]
2^7         [    29.493 ms      29.545 ms      29.613 ms]
2^8         [    48.970 ms      49.039 ms      49.104 ms]
2^9         [    72.251 ms      72.533 ms      72.703 ms]
2^10        [   128.89  ms     130.71  ms     132.10  ms]
2^11        [   242.91  ms     247.74  ms     252.29  ms]
2^12        [   455.79  ms     459.45  ms     462.85  ms]
2^13        [   776.94  ms     781.89  ms     787.94  ms]
2^14        [ 1.4752     s   1.4824     s   1.4893     s]
2^15        [ 2.8589     s   2.8682     s   2.8787     s]
2^16        [ 5.4610     s   5.4766     s   5.4927     s]
2^17        [10.078      s  10.118      s  10.159      s]
2^18        [20.151      s  20.184      s  20.216      s]

Verify:
2^5         [    5.5250 ms      5.5560 ms      5.5983 ms]
2^6         [    5.4933 ms      5.5461 ms      5.5910 ms]
2^7         [    5.5678 ms      5.6002 ms      5.6247 ms]
2^8         [    5.5391 ms      5.5756 ms      5.6027 ms]
2^9         [    5.5421 ms      5.5648 ms      5.5929 ms]
2^10        [    5.5423 ms      5.5825 ms      5.6240 ms]
2^11        [    5.5269 ms      5.5576 ms      5.6027 ms]
2^12        [    5.5624 ms      5.6081 ms      5.6623 ms]
2^13        [    5.6288 ms      5.6656 ms      5.6914 ms]
2^14        [    5.6068 ms      5.6186 ms      5.6292 ms]
2^15        [    5.5930 ms      5.6241 ms      5.6543 ms]
2^16        [    6.0845 ms      6.1324 ms      6.1745 ms]
2^17        [    6.5760 ms      6.5896 ms      6.6030 ms]
2^18        [    8.1152 ms      8.1481 ms      8.1710 ms]

Using IPA commitments:

Compile:
2^5         [    16.768 ms      16.818 ms      16.857 ms]
2^6         [    21.958 ms      21.977 ms      21.993 ms]
2^7         [    28.847 ms      28.869 ms      28.903 ms]
2^8         [    47.626 ms      47.660 ms      47.693 ms]
2^9         [    67.319 ms      67.485 ms      67.674 ms]
2^10        [    98.526 ms      98.891 ms      99.072 ms]
2^11        [   171.84  ms     172.06  ms     172.25  ms]
2^12        [   322.42  ms     322.55  ms     322.69  ms]
2^13        [   533.50  ms     533.95  ms     534.53  ms]
2^14        [ 1.0333     s   1.0342     s   1.0351     s]
2^15        [ 2.0156     s   2.0240     s   2.0308     s]
2^16        [ 3.8668     s   3.8769     s   3.8871     s]
2^17        [ 6.8066     s   6.8259     s   6.8506     s]
2^18        [13.757      s  13.773      s  13.788      s]

Prove:
2^5         [    32.205 ms      32.802 ms      33.418 ms]
2^6         [    39.419 ms      39.479 ms      39.550 ms]
2^7         [    53.665 ms      53.767 ms      53.876 ms]
2^8         [    83.829 ms      84.005 ms      84.171 ms]
2^9         [   127.58  ms     127.85  ms     128.11  ms]
2^10        [   207.01  ms     208.50  ms     210.09  ms]
2^11        [   397.91  ms     400.53  ms     403.63  ms]
2^12        [   719.49  ms     725.85  ms     732.68  ms]
2^13        [ 1.2864     s   1.2912     s   1.2953     s]
2^14        [ 2.4494     s   2.4552     s   2.4620     s]
2^15        [ 4.7411     s   4.7617     s   4.7826     s]
2^16        [ 9.1925     s   9.2148     s   9.2360     s]
2^17        [17.499      s  17.584      s  17.660      s]
2^18        [35.019      s  35.084      s  35.138      s]

Verify:
2^5         [    7.9861 ms      8.0159 ms      8.0433 ms]
2^6         [    8.9787 ms      9.0031 ms      9.0272 ms]
2^7         [   10.648  ms     10.675  ms     10.714  ms]
2^8         [   13.466  ms     13.526  ms     13.596  ms]
2^9         [   17.140  ms     17.188  ms     17.267  ms]
2^10        [   25.379  ms     25.574  ms     25.785  ms]
2^11        [   34.424  ms     37.413  ms     38.720  ms]
2^12        [   39.254  ms     39.429  ms     39.595  ms]
2^13        [   69.872  ms     70.392  ms     70.790  ms]
2^14        [  130.16   ms    130.93   ms    131.90   ms]
2^15        [  243.71   ms    246.59   ms    249.40   ms]
2^16        [  409.56   ms    415.00   ms    419.81   ms]
2^17        [  777.07   ms    789.39   ms    801.28   ms]
2^18        [1.4931      s  1.4999      s  1.5065      s]

Acknowledgements

• Reference implementation by Aztec Protocol
• Initial implementation of PLONK with arkworks backend was done years before this lib existed by Kobi Gurkan
• Initial rust implementation of PLONK by Dusk Network, originally forked from dusk-network/plonk

Licensing

This software is distributed under the terms of Mozilla Public License Version 2.0 (MPL-2.0). Please see LICENSE for further info.

Contributing

• If you want to contribute to this repository/project please, check CONTRIBUTING.md
• If you want to report a bug or request a new feature addition, please open an issue on this repository.

plonk's Issues

Add back original `commitment-scheme` KZG10 module

Implement a modularised version of the KZG10 commitment scheme to work with commitments in PLONK

Fix broken doc link

The broken link is coming from the plonk-book. We need investigation into why it won't work.

At the moment it is a blocker so we will ignore the infra-link on the PR's

cc: @CPerezz @mathcrypto @markulf

Improve `linearisation_poly` code

There are some changes that could be made in order to improve the code of linearisation_poly.rs in terms of readability:

• Clearer variable names: Have more descriptive names instead of potentially ambiguous or confusing names (a, b, c, f_1, etc.)
• Descriptive function names: Try to reflect more accurately the purpose of the functions in its names
• Code comments: Add comments detailing which polynomials/ equations are being constructed and other clarifications when necessary

Commitment Gadget Design

Commitment Gadget Design

Goal

Make a commitment gadget library based on ark-plonk.

Initial Design

We still need those features:

• A two-to-one hash:

  • candidate 1: Poseidon Hash (Used as Leaf Hash, or arity-2/ arity-4 hash)
  • candidate 2: Reimforcement-Concrete

• Two commitment schemes

  1. take a single scalar as input, output a group element
  2. take a bitarray as input, output a scalar

• Commitment Scheme using API like this (native and constraints)

trait Commitment{
    type Input;      //i.e. bitarray, a single scalar
    type Output;     //i.e. a single scalar, or a group element
    type CommitKey;
    type VerifyKey;
    type Proof;
    type Parameters;
    
    fn setup(...);
    fn commit<R: Rng>(parameters: &Parameters, ck: &CommitKey, input: &Input, rng: &mut R) -> Output;
    fn open(parameters: &Parameters,ck: &CommitKey, input: &Input, output: &Output) -> Proof;
    fn verify(parameters: &Parameters, vk: VerifyKey, input: &Input, output: &Output, proof: &Proof) -> bool;
}

• Choice Merkle Tree Leaf Hash that matches the output of Manta's commitment

trait LeafHash{
    type Input; 
    type Output;
    
    fn setup(...);
    fn evaluate(input: &Input) -> Output;
}

Questions:

• Can we design the trait that fits both native and constraints?

Implement PLONKup

This issue will include the addition of lookups into the code via the plonkup proving system.

Plonk Book / Implementation Documentation

Add an extensive documentation in the style of Halo2 Book.
It should contain:

• Theoretical background and explanation of Plonk
• Details of the implementation including: description of the structures and traits, complexitites of the main operations, differences from the original protocol, etc.
• Examples of use

The purpose of the book should be to allow new developers to learn how to use this library in the easiest way possible.

Find workarround for bitshifting ops in logic gate assertion.

Originally posted by @CPerezz in #61 (comment)

"Traitify" the VerifierKey composition process

We currently have our VerifierKey being built by small aggregations of each custom-gate component, which "aggregates" it's VerifierKey piece into the general VerifierKey structure.

We should re-think this and implement a better solution, probably based on traits. That helps to reduce code and also to make more clear the codebase.

See: https://github.com/rust-zkp/ark-plonk/blob/master/src/proof_system/widget/mod.rs#L30-L48

Implement tests for the transcript

At the moment, the amount of challenges on the transcript is not checked. All the transcripts are being generated, however only beta is appended. This does not cause failures as the challenges only need to equal in number and name for the prover & verifier - which they do.

The test should check that the number of challenges matches the spec.

Update and extend documentation for crate exported structures and Readme

Replace `kzg10` with generic polynomial commitment scheme

Replace the commitment_scheme module that provides kzg10 commitments with ark_poly_commit to enable the use of other polynomial commitment schemes.

Consolidate naming for arithmetic Composer gates

I see the naming convention as follows:

• The methods that have a _gate sufix (add_gate, mul_gate...) do not compute values, they receive as input the relevant wire values and selectors of the gate and check that the equation holds.
  The methods that do not have the _gate sufix (add, mul...) compute the output value w_o and always generate a satisfied constraint.
• The methods with big_ prefix receive a 4th wire, those without the prefix don´t.

I think big_arith and big_arith_gate fit in the same family as poly_gate so we should choose a common name for all of them: poly or arith.

Originally posted by @davidnevadoc in #43 (comment)

Circuit and gadget hashing

We should have some way of hashing circuits/constraint systems/gadgets/etc, and then when they stabilize, create tests to pin each to their exact instantiation to ensure any unintended changes are detectable.

Improve circuit debugging with a MockProver approach `a la Halo2`

In Halo2 we have a fantastic tool for circuit-debugging purposes. The MockProver. It basically allows to check all the gate-constraints and Lookup errors returning a really accurated description of the error place and the values involved in it.

The idea is to do something similar. Which at the same time, aims to reduce testing-time since it does not actually perform any commitments or requires any setup.

See more details here: https://github.com/zcash/halo2/blob/d111807798d4719df36dc2b05b0104b69efdceb3/halo2_proofs/src/dev.rs#L465

Add benchmarks for the crate

Once #10 is completed, we should think about adding benchmarks and take some numbers to see how the proving and verification processes perform.

And expose the results extracted from Criterion in the README.md

Add blinder polynomials

The Plonk protocol provides zero-knowledge by adding random multiples of the vanishing polynomial Z_H (referred as blinder polynomials) to the witness based polynomials: The wire polynomials + permutation polynomial.

We should add these blinders.

Better Test Framework / Making `gadget_tester` Public

I really like the gadget_tester in ark-plonk, which makes writing end-to-end tests much easier, but this gadget is pub(crate) so user cannot access it...

I believe many users will end up writing their own gadgets (for gadgets, I mean any function that includes StandardComposer as a parameter). Can we make the following public:

• gadget_tester
• batch_test!

If there is any reason that prevents doing so, shall we have a good testing framework? Writing end-to-end tests for a gadget from scratch is a bit verbose.

Thanks!

Remove ProjectiveCurve constraint from StandardComposer

As said by @Pratyush

you don't need to bound by both C: ProjectiveCurve and P: TEParameters; you can access the Edwards curve
corresponding to the parameters by doing TEProjective

(You can still match the fields up by doing E: PairingEngine<Fr = P::ScalarField>

Therefore, we should proceed on that way and save a trait bound in the Composer struct.

Derive the Minimal Quotient Polynomial

A given concrete circuit may only use a subset of the custom-gate functionality available to the proof system. This can be detected whenever some selectors are all zero throughout the circuit. More generally, if a selector is nonzero but constant throughout the circuit, we can also reduce the complexity of the quotient polynomial. This is a step towards the fully customizable system where users can design their own custom gates and the proof system will select the subset of custom gates which are used in any concrete circuit.

Move the crate to 2018 and 2021 edition guidelines

The crate is based on the Rust 2015 edition now.

We should aim to be compatible with the newest editions such as 2018 and 2021.
Also, adding lints for them could be really useful.

Implement KZG commitments in Lagrange basis

KZG commitments typically use a monomial basis for its structured reference string (SRS). By switching to a Lagrange basis for the SRS we can avoid computing an iFFT for each commitment.

Monomial basis KZG

For secret scalar s and group generator G we have {G, sG, s^2G, ... , s^nG}

Lagrange basis KZG

For secret scalar s and group generator G we have {L_0(s)G, L_1(s)G, L_2(G), ...., L_{n-1}(s)G} where L_k is the kth Lagrange basis polynomial over the domain H, where H is a multiplicative subgroup generated by w. That is, L_k is the polynomial for which L_k(w^k) = 1 but takes the value 0 on all other powers of w.

If the SRS is in Lagrange form (evaluation form), committing to a polynomial that is also in evaluation form is just a multi-scalar multiplication and an iFFT does not need to be performed. Justin Drake refers to this trick in this ZK Study Club talk: https://www.youtube.com/watch?v=TbNauD5wgXM

Changes to be made in ark-plonk

All commitments would need to be modified so that they no longer perform an iFFT before committing if the SRS is in Lagrange form.

Changes to be made elsewhere

KZG setup and commit functions will need to be changed in ark-poly-commit to support Lagrange form setup and commitment

Possibilities

It may be possible to to convert an SRS that was created in monomial form into one in Lagrange form. This might be a major computation but would only need to be done once per setup.

Add transformation functions between outer and embedded curve scalars

All variables in the circuit are viewed as the pairing friendly curve scalars regardless of their function (i.e. wire values, coordinates of an embedded curve point or embedded curve scalars).
It is necessary to implement safe transformations between these two types so that the embedded curve scalars can be used in scalar-point multiplications and as variables in the circuit.

Refactor Gadget definition strategy to treat it as a `Gate` or `Collection of Gates`

With this change, it would be possible to add &str definitions for each gate created which can be used for debugging purposes later on.

The idea is to end up with something much closer and that is better handled in other libs such as Halo2 which looks like:

meta.create_gate("R1CS constraint", |meta| {
             let a = meta.query_advice(a, Rotation::cur());
             let b = meta.query_advice(b, Rotation::cur());
             let c = meta.query_advice(c, Rotation::cur());
             let s = meta.query_selector(s);

             // BUG: Should be a * b - c
             Some(("buggy R1CS", s * (a * b + c)))
         });

Which enables producing better err messages while debugging like:

Err(vec![VerifyFailure::ConstraintNotSatisfied {
constraint: ((0, "R1CS constraint").into(), 0, "buggy R1CS").into(),
location: FailureLocation::InRegion {
region: (0, "Example region").into(),
offset: 0,
},

That overall should help to:

• Gadget composability
• Gadget/circuit debugging (#101 )

Compile (but not run) benchmarks on each CI trigger

@bhgomes, does the benches/plonk.rs compile on your machine?

Originally posted by @LukePearson1 in #49 (comment)

Book deployment workflow not working

After the merge of #55 the deployment of the Book is not working.
This should be fixed before moving to a workspace

Remove docs folder

As @markulf pointed out, there are outdated docs in the repo.

The current changes to ark-plonk should better reflect the theory implementation.

Does not compile to WASM

This repo is strictly pegged to std dependencies, unlike most other Arkworks repositories. Is anyone working on compiling this in WASM?

Fix dependency error

The current BLS12-381 import is broken, this is in the examples folder sample circuit.

Implement De/Serialization for exported crate's data structures

See: https://docs.rs/ark-serialize/0.3.0/ark_serialize/trait.CanonicalSerialize.html

This should target:

• Proof
• KZGProof
• OpeningKey
• ProverKey
• CommitKey
• VerifierKey
• PublicParameters
• VerifierData

Error handling for InvalidEvalDomain improvement

We should do something like:

.ok_or(Error::InvalidEvalDomainSize {
                log_size_of_group: plonk_verifier_key.n.trailing_zeros(),
                adacity: <F as FftField>::FftParams::TWO_ADACITY,
            })?

instead of unwrap() but I'm having some issues implementing this.
I could just remove the parameters from InvalidEvalDomainSize or something quick, or leave it as unwrap and open another issue/PR for this case (since it's rather independent)

Originally posted by @joebebel in #61 (comment)

Re-structure ConstraintSystem module and glue up the modules

Implement changes to license and aesthetics

It has been decided that the license should be change for the direction of the organisation. This will remain MPL.

There should also be some readme changes.

Remove `pub` visibility from embedded to outer curve scalar conversions

These conversions like the one performed in:
https://github.com/ZK-Garage/plonk/blob/master/plonk-core/src/util.rs#L93 pub fn from_embedded_curve_scalar<F, P>( embedded_scalar: <P as ModelParameters>::ScalarField, ) -> F
https://github.com/ZK-Garage/plonk/blob/master/plonk-core/src/util.rs#L122 pub(crate) fn to_embedded_curve_scalar<F, P>(pfc_scalar: F) -> P::ScalarField

Are never safe unless we have 100% clear that our StandardComposer API previously enforced some constraints(not circuit constraints) that guarantee that we can safely make this conversions.

We should remove the pub visibility and make sure that the invariants are never broken for them.

Add tests for generic Paring Engines and Embedded Curves

Add macros to run the tests over several embedded curves and over different paring engines.
The tests should at least run over the following:

• Jubjub
• TE curve over Bls12-377

Gadget Library

To make ark-plonk more useful, It would be nice to have a gadget library. (It should be a separate repo for the gadget library in my view).

The gadget library that in our interests include:

• a commitment gadget (should be agnostic to the hash functions or commitment scheme used)
• a ZK-friendly hash gadget, e.g. Pedersen Hash, Poseidon, Reinforcement-Concrete
• a merkle tree gadget

For the commitment gadget, @tsunrise and me has an initial interface design here:

#54

In my view, there might not be a perfect design, we are happy to start the implementation now starting from the commitment gadget. But in high-level, would like to get consensus on the following two things:

• repo organization
• stabilize the ark-plonk interface

Make `Variable` refactor to save info about the Scalar field of the input

Poiseidon Hash Implementation

Opening this to alert everyone that I am in the process of adapting Manta's poseidon implementation here (Manta-Network/Plonk-Prototype#3) to be ready to enter the plonk-hashing module.

This implementation includes filecoin's optimizations (see here too) as well as further optimizations that @tsunrise added.

I will link this issue to a PR over the coming days.

Automatically Compute the Linearisation Polynomial from the Quotient Polynomial

We want to build custom gates, lookups, etc. by considering each term's contribution to the quotient polynomial (and evaluation polynomials if we have terms that use local wires or "next" wires). These should be constructed symbolically at circuit::compile time.

Use `P::COEFF_A` instead of assuming `a=-1`

While working on #59 I noticed about this:
https://github.com/rust-zkp/plonk/blob/7b8298ea16fd4b67220d3ff5c95053e171200e48/src/constraint_system/ecc/curve_addition/variable_base_gate.rs#L144

This basically is assuming a=-1 for all curves when indeed, that might not be true. And we should force the gates to be in respect of P::COEFF_A as they're for P::COEFF_D.

Add GH Actions CI once the crate is ready to handle it

• Based on nightly without overwiriting the toolchain version.
• Not running anything for draft PRs.
• Passing doc tests and maybe clippy also. (We should discuss that one)

Fix CI error introduced in #38

In #38 @bhgomes updated the clippy workflow.

The problem is that in GH actions, each step has to contain a run or uses statement. Otherways it translates into a direct CI failure.

That's my bad since I should had realized in the review.

That needs to be fixed by adding back:
uses: actions-rs/cargo@v1

Address code TODOs.

We have left during the refactor several TODO's such as:

• Vanishing polynomial computations which are done "without being explicitly mentioned".
• Lagrange polynomial coefficient computations.
  And a large etc..

Define library design.

Currently this library has only an implementation of PLONK. In the coming weeks, we will be using the core functional to power gadgets as discussed in #54, and a hashing library.
The initial idea was to have these as separate libraries under the organisation. However, given the past difficulty of juggling lots of version updates, I think we should consider placing gadgets and hashing inside this one repo as modules. I see this as a successful approach in many projects.

It may also help with the exposing of witness values inside of variables, such with the mod_arith gadget that would be needed for the implementation of reinforced concrete. However, this warrants more thought wrt the exposing of modules.

WDYT? @bhgomes @lopeetall @CPerezz @noctrlz @tsunrise @julesdesmit @joebebel @EDGDrummond @stechu @iquerejeta @davidnevadoc @drewstone @GhostOfGauss @mathcrypto @markulf

Fix `logic.rs` comments

The logic gates are explained with formulas drawn in the comments.
Automatic formatting has shifted this drawings making some of them incomprehensible. Example:

  //                    /                 \          /
  // \  c      - 4 . c  = | a      - 4 . a  | (& OR ^) | b
  // - 4 . b  |   i + 1        i   \  i + 1        i /
  // \  i + 1        i /
  //

Originally:

//                    /                 \          /                 \
//  c      - 4 . c  = | a      - 4 . a  | (& OR ^) | b      - 4 . b  |
//   i + 1        i   \  i + 1        i /          \  i + 1        i /
//

Include custom gates for hashing purposes

When verifying paths in a Merkle tree it is useful to use a conditional_select together with a bit based on whether a hash refers to the left/right sibling at a given level.  To generate validity proofs of paths I propose a gate is_eq_gate that has two input wires and an output wire whose value is constrained to be 1 if the input wires have equal values and 0 otherwise.  It seems natural for this to be accompanied by is_zero and is_nonzero gates that have a single input wire and an output wire whose value is constrained to be 1 if the input is zero/nonzero and 0 otherwise.

Create Directory for Specification

There needs to be a directory which includes the spec of the code, as well as open research items and questions.

Fix circuit example

Fix bug in TestCircuit implementation:

• Correct selector polynomial for add gate
• Add constraint for add and multiplication gates

Add arkworks features for the crate

We should expose asm and parallel features as well as any other avaliable so that the users are able to choose if they want or not to use them.

Put back in `circuit` module into the crate

• Migrate the circuit module to arkworks backend.
• Migrate the Circuit tests to arkworks.
• Update the README.md example with the new circuit example.

Not enough variety in `add_dummy_constraints` can cause commitment errors for circuits of length 2^k before padding

The function add_dummy_constraints uses two arithmetic gates to add witnesses to the circuit. If the circuit itself also uses only arithmetic gates AND the total number of gates is a power of 2, then the circuit is never padded with 0s and the q_arith vector becomes constant which causes an error when committing to q_arith_poly.

Although this is unlikely to happen in a production circuit with many gates it can easily happen in tests of small subcircuits.

Until we implement lookups, all gates (including range, logic, etc.) resolve to arithmetic gates, so it might be tricky to make this work until lookups are enabled and we have a second "elemental" gate. But there may be a way to do it sooner by using an arithmetic selector value > 1.