miden_processor/trace/
mod.rs

1use alloc::vec::Vec;
2#[cfg(any(test, feature = "testing"))]
3use core::ops::Range;
4
5use miden_air::{
6    MidenMultiAir, ProverStatement, PublicInputs, StarkConfig, Statement, config, debug,
7    trace::{MainTrace, decoder::NUM_USER_OP_HELPERS},
8};
9use miden_core::{crypto::hash::Blake3_256, serde::Serializable};
10
11use crate::{
12    Felt, MIN_STACK_DEPTH, Program, ProgramInfo, StackInputs, StackOutputs, Word, ZERO,
13    fast::ExecutionOutput,
14    field::QuadFelt,
15    precompile::{PrecompileRequest, PrecompileTranscript},
16    utils::RowMajorMatrix,
17};
18
19pub(crate) mod utils;
20use utils::ChipletTraceFragment;
21
22pub mod chiplets;
23pub(crate) mod execution_tracer;
24
25mod block_stack;
26mod parallel;
27mod range;
28mod stack;
29mod trace_state;
30
31#[cfg(test)]
32mod tests;
33
34// RE-EXPORTS
35// ================================================================================================
36
37pub use execution_tracer::TraceGenerationContext;
38pub use miden_air::trace::RowIndex;
39pub use parallel::{CORE_TRACE_WIDTH, build_trace, build_trace_with_max_len};
40pub use utils::{ChipletsLengths, TraceLenSummary};
41
42/// Inputs required to build an execution trace from pre-executed data.
43#[derive(Debug)]
44pub struct TraceBuildInputs {
45    trace_output: TraceBuildOutput,
46    trace_generation_context: TraceGenerationContext,
47    program_info: ProgramInfo,
48}
49
50#[derive(Debug)]
51pub(crate) struct TraceBuildOutput {
52    stack_outputs: StackOutputs,
53    final_precompile_transcript: PrecompileTranscript,
54    precompile_requests: Vec<PrecompileRequest>,
55    precompile_requests_digest: [u8; 32],
56}
57
58impl TraceBuildOutput {
59    fn from_execution_output(execution_output: ExecutionOutput) -> Self {
60        let ExecutionOutput {
61            stack,
62            mut advice,
63            memory: _,
64            final_precompile_transcript,
65        } = execution_output;
66
67        Self {
68            stack_outputs: stack,
69            final_precompile_transcript,
70            precompile_requests: advice.take_precompile_requests(),
71            precompile_requests_digest: [0; 32],
72        }
73        .with_precompile_requests_digest()
74    }
75
76    fn with_precompile_requests_digest(mut self) -> Self {
77        self.precompile_requests_digest =
78            Blake3_256::hash(&self.precompile_requests.to_bytes()).into();
79        self
80    }
81
82    fn has_matching_precompile_requests_digest(&self) -> bool {
83        let expected_digest: [u8; 32] =
84            Blake3_256::hash(&self.precompile_requests.to_bytes()).into();
85        self.precompile_requests_digest == expected_digest
86    }
87}
88
89impl TraceBuildInputs {
90    pub(crate) fn from_execution(
91        program: &Program,
92        execution_output: ExecutionOutput,
93        trace_generation_context: TraceGenerationContext,
94    ) -> Self {
95        let trace_output = TraceBuildOutput::from_execution_output(execution_output);
96        let program_info = program.to_info();
97        Self {
98            trace_output,
99            trace_generation_context,
100            program_info,
101        }
102    }
103
104    /// Returns the stack outputs captured for the execution being replayed.
105    pub fn stack_outputs(&self) -> &StackOutputs {
106        &self.trace_output.stack_outputs
107    }
108
109    /// Returns deferred precompile requests generated during execution.
110    pub fn precompile_requests(&self) -> &[PrecompileRequest] {
111        &self.trace_output.precompile_requests
112    }
113
114    /// Returns the final precompile transcript observed during execution.
115    pub fn final_precompile_transcript(&self) -> &PrecompileTranscript {
116        &self.trace_output.final_precompile_transcript
117    }
118
119    /// Returns the program info captured for the execution being replayed.
120    pub fn program_info(&self) -> &ProgramInfo {
121        &self.program_info
122    }
123
124    // Kept for mismatch and edge-case tests that mutate replay inputs directly.
125    #[cfg(any(test, feature = "testing"))]
126    #[cfg_attr(all(feature = "testing", not(test)), expect(dead_code))]
127    pub(crate) fn into_parts(self) -> (TraceBuildOutput, TraceGenerationContext, ProgramInfo) {
128        (self.trace_output, self.trace_generation_context, self.program_info)
129    }
130
131    #[cfg(any(test, feature = "testing"))]
132    /// Returns the trace replay context captured during execution.
133    pub fn trace_generation_context(&self) -> &TraceGenerationContext {
134        &self.trace_generation_context
135    }
136
137    // Kept for tests that force invalid replay contexts without widening the public API.
138    #[cfg(any(test, feature = "testing"))]
139    #[cfg_attr(all(feature = "testing", not(test)), expect(dead_code))]
140    pub(crate) fn trace_generation_context_mut(&mut self) -> &mut TraceGenerationContext {
141        &mut self.trace_generation_context
142    }
143
144    #[cfg(test)]
145    pub(crate) fn from_parts(
146        trace_output: TraceBuildOutput,
147        trace_generation_context: TraceGenerationContext,
148        program_info: ProgramInfo,
149    ) -> Self {
150        Self {
151            trace_output,
152            trace_generation_context,
153            program_info,
154        }
155    }
156}
157
158// VM EXECUTION TRACE
159// ================================================================================================
160
161/// Execution trace which is generated when a program is executed on the VM.
162///
163/// The trace consists of the following components:
164/// - Main traces of System, Decoder, Operand Stack, Range Checker, and Chiplets.
165/// - Information about the program (program hash and the kernel).
166/// - Information about execution outputs (stack state, deferred precompile requests, and the final
167///   precompile transcript).
168/// - Summary of trace lengths of the main trace components.
169#[derive(Debug)]
170pub struct ExecutionTrace {
171    main_trace: MainTrace,
172    program_info: ProgramInfo,
173    stack_outputs: StackOutputs,
174    precompile_requests: Vec<PrecompileRequest>,
175    final_precompile_transcript: PrecompileTranscript,
176    trace_len_summary: TraceLenSummary,
177}
178
179impl ExecutionTrace {
180    // CONSTRUCTOR
181    // --------------------------------------------------------------------------------------------
182
183    pub(crate) fn new_from_parts(
184        program_info: ProgramInfo,
185        trace_output: TraceBuildOutput,
186        main_trace: MainTrace,
187        trace_len_summary: TraceLenSummary,
188    ) -> Self {
189        let TraceBuildOutput {
190            stack_outputs,
191            final_precompile_transcript,
192            precompile_requests,
193            ..
194        } = trace_output;
195
196        Self {
197            main_trace,
198            program_info,
199            stack_outputs,
200            precompile_requests,
201            final_precompile_transcript,
202            trace_len_summary,
203        }
204    }
205
206    // PUBLIC ACCESSORS
207    // --------------------------------------------------------------------------------------------
208
209    /// Returns the program info of this execution trace.
210    pub fn program_info(&self) -> &ProgramInfo {
211        &self.program_info
212    }
213
214    /// Returns hash of the program execution of which resulted in this execution trace.
215    pub fn program_hash(&self) -> &Word {
216        self.program_info.program_hash()
217    }
218
219    /// Returns outputs of the program execution which resulted in this execution trace.
220    pub fn stack_outputs(&self) -> &StackOutputs {
221        &self.stack_outputs
222    }
223
224    /// Returns the public inputs for this execution trace.
225    pub fn public_inputs(&self) -> PublicInputs {
226        PublicInputs::new(
227            self.program_info.clone(),
228            self.init_stack_state(),
229            self.stack_outputs,
230            self.final_precompile_transcript.state(),
231        )
232    }
233
234    /// Returns the public values for this execution trace.
235    pub fn to_public_values(&self) -> Vec<Felt> {
236        self.public_inputs().to_elements()
237    }
238
239    /// Returns a reference to the main trace.
240    pub fn main_trace(&self) -> &MainTrace {
241        &self.main_trace
242    }
243
244    /// Returns a mutable reference to the main trace.
245    pub fn main_trace_mut(&mut self) -> &mut MainTrace {
246        &mut self.main_trace
247    }
248
249    /// Returns the precompile requests generated during program execution.
250    pub fn precompile_requests(&self) -> &[PrecompileRequest] {
251        &self.precompile_requests
252    }
253
254    /// Returns the final precompile transcript observed during execution.
255    pub fn final_precompile_transcript(&self) -> PrecompileTranscript {
256        self.final_precompile_transcript
257    }
258
259    /// Returns the owned execution outputs required for proof packaging.
260    pub fn into_outputs(self) -> (StackOutputs, Vec<PrecompileRequest>, PrecompileTranscript) {
261        (self.stack_outputs, self.precompile_requests, self.final_precompile_transcript)
262    }
263
264    /// Returns the initial state of the top 16 stack registers.
265    pub fn init_stack_state(&self) -> StackInputs {
266        let mut result = [ZERO; MIN_STACK_DEPTH];
267        let row = RowIndex::from(0_u32);
268        for (i, result) in result.iter_mut().enumerate() {
269            *result = self.main_trace.stack_element(i, row);
270        }
271        result.into()
272    }
273
274    /// Returns the final state of the top 16 stack registers.
275    pub fn last_stack_state(&self) -> StackOutputs {
276        let last_step = RowIndex::from(self.last_step());
277        let mut result = [ZERO; MIN_STACK_DEPTH];
278        for (i, result) in result.iter_mut().enumerate() {
279            *result = self.main_trace.stack_element(i, last_step);
280        }
281        result.into()
282    }
283
284    /// Returns helper registers state at the specified `clk` of the VM
285    pub fn get_user_op_helpers_at(&self, clk: u32) -> [Felt; NUM_USER_OP_HELPERS] {
286        let mut result = [ZERO; NUM_USER_OP_HELPERS];
287        let row = RowIndex::from(clk);
288        for (i, result) in result.iter_mut().enumerate() {
289            *result = self.main_trace.helper_register(i, row);
290        }
291        result
292    }
293
294    /// Returns the trace length.
295    pub fn get_trace_len(&self) -> usize {
296        self.main_trace.num_rows()
297    }
298
299    /// Returns the length of the trace (number of rows in the main trace).
300    pub fn length(&self) -> usize {
301        self.get_trace_len()
302    }
303
304    /// Returns a summary of the lengths of main, range and chiplet traces.
305    pub fn trace_len_summary(&self) -> &TraceLenSummary {
306        &self.trace_len_summary
307    }
308
309    // DEBUG CONSTRAINT CHECKING
310    // --------------------------------------------------------------------------------------------
311
312    /// Validates this execution trace against all AIR constraints without generating a STARK
313    /// proof.
314    ///
315    /// This is the recommended way to test trace correctness. It is much faster than full STARK
316    /// proving and provides better error diagnostics (panics on the first constraint violation
317    /// with the instance and row index).
318    ///
319    /// # Panics
320    ///
321    /// Panics if any AIR constraint evaluates to nonzero.
322    pub fn check_constraints(&self) {
323        let public_inputs = self.public_inputs();
324        let (core_matrix, chiplets_matrix) = self.main_trace.to_core_chiplets_matrices();
325
326        let (public_values, kernel_felts) = public_inputs.to_air_inputs();
327
328        let statement =
329            Statement::<Felt, QuadFelt, _>::new(MidenMultiAir::new(), public_values, kernel_felts)
330                .expect("valid statement inputs");
331        let prover_statement = ProverStatement::new(statement, vec![core_matrix, chiplets_matrix])
332            .expect("valid trace shapes");
333
334        // A deterministic challenger seeds the debug constraint check; this is a local
335        // constraint debugger, not a full proof transcript, so any fixed challenge set works.
336        let config = config::poseidon2_config(config::pcs_params());
337        debug::check_constraints(&prover_statement, config.challenger());
338    }
339
340    /// Splits the trace into the per-AIR `(Core, Chiplets)` matrix pair consumed by the
341    /// multi-AIR proving path. Strips the Poseidon2 rate-alignment padding columns
342    /// before returning.
343    pub fn to_core_chiplets_matrices(&self) -> (RowMajorMatrix<Felt>, RowMajorMatrix<Felt>) {
344        self.main_trace.to_core_chiplets_matrices()
345    }
346
347    /// Consuming variant for the proving hot path: moves the chiplets row-major buffer
348    /// instead of copying it. See [`MainTrace::into_core_chiplets_matrices`].
349    pub fn into_core_chiplets_matrices(self) -> (RowMajorMatrix<Felt>, RowMajorMatrix<Felt>) {
350        self.main_trace.into_core_chiplets_matrices()
351    }
352
353    // HELPER METHODS
354    // --------------------------------------------------------------------------------------------
355
356    /// Returns the index of the last row in the Core trace.
357    fn last_step(&self) -> usize {
358        self.main_trace.core_height() - 1
359    }
360
361    #[cfg(any(test, feature = "testing"))]
362    pub fn get_column_range(&self, range: Range<usize>) -> Vec<Vec<Felt>> {
363        self.main_trace.get_column_range(range)
364    }
365}
miden_processor/trace/mod.rs

miden_processor/trace/
mod.rs
