sigma_proofs/
fiat_shamir.rs

1//! Fiat-Shamir transformation for [`SigmaProtocol`]s.
2//!
3//! This module defines [`Nizk`], a generic non-interactive Sigma protocol wrapper,
4//! based on applying the Fiat-Shamir heuristic using a cryptographic sponge function.
5//!
6//! It transforms an interactive [`SigmaProtocol`] into a non-interactive one,
7//! by deriving challenges deterministically from previous protocol messages.
8//!
9//! # Usage
10//! This struct is generic over:
11//! - `P`: the underlying Sigma protocol ([`SigmaProtocol`] trait).
12
13use crate::errors::Error;
14use crate::traits::ScalarRng;
15use crate::traits::SigmaProtocol;
16use crate::traits::SigmaProtocolSimulator;
17use alloc::vec::Vec;
18use sha3::digest::{ExtendableOutput, Update, XofReader};
19use spongefish::{
20    DomainSeparator, Encoding, NargDeserialize, NargSerialize, ProverState, VerifierState,
21};
22
23/// A Fiat-Shamir transformation of a [`SigmaProtocol`] into a non-interactive proof.
24///
25/// [`Nizk`] wraps an interactive Sigma protocol `P`
26/// to produce non-interactive proofs by deriving verifier challenges from a
27/// cryptographic sponge state.
28///
29/// # Type Parameters
30/// - `P`: the Sigma protocol implementation.
31#[derive(Debug)]
32pub struct Nizk<P>
33where
34    P: SigmaProtocol,
35    P::Challenge: PartialEq,
36{
37    pub session_id: Vec<u8>,
38    /// Underlying interactive proof.
39    pub interactive_proof: P,
40}
41
42impl<P> Nizk<P>
43where
44    P: SigmaProtocol,
45    P::Challenge: PartialEq,
46    P::Commitment: NargSerialize + NargDeserialize + Encoding,
47    P::Response: NargSerialize + NargDeserialize + Encoding,
48{
49    /// Constructs a new [`Nizk`] instance.
50    ///
51    /// # Parameters
52    /// - `iv`: Domain separation tag for the hash function (e.g., protocol name or context).
53    /// - `instance`: An instance of the interactive Sigma protocol.
54    ///
55    /// # Returns
56    /// A new [`Nizk`] that can generate and verify non-interactive proofs.
57    pub fn new(session_identifier: &[u8], interactive_proof: P) -> Self {
58        Self {
59            session_id: session_identifier.to_vec(),
60            interactive_proof,
61        }
62    }
63
64    /// Generates a batchable, serialized non-interactive proof.
65    ///
66    /// # Parameters
67    /// - `witness`: The secret witness.
68    /// - `rng`: A cryptographically secure random number generator.
69    ///
70    /// # Returns
71    /// A serialized proof suitable for batch verification.
72    ///
73    /// # Panics
74    /// Panics if serialization fails (should not happen under correct implementation).
75    pub fn prove_batchable(
76        &self,
77        witness: &P::Witness,
78        rng: &mut impl ScalarRng,
79    ) -> Result<Vec<u8>, Error> {
80        let protocol_id = self.interactive_proof.protocol_identifier();
81        let instance_label = self.interactive_proof.instance_label();
82        let mut transcript =
83            initialize_prover_state(protocol_id, &self.session_id, instance_label.as_ref());
84        let (commitment, ip_state) = self.interactive_proof.prover_commit(witness, rng)?;
85        let commitment_bytes = serialize_messages(&commitment);
86        transcript.public_message(commitment_bytes.as_slice());
87        let challenge = transcript.verifier_message::<P::Challenge>();
88        let response = self
89            .interactive_proof
90            .prover_response(ip_state, &challenge)?;
91        let mut proof = commitment_bytes;
92        serialize_messages_into(&response, &mut proof);
93        Ok(proof)
94    }
95
96    /// Verifies a batchable non-interactive proof.
97    ///
98    /// # Parameters
99    /// - `proof`: A serialized batchable proof.
100    ///
101    /// # Returns
102    /// - `Ok(())` if the proof is valid.
103    /// - `Err(Error)` if deserialization or verification fails.
104    ///
105    /// # Errors
106    /// - Returns [`Error::VerificationFailure`] if:
107    ///   - The challenge doesn't match the recomputed one from the commitment.
108    ///   - The response fails verification under the Sigma protocol.
109    pub fn verify_batchable(&self, narg_string: &[u8]) -> Result<(), Error> {
110        let protocol_id = self.interactive_proof.protocol_identifier();
111        let instance_label = self.interactive_proof.instance_label();
112        let commitment_len = self.interactive_proof.commitment_len();
113        let response_len = self.interactive_proof.response_len();
114        let mut transcript = initialize_verifier_state(
115            protocol_id,
116            &self.session_id,
117            instance_label.as_ref(),
118            narg_string,
119        );
120        let commitment = transcript.prover_messages_vec::<P::Commitment>(commitment_len)?;
121        let challenge = transcript.verifier_message::<P::Challenge>();
122        let response = transcript.prover_messages_vec::<P::Response>(response_len)?;
123        transcript.check_eof()?;
124        self.interactive_proof
125            .verifier(&commitment, &challenge, &response)
126    }
127}
128
129impl<P> Nizk<P>
130where
131    P: SigmaProtocol + SigmaProtocolSimulator,
132    P::Challenge: PartialEq + NargDeserialize + NargSerialize,
133{
134    /// Generates a compact serialized proof.
135    ///
136    /// Uses a more space-efficient representation compared to batchable proofs.
137    ///
138    /// # Parameters
139    /// - `witness`: The secret witness.
140    /// - `rng`: A cryptographically secure random number generator.
141    ///
142    /// # Returns
143    /// A compact, serialized proof.
144    ///
145    /// # Panics
146    /// Panics if serialization fails.
147    pub fn prove_compact(
148        &self,
149        witness: &P::Witness,
150        rng: &mut impl ScalarRng,
151    ) -> Result<Vec<u8>, Error> {
152        let protocol_id = self.interactive_proof.protocol_identifier();
153        let instance_label = self.interactive_proof.instance_label();
154        let mut transcript =
155            initialize_prover_state(protocol_id, &self.session_id, instance_label.as_ref());
156        let (commitment, ip_state) = self.interactive_proof.prover_commit(witness, rng)?;
157        let commitment_bytes = serialize_messages(&commitment);
158        transcript.public_message(commitment_bytes.as_slice());
159        let challenge = transcript.verifier_message::<P::Challenge>();
160        let response = self
161            .interactive_proof
162            .prover_response(ip_state, &challenge)?;
163
164        // Serialize the compact proof string.
165        let mut proof = Vec::new();
166        challenge.serialize_into_narg(&mut proof);
167        serialize_messages_into(&response, &mut proof);
168        Ok(proof)
169    }
170
171    /// Verifies a compact proof.
172    ///
173    /// Recomputes the commitment from the challenge and response, then verifies it.
174    ///
175    /// # Parameters
176    /// - `proof`: A compact serialized proof.
177    ///
178    /// # Returns
179    /// - `Ok(())` if the proof is valid.
180    /// - `Err(Error)` if deserialization or verification fails.
181    ///
182    /// # Errors
183    /// - Returns [`Error::VerificationFailure`] if:
184    ///   - Deserialization fails.
185    ///   - The recomputed commitment or response is invalid under the Sigma protocol.
186    pub fn verify_compact(&self, proof: &[u8]) -> Result<(), Error> {
187        // Deserialize challenge and response from compact proof
188        let mut cursor = proof;
189        let protocol_id = self.interactive_proof.protocol_identifier();
190        let instance_label = self.interactive_proof.instance_label();
191        let challenge = P::Challenge::deserialize_from_narg(&mut cursor)?;
192        let response_len = self.interactive_proof.response_len();
193        let response = deserialize_messages(response_len, &mut cursor)?;
194
195        // Proof size check
196        if !cursor.is_empty() {
197            return Err(Error::VerificationFailure);
198        }
199
200        // Compute the commitments
201        let commitment = self
202            .interactive_proof
203            .simulate_commitment(&challenge, &response)?;
204
205        // Re-compute the challenge and ensure it's the same as the one
206        // we received
207        let commitment_bytes = serialize_messages(&commitment);
208        let mut transcript =
209            initialize_verifier_state(protocol_id, &self.session_id, instance_label.as_ref(), &[]);
210        transcript.public_message(commitment_bytes.as_slice());
211        let recomputed_challenge = transcript.verifier_message::<P::Challenge>();
212        if challenge != recomputed_challenge {
213            return Err(Error::VerificationFailure);
214        }
215
216        // At this point, checking
217        // self.interactive_proof.verifier(&commitment, &challenge,
218        // &response) is redundant, because we know that commitment =
219        // simulate_commitment(challenge, response), and that challenge
220        // is the output of the appropriate hash, so the signature is
221        // valid.
222        Ok(())
223    }
224}
225
226fn initialize_prover_state(
227    protocol_id: [u8; 64],
228    session_id: &[u8],
229    instance_label: &[u8],
230) -> ProverState {
231    let instance_label = instance_label.to_vec();
232    DomainSeparator::new(protocol_id)
233        .session(derive_session_id(session_id))
234        .instance(&instance_label)
235        .std_prover()
236}
237
238fn initialize_verifier_state<'a>(
239    protocol_id: [u8; 64],
240    session_id: &[u8],
241    instance_label: &[u8],
242    narg_string: &'a [u8],
243) -> VerifierState<'a> {
244    let instance_label = instance_label.to_vec();
245    DomainSeparator::new(protocol_id)
246        .session(derive_session_id(session_id))
247        .instance(&instance_label)
248        .std_verifier(narg_string)
249}
250
251fn derive_session_id(session_id: &[u8]) -> [u8; 64] {
252    const RATE: usize = 168;
253    const DOMAIN: &[u8] = b"fiat-shamir/session-id";
254
255    let mut initial_block = [0u8; RATE];
256    initial_block[..DOMAIN.len()].copy_from_slice(DOMAIN);
257
258    let mut shake = sha3::Shake128::default();
259    shake.update(&initial_block);
260    shake.update(session_id);
261
262    let mut reader = shake.finalize_xof();
263    let mut derived = [0u8; 64];
264    reader.read(&mut derived[32..]);
265    derived
266}
267
268fn serialize_messages_into<T: NargSerialize>(messages: &[T], out: &mut Vec<u8>) {
269    for message in messages {
270        message.serialize_into_narg(out);
271    }
272}
273
274fn serialize_messages<T: NargSerialize>(messages: &[T]) -> Vec<u8> {
275    let mut out = Vec::new();
276    serialize_messages_into(messages, &mut out);
277    out
278}
279
280fn deserialize_messages<T: NargDeserialize>(len: usize, buf: &mut &[u8]) -> Result<Vec<T>, Error> {
281    let mut out = Vec::with_capacity(len);
282    for _ in 0..len {
283        out.push(T::deserialize_from_narg(buf).map_err(|_| Error::VerificationFailure)?);
284    }
285    Ok(out)
286}
sigma_proofs/fiat_shamir.rs

sigma_proofs/
fiat_shamir.rs
