sp1_recursion_machine/
machine.rs

1use std::fmt;
2
3use slop_algebra::{extension::BinomiallyExtendable, PrimeField32};
4use sp1_hypercube::{air::MachineAir, Chip, Machine, MachineShape, PROOF_MAX_NUM_PVS};
5use sp1_recursion_executor::{ExecutionRecord, RecursionAirEventCount, RecursionProgram, D};
6
7use crate::chips::{
8    alu_base::{BaseAluChip, NUM_BASE_ALU_ENTRIES_PER_ROW},
9    alu_ext::{ExtAluChip, NUM_EXT_ALU_ENTRIES_PER_ROW},
10    mem::{constant::NUM_CONST_MEM_ENTRIES_PER_ROW, MemoryConstChip, MemoryVarChip},
11    poseidon2_helper::{
12        convert::{ConvertChip, NUM_CONVERT_ENTRIES_PER_ROW},
13        linear::{Poseidon2LinearLayerChip, NUM_LINEAR_ENTRIES_PER_ROW},
14        sbox::{Poseidon2SBoxChip, NUM_SBOX_ENTRIES_PER_ROW},
15    },
16    poseidon2_wide::Poseidon2WideChip,
17    prefix_sum_checks::PrefixSumChecksChip,
18    public_values::{PublicValuesChip, PUB_VALUES_LOG_HEIGHT},
19    select::SelectChip,
20};
21use std::mem::MaybeUninit;
22use strum::{EnumDiscriminants, EnumIter};
23
24#[derive(sp1_derive::MachineAir, EnumDiscriminants, Clone)]
25#[execution_record_path = "ExecutionRecord<F>"]
26#[program_path = "RecursionProgram<F>"]
27#[builder_path = "crate::builder::SP1RecursionAirBuilder<F = F>"]
28#[eval_trait_bound = "AB::Var: 'static"]
29#[strum_discriminants(derive(Hash, EnumIter))]
30pub enum RecursionAir<
31    F: PrimeField32 + BinomiallyExtendable<D>,
32    const DEGREE: usize,
33    const VAR_EVENTS_PER_ROW: usize,
34> {
35    MemoryConst(MemoryConstChip<F>),
36    MemoryVar(MemoryVarChip<F, VAR_EVENTS_PER_ROW>),
37    BaseAlu(BaseAluChip),
38    ExtAlu(ExtAluChip),
39    Poseidon2Wide(Poseidon2WideChip<DEGREE>),
40    Poseidon2LinearLayer(Poseidon2LinearLayerChip),
41    Poseidon2SBox(Poseidon2SBoxChip),
42    ExtFeltConvert(ConvertChip),
43    Select(SelectChip),
44    PrefixSumChecks(PrefixSumChecksChip),
45    PublicValues(PublicValuesChip),
46}
47
48impl<
49        F: PrimeField32 + BinomiallyExtendable<D>,
50        const DEGREE: usize,
51        const VAR_EVENTS_PER_ROW: usize,
52    > fmt::Debug for RecursionAir<F, DEGREE, VAR_EVENTS_PER_ROW>
53{
54    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
55        write!(f, "{}", self.name())
56    }
57}
58
59impl<
60        F: PrimeField32 + BinomiallyExtendable<D>,
61        const DEGREE: usize,
62        const VAR_EVENTS_PER_ROW: usize,
63    > RecursionAir<F, DEGREE, VAR_EVENTS_PER_ROW>
64{
65    /// Get a machine with all chips, except the dummy chip.
66    pub fn machine_wide_with_all_chips() -> Machine<F, Self> {
67        let chips = [
68            RecursionAir::MemoryConst(MemoryConstChip::default()),
69            RecursionAir::MemoryVar(MemoryVarChip::<F, VAR_EVENTS_PER_ROW>::default()),
70            RecursionAir::BaseAlu(BaseAluChip),
71            RecursionAir::ExtAlu(ExtAluChip),
72            RecursionAir::Poseidon2Wide(Poseidon2WideChip::<DEGREE>),
73            RecursionAir::Poseidon2LinearLayer(Poseidon2LinearLayerChip),
74            RecursionAir::Poseidon2SBox(Poseidon2SBoxChip),
75            RecursionAir::ExtFeltConvert(ConvertChip),
76            RecursionAir::PrefixSumChecks(PrefixSumChecksChip),
77            RecursionAir::Select(SelectChip),
78            RecursionAir::PublicValues(PublicValuesChip),
79        ]
80        .map(Chip::new)
81        .into_iter()
82        .collect::<Vec<_>>();
83
84        let shape = MachineShape::all(&chips);
85        Machine::new(chips, PROOF_MAX_NUM_PVS, shape)
86    }
87
88    /// A machine with dyunamic chip sizes.
89    pub fn compress_machine() -> Machine<F, Self> {
90        let chips = [
91            RecursionAir::MemoryConst(MemoryConstChip::default()),
92            RecursionAir::MemoryVar(MemoryVarChip::<F, VAR_EVENTS_PER_ROW>::default()),
93            RecursionAir::BaseAlu(BaseAluChip),
94            RecursionAir::ExtAlu(ExtAluChip),
95            RecursionAir::Poseidon2Wide(Poseidon2WideChip::<DEGREE>),
96            RecursionAir::PrefixSumChecks(PrefixSumChecksChip),
97            RecursionAir::Select(SelectChip),
98            RecursionAir::PublicValues(PublicValuesChip),
99        ]
100        .map(Chip::new)
101        .into_iter()
102        .collect::<Vec<_>>();
103        let shape = MachineShape::all(&chips);
104        Machine::new(chips, PROOF_MAX_NUM_PVS, shape)
105    }
106
107    pub fn shrink_machine() -> Machine<F, Self> {
108        Self::compress_machine()
109    }
110
111    /// A machine with dynamic chip sizes.
112    ///
113    /// This machine assumes that the `shrink` stage has a fixed shape, so there is no need to
114    /// fix the trace sizes.
115    pub fn wrap_machine() -> Machine<F, Self> {
116        let chips = [
117            RecursionAir::MemoryConst(MemoryConstChip::default()),
118            RecursionAir::MemoryVar(MemoryVarChip::<F, VAR_EVENTS_PER_ROW>::default()),
119            RecursionAir::BaseAlu(BaseAluChip),
120            RecursionAir::ExtAlu(ExtAluChip),
121            RecursionAir::Poseidon2LinearLayer(Poseidon2LinearLayerChip),
122            RecursionAir::Poseidon2SBox(Poseidon2SBoxChip),
123            RecursionAir::ExtFeltConvert(ConvertChip),
124            RecursionAir::Select(SelectChip),
125            RecursionAir::PublicValues(PublicValuesChip),
126        ]
127        .map(Chip::new)
128        .into_iter()
129        .collect::<Vec<_>>();
130        let shape = MachineShape::all(&chips);
131        Machine::new(chips, PROOF_MAX_NUM_PVS, shape)
132    }
133
134    pub fn heights(program: &RecursionProgram<F>) -> Vec<(String, usize)> {
135        let heights =
136            program.inner.iter().fold(RecursionAirEventCount::default(), |heights, instruction| {
137                heights + instruction.inner()
138            });
139
140        [
141            (
142                Self::MemoryConst(MemoryConstChip::default()),
143                heights.mem_const_events.div_ceil(NUM_CONST_MEM_ENTRIES_PER_ROW),
144            ),
145            (
146                Self::MemoryVar(MemoryVarChip::default()),
147                heights.mem_var_events.div_ceil(VAR_EVENTS_PER_ROW),
148            ),
149            (
150                Self::BaseAlu(BaseAluChip),
151                heights.base_alu_events.div_ceil(NUM_BASE_ALU_ENTRIES_PER_ROW),
152            ),
153            (
154                Self::ExtAlu(ExtAluChip),
155                heights.ext_alu_events.div_ceil(NUM_EXT_ALU_ENTRIES_PER_ROW),
156            ),
157            (Self::Poseidon2Wide(Poseidon2WideChip::<DEGREE>), heights.poseidon2_wide_events),
158            (
159                Self::Poseidon2LinearLayer(Poseidon2LinearLayerChip),
160                heights.poseidon2_linear_layer_events.div_ceil(NUM_LINEAR_ENTRIES_PER_ROW),
161            ),
162            (
163                Self::Poseidon2SBox(Poseidon2SBoxChip),
164                heights.poseidon2_sbox_events.div_ceil(NUM_SBOX_ENTRIES_PER_ROW),
165            ),
166            (
167                Self::ExtFeltConvert(ConvertChip),
168                heights.ext_felt_conversion_events.div_ceil(NUM_CONVERT_ENTRIES_PER_ROW),
169            ),
170            (Self::PrefixSumChecks(PrefixSumChecksChip), heights.prefix_sum_checks_events),
171            (Self::Select(SelectChip), heights.select_events),
172            (Self::PublicValues(PublicValuesChip), 1 << PUB_VALUES_LOG_HEIGHT),
173        ]
174        .map(|(chip, log_height)| (chip.name().to_string(), log_height))
175        .to_vec()
176    }
177}
178
179#[cfg(test)]
180pub mod tests {
181
182    use std::iter::once;
183
184    use rand::{rngs::StdRng, Rng, SeedableRng};
185    use slop_algebra::{
186        extension::{BinomialExtensionField, HasFrobenius},
187        AbstractExtensionField, AbstractField, Field,
188    };
189
190    use sp1_recursion_executor::{
191        instruction as instr, BaseAluOpcode, ExtAluOpcode, MemAccessKind, D,
192    };
193
194    use crate::test::test_recursion_linear_program;
195
196    #[tokio::test]
197    pub async fn fibonacci() {
198        let n = 10;
199
200        let instructions = once(instr::mem(MemAccessKind::Write, 1, 0, 0))
201            .chain(once(instr::mem(MemAccessKind::Write, 2, 1, 1)))
202            .chain((2..=n).map(|i| instr::base_alu(BaseAluOpcode::AddF, 2, i, i - 2, i - 1)))
203            .chain(once(instr::mem(MemAccessKind::Read, 1, n - 1, 34)))
204            .chain(once(instr::mem(MemAccessKind::Read, 2, n, 55)))
205            .collect::<Vec<_>>();
206
207        test_recursion_linear_program(instructions).await;
208    }
209
210    #[tokio::test]
211    #[should_panic]
212    pub async fn div_nonzero_by_zero() {
213        let instructions = vec![
214            instr::mem(MemAccessKind::Write, 1, 0, 0),
215            instr::mem(MemAccessKind::Write, 1, 1, 1),
216            instr::base_alu(BaseAluOpcode::DivF, 1, 2, 1, 0),
217            instr::mem(MemAccessKind::Read, 1, 2, 1),
218        ];
219
220        test_recursion_linear_program(instructions).await;
221    }
222
223    #[tokio::test]
224    pub async fn div_zero_by_zero() {
225        let instructions = vec![
226            instr::mem(MemAccessKind::Write, 1, 0, 0),
227            instr::mem(MemAccessKind::Write, 1, 1, 0),
228            instr::base_alu(BaseAluOpcode::DivF, 1, 2, 1, 0),
229            instr::mem(MemAccessKind::Read, 1, 2, 1),
230        ];
231
232        test_recursion_linear_program(instructions).await;
233    }
234
235    #[tokio::test]
236    pub async fn field_norm() {
237        use sp1_primitives::SP1Field;
238        type F = SP1Field;
239
240        let mut instructions = Vec::new();
241
242        let mut rng = StdRng::seed_from_u64(0xDEADBEEF);
243        let mut addr = 0;
244        for _ in 0..100 {
245            let inner: [F; 4] = std::iter::repeat_with(|| {
246                core::array::from_fn(|_| rng.sample(rand::distributions::Standard))
247            })
248            .find(|xs| !xs.iter().all(F::is_zero))
249            .unwrap();
250            let x = BinomialExtensionField::<F, D>::from_base_slice(&inner);
251            let gal = x.galois_group();
252
253            let mut acc = BinomialExtensionField::one();
254
255            instructions.push(instr::mem_ext(MemAccessKind::Write, 1, addr, acc));
256            for conj in gal {
257                instructions.push(instr::mem_ext(MemAccessKind::Write, 1, addr + 1, conj));
258                instructions.push(instr::ext_alu(ExtAluOpcode::MulE, 1, addr + 2, addr, addr + 1));
259
260                addr += 2;
261                acc *= conj;
262            }
263            let base_cmp: F = acc.as_base_slice()[0];
264            instructions.push(instr::mem_single(MemAccessKind::Read, 1, addr, base_cmp));
265            addr += 1;
266        }
267
268        test_recursion_linear_program(instructions).await;
269    }
270}
sp1_recursion_machine/machine.rs

sp1_recursion_machine/
machine.rs
