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.

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

use the permutation to constrain assert_eq(_var) #55

Open
mimoo opened this issue Apr 26, 2024 · 1 comment
Open

use the permutation to constrain assert_eq(_var) #55

mimoo opened this issue Apr 26, 2024 · 1 comment
Labels

Comments

@mimoo
Copy link
Contributor

mimoo commented Apr 26, 2024

in kimchi/plonk, no need to have a gate to constrain that two vars are equal, it's enough to create a wire between them with the permutation

the same is true for constraint_eq_const (add_constant should create the constant and then wire them)

@mimoo mimoo added the easy label Apr 26, 2024
@mimoo mimoo changed the title use the permutation to constrain constraint_eq_var use the permutation to constrain assert_eq May 6, 2024
@mimoo mimoo changed the title use the permutation to constrain assert_eq use the permutation to constrain assert_eq(_var) May 6, 2024
levihackerman-102 added a commit to levihackerman-102/noname that referenced this issue Jun 11, 2024
levihackerman-102 added a commit to levihackerman-102/noname that referenced this issue Jun 15, 2024
@mimoo
Copy link
Contributor Author

mimoo commented Jun 16, 2024

I think the way we do the permutation right now is too naive to allow us to implement this optimization right away. We need to be able to keep track of cycles of variables, and to MERGE cycles of variables when we wire two variables that belong to two different cycles. We did this in snarky using union finds: https://github.com/o1-labs/proof-systems/blob/master/kimchi/src/snarky/constraint_system.rs#L528

I explain how this works here: https://github.com/o1-labs/proof-systems/blob/master/book/src/snarky/kimchi-backend.md#implementation-details

@mimoo mimoo added medium and removed easy labels Jun 16, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant