argumentcomputer / argumentcomputer/sphinx
Support montgomery form directly in non-native field operations
- Dominant language
- Rust
- Stars
- 80
- Forks
- 8
- PR merge metrics
- No merged PRs in 30d
Description
Many implementations of elliptic curves in libraries (e.g. [`bls12_381`](https://github.com/lurk-lab/bls12_381)) internally make use of the [montgomery form](https://en.wikipedia.org/wiki/Montgomery_modular_multiplication#Montgomery_form) to represent field elements, where a number `a mod P` is stored as `aR mod P` for some factor `R` (for `bls12_381`, this is `2^384 mod P`).
Currently, the existing [non-native field operations](https://github.com/wormhole-foundation/wp1/tree/dev/core/src/operations/field) supported all simply deal with regular `a mod P` representations of these numbers. In the case of addition and subtraction nothing changes, but when multiplication and division are involved, the `R` factor needs to be dealt with separately. This incurs overhead by requiring multiple additional operations. It would be desirable to have non-native field operations that natively directly support the montgomery form when performing multiplication and division/inversion.
This is not a high-priority blocking issue since we can work around this issue by using a field multiplication precompile to perform the reduction, i.e. multiplying by `R^(-1)` to remove the `R` factor, perform the usual operation, then multiply back by `R` to return it to its montgomery representation. There is still overhead in doing this though, specially in long-running computations that perform many of these roundtrips.
Contributor guide
Research direction
Start by reading the existing non-native field operations under core/src/operations/field and compare how multiplication and division/inversion handle regular field representations. The issue describes Montgomery-form support as the goal; done should provide operations that handle the R factor directly and avoid the described conversion roundtrips.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- cryptography
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100