generalized_schnorr/
lib.rs

1#![cfg_attr(docsrs, feature(doc_auto_cfg))]
2#![doc = include_str!("../README.md")]
3#![cfg_attr(not(feature = "std"), no_std)]
4#![allow(non_snake_case)]
5
6use core::ops::Deref;
7#[cfg(not(feature = "std"))]
8#[macro_use]
9extern crate alloc;
10use std_shims::io::{self, Read, Write};
11
12use rand_core::{RngCore, CryptoRng};
13
14use zeroize::{Zeroize, Zeroizing};
15
16use blake2::{Digest, Blake2b512};
17
18use ciphersuite::{
19  group::{
20    ff::{Field, PrimeField},
21    Group, GroupEncoding,
22  },
23  Ciphersuite,
24};
25use multiexp::{multiexp_vartime, BatchVerifier};
26
27#[cfg(feature = "mpc")]
28mod mpc;
29
30#[cfg(test)]
31mod tests;
32
33/// A Generalized Schnorr Proof.
34#[derive(Clone, PartialEq, Eq, Debug, Zeroize)]
35pub struct GeneralizedSchnorr<
36  C: Ciphersuite,
37  const OUTPUTS: usize,
38  const SCALARS: usize,
39  const SCALARS_PLUS_TWO: usize,
40> {
41  pub R: [C::G; OUTPUTS],
42  pub s: [C::F; SCALARS],
43}
44
45impl<C: Ciphersuite, const OUTPUTS: usize, const SCALARS: usize, const SCALARS_PLUS_TWO: usize>
46  GeneralizedSchnorr<C, OUTPUTS, SCALARS, SCALARS_PLUS_TWO>
47{
48  /// Read a GeneralizedSchnorr from something implementing Read.
49  pub fn read<R: Read>(reader: &mut R) -> io::Result<Self> {
50    let mut R = [C::G::identity(); OUTPUTS];
51    for R in &mut R {
52      *R = C::read_G(reader)?;
53    }
54    let mut s = [C::F::ZERO; SCALARS];
55    for s in &mut s {
56      *s = C::read_F(reader)?;
57    }
58    Ok(Self { R, s })
59  }
60
61  /// Write a GeneralizedSchnorr to something implementing Read.
62  pub fn write<W: Write>(&self, writer: &mut W) -> io::Result<()> {
63    for R in self.R {
64      writer.write_all(R.to_bytes().as_ref())?;
65    }
66    for s in self.s {
67      writer.write_all(s.to_repr().as_ref())?;
68    }
69    Ok(())
70  }
71
72  fn challenge(context: [u8; 32], outputs: [C::G; OUTPUTS], nonces: [C::G; OUTPUTS]) -> C::F {
73    // This doesn't transcript the matrix as that's assumed deterministic to the context (as
74    // documented)
75    let mut hasher = Blake2b512::new();
76    hasher.update(context);
77    for output in outputs {
78      hasher.update(output.to_bytes());
79    }
80    for nonce in nonces {
81      hasher.update(nonce.to_bytes());
82    }
83
84    // Ensure this field is small enough this is a successful wide reduction
85    assert!(C::F::NUM_BITS <= (512 - 128));
86
87    let mut res = C::F::ZERO;
88    for (i, mut byte) in hasher.finalize().into_iter().enumerate() {
89      for j in 0 .. 8 {
90        let lsb = byte & 1;
91        let mut bit = C::F::from(u64::from(lsb));
92        for _ in 0 .. ((i * 8) + j) {
93          bit = bit.double();
94        }
95        res += bit;
96
97        byte >>= 1;
98      }
99    }
100
101    // Negligible probability
102    if bool::from(res.is_zero()) {
103      panic!("zero challenge");
104    }
105
106    res
107  }
108
109  /// Serialize a GeneralizedSchnorr, returning a `Vec<u8>`.
110  #[cfg(feature = "std")]
111  pub fn serialize(&self) -> Vec<u8> {
112    let mut buf = vec![];
113    self.write(&mut buf).unwrap();
114    buf
115  }
116
117  /// Prove a Generalized Schnorr statement.
118  ///
119  /// The matrix is assumed to be transcribed within the context.
120  ///
121  /// Returns the outputs and the proof for them.
122  pub fn prove(
123    rng: &mut (impl RngCore + CryptoRng),
124    context: [u8; 32],
125    matrix: [[C::G; SCALARS]; OUTPUTS],
126    scalars: [&Zeroizing<C::F>; SCALARS],
127  ) -> ([C::G; OUTPUTS], Self) {
128    let outputs: [C::G; OUTPUTS] = core::array::from_fn(|i| {
129      matrix[i].iter().zip(scalars.iter()).map(|(generator, scalar)| *generator * ***scalar).sum()
130    });
131
132    let nonces: [Zeroizing<C::F>; SCALARS] =
133      core::array::from_fn(|_| Zeroizing::new(C::F::random(&mut *rng)));
134    let R = core::array::from_fn(|i| {
135      matrix[i].iter().zip(nonces.iter()).map(|(generator, nonce)| *generator * **nonce).sum()
136    });
137
138    let c = Self::challenge(context, outputs, R);
139    (outputs, Self { R, s: core::array::from_fn(|i| (c * scalars[i].deref()) + nonces[i].deref()) })
140  }
141
142  /// Return the series of pairs whose products sum to zero for a valid signature.
143  ///
144  /// This is intended to be used with a multiexp for efficient batch verification.
145  fn batch_statements(
146    &self,
147    context: [u8; 32],
148    matrix: [[C::G; SCALARS]; OUTPUTS],
149    outputs: [C::G; OUTPUTS],
150  ) -> [[(C::F, C::G); SCALARS_PLUS_TWO]; OUTPUTS] {
151    assert_eq!(SCALARS_PLUS_TWO, SCALARS + 2);
152    let c = Self::challenge(context, outputs, self.R);
153    core::array::from_fn(|i| {
154      core::array::from_fn(|j| {
155        if j == SCALARS {
156          (-C::F::ONE, self.R[i])
157        } else if j == (SCALARS + 1) {
158          (-c, outputs[i])
159        } else {
160          (self.s[j], matrix[i][j])
161        }
162      })
163    })
164  }
165
166  /// Verify a Generalized Schnorr proof.
167  ///
168  /// The matrix is assumed to be transcribed within the context.
169  #[must_use]
170  pub fn verify(
171    &self,
172    context: [u8; 32],
173    matrix: [[C::G; SCALARS]; OUTPUTS],
174    outputs: [C::G; OUTPUTS],
175  ) -> bool {
176    for statements in self.batch_statements(context, matrix, outputs) {
177      if !bool::from(multiexp_vartime(statements.as_slice()).is_identity()) {
178        return false;
179      }
180    }
181    true
182  }
183
184  /// Queue a proof for batch verification.
185  ///
186  /// The matrix is assumed to be transcribed within the context.
187  pub fn batch_verify<R: RngCore + CryptoRng, I: Copy + Zeroize>(
188    &self,
189    rng: &mut R,
190    batch: &mut BatchVerifier<I, C::G>,
191    id: I,
192    context: [u8; 32],
193    matrix: [[C::G; SCALARS]; OUTPUTS],
194    outputs: [C::G; OUTPUTS],
195  ) {
196    for statements in self.batch_statements(context, matrix, outputs) {
197      batch.queue(rng, id, statements);
198    }
199  }
200}
generalized_schnorr/lib.rs

generalized_schnorr/
lib.rs
