gnark
gnark copied to clipboard
Improve non-native arithmetic gadget
Non-native arithmetic gadget has now been implemented. Collecting small snippets and improvement ideas for later improvement:
- [x] feat: add Field structure which has methods which return
emulated.Element
instead offrontend.Variable
. Then don't have to cast toemulated.Element
when explicitly needed (for example forsw_emulated
point coords). This would also provide type safety betweenField
andElement
. - [x] perf: implement fast paths for cases where inputs are constants
- [x] refactor: we differentiate between constant and variable. Add checks to ensure user does not try to use constant as value receiver (they still get panic, but for other reasons and isn't helpful for the user)
- [x] refactor: check that the elements belong to the same field in operations.
- [x] refactor: add sanity checks before the operations (e.g. that overflow is sufficient and do not need to reduce)
- [x] refactor: split
variable.go
intovariable.go
andparams.go
- [x] perf: for lookup2 and select we need that the inputs have the same number of limbs and overflow. But actually the can be different, just the result has to have maximum number of limbs and overflow
- [x] feat: remove
Placeholder
when compiling circuits. - [x] perf: maybe there is a more efficient method for checking that multiple bits are zeros.
- [x] bug: #348
- [ ] perf: try to have more efficient splitting of a variable (instead of doing full binary decomposition and recomposition of the slices, create only the needed split)
- [ ] perf: consider the case where the emulated field is a lot smaller than the native field. If the operations never overflow the native field, then maybe there are more efficient ways for reducing the values (we would be interested in Goldilocks field).
- [ ] feat/perf: theoretically it is possible to optimise modular exponentiation using Wesolowsky RSA VDF verification. Not high-priority yet.
- [ ] feat: implement Sqrt, Double, Half, Square
- [ ] perf: look into Montgomery form for representing elements. It may allow for more efficient modular reduction after multiplication (a la Aztec/Jellyfish)
- [ ] perf: when initialising constant from big.Int, then instead of creating all nbLimbs limbs, create only sufficient number of limbs to fit the constant. NB! in this case we should be certain that the placeholder limb count corresponds to the witness limb count.
- [ ] test: implement tests for expected failures
- [ ] related: #416 - add methods on
Field
type which also take theElement
receiver to modify in-place. - [ ] feat: implement parametrised
std/selector.Mux
andstd/selector.Map
. Right now the selectors work only on slices of variables. However, maybe we could parametrise the methods so that we could use the functions onemulated.Element
and other more complex types. - [ ] use #547 for internal hints.
The tasks are nice-to-have future developments for non-native arithmetic. Proposing to postpone for the next release after including more efficient range checks.