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