Module ed25519_zebra::batch

Performs batch Ed25519 signature verification.

Batch verification asks whether all signatures in some set are valid, rather than asking whether each of them is valid. This allows sharing computations among all signature verifications, performing less work overall at the cost of higher latency (the entire batch must complete), complexity of caller code (which must assemble a batch of signatures across work-items), and loss of the ability to easily pinpoint failing signatures.

In addition to these general tradeoffs, design flaws in Ed25519 specifically mean that batched verification may not agree with individual verification. Some signature may verify as part of a batch but not on its own. In particular, this batching implementation does not perform the same verification checks as the standalone implementation in this crate. It should therefore not be used in consensus-critical applications.

This batch verification implementation is adaptive in the sense that it detects multiple signatures created with the same verification key and automatically coalesces terms in the final verification equation. In the limiting case where all signatures in the batch are made with the same verification key, coalesced batch verification runs twice as fast as ordinary batch verification.

This optimization doesn't help much with Zcash, where public keys are random, but could be useful in proof-of-stake systems where signatures come from a set of validators (except for the consensus behavior described above, which will be addressed in a future version of this library).

Example

let mut batch = batch::Verifier::new();
for _ in 0..32 {
    let sk = SigningKey::new(rand::thread_rng());
    let vk_bytes = VerificationKeyBytes::from(&sk);
    let msg = b"BatchVerifyTest";
    let sig = sk.sign(&msg[..]);
    batch.queue((vk_bytes, sig, &msg[..]));
}
assert!(batch.verify(rand::thread_rng()).is_ok());

Structs

Item	A batch verification item.
Verifier	A batch verification context.