sp1_recursion_core/chips/
mod.rs

1pub mod alu_base;
2pub mod alu_ext;
3pub mod batch_fri;
4pub mod exp_reverse_bits;
5pub mod fri_fold;
6pub mod mem;
7pub mod poseidon2_skinny;
8pub mod poseidon2_wide;
9pub mod public_values;
10pub mod select;
11
12#[cfg(test)]
13pub mod test_fixtures {
14    use crate::*;
15    use p3_baby_bear::BabyBear;
16    use p3_field::{AbstractField, Field, PrimeField32};
17    use p3_symmetric::Permutation;
18    use rand::{prelude::SliceRandom, rngs::StdRng, Rng, SeedableRng};
19    use sp1_stark::inner_perm;
20    use std::{array, borrow::Borrow};
21
22    const SEED: u64 = 12345;
23    pub const MIN_TEST_CASES: usize = 1000;
24    const MAX_TEST_CASES: usize = 10000;
25
26    pub fn shard() -> ExecutionRecord<BabyBear> {
27        ExecutionRecord {
28            base_alu_events: base_alu_events(),
29            ext_alu_events: ext_alu_events(),
30            batch_fri_events: batch_fri_events(),
31            exp_reverse_bits_len_events: exp_reverse_bits_events(),
32            fri_fold_events: fri_fold_events(),
33            commit_pv_hash_events: public_values_events(),
34            select_events: select_events(),
35            poseidon2_events: poseidon2_events(),
36            ..Default::default()
37        }
38    }
39
40    pub fn program() -> RecursionProgram<BabyBear> {
41        let mut instructions = [
42            base_alu_instructions(),
43            ext_alu_instructions(),
44            batch_fri_instructions(),
45            exp_reverse_bits_instructions(),
46            fri_fold_instructions(),
47            public_values_instructions(),
48            select_instructions(),
49            poseidon2_instructions(),
50        ]
51        .concat();
52
53        let mut rng = StdRng::seed_from_u64(SEED);
54        instructions.shuffle(&mut rng);
55
56        linear_program(instructions).unwrap()
57    }
58
59    pub fn default_execution_record() -> ExecutionRecord<BabyBear> {
60        ExecutionRecord::<BabyBear>::default()
61    }
62
63    fn initialize() -> (StdRng, usize) {
64        let mut rng = StdRng::seed_from_u64(SEED);
65        let num_test_cases = rng.gen_range(MIN_TEST_CASES..=MAX_TEST_CASES);
66        (rng, num_test_cases)
67    }
68
69    fn base_alu_events() -> Vec<BaseAluIo<BabyBear>> {
70        let (mut rng, num_test_cases) = initialize();
71        let mut events = Vec::with_capacity(num_test_cases);
72        for _ in 0..num_test_cases {
73            let in1 = BabyBear::from_wrapped_u32(rng.gen());
74            let in2 = BabyBear::from_wrapped_u32(rng.gen());
75            let out = match rng.gen_range(0..4) {
76                0 => in1 + in2, // Add
77                1 => in1 - in2, // Sub
78                2 => in1 * in2, // Mul
79                _ => {
80                    let in2 = if in2.is_zero() { BabyBear::one() } else { in2 };
81                    in1 / in2
82                }
83            };
84            events.push(BaseAluIo { out, in1, in2 });
85        }
86        events
87    }
88
89    fn ext_alu_events() -> Vec<ExtAluIo<Block<BabyBear>>> {
90        let (_, num_test_cases) = initialize();
91        let mut events = Vec::with_capacity(num_test_cases);
92        for _ in 0..num_test_cases {
93            events.push(ExtAluIo {
94                out: BabyBear::one().into(),
95                in1: BabyBear::one().into(),
96                in2: BabyBear::one().into(),
97            });
98        }
99        events
100    }
101
102    fn batch_fri_events() -> Vec<BatchFRIEvent<BabyBear>> {
103        let (_, num_test_cases) = initialize();
104        let mut events = Vec::with_capacity(num_test_cases);
105        for _ in 0..num_test_cases {
106            events.push(BatchFRIEvent {
107                ext_single: BatchFRIExtSingleIo { acc: Block::default() },
108                ext_vec: BatchFRIExtVecIo { alpha_pow: Block::default(), p_at_z: Block::default() },
109                base_vec: BatchFRIBaseVecIo { p_at_x: BabyBear::one() },
110            });
111        }
112        events
113    }
114
115    fn exp_reverse_bits_events() -> Vec<ExpReverseBitsEvent<BabyBear>> {
116        let (mut rng, num_test_cases) = initialize();
117        let mut events = Vec::with_capacity(num_test_cases);
118        for _ in 0..num_test_cases {
119            let base = BabyBear::from_wrapped_u32(rng.gen());
120            let len = rng.gen_range(1..8); // Random length between 1 and 7 bits
121            let exp: Vec<BabyBear> =
122                (0..len).map(|_| BabyBear::from_canonical_u32(rng.gen_range(0..2))).collect();
123            let exp_num = exp
124                .iter()
125                .enumerate()
126                .fold(0u32, |acc, (i, &bit)| acc + (bit.as_canonical_u32() << i));
127            let result = base.exp_u64(exp_num as u64);
128
129            events.push(ExpReverseBitsEvent { base, exp, result });
130        }
131        events
132    }
133
134    fn fri_fold_events() -> Vec<FriFoldEvent<BabyBear>> {
135        let (mut rng, num_test_cases) = initialize();
136        let mut events = Vec::with_capacity(num_test_cases);
137        let random_block =
138            |rng: &mut StdRng| Block::from([BabyBear::from_wrapped_u32(rng.gen()); 4]);
139        for _ in 0..num_test_cases {
140            events.push(FriFoldEvent {
141                base_single: FriFoldBaseIo { x: BabyBear::from_wrapped_u32(rng.gen()) },
142                ext_single: FriFoldExtSingleIo {
143                    z: random_block(&mut rng),
144                    alpha: random_block(&mut rng),
145                },
146                ext_vec: FriFoldExtVecIo {
147                    mat_opening: random_block(&mut rng),
148                    ps_at_z: random_block(&mut rng),
149                    alpha_pow_input: random_block(&mut rng),
150                    ro_input: random_block(&mut rng),
151                    alpha_pow_output: random_block(&mut rng),
152                    ro_output: random_block(&mut rng),
153                },
154            });
155        }
156        events
157    }
158
159    fn public_values_events() -> Vec<CommitPublicValuesEvent<BabyBear>> {
160        let (mut rng, num_test_cases) = initialize();
161        let mut events = Vec::with_capacity(num_test_cases);
162        for _ in 0..num_test_cases {
163            let random_felts: [BabyBear; air::RECURSIVE_PROOF_NUM_PV_ELTS] =
164                array::from_fn(|_| BabyBear::from_wrapped_u32(rng.gen()));
165            events
166                .push(CommitPublicValuesEvent { public_values: *random_felts.as_slice().borrow() });
167        }
168        events
169    }
170
171    fn select_events() -> Vec<SelectIo<BabyBear>> {
172        let (mut rng, num_test_cases) = initialize();
173        let mut events = Vec::with_capacity(num_test_cases);
174        for _ in 0..num_test_cases {
175            let bit = if rng.gen_bool(0.5) { BabyBear::one() } else { BabyBear::zero() };
176            let in1 = BabyBear::from_wrapped_u32(rng.gen());
177            let in2 = BabyBear::from_wrapped_u32(rng.gen());
178            let (out1, out2) = if bit == BabyBear::one() { (in1, in2) } else { (in2, in1) };
179            events.push(SelectIo { bit, out1, out2, in1, in2 });
180        }
181        events
182    }
183
184    fn poseidon2_events() -> Vec<Poseidon2Event<BabyBear>> {
185        let (mut rng, num_test_cases) = initialize();
186        let mut events = Vec::with_capacity(num_test_cases);
187        for _ in 0..num_test_cases {
188            let input = array::from_fn(|_| BabyBear::from_wrapped_u32(rng.gen()));
189            let permuter = inner_perm();
190            let output = permuter.permute(input);
191
192            events.push(Poseidon2Event { input, output });
193        }
194        events
195    }
196
197    fn base_alu_instructions() -> Vec<Instruction<BabyBear>> {
198        let (mut rng, num_test_cases) = initialize();
199        let mut instructions = Vec::with_capacity(num_test_cases);
200        for _ in 0..num_test_cases {
201            let opcode = match rng.gen_range(0..4) {
202                0 => BaseAluOpcode::AddF,
203                1 => BaseAluOpcode::SubF,
204                2 => BaseAluOpcode::MulF,
205                _ => BaseAluOpcode::DivF,
206            };
207            instructions.push(Instruction::BaseAlu(BaseAluInstr {
208                opcode,
209                mult: BabyBear::from_wrapped_u32(rng.gen()),
210                addrs: BaseAluIo {
211                    out: Address(BabyBear::from_wrapped_u32(rng.gen())),
212                    in1: Address(BabyBear::from_wrapped_u32(rng.gen())),
213                    in2: Address(BabyBear::from_wrapped_u32(rng.gen())),
214                },
215            }));
216        }
217        instructions
218    }
219
220    fn ext_alu_instructions() -> Vec<Instruction<BabyBear>> {
221        let (mut rng, num_test_cases) = initialize();
222        let mut instructions = Vec::with_capacity(num_test_cases);
223        for _ in 0..num_test_cases {
224            let opcode = match rng.gen_range(0..4) {
225                0 => ExtAluOpcode::AddE,
226                1 => ExtAluOpcode::SubE,
227                2 => ExtAluOpcode::MulE,
228                _ => ExtAluOpcode::DivE,
229            };
230            instructions.push(Instruction::ExtAlu(ExtAluInstr {
231                opcode,
232                mult: BabyBear::from_wrapped_u32(rng.gen()),
233                addrs: ExtAluIo {
234                    out: Address(BabyBear::from_wrapped_u32(rng.gen())),
235                    in1: Address(BabyBear::from_wrapped_u32(rng.gen())),
236                    in2: Address(BabyBear::from_wrapped_u32(rng.gen())),
237                },
238            }));
239        }
240        instructions
241    }
242
243    fn batch_fri_instructions() -> Vec<Instruction<BabyBear>> {
244        let (mut rng, num_test_cases) = initialize();
245        let mut instructions = Vec::with_capacity(num_test_cases);
246        for _ in 0..num_test_cases {
247            let len = rng.gen_range(1..5); // Random number of addresses in vectors
248            let p_at_x = (0..len).map(|_| Address(BabyBear::from_wrapped_u32(rng.gen()))).collect();
249            let alpha_pow =
250                (0..len).map(|_| Address(BabyBear::from_wrapped_u32(rng.gen()))).collect();
251            let p_at_z = (0..len).map(|_| Address(BabyBear::from_wrapped_u32(rng.gen()))).collect();
252            let acc = Address(BabyBear::from_wrapped_u32(rng.gen()));
253            instructions.push(Instruction::BatchFRI(Box::new(BatchFRIInstr {
254                base_vec_addrs: BatchFRIBaseVecIo { p_at_x },
255                ext_single_addrs: BatchFRIExtSingleIo { acc },
256                ext_vec_addrs: BatchFRIExtVecIo { alpha_pow, p_at_z },
257                acc_mult: BabyBear::one(), // BatchFRI always uses mult of 1
258            })));
259        }
260        instructions
261    }
262
263    fn exp_reverse_bits_instructions() -> Vec<Instruction<BabyBear>> {
264        let (mut rng, num_test_cases) = initialize();
265        let mut instructions = Vec::with_capacity(num_test_cases);
266        for _ in 0..num_test_cases {
267            let len = rng.gen_range(1..8); // Random length between 1 and 7 bits
268            let exp: Vec<Address<BabyBear>> =
269                (0..len).map(|_| Address(BabyBear::from_wrapped_u32(rng.gen()))).collect();
270            let base = Address(BabyBear::from_wrapped_u32(rng.gen()));
271            let result = Address(BabyBear::from_wrapped_u32(rng.gen()));
272            let mult = BabyBear::from_wrapped_u32(rng.gen());
273            instructions.push(Instruction::ExpReverseBitsLen(ExpReverseBitsInstr {
274                addrs: ExpReverseBitsIo { base, exp, result },
275                mult,
276            }));
277        }
278        instructions
279    }
280
281    fn fri_fold_instructions() -> Vec<Instruction<BabyBear>> {
282        let (mut rng, num_test_cases) = initialize();
283        let mut instructions = Vec::with_capacity(num_test_cases);
284        let random_addr = |rng: &mut StdRng| Address(BabyBear::from_wrapped_u32(rng.gen()));
285        let random_addrs =
286            |rng: &mut StdRng, len: usize| (0..len).map(|_| random_addr(rng)).collect();
287        for _ in 0..num_test_cases {
288            let len = rng.gen_range(1..5); // Random vector length
289            instructions.push(Instruction::FriFold(Box::new(FriFoldInstr {
290                base_single_addrs: FriFoldBaseIo { x: random_addr(&mut rng) },
291                ext_single_addrs: FriFoldExtSingleIo {
292                    z: random_addr(&mut rng),
293                    alpha: random_addr(&mut rng),
294                },
295                ext_vec_addrs: FriFoldExtVecIo {
296                    mat_opening: random_addrs(&mut rng, len),
297                    ps_at_z: random_addrs(&mut rng, len),
298                    alpha_pow_input: random_addrs(&mut rng, len),
299                    ro_input: random_addrs(&mut rng, len),
300                    alpha_pow_output: random_addrs(&mut rng, len),
301                    ro_output: random_addrs(&mut rng, len),
302                },
303                alpha_pow_mults: vec![BabyBear::one(); len],
304                ro_mults: vec![BabyBear::one(); len],
305            })));
306        }
307        instructions
308    }
309
310    fn public_values_instructions() -> Vec<Instruction<BabyBear>> {
311        let (mut rng, num_test_cases) = initialize();
312        let mut instructions = Vec::with_capacity(num_test_cases);
313        for _ in 0..num_test_cases {
314            let public_values_a: [u32; air::RECURSIVE_PROOF_NUM_PV_ELTS] =
315                array::from_fn(|_| BabyBear::from_wrapped_u32(rng.gen()).as_canonical_u32());
316            let public_values: &RecursionPublicValues<u32> = public_values_a.as_slice().borrow();
317            instructions.push(runtime::instruction::commit_public_values(public_values));
318        }
319        instructions
320    }
321
322    fn select_instructions() -> Vec<Instruction<BabyBear>> {
323        let (mut rng, num_test_cases) = initialize();
324        let mut instructions = Vec::with_capacity(num_test_cases);
325        for _ in 0..num_test_cases {
326            instructions.push(Instruction::Select(SelectInstr {
327                addrs: SelectIo {
328                    bit: Address(BabyBear::from_wrapped_u32(rng.gen())),
329                    out1: Address(BabyBear::from_wrapped_u32(rng.gen())),
330                    out2: Address(BabyBear::from_wrapped_u32(rng.gen())),
331                    in1: Address(BabyBear::from_wrapped_u32(rng.gen())),
332                    in2: Address(BabyBear::from_wrapped_u32(rng.gen())),
333                },
334                mult1: BabyBear::from_wrapped_u32(rng.gen()),
335                mult2: BabyBear::from_wrapped_u32(rng.gen()),
336            }));
337        }
338        instructions
339    }
340
341    fn poseidon2_instructions() -> Vec<Instruction<BabyBear>> {
342        let (mut rng, num_test_cases) = initialize();
343        let mut instructions = Vec::with_capacity(num_test_cases);
344
345        for _ in 0..num_test_cases {
346            let input = array::from_fn(|_| Address(BabyBear::from_wrapped_u32(rng.gen())));
347            let output = array::from_fn(|_| Address(BabyBear::from_wrapped_u32(rng.gen())));
348            let mults = array::from_fn(|_| BabyBear::from_wrapped_u32(rng.gen()));
349
350            instructions.push(Instruction::Poseidon2(Box::new(Poseidon2Instr {
351                addrs: Poseidon2Io { input, output },
352                mults,
353            })));
354        }
355        instructions
356    }
357}
sp1_recursion_core/chips/mod.rs

sp1_recursion_core/chips/
mod.rs
