sp1_recursion_program/machine/
root.rs

1use std::borrow::Borrow;
2
3use p3_air::Air;
4use p3_baby_bear::BabyBear;
5use p3_commit::TwoAdicMultiplicativeCoset;
6use p3_field::{AbstractField, PrimeField32, TwoAdicField};
7use sp1_primitives::types::RecursionProgramType;
8use sp1_recursion_compiler::{
9    config::InnerConfig,
10    ir::{Builder, Config, Felt, Var},
11    prelude::DslVariable,
12};
13use sp1_recursion_core::{
14    air::{RecursionPublicValues, RECURSIVE_PROOF_NUM_PV_ELTS},
15    runtime::{RecursionProgram, DIGEST_SIZE},
16};
17
18use sp1_recursion_compiler::prelude::*;
19use sp1_stark::{
20    air::MachineAir, baby_bear_poseidon2::BabyBearPoseidon2, Com, ShardProof, StarkGenericConfig,
21    StarkMachine, StarkVerifyingKey,
22};
23
24use crate::{
25    challenger::{CanObserveVariable, DuplexChallengerVariable},
26    fri::TwoAdicFriPcsVariable,
27    hints::Hintable,
28    machine::utils::proof_data_from_vk,
29    stark::{RecursiveVerifierConstraintFolder, ShardProofHint, StarkVerifier},
30    types::ShardProofVariable,
31    utils::{const_fri_config, hash_vkey},
32};
33
34use super::utils::{commit_public_values, verify_public_values_hash};
35
36/// The program that gets a final verifier at the root of the tree.
37#[derive(Debug, Clone, Copy)]
38pub struct SP1RootVerifier<C: Config, SC: StarkGenericConfig, A> {
39    _phantom: std::marker::PhantomData<(C, SC, A)>,
40}
41
42pub struct SP1RootMemoryLayout<'a, SC: StarkGenericConfig, A: MachineAir<SC::Val>> {
43    pub machine: &'a StarkMachine<SC, A>,
44    pub proof: ShardProof<SC>,
45    pub is_reduce: bool,
46}
47
48#[derive(DslVariable, Clone)]
49pub struct SP1RootMemoryLayoutVariable<C: Config> {
50    pub proof: ShardProofVariable<C>,
51    pub is_reduce: Var<C::N>,
52}
53
54impl<A> SP1RootVerifier<InnerConfig, BabyBearPoseidon2, A>
55where
56    A: MachineAir<BabyBear> + for<'a> Air<RecursiveVerifierConstraintFolder<'a, InnerConfig>>,
57{
58    /// Create a new instance of the program for the [BabyBearPoseidon2] config.
59    pub fn build(
60        machine: &StarkMachine<BabyBearPoseidon2, A>,
61        vk: &StarkVerifyingKey<BabyBearPoseidon2>,
62        program_type: RecursionProgramType,
63    ) -> RecursionProgram<BabyBear> {
64        assert!(matches!(program_type, RecursionProgramType::Shrink | RecursionProgramType::Wrap));
65
66        let mut builder = Builder::<InnerConfig>::new(program_type);
67
68        let proof: ShardProofVariable<_> = builder.uninit();
69        ShardProofHint::<BabyBearPoseidon2, A>::witness(&proof, &mut builder);
70
71        let pcs = TwoAdicFriPcsVariable {
72            config: const_fri_config(&mut builder, machine.config().pcs().fri_config()),
73        };
74
75        SP1RootVerifier::verify(&mut builder, &pcs, machine, vk, &proof);
76
77        builder.compile_program()
78    }
79}
80
81impl<C: Config, SC, A> SP1RootVerifier<C, SC, A>
82where
83    C::F: PrimeField32 + TwoAdicField,
84    SC: StarkGenericConfig<
85        Val = C::F,
86        Challenge = C::EF,
87        Domain = TwoAdicMultiplicativeCoset<C::F>,
88    >,
89    A: MachineAir<C::F> + for<'a> Air<RecursiveVerifierConstraintFolder<'a, C>>,
90    Com<SC>: Into<[SC::Val; DIGEST_SIZE]>,
91{
92    /// Verify a proof with given vk and aggregate their public values.
93    ///
94    /// is_reduce : if the proof is a reduce proof, we will assert that the given vk indentifies
95    /// with the reduce vk digest of public inputs.
96    pub fn verify(
97        builder: &mut Builder<C>,
98        pcs: &TwoAdicFriPcsVariable<C>,
99        machine: &StarkMachine<SC, A>,
100        vk: &StarkVerifyingKey<SC>,
101        proof: &ShardProofVariable<C>,
102    ) {
103        // Get the verifying key info from the vk.
104        let vk = proof_data_from_vk(builder, vk, machine);
105
106        // Verify the proof.
107
108        let mut challenger = DuplexChallengerVariable::new(builder);
109        // Observe the vk and start pc.
110        challenger.observe(builder, vk.commitment.clone());
111        challenger.observe(builder, vk.pc_start);
112        // Observe the main commitment and public values.
113        challenger.observe(builder, proof.commitment.main_commit.clone());
114        for j in 0..machine.num_pv_elts() {
115            let element = builder.get(&proof.public_values, j);
116            challenger.observe(builder, element);
117        }
118        // verify proof.
119        StarkVerifier::<C, SC>::verify_shard(
120            builder,
121            &vk,
122            pcs,
123            machine,
124            &mut challenger,
125            proof,
126            true,
127        );
128
129        // Get the public inputs from the proof.
130        let public_values_elements = (0..RECURSIVE_PROOF_NUM_PV_ELTS)
131            .map(|i| builder.get(&proof.public_values, i))
132            .collect::<Vec<Felt<_>>>();
133        let public_values: &RecursionPublicValues<Felt<C::F>> =
134            public_values_elements.as_slice().borrow();
135
136        // Check that the public values digest is correct.
137        verify_public_values_hash(builder, public_values);
138
139        // Assert that the proof is complete.
140        //
141        // *Remark*: here we are assuming on that the program we are verifying indludes the check
142        // of completeness conditions are satisfied if the flag is set to one, so we are only
143        // checking the `is_complete` flag in this program.
144        builder.assert_felt_eq(public_values.is_complete, C::F::one());
145
146        // If this is a Shrink program (when it's verifying a compress proof), then assert that the
147        // vk is the same as the compress vk from the public values.
148        if matches!(builder.program_type, RecursionProgramType::Shrink) {
149            let vk_digest = hash_vkey(builder, &vk);
150            for (i, reduce_digest_elem) in public_values.compress_vk_digest.iter().enumerate() {
151                let vk_digest_elem = builder.get(&vk_digest, i);
152                builder.assert_felt_eq(vk_digest_elem, *reduce_digest_elem);
153            }
154        }
155
156        commit_public_values(builder, public_values);
157
158        builder.halt();
159    }
160}
sp1_recursion_program/machine/root.rs

sp1_recursion_program/machine/
root.rs
