The current state of compile-time evaluations in rust

✍️ Written on 2021-06-15 in 2555 words.
Part of cs software-development programming-languages rustlang

Motivation

In PQC schemes, you define the parameter set and then the corresponding cryptographic scheme depends upon these values. This is specified in the 2016 call for proposals:

For algorithms that have tunable parameters (such as the dimension of some underlying vector space, or the number of equations and variables), the submission document shall specify concrete values for these parameters. If possible, the submission should specify several parameter sets that allow the selection of a range of possible security/performance tradeoffs

— NIST PQC Call for proposals

Obviously in C, these values are compile time constants declared in preprocessor directives (e.g. in CRYSTALS-Kyber). Based upon these values, arrays are declared and pointer arithmetic within arrays is applied.

But what is the rust equivalent?

Rust concepts

Constant values

fn main() {
    const POWERS: [u8; 6] = [0, 1, 2, 4, 8, 16];
    println!("{}", POWERS[1]);
}
  • Constants can be declared with the const keyword.

  • Usually you want to declare constants in the module namespace (i.e. outside main). They will be immutable unlike static values.

  • Of course, this features constant propagation meaning that expressions like 2 * 3 are evaluated at compile time and only the resulting value will be assigned.

Constant collections

  • Allocations on the heap are not allowed to create a constant value. Be aware that Vec, Box, … are always allocated on the heap. Thus for example, a vector Vec cannot be declared const.

  • If you can mutate a collection, it is obviously not constant.

  • But is the distinction between mutable and immutale not given by the mut keyword? It is. To the best of by knowledge, any constant collection is immutable. But is every immutable collection constant? I think there might be compiler constraints making this statement false.

  • So we need an immutable data structure without allocations. The simplest type is an array. An array can be made const.

  • Regarding pointers in unsafe rust, you need to be aware that *const T is covariant whereas *mut T is invariant.

const POWERS: [u8; 5] = [1, 2, 4, 8, 16];

fn main() {
    println!("{}", POWERS[1]);
}

Compile-time arrays

An array has several values which can be constant.

const HEAD: usize = 2;
const TAIL: usize = 3;
const SIZE: usize = HEAD + TAIL;
const POWERS: [u8; SIZE] = [1, 2, 4, 8, 16];

fn main() {
    println!("{}", POWERS[1]);
}

Compile-time generically sized arrays

Computations at compile-time

User-configured compile-time constants

How can you specify constants to be set to a user provided value at compilation time?

  • For boolean values:

    • Attributes allow to define known flags, which enable conditional compilation for standardized values.

      • e.g. if I add #[cfg(target_os = "linux")] to the main function, it will compile only if the target OS is some Linux OS (→ cfg attribute).

      • You can also assign it to some variable: let os: bool = cfg!(target_os = "linux"); (→ cfg! macro)

      • You can also make it const: const OS: bool = cfg!(target_os = "linux");

      • You seem to be able to attach cfg attributes to {} blocks, which means it can be applied essentially to any instruction. They also work for mod{} and fn() {}.

    • Features allow to define flags, which could e.g. turn on/off functionality of your program.

      • e.g. I could specify …

        [features]
        default = ["hrss", "hps"]
        hrss = []
        hps = []

        … in Cargo.toml. Then #[cfg(feature = "hrss")] evaluates to true.

      • Since you specify features explicitly (also when used as a dependency), the library contains the features you enabled.

  • For non-bool values:

    • Can I fetch values of configuration attributes before coercion into booleans?

      • std::env::consts provides some constants as &str: const env_os: &str = std::env::consts::OS;

      • No, they all have standardized values and cannot be overwritten.

    • Can I turn environment variables into const values?

      • std::env refers to the process environment which contains obviously runtime constants and thus cannot be made const.

      • Environment variables lists standardized compile time environment variables.

      • env! refers to a macro evaluated at compilation time. It allows you to fetch any environment variable like PATH when compiling the program.

      • Due to the const fn restrictions above, parsing the environment variable into a const of your desired type, might not be possible. Calls in constant functions are limited to constant functions, tuple structs and tuple variants.

  • Build scripts is a universal answer. Placing a file named build.rs in the root of a package will cause Cargo to compile that script and execute it just before building the package.

    • You can parse the values and panic in case of problems. There is no need for const declarations.

    • I am not aware of any approach to propagate values from an executable to the library subject to dependency.

    • stdout is parsed in a special way by rust:

      • If you emit cargo:rustc-cfg=NTRU_N_IS_509="true", then cfg!(NTRU_N_IS_509) will be true. Thus, you can parse values arbitrarily to finally emit a bunch of boolean const values.

      • On the other hand, cargo:rustc-env=VAR=VALUE passes an arbitrary string VALUE which can be picked up with the env! macro.

    • Example:

fn to_int(n: &str) -> usize {
    n.parse::<usize>().unwrap()
}

fn main() {
    const ENV_NTRU_N: &'static str = env!("NTRU_N", "NTRU_N must be provided");

    let ntru_n: usize = to_int(ENV_NTRU_N);
    if ntru_n != 509 && ntru_n != 677 && ntru_n != 821 && ntru_n != 701 {
        panic!("Only NTRU_N values of recommended parameter sets are supported");
    }
}

Conclusion

History and opinion

  • We restricted our discussion to compilation time evaluation. So the goal is to get a const value in the rust code.

  • Here const-generic and const-fn come in handy. They are young features with limitations.

  • Before these features, rust was much less powerful than C. I had to duplicate an entire file for my NewHope implementation and edit array sizes manually.

  • I think templates and constexpr in C++ are a mess. I always hoped for a file which evaluates a compile time and evaluates all compile time values. Then these values can be used at run time as constants. rust’s build scripts come really close to this concept.

Decision process

  • If you are happy with boolean values, you can use attributes (allowlisted keys) and features (arbitrary keys). They have a nice feature set.

  • If you want to pass arbitrary strings, you can use environment variables (fetch values with env!) (const fn is only useful for simple computations) or build scripts (arbitrary computation).

  • But if you need other types or need pre-processing, then you can write rust files into the package dynamically with build scripts. This is an error-prone approach.

Specifically for PQC, we need to use some value specifying the number of dimensions as const value. We use the const value to specify the size of arrays across the entire program. My recommendation:

  1. If the power of const fn improved (e.g. for loops are possible), const generics are more powerful (e.g. multiple generics define the array size), or [env is available in your compiler version], don’t follow this advice. This approach is purposefully conservative.

  2. Otherwise consider the set of names for recommended parameter sets.

  3. List all NAMEs in a build script and check whether cfg!(feature = "use_NAME") is set

  4. Emit exactly one parameter set with cargo:rustc-cfg=NAME or throw a panic

  5. In src/params.rs, define a const fn params which returns one parameter set. Only one return value { Params {…} } is actually returned because all are gated with #[cfg(NAME)].

  6. We assign the parameter set as const PARAMS: Params = params() and thus have the parameters as constants available.

I hope this approach will soon be deprecated and the parameter set will be represented as const generic values only.