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