multiexp/
batch.rs

1use std_shims::vec::Vec;
2
3use rand_core::{RngCore, CryptoRng};
4
5use zeroize::{Zeroize, Zeroizing};
6
7use ff::{Field, PrimeFieldBits};
8use group::Group;
9
10use crate::{multiexp, multiexp_vartime};
11
12// Flatten the contained statements to a single Vec.
13// Wrapped in Zeroizing in case any of the included statements contain private values.
14#[allow(clippy::type_complexity)]
15fn flat<Id: Copy + Zeroize, G: Zeroize + Group<Scalar: Zeroize + PrimeFieldBits>>(
16  slice: &[(Id, Vec<(G::Scalar, G)>)],
17) -> Zeroizing<Vec<(G::Scalar, G)>> {
18  Zeroizing::new(slice.iter().flat_map(|pairs| pairs.1.iter()).copied().collect::<Vec<_>>())
19}
20
21/// A batch verifier intended to verify a series of statements are each equivalent to zero.
22#[allow(clippy::type_complexity)]
23#[derive(Clone, Zeroize)]
24pub struct BatchVerifier<Id: Copy + Zeroize, G: Zeroize + Group<Scalar: Zeroize + PrimeFieldBits>>(
25  Zeroizing<Vec<(Id, Vec<(G::Scalar, G)>)>>,
26);
27
28impl<Id: Copy + Zeroize, G: Zeroize + Group<Scalar: Zeroize + PrimeFieldBits>>
29  BatchVerifier<Id, G>
30{
31  /// Create a new batch verifier, expected to verify the following amount of statements.
32  ///
33  /// `capacity` is a size hint and is not required to be accurate.
34  pub fn new(capacity: usize) -> BatchVerifier<Id, G> {
35    BatchVerifier(Zeroizing::new(Vec::with_capacity(capacity)))
36  }
37
38  /// Queue a statement for batch verification.
39  pub fn queue<R: RngCore + CryptoRng, I: IntoIterator<Item = (G::Scalar, G)>>(
40    &mut self,
41    rng: &mut R,
42    id: Id,
43    pairs: I,
44  ) {
45    // Define a unique scalar factor for this set of variables so individual items can't overlap
46    let u = if self.0.is_empty() {
47      G::Scalar::ONE
48    } else {
49      let mut weight;
50      while {
51        // Generate a random scalar
52        weight = G::Scalar::random(&mut *rng);
53
54        // Clears half the bits, maintaining security, to minimize scalar additions
55        // Is not practically faster for whatever reason
56        /*
57        // Generate a random scalar
58        let mut repr = G::Scalar::random(&mut *rng).to_repr();
59
60        // Calculate the amount of bytes to clear. We want to clear less than half
61        let repr_len = repr.as_ref().len();
62        let unused_bits = (repr_len * 8) - usize::try_from(G::Scalar::CAPACITY).unwrap();
63        // Don't clear any partial bytes
64        let to_clear = (repr_len / 2) - ((unused_bits + 7) / 8);
65
66        // Clear a safe amount of bytes
67        for b in &mut repr.as_mut()[.. to_clear] {
68          *b = 0;
69        }
70
71        // Ensure these bits are used as the low bits so low scalars multiplied by this don't
72        // become large scalars
73        weight = G::Scalar::from_repr(repr).unwrap();
74        // Tests if any bit we supposedly just cleared is set, and if so, reverses it
75        // Not a security issue if this fails, just a minor performance hit at ~2^-120 odds
76        if weight.to_le_bits().iter().take(to_clear * 8).any(|bit| *bit) {
77          repr.as_mut().reverse();
78          weight = G::Scalar::from_repr(repr).unwrap();
79        }
80        */
81
82        // Ensure it's non-zero, as a zero scalar would cause this item to pass no matter what
83        weight.is_zero().into()
84      } {}
85      weight
86    };
87
88    self.0.push((id, pairs.into_iter().map(|(scalar, point)| (scalar * u, point)).collect()));
89  }
90
91  /// Perform batch verification, returning a boolean of if the statements equaled zero.
92  #[must_use]
93  pub fn verify(&self) -> bool {
94    multiexp(&flat(&self.0)).is_identity().into()
95  }
96
97  /// Perform batch verification in variable time.
98  #[must_use]
99  pub fn verify_vartime(&self) -> bool {
100    multiexp_vartime(&flat(&self.0)).is_identity().into()
101  }
102
103  /// Perform a binary search to identify which statement does not equal 0, returning None if all
104  /// statements do.
105  ///
106  /// This function will only return the ID of one invalid statement, even if multiple are invalid.
107  // A constant time variant may be beneficial for robust protocols
108  pub fn blame_vartime(&self) -> Option<Id> {
109    let mut slice = self.0.as_slice();
110    while slice.len() > 1 {
111      let split = slice.len() / 2;
112      if multiexp_vartime(&flat(&slice[.. split])).is_identity().into() {
113        slice = &slice[split ..];
114      } else {
115        slice = &slice[.. split];
116      }
117    }
118
119    slice
120      .first()
121      .filter(|(_, value)| !bool::from(multiexp_vartime(value).is_identity()))
122      .map(|(id, _)| *id)
123  }
124
125  /// Perform constant time batch verification, and if verification fails, identify one faulty
126  /// statement in variable time.
127  pub fn verify_with_vartime_blame(&self) -> Result<(), Id> {
128    if self.verify() {
129      Ok(())
130    } else {
131      Err(self.blame_vartime().unwrap())
132    }
133  }
134
135  /// Perform variable time batch verification, and if verification fails, identify one faulty
136  /// statement in variable time.
137  pub fn verify_vartime_with_vartime_blame(&self) -> Result<(), Id> {
138    if self.verify_vartime() {
139      Ok(())
140    } else {
141      Err(self.blame_vartime().unwrap())
142    }
143  }
144}
multiexp/batch.rs

multiexp/
batch.rs
