sigma-proofs 0.3.1

A toolkit for auto-generated implementations of Σ-protocols
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

//! Generic interface for 3-message Sigma protocols.
//!
//! This module defines the [`SigmaProtocol`] and [`SigmaProtocolSimulator`] traits,
//! used to describe interactive zero-knowledge proofs of knowledge,
//! such as Schnorr proofs, that follow the 3-message Sigma protocol structure.

use crate::errors::Result;
use alloc::vec::Vec;
use group::Group;
use spongefish::{Decoding, Encoding, NargDeserialize, NargSerialize};

/// An automatic trait helper for sampling scalars from an RNG.
///
/// This trait is implemented for all types implementing
/// `rand_core::RngCore + rand_core::CryptoRng`.
/// Passing any cryptographically-secure random number generator (CSRNG) is
/// recommended for creating proofs.
pub trait ScalarRng {
    fn random_scalars<G: Group, const N: usize>(&mut self) -> [G::Scalar; N];
    fn random_scalars_vec<G: Group>(&mut self, n: usize) -> Vec<G::Scalar>;
}

pub type Transcript<P> = (
    Vec<<P as SigmaProtocol>::Commitment>,
    <P as SigmaProtocol>::Challenge,
    Vec<<P as SigmaProtocol>::Response>,
);

/// A trait defining the behavior of a generic Sigma protocol.
///
/// A Sigma protocol is a 3-message proof protocol where a prover can convince
/// a verifier of knowledge of a witness for a given public statement
/// without revealing the witness.
///
/// ## Associated Types
/// - `Commitment`: The prover's initial commitment.
/// - `ProverState`: The prover's internal state needed to compute a response.
/// - `Response`: The prover's response to a verifier's challenge.
/// - `Witness`: The prover's secret knowledge.
/// - `Challenge`: The verifier's challenge value.
///
///  ## Minimal Implementation
/// Types implementing [`SigmaProtocol`] must define:
/// - `prover_commit` — Generates a commitment and internal state.
/// - `prover_response` — Computes a response to a challenge.
/// - `verifier` — Verifies a full transcript `(commitment, challenge, response)`.
///
/// ## Serialization
/// Implementors must also provide methods for serialization and deserialization
/// of each component of the proof.
/// Required methods:
/// - `serialize_commitment` / `deserialize_commitment`
/// - `serialize_challenge` / `deserialize_challenge`
/// - `serialize_response` / `deserialize_response`
///
/// These functions should encode/decode each component into/from a compact binary format.
///
/// ## Identification
/// To allow transcript hash binding and protocol distinction,
/// implementors must provide:
/// - `protocol_identifier` — A fixed byte identifier of the protocol.
/// - `instance_label` — A label specific to the instance being proven.
pub trait SigmaProtocol {
    type Commitment: Encoding<[u8]> + NargSerialize + NargDeserialize;
    type Challenge: Decoding<[u8]>;
    type Response: Encoding<[u8]> + NargSerialize + NargDeserialize;
    type ProverState;
    type Witness;

    /// First step of the protocol. Given the witness and RNG, this generates:
    /// - A public commitment to send to the verifier.
    /// - The internal state to use when computing the response.
    fn prover_commit(
        &self,
        witness: &Self::Witness,
        rng: &mut impl ScalarRng,
    ) -> Result<(Vec<Self::Commitment>, Self::ProverState)>;

    /// Computes the prover's response to a challenge based on the prover state.
    fn prover_response(
        &self,
        state: Self::ProverState,
        challenge: &Self::Challenge,
    ) -> Result<Vec<Self::Response>>;

    /// Final step of the protocol: checks that the commitment, challenge, and response form a valid transcript.
    ///
    /// Returns:
    /// - `Ok(())` if the transcript is valid.
    /// - `Err(())` otherwise.
    fn verifier(
        &self,
        commitment: &[Self::Commitment],
        challenge: &Self::Challenge,
        response: &[Self::Response],
    ) -> Result<()>;

    fn commitment_len(&self) -> usize;

    fn response_len(&self) -> usize;

    fn protocol_identifier(&self) -> [u8; 64];

    fn instance_label(&self) -> impl AsRef<[u8]>;
}

/// A trait defining the behavior of a Sigma protocol for which simulation of transcripts is necessary.
///
/// Every Sigma protocol can be simulated, but in practice, this is primarily used
/// for proving security properties (zero-knowledge, soundness, etc.).
///
/// Some protocols (e.g. OR compositions) require simulation capabilities during actual proof generation.
///
/// ## Minimal Implementation
/// Types implementing [`SigmaProtocolSimulator`] must define:
/// - `simulate_proof`
/// - `simulate_transcript`
pub trait SigmaProtocolSimulator: SigmaProtocol {
    /// Generates a random response (e.g. for simulation or OR composition).
    ///
    /// Typically used to simulate a proof without a witness.
    fn simulate_response(&self, rng: &mut impl ScalarRng) -> Vec<Self::Response>;

    /// Simulates a commitment for which ('commitment', 'challenge', 'response') is a valid transcript.
    ///
    /// This function allows to omit commitment in compact proofs of the type ('challenge', 'response').
    fn simulate_commitment(
        &self,
        challenge: &Self::Challenge,
        response: &[Self::Response],
    ) -> Result<Vec<Self::Commitment>>;

    /// Generates a full simulated proof transcript (commitment, challenge, response)
    /// without requiring knowledge of a witness.
    fn simulate_transcript(&self, rng: &mut impl ScalarRng) -> Result<Transcript<Self>>;
}