Skip to content

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 A is denoted by A=(a0,a1,...,a2k1), where each ai+1 is the value in A subsequent to ai. Denote this next value in A by a. That is, a=ai+1.

Each a is typically the output of some operation Op, applied on some entries (ai,bi,ci) from columns A, B and C. That is:

a=Op(ai,bi,ci)

Example: (Fitting all variables in few columns)

Consider the three operations, Op1, Op2 and Op3, as instructions to the executor, written in zkASM.

These operations, Op1, Op2 and Op3, are defined to change the next entry of the registry A=(a0,a1,...,a2k1) as follows:

Op1:a=a+b+cOp2:a=a+b+c+d+eOp3:a=a+b+c+d+e+f+g+h

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 a,b,c,d,e,f,g,h. For illustration purposes, we set each variable to 1.

 A  B  C  D  E  F  G  H 111311117111111114

Observe that the above execution trace has too many unused cells (15 unused cells in this case).

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 Op1, Op2 and Op3 fit in a 6-column matrix? If so, how can this be done?

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 4 , and find appropriate cells in which to store the values of the variables g and h.

The simplest solution is to store the values of the variables g and h in the fourth row and columns B and C, and hence redefine Op3 as:

Op3: a=a+b+c+d+e+f+b+c

See how the above alterations in Op3 affects the execution trace.

Figure:

In the above table,

  • The yellow cells represent the operands of Op​3.
  • The green cell represents the output of Op3. 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 (Op1,Op2,Op3). So setting each variable to 1 yields the matrix below.

 A  B  C  D  E  F 111311117111111411

Example: (Compact execution trace for 2 operations)

Suppose now that the computation involves only two operations; Op1 and Op2.

Let’s examine how to optimize the proving system when the executor’s input program is:

(Op1,Op2)

Using a 6-column matrix yields the following execution matrix:

Figure:

The blue cells, in the above table, represent the unused cells. These are 9 in number, constituting exactly 50% of all the cells of the matrix. Such an under utilization of the matrix space is dissatisfactory.

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 Op2 in the last row of the execution matrix. And thus reduce the number of columns from 6 to 3.

Op2 is therefore redefined as follows:

OP2: c=a+b+c+a+b

The computation’s final outcome is in this case placed in column C, as shown in the table below.

Figure:

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.