Function ed25519_dalek::verify_batch

pub fn verify_batch(
    messages: &[&[u8]], 
    signatures: &[Signature], 
    public_keys: &[PublicKey]
) -> Result<(), SignatureError>

Verify a batch of signatures on messages with their respective public_keys.

Inputs

• messages is a slice of byte slices, one per signed message.
• signatures is a slice of Signatures.
• public_keys is a slice of PublicKeys.

Returns

• A Result whose Ok value is an emtpy tuple and whose Err value is a SignatureError containing a description of the internal error which occured.

Notes on Nonce Generation & Malleability

On Synthetic Nonces

This library defaults to using what is called “synthetic” nonces, which means that a mixture of deterministic (per any unique set of inputs to this function) data and system randomness is used to seed the CSPRNG for nonce generation. For more of the background theory on why many cryptographers currently believe this to be superior to either purely deterministic generation or purely relying on the system’s randomness, see this section of the Merlin design by Henry de Valence, isis lovecruft, and Oleg Andreev, as well as Trevor Perrin’s designs for generalised EdDSA.

On Deterministic Nonces

In order to be ammenable to protocols which require stricter third-party auditability trails, such as in some financial cryptographic settings, this library also supports a --features=batch_deterministic setting, where the nonces for batch signature verification are derived purely from the inputs to this function themselves.

This is not recommended for use unless you have several cryptographers on staff who can advise you in its usage and all the horrible, terrible, awful ways it can go horribly, terribly, awfully wrong.

In any sigma protocol it is wise to include as much context pertaining to the public state in the protocol as possible, to avoid malleability attacks where an adversary alters publics in an algebraic manner that manages to satisfy the equations for the protocol in question.

For ed25519 batch verification (both with synthetic and deterministic nonce generation), we include the following as scalars in the protocol transcript:

• All of the computed H(R||A||M)s to the protocol transcript, and
• All of the s components of each signature.

Each is also prefixed with their index in the vector.

The former, while not quite as elegant as adding the Rs, As, and Ms separately, saves us a bit of context hashing since the H(R||A||M)s need to be computed for the verification equation anyway.

The latter prevents a malleability attack only found in deterministic batch signature verification (i.e. only when compiling ed25519-dalek with --features batch_deterministic) wherein an adversary, without access to the signing key(s), can take any valid signature, (s,R), and swap s with s' = -z1. This doesn’t contitute a signature forgery, merely a vulnerability, as the resulting signature will not pass single signature verification. (Thanks to Github users @real_or_random and @jonasnick for pointing out this malleability issue.)

For an additional way in which signatures can be made to probablistically falsely “pass” the synthethic batch verification equation for the same inputs, but only some crafted inputs will pass the deterministic batch single, and neither of these will ever pass single signature verification, see the documentation for [PublicKey.validate()].

Examples

extern crate ed25519_dalek;
extern crate rand;

use ed25519_dalek::verify_batch;
use ed25519_dalek::Keypair;
use ed25519_dalek::PublicKey;
use ed25519_dalek::Signer;
use ed25519_dalek::Signature;
use rand::rngs::OsRng;

let mut csprng = OsRng{};
let keypairs: Vec<Keypair> = (0..64).map(|_| Keypair::generate(&mut csprng)).collect();
let msg: &[u8] = b"They're good dogs Brant";
let messages: Vec<&[u8]> = (0..64).map(|_| msg).collect();
let signatures:  Vec<Signature> = keypairs.iter().map(|key| key.sign(&msg)).collect();
let public_keys: Vec<PublicKey> = keypairs.iter().map(|key| key.public).collect();

let result = verify_batch(&messages[..], &signatures[..], &public_keys[..]);
assert!(result.is_ok());