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        transcript.prover_messages(&commitment);
86        let challenge = transcript.verifier_message::<P::Challenge>();
87        let response = self
88            .interactive_proof
89            .prover_response(ip_state, &challenge)?;
90        transcript.prover_messages(&response);
91        Ok(transcript.narg_string().to_vec())
92    }
93
94    /// Verifies a batchable non-interactive proof.
95    ///
96    /// # Parameters
97    /// - `proof`: A serialized batchable proof.
98    ///
99    /// # Returns
100    /// - `Ok(())` if the proof is valid.
101    /// - `Err(Error)` if deserialization or verification fails.
102    ///
103    /// # Errors
104    /// - Returns [`Error::VerificationFailure`] if:
105    ///   - The challenge doesn't match the recomputed one from the commitment.
106    ///   - The response fails verification under the Sigma protocol.
107    pub fn verify_batchable(&self, narg_string: &[u8]) -> Result<(), Error> {
108        let protocol_id = self.interactive_proof.protocol_identifier();
109        let instance_label = self.interactive_proof.instance_label();
110        let commitment_len = self.interactive_proof.commitment_len();
111        let response_len = self.interactive_proof.response_len();
112        let mut transcript = initialize_verifier_state(
113            protocol_id,
114            &self.session_id,
115            instance_label.as_ref(),
116            narg_string,
117        );
118        let commitment = transcript.prover_messages_vec::<P::Commitment>(commitment_len)?;
119        let challenge = transcript.verifier_message::<P::Challenge>();
120        let response = transcript.prover_messages_vec::<P::Response>(response_len)?;
121        transcript.check_eof()?;
122        self.interactive_proof
123            .verifier(&commitment, &challenge, &response)
124    }
125}
126
127impl<P> Nizk<P>
128where
129    P: SigmaProtocol + SigmaProtocolSimulator,
130    P::Challenge: PartialEq + NargDeserialize + NargSerialize,
131{
132    /// Generates a compact serialized proof.
133    ///
134    /// Uses a more space-efficient representation compared to batchable proofs.
135    ///
136    /// # Parameters
137    /// - `witness`: The secret witness.
138    /// - `rng`: A cryptographically secure random number generator.
139    ///
140    /// # Returns
141    /// A compact, serialized proof.
142    ///
143    /// # Panics
144    /// Panics if serialization fails.
145    pub fn prove_compact(
146        &self,
147        witness: &P::Witness,
148        rng: &mut impl ScalarRng,
149    ) -> Result<Vec<u8>, Error> {
150        let protocol_id = self.interactive_proof.protocol_identifier();
151        let instance_label = self.interactive_proof.instance_label();
152        let mut transcript =
153            initialize_prover_state(protocol_id, &self.session_id, instance_label.as_ref());
154        let (commitment, ip_state) = self.interactive_proof.prover_commit(witness, rng)?;
155        let commitment_bytes = serialize_messages(&commitment);
156        transcript.public_message(commitment_bytes.as_slice());
157        let challenge = transcript.verifier_message::<P::Challenge>();
158        let response = self
159            .interactive_proof
160            .prover_response(ip_state, &challenge)?;
161
162        // Serialize the compact proof string.
163        let mut proof = Vec::new();
164        challenge.serialize_into_narg(&mut proof);
165        serialize_messages_into(&response, &mut proof);
166        Ok(proof)
167    }
168
169    /// Verifies a compact proof.
170    ///
171    /// Recomputes the commitment from the challenge and response, then verifies it.
172    ///
173    /// # Parameters
174    /// - `proof`: A compact serialized proof.
175    ///
176    /// # Returns
177    /// - `Ok(())` if the proof is valid.
178    /// - `Err(Error)` if deserialization or verification fails.
179    ///
180    /// # Errors
181    /// - Returns [`Error::VerificationFailure`] if:
182    ///   - Deserialization fails.
183    ///   - The recomputed commitment or response is invalid under the Sigma protocol.
184    pub fn verify_compact(&self, proof: &[u8]) -> Result<(), Error> {
185        // Deserialize challenge and response from compact proof
186        let mut cursor = proof;
187        let protocol_id = self.interactive_proof.protocol_identifier();
188        let instance_label = self.interactive_proof.instance_label();
189        let challenge = P::Challenge::deserialize_from_narg(&mut cursor)?;
190        let response_len = self.interactive_proof.response_len();
191        let response = deserialize_messages(response_len, &mut cursor)?;
192
193        // Proof size check
194        if !cursor.is_empty() {
195            return Err(Error::VerificationFailure);
196        }
197
198        // Compute the commitments
199        let commitment = self
200            .interactive_proof
201            .simulate_commitment(&challenge, &response)?;
202
203        // Re-compute the challenge and ensure it's the same as the one
204        // we received
205        let commitment_bytes = serialize_messages(&commitment);
206        let mut transcript =
207            initialize_verifier_state(protocol_id, &self.session_id, instance_label.as_ref(), &[]);
208        transcript.public_message(commitment_bytes.as_slice());
209        let recomputed_challenge = transcript.verifier_message::<P::Challenge>();
210        if challenge != recomputed_challenge {
211            return Err(Error::VerificationFailure);
212        }
213
214        // At this point, checking
215        // self.interactive_proof.verifier(&commitment, &challenge,
216        // &response) is redundant, because we know that commitment =
217        // simulate_commitment(challenge, response), and that challenge
218        // is the output of the appropriate hash, so the signature is
219        // valid.
220        Ok(())
221    }
222}
223
224fn initialize_prover_state(
225    protocol_id: [u8; 64],
226    session_id: &[u8],
227    instance_label: &[u8],
228) -> ProverState {
229    let instance_label = instance_label.to_vec();
230    DomainSeparator::new(protocol_id)
231        .session(derive_session_id(session_id))
232        .instance(&instance_label)
233        .std_prover()
234}
235
236fn initialize_verifier_state<'a>(
237    protocol_id: [u8; 64],
238    session_id: &[u8],
239    instance_label: &[u8],
240    narg_string: &'a [u8],
241) -> VerifierState<'a> {
242    let instance_label = instance_label.to_vec();
243    DomainSeparator::new(protocol_id)
244        .session(derive_session_id(session_id))
245        .instance(&instance_label)
246        .std_verifier(narg_string)
247}
248
249fn derive_session_id(session_id: &[u8]) -> [u8; 64] {
250    const RATE: usize = 168;
251    const DOMAIN: &[u8] = b"fiat-shamir/session-id";
252
253    let mut initial_block = [0u8; RATE];
254    initial_block[..DOMAIN.len()].copy_from_slice(DOMAIN);
255
256    let mut shake = sha3::Shake128::default();
257    shake.update(&initial_block);
258    shake.update(session_id);
259
260    let mut reader = shake.finalize_xof();
261    let mut derived = [0u8; 64];
262    reader.read(&mut derived[32..]);
263    derived
264}
265
266fn serialize_messages_into<T: NargSerialize>(messages: &[T], out: &mut Vec<u8>) {
267    for message in messages {
268        message.serialize_into_narg(out);
269    }
270}
271
272fn serialize_messages<T: NargSerialize>(messages: &[T]) -> Vec<u8> {
273    let mut out = Vec::new();
274    serialize_messages_into(messages, &mut out);
275    out
276}
277
278fn deserialize_messages<T: NargDeserialize>(len: usize, buf: &mut &[u8]) -> Result<Vec<T>, Error> {
279    let mut out = Vec::new();
280    for _ in 0..len {
281        out.push(T::deserialize_from_narg(buf).map_err(|_| Error::VerificationFailure)?);
282    }
283    Ok(out)
284}
sigma_proofs/fiat_shamir.rs

sigma_proofs/
fiat_shamir.rs
