sp1_recursion_circuit_v2/
lib.rs

1//! Copied from [`sp1_recursion_program`].
2
3use std::{
4    iter::{repeat, zip},
5    ops::{Add, Mul},
6};
7
8use challenger::{
9    CanCopyChallenger, CanObserveVariable, DuplexChallengerVariable, FieldChallengerVariable,
10    MultiField32ChallengerVariable,
11};
12use hash::FieldHasherVariable;
13use p3_bn254_fr::Bn254Fr;
14use p3_field::AbstractField;
15use p3_matrix::dense::RowMajorMatrix;
16use sp1_recursion_compiler::{
17    circuit::CircuitV2Builder,
18    config::{InnerConfig, OuterConfig},
19    ir::{Builder, Config, DslIr, Ext, Felt, Var, Variable},
20};
21
22mod types;
23
24pub mod build_wrap_v2;
25pub mod challenger;
26pub mod constraints;
27pub mod domain;
28pub mod fri;
29pub mod hash;
30pub mod machine;
31pub mod stark;
32pub(crate) mod utils;
33pub mod witness;
34
35use sp1_stark::{
36    baby_bear_poseidon2::{BabyBearPoseidon2, ValMmcs},
37    StarkGenericConfig,
38};
39pub use types::*;
40
41use p3_challenger::{CanObserve, CanSample, FieldChallenger, GrindingChallenger};
42use p3_commit::{ExtensionMmcs, Mmcs};
43use p3_dft::Radix2DitParallel;
44use p3_fri::{FriConfig, TwoAdicFriPcs};
45use sp1_recursion_core_v2::{
46    stark::config::{BabyBearPoseidon2Outer, OuterValMmcs},
47    D,
48};
49
50use p3_baby_bear::BabyBear;
51
52type EF = <BabyBearPoseidon2 as StarkGenericConfig>::Challenge;
53
54pub type PcsConfig<C> = FriConfig<
55    ExtensionMmcs<
56        <C as StarkGenericConfig>::Val,
57        <C as StarkGenericConfig>::Challenge,
58        <C as BabyBearFriConfig>::ValMmcs,
59    >,
60>;
61
62pub type Digest<C, SC> = <SC as FieldHasherVariable<C>>::Digest;
63
64pub type FriMmcs<C> = ExtensionMmcs<BabyBear, EF, <C as BabyBearFriConfig>::ValMmcs>;
65
66pub trait BabyBearFriConfig:
67    StarkGenericConfig<
68    Val = BabyBear,
69    Challenge = EF,
70    Challenger = Self::FriChallenger,
71    Pcs = TwoAdicFriPcs<
72        BabyBear,
73        Radix2DitParallel,
74        Self::ValMmcs,
75        ExtensionMmcs<BabyBear, EF, Self::ValMmcs>,
76    >,
77>
78{
79    type ValMmcs: Mmcs<BabyBear, ProverData<RowMajorMatrix<BabyBear>> = Self::RowMajorProverData>
80        + Send
81        + Sync;
82    type RowMajorProverData: Clone + Send + Sync;
83    type FriChallenger: CanObserve<<Self::ValMmcs as Mmcs<BabyBear>>::Commitment>
84        + CanSample<EF>
85        + GrindingChallenger<Witness = BabyBear>
86        + FieldChallenger<BabyBear>;
87
88    fn fri_config(&self) -> &FriConfig<FriMmcs<Self>>;
89}
90
91pub trait BabyBearFriConfigVariable<C: CircuitConfig<F = BabyBear>>:
92    BabyBearFriConfig + FieldHasherVariable<C>
93{
94    type FriChallengerVariable: FieldChallengerVariable<C, <C as CircuitConfig>::Bit>
95        + CanObserveVariable<C, <Self as FieldHasherVariable<C>>::Digest>
96        + CanCopyChallenger<C>;
97
98    /// Get a new challenger corresponding to the given config.
99    fn challenger_variable(&self, builder: &mut Builder<C>) -> Self::FriChallengerVariable;
100}
101
102pub trait CircuitConfig: Config {
103    type Bit: Clone + Variable<Self>;
104
105    fn read_bit(builder: &mut Builder<Self>) -> Self::Bit;
106
107    fn read_felt(builder: &mut Builder<Self>) -> Felt<Self::F>;
108
109    fn read_ext(builder: &mut Builder<Self>) -> Ext<Self::F, Self::EF>;
110
111    fn ext2felt(
112        builder: &mut Builder<Self>,
113        ext: Ext<<Self as Config>::F, <Self as Config>::EF>,
114    ) -> [Felt<<Self as Config>::F>; D];
115
116    fn exp_reverse_bits(
117        builder: &mut Builder<Self>,
118        input: Felt<<Self as Config>::F>,
119        power_bits: Vec<Self::Bit>,
120    ) -> Felt<<Self as Config>::F>;
121
122    fn num2bits(
123        builder: &mut Builder<Self>,
124        num: Felt<<Self as Config>::F>,
125        num_bits: usize,
126    ) -> Vec<Self::Bit>;
127
128    fn bits2num(
129        builder: &mut Builder<Self>,
130        bits: impl IntoIterator<Item = Self::Bit>,
131    ) -> Felt<<Self as Config>::F>;
132
133    #[allow(clippy::type_complexity)]
134    fn select_chain_ef(
135        builder: &mut Builder<Self>,
136        should_swap: Self::Bit,
137        first: impl IntoIterator<Item = Ext<<Self as Config>::F, <Self as Config>::EF>> + Clone,
138        second: impl IntoIterator<Item = Ext<<Self as Config>::F, <Self as Config>::EF>> + Clone,
139    ) -> Vec<Ext<<Self as Config>::F, <Self as Config>::EF>>;
140}
141
142impl CircuitConfig for InnerConfig {
143    type Bit = Felt<<Self as Config>::F>;
144
145    fn read_bit(builder: &mut Builder<Self>) -> Self::Bit {
146        builder.hint_felt_v2()
147    }
148
149    fn read_felt(builder: &mut Builder<Self>) -> Felt<Self::F> {
150        builder.hint_felt_v2()
151    }
152
153    fn read_ext(builder: &mut Builder<Self>) -> Ext<Self::F, Self::EF> {
154        builder.hint_ext_v2()
155    }
156
157    fn ext2felt(
158        builder: &mut Builder<Self>,
159        ext: Ext<<Self as Config>::F, <Self as Config>::EF>,
160    ) -> [Felt<<Self as Config>::F>; D] {
161        builder.ext2felt_v2(ext)
162    }
163
164    fn exp_reverse_bits(
165        builder: &mut Builder<Self>,
166        input: Felt<<Self as Config>::F>,
167        power_bits: Vec<Felt<<Self as Config>::F>>,
168    ) -> Felt<<Self as Config>::F> {
169        builder.exp_reverse_bits_v2(input, power_bits)
170    }
171
172    fn num2bits(
173        builder: &mut Builder<Self>,
174        num: Felt<<Self as Config>::F>,
175        num_bits: usize,
176    ) -> Vec<Felt<<Self as Config>::F>> {
177        builder.num2bits_v2_f(num, num_bits)
178    }
179
180    fn bits2num(
181        builder: &mut Builder<Self>,
182        bits: impl IntoIterator<Item = Felt<<Self as Config>::F>>,
183    ) -> Felt<<Self as Config>::F> {
184        builder.bits2num_v2_f(bits)
185    }
186
187    fn select_chain_ef(
188        builder: &mut Builder<Self>,
189        should_swap: Self::Bit,
190        first: impl IntoIterator<Item = Ext<<Self as Config>::F, <Self as Config>::EF>> + Clone,
191        second: impl IntoIterator<Item = Ext<<Self as Config>::F, <Self as Config>::EF>> + Clone,
192    ) -> Vec<Ext<<Self as Config>::F, <Self as Config>::EF>> {
193        let one: Felt<_> = builder.constant(Self::F::one());
194        let shouldnt_swap: Felt<_> = builder.eval(one - should_swap);
195
196        let id_branch = first.clone().into_iter().chain(second.clone());
197        let swap_branch = second.into_iter().chain(first);
198        zip(zip(id_branch, swap_branch), zip(repeat(shouldnt_swap), repeat(should_swap)))
199            .map(|((id_v, sw_v), (id_c, sw_c))| builder.eval(id_v * id_c + sw_v * sw_c))
200            .collect()
201    }
202}
203
204impl CircuitConfig for OuterConfig {
205    type Bit = Var<<Self as Config>::N>;
206
207    fn read_bit(builder: &mut Builder<Self>) -> Self::Bit {
208        builder.witness_var()
209    }
210
211    fn read_felt(builder: &mut Builder<Self>) -> Felt<Self::F> {
212        builder.witness_felt()
213    }
214
215    fn read_ext(builder: &mut Builder<Self>) -> Ext<Self::F, Self::EF> {
216        builder.witness_ext()
217    }
218
219    fn ext2felt(
220        builder: &mut Builder<Self>,
221        ext: Ext<<Self as Config>::F, <Self as Config>::EF>,
222    ) -> [Felt<<Self as Config>::F>; D] {
223        let felts = core::array::from_fn(|_| builder.uninit());
224        builder.operations.push(DslIr::CircuitExt2Felt(felts, ext));
225        felts
226    }
227
228    fn exp_reverse_bits(
229        builder: &mut Builder<Self>,
230        input: Felt<<Self as Config>::F>,
231        power_bits: Vec<Var<<Self as Config>::N>>,
232    ) -> Felt<<Self as Config>::F> {
233        let mut result = builder.constant(Self::F::one());
234        let power_f = input;
235        let bit_len = power_bits.len();
236
237        for i in 1..=bit_len {
238            let index = bit_len - i;
239            let bit = power_bits[index];
240            let prod = builder.eval(result * power_f);
241            result = builder.select_f(bit, prod, result);
242            builder.assign(power_f, power_f * power_f);
243        }
244        result
245    }
246
247    fn num2bits(
248        builder: &mut Builder<Self>,
249        num: Felt<<Self as Config>::F>,
250        num_bits: usize,
251    ) -> Vec<Var<<Self as Config>::N>> {
252        builder.num2bits_f_circuit(num)[..num_bits].to_vec()
253    }
254
255    fn bits2num(
256        builder: &mut Builder<Self>,
257        bits: impl IntoIterator<Item = Var<<Self as Config>::N>>,
258    ) -> Felt<<Self as Config>::F> {
259        let result = builder.eval(Self::F::zero());
260        for (i, bit) in bits.into_iter().enumerate() {
261            let to_add: Felt<_> = builder.uninit();
262            let pow2 = builder.constant(Self::F::from_canonical_u32(1 << i));
263            let zero = builder.constant(Self::F::zero());
264            builder.operations.push(DslIr::CircuitSelectF(bit, pow2, zero, to_add));
265            builder.assign(result, result + to_add);
266        }
267        result
268    }
269
270    fn select_chain_ef(
271        builder: &mut Builder<Self>,
272        should_swap: Self::Bit,
273        first: impl IntoIterator<Item = Ext<<Self as Config>::F, <Self as Config>::EF>> + Clone,
274        second: impl IntoIterator<Item = Ext<<Self as Config>::F, <Self as Config>::EF>> + Clone,
275    ) -> Vec<Ext<<Self as Config>::F, <Self as Config>::EF>> {
276        let id_branch = first.clone().into_iter().chain(second.clone());
277        let swap_branch = second.into_iter().chain(first);
278        zip(id_branch, swap_branch)
279            .map(|(id_v, sw_v): (Ext<_, _>, Ext<_, _>)| -> Ext<_, _> {
280                let result: Ext<_, _> = builder.uninit();
281                builder.operations.push(DslIr::CircuitSelectE(should_swap, sw_v, id_v, result));
282                result
283            })
284            .collect()
285    }
286}
287
288impl BabyBearFriConfig for BabyBearPoseidon2 {
289    type ValMmcs = ValMmcs;
290    type FriChallenger = <Self as StarkGenericConfig>::Challenger;
291    type RowMajorProverData = <ValMmcs as Mmcs<BabyBear>>::ProverData<RowMajorMatrix<BabyBear>>;
292
293    fn fri_config(&self) -> &FriConfig<FriMmcs<Self>> {
294        self.pcs().fri_config()
295    }
296}
297
298impl BabyBearFriConfig for BabyBearPoseidon2Outer {
299    type ValMmcs = OuterValMmcs;
300    type FriChallenger = <Self as StarkGenericConfig>::Challenger;
301
302    type RowMajorProverData =
303        <OuterValMmcs as Mmcs<BabyBear>>::ProverData<RowMajorMatrix<BabyBear>>;
304
305    fn fri_config(&self) -> &FriConfig<FriMmcs<Self>> {
306        self.pcs().fri_config()
307    }
308}
309
310impl<C: CircuitConfig<F = BabyBear, Bit = Felt<BabyBear>>> BabyBearFriConfigVariable<C>
311    for BabyBearPoseidon2
312{
313    type FriChallengerVariable = DuplexChallengerVariable<C>;
314
315    fn challenger_variable(&self, builder: &mut Builder<C>) -> Self::FriChallengerVariable {
316        DuplexChallengerVariable::new(builder)
317    }
318}
319
320impl<C: CircuitConfig<F = BabyBear, N = Bn254Fr, Bit = Var<Bn254Fr>>> BabyBearFriConfigVariable<C>
321    for BabyBearPoseidon2Outer
322{
323    type FriChallengerVariable = MultiField32ChallengerVariable<C>;
324
325    fn challenger_variable(&self, builder: &mut Builder<C>) -> Self::FriChallengerVariable {
326        MultiField32ChallengerVariable::new(builder)
327    }
328}
329
330pub fn select_chain<'a, C, R, S>(
331    builder: &'a mut Builder<C>,
332    should_swap: R,
333    first: impl IntoIterator<Item = S> + Clone + 'a,
334    second: impl IntoIterator<Item = S> + Clone + 'a,
335) -> impl Iterator<Item = S> + 'a
336where
337    C: Config,
338    R: Variable<C> + 'a,
339    S: Variable<C> + 'a,
340    <R as Variable<C>>::Expression: AbstractField
341        + Mul<<S as Variable<C>>::Expression, Output = <S as Variable<C>>::Expression>,
342    <S as Variable<C>>::Expression: Add<Output = <S as Variable<C>>::Expression>,
343{
344    let should_swap: <R as Variable<C>>::Expression = should_swap.into();
345    let one = <R as Variable<C>>::Expression::one();
346    let shouldnt_swap = one - should_swap.clone();
347
348    let id_branch =
349        first.clone().into_iter().chain(second.clone()).map(<S as Variable<C>>::Expression::from);
350    let swap_branch = second.into_iter().chain(first).map(<S as Variable<C>>::Expression::from);
351    zip(zip(id_branch, swap_branch), zip(repeat(shouldnt_swap), repeat(should_swap)))
352        .map(|((id_v, sw_v), (id_c, sw_c))| builder.eval(id_c * id_v + sw_c * sw_v))
353}
sp1_recursion_circuit_v2/lib.rs

sp1_recursion_circuit_v2/
lib.rs
