Feature request: scatter/gather implementation for plain ed25519 signatures

[enrikb]

In constrained memory systems, it can be very handy to ed25519 sign messages that are readily available and complete, however not available in one contiguous memory. With the current sign() signature, such messages need to be copied into contiguous memory.
An example for this situation is my solokey eddsa support POC solokeys/solo1#478.
For illustration, I added a sign2() function in https://github.com/enrikb/salty/tree/feature/scatter-gather-message (just copy and paste of the regular sign()).
Of course, this can also be done for verify(), and also more sophisticated versions like working on a vector of message fragments are possible, following the POSIX readv()/writev() pattern (but maybe not needed that much?).
What do you think about such an API enhancement?

[nickray]

How often do you really have messages in embedded systems that are long enough to make this a necessity? (This is me speaking from the point of view of 320KB of RAM on the LPC55, and signing messages that are short. I tend to think the Cortex-M4 requirement excludes very small RAM MCUs, but likely I'm wrong hehe).

I have a preference for keeping the API surface simple, but if the use case is valid we can try and do something about it for sure! In which case spontaneously I think we might want to go all the way and have sign et al. accept a kind of "resettable iterator" (or "clonable iterator") over bytes (a standard iterator won't work since we need it twice). It would be great if we could avoid non-standard traits, but we could also define the trait in salty and implement it for byte arrays etc. Or possibly confer with the RustCrypto guys to get a shared definition. Of course in the C-API it won't look as nice :)

What do you think?

[nickray]

I played around with this a bit (https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=ae7a21ba8cc33631c981872f92408947), and I think at this point I'd favor something like:

fn sign_non_contiguous(message: &[&[u8]]) -> Signature

The hope with this IntoIterator stuff was to find a trait bound that lets the user pass in either a slice or a slice of slices, thereby avoiding duplicating the API surface (sign + sign_non_contiguous, verify + verify_non_contiguous, etc.). But either my type fu isn't strong enough or it's not possible. E.g., &T does not implement IntoIter<Item=&T> (which it "could", considering &T as an array of one &T element, but maybe this is a trait coherence issue).

But the case for the necessity of this API increase still needs to be made by you :)

[nickray]

Another attempt: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0acfb27e1ca7a1d81994ebc603bf5e88

I'm not happy with having to use .as_ref() on references to byte arrays of known length. I think with const generics we could implement the trait for all [u8; N] (but we don't have them yet), or maybe there's some way to as for AsRef<SliceOrSliceOfSlices>, but I haven't managed.

Maybe the pragmatic choice is to add the _non_contiguous methods separately :)

[enrikb]

But the case for the necessity of this API increase still needs to be made by you :)

I have to admit that my wish was maybe driven by an attempt to over optimize. I don't know how tight (stack) memory e.g. on the solokey actually is, just saw one or two comments like 'let's do it like this to save on stack memory'. And being used to the usual init/update/finalize pattern of hashing functions, I thought it might be useful to have something at least close to it for ed25519 signatures, if the non-contiguous message parts can be accessed twice during the signature generation.

I am quite new to Rust, so I had expected that a general/generic solution for multi part messages like you describe above might come at virtually no cost. However, if it makes the common case much 'uglier' like needing all the as_ref()'s, users won't like it and that's not a good option.

[nickray]

I'll leave this open for sure. If I understand correctly, "baby const generics" (rust-lang/lang-team#37) might be released soon, and should make a nice shared API possible.

[nickray]

Looking at https://doc.rust-lang.org/std/io/trait.Write.html#method.write_vectored, maybe such a method could be called sign_vectored.

[enrikb]

Sounds like a good match.

[nickray]

Another option: https://docs.rs/iterate/1.0.0/iterate/macro.iterate.html