Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

feat(ivc): impl cyclefold #373

Open
cyphersnake opened this issue Oct 21, 2024 · 0 comments
Open

feat(ivc): impl cyclefold #373

cyphersnake opened this issue Oct 21, 2024 · 0 comments
Assignees
@cyphersnake
Milestone
CycleFold

Comments

@cyphersnake
Copy link
Collaborator

cyphersnake commented Oct 21, 2024 •
edited
Loading

Assemble all components of the Cyclefold protocol, similar to ivc::sangria::IVC.

Depends on #372 for public parameters and all previous issues (#366 #367 #368 #369 #370 #371 #372 ) for core components.
@cyphersnake cyphersnake added this to the CycleFold milestone Oct 21, 2024
@cyphersnake cyphersnake self-assigned this Oct 21, 2024
@cyphersnake cyphersnake mentioned this issue Oct 21, 2024
Open
@cyphersnake cyphersnake changed the title feat(ivc): implement cyclefold feat(ivc): impl cyclefold Oct 21, 2024
@cyphersnake cyphersnake mentioned this issue Oct 22, 2024
Closed
cyphersnake added a commit that referenced this issue Dec 16, 2024
@cyphersnake
feat(ivc): impl cyclefold zero step
ddd13b6 
**Motivation**
Part of #373 and testing of #369

**Overview**
The first part of the implementation of the zero step cyclefold

__Temporarily commented out part of cyclefold step folding circuit concerning pairing check__
@cyphersnake cyphersnake mentioned this issue Dec 16, 2024
Open
cyphersnake added a commit that referenced this issue Dec 16, 2024
@cyphersnake
feat(ivc): impl cyclefold zero step
ae71038 
**Motivation**
Part of #373 and testing of #369

**Overview**
The first part of the implementation of the zero step cyclefold

__Temporarily commented out part of cyclefold step folding circuit concerning pairing check__
cyphersnake added a commit that referenced this issue Dec 16, 2024
@cyphersnake
test(ivc): cyclefold ivc zero step
3c519bf 
**Motivation**
First part of tests of #373

**Overview**
WIP
This was referenced Dec 16, 2024
Closed
Closed
cyphersnake added a commit that referenced this issue Jan 8, 2025
@cyphersnake
fix(gadgets): additional unsafe checks
9967306 
**Motivation**
During implementation #373, it was discovered that the ecc gadget does
not work correctly when multiplying zero points

The point is that unsafe methods were called that were unsafe for some
inputs, but it was implied that their result was not used in case of a
match. However, this led to incorrect witness (verification errors),
because the logic should be the opposite - the verification should go
before the call.

**Overview**
- Nonnull checks are performed BEFORE unsafe blocks are called
- Added tests
- For tests with ecc `K_TABLE_SIZE` was increased, because additional lines for non-zero checks
@cyphersnake cyphersnake mentioned this issue Jan 8, 2025
Open
cyphersnake added a commit that referenced this issue Jan 8, 2025
@cyphersnake
feat(gadgets): impl bn::from_assigned_value_to_limbs
5f3ed33 
**Motivation**
Within #373, it was necessary to implement
`from_assigned_value_to_limbs` to compare values from
`support_circuit::instance` and the primary circuit

**Overview**
Implemented the necessary functionality and corrected nuances related to
the number of limb for `BN::zero` functions
@cyphersnake cyphersnake mentioned this issue Jan 8, 2025
Open
cyphersnake added a commit that referenced this issue Jan 8, 2025
@cyphersnake
feat(nifs): support generic number of sangria c-markers
1f2149d 
**Motivation**
Within the sangria folding scheme we have two consistency markers that
fold via multiplication by `r`. For use within cyclefold (#373) we need
9 of them, so we make support for an arbitrary markers len.

Also the second problem was the availability of an accumulator for the
step-circuit instance in nifs::sangria of the columns. Without changes -
it would be necessary to do hash counting for an empty set within
Cyclefold IVC as part of the sagnria check of the accumulator.

**Overview**

The first problem was solved by adding generics to all types

The second problem was solved by wrapping the
accumulator.step_circuit_hash_acc in `Option`, which always zeroes for
step-circuit instances, if they not present. To make it more expressive
as an `Option`, the custom type `SCInstancesHashAcc` was used

Also, to cure conflicts, I temporarily removed the ivc::cyclefold implementation
cyphersnake added a commit that referenced this issue Jan 8, 2025
@cyphersnake
feat(nifs): support generic number of sangria c-markers
e52dfd0 
**Motivation**
Within the sangria folding scheme we have two consistency markers that
fold via multiplication by `r`. For use within cyclefold (#373) we need
9 of them, so we make support for an arbitrary markers len.

Also the second problem was the availability of an accumulator for the
step-circuit instance in nifs::sangria of the columns. Without changes -
it would be necessary to do hash counting for an empty set within
Cyclefold IVC as part of the sagnria check of the accumulator.

**Overview**

The first problem was solved by adding generics to all types

The second problem was solved by wrapping the
accumulator.step_circuit_hash_acc in `Option`, which always zeroes for
step-circuit instances, if they not present. To make it more expressive
as an `Option`, the custom type `SCInstancesHashAcc` was used

Also, to cure conflicts, I temporarily removed the ivc::cyclefold implementation
cyphersnake added a commit that referenced this issue Jan 8, 2025
@cyphersnake
feat(nifs): support generic number of sangria c-markers
b29445f 
**Motivation**
Within the sangria folding scheme we have two consistency markers that
fold via multiplication by `r`. For use within cyclefold (#373) we need
9 of them, so we make support for an arbitrary markers len.

Also the second problem was the availability of an accumulator for the
step-circuit instance in nifs::sangria of the columns. Without changes -
it would be necessary to do hash counting for an empty set within
Cyclefold IVC as part of the sagnria check of the accumulator.

**Overview**

The first problem was solved by adding generics to all types

The second problem was solved by wrapping the
accumulator.step_circuit_hash_acc in `Option`, which always zeroes for
step-circuit instances, if they not present. To make it more expressive
as an `Option`, the custom type `SCInstancesHashAcc` was used

Also, to cure conflicts, I temporarily removed the ivc::cyclefold implementation
@cyphersnake cyphersnake mentioned this issue Jan 8, 2025
Open
cyphersnake added a commit that referenced this issue Jan 8, 2025
@cyphersnake
feat(nifs): support generic number of sangria c-markers
72770d4 
**Motivation**
Within the sangria folding scheme we have two consistency markers that
fold via multiplication by `r`. For use within cyclefold (#373) we need
9 of them, so we make support for an arbitrary markers len.

Also the second problem was the availability of an accumulator for the
step-circuit instance in nifs::sangria of the columns. Without changes -
it would be necessary to do hash counting for an empty set within
Cyclefold IVC as part of the sagnria check of the accumulator.

**Overview**

The first problem was solved by adding generics to all types

The second problem was solved by wrapping the
accumulator.step_circuit_hash_acc in `Option`, which always zeroes for
step-circuit instances, if they not present. To make it more expressive
as an `Option`, the custom type `SCInstancesHashAcc` was used

- Also, to cure conflicts, I temporarily removed the ivc::cyclefold implementation
- Also modules related to sangria were moved to the ivc::sangria submodule.
cyphersnake added a commit that referenced this issue Jan 8, 2025
@cyphersnake
fix(nifs): protogalaxy initial acc
6070ee5 
**Motivation**
ProtoGalaxy accumulator was created immediately by `!is_sat`, which prevents folding in #373

**Overview**
- The protogalaxy accumulator logic has been changed
- AssignedBigUint within ivc::protogalaxy is now an array. This generated a certain number of try_into().unwrap(), however, these will be cleaned up soon
- Changed the order of absorption in ro, for consistency with cyclefold
@cyphersnake cyphersnake mentioned this issue Jan 8, 2025
Open
cyphersnake added a commit that referenced this issue Jan 8, 2025
@cyphersnake
feat(ivc): impl cyclefold::sfc
f6693eb 
**Motivation**
This PR combines all the changes for operability #373

**Overview**
Refactor and enhance `Support Circuit` input handling and trace consistency checks
- Renamed `PairedPlonkInstance` and `PairedTrace` to `SupportPlonkInstance` and `SupportTrace` for better alignment with the functionality
- Adjusted handling of `W_commitments`, `instances`, and `challenges` to support consistent input representation across both native and circuit operations.
- Introduced constants (`W_COMMITMENTS_MAX_LEN` and `W_CHALLENGES_MAX_LEN`) to ensure padded consistency in trace handling.
- Unified handling of `self_trace` and `support_trace` across all steps.
- Reworked consistency marker generation and constraint assignment to ensure accurate outputs even in zero and non-zero step cases.
- Added robust boundary checks for accumulator instances during folding.
cyphersnake added a commit that referenced this issue Jan 8, 2025
@cyphersnake
feat(ivc): impl cyclefold::sfc
360ca6e 
**Motivation**
This PR combines all the changes for operability #373

**Overview**
* Important
- Renamed `PairedPlonkInstance` and `PairedTrace` to `SupportPlonkInstance` and `SupportTrace` for better alignment with the functionality
- Added alignment for W_commitments & challenes, since we don't know them at the "before zero step" stage, this takes 300 extra rows
- Changed `Input` absorption order for consistency from nifs::{sangria,protogalaxy} (Some fields are now converted to bn, oncircuit only)
@cyphersnake cyphersnake mentioned this issue Jan 8, 2025
Open
cyphersnake added a commit that referenced this issue Jan 8, 2025
@cyphersnake
feat(ivc): impl cyclefold::sfc
5bb8218 
**Motivation**
This PR combines all the changes for operability #373

**Overview**
- Renamed `PairedPlonkInstance` and `PairedTrace` to `SupportPlonkInstance` and `SupportTrace` for better alignment with the functionality
- Added alignment for W_commitments & challenes, since we don't know them at the "before zero step" stage, this takes 300 extra rows
- Changed `Input` absorption order for consistency from nifs::{sangria,protogalaxy} (Some fields are now converted to bn, oncircuit only)
cyphersnake added a commit that referenced this issue Jan 8, 2025
@cyphersnake
feat(ivc): impl cyclefold::ivc
810365e 
**Motivation**
Close #368
Close #369
Close #370
Close #372
Close #373
Close #374

**Overview**
Implementation of the cyclefold with test
@cyphersnake cyphersnake mentioned this issue Jan 8, 2025
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@cyphersnake cyphersnake

Labels
None yet
Projects
None yet
Milestone
CycleFold
Development

No branches or pull requests
1 participant
@cyphersnake