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