Struct winter_prover::ExecutionTrace

pub struct ExecutionTrace<B: StarkField> { /* fields omitted */ }

An execution trace of a computation.

Execution trace is a two-dimensional matrix in which each row represents the state of a computation at a single point in time and each column corresponds to an algebraic register tracked over all steps of the computation.

There are two ways to create an execution trace.

First, you can use the ExecutionTrace::init() function which takes a set of vectors as a parameter, where each vector contains values for a given column of the trace. This approach allows you to build an execution trace as you see fit, as long as it meets a basic set of requirements. These requirements are:

1. Lengths of all columns in the execution trace must be the same.
2. The length of the columns must be some power of two.

The other approach is to use ExecutionTrace::new() function, which takes trace width and length as parameters. This function will allocate memory for the trace, but will not fill it with data. To fill the execution trace, you can use the fill() method, which takes two closures as parameters:

1. The first closure is responsible for initializing the first state of the computation (the first row of the execution trace).
2. The second closure receives the previous state of the execution trace as input, and must update it to the next state of the computation.

You can also use ExecutionTrace::with_meta() function to create a blank execution trace. This function work just like ExecutionTrace::new() function, but also takes a metadata parameter which can be an arbitrary sequence of bytes up to 64KB in size.

Concurrent trace generation

For computations which consist of many small independent computations, we can generate the execution trace of the entire computation by building fragments of the trace in parallel, and then joining these fragments together.

For this purpose, ExecutionTrace struct exposes fragments() method, which takes fragment length as a parameter, breaks the execution trace into equally sized fragments, and returns an iterator over these fragments. You can then use fragment’s fill() method to fill all fragments with data in parallel. The semantics of the fragment’s ExecutionTraceFragment::fill() method are identical to the semantics of the ExecutionTrace::fill() method.

Implementations

impl<B: StarkField> ExecutionTrace<B>

pub fn new(width: usize, length: usize) -> Self

Creates a new execution trace of the specified width and length.

This allocates all the required memory for the trace, but does not initialize it. It is expected that the trace will be filled using one of the data mutator methods.

Panics

Panics if:

• width is zero or greater than 255.
• length is smaller than 8, greater than biggest multiplicative subgroup in the field B, or is not a power of two.

pub fn with_meta(width: usize, length: usize, meta: Vec<u8>) -> Self

Creates a new execution trace of the specified width and length, and with the specified metadata.

This allocates all the required memory for the trace, but does not initialize it. It is expected that the trace will be filled using one of the data mutator methods.

Panics

Panics if:

• width is zero or greater than 255.
• length is smaller than 8, greater than the biggest multiplicative subgroup in the field B, or is not a power of two.
• Length of meta is greater than 65535;

pub fn init(registers: Vec<Vec<B>>) -> Self

Creates a new execution trace from a list of provided register traces.

The provides registers vector is expected to contain register traces.

Panics

Panics if:

• The registers vector is empty or has over 255 registers.
• Number of elements in any of the registers is smaller than 8, greater than the biggest multiplicative subgroup in the field B, or is not a power of two.
• Number of elements is not identical for all registers.

pub fn set(&mut self, register: usize, step: usize, value: B)

Updates a value in a single cell of the execution trace.

Specifically, the value in the specified register and the specified step is set to the provide value.

Panics

Panics if either register or step are out of bounds for this execution trace.

pub fn set_meta(&mut self, meta: Vec<u8>)

Updates metadata for this execution trace to the specified vector of bytes.

Panics

Panics if the length of meta is greater than 65535;

pub fn fill<I, U>(&mut self, init: I, update: U) where
    I: Fn(&mut [B]),
    U: Fn(usize, &mut [B]), 

Fill all rows in the execution trace.

The rows are filled by executing the provided closures as follows:

• init closure is used to initialize the first row of the trace; it receives a mutable reference to the first state initialized to all zeros. The contents of the state are copied into the first row of the trace after the closure returns.
• update closure is used to populate all subsequent rows of the trace; it receives two parameters:
  • index of the last updated row (starting with 0).
  • a mutable reference to the last updated state; the contents of the state are copied into the next row of the trace after the closure returns.

pub fn update_row(&mut self, step: usize, state: &[B])

Updates a single row in the execution trace with provided data.

pub fn fragments(
    &mut self,
    fragment_length: usize
) -> IntoIter<ExecutionTraceFragment<'_, B>>

Breaks the execution trace into mutable fragments.

The number of rows in each fragment will be equal to fragment_length parameter. The returned fragments can be used to update data in the trace from multiple threads.

Panics

Panics if fragment_length is smaller than 2, greater than the length of the trace, or is not a power of two.

pub fn get_info(&self) -> TraceInfo

Returns trace info for this execution trace.

pub fn width(&self) -> usize

Returns number of registers in the trace table.

pub fn length(&self) -> usize

Returns the number of states in this trace table.

pub fn get(&self, register: usize, step: usize) -> B

Returns value of the cell the specified register at the specified step.

pub fn get_register(&self, idx: usize) -> &[B]

Returns the entire register trace for the register at the specified index.

pub fn read_row_into(&self, step: usize, target: &mut [B])

Reads a single row of this trace at the specified step into the specified target.

pub fn get_meta(&self) -> &[u8]

Returns metadata associated with this execution trace.

pub fn validate<A: Air<BaseElement = B>>(&self, air: &A)

Checks if this execution trace is valid against the specified AIR, and panics if not.

NOTE: this is a very expensive operation and is intended for use only in debug mode.

pub fn extend(
    self,
    domain: &StarkDomain<B>
) -> (TraceTable<B>, TracePolyTable<B>)

Extends all registers of the trace table to the length of the LDE domain.

The extension is done by first interpolating each register into a polynomial over the trace domain, and then evaluating the polynomial over the LDE domain.