Module arrabbiata::interpreter

This module contains the implementation of the IVC scheme in addition to running an arbitrary function that can use up to crate::NUMBER_OF_COLUMNS columns. At the moment, all constraints must be of maximum degree crate::MAX_DEGREE, but it might change in the future.

The implementation relies on a representation of the circuit as a 2D array of “data points” the interpreter can use.

An interpreter defines what a “position” is in the circuit and allow to perform operations using these positions. Some of these positions will be considered as public inputs and might be fixed at setup time while making a proof, when other will be considered as private inputs.

On top of these abstraction, gadgets are implemented. For the Nova-like IVC schemes, we describe below the different gadgets and how they are implemented with this abstraction.

Table of contents:

• Gadgets implemented
  • Elliptic curve addition
    • Gadget layout
  • Hash - Poseidon
    • Gadget layout
  • Elliptic curve scalar multiplication
    • Gadget layout
• Handle the combinaison of constraints
• Permutation argument
• Fiat-Shamir challenges

Gadgets implemented

Elliptic curve addition

The Nova augmented circuit requires to perform elliptic curve operations, in particular additions and scalar multiplications.

To reduce the number of operations, we consider the affine coordinates. As a reminder, here the equations to compute the addition of two different points P1 = (X1, Y1) and P2 = (X2, Y2). Let define P3 = (X3, Y3) = P1 + P2.

- λ = (Y1 - Y2) / (X1 - X2)
- X3 = λ^2 - X1 - X2
- Y3 = λ (X1 - X3) - Y1

Therefore, the addition of elliptic curve points can be computed using the following degree-2 constraints

- Constraint 1: λ (X1 - X2) - Y1 + Y2 = 0
- Constraint 2: X3 + X1 + X2 - λ^2 = 0
- Constraint 3: Y3 - λ (X1 - X3) + Y1 = 0

If the points are the same, the λ is computed as follows:

- λ = (3 X1^2 + a) / (2Y1)

Gadget layout

For given inputs (x1, y1) and (x2, y2), the layout will be as follow:

| C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | C10 | C11 | C12 | C13 | C14 | C15 | C16 | C17 |
| -- | -- | -- | -- | -- | -- | -- | -- | -- | --- | --- | --- | --- | --- | --- | --- | --- |
| x1 | y1 | x2 | y2 | b0 | λ  | x3 | y3 |    |     |     |     |     |     |     |     |     |

where b0 is equal two 1 if the points are the same, and 0 otherwise.

TBD/FIXME: supports negation and the infinity point.

TBD/FIXME: the gadget layout might change when we will implement the permutation argument. The values (x1, y1) can be public inputs. The values (x2, y2) can be fetched from the permutation argument, and must be the output of the elliptic curve scaling.

The gadget requires therefore 7 columns.

Hash - Poseidon

Hashing is a crucial part of the IVC scheme. The hash function the interpreter does use for the moment is an instance of the Poseidon hash function with a fixed state size of crate::curve::PlonkSpongeConstants::SPONGE_WIDTH. Increasing the state size can be considered as it would potentially optimize the number of rounds, and allow hashing more data on one row. We leave this for future works.

A direct optimisation would be to use Poseidon2 as its performance on CPU is better, for the same security level and the same cost in circuit. We leave this for future works.

For a first version, we consider an instance of the Poseidon hash function that is suitable for curves whose field size is around 256 bits. A security analysis for these curves give us a recommandation of 60 full rounds if we consider a 128-bit security level and a low-degree exponentiation of 5, with only full rounds. In the near future, we will consider the partial rounds strategy to reduce the CPU cost. For a first version, we keep the full rounds strategy to keep the design simple.

When applying the full/partial round strategy, an optimisation can be used, see New Optimization techniques for PlonK’s arithmetisation. The techniques described in the paper can also be generalized to other constraints used in the interpreter, but we leave this for future works.

Gadget layout

We start with the assumption that 17 columns are available for the whole circuit, and we can support constraints up to degree 5. Therefore, we can compute 4 full rounds per row if we rely on the permutation argument, or 5 full rounds per row if we use the “next row”.

We provide two implementations of the Poseidon hash function. The first one does not use the “next row” and is limited to 4 full rounds per row. The second one uses the “next row” and can compute 5 full rounds per row. The second implementation is more efficient as it allows to compute one additional round per row. For the second implementation, the permutation argument will only be activated on the first and last group of 5 rounds.

The layout for the one not using the “next row” is as follow (4 full rounds):

| C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | C10 | C11 | C12 | C13 | C14 | C15 |
| -- | -- | -- | -- | -- | -- | -- | -- | -- | --- | --- | --- | --- | --- | --- |
| x  | y  | z  | a1 | a2 | a3 | b1 | b2 | b3 | c1  | c2  | c3  | o1  | o2  | o3  |

where (x, y, z) is the input of the current step, (o1, o2, o3) is the output, and the other values are intermediary values. And we have the following equalities:

(a1, a2, a3) = PoseidonRound(x, y, z)
(b1, b2, b3) = PoseidonRound(a1, a2, a3)
(c1, c2, c3) = PoseidonRound(b1, b2, b3)
(o1, o2, o3) = PoseidonRound(c1, c2, c3)

The layout for the one using the “next row” is as follow (5 full rounds):

| C1 | C2 | C3 | C4 | C5 | C6 | C7 | C8 | C9 | C10 | C11 | C12 | C13 | C14 | C15 |
| -- | -- | -- | -- | -- | -- | -- | -- | -- | --- | --- | --- | --- | --- | --- |
| x  | y  | z  | a1 | a2 | a3 | b1 | b2 | b3 | c1  | c2  | c3  | d1  | d2  | d3  |
| o1 | o2 | o2

where (x, y, z) is the input of the current step, (o1, o2, o3) is the output, and the other values are intermediary values. And we have the following equalities:

(a1, a2, a3) = PoseidonRound(x, y, z)
(b1, b2, b3) = PoseidonRound(a1, a2, a3)
(c1, c2, c3) = PoseidonRound(b1, b2, b3)
(d1, d2, d3) = PoseidonRound(c1, c2, c3)
(o1, o2, o3) = PoseidonRound(d1, d2, d3)

For both implementations, round constants are passed as public inputs. As a reminder, public inputs are simply additional columns known by the prover and verifier. Also, the elements to absorb are added to the initial state at the beginning of the call of the Poseidon full hash. The elements to absorb are supposed to be passed as public inputs.

Elliptic curve scalar multiplication

The Nova-based IVC schemes require to perform scalar multiplications on elliptic curve points. The scalar multiplication is computed using the double-and-add algorithm.

We will consider a basic implementation using the “next row”. The accumulators will be saved on the “next row”. The decomposition of the scalar will be incrementally on each row. The scalar used for the scalar multiplication will be fetched using the permutation argument (FIXME: to be implemented). More than one bit can be decomposed at the same time, and we could reduce the number of rows. We leave this for future work.

Gadget layout

For a (x, y) point and a scalar, we apply the double-and-add algorithm, one step per row. Therefore, we have 255 rows to compute the scalar multiplication. For a given step i, we have the following values:

• tmp_x, tmp_y: the temporary values used to keep the double.
• res_x, res_y: the result of the scalar multiplication i.e. the accumulator.
• b: the i-th bit of the scalar.
• r_i and r_(i+1): scalars such that r_(i+1) = b + 2 * r_i.
• λ' and λ: the coefficients
• o’_x and o’_y equal to res_plus_tmp_x and res_plus_tmp_y if b == 1, otherwise equal to o_x and o_y.

We have the following layout:

| C1   |   C2   |      C3       |      C4       |    C5     | C7 |       C7       |       C8       | C9 | C10 |   C11    | C12 | C13 | C14 | C15 | C16 | C17 |
| --   | -----  | ------------- | ------------- | --------- | -- | -------------- | -------------- | -- | --- | -------- | --- | --- | --- | --- | --- | --- |
| o_x  |  o_y   | double_tmp_x  | double_tmp_y  |    r_i    | λ  | res_plus_tmp_x | res_plus_tmp_y | λ' |  b  |
| o'_x |  o'_y  | double_tmp'_x | double_tmp'_y |  r_(i+1)  |

FIXME: an optimisation can be implemented using “a bucket” style algorithm, as described in Efficient MSMs in Kimchi Circuits. We leave this for future work.

Handle the combinaison of constraints

The prover will have to combine the constraints to generate the full circuit at the end. The constraints will be combined using a challenge (often called α) that will be generated in the verifier circuit by simulating the Fiat-Shamir transformation. The challenges will then be accumulated over time using the random coin used by the folding argument. The verifier circuit must be carefully implemented to ensure that all the messages that the prover would have sent before coining the random combiner for the constraints has been absorbed properly in the verifier circuit.

Using this technique requires us a folding scheme that handles degree 5 + 1 constraints, as the challenge will be considered as a variable. The reader can refer to the folding library available in this monorepo for more contexts.

Permutation argument

Communication between rows must be done using a permutation argument. The argument we use will be a generalisation of the one used in the PlonK paper.

The construction of the permutations will be done using the methods prefixed save and load. The index of the current row and the index of the time the value has been written will be used to generate the permutation on the fly.

The permutation argument described in the PlonK paper is a kind of “inverse lookup” protocol, like Plookup. The polynomials are defined as follows:

           Can be seen as T[f(X)] = Χ
         --------
         |      |
f'(X) = f(X) + β X + γ
                     |--- Can be seen as the evaluation point.
                        |
                        |
g'(X) = g(X) + β σ(X) + γ
         |      |
         --------
         Can be seen as T[g(X)] = σ(X)

And from this, we build an accumulator, like for Plookup. The accumulator requires to coin two challenges, β and γ, and it must be done after the commitments to the columns have been absorbed. The verifier at the next step will verify that the challenges have been correctly computed. In the implementation, the accumulator will be computed after the challenges and the commitments. Note that the accumulator must also be aggregated, and the aggregation must be performed by the verifier at the next step.

The methods save and load will accept as arguments only a column that is included in the permutation argument. For instance, save_poseidon_state will only accept columns with index 3, 4 and 5, where the load_poseidon_state will only accepts columns with index 0, 1 and 2.

The permutations values will be saved in public values, and will contain the index of the row. The permutation values will be encoded with a 32 bits value (u32) as we can suppose a negligible probability that a user will use more than 2^32 rows.

The permutation argument also generates constraints that will be homogenized with the gadget constraints.

Note all rows might require to use the permutation argument. Therefore, a selector will be added to activate/deactivate the permutation argument. When a method calls save or load, the selector will be activated. By default, the selector will be deactivated.

TBD:

• number of columns
• accumulator column
• folding of the permutation argument

TBD/FIXME: do we use a additive permutation argument to increase the number of columns we can perform the permutation on?

TBD/FIXME: We can have more than one permutation argument. For instance, we can have a permutation argument for the columns 0, 1, 2, 3 and one for the columns 4, 5, 6, 7. It can help to decrease the degree.

Fiat-Shamir challenges

The challenges sent by the verifier must also be simulated by the IVC circuit.

For a step i + 1, the challenges of the step i must be computed by the verifier, and check that it corresponds to the ones received as a public input.

TBD/FIXME: specify. Might require foreign field arithmetic.

TBD/FIXME: do we need to aggregate them for the end?

Folding

Constraints must be homogenized for the folding scheme. Homogenising a constraint means that we add a new variable (called “U” in Nova for instance) that will be used to homogenize the degree of the monomials forming the constraint. Next to this, additional information, like the cross-terms and the error terms must be computed.

This computation depends on the constraints, and in particular on the monomials describing the constraints. The computation of the cross-terms and the error terms happen after the witness has been built and the different arguments like the permutation or lookup have been done. Therefore, the interpreter must provide a method to compute it, and the constraints should be passed as an argument.

When computing the cross-terms, we must compute the contribution of each monomial to it.

The implementation works as follow:

• Split the constraint in monomials
• For the monomials of degree d, compute the contribution when homogenizing to degree d'.
• Sum all the contributions.

The library [mvpoly] can be used to compute the cross-terms and to homogenize the constraints. The constraints can be converted into a type implementing the trait MVPoly and the method compute_cross_terms can be used from there.

Enums

• Instruction
  A list of instruction/gadget implemented in the interpreter. The control flow can be managed by implementing a function fetch_next_instruction and fetch_instruction on a witness environnement. See the Witness environment for more details.
• Side
  Define the side of the temporary accumulator. When computing G1 + G2, the interpreter will load G1 and after that G2. This enum is used to decide which side fetching into the cells. In the near future, it can be replaced by an index.

Traits

• InterpreterEnv
  An abstract interpreter that provides some functionality on the circuit. The interpreter should be seen as a state machine with some built-in functionality whose state is a matrix, and whose transitions are described by polynomial functions.

Functions

• run_app
  Run the application
• run_ivc
  Run an iteration of the IVC scheme