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
30#![allow(clippy::needless_lifetimes)]
31
32extern crate alloc;
33
34pub mod control_id;
35#[cfg(feature = "prove")]
36mod cpp;
37#[cfg(feature = "prove")]
38pub mod cpu;
39#[cfg(feature = "cuda")]
40pub mod cuda;
41mod info;
42pub mod layout;
43#[cfg(all(
44    feature = "prove",
45    any(all(target_os = "macos", target_arch = "aarch64"), target_os = "ios")
46))]
47pub mod metal;
48mod poly_ext;
49#[cfg(feature = "prove")]
50pub mod prove;
51mod taps;
52#[cfg(feature = "prove")]
53pub mod zkr;
54
55use risc0_core::field::baby_bear::{BabyBearElem, BabyBearExtElem};
56use risc0_zkp::{
57    adapter::{CircuitCoreDef, TapsProvider},
58    field::baby_bear::BabyBear,
59    taps::TapSet,
60};
61
62pub const REGISTER_GROUP_ACCUM: usize = 0;
63pub const REGISTER_GROUP_CODE: usize = 1;
64pub const REGISTER_GROUP_CTRL: usize = 1;
65pub const REGISTER_GROUP_DATA: usize = 2;
66
67pub const GLOBAL_MIX: usize = 0;
68pub const GLOBAL_OUT: usize = 1;
69
70pub const CHECKED_COEFFS_PER_POLY: usize = 16;
71
72/// This struct implements traits that are defined by code generated by the
73/// circuit definition.
74pub struct CircuitImpl;
75
76#[allow(clippy::new_without_default)]
77impl CircuitImpl {
78    pub const fn new() -> Self {
79        CircuitImpl
80    }
81}
82
83pub const CIRCUIT: CircuitImpl = CircuitImpl::new();
84
85impl TapsProvider for CircuitImpl {
86    fn get_taps(&self) -> &'static TapSet<'static> {
87        self::taps::TAPSET
88    }
89}
90
91impl CircuitCoreDef<BabyBear> for CircuitImpl {}
92
93// Values for micro inst "opcode"
94pub mod micro_op {
95    pub const CONST: u32 = 0;
96    pub const ADD: u32 = 1;
97    pub const SUB: u32 = 2;
98    pub const MUL: u32 = 3;
99    pub const INV: u32 = 4;
100    pub const EQ: u32 = 5;
101    pub const READ_IOP_HEADER: u32 = 6;
102    pub const READ_IOP_BODY: u32 = 7;
103    pub const MIX_RNG: u32 = 8;
104    pub const SELECT: u32 = 9;
105    pub const EXTRACT: u32 = 10;
106}
107
108// Externs used by recursion circuit with native data types.
109pub trait Externs {
110    fn wom_write(&mut self, _addr: BabyBearElem, _val: BabyBearExtElem) {
111        unimplemented!()
112    }
113
114    fn wom_read(&self, _addr: BabyBearElem) -> BabyBearExtElem {
115        unimplemented!()
116    }
117
118    fn read_iop_header(&mut self, _count: BabyBearElem, _k_and_flip_flag: BabyBearElem) {
119        unimplemented!()
120    }
121
122    fn read_iop_body(&mut self, _do_mont: BabyBearElem) -> BabyBearExtElem {
123        unimplemented!()
124    }
125
126    fn read_input_word(&mut self) -> u32 {
127        unimplemented!()
128    }
129}
130
131#[cfg(feature = "test")]
132pub mod testutil {
133    use rand::{thread_rng, Rng};
134    use risc0_zkp::{
135        adapter::{CircuitInfo, TapsProvider},
136        field::{
137            baby_bear::{BabyBearElem, BabyBearExtElem},
138            Elem, ExtElem,
139        },
140        hal::{Buffer, CircuitHal, Hal},
141        INV_RATE,
142    };
143
144    use crate::{CircuitImpl, REGISTER_GROUP_ACCUM, REGISTER_GROUP_CODE, REGISTER_GROUP_DATA};
145
146    pub struct EvalCheckParams {
147        pub po2: usize,
148        pub steps: usize,
149        pub domain: usize,
150        pub code: Vec<BabyBearElem>,
151        pub data: Vec<BabyBearElem>,
152        pub accum: Vec<BabyBearElem>,
153        pub mix: Vec<BabyBearElem>,
154        pub out: Vec<BabyBearElem>,
155        pub poly_mix: BabyBearExtElem,
156    }
157
158    impl EvalCheckParams {
159        pub fn new(po2: usize) -> Self {
160            let mut rng = thread_rng();
161            let steps = 1 << po2;
162            let domain = steps * INV_RATE;
163            let circuit = CircuitImpl::new();
164            let taps = circuit.get_taps();
165            let code_size = taps.group_size(REGISTER_GROUP_CODE);
166            let data_size = taps.group_size(REGISTER_GROUP_DATA);
167            let accum_size = taps.group_size(REGISTER_GROUP_ACCUM);
168            let code = random_fps(&mut rng, code_size * domain);
169            let data = random_fps(&mut rng, data_size * domain);
170            let accum = random_fps(&mut rng, accum_size * domain);
171            let mix = random_fps(&mut rng, CircuitImpl::MIX_SIZE);
172            let out = random_fps(&mut rng, CircuitImpl::OUTPUT_SIZE);
173            let poly_mix = BabyBearExtElem::random(&mut rng);
174            tracing::debug!("code: {} bytes", code.len() * 4);
175            tracing::debug!("data: {} bytes", data.len() * 4);
176            tracing::debug!("accum: {} bytes", accum.len() * 4);
177            tracing::debug!("mix: {} bytes", mix.len() * 4);
178            tracing::debug!("out: {} bytes", out.len() * 4);
179            Self {
180                po2,
181                steps,
182                domain,
183                code,
184                data,
185                accum,
186                mix,
187                out,
188                poly_mix,
189            }
190        }
191    }
192
193    fn random_fps<E: Elem>(rng: &mut impl Rng, size: usize) -> Vec<E> {
194        let mut ret = Vec::new();
195        for _ in 0..size {
196            ret.push(E::random(rng));
197        }
198        ret
199    }
200
201    #[allow(unused)]
202    pub(crate) fn eval_check<H1, H2, C1, C2>(hal1: &H1, eval1: C1, hal2: &H2, eval2: C2, po2: usize)
203    where
204        H1: Hal<Elem = BabyBearElem, ExtElem = BabyBearExtElem>,
205        H2: Hal<Elem = BabyBearElem, ExtElem = BabyBearExtElem>,
206        C1: CircuitHal<H1>,
207        C2: CircuitHal<H2>,
208    {
209        let params = EvalCheckParams::new(po2);
210        let check1 = eval_check_impl(&params, hal1, &eval1);
211        let check2 = eval_check_impl(&params, hal2, &eval2);
212        assert_eq!(check1, check2);
213    }
214
215    pub fn eval_check_impl<H, C>(params: &EvalCheckParams, hal: &H, eval: &C) -> Vec<H::Elem>
216    where
217        H: Hal<Elem = BabyBearElem, ExtElem = BabyBearExtElem>,
218        C: CircuitHal<H>,
219    {
220        let check = hal.alloc_elem("check", BabyBearExtElem::EXT_SIZE * params.domain);
221        let code = hal.copy_from_elem("code", &params.code);
222        let data = hal.copy_from_elem("data", &params.data);
223        let accum = hal.copy_from_elem("accum", &params.accum);
224        let mix = hal.copy_from_elem("mix", &params.mix);
225        let out = hal.copy_from_elem("out", &params.out);
226        eval.eval_check(
227            &check,
228            &[&accum, &code, &data],
229            &[&mix, &out],
230            params.poly_mix,
231            params.po2,
232            params.steps,
233        );
234        let mut ret = vec![H::Elem::ZERO; check.size()];
235        check.view(|view| {
236            ret.clone_from_slice(view);
237        });
238        ret
239    }
240}
risc0_circuit_recursion/lib.rs

risc0_circuit_recursion/
lib.rs
