Implement batch verification

[dconnolly]

https://zips.z.cash/protocol/protocol.pdf#reddsabatchverify

[hdevalence]

The batch verification API should have an IUF-style API like the one I designed for ed25519-zebra, documented here. The Verifier struct is initialized, updated with Items, and then finalized (computing the verification result).

The Item type is important to make the API more ergonomic in async contexts, because it allows the batch processing to be decoupled from the lifetimes of the messages to be verified. To do this, it separates the computation of the challenge scalar (k in Ed25519, and the c <- H^star(R_j || vk_j || M_j) in the description above) from the rest of the batch computations, and performs it when the Item is created rather than in the final batch computation. Otherwise, the verifier would need to either copy all messages into an internal buffer, or express a complex lifetime bound, requiring callers to prove that all messages outlive the batch verifier. The latter would be extremely difficult in an async context.

The type signature for the From impl and the type signature of Verifier::queue are chosen so that the caller can just write verifier.queue((vk, sig, msg).into()) and have everything just work without having to worry too much about these details. Implementing this for Redjubjub will require slightly rearranging the steps as described in the screenshot above.

To actually perform the verification, we need to compute a multiscalar multiplication. The jubjub crate should provide this functionality, but it doesn't, so we should add it to a local fork and upstream those changes. Probably the best algorithm to use would be Straus', as documented in this part of curve25519-dalek. That documentation describes the general technique as well as the specific implementation for constant-time multiscalar multiplication, but we don't want a constant-time implementation. The variable-time implementation is similar but slightly different. The implementation we should add to jubjub will in turn be slightly different, because it should reuse the lookup table types available in that crate.

In the meantime, I think it makes sense to write a stub multiscalar multiplication function in the redjubjub crate of the form

// exact types tbd
fn multiscalar_mul(scalars: impl Iterator<Item=Scalar>, points: impl Iterator<Item=Point>) -> Point {
    // perform N individual scalar*point operations and add the results
}

and use that to implement the batch verification, later replacing it with a call to an optimized implementation in jubjub.

The synchronous API exposed by this crate should have an async interface in Zebra, not in this crate, as described here: ZcashFoundation/zebra#460 (comment)

[hdevalence]

In summary, there should be:

mod batch {
    pub struct Item { /* ... */ }
    impl<'msg, M: AsRef<[u8]>> From<(PublicKeyBytes, Signature, &'msg M)> for Item { /* ... */ }

    pub struct Verifier { /* ... */ }
    impl Verifier {
        pub fn new() { /* ... */ }
        pub fn queue(item: Item) { /* ... */ }
        pub fn verify<R: RngCore + CryptoRng>(self, rng: R) -> Result<(), Error> {
            // use stub multiscalar function to do batch
        }
    }
}

[dconnolly]

Pertains to ZcashFoundation/zebra#407

[dconnolly]

Daira indicates that the reddsa batch optimization formula in section B.1 of the spec is missing a sign, which would bring it in line with the single signature verification formula:

[dconnolly]

Updated formula from Daira, split out a bit too:

[hdevalence]

Per #36 (comment), the design sketch above is suboptimal, and instead, the batch::Verifier should take any kind of signature.