You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Currently for verifying in circuit that (f_i)_i is a subset of a table (s_i)_i, we record the f_i, use a hint to compute the multiplicity e_i of the f_i and we check using a random challenge x that Pi_i (x-s_i)^e_i = Pi_i (x-f_i). The e_i are themselves internal variables and this computation leads to a lot of exponentiations.
We should use the logarithmic derivatives (taken from Caulk) to rather check that Sum_i e_i / (x-s_i) = Sum_i 1 / (x-f_i). Those are rational functions, but as long as x is not in the set of poles (that is it does not belong to {f_1, .., f_n} ) Schwartz Zippel lemma (univariate case) works exactly as for polynomials (in fact for polynomials we just avoid the set of poles which is the infinity when sampling a random challenge).
This would save all the exponentiations by the e_i.
* feat: range checks using log derivative, fixes#581
* feat: compute constraints for log-deriv range check
* feat: use unchecked division
* chore: cleanup test
* feat: compress groth16 linear expression
* docs: refer to log-derivate idea paper
* fix: include exponents in commitment
* test: more cleanup
* fix: compute a bit more complex fake commit
* test: update circuit statistics
---------
Co-authored-by: Ivo Kubjas <ivo.kubjas@consensys.net>
Currently for verifying in circuit that (f_i)_i is a subset of a table (s_i)_i, we record the f_i, use a hint to compute the multiplicity e_i of the f_i and we check using a random challenge x that Pi_i (x-s_i)^e_i = Pi_i (x-f_i). The e_i are themselves internal variables and this computation leads to a lot of exponentiations.
We should use the logarithmic derivatives (taken from Caulk) to rather check that Sum_i e_i / (x-s_i) = Sum_i 1 / (x-f_i). Those are rational functions, but as long as x is not in the set of poles (that is it does not belong to {f_1, .., f_n} ) Schwartz Zippel lemma (univariate case) works exactly as for polynomials (in fact for polynomials we just avoid the set of poles which is the infinity when sampling a random challenge).
This would save all the exponentiations by the e_i.
Here is the ref for the logarithmic derivative
The text was updated successfully, but these errors were encountered: