mmr_crypto_primitives/signature/schnorr/
mod.rs

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

mmr_crypto_primitives/signature/schnorr/
mod.rs
