Struct AlgebraicExecutionTrace

pub struct AlgebraicExecutionTrace {
    pub program: Program,
    pub instruction_multiplicities: Vec<u32>,
    pub processor_trace: Array2<BFieldElement>,
    pub op_stack_underflow_trace: Array2<BFieldElement>,
    pub ram_trace: Array2<BFieldElement>,
    pub program_hash_trace: Array2<BFieldElement>,
    pub hash_trace: Array2<BFieldElement>,
    pub sponge_trace: Array2<BFieldElement>,
    pub u32_entries: IndexMap<U32TableEntry, u64>,
    pub cascade_table_lookup_multiplicities: IndexMap<u16, u64>,
    pub lookup_table_lookup_multiplicities: [u64; 256],
}

An Algebraic Execution Trace (AET) is the primary witness required for proof generation. It holds every intermediate state of the processor and all co-processors, alongside additional witness information, such as the number of times each instruction has been looked up (equivalently, how often each instruction has been executed).

Fields

program: Program

The program that was executed in order to generate the trace.

instruction_multiplicities: Vec<u32>

The number of times each instruction has been executed.

Each instruction in the program has one associated entry in instruction_multiplicities, counting the number of times this specific instruction at that location in the program memory has been executed.

processor_trace: Array2<BFieldElement>

Records the state of the processor after each instruction.

op_stack_underflow_trace: Array2<BFieldElement>

ram_trace: Array2<BFieldElement>

program_hash_trace: Array2<BFieldElement>

The trace of hashing the program whose execution generated this AlgebraicExecutionTrace. The resulting digest

1. ties a Proof to the program it was produced from, and
2. is accessible to the program being executed.

hash_trace: Array2<BFieldElement>

For the hash instruction, the hash trace records the internal state of the Tip5 permutation for each round.

sponge_trace: Array2<BFieldElement>

For the Sponge instructions, i.e., sponge_init, sponge_absorb, sponge_absorb_mem, and sponge_squeeze, the Sponge trace records the internal state of the Tip5 permutation for each round.

u32_entries: IndexMap<U32TableEntry, u64>

The u32 entries hold all pairs of BFieldElements that were written to the U32 Table, alongside the u32 instruction that was executed at the time. Additionally, it records how often the instruction was executed with these arguments.

cascade_table_lookup_multiplicities: IndexMap<u16, u64>

Records how often each entry in the cascade table was looked up.

lookup_table_lookup_multiplicities: [u64; 256]

Records how often each entry in the lookup table was looked up.

Implementations

impl AlgebraicExecutionTrace

pub fn new(program: Program) -> Self

pub fn padded_height(&self) -> usize

The height of the AET after padding.

Guaranteed to be a power of two.

pub fn height(&self) -> TableHeight

The height of the AET before padding. Corresponds to the height of the longest table.

pub fn height_of_table(&self, table: TableId) -> usize

Trait Implementations

impl Clone for AlgebraicExecutionTrace

fn clone(&self) -> AlgebraicExecutionTrace

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for AlgebraicExecutionTrace

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.