sp1_hypercube/verifier/
proof.rs

1use std::collections::BTreeMap;
2
3use serde::{Deserialize, Serialize};
4use slop_algebra::AbstractField;
5use slop_alloc::{CpuBackend, GLOBAL_CPU_BACKEND};
6use slop_basefold::BasefoldProof;
7use slop_challenger::{GrindingChallenger, IopCtx};
8use slop_commit::Rounds;
9use slop_jagged::{JaggedPcsProof, JaggedSumcheckEvalProof};
10use slop_matrix::dense::RowMajorMatrixView;
11use slop_multilinear::{Mle, MleEval, MultilinearPcsVerifier, Point};
12use slop_sumcheck::PartialSumcheckProof;
13use slop_symmetric::PseudoCompressionFunction;
14use slop_tensor::Tensor;
15use sp1_primitives::{utils::reverse_bits_len, SP1ExtensionField, SP1Field, SP1GlobalContext};
16
17use crate::{
18    LogUpEvaluations, LogUpGkrOutput, LogupGkrProof, MachineVerifyingKey, SP1PcsProof,
19    SP1PcsProofInner, SP1VerifyingKey, ShardContext, DIGEST_SIZE,
20};
21
22/// The maximum number of elements that can be stored in the public values vec.  Both SP1 and
23/// recursive proofs need to pad their public values vec to this length.  This is required since the
24/// recursion verification program expects the public values vec to be fixed length.
25pub const PROOF_MAX_NUM_PVS: usize = 187;
26
27/// Data required for testing.
28#[derive(Clone, Serialize, Deserialize)]
29#[serde(bound(
30    serialize = "GC: IopCtx, GC::Challenger: Serialize",
31    deserialize = "GC: IopCtx, GC::Challenger: Deserialize<'de>"
32))]
33// #[cfg(any(test, feature = "test-proof"))]
34pub struct TestingData<GC: IopCtx> {
35    /// The gkr points.
36    pub gkr_points: Vec<Point<GC::EF>>,
37    /// The challenger state just before the zerocheck.
38    pub challenger_state: GC::Challenger,
39}
40
41/// A proof for a shard.
42#[derive(Clone, Serialize, Deserialize)]
43#[serde(bound(
44    serialize = "GC: IopCtx, GC::Challenger: Serialize, Proof: Serialize",
45    deserialize = "GC: IopCtx, GC::Challenger: Deserialize<'de>, Proof: Deserialize<'de>"
46))]
47pub struct ShardProof<GC: IopCtx, Proof> {
48    /// The public values
49    pub public_values: Vec<GC::F>,
50    /// The commitments to main traces.
51    pub main_commitment: GC::Digest,
52    /// The Logup GKR IOP proof.
53    pub logup_gkr_proof: LogupGkrProof<<GC::Challenger as GrindingChallenger>::Witness, GC::EF>,
54    /// TH zerocheck IOP proof.
55    pub zerocheck_proof: PartialSumcheckProof<GC::EF>,
56    /// The values of the traces at the final random point.
57    pub opened_values: ShardOpenedValues<GC::F, GC::EF>,
58    /// The evaluation proof.
59    pub evaluation_proof: JaggedPcsProof<GC, Proof>,
60}
61
62/// The `ShardProof` type generic in `GC` and `SC`.
63pub type ShardContextProof<GC, SC> =
64    ShardProof<GC, <<SC as ShardContext<GC>>::Config as MultilinearPcsVerifier<GC>>::Proof>;
65
66/// The values of the chips in the shard at a random point.
67#[derive(Debug, Clone, Serialize, Deserialize)]
68pub struct ShardOpenedValues<F, EF> {
69    /// For each chip with respect to the canonical ordering, the values of the chip at the random
70    /// point.
71    pub chips: BTreeMap<String, ChipOpenedValues<F, EF>>,
72}
73
74/// The opening values for a given chip at a random point.
75#[derive(Debug, Clone, Serialize, Deserialize)]
76#[serde(bound(serialize = "F: Serialize, EF: Serialize"))]
77#[serde(bound(deserialize = "F: Deserialize<'de>, EF: Deserialize<'de>"))]
78pub struct ChipOpenedValues<F, EF> {
79    /// The opening of the preprocessed trace.
80    pub preprocessed: AirOpenedValues<EF>,
81    /// The opening of the main trace.
82    pub main: AirOpenedValues<EF>,
83    /// The big-endian bit representation of the degree of the chip.
84    pub degree: Point<F>,
85}
86
87/// The opening values for a given table section at a random point.
88#[derive(Debug, Clone, Serialize, Deserialize)]
89#[serde(bound(serialize = "T: Serialize"))]
90#[serde(bound(deserialize = "T: Deserialize<'de>"))]
91pub struct AirOpenedValues<T> {
92    /// The opening of the local trace
93    pub local: Vec<T>,
94}
95
96impl<T> AirOpenedValues<T> {
97    /// Organize the opening values into a vertical pair.
98    #[must_use]
99    pub fn view(&self) -> RowMajorMatrixView<'_, T>
100    where
101        T: Clone + Send + Sync,
102    {
103        RowMajorMatrixView::new_row(&self.local)
104    }
105}
106
107/// A Merkle tree proof for proving membership in the recursion verifying key set.
108#[derive(Debug, Clone, Serialize, Deserialize)]
109pub struct MerkleProof<GC: IopCtx> {
110    /// The index of the leaf being proven.
111    pub index: usize,
112    /// The Merkle path.
113    pub path: Vec<GC::Digest>,
114}
115
116#[derive(Debug)]
117/// The error type for Merkle proof verification.
118pub struct VcsError;
119
120/// Verify a Merkle proof.
121pub fn verify_merkle_proof<GC: IopCtx>(
122    proof: &MerkleProof<GC>,
123    value: GC::Digest,
124    commitment: GC::Digest,
125) -> Result<(), VcsError> {
126    let MerkleProof { index, path } = proof;
127
128    let mut value = value;
129
130    let mut index = reverse_bits_len(*index, path.len());
131
132    for sibling in path {
133        // If the index is odd, swap the order of [value, sibling].
134        let new_pair = if index.is_multiple_of(2) { [value, *sibling] } else { [*sibling, value] };
135        let (_, compressor) = GC::default_hasher_and_compressor();
136        value = compressor.compress(new_pair);
137        index >>= 1;
138    }
139    if value != commitment {
140        Err(VcsError)
141    } else {
142        Ok(())
143    }
144}
145
146/// An intermediate proof which proves the execution of a Hypercube verifier.
147#[derive(Serialize, Deserialize, Clone)]
148#[serde(bound(
149    serialize = "GC: IopCtx, GC::Challenger: Serialize, Proof: Serialize",
150    deserialize = "GC: IopCtx, GC::Challenger: Deserialize<'de>, Proof: Deserialize<'de>"
151))]
152pub struct SP1RecursionProof<GC: IopCtx, Proof> {
153    /// The verifying key associated with the proof.
154    pub vk: MachineVerifyingKey<GC>,
155    /// The shard proof representing the shard proof.
156    pub proof: ShardProof<GC, Proof>,
157    /// The Merkle proof for the recursion verifying key.
158    pub vk_merkle_proof: MerkleProof<SP1GlobalContext>,
159}
160
161impl<GC: IopCtx, Proof> std::fmt::Debug for SP1RecursionProof<GC, Proof> {
162    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
163        let mut debug_struct = f.debug_struct("SP1ReduceProof");
164        // TODO: comment back after debug enabled.
165        // debug_struct.field("vk", &self.vk);
166        // debug_struct.field("proof", &self.proof);
167        debug_struct.finish()
168    }
169}
170
171/// An intermediate proof which proves the execution of a Hypercube verifier.
172#[derive(Serialize, Deserialize, Clone)]
173#[serde(bound(
174    serialize = "GC: IopCtx, GC::Challenger: Serialize, Proof: Serialize",
175    deserialize = "GC: IopCtx, GC::Challenger: Deserialize<'de>, Proof: Deserialize<'de>"
176))]
177pub struct SP1WrapProof<GC: IopCtx, Proof> {
178    /// The verifying key associated with the proof.
179    pub vk: MachineVerifyingKey<GC>,
180    /// The shard proof within the wrap proof.
181    pub proof: ShardProof<GC, Proof>,
182}
183
184/// Creates a dummy recursion proof with minimal values for mock proof creation.
185///
186/// This is used internally for creating mock compressed proofs. The proof contains
187/// valid structures but with zero/empty values since the mock verifier doesn't
188/// actually verify the proof contents.
189#[must_use]
190pub fn create_dummy_recursion_proof(
191    vk: &SP1VerifyingKey,
192) -> SP1RecursionProof<SP1GlobalContext, SP1PcsProofInner> {
193    // Create minimal dummy values for the proof.
194    // These are the minimum required to satisfy the type system.
195
196    // Create dummy basefold proof.
197    let dummy_query_proof = Vec::new();
198    let basefold_proof = BasefoldProof::<SP1GlobalContext> {
199        univariate_messages: vec![],
200        fri_commitments: vec![],
201        final_poly: SP1ExtensionField::zero(),
202        pow_witness: SP1Field::zero(),
203        batch_grinding_witness: SP1Field::zero(),
204        component_polynomials_query_openings_and_proofs: vec![],
205        query_phase_openings_and_proofs: dummy_query_proof,
206    };
207
208    let batch_evaluations: Rounds<MleEval<SP1ExtensionField, CpuBackend>> = Rounds::default();
209
210    let stacked_proof = SP1PcsProof { basefold_proof, batch_evaluations };
211
212    let jagged_eval_proof =
213        JaggedSumcheckEvalProof { partial_sumcheck_proof: PartialSumcheckProof::dummy() };
214
215    let evaluation_proof = JaggedPcsProof {
216        pcs_proof: stacked_proof,
217        jagged_eval_proof,
218        sumcheck_proof: PartialSumcheckProof::dummy(),
219        merkle_tree_commitments: Rounds::default(),
220        row_counts_and_column_counts: Rounds::default(),
221        expected_eval: SP1ExtensionField::zero(),
222        max_log_row_count: 1,
223        log_m: 1,
224    };
225
226    // Create dummy LogupGkrProof.
227    // Create empty Mle with minimal size using Tensor::zeros_in.
228    let empty_tensor: Tensor<SP1ExtensionField, CpuBackend> =
229        Tensor::zeros_in([1], GLOBAL_CPU_BACKEND);
230    let logup_gkr_proof = LogupGkrProof {
231        circuit_output: LogUpGkrOutput {
232            numerator: Mle::new(empty_tensor.clone()),
233            denominator: Mle::new(empty_tensor),
234        },
235        round_proofs: vec![],
236        logup_evaluations: LogUpEvaluations {
237            point: Point::from_usize(0, 1),
238            chip_openings: BTreeMap::new(),
239        },
240        witness: SP1Field::zero(),
241    };
242
243    // Create dummy ShardProof.
244    let dummy_shard_proof = ShardProof {
245        public_values: Vec::new(),
246        main_commitment: [SP1Field::zero(); DIGEST_SIZE],
247        logup_gkr_proof,
248        zerocheck_proof: PartialSumcheckProof::dummy(),
249        opened_values: ShardOpenedValues { chips: BTreeMap::new() },
250        evaluation_proof,
251    };
252
253    SP1RecursionProof {
254        vk: vk.vk.clone(),
255        proof: dummy_shard_proof,
256        vk_merkle_proof: MerkleProof { index: 0, path: vec![] },
257    }
258}
sp1_hypercube/verifier/proof.rs

sp1_hypercube/verifier/
proof.rs
