sp1_core_executor/
program.rs

1//! Programs that can be executed by the SP1 zkVM.
2
3use std::{fs::File, io::Read, str::FromStr};
4
5use crate::{
6    disassembler::{transpile, Elf},
7    instruction::Instruction,
8    RiscvAirId,
9};
10use hashbrown::HashMap;
11use serde::{Deserialize, Serialize};
12use slop_algebra::{Field, PrimeField32};
13use slop_maybe_rayon::prelude::{IntoParallelIterator, ParallelBridge, ParallelIterator};
14use sp1_hypercube::{
15    air::{MachineAir, MachineProgram},
16    septic_curve::{SepticCurve, SepticCurveComplete},
17    septic_digest::SepticDigest,
18    shape::Shape,
19    InteractionKind,
20};
21use sp1_primitives::consts::split_page_idx;
22use std::sync::Arc;
23
24/// The maximum number of instructions in a program.
25pub const MAX_PROGRAM_SIZE: usize = 1 << 22;
26
27/// A program that can be executed by the SP1 zkVM.
28///
29/// Contains a series of instructions along with the initial memory image. It also contains the
30/// start address and base address of the program.
31#[derive(Debug, Clone, Default, Serialize, Deserialize, deepsize2::DeepSizeOf)]
32pub struct Program {
33    /// The instructions of the program.
34    pub instructions: Vec<Instruction>,
35    /// The encoded instructions of the program. Only used if program is untrusted
36    pub instructions_encoded: Option<Vec<u32>>,
37    /// The start address of the program. It is absolute, meaning not relative to `pc_base`.
38    pub pc_start_abs: u64,
39    /// The base address of the program.
40    pub pc_base: u64,
41    /// The initial page protection image, mapping page indices to protection flags.
42    pub page_prot_image: HashMap<u64, u8>,
43    /// The initial memory image, useful for global constants
44    pub memory_image: Arc<HashMap<u64, u64>>,
45    /// The shape for the preprocessed tables.
46    pub preprocessed_shape: Option<Shape<RiscvAirId>>,
47    /// Flag indicating if untrusted programs are allowed.
48    pub enable_untrusted_programs: bool,
49    /// Function symbols for profiling & debugging. In the form of (name, start address, size)
50    pub function_symbols: Vec<(String, u64, u64)>,
51}
52
53impl Program {
54    /// Create a new [Program].
55    #[must_use]
56    pub fn new(instructions: Vec<Instruction>, pc_start_abs: u64, pc_base: u64) -> Self {
57        assert!(!instructions.is_empty(), "empty program not supported");
58        assert!(instructions.len() <= (1 << 22), "program has too many instructions");
59
60        Self {
61            instructions,
62            instructions_encoded: None,
63            pc_start_abs,
64            pc_base,
65            page_prot_image: HashMap::new(),
66            memory_image: Arc::new(HashMap::new()),
67            preprocessed_shape: None,
68            enable_untrusted_programs: false,
69            function_symbols: Vec::new(),
70        }
71    }
72
73    /// Disassemble a RV64IM ELF to a program that be executed by the VM.
74    ///
75    /// # Errors
76    ///
77    /// This function may return an error if the ELF is not valid.
78    pub fn from(input: &[u8]) -> eyre::Result<Self> {
79        // Decode the bytes as an ELF.
80        let elf = Elf::decode(input)?;
81
82        if elf.pc_base < 32 {
83            eyre::bail!("elf with pc_base < 32 is not supported");
84        }
85        if elf.pc_base % 4 != 0 {
86            eyre::bail!("elf with pc_base not a multiple of 4 is not supported");
87        }
88
89        // Transpile the RV64IM instructions.
90        let instruction_pair = transpile(&elf.instructions);
91        let (instructions, instructions_encoded): (Vec<Instruction>, Vec<u32>) =
92            instruction_pair.into_iter().unzip();
93
94        if instructions.is_empty() {
95            eyre::bail!("empty elf not supported");
96        }
97        if instructions.len() > (1 << 22) {
98            eyre::bail!("elf has too many instructions");
99        }
100
101        // Return the program.
102        Ok(Program {
103            instructions,
104            instructions_encoded: Some(instructions_encoded),
105            pc_start_abs: elf.pc_start,
106            pc_base: elf.pc_base,
107            memory_image: elf.memory_image,
108            page_prot_image: elf.page_prot_image,
109            preprocessed_shape: None,
110            enable_untrusted_programs: elf.enable_untrusted_programs,
111            function_symbols: elf.function_symbols,
112        })
113    }
114
115    /// Disassemble a RV64IM ELF to a program that be executed by the VM from a file path.
116    ///
117    /// # Errors
118    ///
119    /// This function will return an error if the file cannot be opened or read.
120    pub fn from_elf(path: &str) -> eyre::Result<Self> {
121        let mut elf_code = Vec::new();
122        File::open(path)?.read_to_end(&mut elf_code)?;
123        Program::from(&elf_code)
124    }
125
126    /// Custom logic for padding the trace to a power of two according to the proof shape.
127    pub fn fixed_log2_rows<F: Field, A: MachineAir<F>>(&self, air: &A) -> Option<usize> {
128        let id = RiscvAirId::from_str(air.name()).unwrap();
129        self.preprocessed_shape.as_ref().map(|shape| {
130            shape
131                .log2_height(&id)
132                .unwrap_or_else(|| panic!("Chip {} not found in specified shape", air.name()))
133        })
134    }
135
136    #[must_use]
137    /// Fetch the instruction at the given program counter.
138    pub fn fetch(&self, pc: u64) -> Option<&Instruction> {
139        let idx = ((pc - self.pc_base) / 4) as usize;
140        self.instructions.get(idx)
141    }
142}
143
144impl<F: PrimeField32> MachineProgram<F> for Program {
145    fn pc_start(&self) -> [F; 3] {
146        [
147            F::from_canonical_u16((self.pc_start_abs & 0xFFFF) as u16),
148            F::from_canonical_u16(((self.pc_start_abs >> 16) & 0xFFFF) as u16),
149            F::from_canonical_u16(((self.pc_start_abs >> 32) & 0xFFFF) as u16),
150        ]
151    }
152
153    fn initial_global_cumulative_sum(&self) -> SepticDigest<F> {
154        let mut memory_digests: Vec<SepticCurveComplete<F>> = self
155            .memory_image
156            .iter()
157            .par_bridge()
158            .map(|(&addr, &word)| {
159                let limb_1 = (word & 0xFFFF) as u32 + (1 << 16) * ((word >> 32) & 0xFF) as u32;
160                let limb_2 =
161                    ((word >> 16) & 0xFFFF) as u32 + (1 << 16) * ((word >> 40) & 0xFF) as u32;
162                let values = [
163                    (InteractionKind::Memory as u32) << 24,
164                    0,
165                    (addr & 0xFFFF) as u32,
166                    ((addr >> 16) & 0xFFFF) as u32,
167                    ((addr >> 32) & 0xFFFF) as u32,
168                    limb_1,
169                    limb_2,
170                    ((word >> 48) & 0xFFFF) as u32,
171                ];
172                let (point, _, _, _) =
173                    SepticCurve::<F>::lift_x(values.map(|x| F::from_canonical_u32(x)));
174                SepticCurveComplete::Affine(point.neg())
175            })
176            .collect();
177
178        if self.enable_untrusted_programs {
179            let page_prot_digests: Vec<SepticCurveComplete<F>> = self
180                .page_prot_image
181                .iter()
182                .par_bridge()
183                .map(|(&page_idx, &page_prot)| {
184                    // Use exact same encoding as PageProtGlobalChip Initialize events
185                    let page_idx_limbs = split_page_idx(page_idx);
186                    let values = [
187                        (InteractionKind::PageProtAccess as u32) << 24,
188                        0,
189                        page_idx_limbs[0].into(),
190                        page_idx_limbs[1].into(),
191                        page_idx_limbs[2].into(),
192                        page_prot.into(),
193                        0,
194                        0,
195                    ];
196                    let (point, _, _, _) =
197                        SepticCurve::<F>::lift_x(values.map(|x| F::from_canonical_u32(x)));
198                    SepticCurveComplete::Affine(point.neg())
199                })
200                .collect();
201
202            // Combine both memory and page protection contributions.
203            memory_digests.extend(page_prot_digests);
204        }
205
206        memory_digests.push(SepticCurveComplete::Affine(SepticDigest::<F>::zero().0));
207        SepticDigest(
208            memory_digests
209                .into_par_iter()
210                .reduce(|| SepticCurveComplete::Infinity, |a, b| a + b)
211                .point(),
212        )
213    }
214
215    fn enable_untrusted_programs(&self) -> F {
216        F::from_bool(self.enable_untrusted_programs)
217    }
218}
sp1_core_executor/program.rs

sp1_core_executor/
program.rs
