Skip to main content

Arithmetic State Machine

The Arithmetic State Machine is a secondary state machine that also has an executor (the Arithmetic SM Executor) and an internal Arithmetic program (a set of verification rules written in the PIL language). The Arithmetic SM Executor is available in two languages: Javascript and C/C++.

It is one of the six secondary state machines receiving instructions from the Main SM Executor. The main purpose of the Arithmetic SM is to carry out elliptic curve arithmetic operations, such as Point Addition and Point Doubling as well as performing 256-bit operations like addition, product or division.

Standard Elliptic Curve Arithmetic

Consider an elliptic curve EE defined by y2=x3+ax+by^2 = x^3 + ax + b over the finite field F=Zp\mathbb{F} = \mathbb{Z}_p, where pp is the prime,

p=225623229282726241.p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 -2^6 - 2^4 - 1.

Set the coefficients a=0a = 0 and b=7b = 7, so that EE reduces to

y2=x3+7.y^2 = x^3 + 7.

Point Addition

Given two points, P=(x1,y1)P = (x_1,y_1) and Q=(x2,y2)Q = (x_2,y_2), on the curve EE with x1x2x_1 \neq x_2, the point P+Q=(x3,y3)P+Q = (x_3,y_3) is computed as follows,

x3=s2x1x2,y3=s(x1x3)y1x_3 = s^2 - x_1 - x_2,\quad \\ y_3 = s (x_1 - x_3) - y_1

Point Doubling

Given a point P=(x1,y1)P = (x_1,y_1) on the curve EE such that POP \neq \mathcal{O}, the point P+P=2P=(x3,y3)P+P = 2P = (x_3,y_3) is computed as follows,

x3=s22x1,y3=s(x1x3)y1,x_3 = s^2 - 2x_1, \qquad\quad \\ y_3 = s (x_1 - x_3) - y_1,


s=3x122y1.s = \dfrac{3x_1^2}{2y_1}.

Field Arithmetic

Several 256-bit operations can be expressed in the following form:

AB+C=D2256+E(Eqn A)A \cdot B + C = D \cdot 2^{256} + E \tag{\bf{Eqn A}}

where A,B,C,DA, B, C, D and EE are 256-bit integers.

For instance, if C=0C = 0, then Eqn A\bf{Eqn\ A} states that the result of multiplying AA and BB is EE with a carry of DD. That is, DD is the chunk that exceeds 256 bits.

Or, if B=1B = 1, Eqn A\bf{Eqn\ A} states that the result of adding AA and CC is the same as before: EE with a carry of DD. Similarly, division and modular reductions can also be expressed as derivatives of Eqn A\bf{Eqn\ A}.

These operations are performed in the Arithmetic State Machine, with registers satisfying the following PIL relation,

EQ0 ⁣:x1y1+x2y22256y3=0\text{EQ}_0 \colon \quad x_1 \cdot y_1 + x_2 - y_2 \cdot 2^{256} - y_3 = 0


Since the above Elliptic Curve operations are implemented in the PIL language, it is more convenient to express them in terms of the constraints they must satisfy. These constraints are:

EQ0 ⁣:x1y1+x2y22256y3=0,EQ1 ⁣:sx2sx1y2+y1+q0p=0,EQ2 ⁣:2sy13x1x1+q0p=0,EQ3 ⁣:ssx1x2x3+q1p=0,EQ4 ⁣:sx1sx3y1y3+q2p=0,\begin{aligned} \text{EQ}_0 \colon \quad &x_1 \cdot y_1 + x_2 - y_2 \cdot 2^{256} - y_3 = 0, \\ \text{EQ}_1 \colon \quad &s \cdot x_2 - s \cdot x_1 -y_2 + y_1 + q_0 \cdot p = 0, \\ \text{EQ}_2 \colon \quad & 2 \cdot s \cdot y_1 - 3 \cdot x_1 \cdot x_1 + q_0 \cdot p = 0, \\ \text{EQ}_3 \colon \quad & s \cdot s - x_1 - x_2 - x_3 + q_1 \cdot p = 0, \\ \text{EQ}_4 \colon \quad & s \cdot x_1 - s \cdot x_3 - y_1 - y_3 + q_2 \cdot p = 0, \end{aligned}

where q0,q1,q2Zq_0,q_1,q_2 \in \mathbb{Z}, implying that these equations hold true over the integers.

This approach is taken because of the need to compute divisions by pp. Note that only three possible computation scenarios can arise:

  1. EQ0\text{EQ}_0 is activated while the rest are deactivated,
  2. EQ1\text{EQ}_1, EQ3\text{EQ}_3 and EQ4\text{EQ}_4 are activated but EQ0\text{EQ}_0 and EQ2\text{EQ}_2 are deactivated,
  3. EQ2\text{EQ}_2, EQ3\text{EQ}_3 and EQ4\text{EQ}_4 are activated and EQ0\text{EQ}_0 and EQ1\text{EQ}_1 are deactivated.

Since at most, one of EQ1\text{EQ}_1 and EQ2\text{EQ}_2 are activated in any scenario, we can afford "sharing'' the same q0q_0 for both.

Motivated by the implemented operations, the Arithmetic SM is composed of 6 registers, each of which is composed of 16 sub-registers of 16-bit (2 byte) capacity, adding up to a total of 256 bits per register.

x1, y1, x2, y2, x3, y3.\begin{aligned} x_1,\ y_1,\ x_2,\ y_2,\ x_3,\ y_3. \end{aligned}

There is also a need to provide ss and q0,q1,q2q_0,q_1,q_2, which are also 256-bit field elements.

How Operations Are Performed

Compute the previous operations at 2-byte level. For instance, if one is performing the multiplication of x1x_1 and y1y_1, at the first clock x1[0]y1[0]x_1[0] \cdot y_1[0] is computed.

Then, (x1[0]y1[1])+(x1[1]y1[0])(x_1[0] \cdot y_1[1]) + (x_1[1] \cdot y_1[0]) is computed in the second clock, followed by (x1[0]y1[2])+(x1[1]y1[1])+(x1[2]y1[0])(x_1[0] \cdot y_1[2]) + (x_1[1] \cdot y_1[1]) + (x_1[2] \cdot y_1[0]) in the third, and so on.

As depicted in the below figure, this process is completely analogous to the schoolbook multiplication. However, it is performed at 2-byte level, instead of decimal level.

School Multiplication Example

Use the following notation:

eq =x1[0]y1[0]eq=x1[0]y1[1]+x1[1]y1[0]\begin{aligned} \mathbf{eq\ } &= x_1[0] \cdot y_1[0] \\ \mathbf{eq'} &= x_1[0] \cdot y_1[1] + x_1[1] \cdot y_1[0] \end{aligned}

But then, the carry generated by eq\mathbf{eq} has to be taken into account by eq\mathbf{eq'}.

Going back to our equations EQ0,EQ1,EQ2,EQ4\text{EQ}_0, \text{EQ}_1, \text{EQ}_2, \text{EQ}_4; let's see how the operation is performed in EQ0\text{EQ}_0.

  1. Compute eq0=(x1[0]y1[0])+x2[0]y3[0]\mathbf{eq}_0 = (x_1[0] \cdot y_1[0]) + x_2[0] - y_3[0]

  2. Compute eq1=(x1[0]y1[1])+(x1[1]y1[0])+x2[1]y3[1]\mathbf{eq}_1 = (x_1[0] \cdot y_1[1]) + (x_1[1] \cdot y_1[0]) + x_2[1] - y_3[1]

  3. eq2=(x1[0]y1[2])+(x1[1]y1[1])+(x1[2]y1[0])+x2[2]y3[2]\mathbf{eq}_2 = (x_1[0] \cdot y_1[2]) + (x_1[1] \cdot y_1[1]) + (x_1[2] \cdot y_1[0]) + x_2[2] - y_3[2]

This is continued until one reaches the computation, eq15=(x1[0]y1[15])+(x1[1]y1[14])++x2[15]y3[15]\mathbf{eq}_{15} = (x_1[0] \cdot y_1[15]) + (x_1[1] \cdot y_1[14]) + \dots + x_2[15] - y_3[15].

At this stage y2y_2 comes into place.

Since the first 256 bits of the result of the operation have been filled (and the result can be made of more than 256-bits), a new register is needed to store the rest of the output. We change the addition of x2[i]y3[i]x_2[i] - y_3[i] by y2[i]-y_2[i].

Therefore, we obtain that:

eq16=(x1[1]y1[15])+(x1[2]y1[14])+y2[0],eq17=(x1[2]y1[15])+(x1[3]y1[14])+y2[1]\begin{aligned} \mathbf{eq}_{16} &= (x_1[1] \cdot y_1[15]) + (x_1[2] \cdot y_1[14]) + \dots - y_2[0], \\ \mathbf{eq}_{17} &= (x_1[2] \cdot y_1[15]) + (x_1[3] \cdot y_1[14]) + \dots - y_2[1] \end{aligned}

and so on.

Continuing until the last two:

eq30=(x1[15]y1[15])y2[14],eq31=y2[15].\begin{aligned} \mathbf{eq}_{30} &= (x_1[15] \cdot y_1[15]) - y_2[14], \\ \mathbf{eq}_{31} &= -y_2[15]. \end{aligned}

Now, notice that the carry generated by the eqi\mathbf{eq}_i's is not important for them. That means, if eqi=10\mathbf{eq}_i = 10, then what we really want the result to be is 00 and save 11 as a carry for the next operation. To express this fact as a constraint, we say that the following has to be satisfied:

eq+carry=carry216,\mathbf{eq} + \text{carry} = \text{carry}' \cdot 2^{16},

where carry\text{carry} represents the carry taken into account in the actual clock, and carry\text{carry}' represents the carry generated by the actual operation.


A technicality is that carry\text{carry} is subdivided into two other carryL\text{carry}_L and carryH\text{carry}_H such that:

carry=carryL+carryH218.\text{carry} = \text{carry}_L + \text{carry}_H \cdot 2^{18}.

Source Code

The Polygon zkEVM repository is available on GitHub.

Arithmetic SM Executor: sm_arith folder

Arithmetic SM PIL: arith.pil