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
use rand_core::{RngCore, CryptoRng};
use zeroize::Zeroize;
use ff::{Field, PrimeFieldBits};
use group::Group;
use crate::{multiexp, multiexp_vartime};
/// A batch verifier intended to verify a series of statements are each equivalent to zero.
#[derive(Clone, Zeroize)]
pub struct BatchVerifier<Id: Copy + Zeroize, G: Group + Zeroize>(Vec<(Id, Vec<(G::Scalar, G)>)>);
impl<Id: Copy + Zeroize, G: Group + Zeroize> BatchVerifier<Id, G>
where
<G as Group>::Scalar: PrimeFieldBits + Zeroize,
{
/// Create a new batch verifier, expected to verify the following amount of statements.
/// This is a size hint and is not required to be accurate.
pub fn new(capacity: usize) -> BatchVerifier<Id, G> {
BatchVerifier(Vec::with_capacity(capacity))
}
/// Queue a statement for batch verification.
pub fn queue<R: RngCore + CryptoRng, I: IntoIterator<Item = (G::Scalar, G)>>(
&mut self,
rng: &mut R,
id: Id,
pairs: I,
) {
// Define a unique scalar factor for this set of variables so individual items can't overlap
let u = if self.0.is_empty() {
G::Scalar::one()
} else {
let mut weight;
while {
// Generate a random scalar
weight = G::Scalar::random(&mut *rng);
// Clears half the bits, maintaining security, to minimize scalar additions
// Is not practically faster for whatever reason
/*
// Generate a random scalar
let mut repr = G::Scalar::random(&mut *rng).to_repr();
// Calculate the amount of bytes to clear. We want to clear less than half
let repr_len = repr.as_ref().len();
let unused_bits = (repr_len * 8) - usize::try_from(G::Scalar::CAPACITY).unwrap();
// Don't clear any partial bytes
let to_clear = (repr_len / 2) - ((unused_bits + 7) / 8);
// Clear a safe amount of bytes
for b in &mut repr.as_mut()[.. to_clear] {
*b = 0;
}
// Ensure these bits are used as the low bits so low scalars multiplied by this don't
// become large scalars
weight = G::Scalar::from_repr(repr).unwrap();
// Tests if any bit we supposedly just cleared is set, and if so, reverses it
// Not a security issue if this fails, just a minor performance hit at ~2^-120 odds
if weight.to_le_bits().iter().take(to_clear * 8).any(|bit| *bit) {
repr.as_mut().reverse();
weight = G::Scalar::from_repr(repr).unwrap();
}
*/
// Ensure it's non-zero, as a zero scalar would cause this item to pass no matter what
weight.is_zero().into()
} {}
weight
};
self.0.push((id, pairs.into_iter().map(|(scalar, point)| (scalar * u, point)).collect()));
}
/// Perform batch verification, returning a boolean of if the statements equaled zero.
#[must_use]
pub fn verify_core(&self) -> bool {
let mut flat = self.0.iter().flat_map(|pairs| pairs.1.iter()).cloned().collect::<Vec<_>>();
let res = multiexp(&flat).is_identity().into();
flat.zeroize();
res
}
/// Perform batch verification, zeroizing the statements verified.
pub fn verify(mut self) -> bool {
let res = self.verify_core();
self.zeroize();
res
}
/// Perform batch verification in variable time.
#[must_use]
pub fn verify_vartime(&self) -> bool {
multiexp_vartime(&self.0.iter().flat_map(|pairs| pairs.1.iter()).cloned().collect::<Vec<_>>())
.is_identity()
.into()
}
/// Perform a binary search to identify which statement does not equal 0, returning None if all
/// statements do. This function will only return the ID of one invalid statement, even if
/// multiple are invalid.
// A constant time variant may be beneficial for robust protocols
pub fn blame_vartime(&self) -> Option<Id> {
let mut slice = self.0.as_slice();
while slice.len() > 1 {
let split = slice.len() / 2;
if multiexp_vartime(
&slice[.. split].iter().flat_map(|pairs| pairs.1.iter()).cloned().collect::<Vec<_>>(),
)
.is_identity()
.into()
{
slice = &slice[split ..];
} else {
slice = &slice[.. split];
}
}
slice
.get(0)
.filter(|(_, value)| !bool::from(multiexp_vartime(value).is_identity()))
.map(|(id, _)| *id)
}
/// Perform constant time batch verification, and if verification fails, identify one faulty
/// statement in variable time.
pub fn verify_with_vartime_blame(mut self) -> Result<(), Id> {
let res = if self.verify_core() { Ok(()) } else { Err(self.blame_vartime().unwrap()) };
self.zeroize();
res
}
/// Perform variable time batch verification, and if verification fails, identify one faulty
/// statement in variable time.
pub fn verify_vartime_with_vartime_blame(&self) -> Result<(), Id> {
if self.verify_vartime() {
Ok(())
} else {
Err(self.blame_vartime().unwrap())
}
}
}