sigma_proofs/
schnorr_protocol.rs

1//! Implementation of the generic Schnorr Sigma Protocol over a [`group::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, Result};
8use crate::linear_relation::CanonicalLinearRelation;
9use crate::traits::{ScalarRng, SigmaProtocol, SigmaProtocolSimulator, Transcript};
10use crate::{LinearRelation, MultiScalarMul, Nizk};
11use alloc::vec::Vec;
12
13use group::prime::PrimeGroup;
14use spongefish::{Decoding, Encoding, NargDeserialize, NargSerialize};
15
16impl<G> SigmaProtocol for CanonicalLinearRelation<G>
17where
18    G: PrimeGroup + Encoding<[u8]> + NargSerialize + NargDeserialize + MultiScalarMul,
19    G::Scalar: Encoding<[u8]> + NargSerialize + NargDeserialize + Decoding<[u8]>,
20{
21    type Commitment = G;
22    type ProverState = (Vec<G::Scalar>, Vec<G::Scalar>);
23    type Response = G::Scalar;
24    type Witness = Vec<G::Scalar>;
25    type Challenge = G::Scalar;
26
27    /// Prover's first message: generates a commitment using random nonces.
28    ///
29    /// # Parameters
30    /// - `witness`: A vector of scalars that satisfy the linear map relation.
31    /// - `rng`: A cryptographically secure random number generator.
32    ///
33    /// # Returns
34    /// - A tuple containing:
35    ///     - The commitment (a vector of group elements).
36    ///     - The prover state (random nonces and witness) used to compute the response.
37    ///
38    /// # Errors
39    ///
40    /// -[`Error::InvalidInstanceWitnessPair`] if the witness vector length is less than the number of scalar variables.
41    /// If the witness vector is larger, extra variables are ignored.
42    fn prover_commit(
43        &self,
44        witness: &Self::Witness,
45        rng: &mut impl ScalarRng,
46    ) -> Result<(Vec<Self::Commitment>, Self::ProverState)> {
47        if witness.len() < self.num_scalars {
48            return Err(Error::InvalidInstanceWitnessPair);
49        }
50
51        let nonces = rng.random_scalars_vec::<G>(self.num_scalars);
52        let commitment = self.evaluate(&nonces);
53        let prover_state = (nonces.to_vec(), witness.to_vec());
54        Ok((commitment, prover_state))
55    }
56
57    /// Computes the prover's response (second message) using the challenge.
58    ///
59    /// # Parameters
60    /// - `state`: The prover state returned by `prover_commit`, typically containing randomness and witness components.
61    /// - `challenge`: The verifier's challenge scalar.
62    ///
63    /// # Returns
64    /// - A vector of scalars forming the prover's response.
65    ///
66    /// # Errors
67    /// - Returns [`Error::InvalidInstanceWitnessPair`] if the prover state vectors have incorrect lengths.
68    fn prover_response(
69        &self,
70        prover_state: Self::ProverState,
71        challenge: &Self::Challenge,
72    ) -> Result<Vec<Self::Response>> {
73        let (nonces, witness) = prover_state;
74
75        let responses = nonces
76            .into_iter()
77            .zip(witness)
78            .map(|(r, w)| r + w * challenge)
79            .collect();
80        Ok(responses)
81    }
82    /// Verifies the correctness of the proof.
83    ///
84    /// # Parameters
85    /// - `commitment`: The prover's commitment vector (group elements).
86    /// - `challenge`: The challenge scalar.
87    /// - `response`: The prover's response vector.
88    ///
89    /// # Returns
90    /// - `Ok(())` if the proof is valid.
91    /// - `Err(Error::VerificationFailure)` if the proof is invalid.
92    /// - `Err(Error::InvalidInstanceWitnessPair)` if the lengths of commitment or response do not match the expected counts.
93    ///
94    /// # Errors
95    /// -[`Error::VerificationFailure`] if the computed relation
96    /// does not hold for the provided challenge and response, indicating proof invalidity.
97    /// -[`Error::InvalidInstanceWitnessPair`] if the commitment or response length is incorrect.
98    fn verifier(
99        &self,
100        commitment: &[Self::Commitment],
101        challenge: &Self::Challenge,
102        response: &[Self::Response],
103    ) -> Result<()> {
104        if commitment.len() != self.image.len() || response.len() != self.num_scalars {
105            return Err(Error::InvalidInstanceWitnessPair);
106        }
107
108        let lhs = self.evaluate(response);
109        let mut rhs = Vec::new();
110        for (img, g) in self.image_elements().zip(commitment) {
111            rhs.push(img * challenge + g);
112        }
113        if lhs == rhs {
114            Ok(())
115        } else {
116            Err(Error::VerificationFailure)
117        }
118    }
119    fn commitment_len(&self) -> usize {
120        self.image.len()
121    }
122
123    fn response_len(&self) -> usize {
124        self.num_scalars
125    }
126
127    fn instance_label(&self) -> impl AsRef<[u8]> {
128        self.label()
129    }
130
131    fn protocol_identifier(&self) -> [u8; 64] {
132        let mut id = [0u8; 64];
133        id[..32].clone_from_slice(b"ietf sigma proof linear relation");
134        id
135    }
136}
137
138impl<G> CanonicalLinearRelation<G>
139where
140    G: PrimeGroup + Encoding<[u8]> + NargSerialize + NargDeserialize + MultiScalarMul,
141    G::Scalar: Encoding<[u8]> + NargSerialize + NargDeserialize + Decoding<[u8]>,
142{
143    /// Convert this LinearRelation into a non-interactive zero-knowledge protocol
144    /// using the ShakeCodec and a specified context/domain separator.
145    ///
146    /// # Parameters
147    /// - `context`: Domain separator bytes for the Fiat-Shamir transform
148    ///
149    /// # Returns
150    /// A `Nizk` instance ready for proving and verification
151    ///
152    /// # Example
153    /// ```
154    /// # #[cfg(feature = "curve25519-dalek")] {
155    /// # use sigma_proofs::{LinearRelation, Nizk};
156    /// # use curve25519_dalek::RistrettoPoint as G;
157    /// # use curve25519_dalek::scalar::Scalar;
158    /// # use rand::rngs::OsRng;
159    /// # use group::Group;
160    ///
161    /// let mut relation = LinearRelation::<G>::new();
162    /// let x_var = relation.allocate_scalar();
163    /// let g_var = relation.allocate_element();
164    /// let p_var = relation.allocate_eq(x_var * g_var);
165    ///
166    /// relation.set_element(g_var, G::generator());
167    /// let x = Scalar::random(&mut OsRng);
168    /// relation.compute_image(&[x]).unwrap();
169    ///
170    /// // Convert to NIZK with custom context
171    /// let nizk = relation.into_nizk(b"my-protocol-v1").unwrap();
172    /// let proof = nizk.prove_batchable(&vec![x], &mut OsRng).unwrap();
173    /// assert!(nizk.verify_batchable(&proof).is_ok());
174    /// # }
175    /// ```
176    pub fn into_nizk(self, session_identifier: &[u8]) -> Result<Nizk<CanonicalLinearRelation<G>>> {
177        Ok(Nizk::new(session_identifier, self))
178    }
179}
180
181impl<G> LinearRelation<G>
182where
183    G: PrimeGroup + Encoding<[u8]> + NargSerialize + NargDeserialize + MultiScalarMul,
184    G::Scalar: Encoding<[u8]> + NargSerialize + NargDeserialize + Decoding<[u8]>,
185{
186    /// Convert this LinearRelation into a non-interactive zero-knowledge protocol
187    /// using the Fiat-Shamir transform.
188    ///
189    /// This is a convenience method that combines `.canonical()` and `.into_nizk()`.
190    ///
191    /// # Parameters
192    /// - `session_identifier`: Domain separator bytes for the Fiat-Shamir transform
193    ///
194    /// # Returns
195    /// A `Nizk` instance ready for proving and verification
196    ///
197    /// # Example
198    /// ```
199    /// # #[cfg(feature = "curve25519-dalek")] {
200    /// # use sigma_proofs::{LinearRelation, Nizk};
201    /// # use curve25519_dalek::RistrettoPoint as G;
202    /// # use curve25519_dalek::scalar::Scalar;
203    /// # use rand::rngs::OsRng;
204    /// # use group::Group;
205    ///
206    /// let mut relation = LinearRelation::<G>::new();
207    /// let x_var = relation.allocate_scalar();
208    /// let g_var = relation.allocate_element();
209    /// let p_var = relation.allocate_eq(x_var * g_var);
210    ///
211    /// relation.set_element(g_var, G::generator());
212    /// let x = Scalar::random(&mut OsRng);
213    /// relation.compute_image(&[x]).unwrap();
214    ///
215    /// // Convert to NIZK directly
216    /// let nizk = relation.into_nizk(b"my-protocol-v1").unwrap();
217    /// let proof = nizk.prove_batchable(&vec![x], &mut OsRng).unwrap();
218    /// assert!(nizk.verify_batchable(&proof).is_ok());
219    /// # }
220    /// ```
221    pub fn into_nizk(
222        self,
223        session_identifier: &[u8],
224    ) -> crate::errors::Result<crate::Nizk<CanonicalLinearRelation<G>>>
225    where
226        G: PrimeGroup + Encoding<[u8]> + NargSerialize + NargDeserialize,
227        G::Scalar: Encoding<[u8]> + NargSerialize + NargDeserialize + Decoding<[u8]>,
228    {
229        self.canonical()
230            .map_err(|_| crate::errors::Error::InvalidInstanceWitnessPair)?
231            .into_nizk(session_identifier)
232    }
233}
234impl<G> SigmaProtocolSimulator for CanonicalLinearRelation<G>
235where
236    G: PrimeGroup + Encoding<[u8]> + NargSerialize + NargDeserialize + MultiScalarMul,
237    G::Scalar: Encoding<[u8]> + NargSerialize + NargDeserialize + Decoding<[u8]>,
238{
239    /// Simulates a valid transcript for a given challenge without a witness.
240    ///
241    /// # Parameters
242    /// - `challenge`: A scalar value representing the challenge.
243    /// - `rng`: A cryptographically secure RNG.
244    ///
245    /// # Returns
246    /// - A commitment and response forming a valid proof for the given challenge.
247    fn simulate_response(&self, rng: &mut impl ScalarRng) -> Vec<Self::Response> {
248        rng.random_scalars_vec::<G>(self.num_scalars)
249    }
250
251    /// Simulates a full proof transcript using a randomly generated challenge.
252    ///
253    /// # Parameters
254    /// - `rng`: A cryptographically secure RNG.
255    ///
256    /// # Returns
257    /// - A tuple `(commitment, challenge, response)` forming a valid proof.
258    fn simulate_transcript(&self, rng: &mut impl ScalarRng) -> Result<Transcript<Self>> {
259        let [challenge] = rng.random_scalars::<G, _>();
260        let response = self.simulate_response(rng);
261        let commitment = self.simulate_commitment(&challenge, &response)?;
262        Ok((commitment, challenge, response))
263    }
264
265    /// Recomputes the commitment from the challenge and response (used in compact proofs).
266    ///
267    /// # Parameters
268    /// - `challenge`: The challenge scalar issued by the verifier or derived via Fiat–Shamir.
269    /// - `response`: The prover's response vector.
270    ///
271    /// # Returns
272    /// - A vector of group elements representing the simulated commitment (one per linear constraint).
273    ///
274    /// # Errors
275    /// - [`Error::InvalidInstanceWitnessPair`] if the response length does not match the expected number of scalars.
276    fn simulate_commitment(
277        &self,
278        challenge: &Self::Challenge,
279        response: &[Self::Response],
280    ) -> Result<Vec<Self::Commitment>> {
281        if response.len() != self.num_scalars {
282            return Err(Error::InvalidInstanceWitnessPair);
283        }
284
285        let response_image = self.evaluate(response);
286        let commitment = response_image
287            .iter()
288            .zip(self.image_elements())
289            .map(|(res, img)| *res - img * challenge)
290            .collect::<Vec<_>>();
291        Ok(commitment)
292    }
293}
sigma_proofs/schnorr_protocol.rs

sigma_proofs/
schnorr_protocol.rs
