openvm_circuit/system/program/
trace.rs

1use std::borrow::BorrowMut;
2
3use itertools::Itertools;
4use openvm_circuit::{arch::hasher::poseidon2::Poseidon2Hasher, primitives::Chip};
5use openvm_cpu_backend::CpuBackend;
6use openvm_instructions::{
7    exe::VmExe,
8    program::{Program, DEFAULT_PC_STEP},
9    LocalOpcode, SystemOpcode,
10};
11use openvm_stark_backend::{
12    p3_field::{Field, PrimeCharacteristicRing, PrimeField32},
13    p3_matrix::dense::RowMajorMatrix,
14    p3_maybe_rayon::prelude::*,
15    prover::AirProvingContext,
16    StarkProtocolConfig, Val,
17};
18
19use super::{Instruction, ProgramExecutionCols, EXIT_CODE_FAIL};
20use crate::{
21    arch::{
22        hasher::{poseidon2::vm_poseidon2_hasher, Hasher},
23        MemoryConfig,
24    },
25    system::{
26        memory::{merkle::MerkleTree, AddressMap, CHUNK},
27        program::ProgramChip,
28    },
29};
30
31impl<SC: StarkProtocolConfig> Chip<(), CpuBackend<SC>> for ProgramChip<SC> {
32    /// The cached program trace is cloned and left for future use. The clone is cheap because the
33    /// cached trace is behind smart pointers. The execution frequencies are left unchanged.
34    fn generate_proving_ctx(&self, _: ()) -> AirProvingContext<CpuBackend<SC>> {
35        let cached = self
36            .cached
37            .clone()
38            .expect("cached program trace must be loaded");
39        assert!(self.filtered_exec_frequencies.len() <= cached.height());
40        let mut freqs = Val::<SC>::zero_vec(cached.height());
41        freqs
42            .par_iter_mut()
43            .zip(self.filtered_exec_frequencies.par_iter())
44            .for_each(|(f, x)| *f = Val::<SC>::from_u32(*x));
45        let common_trace = RowMajorMatrix::new(freqs, 1);
46        AirProvingContext {
47            cached_mains: vec![cached],
48            common_main: common_trace,
49            public_values: vec![],
50        }
51    }
52}
53
54/// Computes a commitment to a VM executable. This is a Merklelized hash of:
55/// - Program code commitment (commitment of the cached trace)
56/// - Merkle root of the initial memory
57/// - Starting program counter (`pc_start`)
58///
59/// The program code commitment is itself a commitment (via the proof system PCS) to
60/// the program code.
61///
62/// The Merklelization uses Poseidon2 as a cryptographic hash function (for the leaves)
63/// and a cryptographic compression function (for internal nodes).
64///
65/// **Note**: This function recomputes the Merkle tree for the initial memory image.
66pub fn compute_exe_commit_from_mem_config<F: PrimeField32>(
67    program_commitment: &[F; CHUNK],
68    exe: &VmExe<F>,
69    memory_config: &MemoryConfig,
70) -> [F; CHUNK] {
71    let hasher = vm_poseidon2_hasher();
72    let memory_dimensions = memory_config.memory_dimensions();
73    let mut memory_image = AddressMap::new(memory_config.addr_spaces.clone());
74    memory_image.set_from_sparse(&exe.init_memory);
75    let init_memory_commit =
76        MerkleTree::from_memory(&memory_image, &memory_dimensions, &hasher).root();
77    compute_exe_commit(
78        &hasher,
79        program_commitment,
80        &init_memory_commit,
81        F::from_u32(exe.pc_start),
82    )
83}
84
85/// Computes a Merklelized hash of:
86/// - Program code commitment (commitment of the cached trace)
87/// - Merkle root of the initial memory
88/// - Starting program counter (`pc_start`)
89///
90/// The Merklelization uses [Poseidon2Hasher] as a cryptographic hash function (for the leaves)
91/// and a cryptographic compression function (for internal nodes).
92pub fn compute_exe_commit<F: PrimeField32>(
93    hasher: &Poseidon2Hasher<F>,
94    program_commit: &[F; CHUNK],
95    init_memory_root: &[F; CHUNK],
96    pc_start: F,
97) -> [F; CHUNK] {
98    let mut padded_pc_start = [F::ZERO; CHUNK];
99    padded_pc_start[0] = pc_start;
100    let program_hash = hasher.hash(program_commit);
101    let memory_hash = hasher.hash(init_memory_root);
102    let pc_hash = hasher.hash(&padded_pc_start);
103    hasher.compress(&hasher.compress(&program_hash, &memory_hash), &pc_hash)
104}
105
106pub(crate) fn generate_cached_trace<F: Field>(program: &Program<F>) -> RowMajorMatrix<F> {
107    let width = ProgramExecutionCols::<F>::width();
108    let mut instructions = program
109        .enumerate_by_pc()
110        .into_iter()
111        .map(|(pc, instruction, _)| (pc, instruction))
112        .collect_vec();
113
114    let padding = padding_instruction();
115    while !instructions.len().is_power_of_two() {
116        instructions.push((
117            program.pc_base + instructions.len() as u32 * DEFAULT_PC_STEP,
118            padding.clone(),
119        ));
120    }
121
122    let mut rows = F::zero_vec(instructions.len() * width);
123    rows.par_chunks_mut(width)
124        .zip(instructions)
125        .for_each(|(row, (pc, instruction))| {
126            let row: &mut ProgramExecutionCols<F> = row.borrow_mut();
127            *row = ProgramExecutionCols {
128                pc: F::from_u32(pc),
129                opcode: instruction.opcode.to_field(),
130                a: instruction.a,
131                b: instruction.b,
132                c: instruction.c,
133                d: instruction.d,
134                e: instruction.e,
135                f: instruction.f,
136                g: instruction.g,
137            };
138        });
139
140    RowMajorMatrix::new(rows, width)
141}
142
143pub(super) fn padding_instruction<F: Field>() -> Instruction<F> {
144    Instruction::from_usize(
145        SystemOpcode::TERMINATE.global_opcode(),
146        [0, 0, EXIT_CODE_FAIL],
147    )
148}
openvm_circuit/system/program/trace.rs

openvm_circuit/system/program/
trace.rs
