Support montgomery form directly in non-native field operations
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 35/100
- Issue type
- Feature
- Clarity
- Mostly clear
- Activity status
- Stale
- Tech stack
- rust
- Domain
- cryptography
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.
Description
Many implementations of elliptic curves in libraries (e.g. bls12_381) internally make use of the 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 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.
- Dominant language
- Rust
- Stars
- 80
- Forks
- 8
- PR merge metrics
- No merged PRs in 30d
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from argumentcomputer/sphinx
-
Difficulty 4/5 3-5 days Newbie friendliness 38/100
argumentcomputer/sphinx#206 ·
-
The termination check is under-constrained due to incomplete check of "public_values.next_pc == 0". Open
Difficulty 3/5 1-2 days Newbie friendliness 72/100
argumentcomputer/sphinx#205 ·
-
Difficulty 5/5 Over a week Newbie friendliness 20/100
argumentcomputer/sphinx#204 ·
-
Difficulty 5/5 Over a week Newbie friendliness 25/100
argumentcomputer/sphinx#188 ·
-
SHA-512 improvements Open
Difficulty 4/5 3-5 days Newbie friendliness 35/100
argumentcomputer/sphinx#181 ·
All issues in argumentcomputer/sphinx
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 85/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
Eynzof/Hermes-CN-Desktop#610 ·
-
bug team:backend track:services-maintenance
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
cowprotocol/services#4950 ·
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
gitbutlerapp/gitbutler#15998 · 1 comment ·
-
bug triage:deciding
Difficulty 1/5 Under an hour Newbie friendliness 88/100
open-telemetry/otel-arrow#4132 ·