sp1_hypercube/verifier/
proof.rs

1use std::collections::BTreeMap;
2
3use serde::{Deserialize, Serialize};
4use slop_challenger::{GrindingChallenger, IopCtx};
5use slop_jagged::JaggedPcsProof;
6use slop_matrix::dense::RowMajorMatrixView;
7use slop_multilinear::{MultilinearPcsVerifier, Point};
8use slop_sumcheck::PartialSumcheckProof;
9use slop_symmetric::PseudoCompressionFunction;
10use sp1_primitives::{utils::reverse_bits_len, SP1GlobalContext};
11
12use crate::{LogupGkrProof, MachineVerifyingKey, ShardContext};
13
14/// The maximum number of elements that can be stored in the public values vec.  Both SP1 and
15/// recursive proofs need to pad their public values vec to this length.  This is required since the
16/// recursion verification program expects the public values vec to be fixed length.
17pub const PROOF_MAX_NUM_PVS: usize = 187;
18
19/// Data required for testing.
20#[derive(Clone, Serialize, Deserialize)]
21#[serde(bound(
22    serialize = "GC: IopCtx, GC::Challenger: Serialize",
23    deserialize = "GC: IopCtx, GC::Challenger: Deserialize<'de>"
24))]
25// #[cfg(any(test, feature = "test-proof"))]
26pub struct TestingData<GC: IopCtx> {
27    /// The gkr points.
28    pub gkr_points: Vec<Point<GC::EF>>,
29    /// The challenger state just before the zerocheck.
30    pub challenger_state: GC::Challenger,
31}
32
33/// A proof for a shard.
34#[derive(Clone, Serialize, Deserialize)]
35#[serde(bound(
36    serialize = "GC: IopCtx, GC::Challenger: Serialize, Proof: Serialize",
37    deserialize = "GC: IopCtx, GC::Challenger: Deserialize<'de>, Proof: Deserialize<'de>"
38))]
39pub struct ShardProof<GC: IopCtx, Proof> {
40    /// The public values
41    pub public_values: Vec<GC::F>,
42    /// The commitments to main traces.
43    pub main_commitment: GC::Digest,
44    /// The Logup GKR IOP proof.
45    pub logup_gkr_proof: LogupGkrProof<<GC::Challenger as GrindingChallenger>::Witness, GC::EF>,
46    /// TH zerocheck IOP proof.
47    pub zerocheck_proof: PartialSumcheckProof<GC::EF>,
48    /// The values of the traces at the final random point.
49    pub opened_values: ShardOpenedValues<GC::F, GC::EF>,
50    /// The evaluation proof.
51    pub evaluation_proof: JaggedPcsProof<GC, Proof>,
52}
53
54/// The `ShardProof` type generic in `GC` and `SC`.
55pub type ShardContextProof<GC, SC> =
56    ShardProof<GC, <<SC as ShardContext<GC>>::Config as MultilinearPcsVerifier<GC>>::Proof>;
57
58/// The values of the chips in the shard at a random point.
59#[derive(Debug, Clone, Serialize, Deserialize)]
60pub struct ShardOpenedValues<F, EF> {
61    /// For each chip with respect to the canonical ordering, the values of the chip at the random
62    /// point.
63    pub chips: BTreeMap<String, ChipOpenedValues<F, EF>>,
64}
65
66/// The opening values for a given chip at a random point.
67#[derive(Debug, Clone, Serialize, Deserialize)]
68#[serde(bound(serialize = "F: Serialize, EF: Serialize"))]
69#[serde(bound(deserialize = "F: Deserialize<'de>, EF: Deserialize<'de>"))]
70pub struct ChipOpenedValues<F, EF> {
71    /// The opening of the preprocessed trace.
72    pub preprocessed: AirOpenedValues<EF>,
73    /// The opening of the main trace.
74    pub main: AirOpenedValues<EF>,
75    /// The big-endian bit representation of the degree of the chip.
76    pub degree: Point<F>,
77}
78
79/// The opening values for a given table section at a random point.
80#[derive(Debug, Clone, Serialize, Deserialize)]
81#[serde(bound(serialize = "T: Serialize"))]
82#[serde(bound(deserialize = "T: Deserialize<'de>"))]
83pub struct AirOpenedValues<T> {
84    /// The opening of the local trace
85    pub local: Vec<T>,
86}
87
88impl<T> AirOpenedValues<T> {
89    /// Organize the opening values into a vertical pair.
90    #[must_use]
91    pub fn view(&self) -> RowMajorMatrixView<'_, T>
92    where
93        T: Clone + Send + Sync,
94    {
95        RowMajorMatrixView::new_row(&self.local)
96    }
97}
98
99/// A Merkle tree proof for proving membership in the recursion verifying key set.
100#[derive(Debug, Clone, Serialize, Deserialize)]
101pub struct MerkleProof<GC: IopCtx> {
102    /// The index of the leaf being proven.
103    pub index: usize,
104    /// The Merkle path.
105    pub path: Vec<GC::Digest>,
106}
107
108#[derive(Debug)]
109/// The error type for Merkle proof verification.
110pub struct VcsError;
111
112/// Verify a Merkle proof.
113pub fn verify_merkle_proof<GC: IopCtx>(
114    proof: &MerkleProof<GC>,
115    value: GC::Digest,
116    commitment: GC::Digest,
117) -> Result<(), VcsError> {
118    let MerkleProof { index, path } = proof;
119
120    let mut value = value;
121
122    let mut index = reverse_bits_len(*index, path.len());
123
124    for sibling in path {
125        // If the index is odd, swap the order of [value, sibling].
126        let new_pair = if index.is_multiple_of(2) { [value, *sibling] } else { [*sibling, value] };
127        let (_, compressor) = GC::default_hasher_and_compressor();
128        value = compressor.compress(new_pair);
129        index >>= 1;
130    }
131    if value != commitment {
132        Err(VcsError)
133    } else {
134        Ok(())
135    }
136}
137
138/// An intermediate proof which proves the execution of a Hypercube verifier.
139#[derive(Serialize, Deserialize, Clone)]
140#[serde(bound(
141    serialize = "GC: IopCtx, GC::Challenger: Serialize, Proof: Serialize",
142    deserialize = "GC: IopCtx, GC::Challenger: Deserialize<'de>, Proof: Deserialize<'de>"
143))]
144pub struct SP1RecursionProof<GC: IopCtx, Proof> {
145    /// The verifying key associated with the proof.
146    pub vk: MachineVerifyingKey<GC>,
147    /// The shard proof representing the shard proof.
148    pub proof: ShardProof<GC, Proof>,
149    /// The Merkle proof for the recursion verifying key.
150    pub vk_merkle_proof: MerkleProof<SP1GlobalContext>,
151}
152
153impl<GC: IopCtx, Proof> std::fmt::Debug for SP1RecursionProof<GC, Proof> {
154    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
155        let mut debug_struct = f.debug_struct("SP1ReduceProof");
156        // TODO: comment back after debug enabled.
157        // debug_struct.field("vk", &self.vk);
158        // debug_struct.field("proof", &self.proof);
159        debug_struct.finish()
160    }
161}
162
163/// An intermediate proof which proves the execution of a Hypercube verifier.
164#[derive(Serialize, Deserialize, Clone)]
165#[serde(bound(
166    serialize = "GC: IopCtx, GC::Challenger: Serialize, Proof: Serialize",
167    deserialize = "GC: IopCtx, GC::Challenger: Deserialize<'de>, Proof: Deserialize<'de>"
168))]
169pub struct SP1WrapProof<GC: IopCtx, Proof> {
170    /// The verifying key associated with the proof.
171    pub vk: MachineVerifyingKey<GC>,
172    /// The shard proof within the wrap proof.
173    pub proof: ShardProof<GC, Proof>,
174}
sp1_hypercube/verifier/proof.rs

sp1_hypercube/verifier/
proof.rs
