RustCrypto / RustCrypto/crypto-bigint

Performance of `overflowing_add`/`overflowing_sub` in comparison to `adc`/`sbb`

Open
#871 3 comments 0 reactions 0 assignees View on GitHub

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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.