risc0_circuit_recursion/
lib.rs

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

risc0_circuit_recursion/
lib.rs
