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
This PR adds direct multivariate polynomial evaluation using non-native arithmetic. It can be used to perform direct extension computation, used in pairing computation (BW6, BN254, BLS12-377).
The idea is very similar to the multiplication approach, but when we do the evaluation check then we can work with arbitrary multivariate polynomials. This is really beneficial as the most of the cost is in range checking the result and the quotient, so when we can amortize multiple operations.
Another PR using it in BW6 evaluation is incoming, but it saves more than 50% of constraints in the Miller loop computation.
NB! One thing which I haven't figure out is how to allow negative coefficients. For example for BW6 we need to multiply by the non residue -4 for which we currently use a non-native value. But this changes the carry computation and SZ check which still isn't fully functional. But I think I'll keep it for the future to get working.
Type of change
[x] New feature (non-breaking change which adds functionality)
How has this been tested?
[x] TestPolyEval
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
Description
This PR adds direct multivariate polynomial evaluation using non-native arithmetic. It can be used to perform direct extension computation, used in pairing computation (BW6, BN254, BLS12-377).
The idea is very similar to the multiplication approach, but when we do the evaluation check then we can work with arbitrary multivariate polynomials. This is really beneficial as the most of the cost is in range checking the result and the quotient, so when we can amortize multiple operations.
Another PR using it in BW6 evaluation is incoming, but it saves more than 50% of constraints in the Miller loop computation.
NB! One thing which I haven't figure out is how to allow negative coefficients. For example for BW6 we need to multiply by the non residue -4 for which we currently use a non-native value. But this changes the carry computation and SZ check which still isn't fully functional. But I think I'll keep it for the future to get working.
Type of change
How has this been tested?
Checklist:
golangci-lintdoes not output errors locally