arnaucube
arnaucube/sonobePublic Self-hosted repository

Commit history

main
a
Add NIFSGadgetTrait, implement Mova's NIFSGadget, adapt Nova NIFSGadget into NIFSGadgetTrait (#173) * add new NIFSGadgetTrait * implement Mova's NIFSGadget * refactor Nova NIFSGadget to fit into the new NIFSGadgetTrait * abstract NIFSGadget related tests for all implementors of NIFSGadgetTrait to avoid duplicated code in the tests between the different Nova variants gadget tests * frontends/noir update mimc usage since it has been migrated from noir's std into it's own repo
arnaucube committed on Nov 12, 2024
e118387
w
Onchain decider circuit for Protogalaxy (#145) * Move r1cs and ccs to standalone folders * Simplify type bounds of SparseMatrixVar * Implement `EquivalenceGadget` trait for `FpVar` and `NonNativeUintVar`. Together with the existing `MatrixGadget` and `VectorGadget`, we can now use the same logic for checking R1CS satisfiability of `R1CSVar` both natively and non-natively. * Simplify trait bounds * Implement `ArithGadget` for `R1CSMatricesVar` and `CCSMatricesVar` * `PedersenGadget::commit` now takes slices as input * Structs for proofs and auxiliary values in protogalaxy * `u` in LCCCS should be `z[0]` * `Inputize` trait * Generic decider circuits * Verifier should check the commitments in committed instances * Update the comments according to the new docs * Fix examples * Add `DeciderEnabledNIFS::fold_group_elements_native` to wrap code for folding commitments * Fix incorrect endian * Format * Get rid of `unwrap` when possible
winderica committed on Nov 4, 2024
b812dd6
N
Implemented Mova folding scheme (#161) * Adding Mova Co-Authored-By: Togzhan Barakbayeva <45527668+btogzhan2000@users.noreply.github.com> Co-Authored-By: Ilia Vlasov <5365540+elijahvlasov@users.noreply.github.com> Co-Authored-By: matthew-a-klein <96837318+matthew-a-klein@users.noreply.github.com> * Fix CLI * Updated from main * Solution to stop the CLI from complaining about deadcode PR comment Co-authored-by: arnaucube <root@arnaucube.com> * Requested changes and update from main * Refactor NIFSTrait & port Mova impl to it * refactor NIFSTrait interface to fit Nova variants (Nova,Mova,Ova) Refactor NIFSTrait interface to fit Nova variants (Nova,Mova,Ova). The relevant change is instead of passing the challenge as input, now it passes the transcript and computes the challenges internally (Nova & Ova still compute a single challenge, but Mova computes multiple while absorbing at different steps). * port Mova impl to the NIFSTrait * remove unnecessary wrappers in the nova/zk.rs * remove Nova NIFS methods that are no longer needed after the refactor * put together the different NIFS implementations (Nova, Mova, Ova) so that they can interchanged at usage. The idea is that Nova and its variants (Ova & Mova) share most of the logic for the circuits & IVC & Deciders, so with the abstracted NIFS interface we will be able to reuse most of the already existing Nova code for having the Mova & Ova circuits, IVC, and Decider. * adapt Nova's DeciderEth prepare_calldata & update examples to it * small update to fix solidity tests --------- Co-authored-by: Togzhan Barakbayeva <45527668+btogzhan2000@users.noreply.github.com> Co-authored-by: Ilia Vlasov <5365540+elijahvlasov@users.noreply.github.com> Co-authored-by: matthew-a-klein <96837318+matthew-a-klein@users.noreply.github.com> Co-authored-by: arnaucube <root@arnaucube.com> Co-authored-by: arnaucube <git@arnaucube.com>
Nick Dimitriou committed on Oct 23, 2024
6d8f297
a
Move the experimental frontends into a separate crate, so that when not using them they don't take several minutes to compile (and indirect dependencies). (#168) This saves several minutes (and MBs of data) on compilation time both when running tests in this repo, but also when using the sonobe lib as a dependency in external repos.
arnaucube committed on Oct 19, 2024
234600b
a
Add IVCProof to the existing folding schemes (Nova,HyperNova,ProtoGalaxy) (#167) * Add IVCProof to the existing folding schemes (Nova,HyperNova,ProtoGalaxy) * Implement `from_ivc_proof` for the FoldingSchemes trait (and Nova, HyperNova, ProtoGalaxy), so that the FoldingScheme IVC's instance can be constructed from the given parameters and the last IVCProof, which allows to sent the IVCProof between different parties, so that they can continue iterating the IVC from the received IVCProof. Also the serializers allow for the IVCProof to be sent to a verifier that can deserialize it and verify it. This allows to remove the logic from the file [folding/nova/serialize.rs](https://github.com/privacy-scaling-explorations/sonobe/blob/f1d82418ba047cf90805f2d0505370246df24d68/folding-schemes/src/folding/nova/serialize.rs) and [folding/hypernova/serialize.rs](https://github.com/privacy-scaling-explorations/sonobe/blob/f1d82418ba047cf90805f2d0505370246df24d68/folding-schemes/src/folding/hypernova/serialize.rs) (removing the whole files), which is now covered by the `IVCProof` generated serializers (generated by macro instead of handwritten), and the test that the file contained is now abstracted and applied to all the 3 existing folding schemes (Nova, HyperNova, ProtoGalaxy) at the folding/mod.rs file. * update Nova VerifierParams serializers to avoid serializing the R1CS to save big part of the old serialized size * rm .instances() since it's not needed * add nova params serialization to nova's ivc test to ensure that IVC verification works with deserialized data * Add unified FS::ProverParam & VerifierParam serialization & deserialization (for all Nova, HyperNova and ProtoGalaxy), without serializing the R1CS/CCS and thus saving substantial serialized bytes space. * rm CanonicalDeserialize warnings msgs for VerifierParams
arnaucube committed on Oct 11, 2024
cb1b8e3
w
Resolve the stack overflow issue when evaluating polynomials in-circuit (#166) * Resolve the stack overflow issue when evaluating polynomials in-circuit * Format * Add the missing line of comment
winderica committed on Oct 3, 2024
ed14889
a
Nova vairants (Ova) NIFS abstraction (#165) * add NIFS trait abstraction (based on the needs for Nova, Mova, Ova), defining a common interface between the three Nova variants The recent Ova NIFS PR #163 (https://github.com/privacy-scaling-explorations/sonobe/pull/163) and Mova NIFS PR #161 (https://github.com/privacy-scaling-explorations/sonobe/pull/161) PRs add Nova NIFS variants implementations which differ from Nova in the logic done for the `E` error terms of the instances. The current Ova implementation (https://github.com/privacy-scaling-explorations/sonobe/pull/163) is based on the existing Nova NIFS code base and adds the modifications to the `E` logic on top of it, and thus duplicating the code. Similarly for the Mova NIFS impl. The rest of the Mova & Ova schemes logic that is not yet implemented is pretty similar to Nova one (ie. the IVC logic, the circuits and the Decider), so ideally that can be done reusing most of the already existing Nova code without duplicating it. This PR is a first step in that direction for the existing Ova NIFS code. This commit adds the NIFS trait abstraction with the idea of allowing to reduce the amount of duplicated code for the Ova's NIFS impl on top of the Nova's code. * add Ova variant on top of the new NIFS trait abstraction This is done from the existing Ova implementation at `folding/ova/{mod.rs,nofs.rs}`, but removing when possible code that is not needed or duplicated from the Nova logic. * rm old Ova duplicated code This commit combined with the other ones (add nifs abstraction & port Ova to the nifs abstraction) allows to effectively get rid of ~400 lines of code that were duplicated in the Ova NIFS impl from the Nova impl. * small polishing & rebase to latest `main` branch updates
arnaucube committed on Oct 3, 2024
a07e17e
a
implement Nova's Offchain Decider (prover & verifier) for non-ethereum cases (#164) The idea & motivation is that the [onchain decider](https://privacy-scaling-explorations.github.io/sonobe-docs/design/nova-decider-onchain.html) could still be used for non-onchain verification but the proving time is big (eg. a little bit less than 3 minutes on my laptop) since the circuit is big due the EVM constraints. Whereas with this new [offchain decider](https://privacy-scaling-explorations.github.io/sonobe-docs/design/nova-decider-offchain.html) we can generate the proofs much faster for the cases where it is not required to verify the proofs in the EVM. The code is mostly abstracted from any specifics of the current usage of Groth16 & KZG10, with the idea that eventually in the future we can have Spartan plugged in and use non-pairing-curves such as pallas&vesta. For the current version it relies on KZG10 commitments. The logic implemented in the code of this commit can be found at the updated docs section 'offchain decider': https://privacy-scaling-explorations.github.io/sonobe-docs/design/nova-decider-offchain.html
arnaucube committed on Oct 3, 2024
edcef6c
C
Implement OVA NIFS (#163) * feat: Basic Ova NIFS impl working The implementation follows the spec outlined by Bunz in: https://hackmd.io/V4838nnlRKal9ZiTHiGYzw?view. With this, the NIFS works and passes all tests. * chore: Resolve all TODOs and warnings * add: Docs for the NIMFS of the scheme and related structs * chore: update imports * add: Docs for all Ova NIFS functions * fix: Unify nomenclature for all variables and elements within NIFS tests * fix: Uniformize instance order in fn calls * chore: pass clippy * chore: clear all clippy findings in tests * chore: Remove `mimc` from spelling checks * chore: Address PR reviews
Carlos Pérez committed on Oct 3, 2024
88bbd9c
w
Refactor `Arith` trait (#162) * `Dummy` trait * More generic design for `Arith` * Distinguish between incoming and running instances in ProtoGalaxy * Format * Fix unit test * Fix incorrect arguments supplied to `CycleFoldWitness::dummy` * `RUNNING` and `INCOMING` constants * Better name and docs for `eval_core` * More docs for `Arith` methods and implementations * Fix missing imports
winderica committed on Sep 25, 2024
f1d8241
a
Implement Nova's Offchain-Decider circuits (#160) * Implement Nova's Offchain-Decider circuits (on both curves) (curve1 circuit: ~152k constraints, curve2 circuit: ~8k constraints) following the enumeration of the Offchain Decider docs: https://privacy-scaling-explorations.github.io/sonobe-docs/design/nova-decider-offchain.html * Update enumeration of checks in Onchain-Decider circuit (decider_eth_circuit.rs) to match the updated Onchain Decider docs: https://privacy-scaling-explorations.github.io/sonobe-docs/design/nova-decider-onchain.html
arnaucube committed on Sep 24, 2024
1e9c13f
w
Traits for witnesses and committed instances (#157) * Add traits for witness and committed instance * Implement witness and committed instance traits for Nova and HyperNova * Implement witness and committed instance traits for ProtoGalaxy * Improve the clarity of docs for `Witness{Var}Ext::get_openings` * Avoid cloning `z_i` * Fix grammar issues * Rename `Ext` traits for committed instances and witnesses to `Ops` * Implement `to_sponge_bytes`
winderica committed on Sep 20, 2024
dfd03ea
P
feat/hypernova serialization (#159) * feat: implement serialization of hypernova prover and verifier params, proof and public inputs * chore: remove leftover comments * chore: remove timers * chore: improve typing and import naming
Pierre committed on Sep 19, 2024
1947ab0
w
Protogalaxy based IVC (#123) * Parallelize vector and matrix operations * Implement convenient methods for `NonNativeAffineVar` * Return `L_X_evals` and intermediate `phi_star`s from ProtoGalaxy prover. These values will be used as hints to the augmented circuit * Correctly use number of variables, number of constraints, and `t` * Fix the size of `F_coeffs` and `K_coeffs` for in-circuit consistency * Improve prover's performance * Make `prepare_inputs` generic * Remove redundant parameters in verifier * Move `eval_f` to arith * `u` is unnecessary in ProtoGalaxy * Convert `RelaxedR1CS` to a trait that can be used in both Nova and ProtoGalaxy * Implement several traits for ProtoGalaxy * Move `FCircuit` impls to `utils.rs` and add `DummyCircuit` * `AugmentedFCircuit` and ProtoGalaxy-based IVC * Add explanations about IVC prover and in-circuit operations * Avoid using unstable features * Rename `PROTOGALAXY` to `PG` to make clippy happy * Fix merge conflicts in `RelaxedR1CS::sample` * Fix merge conflicts in `CycleFoldCircuit` * Swap `m` and `n` for protogalaxy * Add `#[cfg(test)]` to test-only util circuits * Prefer unit struct over empty struct * Add documents to `AugmentedFCircuit` for ProtoGalaxy * Fix the names for CycleFold cricuits in ProtoGalaxy * Fix usize conversion when targeting wasm * Restrict the visibility of fields in `AugmentedFCircuit` to `pub(super)` * Make CycleFold circuits and configs public * Add docs for `ProverParams` and `VerifierParams` * Refactor `pow_i` * Fix imports * Remove lint reasons * Fix type inference
winderica committed on Sep 12, 2024
1322767
a
implement HyperNova's DeciderEth (#156) * implement HyperNova's DeciderEth * add remark about Nova's zk layer implementation and the 3 identified use cases
arnaucube committed on Sep 10, 2024
0ad5457
a
Nova parameters & decider parameters and proofs serialization (#151) * Add nova's decider serialization & deserialization to proof, verifier_params and public inputs * polish * add serialization for nova's ivc proverparams & verifierparams
arnaucube committed on Sep 10, 2024
1f7bf04
C
feat: Minimal in-browser compatibility for the crate (#149) * change: CircomWrapper constructor to use raw bytes * chore: tmp update to latest circom-compat * feat: Introduce PathOrBin to support in-browser CircomWrapper usage This changes the associated type `Params` of the `CircomFCircuit` to use the newly created `PathOrBin` type. This allows the user of the lib to directly send the binary of the files already read or instead, provide a path to it and let `sonobe` do the work. With this, Circom should be already usable from the browser if we allow JS to take care of reading the `.wasm` and `.r1cs` files. * feat: Introduce PathOrBin to support in-browser NoirFCircuit usage This commit temporarilly stands on top of https://github.com/dmpierre/arkworks_backend/pull/1 referenced as `rev`. This changes the associated type `Params` of the `CircomFCircuit` to use the newly created `PathOrBin` type. This allows the user of the lib to directly send the binary of the files already read or instead, provide a path to it and let `sonobe` do the work. With this, Noir should be already usable from the browser if we allow JS to take care of reading the `circuit.json` files * chore: Update deps to branch instead of `rev` * fix: use PathOrBin in examples * fix: clippy * fix: read file length for initializing vec size --------- Co-authored-by: dmpierre <pdaixmoreux@gmail.com>
Carlos Pérez committed on Aug 27, 2024
52de2d1
a
Optimize CycleFold circuit MSM approach (#143) In CycleFold we want to compute $P_{folded} = P_0 + r ⋅ P_1 + r^2 ⋅ P_2 + r^3 ⋅ P_3 + ... + r^{n-2} ⋅ P_{n-2} + r^{n-1} ⋅ P_{n-1}$, since the scalars follow the pattern r^i Youssef El Housni (@yelhousni) proposed to update the approach of the CycleFold circuit to reduce the number of constraints needed, by computing $P_{folded} = (((P_{n-1} ⋅ r + P_{n-2}) ⋅ r + P_{n-3})... ) ⋅ r + P_0$. By itself, this update reduces the number of constraints as the number of points being folded in the CycleFold circuit grows. But it also has impact at the HyperNova circuit, where it removes the need of using the bit representations of the powers of the random value, substancially reducing the amount of constraints used by the HyperNova AugmentedFCircuit. The number of constraints difference in the CycleFold circuit and in the HyperNova's AugmentedFCircuit: - CycleFold circuit: | num points* | old | new | diff | |-------------|-----------|-----------|----------| | 2 | 1_354 | 1_354 | 0 | | 3 | 2_683 | 2_554 | -129 | | 4 | 4_012 | 3_754 | -258 | | 8 | 9_328 | 8_554 | -744 | | 16 | 19_960 | 18_154 | -1_806 | | 32 | 41_224 | 37_354 | -3_870 | | 64 | 83_752 | 75_754 | -7_998 | | 128 | 168_808 | 152_554 | -16_254 | | 1024 | 1_359_592 | 1_227_754 | -131_838 | *num points: number of points being folded by the CycleFold circuit. - HyperNova AugmentedFCircuit circuit | folded instances* | old | new | diff | |-------------------|---------|---------|----------| | 5 | 90_285 | 80_150 | -10_135 | | 10 | 144_894 | 117_655 | -27_239 | | 20 | 249_839 | 192_949 | -56_890 | | 40 | 463_078 | 344_448 | -118_630 | *folded instances: folded instances per step, half of them being LCCCS and the other half CCCS. Co-authored-by: Youssef El Housni <youssef.housni21@gmail.com>
arnaucube committed on Aug 20, 2024
7097c00
P
feat: implement nova's zk layer (#127) * feat: zk nova layer * chore: clippy + trigger CI * chore: add comment for `new` (generating a zk nova ivc proof) * chore: adding text reference to `sample` * chore: use `debug_assert` instead of `cfg(test)` * improve: pass `poseidon_config` by ref Co-authored-by: Carlos Pérez <37264926+CPerezz@users.noreply.github.com> * improve: pass `z_0` by ref Co-authored-by: Carlos Pérez <37264926+CPerezz@users.noreply.github.com> * improve: pass `r1cs` and `cf_r1cs` by ref Co-authored-by: Carlos Pérez <37264926+CPerezz@users.noreply.github.com> * chore: appropriate docs (2) * chore: pass by ref modifications * improve: use single sponge * fix: remove blinding the cyclefold instance, add verifier checks on the prover provided cyclefold intance * fix: assert that the sampled relaxed r1cs is correct * fix: check length of `u_i.x` --------- Co-authored-by: Carlos Pérez <37264926+CPerezz@users.noreply.github.com>
Pierre committed on Aug 18, 2024
c09c52f
C
Enable WASM-compat and monitor it in the CI (#142) * fix: Use `target_pointer_size` conditional compilation There are some parts of the code where is needed to de/serialze `usize`s. These, have sizes that vary depending on the target achitecture the code is compiled for. Hence, this adapts the de/serialization to the specific pointer size for which the crate is being compiled to. * change: Support WASM-compatibility and polish Cargo.toml In order to support Wasm-compat and to simplify and improve `Cargo.toml` readability, the follwing changes have been made: - All the deps that can use `parallel` feature, do so. As `rayon` supports non-threaded targets with a fallback option. See: https://docs.rs/rayon-core/1.12.1/rayon_core/index.html#global-fallback-when-threading-is-unsupported - `ark-grumpking` has been brought to `0.5.0-alpha.0` as `0.4.0` appears to not be in `crates.io` anymore. See: https://crates.io/crates/ark-grumpkin/versions - By default, the crate uses `"ark-circom/default"` which selects the `wasmer/sys` feature such that it knows where wasmer is suposed to be run`. - Added a `wasm` feature which forces `ark-circom/wasm` to be used instead. Which internally selects the `wasmer/js` backend to be used such that in-browser execution is possible. - Added `getrandom` with `js` feature as dependency when `wasm32-unknown-unknown` target is selected such that compilation of the crate for testing or simply building is possible. Notice that with `wasi` and other wasm targets, this is not the case as they're automatically supported. For more info, please check: https://docs.rs/getrandom/latest/getrandom/#webassembly-support * feat: Support WASM-compatibility tests in CI Add support for both testing the build of `sonobe/folding-schemes` for WASM-targets and also, it's build as a dependency for a WASM-crate. This includes a build job for the three main supported rust-WASM targets and the same but for a thrid crate creted on-the-fly which uses `sonobe/folding-schemes` as a dependency. * chore: Add README docs about WASM-compat & feats * ci: don't run WASM-compat job if PR is draft * chore: depend on `arnaucube/circom-compat` fork. Since https://github.com/arnaucube/circom-compat/pull/2 was merged, we can already switch to it as we were depending before. * chore: minimal build/test instructions * fix: CI typos * fix: Update CI to use correct feature sets * fix: `ark-grumpkin` versioning issues As mentioned in https://github.com/privacy-scaling-explorations/sonobe/issues/146 there's a big issue that involves some dependencies of the crate. As a temporary fix, this forces the workspace to rely on a "non-existing" version of `ark-grumpkin` which is immediately patched at workspace-level for a custom version that @arnaucube owns with some cherry-picked commits. While this allows the CI to pass and crate to build, a better solution is needed. * fix: Clippy CI avoiding --all-targets * fix: use `wasm` feat only with folding-schemes
Carlos Pérez committed on Aug 17, 2024
5ec9c2c
a
implement HyperNova's DeciderEth circuit (#132) The HyperNova's DeciderEthCircuit follows a similar logic as Nova's one described in https://privacy-scaling-explorations.github.io/sonobe-docs/design/nova-decider-onchain.html but adapted to HyperNova checks and values.
arnaucube committed on Aug 6, 2024
f6a70fe
w
Generalized CycleFold (#120) * Support randomness of arbitrary length * Rename `N_BITS_RO` to `NOVA_N_BITS_RO` * Compute `r_nonnat` inside `NIFSFullGadget::fold_committed_instance` * Format * Use `CycleFold{CommittedInstance, Witness}` in the context of cyclefold * Format * Fix the creation of dummy witness * Make clippy happy * Improve docs
winderica committed on Aug 5, 2024
ecaecd4
P
feat: fold noir circuits, add an e2e example, tests, a `compile.sh` script and update CI (#131)
Pierre committed on Aug 3, 2024
18a3e0a
P
Enable hiding commitments in nova and hypernova (#129) * feat: enable hiding commitments in nova and hypernova * fix: set blinding values for witness vector * fix: remove cloning of the cyclefold running instance * fix: do not re-use blinding values between prove steps * fix: specify whether the witness should use blinding values using a const generic * feat: create a `dummy` method for nova witnesses as well * chore: clippy - removed unused imports
Pierre committed on Jul 29, 2024
21ff3cf
w
Protogalaxy verifier circuit (#95) * Add in-circuit couterparts of util functions * Support folding `CommittedInstance`s with `u` and `x` * Initial implementation of protogalaxy verifier circuit * Fix the edge case in `all_powers_var` * Absorb `u` and `x` as well * Fix imports * Rename some test functions for clarity * Format * Avoid the use of magic numbers
winderica committed on Jul 18, 2024
6248a90
a
HyperNova: add multi-instances folding to AugmentedFCircuit & IVC (#119) - Adds the logic to support multi-instances folding in HyperNova's AugmentedFCircuit & IVC. - Adds also methods to generate new LCCCS & CCCS instances that don't depend on the main folding chain, to be folded in in the next step - Updates CycleFold circuit & methods to work other folding schemes than Nova, adapting it to fold multiple points per circuit (instead of 2-to-1 as till now) - Handle multi-instances folding in the FoldingScheme trait interface, which expects 'None' in Nova, and 'Some' in HyperNova & other multi-folding schemes.
arnaucube committed on Jul 16, 2024
edadcdd
P
feat: add noname as a frontend to sonobe (#121) * feat: add noname as a frontend to sonobe fix: remove extra `rng` usage Co-authored-by: Carlos Pérez <37264926+CPerezz@users.noreply.github.com> * Update README.md Co-authored-by: arnaucube <root@arnaucube.com> * chore: move ark-noname to dev dependencies in solidity-verifiers cargo --------- Co-authored-by: Carlos Pérez <37264926+CPerezz@users.noreply.github.com> Co-authored-by: arnaucube <root@arnaucube.com>
Pierre committed on Jul 12, 2024
cc1f631
a
fix sumcheck verifier for when poly=0 (#126) Co-authored-by: NiDimi <moonkace24@gmail.com>
arnaucube committed on Jul 11, 2024
bb44a3a
w
Unify the computation of digests and challenges in different folding schemes (#94) * Remove the trait bound `C::BaseField: PrimeField` for better DX * Methods in `TranscriptVar` now exactly matches the ones in `Transcript` * Add `ProtoGalaxyTranscriptVar` and `CommittedInstanceVar` for protogalaxy * betas are unnecessary in "plain" (incoming) instances * Absorb the result of `get_challenge_nbits` as well * `ProtoGalaxyTranscript` now allows absorbing mulitple instances * Always return `Result<(), SynthesisError>` in `ProtoGalaxyTranscriptVar` * Impl `Transcript{Var}` for `PoseidonSponge{Var}` directly and remove `PoseidonTranscript{Var}` * `Transcript::absorb_point` doesn't need to return `Error` * Add `AbsorbNonNative` trait for hashing non-native values Note that now `absorb_point` only supports hashing points whose BaseField is equal to the sponge's field * More efficient `TranscriptVar::absorb_point` by securely removing `is_inf` * Use `sponge` and `transcript` consistently * Clarify the usage of `AbsorbNonNative{Gadget}` * Generic `sponge` and `transcript` params * Avoid unstable `associated_type_bounds` * Reuse `sponge` in hypernova * Clean up redundant imports * Remove unstable code * Clarify the usage of `absorb_point` and `absorb_nonnative`
winderica committed on Jul 8, 2024
16d51d7
a
add hash of public params for Nova & HyperNova (#118) - implement hash of public params for Nova & HyperNova - abstract pp_hash computation for folding schemes - add pp_hash to solidity contract generator to verify the decider proof
arnaucube committed on Jul 5, 2024
c17fcf5
a
Implement HyperNova's IVC into the FoldingScheme trait (#116) - implement the IVC `FoldingScheme` trait for HyperNova - refactor Nova's preprocess logic to make it simplier to use - add to Decider trait (& Nova's DeciderEth) a preprocess method - get rid of the `init_nova_ivc_params` and `init_ivc_and_decider_params` methods in `examples` since this is achieved with the `FS::preprocess` & `Decider::preprocess` methods - (update the examples code to the simplified interface using FS::preprocess & Decider::preprocess)
arnaucube committed on Jul 4, 2024
b566796
k
Generate poseidon constants (#114) * evidence of equivalence of circom and arkworks poseidon params * generate poseidon constants using only `ark_crypto_primitives::sponge::poseidon`
kilic committed on Jul 2, 2024
456dc9f
a
Add CycleFold (https://eprint.iacr.org/2023/1192.pdf) to HyperNova impl (#113)
arnaucube committed on Jun 25, 2024
4ce9a13
a
Implement HyperNova's AugmentedFCircuit (#112) - add LCCCS.hash methods (native & r1cs) - add HyperNova's AugmentedFCircuit with tests
arnaucube committed on Jun 19, 2024
fd942bd
P
Add serde capabilites to `Nova` (#107) * feat: `Nova` can be serialized and deserialized * chore: (temp) allow dead code as serde is not yet used * fix: require trait in `where` to not increase restrictions on `CommitmentScheme` * feat: add file with nova serialization methods * fix: change call to get poseidon config and chore: update traits for serde * chore: remove clang install from CI, move tests and remove unnecessary allow * feat: remove serializing r1cs and cs params and provide them at deserialization time * chore: initialize r1cs within deserialization function directly
Pierre committed on Jun 10, 2024
bdfaa66
a
Optimize native nimfs (#110) * Optimize the HyperNova `compute_g`, `compute_Ls` and `to_lcccs` methods - Optimize the HyperNova `compute_g`, `compute_Ls` and `to_lcccs` methods - in some tests, increase the size of test matrices to a more real-world size. | method | matrix size | old version seconds | new version seconds | | --------------------- | ------------- | ------------------- | ------------------- | | compute_g | 2^8 x 2^8 | 16.48 | 0.16 | | compute_g | 2^9 x 2^9 | 122.62 | 0.51 | | compute_Ls | 2^8 x 2^8 | 9.73 | 0.11 | | compute_Ls | 2^9 x 2^9 | 67.16 | 0.38 | | to_lcccs | 2^8 x 2^8 | 4.56 | 0.21 | | to_lcccs | 2^9 x 2^9 | 67.65 | 0.84 | - Note: 2^16 x 2^16 is the actual size (upperbound) of the circuit, which is not represented in the table since it was needing too much ram to even be computed. * Optimize HyperNova's `compute_sigmas_thetas` and `compute_Q` | method | matrix size | old version seconds | new version seconds | | ------------- | ------------- | ------------------- | ------------------- | | compute_sigmas_thetas | 2^8 x 2^8 | 12.86 | 0.13 | | compute_sigmas_thetas | 2^9 x 2^9 | 100.01 | 0.51 | | compute_Q | 2^8 x 2^8 | 4.49 | 0.07 | | compute_Q | 2^9 x 2^9 | 70.77 | 0.55 | * optimize LCCCS::check_relation & CCCS::check_relation, and remove unnessary methods after last reimplementations
arnaucube committed on Jun 6, 2024
5ea55cf
V
feat (circom): allow to define the step_native in Rust (#105) * create function pointer * custom logic via function pointer * fmt * clippy * rust-version * update review code * fmt
Vu Vo committed on Jun 6, 2024
dd8dacb
o
Fix typos (#109) * fix typos * fix typo
omahs committed on Jun 5, 2024
bda8ad6
a
Add HyperNova's NIMFS circuit (#99) * add HyperNova's NIMFS verifier circuit * update poseidon usage after rebasing to latest main branch changes
arnaucube committed on Jun 4, 2024
59b8bdb
A
BN254 and Grumpkin Poseidon configurations (#106) * Add BN254 and Grumpkin Poseidon configurations * Remove unncecessary comment * Fix BN254 Poseidon config test * Correction * Update folding-schemes/src/transcript/poseidon/grumpkin.rs Co-authored-by: Pierre <pdaixmoreux@gmail.com> --------- Co-authored-by: Pierre <pdaixmoreux@gmail.com>
Ahmad Afuni committed on Jun 3, 2024
852134a
P
Stabilize circom frontend (#101) * refactor test of compute_c circuit to use multiple lcccs&cccs instances * refactor hypernova's compute_c circuit to reduce from `110635` to `553` constraints * fix: change circom fcircuit to extract indexes of inputs and add keccak satisfaction test * fix: disable wire mapping when loading r1cs * chore: update .gitignore and compile.sh * fix: use fixed circom-compat branch * fix: use slice rather than vec ref * chore: add keccak-chain circom * chore: trigger checks * fix: make typos check circom files names but not their content * chore: remove keccak, add tests with more lightweight circom templates, test that circom circuits correctly result in Ok and Err when needed * chore: trigger checks * fix: re-add circuit for full flow example, change naming * chore: comment with link to issue 104, disable constraints check * chore: remove `full_flow_example` from the examples and its corresponding circom circuit * chore: update `circom-compat` repo * chore: clippy * chore: stop excluding circom files from typos checker * chore: remove changes on `typos.toml` --------- Co-authored-by: arnaucube <root@arnaucube.com>
Pierre committed on May 28, 2024
da4ab5c
d
Update README.md (#100)
drewstone committed on May 22, 2024
ed1faee
a
Circuit compute_c reduce constraints (#97) * migrate from CurveGroup to PrimeField in hypernova & ccs when curve whas not needed to simplify the code * refactor test of compute_c circuit to use multiple lcccs&cccs instances * refactor hypernova's compute_c circuit to reduce from `110635` to `553` constraints * apply review nits * fix clippy lints after rust-toolchain v1.76.0
arnaucube committed on May 20, 2024
48947e8
a
Circom external inputs (#91) * circom: add external_inputs * adapt new external_inputs interface to the FoldingScheme trait and Nova impl * adapt examples to new FCircuit external_inputs interface * add state_len & external_inputs_len params to CircomFCircuit * add examples/circom_full_flow.rs * merge the params initializer functions, clippy * circom: move r1cs reading to FCircuit::new instead of each step * CI/examples: add circom so it can run the circom_full_flow example
arnaucube committed on May 6, 2024
d5c1e5f
a
Full flow example (#90) * expose params & structs for external usage * add full_flow example, move examples into 'examples' dir
arnaucube committed on Apr 26, 2024
9bbdfc5
a
Add solidity verifier of the nova+cyclefold (#87) * Add solidity verifier of the nova+cyclefold, and add method to prepare the calldata from Decider's proof. Missing conversion of the point coordinates into limbs (ark compatible) * chore: adding comments linking to the contract's signature * chore: update .gitignore * chore: add num-bigint as dev dependency * fix: work with abs path for storing generated sol code * chore: update comment * feat: solidity verifier working on single and multi-input circuits * feat: multi-input folding verification working + fixing encoding of additive identity in calldata * chore: make bigint a dependency * refactor: import utils functions from utils.rs and make them available from anywhere * chore: make utils and evm available publicly * fix: pub mod instead * chore: make relevant method public and add `get_decider_template_for_cyclefold_decider` to exported objects * solidity-verifiers: move tests to their corresponding files * small update: Cyclefold -> CycleFold at the missing places * abstract nova-cyclefold solidity verifiers tests to avoid code duplication, and abstract also the computed setup params (FS & Decider) to compute them only once for all related tests to save test time * small polish after rebase to last main branch changes * rm unneeded Option for KZGData::g1_crs_batch_points * add checks modifying z_0 & z_i to nova_cyclefold_solidity_verifier test * add light-test feature to decider_eth_circuit to use it in solidity-verifier tests without the big circuit * solidity-verifiers: groth16 template: port the fix from https://github.com/iden3/snarkjs/pull/480 & https://github.com/iden3/snarkjs/issues/479 * add print warning msg for light-test in DeciderEthCircuit * solidity-verifiers: update limbs logic to nonnative last version, parametrize limbs params solidity-verifiers: * update solidity limbs logic to last nonnative impl version, and to last u_i.x impl * parametrize limbs params * add light-test feature: replace the '#[cfg(not(test))]' by the 'light-test' feature that by default is not enabled, so when running the github actions we enable the feature 'light-tests', and then we can have a full-test that runs the test without the 'light-tests' flag, but we don't run this big test every time. The choice of a feature is to allow us to control this from other-crates tests (for example for the solidity-verifier separated crate tests, to avoid running the full heavy circuit in the solidity tests) * move solidity constants into template constants for auto compute of params * polishing * revm use only needed feature This is to avoid c depencency for c-kzg which is behind the c-kzg flag and not needed. * nova_cyclefold_decider.sol header * rearrange test helpers position, add error for min number of steps * in solidity-verifiers: 'data'->'vk/verifier key' * add From for NovaCycleFoldVerifierKey from original vks to simplify dev flow, also conditionally template the batchCheck related structs and methods from the KZG10 solidity template --------- Co-authored-by: dmpierre <pdaixmoreux@gmail.com>
arnaucube committed on Apr 25, 2024
97df224
a
add README.md (#39) * Initialize the README.md with a sketch of the structure * add warning and draft diagram * add authors & years to schemes, add a pre-sketch of the 'development' section * Readme: add link to Carlos talk on folding schemes * readme: sketch sections: offchain & onchain decider, add todo for references * readme: add example of FCircuit & folding * Readme: add lib pipeline diagram, add decider code example * add cyclefold-nova-diagram.png, decider-onchain-flow-diagram.png * polish cli descriptions * small update in the Warning box * add sonobe naming * add folding-main-idea-diagram.png * missing sonobe renaming * migrate part of the README.md to sonobe-docs * rm imgs/, load them from sonobe-docs * tiny update * chore: start update README * add acknolwedgments links and text, small polishing of the overall text * extend folding introduction & sonobe overview * img text alignment * chore: update readme * chore: typos, bits of reformulation, centering images * chore: remove btc example since can not be used as is * rm .vscode dir * readme: merge the duplicated sections into a single one adapting the texts * add Docs badge with link, update acknowledgments * add ci & license badges * fix cli link, add solc mention in solidity-verifiers/readme * small polishing * fix img alignment * rm badges, the reasoning is: - The License badge is not needed since there are already many links to the license both in the readme and in the GitHub UI - The CI checks badge, already appears in the GitHub UI in the last commit preview at the main repo page. Furthermore, after some months of inactivity, the badge would be 'gray' as 'inactive'. - The only badge that I was trying to get there is the 'docs' badge, to make it very clear that the docs page exists, but it was a bit to hard visually to have a single badge there, and furthermore the docs link already appears in the readme twice, and also in the GitHub UI right-panel. --------- Co-authored-by: dmpierre <pdaixmoreux@gmail.com>
arnaucube committed on Apr 17, 2024
8b23303
w
Fix the incorrect `NonNativeAffineVar::inputize` implementation (#89) * Fix the incorrect `NonNativeAffineVar::inputize` implementation * Fmt and clippy
winderica committed on Apr 17, 2024
d23e6d1
w
Reduce the number of constraints in `DeciderEthCircuit` (#88) * Add a dedicated variant of `mat_vec_mul_sparse` for `NonNativeFieldVar` * Switch to a customized in-circuit nonnative implementation for efficiency * Comments and tests for `NonNativeUintVar` * Make `CycleFoldCircuit` a bit smaller * Faster trusted setup and proof generation by avoiding some nested LCs * Check the remaining limbs in a more safe way * Format * Disable the non-native checks in tests again * Clarify the group operation in `enforce_equal_unaligned` * Explain the rationale behind non-native mat-vec multiplication * Explain the difference with some other impls of `enforce_equal_unaligned` * Format
winderica committed on Apr 16, 2024
b648ddb
y
Adapt Frontend/Circom for FCircuit Trait (#71) * initial * improved z_i * improved * Redefined the .circom and the test code for CircomWrapper * added test function for wrapper_circuit which has circom_fcircuit, but incompatibility error of Pairing and Pallas * changed the path in the gitignore * Remove circom generated path * improved variable vector * Pallas::Fr * improved to the primefield * mentioned the issues:1. extract z_i1(only public output) 2.constraintsSystem and its Ref * modified * public input in circom * generalized; removed the hardcorded value * Generalization using FpVar::<Fr>::new_input * initial * improved z_i * improved * Redefined the .circom and the test code for CircomWrapper * added test function for wrapper_circuit which has circom_fcircuit, but incompatibility error of Pairing and Pallas * Remove circom generated path * improved variable vector * Pallas::Fr * improved to the primefield * mentioned the issues:1. extract z_i1(only public output) 2.constraintsSystem and its Ref * modified * Small updates: - update cubic_circuit.circom: remove extra constraint, remove public inputs - remove allocations of inputs in arkworks - add return of z_{i+1} at the end of CircomtoFCircuit::generate_step_constraints With this tmp fix the `test_circom_step_constraints` passes, but needs to be iterated and polished. * Update circom-compat to re-allocate inputs * update after rebase to latest main: add usage of self.state_len() to circom frontend * move circom frontend related structs into frontend/circom dir * clippy lints * extract_witness * add comments * clean * fmt, lint, and spell * CI Check trigger * fmt * applied the feedback --------- Co-authored-by: Y5 <76672645+yugonsan@users.noreply.github.com> Co-authored-by: arnaucube <root@arnaucube.com>
yugocabrio committed on Apr 15, 2024
03f6691
w
Reduce the number of constraints in `AugmentedFCircuit` for Nova (#86) * 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
winderica committed on Apr 12, 2024
4dcb981
w
Add the digest of the Relaxed R1CS instance for CycleFold as a public input to `AugmentedFCircuit` (#84) * 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
winderica committed on Apr 11, 2024
6a7dd93
a
Link committed instances and r to the public input x in cyclefold circuit (#81) * CycleFold circuit: link r,U_i,u_i point coords as inputs * DeciderEth::prove: rm repeated cmT, r, W_i1 computation
arnaucube committed on Apr 4, 2024
b8db622
a
Compute Decider's CM challenges in Groth16 circuit, link G16 & KZG proofs in Onchain Decider, refactor CommitmentScheme trait (#79) * 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.
arnaucube committed on Mar 26, 2024
fe9a488
C
Add CLI interface for verifier contract generation (#74) * 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
Carlos Pérez committed on Mar 18, 2024
1072b66
a
Add external inputs logic to F function/circuit. Add an example of usage with external inputs too. (#78) * Add external inputs logic to F function/circuit. Add an example of usage with external inputs too. * Add examples run into CI
arnaucube committed on Mar 11, 2024
a4905c8
a
Change CycleFold circuit approach (#77) * 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
arnaucube committed on Mar 1, 2024
602a367
a
Add IPA commitment scheme and the respective circuit verifier gadget (#72) * 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
arnaucube committed on Mar 1, 2024
b25037e
a
Add typos tool to CI to automate typo detection (#76) * Add typos to CI * Apply typos suggestions * missing typos
arnaucube committed on Feb 26, 2024
9159c5c
a
Fix Nova multi-elements state (#73) * 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
arnaucube committed on Feb 22, 2024
89d6067
P
Add solidity groth16, kzg10 and final decider verifiers in a dedicated workspace (#70) * 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>
Pierre committed on Feb 9, 2024
63dbbfe
a
Add Decider impl for Nova onchain (#66) * 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
arnaucube committed on Feb 8, 2024
97e973a
S
make calculation of F(X) in protogalaxy prover happen in O(n) (#52) * 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>
Silur committed on Feb 5, 2024
383a70d
a
Fit Nova+CycleFold into `FoldingScheme` trait & Add `examples/` for folding SHA256 circuit (#64) * Update FoldingSchemes trait, fit Nova+CycleFold - update lib.rs's `FoldingScheme` trait interface - fit Nova+CycleFold into the `FoldingScheme` trait - refactor `src/nova/*` * Add `examples` dir, with Nova's `FoldingScheme` example * polishing * expose poseidon_test_config outside tests
arnaucube committed on Feb 2, 2024
186766c
a
Adapt Nova usage of commitment to the generic trait (#63)
arnaucube committed on Jan 30, 2024
f85a056
a
Add CommitmentProver trait, and add KZG prover to it (#62) * 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>
arnaucube committed on Jan 25, 2024
47e47cc
a
refactor frontend composition, update usage of arkworks CS helpers, refactor test circuits (#54) 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.
arnaucube committed on Jan 16, 2024
7e3d2df
P
A circuit for computing c, from section 5, step 5 of "A multi-folding scheme for CCS" (#61) * 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>
Pierre committed on Jan 15, 2024
46e5387
a
Nova+CycleFold Decider circuit (for onchain use case) (#49) * Add Pedersen commitments gadget * Add Nova+CycleFold Decider circuit (for onchain approach) "onchain"==Ethereum's EVM * merge src/decider into src/folding/nova/decider * PR review updates
arnaucube committed on Jan 10, 2024
4981980
P
Feature/sumcheck circuit (#47) * feat: init sumcheck.rs * chore: rename * feat: update lib and add trait for transcript with vec storing challenges * bugfix: mut self ref of transcript * feat: tentative sum-check using poseidon * refactor: remove extension trait and use initial trait * refactor: stop using extension trait, use initial Transcript trait * feat: generic over CurveGroup sum-check verifier and algorithm * feat: implement generic sum-check veriy * bugfix: cargo clippy --fix * chore: cargo fmt * feat: (unstable) sum-check implementation * feat: start benches * chore: run clippy * chore: run cargo fmt * feat: add sum-check tests + benches * chore: clippy + fmt * chore: remove unstable sumcheck * chore: delete duplicated sum-check code * chore: remove deleted sum-check code from lib.rs imports * feat: remove non generic traits, implement sum-check with generic trait and add test * chore: remove non-generic struct * chore: remove non generic verifier * feat: make nifms generic over transcript and update to use poseidon transcript * chore: cargo fmt * chore: remove tmp benches * chore: update cargo.toml * refactor: remove Generic suffix * feat: prover state generic over CurveGroup * chore: disable clippy type complexity warning * refactor: remove Transcript type and espresso transcript dependency * refactor: SumCheckProver generic over CurveGroup * feat: init sumcheck.rs * chore: rename * feat: update lib and add trait for transcript with vec storing challenges * bugfix: mut self ref of transcript * feat: tentative sum-check using poseidon * refactor: stop using extension trait, use initial Transcript trait * feat: generic over CurveGroup sum-check verifier and algorithm * feat: implement generic sum-check veriy * bugfix: cargo clippy --fix * chore: cargo fmt * feat: (unstable) sum-check implementation * feat: start benches * chore: run clippy * chore: run cargo fmt * feat: add sum-check tests + benches * chore: clippy + fmt * chore: remove unstable sumcheck * chore: delete duplicated sum-check code * chore: remove deleted sum-check code from lib.rs imports * feat: remove non generic traits, implement sum-check with generic trait and add test * chore: remove non-generic struct * chore: remove non generic verifier * feat: make nifms generic over transcript and update to use poseidon transcript * chore: cargo fmt * chore: remove tmp benches * chore: update cargo.toml * refactor: remove Generic suffix * feat: prover state generic over CurveGroup * chore: disable clippy type complexity warning * refactor: remove Transcript type and espresso transcript dependency * refactor: SumCheckProver generic over CurveGroup * feat: adds `compute_lagrange_poly`, returning a `DensePolynomial` to extract coeffs from * chore: add assert on interpolated poly degree vs initial poly degree * refactor: use `compute_lagrange_poly` in `SumCheckVerifier` instead of `interpolate_uni_poly` * refactor: have `TranscriptVar` be generic over `CurveGroup` for consistency * refactor: change back to being generic over field * feat: start to use `PoseidonTranscriptVar` struct * chore: add line to eof for `Cargo.toml` * chore: naming consistency with espresso/sum_check folder * bugfix: add error handling on sum-check prove and verify * chore: clippy fix * chore: add line at eof * feat: switch to using coeffs instead of evals in sum-check * bugfix: tmp remove sanity check in nimfs * refactor: update sanity check * refactor: update verifier evaluation form + add comment * chore: run clippy * fix: correct merge artifacts * feat: verify circuit passing * refactor: change naming to use the `Gadget` suffix, update `verify_sumcheck` to not have `&self` as first argument, update test * feat: testing on polynomials with various number of variables * refactor: update method name * fix: avoid rust-analyzer from complaining * fix: fix clippy complains * chore: cargo clippy * chore: udpate arg name for `SumCheckVerifierGadget` * refactor: remove unnecessary cloning in sumcheck circuit * refactor: impl `get_poly_vars_from_sumcheck_proof` for `IOPProof` * chore: group imports * refactor: update `P(0) + P(1)` and name it `eval` * chore: clippy + fmt * refactor: move `compute_lagrange_poly` to `utils` * fix: wrong import * chore: cargo fmt * refactor: absorb num vars and max degree within sumcheck circuit * refactor: update name to `compute_lagrange_interpolated_poly` and add comment * feat: create `IOPProofVar`, which implements the `AllocVar` trait * fix: clippy allow `type_complexity` on return type of `SumCheckVerifierGadget` * refactor: use `VPAuxInfo` instead of virtual type, remove `_` prefix in params name * feat: add tests on computed & returned values from `verify` * refactor: use `new_witness` instead of `new_variable` Co-authored-by: arnaucube <root@arnaucube.com> * chore: clippy * fix: remove `unwrap()` within `verify()` Co-authored-by: arnaucube <root@arnaucube.com> * chore: add comment on `unwrap()` * refactor: move `compute_lagrange_interpolated_poly` tests to `lagrange_poly.rs` --------- Co-authored-by: arnaucube <root@arnaucube.com>
Pierre committed on Jan 4, 2024
05f4991
a
update RelaxedR1CSGadget to work with FieldVar trait so we can plug in FpVar and NonNativeFieldVar indistinctly (#46) 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.
arnaucube committed on Jan 2, 2024
4b929e8
a
Port ProtoGalaxy from https://github.com/arnaucube/protogalaxy-poc adapting it to the current folding-schemes lib (#37) 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.
arnaucube committed on Dec 18, 2023
b9af318
a
Implement CycleFold in Nova's IVC (#45) * Implement CycleFold in Nova's IVC (CycleFold: https://eprint.iacr.org/2023/1192) * CycleFoldChallengeGadget: add points coordinates as bytes * Apply PR review suggestions
arnaucube committed on Dec 18, 2023
b4f42e7
P
Feature/sumcheck (#40) * feat: init sumcheck.rs * chore: rename * feat: update lib and add trait for transcript with vec storing challenges * bugfix: mut self ref of transcript * feat: tentative sum-check using poseidon * refactor: remove extension trait and use initial trait * refactor: stop using extension trait, use initial Transcript trait * feat: generic over CurveGroup sum-check verifier and algorithm * feat: implement generic sum-check veriy * bugfix: cargo clippy --fix * chore: cargo fmt * feat: (unstable) sum-check implementation * feat: start benches * chore: run clippy * chore: run cargo fmt * feat: add sum-check tests + benches * chore: clippy + fmt * chore: remove unstable sumcheck * chore: delete duplicated sum-check code * chore: remove deleted sum-check code from lib.rs imports * feat: remove non generic traits, implement sum-check with generic trait and add test * chore: remove non-generic struct * chore: remove non generic verifier * feat: make nifms generic over transcript and update to use poseidon transcript * chore: cargo fmt * chore: remove tmp benches * chore: update cargo.toml * refactor: remove Generic suffix * feat: prover state generic over CurveGroup * chore: disable clippy type complexity warning * refactor: remove Transcript type and espresso transcript dependency * refactor: SumCheckProver generic over CurveGroup * chore: add line to eof for `Cargo.toml` * bugfix: add error handling on sum-check prove and verify * chore: clippy fix * chore: add line at eof * fix: use `map_err` and call `to_string()` on `PolyIOPErrors`
Pierre committed on Dec 15, 2023
876e23c
P
feat: add TranscriptVar trait (#42) * feat: add TranscriptVar trait * Update src/transcript/poseidon.rs Co-authored-by: arnaucube <root@arnaucube.com> --------- Co-authored-by: arnaucube <root@arnaucube.com>
Pierre committed on Dec 5, 2023
14a0b46
a
Feature/nova ivc (#36) * 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)
arnaucube committed on Nov 24, 2023
905ba44
a
Feature/f circuit multiple in outs (#35) * extend FCircuit to work with multiple ins & outs * refactor FCircuit trait to work with io for multiple frontends support
arnaucube committed on Nov 6, 2023
6d919d7
a
Add Pedersen::{commit,open,verify} MSM error handling (#34)
arnaucube committed on Oct 31, 2023
8edea23
a
implement Nova's AugmentedFCircuit (#33) * 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
arnaucube committed on Oct 30, 2023
597ac27
Y
Circom wrapper's helper function (#26) * 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>
Y5 committed on Oct 18, 2023
7656c6b
a
impl hash committed instance gadget (#17) (#31) together with the native impl compatible with the gadget one
arnaucube committed on Oct 12, 2023
422db75
a
Refactor Matrix vectors and Logical operation (#28) * Refactor Matrix vectors operation * Refacotr NIFS logical operation
ashWhiteHat committed on Oct 10, 2023
9a2a1fd
a
add error handling to several pending methods (#30)
arnaucube committed on Oct 4, 2023
13e471a
a
Port/hypernova multifolding (#10) * 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>
arnaucube committed on Sep 11, 2023
8256c27
a
Add decider circuit RelaxedR1CS (#21) - 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
arnaucube committed on Sep 7, 2023
ac913ab
a
Implement Nova's NIFS.Verify circuits (with CycleFold) (#11) * 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
arnaucube committed on Sep 5, 2023
d9887af
a
Implement CycleFold's EC RLC check circuit (#9)
arnaucube committed on Aug 29, 2023
9ae046c
a
Port Espresso's VirtualPoly, MLE and SumCheck (#8) 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.
arnaucube committed on Aug 29, 2023
b4a0b50
a
Implement Nova's NIFS.P & NIFS.V (#7)
arnaucube committed on Aug 23, 2023
15e2886
a
Add initial CCS mod: (#6) - port initial CCS structure with methods from multifolding-poc - add R1CS helper methods, which will be used in Nova impl
arnaucube committed on Aug 23, 2023
240b916
a
Add utils::vec & pedersen modules (#5) - utils::vec module: port a mix of vec utils from nova-study, multifolding-poc and protogalaxy-poc repos - pedersen.rs: Pedersen commitment module - other: - update FoldingScheme trait interface: rm rng, update internal types naming as agreed in today's call - update Cargo.toml dev-dependencies imports, since bn254 - grumpkin is not ready yet, use bls12-377 - bw6-761 curve cycle - transcript module: add absorb_point method
arnaucube committed on Aug 22, 2023
bc81fbe
H
feat: port CI from `halo2curves` (#4)
Han committed on Aug 17, 2023
77a0c8e
a
Feature/traits (#3) * 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>
arnaucube committed on Aug 17, 2023
16e261b
H
Initial commit
Han committed on Aug 15, 2023
eea9bf2