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