Field

Our zkEVM is designed to have its execution traces encoded in a particular prime field $F_{p}$ , with $p = 2^{64} - 2^{32} + 1$ . A nice property of this field is that it can represent the results of many common u32 operations. For example, (widening) u32 multiplication has a maximum value of $(2^{32} - 1)^{2}$ , which is less than $p$ . In fact a u32 multiply-add has a maximum value of $p - 1$ , so the result can be represented with a single field element, although if we were to add a carry in bit, this no longer holds.

This field also enables a very efficient reduction method. Observe that $2^{64} \equiv 2^{32} - 1 (mod p)$ and consequently $2^{96} \equiv 2^{32} (2^{32} - 1) (mod p) \equiv 2^{64} - 2^{32} (mod p) \equiv - 1 (mod p) .$

To reduce a 128-bit number $n$ , we first rewrite $n$ as $n_{0} + 2^{64} n_{1} + 2^{96} n_{2}$ , where $n_{0}$ is 64 bits and $n_{1}, n_{2}$ are 32 bits each. Then $n \equiv n_{0} + 2^{64} n_{1} + 2^{96} n_{2} (mod p) \equiv n_{0} + (2^{32} - 1) n_{1} - n_{2} (mod p)$

After computing $(2^{32} - 1) n_{1}$ , which can be done with a shift and subtraction, we add the first two terms, subtracting $p$ if overflow occurs. We then subtract $n_{2}$ , adding $p$ if underflow occurs.

At this point we have reduced $n$ to a u64. This partial reduction is adequate for most purposes, but if we needed the result in canonical form, we would perform a final conditional subtraction.