risc0_circuit_recursion/
lib.rs

1// Copyright 2025 RISC Zero, Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![cfg_attr(not(feature = "std"), no_std)]
16
17//! The recursion VM is a non-Turing-complete virtual machine (VM)
18//! optimized for algebraic constraint checking. In particular, it is
19//! well-tuned for verifying STARKs.
20//!
21//! The recursion VM runs "recursion programs", which define the
22//! functionality it will implement.  As examples, the `lift`, `join`,
23//! and `resolve` programs are used by the risc0 ZkVM to compress a
24//! collection of STARK receipts for a composition into a single
25//! succinct receipt.
26//!
27//! This is a low-level interface; users should prefer to use the
28//! `risc0_zkvm` crate.
29
30extern crate alloc;
31
32pub mod control_id;
33mod info;
34pub mod layout;
35mod poly_ext;
36#[cfg(feature = "prove")]
37pub mod prove;
38mod taps;
39
40use risc0_zkp::{
41    adapter::{CircuitCoreDef, TapsProvider},
42    field::baby_bear::BabyBear,
43    taps::TapSet,
44};
45
46pub const REGISTER_GROUP_ACCUM: usize = 0;
47pub const REGISTER_GROUP_CODE: usize = 1;
48pub const REGISTER_GROUP_CTRL: usize = 1;
49pub const REGISTER_GROUP_DATA: usize = 2;
50
51pub const GLOBAL_MIX: usize = 0;
52pub const GLOBAL_OUT: usize = 1;
53pub const CIRCUIT: CircuitImpl = CircuitImpl::new();
54
55/// This struct implements traits that are defined by code generated by the
56/// circuit definition.
57pub struct CircuitImpl;
58
59#[allow(clippy::new_without_default)]
60impl CircuitImpl {
61    pub const fn new() -> Self {
62        CircuitImpl
63    }
64}
65
66impl TapsProvider for CircuitImpl {
67    fn get_taps(&self) -> &'static TapSet<'static> {
68        self::taps::TAPSET
69    }
70}
71
72impl CircuitCoreDef<BabyBear> for CircuitImpl {}
73
74#[cfg(feature = "test")]
75pub mod testutil {
76    use rand::Rng;
77    use risc0_zkp::{
78        adapter::{CircuitInfo, TapsProvider},
79        field::{
80            baby_bear::{BabyBearElem, BabyBearExtElem},
81            Elem, ExtElem,
82        },
83        hal::{Buffer, CircuitHal, Hal},
84        INV_RATE,
85    };
86
87    use crate::{CircuitImpl, REGISTER_GROUP_ACCUM, REGISTER_GROUP_CODE, REGISTER_GROUP_DATA};
88
89    pub struct EvalCheckParams {
90        pub po2: usize,
91        pub steps: usize,
92        pub domain: usize,
93        pub code: Vec<BabyBearElem>,
94        pub data: Vec<BabyBearElem>,
95        pub accum: Vec<BabyBearElem>,
96        pub mix: Vec<BabyBearElem>,
97        pub out: Vec<BabyBearElem>,
98        pub poly_mix: BabyBearExtElem,
99    }
100
101    impl EvalCheckParams {
102        pub fn new(po2: usize) -> Self {
103            let mut rng = rand::rng();
104            let steps = 1 << po2;
105            let domain = steps * INV_RATE;
106            let circuit = CircuitImpl::new();
107            let taps = circuit.get_taps();
108            let code_size = taps.group_size(REGISTER_GROUP_CODE);
109            let data_size = taps.group_size(REGISTER_GROUP_DATA);
110            let accum_size = taps.group_size(REGISTER_GROUP_ACCUM);
111            let code = random_fps(&mut rng, code_size * domain);
112            let data = random_fps(&mut rng, data_size * domain);
113            let accum = random_fps(&mut rng, accum_size * domain);
114            let mix = random_fps(&mut rng, CircuitImpl::MIX_SIZE);
115            let out = random_fps(&mut rng, CircuitImpl::OUTPUT_SIZE);
116            let poly_mix = BabyBearExtElem::random(&mut rng);
117            tracing::debug!("code: {} bytes", code.len() * 4);
118            tracing::debug!("data: {} bytes", data.len() * 4);
119            tracing::debug!("accum: {} bytes", accum.len() * 4);
120            tracing::debug!("mix: {} bytes", mix.len() * 4);
121            tracing::debug!("out: {} bytes", out.len() * 4);
122            Self {
123                po2,
124                steps,
125                domain,
126                code,
127                data,
128                accum,
129                mix,
130                out,
131                poly_mix,
132            }
133        }
134    }
135
136    fn random_fps<E: Elem>(rng: &mut impl Rng, size: usize) -> Vec<E> {
137        let mut ret = Vec::new();
138        for _ in 0..size {
139            ret.push(E::random(rng));
140        }
141        ret
142    }
143
144    #[allow(unused)]
145    pub(crate) fn eval_check<H1, H2, C1, C2>(hal1: &H1, eval1: C1, hal2: &H2, eval2: C2, po2: usize)
146    where
147        H1: Hal<Elem = BabyBearElem, ExtElem = BabyBearExtElem>,
148        H2: Hal<Elem = BabyBearElem, ExtElem = BabyBearExtElem>,
149        C1: CircuitHal<H1>,
150        C2: CircuitHal<H2>,
151    {
152        let params = EvalCheckParams::new(po2);
153        let check1 = eval_check_impl(&params, hal1, &eval1);
154        let check2 = eval_check_impl(&params, hal2, &eval2);
155        assert_eq!(check1, check2);
156    }
157
158    pub fn eval_check_impl<H, C>(params: &EvalCheckParams, hal: &H, eval: &C) -> Vec<H::Elem>
159    where
160        H: Hal<Elem = BabyBearElem, ExtElem = BabyBearExtElem>,
161        C: CircuitHal<H>,
162    {
163        let check = hal.alloc_elem("check", BabyBearExtElem::EXT_SIZE * params.domain);
164        let code = hal.copy_from_elem("code", &params.code);
165        let data = hal.copy_from_elem("data", &params.data);
166        let accum = hal.copy_from_elem("accum", &params.accum);
167        let mix = hal.copy_from_elem("mix", &params.mix);
168        let out = hal.copy_from_elem("out", &params.out);
169        eval.eval_check(
170            &check,
171            &[&accum, &code, &data],
172            &[&mix, &out],
173            params.poly_mix,
174            params.po2,
175            params.steps,
176        );
177        let mut ret = vec![H::Elem::ZERO; check.size()];
178        check.view(|view| {
179            ret.clone_from_slice(view);
180        });
181        ret
182    }
183}
risc0_circuit_recursion/lib.rs

risc0_circuit_recursion/
lib.rs
