Use const generics instead of generic-array

[roblabla]

A minimal version of const generics have been stabilized in Rust 1.51, back in March. Thanks to this, we can now get rid of the dependency on generic-array and move to using a simpler [u8; N] type with const generics. This should give us several benefits, such as unblocking #87.

The downside is that it requires bumping the MSRV (currently at 1.41, I believe) up to 1.51. It may be a bit too early for this bump to take place.

Is there any plans for an eventual migrations to const generics?

[tarcieri]

We definitely have const generics on our radar. See the crypto-bigint crate for the main place we're presently using them.

That said, min_const_generics aren't powerful enough to express the traits from digest.

Notably Digest has an associated OutputSize constant/type, however it's not yet possible to use an associated constant of a trait as a const generic parameter:

pub trait Digest {
    const OUTPUT_SIZE: usize;
}

pub struct Output<D: Digest> {
    bytes: [u8; D::OUTPUT_SIZE]
}

This has the following compile error today:

error: generic parameters may not be used in const operations
 --> src/lib.rs:6:17
  |
6 |     bytes: [u8; D::OUTPUT_SIZE]
  |                 ^^^^^^^^^^^^^^ cannot perform const operation using `D`
  |
  = note: type parameters may not be used in const expressions

In order to express traits like Digest, we need full const_generics to be stabilized (and potentially const_evaluatable_checked as well)

[newpavlov]

FYI relevant rust issues are rust-lang/rust#60551 and rust-lang/rust#76560.

[not-an-aardvark]

I had a similar use case recently, and I found a decent workaround on stable Rust for this kind of thing:

pub trait Array<T>: Copy + Clone + AsRef<[T]> + AsMut<[T]> /* + (other slice traits) + private::Sealed */ {}
impl<T: Copy, const N: usize> Array<T> for [T; N] {}

pub trait Digest {
    type Output: Array<u8>;
    const OutputSize: usize = std::mem::size_of::<Self::Output>(); // (Optional, for backwards-compatibility)
}

pub struct Output<D: Digest> {
    bytes: D::Output
}

// ...

impl Digest for Sha256 {
    type Output = [u8; 32];
}

The difference between this approach and the current GenericArray approach is that Array here is a trait which is satisfied by "real" arrays, rather than being a struct. As a result, anyone who consumes a specific impl of Digest (e.g. a user of a hash function library) is only exposed to primitive arrays.

The disadvantage is that anything that consumes a Digest in a generic manner (i.e. with a <D: Digest> bound) needs to work with a Array<u8> trait bound rather than an actual [u8; N] parameter. This is mildly annoying because Array<u8> doesn't have the same auto-coercion behavior as real arrays. However, I found that this could generally be resolved with a one-line change around the use sites.

[tarcieri]

@not-an-aardvark there are other traits where something like that might suffice, but that doesn't cover our existing use cases for digest, and we're close enough to const generics landing that it doesn't really make sense to explore options like that.

We use sizes as bounds and also to compute other properties/sizes using the type system. Consider something like the DigestSigner impl from the ecdsa crate:

https://docs.rs/ecdsa/0.12.4/ecdsa/struct.SigningKey.html#impl-DigestSigner%3CD%2C%20Signature%3CC%3E%3E

It has this bound:

D: FixedOutput<OutputSize = FieldSize<C>>

In that case, we need to know that the output size of a digest is the same size as the base field of an elliptic curve, as verified by the type system.

That one may seem simple enough, but there's also the use case of a wide reduction to a scalar:

RustCrypto/elliptic-curves#432

...where the input is twice the width of the elliptic curve's modulus which can be used for a hash-to-scalar use case. So we also need to compute properties using the type system (in this example, multiply-by-2), then use those in trait bounds which say that the output of a particular digest is equal to twice the width of a given elliptic curve's scalar field.

[randomairborne]

is there an easy way to convert this into a [u8;32] here?

[tarcieri]

@randomairborne you can use From/Into to convert between core arrays and GenericArray:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=c99c29363edd4c216c6c9bae804b1505

[tarcieri]

There's an overall tracking issue for a const generics migration here: RustCrypto/traits#970

Please follow up there if you have any questions/concerns