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 signatures may verify as part of a batch but not on their own. This problem is fixed by ZIP215, a precise specification for edge cases in Ed25519 signature validation that ensures that batch verification agrees with individual verification in all cases.

This crate implements ZIP215, so batch verification always agrees with individual verification, but this is not guaranteed by other implementations. Be extremely careful when using Ed25519 in a consensus-critical context like a blockchain.

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 (provided that system uses the ZIP215 rules).

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.