miden_processor/trace/
mod.rs

1use alloc::vec::Vec;
2#[cfg(any(test, feature = "testing"))]
3use core::ops::Range;
4
5#[cfg(feature = "std")]
6use miden_air::trace::PADDED_TRACE_WIDTH;
7use miden_air::{
8    PublicInputs,
9    trace::{
10        AuxTraceBuilder, DECODER_TRACE_OFFSET, MainTrace, STACK_TRACE_OFFSET,
11        decoder::{NUM_USER_OP_HELPERS, USER_OP_HELPERS_OFFSET},
12    },
13};
14
15use crate::{
16    AdviceProvider, Felt, MIN_STACK_DEPTH, ProgramInfo, StackInputs, StackOutputs, Word, ZERO,
17    fast::ExecutionOutput,
18    field::ExtensionField,
19    precompile::{PrecompileRequest, PrecompileTranscript},
20    utils::{ColMatrix, Matrix, RowMajorMatrix},
21};
22
23pub(crate) mod utils;
24use utils::{AuxColumnBuilder, TraceFragment};
25
26pub mod chiplets;
27pub mod execution_tracer;
28
29mod decoder;
30mod parallel;
31mod range;
32mod row_major_adapter;
33mod stack;
34mod trace_state;
35
36#[cfg(test)]
37mod tests;
38
39// RE-EXPORTS
40// ================================================================================================
41
42pub use miden_air::trace::RowIndex;
43pub use parallel::{CORE_TRACE_WIDTH, build_trace};
44pub use utils::{ChipletsLengths, TraceLenSummary};
45
46// VM EXECUTION TRACE
47// ================================================================================================
48
49/// Execution trace which is generated when a program is executed on the VM.
50///
51/// The trace consists of the following components:
52/// - Main traces of System, Decoder, Operand Stack, Range Checker, and Chiplets.
53/// - Auxiliary trace builders.
54/// - Information about the program (program hash and the kernel).
55/// - Information about execution outputs (stack state, advice provider, and precompile transcript).
56/// - Summary of trace lengths of the main trace components.
57#[derive(Debug)]
58pub struct ExecutionTrace {
59    main_trace: MainTrace,
60    aux_trace_builders: AuxTraceBuilders,
61    program_info: ProgramInfo,
62    stack_outputs: StackOutputs,
63    advice: AdviceProvider,
64    final_pc_transcript: PrecompileTranscript,
65    trace_len_summary: TraceLenSummary,
66}
67
68impl ExecutionTrace {
69    // CONSTRUCTOR
70    // --------------------------------------------------------------------------------------------
71
72    pub fn new_from_parts(
73        program_info: ProgramInfo,
74        execution_output: ExecutionOutput,
75        main_trace: MainTrace,
76        aux_trace_builders: AuxTraceBuilders,
77        trace_len_summary: TraceLenSummary,
78    ) -> Self {
79        Self {
80            main_trace,
81            aux_trace_builders,
82            program_info,
83            stack_outputs: execution_output.stack,
84            advice: execution_output.advice,
85            final_pc_transcript: execution_output.final_pc_transcript,
86            trace_len_summary,
87        }
88    }
89
90    // PUBLIC ACCESSORS
91    // --------------------------------------------------------------------------------------------
92
93    /// Returns the program info of this execution trace.
94    pub fn program_info(&self) -> &ProgramInfo {
95        &self.program_info
96    }
97
98    /// Returns hash of the program execution of which resulted in this execution trace.
99    pub fn program_hash(&self) -> &Word {
100        self.program_info.program_hash()
101    }
102
103    /// Returns outputs of the program execution which resulted in this execution trace.
104    pub fn stack_outputs(&self) -> &StackOutputs {
105        &self.stack_outputs
106    }
107
108    /// Returns the public values for this execution trace.
109    pub fn to_public_values(&self) -> Vec<Felt> {
110        let public_inputs = PublicInputs::new(
111            self.program_info.clone(),
112            self.init_stack_state(),
113            self.stack_outputs,
114            self.final_pc_transcript.state(),
115        );
116        public_inputs.to_elements()
117    }
118
119    /// Returns a clone of the auxiliary trace builders.
120    pub fn aux_trace_builders(&self) -> AuxTraceBuilders {
121        self.aux_trace_builders.clone()
122    }
123
124    /// Returns a reference to the main trace.
125    pub fn main_trace(&self) -> &MainTrace {
126        &self.main_trace
127    }
128
129    /// Returns a mutable reference to the main trace.
130    pub fn main_trace_mut(&mut self) -> &mut MainTrace {
131        &mut self.main_trace
132    }
133
134    /// Returns the precompile requests generated during program execution.
135    pub fn precompile_requests(&self) -> &[PrecompileRequest] {
136        self.advice.precompile_requests()
137    }
138
139    /// Moves all accumulated precompile requests out of the trace, leaving it empty.
140    ///
141    /// Intended for proof packaging, where requests are serialized into the proof and no longer
142    /// needed in the trace after consumption.
143    pub fn take_precompile_requests(&mut self) -> Vec<PrecompileRequest> {
144        self.advice.take_precompile_requests()
145    }
146
147    /// Returns the final precompile transcript after executing all precompile requests.
148    pub fn final_precompile_transcript(&self) -> PrecompileTranscript {
149        self.final_pc_transcript
150    }
151
152    /// Returns the initial state of the top 16 stack registers.
153    pub fn init_stack_state(&self) -> StackInputs {
154        let mut result = [ZERO; MIN_STACK_DEPTH];
155        for (i, result) in result.iter_mut().enumerate() {
156            *result = self.main_trace.get_column(i + STACK_TRACE_OFFSET)[0];
157        }
158        result.into()
159    }
160
161    /// Returns the final state of the top 16 stack registers.
162    pub fn last_stack_state(&self) -> StackOutputs {
163        let last_step = self.last_step();
164        let mut result = [ZERO; MIN_STACK_DEPTH];
165        for (i, result) in result.iter_mut().enumerate() {
166            *result = self.main_trace.get_column(i + STACK_TRACE_OFFSET)[last_step];
167        }
168        result.into()
169    }
170
171    /// Returns helper registers state at the specified `clk` of the VM
172    pub fn get_user_op_helpers_at(&self, clk: u32) -> [Felt; NUM_USER_OP_HELPERS] {
173        let mut result = [ZERO; NUM_USER_OP_HELPERS];
174        for (i, result) in result.iter_mut().enumerate() {
175            *result = self.main_trace.get_column(DECODER_TRACE_OFFSET + USER_OP_HELPERS_OFFSET + i)
176                [clk as usize];
177        }
178        result
179    }
180
181    /// Returns the trace length.
182    pub fn get_trace_len(&self) -> usize {
183        self.main_trace.num_rows()
184    }
185
186    /// Returns the length of the trace (number of rows in the main trace).
187    pub fn length(&self) -> usize {
188        self.get_trace_len()
189    }
190
191    /// Returns a summary of the lengths of main, range and chiplet traces.
192    pub fn trace_len_summary(&self) -> &TraceLenSummary {
193        &self.trace_len_summary
194    }
195
196    /// Returns the final advice provider state.
197    pub fn advice_provider(&self) -> &AdviceProvider {
198        &self.advice
199    }
200
201    /// Destructures this execution trace into the process’s final stack and advice states.
202    pub fn into_outputs(self) -> (StackOutputs, AdviceProvider) {
203        (self.stack_outputs, self.advice)
204    }
205
206    // HELPER METHODS
207    // --------------------------------------------------------------------------------------------
208
209    /// Returns the index of the last row in the trace.
210    fn last_step(&self) -> usize {
211        self.length() - 1
212    }
213
214    // TEST HELPERS
215    // --------------------------------------------------------------------------------------------
216    #[cfg(feature = "std")]
217    pub fn print(&self) {
218        use miden_air::trace::TRACE_WIDTH;
219        use miden_core::field::PrimeField64;
220
221        let mut row = [ZERO; PADDED_TRACE_WIDTH];
222        for i in 0..self.length() {
223            self.main_trace.read_row_into(i, &mut row);
224            std::println!(
225                "{:?}",
226                row.iter().take(TRACE_WIDTH).map(|v| v.as_canonical_u64()).collect::<Vec<_>>()
227            );
228        }
229    }
230
231    #[cfg(any(test, feature = "testing"))]
232    pub fn get_column_range(&self, range: Range<usize>) -> Vec<Vec<Felt>> {
233        self.main_trace.get_column_range(range)
234    }
235
236    pub fn build_aux_trace<E>(&self, rand_elements: &[E]) -> Option<ColMatrix<E>>
237    where
238        E: ExtensionField<Felt>,
239    {
240        let aux_columns =
241            self.aux_trace_builders.build_aux_columns(&self.main_trace, rand_elements);
242
243        Some(ColMatrix::new(aux_columns))
244    }
245}
246
247// AUX TRACE BUILDERS
248// ================================================================================================
249
250#[derive(Debug, Clone)]
251pub struct AuxTraceBuilders {
252    pub(crate) decoder: decoder::AuxTraceBuilder,
253    pub(crate) stack: stack::AuxTraceBuilder,
254    pub(crate) range: range::AuxTraceBuilder,
255    pub(crate) chiplets: chiplets::AuxTraceBuilder,
256}
257
258impl AuxTraceBuilders {
259    /// Builds auxiliary columns for all trace segments given the main trace and challenges.
260    ///
261    /// This is the internal column-major version used by the processor.
262    pub fn build_aux_columns<E>(&self, main_trace: &MainTrace, challenges: &[E]) -> Vec<Vec<E>>
263    where
264        E: ExtensionField<Felt>,
265    {
266        let decoder_cols = self.decoder.build_aux_columns(main_trace, challenges);
267        let stack_cols = self.stack.build_aux_columns(main_trace, challenges);
268        let range_cols = self.range.build_aux_columns(main_trace, challenges);
269        let chiplets_cols = self.chiplets.build_aux_columns(main_trace, challenges);
270
271        decoder_cols
272            .into_iter()
273            .chain(stack_cols)
274            .chain(range_cols)
275            .chain(chiplets_cols)
276            .collect()
277    }
278}
279
280// PLONKY3 AUX TRACE BUILDER ADAPTER
281// ================================================================================================
282//
283// The `AuxTraceBuilder` trait is defined in `miden-air` to avoid a circular dependency:
284// `miden-prover-p3` needs aux trace building logic from `miden-processor`, but `miden-processor`
285// already depends on `miden-air`. By defining the trait in `miden-air` and implementing it here,
286// `miden-prover-p3` can depend on both crates and use the trait without creating a cycle.
287//
288// Additionally, Plonky3 uses row-major matrices while our existing aux trace building logic uses
289// column-major format. This impl adapts between the two by converting the main trace from
290// row-major to column-major, delegating to the existing logic, and converting the result back.
291
292impl<EF: ExtensionField<Felt>> AuxTraceBuilder<EF> for AuxTraceBuilders {
293    /// Builds auxiliary trace columns from a row-major main trace.
294    ///
295    /// This adapts the column-major `build_aux_columns` method to work with Plonky3's
296    /// row-major format by converting the input and output accordingly.
297    fn build_aux_columns(
298        &self,
299        main_trace: &RowMajorMatrix<Felt>,
300        challenges: &[EF],
301    ) -> RowMajorMatrix<Felt> {
302        let _span = tracing::info_span!("build_aux_columns_wrapper").entered();
303
304        // Convert row-major to column-major MainTrace
305        let main_trace_col_major = row_major_adapter::row_major_to_main_trace(main_trace);
306
307        // Build auxiliary columns using column-major logic
308        let aux_columns = self.build_aux_columns(&main_trace_col_major, challenges);
309
310        // Convert column-major aux columns back to row-major
311        row_major_adapter::aux_columns_to_row_major(aux_columns, main_trace.height())
312    }
313}
miden_processor/trace/mod.rs

miden_processor/trace/
mod.rs
