1use crate::SignatureScheme;
  2use algebra::{
  3    ToConstraintField,
  4    bytes::ToBytes,
  5    fields::{Field, PrimeField},
  6    groups::Group,
  7    to_bytes,
  8};
  9use digest::Digest;
 10use crate::Error;
 11use algebra::UniformRand;
 12use rand::Rng;
 13use std::{
 14    hash::Hash,
 15    io::{Result as IoResult, Write},
 16    marker::PhantomData,
 17};
 18
 19#[cfg(feature = "r1cs")]
 20pub mod constraints;
 21
 22pub struct SchnorrSignature<G: Group, D: Digest> {
 23    _group: PhantomData<G>,
 24    _hash:  PhantomData<D>,
 25}
 26
 27#[derive(Derivative)]
 28#[derivative(Clone(bound = "G: Group, H: Digest"))]
 29pub struct SchnorrSigParameters<G: Group, H: Digest> {
 30    _hash:         PhantomData<H>,
 31    pub generator: G,
 32    pub salt:      [u8; 32],
 33}
 34
 35pub type SchnorrPublicKey<G> = G;
 36
 37#[derive(Derivative)]
 38#[derivative(Clone(bound = "G: Group"), Default(bound = "G: Group"))]
 39pub struct SchnorrSecretKey<G: Group>(pub G::ScalarField);
 40
 41impl<G: Group> ToBytes for SchnorrSecretKey<G> {
 42    #[inline]
 43    fn write<W: Write>(&self, writer: W) -> IoResult<()> {
 44        self.0.write(writer)
 45    }
 46}
 47
 48#[derive(Derivative)]
 49#[derivative(Clone(bound = "G: Group"), Default(bound = "G: Group"))]
 50pub struct SchnorrSig<G: Group> {
 51    pub prover_response:    G::ScalarField,
 52    pub verifier_challenge: G::ScalarField,
 53}
 54
 55impl<G: Group + Hash, D: Digest + Send + Sync> SignatureScheme for SchnorrSignature<G, D>
 56where
 57    G::ScalarField: PrimeField,
 58{
 59    type Parameters = SchnorrSigParameters<G, D>;
 60    type PublicKey = G;
 61    type SecretKey = SchnorrSecretKey<G>;
 62    type Signature = SchnorrSig<G>;
 63
 64    fn setup<R: Rng>(rng: &mut R) -> Result<Self::Parameters, Error> {
 65        let setup_time = start_timer!(|| "SchnorrSig::Setup");
 66
 67        let mut salt = [0u8; 32];
 68        rng.fill_bytes(&mut salt);
 69        let generator = G::rand(rng);
 70
 71        end_timer!(setup_time);
 72        Ok(SchnorrSigParameters {
 73            _hash: PhantomData,
 74            generator,
 75            salt,
 76        })
 77    }
 78
 79    fn keygen<R: Rng>(
 80        parameters: &Self::Parameters,
 81        rng: &mut R,
 82    ) -> Result<(Self::PublicKey, Self::SecretKey), Error> {
 83        let keygen_time = start_timer!(|| "SchnorrSig::KeyGen");
 84
 85        let secret_key = G::ScalarField::rand(rng);
 86        let public_key = parameters.generator.mul(&secret_key);
 87
 88        end_timer!(keygen_time);
 89        Ok((public_key, SchnorrSecretKey(secret_key)))
 90    }
 91
 92    fn sign<R: Rng>(
 93        parameters: &Self::Parameters,
 94        sk: &Self::SecretKey,
 95        message: &[u8],
 96        rng: &mut R,
 97    ) -> Result<Self::Signature, Error> {
 98        let sign_time = start_timer!(|| "SchnorrSig::Sign");
 99        // (k, e);
100        let (random_scalar, verifier_challenge) = loop {
101            // Sample a random scalar `k` from the prime scalar field.
102            let random_scalar: G::ScalarField = G::ScalarField::rand(rng);
103            // Commit to the random scalar via r := k · g.
104            // This is the prover's first msg in the Sigma protocol.
105            let prover_commitment: G = parameters.generator.mul(&random_scalar);
106
107            // Hash everything to get verifier challenge.
108            let mut hash_input = Vec::new();
109            hash_input.extend_from_slice(&parameters.salt);
110            hash_input.extend_from_slice(&to_bytes![prover_commitment]?);
111            hash_input.extend_from_slice(message);
112
113            // Compute the supposed verifier response: e := H(salt || r || msg);
114            if let Some(verifier_challenge) =
115                G::ScalarField::from_random_bytes(&D::digest(&hash_input))
116            {
117                break (random_scalar, verifier_challenge);
118            };
119        };
120
121        // k - xe;
122        let prover_response = random_scalar - &(verifier_challenge * &sk.0);
123        let signature = SchnorrSig {
124            prover_response,
125            verifier_challenge,
126        };
127
128        end_timer!(sign_time);
129        Ok(signature)
130    }
131
132    fn verify(
133        parameters: &Self::Parameters,
134        pk: &Self::PublicKey,
135        message: &[u8],
136        signature: &Self::Signature,
137    ) -> Result<bool, Error> {
138        let verify_time = start_timer!(|| "SchnorrSig::Verify");
139
140        let SchnorrSig {
141            prover_response,
142            verifier_challenge,
143        } = signature;
144        let mut claimed_prover_commitment = parameters.generator.mul(prover_response);
145        let public_key_times_verifier_challenge = pk.mul(verifier_challenge);
146        claimed_prover_commitment += &public_key_times_verifier_challenge;
147
148        let mut hash_input = Vec::new();
149        hash_input.extend_from_slice(&parameters.salt);
150        hash_input.extend_from_slice(&to_bytes![claimed_prover_commitment]?);
151        hash_input.extend_from_slice(&message);
152
153        let obtained_verifier_challenge = if let Some(obtained_verifier_challenge) =
154            G::ScalarField::from_random_bytes(&D::digest(&hash_input))
155        {
156            obtained_verifier_challenge
157        } else {
158            return Ok(false);
159        };
160        end_timer!(verify_time);
161        Ok(verifier_challenge == &obtained_verifier_challenge)
162    }
163
164    fn randomize_public_key(
165        parameters: &Self::Parameters,
166        public_key: &Self::PublicKey,
167        randomness: &[u8],
168    ) -> Result<Self::PublicKey, Error> {
169        let rand_pk_time = start_timer!(|| "SchnorrSig::RandomizePubKey");
170
171        let mut randomized_pk = *public_key;
172        let mut base = parameters.generator;
173        let mut encoded = G::zero();
174        for bit in bytes_to_bits(randomness) {
175            if bit {
176                encoded += &base;
177            }
178            base.double_in_place();
179        }
180        randomized_pk += &encoded;
181
182        end_timer!(rand_pk_time);
183
184        Ok(randomized_pk)
185    }
186
187    fn randomize_signature(
188        _parameter: &Self::Parameters,
189        signature: &Self::Signature,
190        randomness: &[u8],
191    ) -> Result<Self::Signature, Error> {
192        let rand_signature_time = start_timer!(|| "SchnorrSig::RandomizeSig");
193        let SchnorrSig {
194            prover_response,
195            verifier_challenge,
196        } = signature;
197        let mut base = G::ScalarField::one();
198        let mut multiplier = G::ScalarField::zero();
199        for bit in bytes_to_bits(randomness) {
200            if bit {
201                multiplier += &base;
202            }
203            base.double_in_place();
204        }
205
206        let new_sig = SchnorrSig {
207            prover_response:    *prover_response - &(*verifier_challenge * &multiplier),
208            verifier_challenge: *verifier_challenge,
209        };
210        end_timer!(rand_signature_time);
211        Ok(new_sig)
212    }
213}
214
215pub fn bytes_to_bits(bytes: &[u8]) -> Vec<bool> {
216    let mut bits = Vec::with_capacity(bytes.len() * 8);
217    for byte in bytes {
218        for i in 0..8 {
219            let bit = (*byte >> (8 - i - 1)) & 1;
220            bits.push(bit == 1);
221        }
222    }
223    bits
224}
225
226impl<ConstraintF: Field, G: Group + ToConstraintField<ConstraintF>, D: Digest> ToConstraintField<ConstraintF>
227    for SchnorrSigParameters<G, D>
228{
229    #[inline]
230    fn to_field_elements(&self) -> Result<Vec<ConstraintF>, Error> {
231        self.generator.to_field_elements()
232    }
233}