This PR refactors proving in a number of ways. At least some of these changes are necessary to support determinism in the computation of F. The existing code didn't allow this, since compute was always called on the same circuit prototype contained in the public parameters.

• separate circuit/output computation and synthesis into two traits
• at the lowest level, support caller-controlled stepping of the proof
• for convenience, allow caller to provide iterators yielding successive outputs and (un-synthesized) circuits
• most simply, and consistent with current implementation, automatically create such iterators when ComputeStep is implemented

This change also makes num_steps optional, and the state accumulated in a RecursiveSNARK tracks the actual number of steps used. This allows for applications where the number of steps is not known in advance.

It's likely that further small changes may be needed when integrating downstream consumers who will need this functionality, but until integration happens, it is difficult to anticipate what that may entail beyond my best guesses here.

NOTE: in the future, we should support a recursive proof which does not expose the number of steps. This will be important for applications in which knowing the number of steps required to compute a final result leaks information. Having the option to generate proofs without revealing the number of steps will eliminate effective 'timing attacks' on such applications.

UPDATE: I added support for non-unary functions, building on the first part. I know that makes this a fairly large PR, but I had to rework a fair amount of the foundation to get here.

The basic idea is that for higher-arity functions, the implementer should implement methods (compute_inner and synthesize_step_inner, which operate on and return a vector of scalars. The goal was to make the actual mechanism as hidden from the caller/user as possible, but some leakage was unavoidable so far.

Under the hood, at each step, the inputs are hashed to get the true unary input for the step function, F — and the outputs are again hashed to produce the unary output. Both hashes are proved in the circuit.

Because we need to avoid storing the initial input (Z0) in the public parameters, it's necessary to first create an 'empty' input used to generate the R1CS shape. That means the caller does (unfortunately) have to create the poseidon constants for the relevant scalar and arity. This is not especially difficult, but it would be nicer if it could have been avoided. This wart means that the constants are generated twice in this case. With more machinery, the public parameters and IO enum could be more symbiotic, but for now I think this is a reasonable tradeoff.

Hi - the circuit, gadgets, and poseidon modules are not public. Can we make them public?

pub mod bellperson; mod circuit; pub mod errors; mod gadgets; pub mod pasta; mod poseidon; pub mod r1cs; pub mod traits;

This PR adds support for using bellperson R1CS (shape and witness) generation.

It depends on changes in this PR so cannot merge until that does. Once it has, we can update the git dependency here to finalize.

Full compilation error:

error: failed to select a version for the requirement `funty = "~1.2"`
candidate versions found which didn't match: 2.0.0, 1.1.0, 1.0.1, ...
location searched: crates.io index
required by package `bitvec v0.22.3`
    ... which satisfies dependency `bitvec = "^0.22.3"` of package `ec-gpu-gen v0.3.0`
    ... which satisfies dependency `ec-gpu-gen = "^0.3.0"` of package `bellperson v0.22.0`
    ... which satisfies dependency `bellperson = "^0.22"` of package `bellperson-nonnative v0.3.1`
    ... which satisfies dependency `bellperson-nonnative = "^0.3.1"` of package `nova-snark v0.8.1 (/home/t490/programs/Nova)`

For an amusing history which led to this issue, I think this is relevant: https://github.com/bitvecto-rs/funty/issues/3

TL;DR, seems as if they killed funty version 1.2 5 days ago.

I think using bellperson = "0.24.0" (and updating bellperson-nonnative to also use this bellperson) will solve it.

Draft pull request as this pull request depends on a pull request on the pasta_curves repo: https://github.com/zcash/pasta_curves/pull/36/commits

Fixes #46

Now that https://github.com/zcash/pasta_curves is licensed under MIT/Apache, we can depend on it directly here. This simplifies trait definitions (which previously had to be wrapped, with duplicate implementations of standard operations, when providing) for pasta curves.

I removed the dev dependency on Ristretto under the assumption that it was only a placeholder whose purpose could be served by Pasta now. This allowed upgrading the rand dependency, which is useful downstream.

hey this library looks great. we are looking for a "next gen" circom library for implementing smart contracts on blockchains. Do you have any plans going forward to support compiling to other languages such as solidity/huff?

Given that the public IO of the incoming R1CS instance contains the hash of the running instance in addition to (params, U, i, z0, zi), we can skip absorbing the running instance.

Serde serialization an deserialization for shape, parameters, instances, and witnesses.

Depends on the following PR on pasta_curves.

https://github.com/zcash/pasta_curves/pull/36/commits