Execution trace design
In this section we discuss some aspects pertaining to the shapes or dimensions of the execution traces.
The intention is to ensure that each row of an execution trace contains all data required to validate a single or part of a zkASM operation.
Notation
Since execution traces are created in the context of state machines, columns of an execution trace are also referred to as registries.
A registry
Each
Example: (Fitting all variables in few columns)¶
Consider the three operations,
These operations,
These constraints define how each of the operations works in the execution trace.
A naïve construction of the execution trace would yield the following matrix of 8 columns, corresponding to the variables
Observe that the above execution trace has too many unused cells (
Suppose known research on optimal matrix sizes recommends execution traces with only 6 columns.
And we therefore want to create execution traces with only 6 columns.
We will later on introduce a third approach involving look-ups.
Question:
Can all computations involving operations
Caveat: The number of rows must always equal a power of 2.
Optimization strategy
One possible strategy is to keep the number of rows at
The simplest solution is to store the values of the variables
See how the above alterations in
In the above table,
- The yellow cells represent the operands of
3. - The green cell represents the output of
3. i.e., The sum of all the values in the yellow cells.
This time the execution trace has 7 unused cells, which is a big improment compared to the previous 8-column matrix.
Although the columns have reduced, the computation remained the same, and hence the final outcome is also the same.
The input program is still
Example: (Compact execution trace for 2 operations)¶
Suppose now that the computation involves only two operations;
Let’s examine how to optimize the proving system when the executor’s input program is:
Using a 6-column matrix yields the following execution matrix:
The blue cells, in the above table, represent the unused cells. These are
Optimization strategy
An optimal usage of the matrix space can be attained via a strategy similar to the one used in the previous example.
That is, placing the last two operands of
The computation’s final outcome is in this case placed in column
This revised layout ensures that no cell remains unused, reaching the maximum utilization of the matrix space.
In conclusion, we note that the number of unused cells strongly depends on the executed instructions and the number of columns of the execution matrix.