Consider using traits/types from the 'signature' and 'ed25519' crates?

[tarcieri]

NOTE: PR open with these proposed changes here #124

Problem

Crates which use Ed25519 as part of a high-level protocol implementation or abstract signature functionality who want to enable the consumers of their crates to be able to use their choice of Rust Ed25519 libraries wind up writing their own abstractions to do so on a crate-by-crate basis.

Here's an example from the Noise Protocol implementation snow, which does not (yet) use Ed25519 signatures, but I hope still illustrates the point:

Instead of every crate which wants to do this having to wrangle a silly zoo of optional crypto crates dependencies, a better approach would be to define a common set of traits for how to produce (Ed25519) signatures, and encourage algorithm "provider" crates to impl those traits. This makes it easy to, say, use ed25519-dalek as a software signing crate while also supporting the yubihsm crate for hardware-backed Ed25519 signatures.

signature crate

I've been working with @newpavlov via the RustCrypto GH org to create a crate which provides abstract digital signature functionality, which I plan on using to rewrite the internals of Signatory, an existing multi-provider digital signature library.

Where Signatory provides a set of compatible "provider" crates, e.g. signatory-dalek, what I would really love to do as part of a minimalist rewrite is also get crypto library authors to adopt the traits directly into their libraries instead of using "wrapper" crates which impl the relevant traits. And congratulations, you're the first project I'm pinging.

I've just opened a PR to the signature crate which implements the initial set of signing traits:

https://github.com/RustCrypto/signatures/pull/7

(Sidebar: If you see anything you don't like there, please let us know! This is the first major non-boilerplate PR to the crate, so now is a great time to fix anything you don't like about it)

Namely it has traits like these:

pub trait Sign<S: Signature>: Send + Sync {
    fn sign(&self, msg: &[u8]) -> Result<S, Error>;
}

pub trait Verify<S: Signature>: Send + Sync {
    fn verify(&self, msg: &[u8], signature: &S) -> Result<(), Error>;
}

These traits provide equivalent methods to the existing Keypair::sign and PublicKey::verify methods (the only difference being the Sign trait returns a Result for its sign method, in which case it might be worth considering separating sign from try_sign so people who don't care about things like HSM errors don't always need to call unwrap).

Having people import an additional trait is, I will admit, mildly annoying, but I imagine most people are copying/pasting the relevant code, so adding an additional import is not that annoying. You can re-export the relevant traits similar to what you're already doing for Digest.

ed25519 crate

For true interop, crates need to agree on at least an ed25519::Signature type. That said, the ed25519 crate is presently vaporware and these types don't yet exist. Update: it's real, and used in production in a few crates, e.g. yubihsm.

One option, if you are so inclined as authors of what is pretty much the definitive Rust Ed25519 crate, would be to upstream the existing Signature type into the ed25519 crate.

All that said, I'm happy to both make changes to the signature crate as well as put in a PR to ed25519-dalek to switch to using these traits once we publish the initial signature crate. Let me know if you're interested!

[isislovecruft]

hi @tarcieri!

Yes. I've been thinking about abstracting over both signatures and different types and strengths and properties of signatures quite a lot, and I'd be super happy to help contribute towards any and all efforts at generalisation.

It had never occurred to me to return a Result<T, E> due to HSM errors, but this is totally understandable and very helpful API design knowledge, thank you!

The ed25519 crate was offered to me by one of the maintainers (I think a rust-crypto developer?) years ago when I first made ed25519-dalek, but I declined their generous offer, mostly because I was very proud of the in-joke in the dalek naming scheme. Perhaps we could ask them (I'd have to look in my email backlog who specifically it was?) if it would be okay to use the namespace as either a re-export, or as a generalised impl ed25519::Signature for Signer sort of crate? Anyway, I'm open to all these options, and super happy to have more traits and generalisations in the ecosystem.

[newpavlov]

The ed25519 crate was offered to me by one of the maintainers

It was me. :) Yes, I think we can use ed25519 crate as a wrapper around ed25519-dalek to implement signature traits. This way you can move with 1.0 stabilization without tying yourself to stabilization of signature crate.

[tarcieri]

I released v0.1.0 of the signature crate today:

https://docs.rs/signature/0.1.0/signature/

It's probably not terribly helpful in and of itself, but would be if paired with an ed25519 crate which defines an ed25519::Signature type.

[tarcieri]

I opened an issue about an ed25519 crate for those of you who are interested in this: https://github.com/RustCrypto/signatures/issues/22

[tarcieri]

There's now an ed25519 crate containing an ed25519::Signature type which API-wise should be close to a drop-in replacement (aside from serde support) for the Signature type in ed25519-dalek now:

https://github.com/RustCrypto/signatures/blob/master/ed25519/src/lib.rs

The main difference is ed25519-dalek internally represents signatures as an R, s pair, and right now the ed25519 crate uses a bag-of-bytes internal representation.

[tarcieri]

I've opened an issue about doing a 1.0 release of the signature crate here:

https://github.com/RustCrypto/signatures/pull/32

[nickray]

@tarcieri Why does ed25519 specify the internal representation? Is this to avoid causing too much generics for users? Because I think modeling the compressed point/scalar components explicitly is part of the core allure of the API here in the first place.

[tarcieri]

@nickray I really need to write up an architecture document / FAQ to answer these kinds of questions.

So ideally yes, the types here could have a distinction between the internal representation and the serialized form.

Doing that would involve changing the bounds on the signature::Signature type, which I think are very much bikesheddable at this point:

https://docs.rs/signature/1.0.0-pre.1/signature/trait.Signature.html

The core one tying it to a serialized representation is AsRef<[u8]>.

Ultimately I think the goal of this sort of trait abstraction is a type which allows users to serialize the data, but also be assured they're getting the correct signature type.

The main alternatives I think could be explored are a marker trait (e.g. ed25519::Signature: From<[u8; 64]> + Into<[u8; 64]>), or trying to unify that same idea in signature::Signature using generic-array.

The main cons of this approach: it means end users don't have a single signature type to deal with, representing the bag-of-bytes serialized form. Having also implemented an ecdsa crate in all its split ASN.1 vs "fixed"/"raw" signature glory I think one of the best things about Ed25519 as a signature algorithm is operating in what is largely a bag-of-bytes interface which is free of the complexity of different representations for the same thing.

[nickray]

Yeah, well I the "bag of bytes" representation already has its (canonical) type, namely [u8; 64]. It's indeed the beauty of the Ed25519 "API" that the inputs and outputs are exactly that. I don't see why a library user would need to know the specific type of a signature. (What I do see is that too many type annotations are bad for your mental health...)

But it's just the representation, and the job of the Signature trait should be very precisely specifying the conversions (signatures <--> bags), and, explicitly, in the appropriate non-secret revealing granularity, what can go wrong. I mean, this is exactly where Ed25519 itself becomes not so pretty, because it pretends too much that bytes are the actual things. But I don't see signature::Error enumerating this (which is independent of the internal representation and implementation), so what exactly is the value add apart from blessing a specific newtype?

To speak in geometric terms, you don't seem to be specifying the object in terms of its properties (intrinsically), you're prescribing a specific coordinate system (extrinsically). Sorry if that analogy is too handwavy, I'm a mathematician not a cryptographer ;)

I'm not sure Rust's type system is strong enough to express that which I'd want though, as From + Into is just an alias, not its own trait, if I'm not mistaken. So suddenly any old From + Into with associated Error type could pass as a signature 😁

That said, if the goal is (for some pragmatic reasons) to enforce the specific type all implementors are to use, I'd still strongly strongly prefer enforcing the current dalek one. Let them eat extension trait cake hehe.

Regards to generic-array, that's not something I'd put in a potential 1.0 release; it's a patch on a wart that hasn't been removed for far too long.

[nickray]

Also apologies if this comes across as over-critical, it's honestly just my hope that Rust can fulfill its promise to expressively yet pragmatically express what we're actually doing, which is making me averse to hacks like generic-array and shortcuts like concrete types.

[tarcieri]

Following in the footsteps of libraries like serde, the signature::Signer relies on generic return types, which IMO is one of Rust's most powerful features (and likewise and signature::Verifier uses a generic argument):

https://docs.rs/signature/1.0.0-pre.1/signature/trait.Signer.html

Generic return types are the grand unifying principle that holds together the signature crate in its present form, much like the same case is for serde.

This doesn't work in a world where...

its (canonical) type, namely [u8; 64]

[u8; 64] or AsRef<[u8; 64]> are not sufficient bounds to establish "this bytestring represents an Ed25519 signature".

Beyond serde, I look to libraries like embedded-hal where the type system is heavily leveraged to prevent errors, and I think that same sort of approach of using explicit types everywhere to prevent mistakes is also very much applicable to cryptography as well.

These sorts of things aren't possible in a world where an Ed25519 signature is [u8; 64].

All that said, I think the #1 most important feature of the ed25519 crate is having a single signature type which is useful across crates where type safety around "this 64-byte octet string is in fact an Ed25519 signature" is desirable.

Also correct me if I'm wrong, but I think the internal representation of the S component of the signature in its current form relies on an internal field representation which is specific to curve25519-dalek?

Having a signature representation all crates can agree upon or, failing that, serialize to, is the only way to have an abstraction.

[nickray]

Yes sure, I did not say signatures should be identified with arrays, quite the opposite. What I don't understand is whether ed25519 actually needs to define a blessed Signature type. I assume you're only going to have one internal implementation at compile-time anyway, which could have whatever actual type. (Much like the dalek/salty signature type itself actually just needs some Scalar type, that the backend is free to implement however it wishes). As long as it presents the interface your trait defines, you can have Vecs of that specific type, or whatever you actually need in your code that depends on Signatures, and not their bag-of-bytes representation.

Do you and if so why do you need a fixed concrete type? Why is it not enough to have concrete array inputs and outputs to a type that itself is constrained only by whatever bounds?

If I'm understanding you correctly, you want "serialize to" a newtype over arrays for type safety, that's perfectly fine. I'm talking about what is serialized from and is the internal representation and/or output of the API when one signs a message.

[tarcieri]

If I understand you correctly, you want a "structural typing" approach, where an Ed25519 signature is [u8; 64].

As an author of libraries that work with multiple types of signatures, I want to prevent type confusion between:

• an Ed25519 signature which serializes to [u8; 64]
• an ECDSA-P256-SHA256 signature which serializes to [u8; 64]
• an ECDSA-SECP256K1-SHA256 signature which serializes to [u8; 64]

I also want to provide a user interface which is simultaneously type safe and user friendly:

let sig: S = signer.sign(msg);

or:

let sig = signer.sign::<S>(msg);

...leveraging Rust's generic return types the same way serde does.

These interfaces rely on the caller communicating the desired signature type to the type system in the form of a concrete return type.

The ultimate idea is trying to tie the following things together in a type-safe way:

• crates which produce or verify Ed25519 signatures
• crates which implement protocols which rely on Ed25519 signatures
• users of both of these crates which are trying to combine them

...and in the course of the whole process, trying to rely on the type system to ensure that the requested composition is actually valid.

If you're interested in continuing to discuss/debate this, I think it'd be great if we could move the discussion to issues on the https://github.com/RustCrypto/signatures repo

[nickray]

Again, I do not want to identify Ed25519 signatures with [u8; 64]. I am protesting that signatures/ed25519 specifies an Ed25519 type instead of an Ed25519 trait. I think it should specify only the trait, and let the implementing crate specify the type.

Will open an issue there to discuss this further.

[tarcieri]

Oh sorry then! I did say this earlier:

https://github.com/dalek-cryptography/ed25519-dalek/issues/80#issuecomment-566799976

The main alternatives I think could be explored are a marker trait (e.g. ed25519::Signature: From<[u8; 64]> + Into<[u8; 64]>), or trying to unify that same idea in signature::Signature using generic-array.

But also noted these cons:

The main cons of this approach: it means end users don't have a single signature type to deal with, representing the bag-of-bytes serialized form. Having also implemented an ecdsa crate in all its split ASN.1 vs "fixed"/"raw" signature glory I think one of the best things about Ed25519 as a signature algorithm is operating in what is largely a bag-of-bytes interface which is free of the complexity of different representations for the same thing.

Failure to agree on a concrete type passes the complexity onto the API consumer, and as I mentioned earlier, it's the sort of complexity the zen of the Ed25519 bag-of-bytes interface avoids. Reintroducing the complexity of variant internal representations, especially for the specific case of Ed25519, at least in my experience seems to be missing the core lessons of Ed25519 versus earlier signature systems, and I say this as one of Ed25519's earliest users.

Personally I see no benefits in passing the complexity of variant internal representations on to signature users. If anything, IMO, they only carry with them the possibility of incompatibilities, and that's exactly the sort of thing I'm trying to avoid with type-safe abstractions.

I'd love to see a pro/con analysis from your perspective, but ideally on https://github.com/RustCrypto/signatures as these sort of discussions seem pretty scattered at this point.

[tarcieri]

Another way of putting this: I am sympathetic to the cause of signatures with variant representations for what is fundamentally the same signature which is serializable in various different representations, and have had to deal with this for ECDSA, but for the specific case of Ed25519 this feels like snatching defeat from the jaws of victory: everything else aside, one of the biggest problems Ed25519 solved from a software engineering perspective is a uniform bag-of-bytes signature representation.

This same representation allows various crates to work with Ed25519 signatures in a type-safe manner, simply, without generic parameters, or additional trait bounds / impl trait.

To me that's a huge win for signature systems in general, hence my reluctance to support anything more complicated, and suspicion it will repeat the mistakes of the past like incompatible internal representations.

[nickray]

I understand what you're saying.

Perhaps a sensible solution, though, is that ed25519-dalek keeps its nice internal Signature type, and additionally offers a compatibility layer to your signature/ed25519 type: From<ed25519::Signature> for dalek::Signature and Into<ed25519::Signature> for dalek::Signature, ditto for references, so you and users of ed25519 can operate on impl Into<ed25519::Signature> and impl From<ed25519::Signature> (assuming this is all more or less zero-cost). So yeah, a bit of generic type cost (similar perhaps to std::fs). I'd be more than willing to do this in salty.

Or vice-versa, RustCrypto itself could implement the opposite transformations for ed25519::Signature on a curated selection of implementation backends. This way around you could also rule out incompatibilities (vs. relying on the superficially "same" Signature type, which cannot do so, as it isn't expressive enough).

At this point I rest my arguments, at least in this issue, as this is not my library to decide over anyway :)

[tarcieri]

...you and users of ed25519 can operate on impl Into and impl From (assuming this is all more or less zero-cost).

It might be helpful to look concretely at how downstream consumers leverage an object safe API to support multiple signing backends.

Here is code which supports a keyring of Ed25519 signers, leveraging object safety to abstract over them:

https://github.com/tendermint/kms/blob/master/src/keyring/ed25519/signer.rs#L22

signer: Arc<Box<dyn signature::Signer<ed25519::Signature> + Send + Sync>>,

(I added the ed25519:: for clarity, it's not disambiguated that way in the original code)

It achieves object safety by using a generic parameter for the signature type.

Could it use a generic value with impl Into<ed25519::Signature> in the return position instead? Maybe, but that's foisting a lot of complexity onto consumers of an API which is effectively "I operate on Ed25519 signatures".

It also means that consumers who want to operate over multiple Ed25519 signature providers don't have a concrete type to use: if they want type safety, they either need to be generic around S: ed25519::Signature or make their own newtype wrappers for every serialized signature.

Or vice-versa, RustCrypto itself could implement the opposite transformations for ed25519::Signature on a curated selection of implementation backends.

That already exists in the form of:

https://github.com/tendermint/signatory

...which is implemented in terms of the signature crate traits and ed25519 crate types for providers which support Ed25519 signatures (as well as ECDSA signatures)

The problem with the "wrapper crate" approach, IMO, is that approach isn't scalable: I'm pretty much at my personal limit of providers I can maintain, and every time one of them does a semver incompatible downstream release, so do I. Other contributors also found the "wrapper crate" method painful.

In the end, I think you're focused too much on a...

nice internal Signature type

...at the cost of how it affects consumers of the API. To them the internal representation of a signature is an implementation detail, which ultimately serializes to the same 64-byte string. Is it really worth foisting the additional complexity of not having a concrete signature type to work with onto API consumers, just so every provider can have their own unique internal representation of a signature?

Whether the relationship between signatures and traits provided by the RustCrypto libraries are an "is a" or "from"/"into" relationship is definitely one of the details I've gone back and forth on with people, and in the end any attempts to move from the former to the latter, IMO, leak complexity onto API consumers, in a scenario which is already a difficult balance between leveraging type system features and trying to keep things simple for consumers of the API.

About the best I can say is if you think you truly have a concrete counterproposal to this approach, please post it at https://github.com/RustCrypto/signatures and I can step you through all the real-world code I have which is already using these types and traits and we can look at how practical it would be and what the real-world impact is.

[tarcieri]

Note: I've published an announcement of an intent to ship signature 1.0 with two-week final comment period ending March 22nd:

https://github.com/RustCrypto/traits/issues/78

[tarcieri]

New PR open for ed25519-dalek with these proposed changes here: https://github.com/dalek-cryptography/ed25519-dalek/pull/124

[isislovecruft]

This should be fixed by the recent merge of #124 (thanks @tarcieri!) which will be available in 1.0.0-pre.4 (which I'm about to release).