feat: add field extension support over native fields #1493
Conversation
There was a problem hiding this comment.
Pull Request Overview
This PR introduces support for field extensions over native fields to enable non‐native arithmetic operations in small fields.
- Added configurable options to set field extensions or degrees.
- Implemented basic arithmetic operations (reduce, add, sub, mul) over extension fields.
- Provided comprehensive tests for extension field operations.
Reviewed Changes
Copilot reviewed 4 out of 4 changed files in this pull request and generated 3 comments.
| File | Description |
|---|---|
| std/math/fieldextension/option.go | Added configuration options for specifying field extension details. |
| std/math/fieldextension/fieldextension_test.go | Added unit tests for Reduce, Add, Sub, and Mul functions. |
| std/math/fieldextension/fieldextension.go | Implemented extension field arithmetic functions. |
| std/math/fieldextension/default_extensions.go | Defined default extension polynomials. |
|
I think I'll skip the inverse for now, it is not needed for the field emulation over smallfield for now. We can implement it in the future when such need arises. So, it is ready for review for now. |
|
For the inverse, we implement it in gnark-crypto generically for ext. 2 and 3 as in Alg.8 and 17 resp. in https://eprint.iacr.org/2010/354.pdf. |
yelhousni
left a comment
yelhousni
left a comment
There was a problem hiding this comment.
Looks good. Although 2 remarks:
- what is the point of having a generic implementation only for baby/koala bear? we can have
Mul()optimised if we specialise the implementation. - we can also add
Square()as a separate method.
You're right, we don't particularly need generic implementation. I started doing it in the context of field emulation over small field (particularly see https://github.com/Consensys/gnark/pull/1495/files#diff-d4ac9a2f1804d448a0c0743b58bc4494e0eff8e396cb6ae48d58ff01befeaee2L169-R205 and https://github.com/Consensys/gnark/pull/1495/files#diff-d4ac9a2f1804d448a0c0743b58bc4494e0eff8e396cb6ae48d58ff01befeaee2R969-R999, i.e. we compute Particularly - we don't need to be compatible with the koala/baby-bear extensions we have in gnark-crypto, I'm only interested in having degree high enough that SZ is sound. Thats why I'm using the direct simple extension ( But for some reason I though it would be useful if we have a general interface for any possible direct extension. Imo the interface would support it, I just didn't implement it yet. So, if you would have ideas how to optimize Another thing - imo we may not need to call |
|
Merged currently as is - it is good enough for unblocking the rest of the PRs, but there are still many things to do to make the gadget more performant and useful. Will create issue for that. |
Description
For the upcoming support for the non-native arithmetic over native small fields we need to perform multiplication checks in a field extension to obtain the required soundness level. Instead of doing an ad-hoc implementation in the field emulation package, we separate it into a standard interface so it could be reused.
The implementation is currently very basic and supports only specific types of field extensions (
x^d + aandx^d + 1). Will extend the package if the need arises.Currently it doesn't support inversion and division as there wasn't direct need for it directly in the field emulation package. However, if we want to support logderivative argument in native small field, then we need to have inversion/division. However, gnark wouldn't directly have backends targeting small fields and the selector columns and witness assignment would be exported to Linea prover, which would handle range checks itself. And currently range checks is the only use case we would need logderivative argument.
But I think it would be good to have in case we would have some other lookup usages in circuits used for Linea. @yelhousni, @ThomasPiellard - do we have a good reference for a generic inversion algorithm in gnark or gnark-crypto over any field and extension?
Type of change
How has this been tested?
How has this been benchmarked?
Checklist:
golangci-lintdoes not output errors locally