Struct winterfell::TraceTable

pub struct TraceTable<B> where
    B: StarkField,  { /* private fields */ }

A concrete implementation of the Trace trait.

This implementation supports concurrent trace generation and should be sufficient for most use cases. There are two ways to create a trace table trace.

First, you can use the TraceTable::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 TraceTable::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 TraceTable::with_meta() function to create a blank execution trace. This function work just like TraceTable::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, TraceTable 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 TraceTableFragment::fill() method are identical to the semantics of the TraceTable::fill() method.

Implementations

impl<B> TraceTable<B> where
    B: StarkField, 

pub fn new(width: usize, length: usize) -> TraceTable<B>

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, Global>
) -> TraceTable<B>

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(columns: Vec<Vec<B, Global>, Global>) -> TraceTable<B>

Creates a new execution trace from a list of provided trace columns.

Panics

Panics if:

• The columns vector is empty or has over 255 columns.
• Number of elements in any of the columns 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 columns.

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

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

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

Panics

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

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

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<TraceTableFragment<'_, B>, Global>

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 width(&self) -> usize

Returns the number of columns in this execution trace.

pub fn get_column(&self, col_idx: usize) -> &[B]

Returns the entire trace column at the specified index.

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

Returns value of the cell in the specified column at the specified row of this trace.

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

Reads a single row from this execution trace into the provided target.

Trait Implementations

impl<B> Trace for TraceTable<B> where
    B: StarkField, 

type BaseField = B

Base field for this execution trace.

fn layout(&self) -> &TraceLayout

Returns a description of how columns of this trace are arranged into trace segments.

fn length(&self) -> usize

Returns the number of rows in this trace.

fn meta(&self) -> &[u8]

Returns metadata associated with this trace.

fn read_main_frame(
    &self,
    row_idx: usize,
    frame: &mut EvaluationFrame<<TraceTable<B> as Trace>::BaseField>
)

Reads an evaluation frame from the main trace segment at the specified row.

fn main_segment(&self) -> &Matrix<B>

Returns a reference to a Matrix describing the main segment of this trace.

fn build_aux_segment<E>(
    &mut self,
    _aux_segments: &[Matrix<E>],
    _rand_elements: &[E]
) -> Option<Matrix<E>> where
    E: FieldElement<BaseField = <TraceTable<B> as Trace>::BaseField>, 

Builds and returns the next auxiliary trace segment. If there are no more segments to build (i.e., the trace is complete), None is returned.

fn get_info(&self) -> TraceInfo

Returns trace info for this trace.

fn main_trace_width(&self) -> usize

Returns the number of columns in the main segment of this trace.

fn aux_trace_width(&self) -> usize

Returns the number of columns in all auxiliary trace segments.

fn validate<A, E>(
    &self,
    air: &A,
    aux_segments: &[Matrix<E>],
    aux_rand_elements: &AuxTraceRandElements<E>
) where
    A: Air<BaseField = Self::BaseField>,
    E: FieldElement<BaseField = Self::BaseField>, 

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