1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
// -*- mode: rust; -*-
//
// This file is part of ed25519-dalek.
// Copyright (c) 2017-2019 isis lovecruft
// See LICENSE for licensing information.
//
// Authors:
// - isis agora lovecruft <isis@patternsinthevoid.net>

//! Batch signature verification.

use alloc::vec::Vec;

use core::convert::TryFrom;
use core::iter::once;

use curve25519_dalek::constants;
use curve25519_dalek::edwards::EdwardsPoint;
use curve25519_dalek::scalar::Scalar;
use curve25519_dalek::traits::IsIdentity;
use curve25519_dalek::traits::VartimeMultiscalarMul;

pub use curve25519_dalek::digest::Digest;

use merlin::Transcript;

use rand_core::RngCore;

use sha2::Sha512;

use crate::errors::InternalError;
use crate::errors::SignatureError;
use crate::signature::InternalSignature;
use crate::VerifyingKey;

/// An implementation of `rand_core::RngCore` which does nothing. This is necessary because merlin
/// demands an `Rng` as input to `TranscriptRngBuilder::finalize()`. Using this with `finalize()`
/// yields a PRG whose input is the hashed transcript.
struct ZeroRng;

impl rand_core::RngCore for ZeroRng {
    fn next_u32(&mut self) -> u32 {
        rand_core::impls::next_u32_via_fill(self)
    }

    fn next_u64(&mut self) -> u64 {
        rand_core::impls::next_u64_via_fill(self)
    }

    /// A no-op function which leaves the destination bytes for randomness unchanged.
    ///
    /// In this case, the internal merlin code is initialising the destination
    /// by doing `[0u8; …]`, which means that when we call
    /// `merlin::TranscriptRngBuilder.finalize()`, rather than rekeying the
    /// STROBE state based on external randomness, we're doing an
    /// `ENC_{state}(00000000000000000000000000000000)` operation, which is
    /// identical to the STROBE `MAC` operation.
    fn fill_bytes(&mut self, _dest: &mut [u8]) {}

    fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), rand_core::Error> {
        self.fill_bytes(dest);
        Ok(())
    }
}

// `TranscriptRngBuilder::finalize()` requires a `CryptoRng`
impl rand_core::CryptoRng for ZeroRng {}

// We write our own gen() function so we don't need to pull in the rand crate
fn gen_u128<R: RngCore>(rng: &mut R) -> u128 {
    let mut buf = [0u8; 16];
    rng.fill_bytes(&mut buf);
    u128::from_le_bytes(buf)
}

/// Verify a batch of `signatures` on `messages` with their respective `verifying_keys`.
///
/// # Inputs
///
/// * `messages` is a slice of byte slices, one per signed message.
/// * `signatures` is a slice of `Signature`s.
/// * `verifying_keys` is a slice of `VerifyingKey`s.
///
/// # Returns
///
/// * A `Result` whose `Ok` value is an empty tuple and whose `Err` value is a
///   `SignatureError` containing a description of the internal error which
///   occurred.
///
/// ## On Deterministic Nonces
///
/// The nonces for batch signature verification are derived purely from the inputs to this function
/// themselves.
///
/// 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 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.
///
/// The former, while not quite as elegant as adding the `R`s, `A`s, and
/// `M`s 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 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 constitute 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.)
///
/// # Examples
///
/// ```
/// use ed25519_dalek::{
///     verify_batch, SigningKey, VerifyingKey, Signer, Signature,
/// };
/// use rand::rngs::OsRng;
///
/// # fn main() {
/// let mut csprng = OsRng;
/// let signing_keys: Vec<_> = (0..64).map(|_| SigningKey::generate(&mut csprng)).collect();
/// let msg: &[u8] = b"They're good dogs Brant";
/// let messages: Vec<_> = (0..64).map(|_| msg).collect();
/// let signatures:  Vec<_> = signing_keys.iter().map(|key| key.sign(&msg)).collect();
/// let verifying_keys: Vec<_> = signing_keys.iter().map(|key| key.verifying_key()).collect();
///
/// let result = verify_batch(&messages, &signatures, &verifying_keys);
/// assert!(result.is_ok());
/// # }
/// ```
#[allow(non_snake_case)]
pub fn verify_batch(
    messages: &[&[u8]],
    signatures: &[ed25519::Signature],
    verifying_keys: &[VerifyingKey],
) -> Result<(), SignatureError> {
    // Return an Error if any of the vectors were not the same size as the others.
    if signatures.len() != messages.len()
        || signatures.len() != verifying_keys.len()
        || verifying_keys.len() != messages.len()
    {
        return Err(InternalError::ArrayLength {
            name_a: "signatures",
            length_a: signatures.len(),
            name_b: "messages",
            length_b: messages.len(),
            name_c: "verifying_keys",
            length_c: verifying_keys.len(),
        }
        .into());
    }

    // Make a transcript which logs all inputs to this function
    let mut transcript: Transcript = Transcript::new(b"ed25519 batch verification");

    // We make one optimization in the transcript: since we will end up computing H(R || A || M)
    // for each (R, A, M) triplet, we will feed _that_ into our transcript rather than each R, A, M
    // individually. Since R and A are fixed-length, this modification is secure so long as SHA-512
    // is collision-resistant.
    // It suffices to take `verifying_keys[i].as_bytes()` even though a `VerifyingKey` has two
    // fields, and `as_bytes()` only returns the bytes of the first. This is because of an
    // invariant guaranteed by `VerifyingKey`: the second field is always the (unique)
    // decompression of the first. Thus, the serialized first field is a unique representation of
    // the entire `VerifyingKey`.
    let hrams: Vec<[u8; 64]> = (0..signatures.len())
        .map(|i| {
            // Compute H(R || A || M), where
            // R = sig.R
            // A = verifying key
            // M = msg
            let mut h: Sha512 = Sha512::default();
            h.update(signatures[i].r_bytes());
            h.update(verifying_keys[i].as_bytes());
            h.update(messages[i]);
            *h.finalize().as_ref()
        })
        .collect();

    // Update transcript with the hashes above. This covers verifying_keys, messages, and the R
    // half of signatures
    for hram in hrams.iter() {
        transcript.append_message(b"hram", hram);
    }
    // Update transcript with the rest of the data. This covers the s half of the signatures
    for sig in signatures {
        transcript.append_message(b"sig.s", sig.s_bytes());
    }

    // All function inputs have now been hashed into the transcript. Finalize it and use it as
    // randomness for the batch verification.
    let mut rng = transcript.build_rng().finalize(&mut ZeroRng);

    // Convert all signatures to `InternalSignature`
    let signatures = signatures
        .iter()
        .map(InternalSignature::try_from)
        .collect::<Result<Vec<_>, _>>()?;
    // Convert the H(R || A || M) values into scalars
    let hrams: Vec<Scalar> = hrams
        .iter()
        .map(Scalar::from_bytes_mod_order_wide)
        .collect();

    // Select a random 128-bit scalar for each signature.
    let zs: Vec<Scalar> = signatures
        .iter()
        .map(|_| Scalar::from(gen_u128(&mut rng)))
        .collect();

    // Compute the basepoint coefficient, ∑ s[i]z[i] (mod l)
    let B_coefficient: Scalar = signatures
        .iter()
        .map(|sig| sig.s)
        .zip(zs.iter())
        .map(|(s, z)| z * s)
        .sum();

    // Multiply each H(R || A || M) by the random value
    let zhrams = hrams.iter().zip(zs.iter()).map(|(hram, z)| hram * z);

    let Rs = signatures.iter().map(|sig| sig.R.decompress());
    let As = verifying_keys.iter().map(|pk| Some(pk.point));
    let B = once(Some(constants::ED25519_BASEPOINT_POINT));

    // Compute (-∑ z[i]s[i] (mod l)) B + ∑ z[i]R[i] + ∑ (z[i]H(R||A||M)[i] (mod l)) A[i] = 0
    let id = EdwardsPoint::optional_multiscalar_mul(
        once(-B_coefficient).chain(zs.iter().cloned()).chain(zhrams),
        B.chain(Rs).chain(As),
    )
    .ok_or(InternalError::Verify)?;

    if id.is_identity() {
        Ok(())
    } else {
        Err(InternalError::Verify.into())
    }
}