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