sigma_rs/
schnorr_protocol.rs

1//! Implementation of the generic Schnorr Sigma Protocol over a [`Group`].
2//!
3//! This module defines the [`SchnorrProof`] structure, which implements
4//! a Sigma protocol proving different types of discrete logarithm relations (eg. Schnorr, Pedersen's commitments)
5//! through a group morphism abstraction (see [Maurer09](https://crypto-test.ethz.ch/publications/files/Maurer09.pdf)).
6
7use crate::errors::Error;
8use crate::linear_relation::LinearRelation;
9use crate::{
10    serialization::{
11        deserialize_elements, deserialize_scalars, serialize_elements, serialize_scalars,
12    },
13    traits::{SigmaProtocol, SigmaProtocolSimulator},
14};
15
16use ff::Field;
17use group::{Group, GroupEncoding};
18use rand::{CryptoRng, Rng, RngCore};
19
20/// A Schnorr protocol proving knowledge of a witness for a linear group relation.
21///
22/// This implementation generalizes Schnorr’s discrete logarithm proof by using
23/// a [`LinearRelation`], representing an abstract linear relation over the group.
24///
25/// # Type Parameters
26/// - `G`: A cryptographic group implementing [`Group`] and [`GroupEncoding`].
27#[derive(Clone, Default, Debug)]
28pub struct SchnorrProof<G: Group + GroupEncoding>(pub LinearRelation<G>);
29
30impl<G: Group + GroupEncoding> SchnorrProof<G> {
31    pub fn witness_length(&self) -> usize {
32        self.0.linear_map.num_scalars
33    }
34
35    pub fn commitment_length(&self) -> usize {
36        self.0.linear_map.num_constraints()
37    }
38}
39
40impl<G> From<LinearRelation<G>> for SchnorrProof<G>
41where
42    G: Group + GroupEncoding,
43{
44    fn from(value: LinearRelation<G>) -> Self {
45        Self(value)
46    }
47}
48
49impl<G> SigmaProtocol for SchnorrProof<G>
50where
51    G: Group + GroupEncoding,
52{
53    type Commitment = Vec<G>;
54    type ProverState = (Vec<<G as Group>::Scalar>, Vec<<G as Group>::Scalar>);
55    type Response = Vec<<G as Group>::Scalar>;
56    type Witness = Vec<<G as Group>::Scalar>;
57    type Challenge = <G as Group>::Scalar;
58
59    /// Prover's first message: generates a commitment using random nonces.
60    ///
61    /// # Parameters
62    /// - `witness`: A vector of scalars that satisfy the linear map relation.
63    /// - `rng`: A cryptographically secure random number generator.
64    ///
65    /// # Returns
66    /// - A tuple containing:
67    ///     - The commitment (a vector of group elements).
68    ///     - The prover state (random nonces and witness) used to compute the response.
69    ///
70    /// # Errors
71    /// -[`Error::InvalidInstanceWitnessPair`] if the witness vector length is incorrect.
72    fn prover_commit(
73        &self,
74        witness: &Self::Witness,
75        mut rng: &mut (impl RngCore + CryptoRng),
76    ) -> Result<(Self::Commitment, Self::ProverState), Error> {
77        if witness.len() != self.witness_length() {
78            return Err(Error::InvalidInstanceWitnessPair);
79        }
80
81        // If the relation being proven is trivial, refuse to prove the statement.
82        if self.0.image()?.iter().all(|&x| x == G::identity()) {
83            return Err(Error::InvalidInstanceWitnessPair);
84        }
85
86        let nonces: Vec<G::Scalar> = (0..self.witness_length())
87            .map(|_| G::Scalar::random(&mut rng))
88            .collect();
89        let commitment = self.0.linear_map.evaluate(&nonces)?;
90        let prover_state = (nonces, witness.clone());
91        Ok((commitment, prover_state))
92    }
93
94    /// Computes the prover's response (second message) using the challenge.
95    ///
96    /// # Parameters
97    /// - `state`: The prover state returned by `prover_commit`, typically containing randomness and witness components.
98    /// - `challenge`: The verifier's challenge scalar.
99    ///
100    /// # Returns
101    /// - A vector of scalars forming the prover's response.
102    ///
103    /// # Errors
104    /// - Returns [`Error::InvalidInstanceWitnessPair`] if the prover state vectors have incorrect lengths.
105    fn prover_response(
106        &self,
107        prover_state: Self::ProverState,
108        challenge: &Self::Challenge,
109    ) -> Result<Self::Response, Error> {
110        let (nonces, witness) = prover_state;
111
112        if nonces.len() != self.witness_length() || witness.len() != self.witness_length() {
113            return Err(Error::InvalidInstanceWitnessPair);
114        }
115
116        let responses = nonces
117            .into_iter()
118            .zip(witness)
119            .map(|(r, w)| r + w * challenge)
120            .collect();
121        Ok(responses)
122    }
123    /// Verifies the correctness of the proof.
124    ///
125    /// # Parameters
126    /// - `commitment`: The prover's commitment vector (group elements).
127    /// - `challenge`: The challenge scalar.
128    /// - `response`: The prover's response vector.
129    ///
130    /// # Returns
131    /// - `Ok(())` if the proof is valid.
132    /// - `Err(Error::VerificationFailure)` if the proof is invalid.
133    /// - `Err(Error::InvalidInstanceWitnessPair)` if the lengths of commitment or response do not match the expected counts.
134    ///
135    /// # Errors
136    /// -[`Error::VerificationFailure`] if the computed relation
137    /// does not hold for the provided challenge and response, indicating proof invalidity.
138    /// -[`Error::InvalidInstanceWitnessPair`] if the commitment or response length is incorrect.
139    fn verifier(
140        &self,
141        commitment: &Self::Commitment,
142        challenge: &Self::Challenge,
143        response: &Self::Response,
144    ) -> Result<(), Error> {
145        if commitment.len() != self.commitment_length() || response.len() != self.witness_length() {
146            return Err(Error::InvalidInstanceWitnessPair);
147        }
148
149        let lhs = self.0.linear_map.evaluate(response)?;
150        let mut rhs = Vec::new();
151        for (i, g) in commitment.iter().enumerate() {
152            rhs.push({
153                let image_var = self.0.image[i];
154                self.0.linear_map.group_elements.get(image_var)? * challenge + g
155            });
156        }
157        if lhs == rhs {
158            Ok(())
159        } else {
160            Err(Error::VerificationFailure)
161        }
162    }
163
164    /// Serializes the prover's commitment into a byte vector.
165    ///
166    /// This function encodes the vector of group elements (the commitment)
167    /// into a binary format suitable for transmission or storage. This is
168    /// typically the first message sent in a Sigma protocol round.
169    ///
170    /// # Parameters
171    /// - `commitment`: A vector of group elements representing the prover's commitment.
172    ///
173    /// # Returns
174    /// A `Vec<u8>` containing the serialized group elements.
175    fn serialize_commitment(&self, commitment: &Self::Commitment) -> Vec<u8> {
176        serialize_elements(commitment)
177    }
178
179    /// Serializes the verifier's challenge scalar into bytes.
180    ///
181    /// Converts the challenge scalar into a fixed-length byte encoding. This can be used
182    /// for Fiat–Shamir hashing, transcript recording, or proof transmission.
183    ///
184    /// # Parameters
185    /// - `challenge`: The scalar challenge value.
186    ///
187    /// # Returns
188    /// A `Vec<u8>` containing the serialized scalar.
189    fn serialize_challenge(&self, challenge: &Self::Challenge) -> Vec<u8> {
190        serialize_scalars::<G>(&[*challenge])
191    }
192
193    /// Serializes the prover's response vector into a byte format.
194    ///
195    /// The response is a vector of scalars computed by the prover after receiving
196    /// the verifier's challenge. This function encodes the vector into a format
197    /// suitable for transmission or inclusion in a batchable proof.
198    ///
199    /// # Parameters
200    /// - `response`: A vector of scalar responses computed by the prover.
201    ///
202    /// # Returns
203    /// A `Vec<u8>` containing the serialized scalars.
204    fn serialize_response(&self, response: &Self::Response) -> Vec<u8> {
205        serialize_scalars::<G>(response)
206    }
207
208    /// Deserializes a byte slice into a vector of group elements (commitment).
209    ///
210    /// This function reconstructs the prover’s commitment from its binary representation.
211    /// The number of elements expected is determined by the number of linear constraints
212    /// in the underlying linear relation.
213    ///
214    /// # Parameters
215    /// - `data`: A byte slice containing the serialized commitment.
216    ///
217    /// # Returns
218    /// A `Vec<G>` containing the deserialized group elements.
219    ///
220    /// # Errors
221    /// - Returns [`Error::VerificationFailure`] if the data is malformed or contains an invalid encoding.
222    fn deserialize_commitment(&self, data: &[u8]) -> Result<Self::Commitment, Error> {
223        deserialize_elements::<G>(data, self.commitment_length()).ok_or(Error::VerificationFailure)
224    }
225
226    /// Deserializes a byte slice into a challenge scalar.
227    ///
228    /// This function expects a single scalar to be encoded and returns it as the verifier's challenge.
229    ///
230    /// # Parameters
231    /// - `data`: A byte slice containing the serialized scalar challenge.
232    ///
233    /// # Returns
234    /// The deserialized scalar challenge value.
235    ///
236    /// # Errors
237    /// - Returns [`Error::VerificationFailure`] if deserialization fails or data is invalid.
238    fn deserialize_challenge(&self, data: &[u8]) -> Result<Self::Challenge, Error> {
239        let scalars = deserialize_scalars::<G>(data, 1).ok_or(Error::VerificationFailure)?;
240        Ok(scalars[0])
241    }
242
243    /// Deserializes a byte slice into the prover's response vector.
244    ///
245    /// The response vector contains scalars used in the second round of the Sigma protocol.
246    /// The expected number of scalars matches the number of witness variables.
247    ///
248    /// # Parameters
249    /// - `data`: A byte slice containing the serialized response.
250    ///
251    /// # Returns
252    /// A vector of deserialized scalars.
253    ///
254    /// # Errors
255    /// - Returns [`Error::VerificationFailure`] if the byte data is malformed or the length is incorrect.
256    fn deserialize_response(&self, data: &[u8]) -> Result<Self::Response, Error> {
257        deserialize_scalars::<G>(data, self.witness_length()).ok_or(Error::VerificationFailure)
258    }
259
260    fn instance_label(&self) -> impl AsRef<[u8]> {
261        self.0.label()
262    }
263
264    fn protocol_identifier(&self) -> impl AsRef<[u8]> {
265        b"SchnorrProof"
266    }
267}
268
269impl<G> SigmaProtocolSimulator for SchnorrProof<G>
270where
271    G: Group + GroupEncoding,
272{
273    /// Simulates a valid transcript for a given challenge without a witness.
274    ///
275    /// # Parameters
276    /// - `challenge`: A scalar value representing the challenge.
277    /// - `rng`: A cryptographically secure RNG.
278    ///
279    /// # Returns
280    /// - A commitment and response forming a valid proof for the given challenge.
281    fn simulate_response<R: Rng + CryptoRng>(&self, mut rng: &mut R) -> Self::Response {
282        let response: Vec<G::Scalar> = (0..self.witness_length())
283            .map(|_| G::Scalar::random(&mut rng))
284            .collect();
285        response
286    }
287
288    /// Simulates a full proof transcript using a randomly generated challenge.
289    ///
290    /// # Parameters
291    /// - `rng`: A cryptographically secure RNG.
292    ///
293    /// # Returns
294    /// - A tuple `(commitment, challenge, response)` forming a valid proof.
295    fn simulate_transcript<R: Rng + CryptoRng>(
296        &self,
297        rng: &mut R,
298    ) -> Result<(Self::Commitment, Self::Challenge, Self::Response), Error> {
299        let challenge = G::Scalar::random(&mut *rng);
300        let response = self.simulate_response(&mut *rng);
301        let commitment = self.simulate_commitment(&challenge, &response)?;
302        Ok((commitment, challenge, response))
303    }
304
305    /// Recomputes the commitment from the challenge and response (used in compact proofs).
306    ///
307    /// # Parameters
308    /// - `challenge`: The challenge scalar issued by the verifier or derived via Fiat–Shamir.
309    /// - `response`: The prover's response vector.
310    ///
311    /// # Returns
312    /// - A vector of group elements representing the simulated commitment (one per linear constraint).
313    ///
314    /// # Errors
315    /// - [`Error::InvalidInstanceWitnessPair`] if the response length does not match the expected number of scalars.
316    fn simulate_commitment(
317        &self,
318        challenge: &Self::Challenge,
319        response: &Self::Response,
320    ) -> Result<Self::Commitment, Error> {
321        if response.len() != self.witness_length() {
322            return Err(Error::InvalidInstanceWitnessPair);
323        }
324
325        let response_image = self.0.linear_map.evaluate(response)?;
326        let image = self.0.image()?;
327
328        let commitment = response_image
329            .iter()
330            .zip(&image)
331            .map(|(res, img)| *res - *img * challenge)
332            .collect::<Vec<_>>();
333        Ok(commitment)
334    }
335}
sigma_rs/schnorr_protocol.rs

sigma_rs/
schnorr_protocol.rs
