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::deferred::DeferredState;
10
11use crate::{
12    Felt, MIN_STACK_DEPTH, Program, ProgramInfo, StackInputs, StackOutputs, Word, ZERO,
13    fast::ExecutionOutput, field::QuadFelt, utils::RowMajorMatrix,
14};
15
16pub(crate) mod utils;
17use utils::ChipletTraceFragment;
18
19pub mod chiplets;
20pub(crate) mod execution_tracer;
21
22mod block_stack;
23mod parallel;
24mod range;
25mod stack;
26mod trace_state;
27
28#[cfg(test)]
29mod tests;
30
31// RE-EXPORTS
32// ================================================================================================
33
34pub use execution_tracer::TraceGenerationContext;
35pub use miden_air::trace::RowIndex;
36pub use parallel::{CORE_TRACE_WIDTH, build_trace, build_trace_with_max_len};
37// Re-exported for the streaming trace-build path
38// (`FastProcessor::execute_and_build_trace_sync`), which is std-only; the buffered path
39// uses `build_hasher_chiplet` and `MAX_TRACE_LEN` directly within `parallel`.
40#[cfg(feature = "std")]
41pub(crate) use parallel::{MAX_TRACE_LEN, build_hasher_chiplet, build_trace_with_prebuilt_hasher};
42#[cfg(feature = "std")]
43pub(crate) use trace_state::ResolvedHasherOp;
44pub use utils::{ChipletsLengths, TraceLenSummary};
45
46/// Inputs required to build an execution trace from pre-executed data.
47#[derive(Debug)]
48pub struct TraceBuildInputs {
49    trace_output: TraceBuildOutput,
50    trace_generation_context: TraceGenerationContext,
51    program_info: ProgramInfo,
52}
53
54impl TraceBuildInputs {
55    /// Takes the hasher replay out, leaving an empty buffered one.
56    ///
57    /// The streaming path uses this to drop the replay's channel sender once execution has
58    /// finished, so the concurrently running hasher builder sees its input stream end.
59    #[cfg(feature = "std")]
60    pub(crate) fn take_hasher_replay(&mut self) -> trace_state::HasherRequestReplay {
61        core::mem::take(&mut self.trace_generation_context.hasher_for_chiplet)
62    }
63}
64
65#[derive(Debug)]
66pub(crate) struct TraceBuildOutput {
67    stack_outputs: StackOutputs,
68    deferred_state: DeferredState,
69}
70
71impl TraceBuildOutput {
72    fn from_execution_output(execution_output: ExecutionOutput) -> Self {
73        let ExecutionOutput {
74            stack,
75            advice: _,
76            memory: _,
77            deferred_state,
78        } = execution_output;
79
80        Self { stack_outputs: stack, deferred_state }
81    }
82}
83
84impl TraceBuildInputs {
85    pub(crate) fn from_execution(
86        program: &Program,
87        execution_output: ExecutionOutput,
88        trace_generation_context: TraceGenerationContext,
89    ) -> Self {
90        let trace_output = TraceBuildOutput::from_execution_output(execution_output);
91        let program_info = program.to_info();
92        Self {
93            trace_output,
94            trace_generation_context,
95            program_info,
96        }
97    }
98
99    /// Returns the stack outputs captured for the execution being replayed.
100    pub fn stack_outputs(&self) -> &StackOutputs {
101        &self.trace_output.stack_outputs
102    }
103
104    /// Returns the final deferred state captured for the execution being replayed.
105    pub fn deferred_state(&self) -> &DeferredState {
106        &self.trace_output.deferred_state
107    }
108
109    /// Returns the program info captured for the execution being replayed.
110    pub fn program_info(&self) -> &ProgramInfo {
111        &self.program_info
112    }
113
114    #[cfg(any(test, feature = "testing"))]
115    /// Returns the trace replay context captured during execution.
116    pub fn trace_generation_context(&self) -> &TraceGenerationContext {
117        &self.trace_generation_context
118    }
119
120    // Kept for tests that force invalid replay contexts without widening the public API.
121    #[cfg(any(test, feature = "testing"))]
122    #[cfg_attr(all(feature = "testing", not(test)), expect(dead_code))]
123    pub(crate) fn trace_generation_context_mut(&mut self) -> &mut TraceGenerationContext {
124        &mut self.trace_generation_context
125    }
126}
127
128// VM EXECUTION TRACE
129// ================================================================================================
130
131/// Execution trace which is generated when a program is executed on the VM.
132///
133/// The trace consists of the following components:
134/// - Per-AIR trace matrices for Core, Chiplets, and Poseidon2Permutation.
135/// - Information about the program (program hash and the kernel).
136/// - Information about execution outputs (stack state and final deferred state).
137/// - Summary of trace lengths of the main trace components.
138#[derive(Debug)]
139pub struct ExecutionTrace {
140    main_trace: MainTrace,
141    program_info: ProgramInfo,
142    stack_outputs: StackOutputs,
143    deferred_state: DeferredState,
144    trace_len_summary: TraceLenSummary,
145}
146
147impl ExecutionTrace {
148    // CONSTRUCTOR
149    // --------------------------------------------------------------------------------------------
150
151    pub(crate) fn new_from_parts(
152        program_info: ProgramInfo,
153        trace_output: TraceBuildOutput,
154        main_trace: MainTrace,
155        trace_len_summary: TraceLenSummary,
156    ) -> Self {
157        let TraceBuildOutput { stack_outputs, deferred_state } = trace_output;
158
159        Self {
160            main_trace,
161            program_info,
162            stack_outputs,
163            deferred_state,
164            trace_len_summary,
165        }
166    }
167
168    // PUBLIC ACCESSORS
169    // --------------------------------------------------------------------------------------------
170
171    /// Returns the program info of this execution trace.
172    pub fn program_info(&self) -> &ProgramInfo {
173        &self.program_info
174    }
175
176    /// Returns hash of the program execution of which resulted in this execution trace.
177    pub fn program_hash(&self) -> &Word {
178        self.program_info.program_hash()
179    }
180
181    /// Returns outputs of the program execution which resulted in this execution trace.
182    pub fn stack_outputs(&self) -> &StackOutputs {
183        &self.stack_outputs
184    }
185
186    /// Returns the public inputs for this execution trace.
187    pub fn public_inputs(&self) -> PublicInputs {
188        PublicInputs::new(
189            self.program_info.clone(),
190            self.init_stack_state(),
191            self.stack_outputs,
192            self.deferred_state.root(),
193        )
194    }
195
196    /// Returns the public values for this execution trace.
197    pub fn to_public_values(&self) -> Vec<Felt> {
198        self.public_inputs().to_elements()
199    }
200
201    /// Returns a reference to the main trace.
202    pub fn main_trace(&self) -> &MainTrace {
203        &self.main_trace
204    }
205
206    /// Returns a mutable reference to the main trace.
207    pub fn main_trace_mut(&mut self) -> &mut MainTrace {
208        &mut self.main_trace
209    }
210
211    /// Returns the final deferred state generated during program execution.
212    pub fn deferred_state(&self) -> &DeferredState {
213        &self.deferred_state
214    }
215
216    /// Returns the owned stack outputs required for proof packaging.
217    pub fn into_outputs(self) -> StackOutputs {
218        self.stack_outputs
219    }
220
221    /// Returns the initial state of the top 16 stack registers.
222    pub fn init_stack_state(&self) -> StackInputs {
223        let mut result = [ZERO; MIN_STACK_DEPTH];
224        let row = RowIndex::from(0_u32);
225        for (i, result) in result.iter_mut().enumerate() {
226            *result = self.main_trace.stack_element(i, row);
227        }
228        result.into()
229    }
230
231    /// Returns the final state of the top 16 stack registers.
232    pub fn last_stack_state(&self) -> StackOutputs {
233        let last_step = RowIndex::from(self.last_step());
234        let mut result = [ZERO; MIN_STACK_DEPTH];
235        for (i, result) in result.iter_mut().enumerate() {
236            *result = self.main_trace.stack_element(i, last_step);
237        }
238        result.into()
239    }
240
241    /// Returns helper registers state at the specified `clk` of the VM
242    pub fn get_user_op_helpers_at(&self, clk: u32) -> [Felt; NUM_USER_OP_HELPERS] {
243        let mut result = [ZERO; NUM_USER_OP_HELPERS];
244        let row = RowIndex::from(clk);
245        for (i, result) in result.iter_mut().enumerate() {
246            *result = self.main_trace.helper_register(i, row);
247        }
248        result
249    }
250
251    /// Returns the trace length.
252    pub fn get_trace_len(&self) -> usize {
253        self.main_trace.num_rows()
254    }
255
256    /// Returns the length of the trace (number of rows in the main trace).
257    pub fn length(&self) -> usize {
258        self.get_trace_len()
259    }
260
261    /// Returns a summary of the per-component trace lengths.
262    pub fn trace_len_summary(&self) -> &TraceLenSummary {
263        &self.trace_len_summary
264    }
265
266    // DEBUG CONSTRAINT CHECKING
267    // --------------------------------------------------------------------------------------------
268
269    /// Validates this execution trace against all AIR constraints without generating a STARK
270    /// proof.
271    ///
272    /// This is the recommended way to test trace correctness. It is much faster than full STARK
273    /// proving and provides better error diagnostics (panics on the first constraint violation
274    /// with the instance and row index).
275    ///
276    /// # Panics
277    ///
278    /// Panics if any AIR constraint evaluates to nonzero.
279    pub fn check_constraints(&self) {
280        let public_inputs = self.public_inputs();
281        let (core_matrix, chiplets_matrix, poseidon2_matrix) = self.main_trace.to_air_matrices();
282
283        let (public_values, aux_inputs) = public_inputs.to_air_inputs();
284
285        let statement =
286            Statement::<Felt, QuadFelt, _>::new(MidenMultiAir::new(), public_values, aux_inputs)
287                .expect("valid statement inputs");
288        let prover_statement =
289            ProverStatement::new(statement, vec![core_matrix, chiplets_matrix, poseidon2_matrix])
290                .expect("valid trace shapes");
291
292        // A deterministic challenger seeds the debug constraint check; this is a local
293        // constraint debugger, not a full proof transcript, so any fixed challenge set works.
294        let config = config::poseidon2_config(config::pcs_params(), config::RELATION_DIGEST);
295        debug::check_constraints(&prover_statement, config.challenger());
296    }
297
298    /// Splits the trace into the per-AIR matrices consumed by the multi-AIR proving path.
299    pub fn to_air_matrices(
300        &self,
301    ) -> (RowMajorMatrix<Felt>, RowMajorMatrix<Felt>, RowMajorMatrix<Felt>) {
302        self.main_trace.to_air_matrices()
303    }
304
305    /// Consuming variant for the proving hot path.
306    pub fn into_air_matrices(
307        self,
308    ) -> (RowMajorMatrix<Felt>, RowMajorMatrix<Felt>, RowMajorMatrix<Felt>) {
309        self.main_trace.into_air_matrices()
310    }
311
312    // HELPER METHODS
313    // --------------------------------------------------------------------------------------------
314
315    /// Returns the index of the last row in the Core trace.
316    fn last_step(&self) -> usize {
317        self.main_trace.core_height() - 1
318    }
319
320    #[cfg(any(test, feature = "testing"))]
321    pub fn get_column_range(&self, range: Range<usize>) -> Vec<Vec<Felt>> {
322        self.main_trace.get_column_range(range)
323    }
324}
miden_processor/trace/mod.rs

miden_processor/trace/
mod.rs
