schnorrkel/
batch.rs

1// -*- mode: rust; -*-
2//
3// This file is part of schnorrkel.
4// Copyright (c) 2017-2019 isis lovecruft
5// Copyright (c) 2019 Web 3 Foundation
6// See LICENSE for licensing information.
7//
8// Authors:
9// - Jeffrey Burdges <jeff@web3.foundation>
10// - isis agora lovecruft <isis@patternsinthevoid.net>
11
12//! ### Schnorr signature batch verification.
13
14use curve25519_dalek::constants;
15use curve25519_dalek::ristretto::{CompressedRistretto, RistrettoPoint};
16use curve25519_dalek::scalar::Scalar;
17
18use super::*;
19use crate::context::{SigningTranscript};
20
21#[cfg(feature = "alloc")]
22use alloc::vec::Vec;
23
24const ASSERT_MESSAGE: &str =
25    "The number of messages/transcripts, signatures, and public keys must be equal.";
26
27/// Verify a batch of `signatures` on `messages` with their respective `public_keys`.
28///
29/// # Inputs
30///
31/// * `messages` is a slice of byte slices, one per signed message.
32/// * `signatures` is a slice of `Signature`s.
33/// * `public_keys` is a slice of `PublicKey`s.
34/// * `deduplicate_public_keys`
35/// * `csprng` is an implementation of `RngCore+CryptoRng`, such as `rand::ThreadRng`.
36///
37/// # Panics
38///
39/// This function will panic if the `messages, `signatures`, and `public_keys`
40/// slices are not equal length.
41///
42/// # Returns
43///
44/// * A `Result` whose `Ok` value is an empty tuple and whose `Err` value is a
45///   `SignatureError` containing a description of the internal error which
46///   occurred.
47///
48/// # Examples
49///
50/// ```
51/// use schnorrkel::{Keypair,PublicKey,Signature,verify_batch,signing_context};
52///
53/// # fn main() {
54/// let ctx = signing_context(b"some batch");
55/// let mut csprng = rand::thread_rng();
56/// let keypairs: Vec<Keypair> = (0..64).map(|_| Keypair::generate_with(&mut csprng)).collect();
57/// let msg: &[u8] = b"They're good dogs Brant";
58/// let signatures:  Vec<Signature> = keypairs.iter().map(|key| key.sign(ctx.bytes(&msg))).collect();
59/// let public_keys: Vec<PublicKey> = keypairs.iter().map(|key| key.public).collect();
60///
61/// let transcripts = std::iter::once(ctx.bytes(msg)).cycle().take(64);
62///
63/// assert!( verify_batch(transcripts, &signatures[..], &public_keys[..], false).is_ok() );
64/// # }
65/// ```
66pub fn verify_batch<T, I>(
67    transcripts: I,
68    signatures: &[Signature],
69    public_keys: &[PublicKey],
70    deduplicate_public_keys: bool,
71) -> SignatureResult<()>
72where
73    T: SigningTranscript,
74    I: IntoIterator<Item = T>,
75{
76    verify_batch_rng(
77        transcripts,
78        signatures,
79        public_keys,
80        deduplicate_public_keys,
81        getrandom_or_panic(),
82    )
83}
84
85struct NotAnRng;
86#[rustfmt::skip]
87impl rand_core::RngCore for NotAnRng {
88    fn next_u32(&mut self) -> u32 { rand_core::impls::next_u32_via_fill(self) }
89
90    fn next_u64(&mut self) -> u64 { rand_core::impls::next_u64_via_fill(self) }
91
92    /// A no-op function which leaves the destination bytes for randomness unchanged.
93    fn fill_bytes(&mut self, dest: &mut [u8]) { zeroize::Zeroize::zeroize(dest) }
94
95    fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), rand_core::Error> {
96        self.fill_bytes(dest);
97        Ok(())
98    }
99}
100impl rand_core::CryptoRng for NotAnRng {}
101
102/// Verify a batch of `signatures` on `messages` with their respective `public_keys`.
103///
104/// Avoids using system randomness and instead depends entirely upon delinearization.
105///
106/// We break the `R: CryptRng` requirement from `verify_batch_rng`
107/// here, but this appears fine using an Fiat-Shamir transform with
108/// an argument similar to
109/// [public key delinearization](https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html).
110///
111/// We caution deeterministic delinearization could interact poorly
112/// with other functionality, *if* one delinarization scalar were
113/// left constant.  We do not make that mistake here.
114pub fn verify_batch_deterministic<T, I>(
115    transcripts: I,
116    signatures: &[Signature],
117    public_keys: &[PublicKey],
118    deduplicate_public_keys: bool,
119) -> SignatureResult<()>
120where
121    T: SigningTranscript,
122    I: IntoIterator<Item = T>,
123{
124    verify_batch_rng(transcripts, signatures, public_keys, deduplicate_public_keys, NotAnRng)
125}
126
127/// Verify a batch of `signatures` on `messages` with their respective `public_keys`.
128///
129/// Inputs and return agree with `verify_batch` except the user supplies their own random number generator.
130#[rustfmt::skip]
131pub fn verify_batch_rng<T,I,R>(
132    transcripts: I,
133    signatures: &[Signature],
134    public_keys: &[PublicKey],
135    deduplicate_public_keys: bool,
136    rng: R,
137) -> SignatureResult<()>
138where
139    T: SigningTranscript,
140    I: IntoIterator<Item=T>,
141    R: RngCore+CryptoRng,
142{
143    assert!(signatures.len() == public_keys.len(), "{}", ASSERT_MESSAGE);  // Check transcripts length below
144
145    let (zs, hrams) = prepare_batch(transcripts, signatures, public_keys, rng);
146
147    // Compute the basepoint coefficient, ∑ s[i]z[i] (mod l)
148    let bs: Scalar = signatures.iter()
149        .map(|sig| sig.s)
150        .zip(zs.iter())
151        .map(|(s, z)| z * s)
152        .sum();
153
154    verify_batch_equation( bs, zs, hrams, signatures, public_keys, deduplicate_public_keys )
155}
156
157trait HasR {
158    #[allow(non_snake_case)]
159    fn get_R(&self) -> &CompressedRistretto;
160}
161#[rustfmt::skip]
162impl HasR for Signature {
163    #[allow(non_snake_case)]
164    fn get_R(&self) -> &CompressedRistretto { &self.R }
165}
166#[rustfmt::skip]
167impl HasR for CompressedRistretto {
168    #[allow(non_snake_case)]
169    fn get_R(&self) -> &CompressedRistretto { self }
170}
171
172/// First phase of batch verification that computes the delinierizing
173/// coefficents and challenge hashes
174#[allow(non_snake_case)]
175#[rustfmt::skip]
176fn prepare_batch<T,I,R>(
177    transcripts: I,
178    signatures: &[impl HasR],
179    public_keys: &[PublicKey],
180    mut rng: R,
181) -> (Vec<Scalar>,Vec<Scalar>)
182where
183    T: SigningTranscript,
184    I: IntoIterator<Item=T>,
185    R: RngCore+CryptoRng,
186{
187
188    // Assumulate public keys, signatures, and transcripts for pseudo-random delinearization scalars
189    let mut zs_t = merlin::Transcript::new(b"V-RNG");
190    for pk in public_keys {
191        zs_t.commit_point(b"",pk.as_compressed());
192    }
193    for sig in signatures {
194        zs_t.commit_point(b"",sig.get_R());
195    }
196
197    // We might collect here anyways, but right now you cannot have
198    //   IntoIterator<Item=T, IntoIter: ExactSizeIterator+TrustedLen>
199    let mut transcripts = transcripts.into_iter();
200    // Compute H(R || A || M) for each (signature, public_key, message) triplet
201    let hrams: Vec<Scalar> = transcripts.by_ref()
202        .zip(0..signatures.len())
203        .map( |(mut t,i)| {
204            let mut d = [0u8; 16];
205            t.witness_bytes_rng(b"", &mut d, &[&[]], NotAnRng);  // Could speed this up using ZeroRng
206            zs_t.append_message(b"",&d);
207
208            t.proto_name(b"Schnorr-sig");
209            t.commit_point(b"sign:pk",public_keys[i].as_compressed());
210            t.commit_point(b"sign:R",signatures[i].get_R());
211            t.challenge_scalar(b"sign:c")  // context, message, A/public_key, R=rG
212        } ).collect();
213    assert!(transcripts.next().is_none(), "{}", ASSERT_MESSAGE);
214    assert!(hrams.len() == public_keys.len(), "{}", ASSERT_MESSAGE);
215
216    // Use a random number generator keyed by both the public keys,
217    // and the system random number generator
218    let mut csprng = zs_t.build_rng().finalize(&mut rng);
219    // Select a random 128-bit scalar for each signature.
220    // We may represent these as scalars because we use
221    // variable time 256 bit multiplication below.
222    let rnd_128bit_scalar = |_| {
223        let mut r = [0u8; 16];
224        csprng.fill_bytes(&mut r);
225        Scalar::from(u128::from_le_bytes(r))
226    };
227    let zs: Vec<Scalar> = signatures.iter().map(rnd_128bit_scalar).collect();
228
229    (zs, hrams)
230}
231
232/// Last phase of batch verification that checks the verification equation
233#[allow(non_snake_case)]
234#[rustfmt::skip]
235fn verify_batch_equation(
236    bs: Scalar,
237    zs: Vec<Scalar>,
238    mut hrams: Vec<Scalar>,
239    signatures: &[impl HasR],
240    public_keys: &[PublicKey],
241    deduplicate_public_keys: bool,
242) -> SignatureResult<()>
243{
244    use curve25519_dalek::traits::IsIdentity;
245    use curve25519_dalek::traits::VartimeMultiscalarMul;
246
247    use core::iter::once;
248
249    let B = once(Some(constants::RISTRETTO_BASEPOINT_POINT));
250
251    let Rs = signatures.iter().map(|sig| sig.get_R().decompress());
252
253    let mut ppks = Vec::new();
254    let As = if ! deduplicate_public_keys {
255        // Multiply each H(R || A || M) by the random value
256        for (hram, z) in hrams.iter_mut().zip(zs.iter()) {
257            *hram *= z;
258        }
259        public_keys
260    } else {
261        // TODO: Actually deduplicate all if deduplicate_public_keys is set?
262        ppks.reserve( public_keys.len() );
263        // Multiply each H(R || A || M) by the random value
264        for i in 0..public_keys.len() {
265            let zhram = hrams[i] * zs[i];
266            let j = ppks.len().checked_sub(1);
267            if j.is_none() || ppks[j.unwrap()] != public_keys[i] {
268                ppks.push(public_keys[i]);
269                hrams[ppks.len()-1] = zhram;
270            } else {
271                hrams[ppks.len()-1] = hrams[ppks.len()-1] + zhram;
272            }
273        }
274        hrams.truncate(ppks.len());
275        ppks.as_slice()
276    }.iter().map(|pk| Some(*pk.as_point()));
277
278    // Compute (-∑ z[i]s[i] (mod l)) B + ∑ z[i]R[i] + ∑ (z[i]H(R||A||M)[i] (mod l)) A[i] = 0
279    let b = RistrettoPoint::optional_multiscalar_mul(
280        once(-bs).chain(zs.iter().cloned()).chain(hrams),
281        B.chain(Rs).chain(As),
282    ).map(|id| id.is_identity()).unwrap_or(false);
283    // We need not return SignatureError::PointDecompressionError because
284    // the decompression failures occur for R represent invalid signatures.
285
286    if b { Ok(()) } else { Err(SignatureError::EquationFalse) }
287}
288
289/// Half-aggregated aka prepared batch signature
290///
291/// Implementation of "Non-interactive half-aggregation of EdDSA and
292/// variantsof Schnorr signatures" by  Konstantinos Chalkias,
293/// François Garillot, Yashvanth Kondi, and Valeria Nikolaenko
294/// available from https://eprint.iacr.org/2021/350.pdf
295#[allow(non_snake_case)]
296pub struct PreparedBatch {
297    bs: Scalar,
298    Rs: Vec<CompressedRistretto>,
299}
300
301impl PreparedBatch {
302    /// Create a half-aggregated aka prepared batch signature from many other signatures.
303    #[allow(non_snake_case)]
304    #[rustfmt::skip]
305    pub fn new<T,I,R>(
306        transcripts: I,
307        signatures: &[Signature],
308        public_keys: &[PublicKey],
309    ) -> PreparedBatch
310    where
311        T: SigningTranscript,
312        I: IntoIterator<Item=T>,
313    {
314        assert!(signatures.len() == public_keys.len(), "{}", ASSERT_MESSAGE);  // Check transcripts length below
315
316        let (zs, _hrams) = prepare_batch(transcripts, signatures, public_keys, NotAnRng);
317
318        // Compute the basepoint coefficient, ∑ s[i]z[i] (mod l)
319        let bs: Scalar = signatures.iter()
320            .map(|sig| sig.s)
321            .zip(zs.iter())
322            .map(|(s, z)| z * s)
323            .sum();
324
325        let Rs = signatures.iter().map(|sig| sig.R).collect();
326        PreparedBatch { bs, Rs, }
327    }
328
329    /// Verify a half-aggregated aka prepared batch signature
330    #[allow(non_snake_case)]
331    #[rustfmt::skip]
332    pub fn verify<T,I>(
333        &self,
334        transcripts: I,
335        public_keys: &[PublicKey],
336        deduplicate_public_keys: bool,
337    ) -> SignatureResult<()>
338    where
339        T: SigningTranscript,
340        I: IntoIterator<Item=T>,
341    {
342        assert!(self.Rs.len() == public_keys.len(), "{}", ASSERT_MESSAGE);  // Check transcripts length below
343
344        let (zs, hrams) = prepare_batch(transcripts, self.Rs.as_slice(), public_keys, NotAnRng);
345
346        verify_batch_equation(
347            self.bs,
348            zs, hrams,
349            self.Rs.as_slice(),
350            public_keys, deduplicate_public_keys
351        )
352    }
353
354    /// Reads a `PreparedBatch` from a correctly sized buffer
355    #[allow(non_snake_case)]
356    pub fn read_bytes(&self, mut bytes: &[u8]) -> SignatureResult<PreparedBatch> {
357        use arrayref::array_ref;
358        if bytes.len() % 32 != 0 || bytes.len() < 64 {
359            return Err(SignatureError::BytesLengthError {
360                name: "PreparedBatch",
361                description: "A Prepared batched signature",
362                length: 0, // TODO: Maybe get rid of this silly field?
363            });
364        }
365        let l = (bytes.len() % 32) - 1;
366        let mut read = || {
367            let (head, tail) = bytes.split_at(32);
368            bytes = tail;
369            *array_ref![head, 0, 32]
370        };
371        let mut bs = read();
372        bs[31] &= 127;
373        let bs = super::sign::check_scalar(bs)?;
374        let mut Rs = Vec::with_capacity(l);
375        for _ in 0..l {
376            Rs.push(CompressedRistretto(read()));
377        }
378        Ok(PreparedBatch { bs, Rs })
379    }
380
381    /// Returns buffer size required for serialization
382    #[allow(non_snake_case)]
383    pub fn byte_len(&self) -> usize {
384        32 + 32 * self.Rs.len()
385    }
386
387    /// Serializes into exactly sized buffer
388    #[allow(non_snake_case)]
389    pub fn write_bytes(&self, mut bytes: &mut [u8]) {
390        assert!(bytes.len() == self.byte_len());
391        let mut place = |s: &[u8]| reserve_mut(&mut bytes, 32).copy_from_slice(s);
392        let mut bs = self.bs.to_bytes();
393        bs[31] |= 128;
394        place(&bs[..]);
395        for R in self.Rs.iter() {
396            place(R.as_bytes());
397        }
398    }
399}
400
401pub fn reserve_mut<'heap, T>(heap: &mut &'heap mut [T], len: usize) -> &'heap mut [T] {
402    let tmp: &'heap mut [T] = core::mem::take(&mut *heap);
403    let (reserved, tmp) = tmp.split_at_mut(len);
404    *heap = tmp;
405    reserved
406}
407
408#[cfg(test)]
409mod test {
410    #[cfg(feature = "alloc")]
411    use alloc::vec::Vec;
412
413    use rand::prelude::*; // ThreadRng,thread_rng
414
415    use super::super::*;
416
417    #[cfg(feature = "alloc")]
418    #[test]
419    fn verify_batch_seven_signatures() {
420        let ctx = signing_context(b"my batch context");
421
422        let messages: [&[u8]; 7] = [
423            b"Watch closely everyone, I'm going to show you how to kill a god.",
424            b"I'm not a cryptographer I just encrypt a lot.",
425            b"Still not a cryptographer.",
426            b"This is a test of the tsunami alert system. This is only a test.",
427            b"Fuck dumbin' it down, spit ice, skip jewellery: Molotov cocktails on me like accessories.",
428            b"Hey, I never cared about your bucks, so if I run up with a mask on, probably got a gas can too.",
429            b"And I'm not here to fill 'er up. Nope, we came to riot, here to incite, we don't want any of your stuff.", ];
430        let mut csprng: ThreadRng = thread_rng();
431        let mut keypairs: Vec<Keypair> = Vec::new();
432        let mut signatures: Vec<Signature> = Vec::new();
433
434        for i in 0..messages.len() {
435            let mut keypair: Keypair = Keypair::generate_with(&mut csprng);
436            if i == 3 || i == 4 {
437                keypair = keypairs[0].clone();
438            }
439            signatures.push(keypair.sign(ctx.bytes(messages[i])));
440            keypairs.push(keypair);
441        }
442        let mut public_keys: Vec<PublicKey> = keypairs.iter().map(|key| key.public).collect();
443
444        public_keys.swap(1, 2);
445        let transcripts = messages.iter().map(|m| ctx.bytes(m));
446        assert!(verify_batch(transcripts, &signatures[..], &public_keys[..], false).is_err());
447        let transcripts = messages.iter().map(|m| ctx.bytes(m));
448        assert!(verify_batch(transcripts, &signatures[..], &public_keys[..], true).is_err());
449
450        public_keys.swap(1, 2);
451        let transcripts = messages.iter().map(|m| ctx.bytes(m));
452        assert!(verify_batch(transcripts, &signatures[..], &public_keys[..], false).is_ok());
453        let transcripts = messages.iter().map(|m| ctx.bytes(m));
454        assert!(verify_batch(transcripts, &signatures[..], &public_keys[..], true).is_ok());
455
456        signatures.swap(1, 2);
457        let transcripts = messages.iter().map(|m| ctx.bytes(m));
458        assert!(verify_batch(transcripts, &signatures[..], &public_keys[..], false).is_err());
459        let transcripts = messages.iter().map(|m| ctx.bytes(m));
460        assert!(verify_batch(transcripts, &signatures[..], &public_keys[..], true).is_err());
461    }
462}
schnorrkel/batch.rs

schnorrkel/
batch.rs
