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

schnorrkel_purplecoin/
batch.rs
