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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

//! Performs batch Schnorr signature verification.
//!
//! Batch verification asks whether *all* signatures in some set are valid,
//! rather than asking whether *each* of them is valid. This allows sharing
//! computations among all signature verifications, performing less work overall
//! at the cost of higher latency (the entire batch must complete), complexity
//! of caller code (which must assemble a batch of signatures across
//! work-items), and loss of the ability to easily pinpoint failing signatures.

use std::iter::once;

use rand_core::{CryptoRng, RngCore};

use crate::{scalar_mul::VartimeMultiscalarMul, Ciphersuite, Element, *};

/// A batch verification item.
///
/// This struct exists to allow batch processing to be decoupled from the
/// lifetime of the message. This is useful when using the batch verification
/// API in an async context.
#[derive(Clone, Debug)]
pub struct Item<C: Ciphersuite> {
    vk: VerifyingKey<C>,
    sig: Signature<C>,
    c: Challenge<C>,
}

impl<'msg, C, M> From<(VerifyingKey<C>, Signature<C>, &'msg M)> for Item<C>
where
    C: Ciphersuite,
    M: AsRef<[u8]>,
{
    fn from((vk, sig, msg): (VerifyingKey<C>, Signature<C>, &'msg M)) -> Self {
        // Compute c now to avoid dependency on the msg lifetime.
        let c = crate::challenge(&sig.R, &vk.element, msg.as_ref());

        Self { vk, sig, c }
    }
}

impl<C> Item<C>
where
    C: Ciphersuite,
{
    /// Perform non-batched verification of this `Item`.
    ///
    /// This is useful (in combination with `Item::clone`) for implementing
    /// fallback logic when batch verification fails. In contrast to
    /// [`VerifyingKey::verify`](crate::VerifyingKey::verify), which
    /// requires borrowing the message data, the `Item` type is unlinked
    /// from the lifetime of the message.
    pub fn verify_single(self) -> Result<(), Error<C>> {
        self.vk.verify_prehashed(self.c, &self.sig)
    }
}

/// A batch verification context.
pub struct Verifier<C: Ciphersuite> {
    /// Signature data queued for verification.
    signatures: Vec<Item<C>>,
}

impl<C> Verifier<C>
where
    C: Ciphersuite,
{
    /// Constructs a new batch verifier.
    pub fn new() -> Verifier<C> {
        Verifier::default()
    }

    /// Queues an Item for verification.
    pub fn queue<I: Into<Item<C>>>(&mut self, item: I) {
        self.signatures.push(item.into());
    }

    /// Performs batch verification, returning `Ok(())` if all signatures were
    /// valid and `Err` otherwise, or if the batch is empty.
    ///
    /// The batch verification equation is:
    ///
    /// h_G * -[sum(z_i * s_i)]P_G + sum(\[z_i\]R_i + [z_i * c_i]VK_i) = 0_G
    ///
    /// which we split out into:
    ///
    /// h_G * -[sum(z_i * s_i)]P_G + sum(\[z_i\]R_i) + sum([z_i * c_i]VK_i) =
    /// 0_G
    ///
    /// so that we can use multiscalar multiplication speedups.
    ///
    /// where for each signature i,
    /// - VK_i is the verification key;
    /// - R_i is the signature's R value;
    /// - s_i is the signature's s value;
    /// - c_i is the hash of the message and other data;
    /// - z_i is a random 128-bit Scalar;
    /// - h_G is the cofactor of the group;
    /// - P_G is the generator of the subgroup;
    ///
    /// As follows elliptic curve scalar multiplication convention,
    /// scalar variables are lowercase and group point variables
    /// are uppercase. This does not exactly match the RedDSA
    /// notation in the [protocol specification §B.1][ps].
    ///
    /// [ps]: https://zips.z.cash/protocol/protocol.pdf#reddsabatchverify
    pub fn verify<R: RngCore + CryptoRng>(self, mut rng: R) -> Result<(), Error<C>> {
        let n = self.signatures.len();

        if n == 0 {
            return Err(Error::InvalidSignature);
        }

        let mut VK_coeffs = Vec::with_capacity(n);
        let mut VKs = Vec::with_capacity(n);
        let mut R_coeffs = Vec::with_capacity(n);
        let mut Rs = Vec::with_capacity(n);
        let mut P_coeff_acc = <<C::Group as Group>::Field>::zero();

        for item in self.signatures.iter() {
            let z = item.sig.z;
            let R = item.sig.R;

            let blind = <<C::Group as Group>::Field>::random(&mut rng);

            let P_coeff = blind * z;
            P_coeff_acc = P_coeff_acc - P_coeff;

            R_coeffs.push(blind);
            Rs.push(R);

            VK_coeffs.push(<<C::Group as Group>::Field>::zero() + (blind * item.c.0));
            VKs.push(item.vk.element);
        }

        let scalars = once(&P_coeff_acc)
            .chain(VK_coeffs.iter())
            .chain(R_coeffs.iter());

        let basepoints = [C::Group::generator()];
        let points = basepoints.iter().chain(VKs.iter()).chain(Rs.iter());

        let check: Element<C> =
            VartimeMultiscalarMul::<C>::vartime_multiscalar_mul(scalars, points);

        if (check * <C::Group>::cofactor()) == <C::Group>::identity() {
            Ok(())
        } else {
            Err(Error::InvalidSignature)
        }
    }
}

impl<C> Default for Verifier<C>
where
    C: Ciphersuite,
{
    fn default() -> Self {
        Self { signatures: vec![] }
    }
}