# Constraint evaluator format

Below is a description of the format for describing the constraint evaluation logic (i.e., the constraint evaluator). The format is JSON-based. All field elements are represented in their canonical values encoded as strings.

At the root level, the evaluator is defined by the five components described below:

{
    metadata: "<field, trace, and variable definitions>",
    zerofiers: "<an array denominators for constraint expressions>",
    periodic: "<an array of periodic column definitions>",
    expressions: "<an array of expressions defined by numerators/denominators>",
    nodes: "<an array of all nodes in the expressions>",
}

Each of these components is described below.

## Metadata

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:
- We use the Goldilocks field (with degree 2 extension).
- There are 3 variable groups with 5, 10, and 16 variables respectively.
- There are 2 trace segments with 64 and 14 columns respectively.

{
    field: {
        name: "Goldilocks",
        modulus: "18446744069414584321",
        root_of_unity: "7277203076849721926",
        coset_offset: "7",
        extension: {
            degree: 2,
            polynom: "x^2 - x + 2",
        }
    },
    num_variables: [5, 10, 16],
    trace_widths: [64, 14],
}

For the `M31` field, the field parameters are specified analogously as follows:

{
    field: {
        name: "M31",
        modulus: "2147483647",
        root_of_unity: "(311014874, 1584694829)",
        extension: {
            degree: 4,
            polynom: "x^2 - 2 - i",
        }
    },
    num_variables: [5, 10, 16],
    trace_widths: [64, 14],
}

The main differences from the `Goldilocks` field format are:

- `root_of_unit` is specified by a tuple of base field elements.
- The `coset_offset` is implied by the `root_of_unity` and therefore is omitted.
- The irreducible polynomial of the degree 4 extension field is specified via the the irreducible polynomial of degree 2 extension field which is $x^2 + 1$. Thus, $i$ is the root of the $x^2 + 1$.

## Zerofiers

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:

[
    "x - 1",                       // first row
    "x - g^(n - 1)",               // last row
    "x^n - 1",                     // every row
    "(x^n - 1) / (x - g^(n - 1))", // every row except for the last row
    "x^(n/2) - 1",                 // every odd row
]

Algebraic expressions can involve the following:
- Basic arithmetic operations: addition, multiplication, subtraction, division, and exponentiation.
- Ability to group expression using parenthesis.
- Ability to use constants, which are always in the base field.
- Ability to use 3 special variables:
- $n$ - the size of the multiplicative subgroup (i.e., the length of the trace).
- $g$ - the generator of the multiplicative subgroup of size $n$.
- $x$ - computed as $g^i$ where $i$ is the index of the row in the trace.

Note that $g$ and $x$ 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.

## Periodic columns

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.

[
    ["1", "0", "0", "0"],
    ["0", "0", "0", "0", "0", "0", "0", "0", "1"],
]

Values for periodic columns are always base field elements, and the period length is always a power of $2$ (usually a small power - e.g., 4, 8, 16).

## Expressions

An expression consists of a numerator and an optional denominator:

{
    node_id: 10,     // node ID of the numerator entrypoint
    zerofier_id: 1,  // ID of the zerofier; can be omitted if no zerofier
}

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 $n$ rows where $n$ is the size of the extended domain (i.e., the number of rows in a trace segment).

## Nodes

Each node in the `nodes` array has the following general form:

{
    name: "<optional name>",
    type: "const | mul | add | sub | trace | var | periodic",
    args: "dpends on type",
    value: "base | ext",
}

Each node type is described in more detail in the sections below.

### const

The `const` node specifies a constant in the base field.

{
    type: "const",
    args: {
        value: "123456"
    },
    value: "base",    // constants are always in the base field
}

### add, mul, sub

The `mul`, `add`, and `sub` nodes specify binary operations.

{
    type: "mul",
    args: {
        lhs: 10,    // node ID of the left-hand-side operand
        rhs: 11,    // node ID of the right-hand-side operand
    },
    value: "ext",
}

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`.

### trace

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`:

{
    type: "trace",
    args: {
        segment: 0,
        col_offset: 1,
        row_offset: 0,
    },
    value: "base",
}

The above refers to a base field element located at `traces[0][i][1]`, where $i$ is the current row index.

Trace values can also refer to extension field elements as follows:

{
    type: "trace",
    args: {
        segment: 0,
        col_offset: 1,
        row_offset: 0,
    },
    value: "ext",
}

The above refers to an extension field element located at `trace[0][i][1..3]`, where $i$ is the current row index.

The `offset` parameter is a positive integer defining the row offset in relation to the current row. For example:

{
    type: "trace",
    args: {
        segment: 0,
        col_offset: 1,
        row_offset: 1,
    },
    value: "base",
}

Refers to a base field element located at `traces[0][i+1][1]`.

### var
The `var` node is reference to a value in the `variables` vectors. It can be specified using a `group` and an `offset`:

{
    type: "var",
    args: {
        group: 0,
        offset: 1,
    },
    value: "base",
}

The above refers to a single base field element located in `variables[0][1]`.

Variables can also refer to extension field elements as follows:

{
    type: "var",
    args: {
        group: 0,
        offset: 1,
    },
    value: "ext",
}

The above refers to an extension field element (defined as 2 base field elements) located in `variables[0][1..3]`.

### periodic
The `periodic` node is a reference to a value of a periodic column.

{
    type: "periodic",
    args: {
        column: 0,
    },
    value: "base",  // periodic column values are always in the base field
}