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

schnorrkel/
batch.rs
