RustCrypto / RustCrypto/crypto-bigint
Performance of `overflowing_add`/`overflowing_sub` in comparison to `adc`/`sbb`
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 309
- Forks
- 95
- Avg merge
- 1d 14h
- Merged PRs (30d)
- 3
Description
Within a project I'm working on, I noted notably better overall performance (10-20%) using overflowing_add/overflowing_sub instead of adc/sbb. I presume this is due to being able to constrain the over/underflow to only being a single bit, and not any value within the 64-bit range. Obviously, this comes with the trade-off of not having RustCrypto's efforts to ensure the method compiles to a constant-time set of instructions however.
As discussed here https://github.com/RustCrypto/crypto-bigint/issues/418#issuecomment-1858699908, these methods appear to be constant-time, and my own brief Godbolt doesn't seem to raise any concerns at this time: https://godbolt.org/z/3bPchf93x
I'd like to question if RustCrypto should offer an overflowing_add/overflowing_sub to accelerate use-cases where the carry is so constrainable, albeit deferring to the developer to be correct. Within RustCrypto, this would accelerate the Uint addition functions, assuming my casual observations are replicable.
It would incur a maintenance burden onto RustCrypto, and if the current functions end up compiling as variable-time, may provide little/no benefit overall as alternative pure-Rust implementations may lose any efficiency gains compared to the existing adc/sbb functions. I would be open to experimenting with a fork of crypto-bigint which does offer such functions, but before I did so, I wanted to ask if this would be outright rejected or if it had sufficient benefit, would be considered.
Contributor guide
No contributing guide indexed for this repository
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.
Research direction
Start by reviewing the linked discussion and Godbolt experiment, then benchmark the existing adc/sbb operations against overflowing_add/overflowing_sub in representative Uint additions. Confirm whether the proposed API provides a meaningful benefit while preserving the required constant-time properties; done means the trade-offs and implementation scope are established.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- cryptography, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100