crypto-bigint impl_modulus! is unusable for bigints starting from U3072

Description

When using the impl_modulus! macro with U3072 and bigger types, the R2 constant computation takes several seconds. The Rust compilers version >= 1.73 with an error. In some cases (not for the example below, probably depends on how the constants are used, see here) compiler v1.76 panics.

Ways to reproduce

The example below fails to compile with 1.73.

use crypto_bigint::{impl_modulus, modular::ConstMontyParams, U3072};


impl_modulus!(
    StandardModulusP,
    U3072,
"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFB17217F7D1CF79ABC9E3B39803F2F6AF40F343267298B62D8A0D175B8BAAFA2BE7B876206DEBAC98559552FB4AFA1B10ED2EAE35C138214427573B291169B8253E96CA16224AE8C51ACBDA11317C387EB9EA9BC3B136603B256FA0EC7657F74B72CE87B19D6548CAF5DFA6BD38303248655FA1872F20E3A2DA2D97C50F3FD5C607F4CA11FB5BFB90610D30F88FE551A2EE569D6DFC1EFA157D2E23DE1400B39617460775DB8990E5C943E732B479CD33CCCC4E659393514C4C1A1E0BD1D6095D25669B333564A3376A9C7F8A5E148E82074DB6015CFE7AA30C480A5417350D2C955D5179B1E17B9DAE313CDB6C606CB1078F735D1B2DB31B5F50B5185064C18B4D162DB3B365853D7598A1951AE273EE5570B6C68F96983496D4E6D330AF889B44A02554731CDC8EA17293D1228A4EF98D6F5177FBCF0755268A5C1F9538B98261AFFD446B1CA3CF5E9222B88C66D3C5422183EDC99421090BBB16FAF3D949FF"
);

fn main() {
    println!("R2: {:?}", StandardModulusP::R2)
}

Console output

error: constant evaluation is taking a long time
  --> /home/danil/.cargo/registry/src/index.crates.io-6f17d22bba15001f/crypto-bigint-0.6.0-pre.12/src/uint/shr.rs:70:9
   |
70 | /         while i < LIMBS - shift_num {
71 | |             limbs[i] = self.limbs[i + shift_num];
72 | |             i += 1;
73 | |         }
   | |_________^
   |
   = note: this lint makes sure the compiler doesn't get stuck due to infinite loops in const eval.
           If your compilation actually takes a long time, you can safely allow the lint.
help: the constant being evaluated
  --> src/main.rs:4:1
   |
4  | / impl_modulus!(
5  | |     StandardModulusP,
6  | |     U3072,
7  | | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFB17217F7D1CF79ABC9E3B39803F2F6AF40F343267298B62D8A0D175B8BAAFA2BE7B876206DEBAC98559552FB4AFA1B10ED2EAE35C138214427573B291169B8253E96CA16224AE8C51ACBDA11317C387EB9EA9BC3B136603B256FA0EC7657F74B72CE87B19D6548CAF5DFA6BD38303248655FA1872F20E...
8  | | );
   | |_^
   = note: `#[deny(long_running_const_eval)]` on by default
   = note: this error originates in the macro `impl_modulus` (in Nightly builds, run with -Z macro-backtrace for more info)

note: erroneous constant used
  --> src/main.rs:45:26
   |
45 |     println!("R2: {:?}", StandardModulusP::R2)
   |                          ^^^^^^^^^^^^^^^^^^^^

note: erroneous constant used
  --> src/main.rs:45:26
   |
45 |     println!("R2: {:?}", StandardModulusP::R2)
   |                          ^^^^^^^^^^^^^^^^^^^^
   |
   = note: this note originates in the macro `$crate::format_args_nl` which comes from the expansion of the macro `println` (in Nightly builds, run with -Z macro-backtrace for more info)

error: could not compile `crypto-bigint-example` (bin "crypto-bigint-example") due to previous error
danil@danil-ThinkPad:~/Projects/exercises/rust/crypto-bigint-example$ cargo run
   Compiling crypto-bigint-example v0.1.0 (/home/danil/Projects/exercises/rust/crypto-bigint-example)
error: constant evaluation is taking a long time
  --> .../.cargo/registry/src/index.crates.io-6f17d22bba15001f/crypto-bigint-0.6.0-pre.12/src/uint/shr.rs:70:9
   |
70 | /         while i < LIMBS - shift_num {
71 | |             limbs[i] = self.limbs[i + shift_num];
72 | |             i += 1;
73 | |         }
   | |_________^
   |
   = note: this lint makes sure the compiler doesn't get stuck due to infinite loops in const eval.
           If your compilation actually takes a long time, you can safely allow the lint.
help: the constant being evaluated
  --> src/main.rs:4:1
   |
4  | / impl_modulus!(
5  | |     StandardModulusP,
6  | |     U3072,
7  | | "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFB17217F7D1CF79ABC9E3B39803F2F6AF40F343267298B62D8A0D175B8BAAFA2BE7B876206DEBAC98559552FB4AFA1B10ED2EAE35C138214427573B291169B8253E96CA16224AE8C51ACBDA11317C387EB9EA9BC3B136603B256FA0EC7657F74B72CE87B19D6548CAF5DFA6BD38303248655FA1872F20E...
8  | | );
   | |_^
   = note: `#[deny(long_running_const_eval)]` on by default
   = note: this error originates in the macro `impl_modulus` (in Nightly builds, run with -Z macro-backtrace for more info)

note: erroneous constant used
  --> src/main.rs:11:26
   |
11 |     println!("R2: {:?}", StandardModulusP::R2)
   |                          ^^^^^^^^^^^^^^^^^^^^

note: erroneous constant used
  --> src/main.rs:11:26
   |
11 |     println!("R2: {:?}", StandardModulusP::R2)
   |                          ^^^^^^^^^^^^^^^^^^^^
   |
   = note: this note originates in the macro `$crate::format_args_nl` which comes from the expansion of the macro `println` (in Nightly builds, run with -Z macro-backtrace for more info)

error: could not compile `crypto-bigint-example` (bin "crypto-bigint-example") due to previous error

Using the Rust compiler v1.76

Misc

It is possible to create StandardModulusP and the corresponding implementation by hand (or copy-paste the expanded macro) and allow long_running_const_eval:

    #[allow(long_running_const_eval)]
    const R2: U4096 =
        crypto_bigint::Uint::rem_wide_vartime(Self::ONE.square_wide(), Self::MODULUS.as_nz_ref());

In this case, computing the constant in compile time takes ~7s on ThinkPad X1.

Feb 28 '24 15:02 annenkov

There's not a whole lot we can do here. The core problem is Miri performance. You can allow(long_running_const_eval), but the compile times seem perhaps prohibitively slow.

In such cases where computing the Montgomery parameters at compile time is too slow given current Miri limitations, you may need to take the path of just precomputing them, i.e. copy-paste the expanded macro as you suggested.

Feb 28 '24 15:02 tarcieri

Just curious, AWS has their (formally verified) s2n bignum assembly library. https://github.com/awslabs/s2n-bignum

It looks like there may be rust bindings for it. Would that solve any of these issues?

Mar 11 '24 11:03 spitters

@spitters it won't help here, since this question is about const fn usage, and s2n-bignum is a C/ASM library which isn't callable from const fn contexts

Mar 11 '24 11:03 tarcieri

@spitters note, however, that we do have a general tracking issue for incorporating the assembly from s2n-bignum: #572

Mar 11 '24 20:03 tarcieri

From @protz:

HACL* extracted as pure safe Rust (dubbed "HACL-rs") lives here: https://github.com/hacl-star/hacl-star/tree/afromher_rs/dist/rs

In there, you'll find bignums in src/hacl:

bignum.rs, bignum64.rs: variable-length, 32 and 64-bit versions (scattered across these two files, this needs to be done better)
bignum{4096,256}.rs: fixed-length, 32-bit limbs
bignum{4096,256}_64.rs: fixed-length, 64-bit limbs

Since HACL-rs still preliminary, but the C code is documented properly, e.g. https://github.com/hacl-star/hacl-star/blob/afromher_rs/dist/gcc-compatible/Hacl_Bignum64.h.

For performance one should make sure to use "release mode".

Mar 23 '24 17:03 spitters

FWIW this performs much better on recent versions since rem_wide_vartime was optimized. I tested the code above with U4096 and cargo build --release after cargo clean completed in 4.6 seconds (Rust 1.81 on a 2021 Macbook Pro).

Oct 02 '24 19:10 andrewwhitehead