Below is a description of the format for describing the constraint evaluation AST. The format is JSON-based. All field elements are represented in their canonical values encoded as strings.
At the root level, the AST is defined by the five components described below:
Each of these components is described below.
The metadata component describes the parameters of the field, the number of variables and trace segments to be provided as inputs for constraint evaluation.
Variables and trace segment values are specified as base field elements, but they can be interpreted as extension field elements during evaluation. Trace segments are expected to be 2-dimensional matrices in the row-major form. All trace segments are expected to have the same number of rows.
Here is an example of the metadata where:
For the M31
field, the field parameters are specified analogously as follows:
The main differences from the Goldilocks
field format are:
root_of_unit
is specified by a tuple of base field elements.coset_offset
is implied by the root_of_unity
and therefore is omitted.Zerofiers define the denominators used for each expression. Each zerofier is specified by an algebraic expression in a string format. For example, below is an array of 5 zerofiers:
Algebraic expressions can involve the following:
Note that and cannot be used in the exponent position.
For the Goldilocks
field, these expressions can be evaluated directly to compute zerofier values at a given trace row. For the M31
field, they will need to be translated into their equivalent for Circle STARK.
A list of periodic columns defines trace columns which have succinct descriptions. For example, below we describe two periodic columns: one with a period of 4 values, and the other one with a period of 8 values.
Values for periodic columns are always base field elements, and the period length is always a power of (usually a small power - e.g., 4, 8, 16).
An expression consists of a numerator and an optional denominator:
The list of expressions defines the output of the evaluation. For example, if the list contains 2 expressions, evaluation results will be a matrix with 2 column and rows where is the size of the extended domain (i.e., the number of rows in a trace segment).
Each node in the nodes
array has the following general form:
Each node type is described in more detail in the sections below.
The const
node specifies a constant in the base field.
The mul
, add
, and sub
nodes specify binary operations.
The value
field must be derived deterministically from the values of the node's children as follows: if the value of either of the children is ext
, the node's value should also be ext
. Otherwise, the node's value is base
.
The trace
node is a relative reference to a value in a trace matrix. It can be specified using a segment
, col_offset
, and row_offset
:
The above refers to a base field element located at traces[0][i][1]
, where is the current row index.
Trace values can also refer to extension field elements as follows:
The above refers to an extension field element located at trace[0][i][1..3]
, where is the current row index.
The offset
parameter is a positive integer defining the row offset in relation to the current row. For example:
Refers to a base field element located at traces[0][i+1][1]
.
The var
node is reference to a value in the variables
vectors. It can be specified using a group
and an offset
:
The above refers to a single base field element located in variables[0][1]
.
Variables can also refer to extension field elements as follows:
The above refers to an extension field element (defined as 2 base field elements) located in variables[0][1..3]
.
The periodic
node is a reference to a value of a periodic column.
copy
expressions?Below is a description of the draft format for describing the AST. The format is JSON-based, but this can be changed if needed.
At the root level, the AST is defined by the five components described below:
Each of these components is described below.
The metadata component describes the parameters of the field used, the number of variables to be provided by field type, and the number of trace segments to be provided by field type.
Here is an example of the metadata where:
Zerofiers define the denominators used for each expression. Each zerofier is specified by an algebraic expression in a string format. For example, below is an array of 5 zerofiers:
Algebraic expressions can involve the following:
Note that and cannot be used in the exponent position.
A list of periodic columns defines trace columns which have succinct descriptions. For example, below we describe two periodic columns: one with a period of 4 values, and the other one with a period of 8 values.
Values for periodic columns are always base field elements, and the period length is always a power of (usually a small power - e.g., 4, 8, 16).
An expression consists of a numerator and an optional denominator:
Each node in the nodes
array has the following general form:
Each node type is described in more detail in the sections below.
The const
node specifies a constant in the base field.
The mul
, add
, and sub
nodes specify binary operations.
The value
field must be derived deterministically from the values of the node's children as follows: if the value of either of the children is ext
, the node's value should also be ext
. Otherwise, the node's value is base
.
The trace
node is a relative reference to a cell in a trace matrix (either base or extension trace based on the value
field).
The var
node is reference to a cell in a variables vector (either base or extension vector based on the value
field).
The periodic
node is a reference to a value of a periodic column.
The format currently does not include:
This format is similar to the v1 format except trace matrices and variables are defined in terms of base field elements.
For example, a metadata
section equivalent to the previous example would look as follows:
Notice that extension field variables are now expressed as base field variables. Similarly, extension trace of columns is now expressed as a segment of base field columns. This is because the degree of the extension field is .
trace
and var
nodes can still refer to extension field elements, but the references are based on base element offsets. For example:
Refers to a single base field element located in variables[2][1]
. However,
Refers to an extension field element (defined as 2 base field elements) located in variables[2][1..3]
.
Similarly,
Refers to a base field element located at traces[1][i][2]
, where is the current row index. while:
Refers to an extension field element located at trace[1][i][2..4]
, where is the current row index.
Note
This format assumes that trace matrices are always in the row-major form.