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

sigma_proofs/
fiat_shamir.rs
