risc0_circuit_recursion/prove/
program.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
15use risc0_zkp::{
16    core::{digest::Digest, hash::HashSuite},
17    field::baby_bear::{BabyBear, BabyBearElem},
18    hal::{cpu::CpuHal, Hal},
19    prove::poly_group::PolyGroup,
20    ZK_CYCLES,
21};
22
23use super::RECURSION_CODE_SIZE;
24
25/// A Program for the recursion circuit (e.g. lift_20 or join).
26///
27/// The recursion circuit is an application specific virtual machine with a limited instruction
28/// set, no control flow operations, and a write-once memory tape. Although it is not general
29/// purpose, it can load and execute a program, similar to the rv32im zkVM.
30///
31/// Programs for the recursion circuit are loaded into the control columns, which is a set of
32/// public columns in the witness. Programs are therefore identified by their control ID, which is
33/// similar but not the same as the image ID used to identify rv32im programs.
34#[derive(Clone)]
35pub struct Program {
36    /// The code of the program, encoded as Baby Bear field elements.
37    pub code: Vec<BabyBearElem>,
38
39    /// The number of code columns.
40    pub code_size: usize,
41
42    /// 1 << po2 is the number of cycles executed.
43    pub po2: usize,
44}
45
46impl Program {
47    /// Create a [Program] from a stream of data encoded by Zirgen.
48    pub fn from_encoded(encoded: &[u32], po2: usize) -> Self {
49        let prog = Self {
50            code: encoded.iter().copied().map(BabyBearElem::from).collect(),
51            code_size: RECURSION_CODE_SIZE,
52            po2,
53        };
54        assert_eq!(prog.code.len() % RECURSION_CODE_SIZE, 0);
55        assert!(prog.code.len() <= (RECURSION_CODE_SIZE * (1 << po2) - ZK_CYCLES));
56        prog
57    }
58
59    /// Total number of rows in the code group for this program.
60    pub fn code_rows(&self) -> usize {
61        self.code.len() / self.code_size
62    }
63
64    /// An iterator over the rows of the code group.
65    pub fn code_by_row(&self) -> impl Iterator<Item = &[BabyBearElem]> {
66        self.code.as_slice().chunks(self.code_size)
67    }
68
69    /// Given a [Program] for the recursion circuit, compute the control ID as the FRI Merkle root
70    /// of the code group. This uniquely identifies the program running on the recursion circuit
71    /// (e.g. lift_20 or join)
72    pub fn compute_control_id(&self, hash_suite: HashSuite<BabyBear>) -> Digest {
73        let hal = CpuHal::new(hash_suite);
74        let cycles = 1 << self.po2;
75
76        let mut code = vec![BabyBearElem::default(); cycles * self.code_size];
77
78        for (cycle, row) in self.code_by_row().enumerate() {
79            for (i, elem) in row.iter().enumerate() {
80                code[cycles * i + cycle] = *elem;
81            }
82        }
83        let coeffs = hal.copy_from_elem("coeffs", &code);
84        // Do interpolate & shift
85        hal.batch_interpolate_ntt(&coeffs, self.code_size);
86        hal.zk_shift(&coeffs, self.code_size);
87        // Make the poly-group & extract the root
88        let code_group = PolyGroup::new(&hal, coeffs, self.code_size, cycles, "code");
89        let root = *code_group.merkle.root();
90        tracing::trace!("Computed recursion code: {root:?}");
91        root
92    }
93}
risc0_circuit_recursion/prove/program.rs

risc0_circuit_recursion/prove/
program.rs
