arnaucube
arnaucube/sonobePublic Self-hosted repository

Commit history

da4ab5c93706e88c211a44759af4f3647fbb94b2
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