RFC: New facility for exposing "bundled signatures".

[nmathewson]

Sometimes it's useful to save up one or more signatures and have them verified later on. For example, in Arti, we sometimes want to parse a large document containing many internal signatures, but save the verification of the signatures for another thread. We can't use precomputed hashes for this, since the protocol is already specified. Thus, our only choice for now is to carry around the original message--either by copy or by reference--until we're ready to verify the signature on it.

With this patch, ed25519-dalek exposes a new type, BundledSignature. A BundledSignature contains the public key, the InternalSignature, and the scalar k needed to verify the signature against the message. To avoid code bloat and to reuse testing, it uses these objects internally to implement signature verification. (According to cargo bench, there is no performance loss.)

**

Please don't merge this yet. I'm marking this as a "RFC" branch for a few reasons:

First, it seems that my editor setup accidentally ran "cargo fmt" on a few of your files, and I assume you don't want that.

Second, I bet that you'll have comments on the naming and documentation, and I'd like to be responsive to those.

Third, once you think that the basic approach is reasonable, I'd like to add support for batch verification over BundledSignatures.

**

No hurry on the review here, BTW: I'm writing this for fun while I'm on vacation, and I hope you won't look at it until you also feel like it would be fun to look at some code.

[nmathewson]

(There seems to be an unrelated CI failure related to MSRV violations elsewhere in the codebase)

[rozbb]

Thank you for the PR! Some questions:

1. In your usecase, how big are the signed chunks?
2. How many of these chunks are there in a single document?
3. Why is it that you can't use prehashed ed25519?

The reason I ask is because it might not be worth the complication this adds if the use case is small. (/cc @isislovecruft would also like to hear your opinion on this; also see analysis and suggested edits below)

I did some preliminary benchmarks and it seems there are situations in which the improvement is noticeable.

For the reader: recall that verification involves two steps: hashing, then elliptic curve ops. On my machine (CPU from 2016), the latter is a length-independent cost of 40us. At 30KiB per msg, the hashing step of verification is 42us, i.e., 51% of total verification time. At 70KiB per message, hashing is 75% of total verification time. As the message size grows, the hashing time grows proportionally: at 1MiB, bundling is 97% of total verification time, which makes this optimization useless.

So in the specific scenario that someone is parsing a large document with the signed chunks too big or numerous to be heap-allocated (otherwise, you just pass an Arc<Vec<u8>> with the signature to another thread; if messages are > 30KiB, this would process them in realtime, no queueing necessary), and the signed chunks small enough that hashing isn't taking up the overwhelming majority of the processing time, then this optimization makes sense.

Three edits I'd make:

1. Rename BundledSignature. This sounds too close to batching. It's more like a PreprocessedSignature, but I'm not set on that name either.
2. Put access to PreprocessedSignature behind a feature gate. This is a confusing feature and probably shouldn't be exposed to 99% of people.
3. Add benchmarks for PublicKey::prepare_bundled_signature(), BundledSignature::verify(), and their strict variants. These would only be meaningful, however, if we varied the message length in our benchmarks rather than using empty messages. I can make these changes myself, though.