zksecurity / noname

Noname: a programming language to write zkapps
https://zksecurity.github.io/noname/
178 stars 44 forks source link

use the permutation to constrain assert_eq(_var) #55

Open mimoo opened 4 months ago

mimoo commented 4 months ago

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 commented 2 months ago

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