Separating backends into their own crates?

[isislovecruft]

As we continue to add backends, it would be handy to have a more modular way to choose which backend is being used and to use a custom backend (e.g. for developers working on hardware that hasn't been publicly released yet) which we might not want to (or be able to) maintain within our crate.

Would it be feasible to create some sort of "backend trait" which describes what methods we expect out of the field arithmetic? And on that note, would it be possible to also separate out the scalar arithmetic so that someone could develop a chip-specific field implementation but reuse the 64-bit serial scalars?

I'm imagining providing a trait that's something like:

#![feature(trait_alias)]                                                                                                                                                                                                          
                                                                                                                                                                                                                                  
use core::ops::{Add, AddAssign, Sub, SubAssign};                                                                                                                                                                                  
                                                                                                                                                                                                                                  
pub trait FieldArithmetic = Sized + Add + AddAssign + Sub + SubAssign; // ...                                                                                                                                                     
                                                                                                                                                                                                                                  
pub trait FieldElement {                                                                                                                                                                                                          
    fn zero() -> Self;                                                                                                                                                                                                            
    fn one() -> Self;                                                                                                                                                                                                             
    fn from_u64(x: u64) -> Self;                                                                                                                                                                                                  
    // ...                                                                                                                                                                                                                        
}                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                  
pub trait FieldBackend = FieldArithmetic + FieldElement;                                                                                                                                                                          
                                                                                                                                                                                                                                  
pub trait ScalarArithmetic = Sized + Add + AddAssign + Sub + SubAssign; // ...                                                                                                                                                    
                                                                                                                                                                                                                                  
pub trait ModularScalar {                                                                                                                                                                                                         
    fn zero() -> Self;                                                                                                                                                                                                            
    fn one() -> Self;                                                                                                                                                                                                             
    fn from_u64(x: u64) -> Self;                                                                                                                                                                                                  
    // ...                                                                                                                                                                                                                        
}                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                  
pub trait ScalarBackend = ScalarArithmetic + ModularScalar;                                                                                                                                                                       
                                                                                                                                                                                                                                  
pub trait Backend = FieldBackend + ScalarBackend;                      

Unfortunately that requires the experimental trait aliases feature. I'm not sure if there's a better way to do it?

Thoughts? Opinions?

[WildCryptoFox]

Trait aliases only support auto-traits after the + so far (or the last time I checked). Are you sure you need trait aliases?

trait A = B + C;

trait A: B + C {}
impl<Q: B + C> A for Q {}

[hdevalence]

Unfortunately, I think that this is mostly infeasible, and to the extent that it is, it would not provide a benefit over the existing implementation.

First, it is already possible for curve25519-dalek backends to exist in external crates -- the simd_backend already pulls an optional packed_simd dependency, and there's no reason that a curve25519-dalek backend feature couldn't pull a dependency that provided an entire backend. And it is already possible to have a chip-specific field implementation but reuse the 64-bit Scalar implementation, as this is exactly what the current simd_backend does already for the AVX2 and IFMA backends.

Second, Cargo does not allow cyclic dependencies, so if a backend is to exist in a separate external-backend crate, either external-backend can use traits from curve25519-dalek or curve25519-dalek can use the code in external-backend, but not both. And in any case, using external-backend from curve25519-dalek requires (transitively) supporting it in our crate, so this does not solve the problem of not wanting to maintain the backend named in the issue: non-upstreamed changes to curve25519-dalek are required anyways.

Third, encapsulating common field arithmetic behaviour into a trait requires a clean abstraction boundary for the trait to encapsulate. But this is not actually how the implementation works, which is why the backend module tree is designed to finely capture the parts that can be common and the parts that must be distinct. For instance, although both the AVX2 and IFMA backends use the same 4-way parallel formulas, and both use vectors of 4 field elements, they place different demands on the coefficient reductions, so they require different implementations of point arithmetic.

Finally, it's not desirable in general to have common behaviour for field arithmetic, because the whole stack of optimal implementation choices from the curve model to the hardware capabilities are interlinked, so it's likely that any particular description of methods required for field arithmetic would be a suboptimal choice for a particular set of capabilities, as is already the case for the simd_backend.

[tarcieri]

One thing that seems particularly annoying with Rust right now is cross-crate inlining, at least without LTO enabled. Even if LTO solves the problem, for someone trying to write performant crypto, LTO optimizations are a particularly complex and annoying thing to reason about.

If you are targeting a performant implementation right now in Rust, it's a pretty big headache to have the relevant performance-oriented code spread across multiple crates.

[WildCryptoFox]

@hdevalence The trait lets you break the cycle by putting the consumer in control of selecting the backend. I.e. https://docs.rs/criterion-cycles-per-byte depends on https://docs.rs/criterion but a consumer, who uses both, can use Criterion<CyclesPerByte> while most users just use Criterion without recognizing the measurements backend.

With the trait, you can split curve25519-dalek into a -core with the u32/u64 backends and an -avx-backend et al for platform specific backends. Now the curve25519-dalek crate only needs to reexport everything from -core and, if the platform supports it, re-export its specific backend if known and fill in an assumed default backend. Thus, the consumer can still opt to use a specific backend in their code without messing with feature flags. I.e. type MyRistrettoPoint = RistrettoPoint<RiscVVectors>;.

AFAICT this would not be a breaking change, as adding an type parameter with a default is identical to the type without it.

[WildCryptoFox]

@tarcieri The LTO issue might not be an issue due to the implicit inlining behavior with generics.

[burdges]

@james-darkfox Algebra is kinda a graveyard for programming language abstractions even at the best of times, but.. ZCash's curve arithmetic has a trait and crate hierarchy already, which includes some Edwards curves like JubJub. I kinda think their traits and curves provide a better playground for work on back ends under cross crate constraints. Also, zcash's trait hierarchy actually serves an important purpose, not just aesthetics, which reduces the available pitfalls.

[isislovecruft]

Hi, I hate to be annoying, but it's really annoying currently to maintain external backends, and that is only going to get worse over time as we see more backends being produced for more exotic and new instruction sets. I still think having traits to define field/scalar backends, and also having the standard reusable 32-bit and 64-bit scalar backends in a -core crate for ease of reuse, would make it much easier to develop backends externally.

Here's a proposal of tasks that would need to be done to get the ball rolling on this:

• Investigate reusing the zcash trait code, and/or coming up with a common group crate for traits that both dalek and zcash can use. (Optional, but cool and also good for the rust crypto ecosystem. Also, are there any other mature group libraries in Rust that might want to have a say in this? cc/@str4d and @ebfull)
• Create a Scalar trait. (Optional, but also useful since I'd like to someday create 128-bit Scalars to speed up ed25519 batch verification and having a common interface would be nice.)
• Separate the 32-bit and 64-bit scalar implementations into their own curve25519-dalek-core crate.

And do either these things:

• Create a FieldCommon trait to abstract what is common to both the serial backends and the vectorised backends.
• Create a trait VectorisedField: FieldCommon trait to encompass the remainder of the API that can't be in common with serialised code, and export this simply as trait Field when vectorisation is enabled.
• Create a trait SerialisedField: FieldCommon, similar to above.

Or:

• Create a traits for the EdwardsPoint, ExtendedPoint, CachedPoint, etc., interfaces and require that a backend implement those. Probably the best way to do this is by having these traits have associated types to define what implementation of a field element they are using, and then by default we export the usual IsEdwardsPoint<FieldElement51>, etc.

Additionally:

• Investigate whether cross-crate trait implementation requires strict inlining, and what affects this might have on things like LTO and binary size.

Further, a bunch of these tasks are likely suitable for a new person with a bit of mentoring, and I'd be happy to supervise the work to make sure it's acceptable.

[Pratyush]

FWIW we also have Field and Group traits in our algebra crate. Currently we only have a generic 64-bit backend from the old pairing crate, but I'd be interested in collaborating to get a unified interface across crates

[tarcieri]

@Pratyush link is 404

[Pratyush]

fixed