* Reduce the number of constraints in `AugmentedFCircuit`
For the test `folding::nova::tests::test_ivc`
Before: 138240
After: 86756 (1.6x improvement)
Two notable optimization techniques:
1. Instead of allocating two witness variables `a, b` and enforce their equality by calling `a.conditional_enforce_equal(&b, &cond)`, we can avoid the allocation of `b` and directly set `b = a`. The former might be costly due to the checks in allocation and `conditional_enforce_equal`. See `nova/circuits.rs` for details.
2. Before this commit, `NonNativeFieldVar::to_constraint_field` was majorly called for generating the inputs (preimage) to hash functions. However, it turns out that the underlying conversion strategy (optimized for weight) is not optimal for reducing the length of hash preimage. We can go further by maximizing the number of bits per limb, thereby minimizing the preimage length. See `circuits/nonnative.rs` for details.
* Format
* Fix clippy warnings
* Move the comments to the right position
* Cleanup unnecessary code
* Treat (the digest of) `cf_U_i1` as an additional public input to `AugmentedFCircuit` for full soundness
* Fix the y-coordinate in the affine form of zero points
This in turn fixes the inconsistency between the digest of a constant affine point and that of a witness affine point in circuits.
* Set `cf_u_i1_x` to the correct value
* Fix the number of public inputs in dummy instance and witness
* Unify the logic behind `CycleFoldCommittedInstanceVar::hash` and `CycleFoldChallengeGadget::get_challenge_gadget`
* Add `ToConstraintFieldGadget` bound to `GC2`
* Remove unnecessary code used for debugging
* Make clippy and rustfmt happy
* Move conversion methods for `NonNativeFieldVar` to `folding/circuits/nonnative.rs`
* Simplify the check of zero coordinates
* Gracefully handle the result of `nonnative_field_var_to_constraint_field`
* Make clippy happy again
* Compute Decider's CM challenges in Groth16 circuit, link G16 & KZG proofs in Onchain Decider, refactor CommitmentScheme trait
- Refactor commitment package
- Refactor `Commitment` trait and the kzg, ipa, pedersen impls
- Add methods to prove & verify given challenges (not computing them in-method)
- Add KZG challenges computation in decider_eth_circuit
- Add cmE & cmW KZG proving & verification in DeciderEth
- Link Decider's Groth16 proof & KZG proofs data
- Fix point to bytes arkworks inconsistency
- Patch ark_curves to use a cherry-picked version with bn254::constraints & grumpkin for v0.4.0 (once arkworks v0.5.0 is released this will no longer be needed)
* DeciderEthCircuit: Add check eval=p(c) for E & W
The check is temporary disabled due
https://github.com/privacy-scaling-explorations/folding-schemes/issues/80,
but the public inputs and logic are there, to be able to continue the
other parts development while issue #80 is solved.
* add: solidity-verifier workspace member
* chore: Update toolchain to 1.74
* feat: Add basic clap cli interface for solidity verifier
This includes a cli parser that serves as a way to the user to generate the desired Solidity contracts.
* chore: Expose SoldityVerifier template struct
* feat: Finish first working version
* change: Modify some settings
* fix: Fix rebase conflicts
* chore: Leave resolver 2 for workspace
* chore: Rename KZG+G16 template
Now the template refers to Nova + Cyclefold and has a Warning attached to it
* fixup
* chore: Rename to NovaCyclefoldDecider the template
* chore: Change constructors to `new` instead of `from`
* add: ProtocolData trait helper
This trait helps to treat the serialized data required by the Template
as a single element while still allowing a flexible usage.
This is specially interesting as allows the cli to operate considering a
single path of input data where all the data for the selected protocol
co-exists. Reducing the amount of parsing and arguments the user needs
to pass to the cli.
* chore: Create `From` impls formally
Previously we had functions called `from` which had nothing to do with
the trait `From`. This addresses this issue and fixes it.
Now both `new` and `from` are avaliable. But `from` follows the `From`
trait.
* add: Support G16, KZG and Nova+Cyclefold in cli
This adds a `render` fn for `Protocol` which makes it easier to add new
protocols to the CLI as is mainly based in the `ProtocolData` impl
behind the scenes of the selected protocol.
Aside from that, this commit reworks some minor parts of the CLI config
as shorteners for commands or adding `pragma` as an optional parameter.
* chore: Adapt `main.rs` to new cli changes
As seen, this allows to have a much easier `main.rs` which doesn't have
to do any `match` over the selected protocol.
* chore: Make solidity helper fns `cfg(test)`
* chore: Rework folding-schemes-solidity structure
* chore: Remove g1_crs_batch_points_len from KZGData
* add: Serde tests for all template targets
* tmp: Add NovaCyclefold testing
* add: HeaderInclusion template
When we use templates that are composed by others (as happens with
`NovaCyclefold` one) we sadly see that the License and the `pragma`
attributes are rendered once per sub-template.
This generic structure solves this issue by being actually the only item
rendered which has a sub-template the template we indeed want to render
at the end.
* chore: Add tests for NovaCyclefold contract
This also includes small changes to the lib architecture such as adding
constants for GPL3_SDPX_IDENTIFIER or move the default pragma versions
used to `mod.rs`
* chore: Update g16 to use HeaderInclusion template rendering
Now the `ProtocolData` impl falls back to the usage of `HeaderInclusion`
it is easier to handle complex templates like `NovaCyclefold`.
* add: Small builder-pattern to construct HeaderInclusion Templates
As mentioned in previous commits, the idea is that the header is set on
an automatic wrapper template applied to the one that we actually want
to render.
This builder pattern makes it less complex to do such a thing. Specially
avoiding unidiomatic `From` implementations.
* remove: sdpx & pragma from KZG template
Those are externalized and handled by HeaderInclusion template utility
* chore: Update templates to use HeaderInclusion builder
* chore: Update tests to use HeaderInclusion builderPattern
* remove: fixed pragma version in novacyclefold template
* chore: Accept Into<Template> in builder
* tmp: Only KZG return passes. Fix Groth
* fix: Prevent `revert` from paniking for negative tests
* feat: Merge G16 and KZG contract results in NovaCyclefold
* chore: Add assets for quicker/easier testing
Now instead of generating the protocoldata & proofs on each test, we just deserialize
* fix: Address clippy & warnings
* fix: Spelling to prevent PR farmers LOL
* chore: Add about and long_about to CLI tool
* add: README.md
* chore: Revert asset-based testing approach
* remove: Assets folder
* fix: Rebase issues
* fix: use &mut for Reader
* fix: rebase error with Contract name
* chore: Reduce tests LOC with setup fn
* chore: Set MIT license indentifier for CLI & KZG
* chore: Add extra usage example
* chore: Update novacyclefold contract comments on soundess
* chore: Typo
* chore: Allow type complexity clippy for setup fn
* chore: Address Pierre's comments
* chore: Rename workspace members
- folding-schemes-solidity -> soliity-verifiers
* Change CycleFold approach:
Instead of having a single CycleFold circuit that checks the 2 forign
scalarmul of the main circuit instances, now there are 2 separated
CycleFold circuits each of them checking a single foreign scalarmul.
Increasing the number of constraints of the AugmentedFCircuit, but
reducing the number of constraints in the CycleFold circuit, which will
translate into reducing the number of constraints in the Decider
circuit.
* CycleFold circuits checks in AugmentedFCircuit:
- update NonNativeAffineVar to work with NonNativeFieldVar directly
instead of FpVar comming from NonNativeFieldVar.to_constraint_field()
- include in AugmentedFCircuit intermediate steps inbetween CycleFold
circuits, and update the internal checks of the CycleFold circuits
Pending to document the new CycleFold circuits approach and better
variable namings, rm unwraps, etc
* matrix_vec_mul_sparse gadget: skip value * v[col_i] mul when value==1
Saves a notable amount of constraints since there is a notable amount of
1 values in R1CS matrices.
* Reuse computed vector of U_i
Reuse computed vector of U_i, saving 4k constraints in AugmentedFCircuit.
* fixes post last rebase to main
* rm test_augmentedfcircuit since it is already tested in test_ivc (and is a slow computation)
* rm dbg!()
* small fixes after last main rebase
* Add IPA commitment native implementation
* Add IPA Gadget verifier
* polish Pedersen & IPA, add blind bool param to IPA
* Optimize IPA gadget constraints (and native):
- optimize <s,b> computation from linear to log time
- optimize s computation from k*2^k to k*(2^k)/2
* add small optimization: delegate u_i^-1 to prover and just check u_i*u_i^-1==1 in verifier circuit
* IPA polish and document
* Add 'BLIND' parameter to CommitmentProver trait (and to Pedersen and KZG impls). Fit IPA into CommitmentProver trait.
* rename 'BLIND' to 'H' (hiding) in commitment
* IPA: rm u_invs from Proof and compute them incircuit
* Update IPA's build_s & gadget to use Halo2 approach following @han0110 's suggestion.
This reduced further the amount of constraints needed.
- for k=4: -9k constraints (-7%)
- for k=8: -473k constr (-31%)
- for k=9: -1123k constr (-35%)
- for k=10: -2578k constr (-39%)
And now IPA verification (without amortizing) is very close to Pedersen
verification (in-circuits).
* rm dbg!(cs.num_constraints()) from multiple tests
* IPA::prove remove intermediate v_lo,v_hi vectors, add doc to build_s_gadget
* move powers_of into utils/mod.rs, update iters to cfg_iter
* Fix Nova multi-elements state
In the AugmentedFCircuit the default value for the state when no input
is provided was `vec![F::zero()]`, which defaults to length `1`. So when
having more than 1 element in the state, before even starting to fold,
the circuit was already already failing.
Additionally this commit adds an example for a circuit with a state of 5
elements.
* abstract 'nova_setup' helper to avoid code duplication in examples
* update example naming to 'MultiInputs'
* rename nova_setup -> test_nova_setup to make it more explicit
* change: Refactor structure into workspace
* chore: Add empty readme
* change: Transform repo into workspace
* add: Create folding-verifier-solidity crate
* add: Include askama.toml for `sol` extension escaper
* add: Jordi's old Groth16 verifier .sol template and adapt it
* tmp: create simple template struct to test
* Update FoldingSchemes trait, fit Nova+CycleFold
- update lib.rs's `FoldingScheme` trait interface
- fit Nova+CycleFold into the `FoldingScheme` trait
- refactor `src/nova/*`
* chore: add serialization assets for testing
Now we include an `assets` folder with a serialized proof & vk for tests
* Add `examples` dir, with Nova's `FoldingScheme` example
* polishing
* expose poseidon_test_config outside tests
* change: Refactor structure into workspace
* chore: Add empty readme
* change: Transform repo into workspace
* add: Create folding-verifier-solidity crate
* add: Include askama.toml for `sol` extension escaper
* add: Jordi's old Groth16 verifier .sol template and adapt it
* tmp: create simple template struct to test
* feat: templating kzg working
* chore: add emv and revm
* feat: start evm file
* chore: add ark-poly-commit
* chore: move `commitment` to `folding-schemes`
* chore: update `.gitignore` to ignore generated contracts
* chore: update template with bn254 lib on it (avoids import), update for loop to account for whitespaces
* refactor: update template with no lib
* feat: add evm deploy code, compile and create kzg verifier
* chore: update `Cargo.toml` to have `folding-schemes` available with verifiers
* feat: start kzg prove and verify with sol
* chore: compute crs from kzg prover
* feat: evm kzg verification passing
* tmp
* change: Swap order of G2 coordinates within the template
* Update way to serialize proof with correct order
* chore: update `Cargo.toml`
* chore: add revm
* chore: add `save_solidity`
* refactor: verifiers in dedicated mod
* refactor: have dedicated `utils` module
* chore: expose modules
* chore: update verifier for kzg
* chore: rename templates
* fix: look for binary using also name of contract
* refactor: generate groth16 proof for sha256 pre-image, generate groth16 template with verifying key
* chore: template renaming
* fix: switch circuit for circuit that simply adds
* feat: generates test data on the fly
* feat: update to latest groth16 verifier
* refactor: rename folder, update `.gitignore`
* chore: update `Cargo.toml`
* chore: update templates extension to indicate that they are templates
* chore: rename templates, both files and structs
* fix: template inheritance working
* feat: template spdx and pragma statements
* feat: decider verifier compiles, update test for kzg10 and groth16 templates
* feat: parameterize which size of the crs should be stored on the contract
* chore: add comment on how the groth16 and kzg10 proofs will be linked together
* chore: cargo clippy run
* chore: cargo clippy tests
* chore: cargo fmt
* refactor: remove unused lifetime parameter
* chore: end merge
* chore: move examples to `folding-schemes` workspace
* get latest main changes
* fix: temp fix clippy warnings, will remove lints once not used in tests only
* fix: cargo clippy lint added on `code_size`
* fix: update path to test circuit and add step for installing solc
* chore: remove `save_solidity` steps
* fix: the borrowed expression implements the required traits
* chore: update `Cargo.toml`
* chore: remove extra `[patch.crates-io]`
* fix: update to patch at the workspace level and add comment explaining this
* refactor: correct `staticcall` with valid input/output sizes and change return syntax for pairing
* refactor: expose modules and remove `dead_code` calls
* chore: update `README.md`, add additional comments on `kzg10` template and update `groth16` template comments
* chore: be clearer on attributions on `kzg10`
---------
Co-authored-by: CPerezz <c.perezbaro@gmail.com>
Co-authored-by: arnaucube <root@arnaucube.com>
* Add Decider impl for Nova onchain
Add Decider impl for Nova onchain.
Update also the Decider trait.
Nova onchain decider: (compressed SNARK / final proof), in order to
later verify the Nova+CycleFold proofs onchain (in Ethereum’s EVM).
* PR review updates and few other changes
* make second step of the prover happen in O(n)
* readability fixes and error handling
* chore: Address review comments to merge
---------
Co-authored-by: CPerezz <c.perezbaro@gmail.com>
* Add KZG commitment scheme adapted to vector commitment
Add KZG commitment scheme adapted to vector commitment
Also move the `src/pedersen.rs` into `src/commitment/pedersen.rs` where
it will coexist with `kzg.rs` and the trait defined in
`src/commitment/mod.rs`.
* Adapt Pedersen into the new CommitmentProver trait
* add CommitmentProver (Pedersen&KZG) homomorphic property test
* polishing
* Use divide_with_q_and_r, rename skip_first_zero_coeffs
Co-authored-by: han0110 <tinghan0110@gmail.com>
---------
Co-authored-by: han0110 <tinghan0110@gmail.com>
Changes:
- get rid of `extract_r1cs_and_z` and `extract_z`
- move `extract_r1cs` and `extract_w_x` from `frontend/arkworks` into
`r1cs.rs`
The reasoning: they are not methods needed for the Frontend interface,
but only needed internally for the folding scheme to extract values from
the AugmentedF circuit and similar.
- set the `FCircuit` as the trait for the `src/frontend`
- remove the `frontend/arkworks` since the `FCircuit` trait can be
directly implemented without a middle layer
- reorganize test circuits into `src/frontend/mod.rs`, updating them into
`CubicFCircuit`: the typical x^3+x+5=y circuit
`CustomFCircuit`: a circuit in which you can specify the number of
constraints that it will take
where both fulfill the `FCircuit` trait, and they are used for
different tests being folded.
* feat: start hypernova nimfs verifier
* refactor: change where nimfs verifier lives
* feat: `EqEvalGadget` for computing `eq(x, y)`
* refactor: rename to `utils.rs`
* feat: implement a `VecFpVar` struct, representing a vector of `FpVar`s
* refactor: extract a `sum_muls_gamma_pows_eq_sigma` function to make circuit tests easier
* feat: implement a `SumMulsGammaPowEqSigmaGadget` to compute the first term of the sum of section 5, step 5
* refactor: update gadget name and method name to match `sum_muls_gamma_pows_eq_sigma`
* fix: update method call
* refactor: remove usage of `GammaVar`
Co-authored-by: arnaucube <root@arnaucube.com>
* refactor: move hypernova circuit related types and methods into `src/folding/hypernova/circuits.rs`
* refactor: remove all of `GammaVar` wrapper
* chore: update type to `&[F]`
* refactor: update from `new_constant` to `new_witness`
* fix: actual file deletion
* refactor: remove `VecFpVar` struct
* chore: update comment doc
* refactor: extract a `sum_ci_mul_prod_thetaj` function for testing
* feat: `test_sum_ci_mul_prod_thetaj_gadget` passing
* refactor: update docs and add a helper `get_prepared_thetas` function
* refactor: clearer arg name
* fix: clippy typing
* chore: correct latex comments
* refactor: remove unncessary `get_prepared_thetas` fn
* feat: test passing for rough first pass on `ComputeCFromSigmasAndThetasGadget`
* chore: add additional doc comments
* chore: add `#[allow(clippy::too_many_arguments)]`
* refactor: make gadget generic over a curve group
* chore: clippy fixes
* chore: correct latex in doc comment
* refactor: refactor `sum_muls_gamma_pows_eq_sigma` and `sum_ci_mul_prod_thetaj` in `ComputeCFromSigmasAndThetasGadget`
---------
Co-authored-by: arnaucube <root@arnaucube.com>
This is to be able to instantiate the CycleFoldCircuit over Curve2
constraint field, and check it's RelaxedR1CS relation non-natively
inside the Curve1 constraint field, while reusing the same code that we
already have for checking the main circuit RelaxedR1CS over Curve1
constraint field natively.
Port ProtoGalaxy initial version from
https://github.com/arnaucube/protogalaxy-poc adapting it to the current
folding-schemes lib, which is a first iteration that implements the
Lagrange-basis version from
[ProtoGalaxy](https://eprint.iacr.org/2023/1106) folding scheme. There
are some pending optimizations, but is a first step towards integrating
ProtoGalaxy in the library.
* Implement Nova IVC's new & prove_step methods
Implement Nova IVC's new & prove_step methods (without CycleFold part yet)
* transcript.absorb_point err handling, and update C.xy() usage
* add transcript usage to IVC prove, add NovaTranscript trait extending Transcript trait, refactor NIFS.P to allow absorbing in transcript inbetween
* Implement Nova's IVC.V method (without CycleFold part yet)
* clippy lints
* move challenge r computation in-circuit
* reuse computed points with coordinates over CF (non-native) to save constraints in AugmentedFCircuit
(constraint count went down ~6k)
* rm 128 bit constant
* add params to Errors
* Updates from review suggestions. Additionally refactored nova/nifs fold, and rm transcript from nova/IVC.
- Updates from PR suggestions
- Additionally updated:
- in nova/nifs.rs: reuse folded_committed_instance for verify_folded_instance, computationally is the same, but reusing the same code so avoiding duplication and having an error on one of the two versions.
- in nova/ivc.rs: remove transcript from IVC (not needed, it uses the RO)
* impl AugmentedFCircuit non-base case
* add multiple iterations to AugmentedFCircuit test
* implement base case on AugmentedFCircuit and test
* Update cmE of E=0-vec to work as zero point
Update cmE of E=0-vec to work as zero point instead of as cm(0-vec)
* patch r1cs-std dep to a cherry-picked version with the zero-scalar-mult fix
* refactor FCircuit to make it more suitable inside the AugmentedFCircuit
* r1cs_parser
* z vector calculation
* test function done
* improved
* Brushuped
* add comment
* Added description of test_circuit
* found mistake
* fixed cargo.toml
* Imported ark-circom as crate
* improved l in R1CS as the number of public I/O
* separate test functions into success/failure and unify variable to pub_io_len
* removed bn254 & abstracted to PrimeField, but still some work
* add comments and clean up code
* move ark-bn254 in dev-dependencies
* abstracted test function
* fixed github action's error
* cargo fmt
* remove convert_constraints_bigint_to_scalar function
* fixed n_cols
* fixed n_cols
* Add functionality to compile Circom files in tests
* Remove test_circuit.r1cs
* Introduce CircomFrontend trait and simplify with CircomWrapper struct
* deleted the CircomFrontend
* improved
* fixed clippy lint checks of github actions
* probably fixed github actions error by changing the github yaml
* fixed github yaml, fmt, and clippy
---------
Co-authored-by: Carlos Pérez <37264926+CPerezz@users.noreply.github.com>
* Port HyperNova's multifolding from https://github.com/privacy-scaling-explorations/multifolding-poc adapting and refactoring some of its methods and structs.
Note: adapted mle.rs methods from dense to sparse repr.
Co-authored-by: George Kadianakis <desnacked@riseup.net>
* HyperNova: move CCS struct outside of LCCCS & CCCS
HyperNova nimfs: move CCS structure outside of LCCCS & CCCS, to avoid
carrying around the whole CCS and duplicating data when is not needed.
Also add feature flags for the folding schemes.
---------
Co-authored-by: George Kadianakis <desnacked@riseup.net>
- Add naive decider circuit `RelaxedR1CSGadget`, which in-circuit checks
that the given z satisfies the given RelaxedR1CS instance
- Add method to relax the R1CS instance
- Add check_relation (for testing only) to R1CS & RelaxedR1CS
- Migrate from own SparseMatrix to use ark_relations::r1cs::Matrix
- Add frontend helper to use arkworks circuits
* Implement Nova's NIFS.Verify circuits (with CycleFold)
- Add circuit for NIFS.Verify on the main curve to check the folded `u`
& `x`
- Add circuit for NIFS.Verify on the CycleFold's auxiliary curve to
check the folded `cm(E)` & `cm(W)`
- Add transcript.get_challenge_nbits
- Add tests for utils::vec.rs
* replace bls12-377 & bw6-761 by pallas & vesta curves (only affects tests)
We will use pallas & vesta curves (for tests only, the non-tests code
uses generics) for the logic that does not require pairings, and while
Grumpkin is not available
(https://github.com/privacy-scaling-explorations/folding-schemes/issues/12).
* update links to papers to markdown style
Port Espresso/hyperplonk's `virtualpolynomial`, `multilinearpolynomial`
and `sum_check` utils from
https://github.com/EspressoSystems/hyperplonk/tree/main
Each file contains the reference to the original file.
Porting it into a subdirectory `src/utils/espresso`, to have it
self-contained. In future iterations we might replace part of it but we
can keep focusing on the folding schemes part for now.
* feat: draft traits `FoldingScheme` and `Decider`
Co-authored-by: arnaucube <root@arnaucube.com>
* Add Transcript trait, with PoseidonTranscript impl (#1)
Add also the PoseidonTranscriptVar (gadget).
* Update FoldingScheme trait to take C1 & C2 as params (#2)
* Update FoldingScheme trait to take C1 & C2 as params
Update FoldingScheme trait to take C1 & C2 as params which are used by
the diverse folding schemes as a cycle of curves.
* Add constraint to FoldingScheme C1,C2 fields swap.
Co-authored-by: Han <tinghan0110@gmail.com>
---------
Co-authored-by: Han <tinghan0110@gmail.com>
* move transcript to it's own mod
---------
Co-authored-by: han0110 <tinghan0110@gmail.com>
winderica
arnaucube
Carlos Pérez
Pierre
Silur
Y5
ashWhiteHat
arnaucube
Han