gnark is a fast zk-SNARK library that offers a high-level API to design circuits. The library is open source and developed under the Apache 2.0 license
In the log-derivative argument check F \in T the prover provides the histogram of the occurrences M of the elements F in T. We then check \sum_i m_i/(X - t_i) == \sum_j 1/(X - f_j).
Previously we always committed to F, T, M to obtain the random challenge r which we used for checking the equality. But as the left-hand side is always known and the equality doesn't hold for invalid M except for negligible probability, then we can avoid committing to F and T.
However, when the table entries and queries are vectors, then we need to challenge the random coefficients for the random linear combination, so we still commit to the queries then.
Doesn't affect Groth16 as there we compute the commitment as a Pedersen vector commitment. But for PLONK as we need to align the committed values to the commitment column and it saves the number of constraints significantly. Depending on the circuit it may be 10-15%.
How has this been benchmarked?
See the updated stats
Checklist:
[x] I have performed a self-review of my code
[x] I have commented my code, particularly in hard-to-understand areas
[x] I have made corresponding changes to the documentation
[x] I have added tests that prove my fix is effective or that my feature works
[x] I did not modify files generated from templates
[x] golangci-lint does not output errors locally
[x] New and existing unit tests pass locally with my changes
[x] Any dependent changes have been merged and published in downstream modules
ivokub
commented
4 weeks ago
Description
In the log-derivative argument check
F \in Tthe prover provides the histogram of the occurrencesMof the elementsFinT. We then check\sum_i m_i/(X - t_i) == \sum_j 1/(X - f_j).Previously we always committed to
F, T, Mto obtain the random challengerwhich we used for checking the equality. But as the left-hand side is always known and the equality doesn't hold for invalidMexcept for negligible probability, then we can avoid committing toFandT.However, when the table entries and queries are vectors, then we need to challenge the random coefficients for the random linear combination, so we still commit to the queries then.
Doesn't affect Groth16 as there we compute the commitment as a Pedersen vector commitment. But for PLONK as we need to align the committed values to the commitment column and it saves the number of constraints significantly. Depending on the circuit it may be 10-15%.
How has this been benchmarked?
See the updated stats
Checklist:
golangci-lintdoes not output errors locally