search

arkworks-rs / snark

Interfaces for Relations and SNARKs for these relations
https://www.arkworks.rs
Apache License 2.0
770 stars 207 forks source link

Optimisation passes #314

Open jon-chuang opened 3 years ago

jon-chuang commented 3 years ago

So to implement outline_lcs, one should just walk the BTreeMap once in order, and tally the counts. However, if we have highly nested lcs, given an LC upper bound of k, the walk complexity is upper bounded by k^n. Alternatively, one can cache the results by storing an intermediate BTreeMap which for each lc index, in turn contains a vec of tuples of index of the nested lcs contained in the given lc and their counts. This walk complexity is then bounded by n*k^2. Then, we do another walk, in order again, to substitute those lcs with more than one occurrence to a single var lc with coeff one pointing to a newly allocated variable constrained to agree with the value of the lc. Then, when this is inlined/converted to matrices, it will lead to the desired result.

Circuit designers should include parameters to control which optimisation passes are run. One should also include an importable zk system specific (groth16/marlin etc) optimisation pass defaults. The optimisation pass registry should be in r1cs-std

weikengchen commented 3 years ago

The current implementation (here) does not tally indirect counts but only direct counts, which is a shortcut. What do you think?