- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
Warning: This document provides a technical overview of the Translator Circuit used in the Goblin Plonk proving system. It is intended for understanding the design and optimizations. The code is the source of truth for implementation specifics.
The Translator circuit is a critical component of the Goblin Plonk proving system in Aztec. It serves as a bridge between the Mega and ECCVM circuits.
| Curve | Base Field | Scalar Field | Usage |
|---|---|---|---|
| BN254 | $\mathbb{F}_q$ | $\mathbb{F}_r$ | Used in Mega circuits |
| Grumpkin | $\mathbb{F}_r$ | $\mathbb{F}_q$ | Used in ECCVM for efficient EC operations |
When proving recursive circuits with Mega circuit builder, we accumulate elliptic curve operations in an EccOpQueue. Proving these ECC operations is delegated to the ECCVM circuit, which operates over the Grumpkin curve. However, the same operations have different representations in the two circuits because:
For example, consider the operation $(z \cdot P)$ where $P \equiv (P_x, P_y) \in \mathbb{F}_q^2$ is a point on the curve and $z \in \mathbb{F}_r$ is a scalar. The ECCVM arithmetisation represents this operation (in 1 row) as:
| Opcode | $x$-coordinate | $y$-coordinate | Scalar $z_1$ | Scalar $z_2$ | Full scalar $z$ |
|---|---|---|---|---|---|
MUL | $P_x$ | $P_y$ | $z_1$ | $z_2$ | $z$ |
The Mega circuit arithmetisation represents the same operation (in 2 rows) as:
| Column 1 | Column 2 | Column 3 | Column 4 |
|---|---|---|---|
MUL | $P_{x, \textsf{lo}}$ | $P_{x, \textsf{hi}}$ | $P_{y, \textsf{lo}}$ |
| $0$ | $P_{y, \textsf{hi}}$ | $z_1$ | $z_2$ |
where $P_x = (P_{x, \textsf{lo}} + 2^{136} \cdot P_{x, \textsf{hi}}), \ P_y = (P_{y, \textsf{lo}} + 2^{136} \cdot P_{y, \textsf{hi}})$ and the scalar $z = (z_1 + 2^{128} \cdot z_2)$. Note that the limbs $P_{x/y, \textsf{lo}}, P_{x/y, \textsf{hi}}$ are elements in $\mathbb{F}_r$.
We need to prove that these two representations are consistent, i.e., that the polynomial evaluations computed in the ECCVM circuit (over $\mathbb{F}_q$) match those computed in the Mega circuit (over $\mathbb{F}_r$). The Translator circuit is a custom circuit designed to solve this problem. It:
The Translator proves that the ECCVM's batched polynomial evaluation of the ECC operations is computed correctly. Given:
UltraOp operations from the EccOpQueue (each containing: $\text{op}, P_x, P_y, z_1, z_2$)Prove that: $$\boxed{\text{accumulator}_{\text{final}} = \sum_{i=0}^{n-1} x^{n-1-i} \cdot \left( \text{op}_i + v \cdot P_x^{(i)} + v^2 \cdot P_y^{(i)} + v^3 \cdot z_1^{(i)} + v^4 \cdot z_2^{(i)} \right) \pmod{q}}$$
The batching via powers of $v$ combines the 5 values per operation into a single field element, and the powers of $x$ combine all operations into a single accumulator.
Specifically, for each accumulation step (every 2 rows), prove:
$$\text{acc}_{\text{curr}} = \text{acc}_{\text{prev}} \cdot x + \text{op} + P_x \cdot v + P_y \cdot v^2 + z_1 \cdot v^3 + z_2 \cdot v^4 \pmod{q}$$
Note that we process the EccOpQueue in reverse order while computing the accumulator in steps:
$$ \begin{aligned} \textcolor{orange}{\text{acc}_0} &= \textcolor{lightgrey}{0} \cdot x + \text{op}_{n-1} + P_x^{(n-1)} \cdot v + P_y^{(n-1)} \cdot v^2 + z_1^{(n-1)} \cdot v^3 + z_2^{(n-1)} \cdot v^4 \ \textcolor{lightgreen}{\text{acc}_1} &= \textcolor{orange}{\text{acc}_0} \cdot x + \text{op}_{n-2} + P_x^{(n-2)} \cdot v + P_y^{(n-2)} \cdot v^2 + z_1^{(n-2)} \cdot v^3 + z_2^{(n-2)} \cdot v^4 \ \textcolor{skyblue}{\text{acc}_2} &= \textcolor{lightgreen}{\text{acc}_1} \cdot x + \text{op}_{n-3} + P_x^{(n-3)} \cdot v + P_y^{(n-3)} \cdot v^2 + z_1^{(n-3)} \cdot v^3 + z_2^{(n-3)} \cdot v^4 \ &\ \ \vdots \ \textcolor{brown}{\text{acc}_{n-2}} &= \textcolor{grey}{\text{acc}_{n-3}} \cdot x + \text{op}_1 + P_x^{(1)} \cdot v + P_y^{(1)} \cdot v^2 + z_1^{(1)} \cdot v^3 + z_2^{(1)} \cdot v^4 \ \textcolor{violet}{\text{acc}_{n-1}} &= \textcolor{brown}{\text{acc}_{n-2}} \cdot x + \text{op}_0 + P_x^{(0)} \cdot v + P_y^{(0)} \cdot v^2 + z_1^{(0)} \cdot v^3 + z_2^{(0)} \cdot v^4 \ \end{aligned} $$
The final accumulator value $\textcolor{violet}{\text{acc}_{n-1}}$ is what we need to verify against the ECCVM's output. Note that the "previous" accumulator for the last operation must be 0.
Method: Since we cannot directly compute in $\mathbb{F}_q$ using $\mathbb{F}_r$ arithmetic (as $q \neq r$, and in fact $q > r$), we use non-native field arithmetic. Similar to the technique in bigfield, we prove the equation holds in integers:
$$\text{acc}_{\text{prev}} \cdot x + \text{op} + P_x \cdot v + P_y \cdot v^2 + z_1 \cdot v^3 + z_2 \cdot v^4 - \text{quotient} \cdot q - \text{acc}_{\text{curr}} = 0$$
We verify this by proving the equation holds:
By the Chinese Remainder Theorem, since $2^{272} \cdot r > 2^{514}$ exceeds the maximum possible value, the equation must hold in integers, and thus modulo $q$. More details on this relation are in RELATIONS.md.
The Translator is a fixed-size circuit. Its key constants (from translator_flavor.hpp / constants.hpp):
| Constant | Value | Meaning |
|---|---|---|
NUM_LIMB_BITS | 68 | width of a non-native limb (one $\mathbb{F}_r$ chunk of an $\mathbb{F}_q$ value) |
MICRO_LIMB_BITS | 14 | width of a microlimb (the finer chunk used for range constraints) |
LOG_MINI_CIRCUIT_SIZE | 13 | $\log_2$ of the mini-circuit size |
MINI_CIRCUIT_SIZE | $2^{13}$ | rows in the mini-circuit (where the witness actually lives) |
CONCATENATION_GROUP_SIZE | 16 | mini-circuit-size columns concatenated into one full-circuit column |
NUM_CONCATENATED_POLYS | 5 | number of concatenated range-constraint polynomials |
NUM_OP_QUEUE_WIRES | 4 | op-queue transcript columns (op, x_lo_y_hi, x_hi_z_1, y_lo_z_2) |
Mini-circuit vs. full circuit. Witness generation happens in the mini-circuit of MINI_CIRCUIT_SIZE = 2^13 rows. Range-constraint columns are then concatenated in groups of CONCATENATION_GROUP_SIZE = 16 into full-circuit-size polynomials, so the full circuit has $\log$-size LOG_MINI_CIRCUIT_SIZE + log2(CONCATENATION_GROUP_SIZE) = 13 + 4 = 17 (this is the 17 rounds of the joint sumcheck). See Concatenation.
Two fields. The Translator's native field is $\mathbb{F}_r$ (the BN254 scalar field); the values it reduces — BN254 base-field elements — live in $\mathbb{F}_q$, which is non-native here ($q > r$), and the accumulator identity is checked $\bmod\ q$. This is the opposite convention to the ECCVM, whose native field is $\mathbb{F}_q$.
A quick reference for terms and columns that are easy to confuse. Full treatment is in the linked sections.
| Concern | Location |
|---|---|
| Columns / entities (canonical list) | translator_vm/translator_flavor.hpp |
| Witness generation | translator_vm/translator_circuit_builder.{hpp,cpp} |
| Constraints | relations/translator_vm/ — see RELATIONS.md |
| Prover / Verifier | translator_vm/translator_prover.cpp, translator_vm/translator_verifier.cpp |
| Term | The trap | What it actually means |
|---|---|---|
| native $\mathbb{F}_r$ vs. non-native $\mathbb{F}_q$ | which field is which? | The Translator computes **natively in $\mathbb{F}_r$**; the modulus it reduces by is $q$ (the BN254 base field $\mathbb{F}_q$, with $q > r$). This is the opposite of the ECCVM (native $\mathbb{F}_q$). |
| limb (68-bit) vs. microlimb (14-bit) | both "limbs" | A limb (NUM_LIMB_BITS = 68) is one $\mathbb{F}_r$ chunk of a non-native $\mathbb{F}_q$ value (bigfield-style). A microlimb (MICRO_LIMB_BITS = 14) is the finer chunk a limb is split into for range constraints (the *_range_constraint_* columns). |
| mod $2^{272}$ and mod $r$ | redundant checks? | The integer identity is proven both mod $2^{272}$ (68-bit-limb arithmetic, as two 136-bit halves) and mod $r$ (natively). By CRT, since $2^{272}\cdot r$ exceeds the maximum possible value, it then holds over the integers, hence mod $q$. Neither check alone suffices. |
| mini-circuit vs. full circuit | one size? | The witness lives in the mini-circuit (2^13); range-constraint columns are concatenated ×16 into the full circuit (2^17). See Concatenation. |
| even rows vs. odd rows | which row does what? | A 2-row cycle: even rows (2i) are computation rows where the non-native relation is checked; odd rows (2i+1) are storage rows whose values (including the previous accumulator) are read from even rows via shifts. |
| op-queue processing order | first op → first row? | The op queue is processed in reverse: acc_0 is built from the last op op_{n-1}, and the final accumulator from op_0. The "previous accumulator" for the last op is 0. |
x (evaluation challenge) vs. v (batching challenge) | two challenges | Both $\in \mathbb{F}_q$. v batches the 5 values per op (op, P_x, P_y, z_1, z_2) via powers $v,\dots,v^4$; x combines all ops via Horner (powers of x). |
z_1, z_2 vs. the accumulator | z_1, z_2 are the decomposed 128-bit scalar of one op ($z = z_1 + 2^{128} z_2$); the accumulator is the running batched evaluation across all ops. | |
*_binary_limbs_* vs. *_range_constraint_* | *_binary_limbs_* hold the four 68-bit limbs of a value (e.g. accumulators_binary_limbs_0..3); the *_range_constraint_* columns hold the 14-bit microlimb decomposition that range-checks those limbs. | |
the op-queue columns x_lo_y_hi, x_hi_z_1, y_lo_z_2 | odd names | The 4 op-queue transcript columns pack op data across the 2-row cycle; each non-op column carries two limbs (x_lo_y_hi = P_x low limb + P_y high limb, etc.). They are shared with the merge protocol: the same commitments are produced once in the kernel's Oink phase and reused, so the Translator does not commit to them independently. |
ordered_extra_range_constraints_numerator | a witness column | It is the only precomputed selector that needs a commitment (all other precomputed columns are verifier-computable); it seeds the sorted-list range argument. |
The Translator circuit has 81 witness columns, organized into:
EccOpQueue transcript ($\texttt{op}, P_x, P_y, z_1, z_2$ encoded across 2 rows)The circuit operates on a 2-row cycle structure. Each EccOpQueue entry occupies exactly 2 rows:
The opcode is constrained to 0 on odd rows by the Opcode Constraint Relation — a soundness requirement: the non-native accumulator reads only even rows, so a genuine opcode parked on an odd row would be silently skipped, excluding that ECC operation from the batched evaluation.
While enforcing constraints on the even rows, we can access values from the "next" row (which is odd) using shifted column polynomials. As hinted earlier, the "previous" accumulator value needed for computation is stored at odd row $(2i+1)$. This value becomes the "current" accumulator for the next even row $(2i+2)$:
| Operation index | $0$ | $1$ | $\quad \dots \quad$ | $(n-2)$ | $(n-1)$ |
|---|---|---|---|---|---|
| Current accumulator | $\textcolor{violet}{\text{acc}(n-1)}$ | $\textcolor{brown}{\text{acc}(n-2)}$ | $\quad \dots \quad$ | $\textcolor{lightgreen}{\text{acc}(1)}$ | $\textcolor{orange}{\text{acc}(0)}$ |
| Previous accumulator | $\textcolor{brown}{\text{acc}(n-2)}$ | $\textcolor{grey}{\text{acc}(n-3)}$ | $\quad \dots \quad$ | $\textcolor{orange}{\text{acc}(0)}$ | $0$ |
These columns directly represent the EccOpQueue transcript:
| Column Name | Even Row $(2i)$ | Odd Row $(2i+1)$ | Description |
|---|---|---|---|
OP | $\texttt{op} \in \lbrace 0, 3, 4, 8\rbrace$ | 0 (no-op) | Opcode (the type of elliptic curve operation) |
X_LO_Y_HI | $P_{x,\text{lo}}$ (136 bits) | $P_{y,\text{hi}}$ (118 bits) | Low 136 bits of $x$-coordinate and high 118 bits of $y$-coordinate |
X_HI_Z_1 | $P_{x,\text{hi}}$ (118 bits) | $z_1$ (128 bits) | High 118 bits of $x$-coordinate and first scalar |
Y_LO_Z_2 | $P_{y,\text{lo}}$ (136 bits) | $z_2$ (128 bits) | Low 136 bits of $y$-coordinate and second scalar |
Encoding scheme: Point coordinates $P_x$ and $P_y$ are each 254 bits, split as:
These columns store finer-grained limb decompositions for non-native arithmetic:
| Column Group | Even Row $(2i)$ | Odd Row $(2i+1)$ | Bits | Purpose |
|---|---|---|---|---|
P_X_LOW_LIMBS | $P_{x,0}^{\text{lo}} = P_{x, 0}$ | $P_{x,1}^{\text{lo}} = P_{x, 1}$ | 68 | Limbs 0 & 1 of $P_{x}$ |
P_X_HIGH_LIMBS | $P_{x,0}^{\text{hi}} = P_{x, 2}$ | $P_{x,1}^{\text{hi}} = P_{x, 3}$ | 68, 50 | Limbs 2 & 3 of $P_{x}$ |
P_Y_LOW_LIMBS | $P_{y,0}^{\text{lo}} = P_{y, 0}$ | $P_{y,1}^{\text{lo}} = P_{y, 1}$ | 68 | Limbs 0 & 1 of $P_{y}$ |
P_Y_HIGH_LIMBS | $P_{y,0}^{\text{hi}} = P_{y, 2}$ | $P_{y,1}^{\text{hi}} = P_{y, 3}$ | 68, 50 | Limbs 2 & 3 of $P_{y}$ |
Z_LOW_LIMBS | $z_{1,0}$ | $z_{2,0}$ | 68 | Low limbs of $z_1$ and $z_2$ |
Z_HIGH_LIMBS | $z_{1,1}$ | $z_{2,1}$ | 60 | High limbs of $z_1$ and $z_2$ |
ACCUMULATORS_BINARY_LIMBS_0 | $a_0^{\text{curr}}$ | $a_0^{\text{prev}}$ | 68 | Limb 0 of current/previous accumulator |
ACCUMULATORS_BINARY_LIMBS_1 | $a_1^{\text{curr}}$ | $a_1^{\text{prev}}$ | 68 | Limb 1 of current/previous accumulator |
ACCUMULATORS_BINARY_LIMBS_2 | $a_2^{\text{curr}}$ | $a_2^{\text{prev}}$ | 68 | Limb 2 of current/previous accumulator |
ACCUMULATORS_BINARY_LIMBS_3 | $a_3^{\text{curr}}$ | $a_3^{\text{prev}}$ | 50 | Limb 3 of current/previous accumulator |
QUOTIENT_LOW_BINARY_LIMBS | $q_0$ | $q_1$ | 68 | Limbs 0 & 1 of quotient $\mathcal{Q}$ |
QUOTIENT_HIGH_BINARY_LIMBS | $q_2$ | $q_3$ | 68, 52 | Limbs 2 & 3 of quotient $\mathcal{Q}$ |
RELATION_WIDE_LIMBS | $c^{\text{lo}}$ | $c^{\text{hi}}$ | 84 | Carry/overflow from mod $2^{136}$ checks |
Key insight: The accumulator columns demonstrate the shift mechanism:
Each limb is further decomposed into 14-bit microlimbs for range checking. Each 68-bit limb has 5 microlimbs (14 bits each) plus a "tail" microlimb that enforces tight range constraints. The columns are organized as follows:
| Column Group | Even Row $(2i)$ | Odd Row $(2i+1)$ |
|---|---|---|
| Coordinate $P_x$ microlimbs | ||
P_X_LOW_LIMBS_RANGE_CONSTRAINT_0 | $P_{x,0}[0]$ | $P_{x,1}[0]$ |
P_X_LOW_LIMBS_RANGE_CONSTRAINT_1 | $P_{x,0}[1]$ | $P_{x,1}[1]$ |
P_X_LOW_LIMBS_RANGE_CONSTRAINT_2 | $P_{x,0}[2]$ | $P_{x,1}[2]$ |
P_X_LOW_LIMBS_RANGE_CONSTRAINT_3 | $P_{x,0}[3]$ | $P_{x,1}[3]$ |
P_X_LOW_LIMBS_RANGE_CONSTRAINT_4 | $P_{x,0}[4]$ | $P_{x,1}[4]$ |
P_X_HIGH_LIMBS_RANGE_CONSTRAINT_0 | $P_{x,2}[0]$ | $P_{x,3}[0]$ |
P_X_HIGH_LIMBS_RANGE_CONSTRAINT_1 | $P_{x,2}[1]$ | $P_{x,3}[1]$ |
P_X_HIGH_LIMBS_RANGE_CONSTRAINT_2 | $P_{x,2}[2]$ | $P_{x,3}[2]$ |
P_X_HIGH_LIMBS_RANGE_CONSTRAINT_3 | $P_{x,2}[3]$ | $P_{x,3}[3]$ |
P_X_HIGH_LIMBS_RANGE_CONSTRAINT_4 | $P_{x,2}[4]$ | $\textcolor{yellow}{P_{x,3}[\textsf{tail}]}$ (reassigned) |
| Coordinate $P_y$ microlimbs | ||
P_Y_LOW_LIMBS_RANGE_CONSTRAINT_0 | $P_{y,0}[0]$ | $P_{y,1}[0]$ |
P_Y_LOW_LIMBS_RANGE_CONSTRAINT_1 | $P_{y,0}[1]$ | $P_{y,1}[1]$ |
P_Y_LOW_LIMBS_RANGE_CONSTRAINT_2 | $P_{y,0}[2]$ | $P_{y,1}[2]$ |
P_Y_LOW_LIMBS_RANGE_CONSTRAINT_3 | $P_{y,0}[3]$ | $P_{y,1}[3]$ |
P_Y_LOW_LIMBS_RANGE_CONSTRAINT_4 | $P_{y,0}[4]$ | $P_{y,1}[4]$ |
P_Y_HIGH_LIMBS_RANGE_CONSTRAINT_0 | $P_{y,2}[0]$ | $P_{y,3}[0]$ |
P_Y_HIGH_LIMBS_RANGE_CONSTRAINT_1 | $P_{y,2}[1]$ | $P_{y,3}[1]$ |
P_Y_HIGH_LIMBS_RANGE_CONSTRAINT_2 | $P_{y,2}[2]$ | $P_{y,3}[2]$ |
P_Y_HIGH_LIMBS_RANGE_CONSTRAINT_3 | $P_{y,2}[3]$ | $P_{y,3}[3]$ |
P_Y_HIGH_LIMBS_RANGE_CONSTRAINT_4 | $P_{y,2}[4]$ | $\textcolor{yellow}{P_{y,3}[\textsf{tail}]}$ (reassigned) |
| Coordinate $z_1$ and $z_2$ microlimbs | ||
Z_LOW_LIMBS_RANGE_CONSTRAINT_0 | $z_{1,0}[0]$ | $z_{2,0}[0]$ |
Z_LOW_LIMBS_RANGE_CONSTRAINT_1 | $z_{1,0}[1]$ | $z_{2,0}[1]$ |
Z_LOW_LIMBS_RANGE_CONSTRAINT_2 | $z_{1,0}[2]$ | $z_{2,0}[2]$ |
Z_LOW_LIMBS_RANGE_CONSTRAINT_3 | $z_{1,0}[3]$ | $z_{2,0}[3]$ |
Z_LOW_LIMBS_RANGE_CONSTRAINT_4 | $z_{1,0}[4]$ | $z_{2,0}[4]$ |
Z_HIGH_LIMBS_RANGE_CONSTRAINT_0 | $z_{1,1}[0]$ | $z_{2,1}[0]$ |
Z_HIGH_LIMBS_RANGE_CONSTRAINT_1 | $z_{1,1}[1]$ | $z_{2,1}[1]$ |
Z_HIGH_LIMBS_RANGE_CONSTRAINT_2 | $z_{1,1}[2]$ | $z_{2,1}[2]$ |
Z_HIGH_LIMBS_RANGE_CONSTRAINT_3 | $z_{1,1}[3]$ | $z_{2,1}[3]$ |
Z_HIGH_LIMBS_RANGE_CONSTRAINT_4 | $z_{1,1}[4]$ | $z_{2,1}[4]$ |
| Current and previous accumulator microlimbs | ||
ACCUMULATOR_LOW_LIMBS_RANGE_CONSTRAINT_0 | $a_{0}^{\text{curr}}[0]$ | $a_{1}^{\text{curr}}[0]$ |
ACCUMULATOR_LOW_LIMBS_RANGE_CONSTRAINT_1 | $a_{0}^{\text{curr}}[1]$ | $a_{1}^{\text{curr}}[1]$ |
ACCUMULATOR_LOW_LIMBS_RANGE_CONSTRAINT_2 | $a_{0}^{\text{curr}}[2]$ | $a_{1}^{\text{curr}}[2]$ |
ACCUMULATOR_LOW_LIMBS_RANGE_CONSTRAINT_3 | $a_{0}^{\text{curr}}[3]$ | $a_{1}^{\text{curr}}[3]$ |
ACCUMULATOR_LOW_LIMBS_RANGE_CONSTRAINT_4 | $a_{0}^{\text{curr}}[4]$ | $a_{1}^{\text{curr}}[4]$ |
ACCUMULATOR_HIGH_LIMBS_RANGE_CONSTRAINT_0 | $a_{2}^{\text{curr}}[0]$ | $a_{3}^{\text{curr}}[0]$ |
ACCUMULATOR_HIGH_LIMBS_RANGE_CONSTRAINT_1 | $a_{2}^{\text{curr}}[1]$ | $a_{3}^{\text{curr}}[1]$ |
ACCUMULATOR_HIGH_LIMBS_RANGE_CONSTRAINT_2 | $a_{2}^{\text{curr}}[2]$ | $a_{3}^{\text{curr}}[2]$ |
ACCUMULATOR_HIGH_LIMBS_RANGE_CONSTRAINT_3 | $a_{2}^{\text{curr}}[3]$ | $a_{3}^{\text{curr}}[3]$ |
ACCUMULATOR_HIGH_LIMBS_RANGE_CONSTRAINT_4 | $a_{2}^{\text{curr}}[4]$ | $\textcolor{yellow}{a_{3}[\textsf{tail}]}$ (reassigned) |
| Quotient microlimbs | ||
QUOTIENT_LOW_LIMBS_RANGE_CONSTRAINT_0 | $q_{0}[0]$ | $q_{1}[0]$ |
QUOTIENT_LOW_LIMBS_RANGE_CONSTRAINT_1 | $q_{0}[1]$ | $q_{1}[1]$ |
QUOTIENT_LOW_LIMBS_RANGE_CONSTRAINT_2 | $q_{0}[2]$ | $q_{1}[2]$ |
QUOTIENT_LOW_LIMBS_RANGE_CONSTRAINT_3 | $q_{0}[3]$ | $q_{1}[3]$ |
QUOTIENT_LOW_LIMBS_RANGE_CONSTRAINT_4 | $q_{0}[4]$ | $q_{1}[4]$ |
QUOTIENT_HIGH_LIMBS_RANGE_CONSTRAINT_0 | $q_{2}[0]$ | $q_{3}[0]$ |
QUOTIENT_HIGH_LIMBS_RANGE_CONSTRAINT_1 | $q_{2}[1]$ | $q_{3}[1]$ |
QUOTIENT_HIGH_LIMBS_RANGE_CONSTRAINT_2 | $q_{2}[2]$ | $q_{3}[2]$ |
QUOTIENT_HIGH_LIMBS_RANGE_CONSTRAINT_3 | $q_{2}[3]$ | $q_{3}[3]$ |
QUOTIENT_HIGH_LIMBS_RANGE_CONSTRAINT_4 | $q_{2}[4]$ | $\textcolor{yellow}{q_{3}[\textsf{tail}]}$ (reassigned) |
| Carry microlimbs | ||
RELATION_WIDE_LIMBS_RANGE_CONSTRAINT_0 | $c^{\text{lo}}[0]$ | $c^{\text{hi}}[0]$ |
RELATION_WIDE_LIMBS_RANGE_CONSTRAINT_1 | $c^{\text{lo}}[1]$ | $c^{\text{hi}}[1]$ |
RELATION_WIDE_LIMBS_RANGE_CONSTRAINT_2 | $c^{\text{lo}}[2]$ | $c^{\text{hi}}[2]$ |
RELATION_WIDE_LIMBS_RANGE_CONSTRAINT_3 | $c^{\text{lo}}[3]$ | $c^{\text{hi}}[3]$ |
| Tail microlimbs | ||
P_X_LOW_LIMBS_RANGE_CONSTRAINT_TAIL | $\textcolor{yellow}{P_{x,0}[\textsf{tail}]}$ | $\textcolor{yellow}{P_{x,1}[\textsf{tail}]}$ |
P_X_HIGH_LIMBS_RANGE_CONSTRAINT_TAIL | $\textcolor{yellow}{P_{x,2}[\textsf{tail}]}$ | $c^{\text{lo}}[4]$ (reassigned) |
P_Y_LOW_LIMBS_RANGE_CONSTRAINT_TAIL | $\textcolor{yellow}{P_{y,0}[\textsf{tail}]}$ | $\textcolor{yellow}{P_{y,1}[\textsf{tail}]}$ |
P_Y_HIGH_LIMBS_RANGE_CONSTRAINT_TAIL | $\textcolor{yellow}{P_{y,2}[\textsf{tail}]}$ | $c^{\text{hi}}[4]$ (reassigned) |
Z_LOW_LIMBS_RANGE_CONSTRAINT_TAIL | $\textcolor{yellow}{z_{1,0}[\textsf{tail}]}$ | $\textcolor{yellow}{z_{2,0}[\textsf{tail}]}$ |
Z_HIGH_LIMBS_RANGE_CONSTRAINT_TAIL | $\textcolor{yellow}{z_{1,1}[\textsf{tail}]}$ | $\textcolor{yellow}{z_{2,1}[\textsf{tail}]}$ |
ACCUMULATOR_LOW_LIMBS_RANGE_CONSTRAINT_TAIL | $\textcolor{yellow}{a_{0}^{\text{curr}}[\textsf{tail}]}$ | $\textcolor{yellow}{a_{1}^{\text{curr}}[\textsf{tail}]}$ |
ACCUMULATOR_HIGH_LIMBS_RANGE_CONSTRAINT_TAIL | $\textcolor{yellow}{a_{2}^{\text{curr}}[\textsf{tail}]}$ | $c^{\text{lo}}[5]$ (reassigned) |
QUOTIENT_LOW_LIMBS_RANGE_CONSTRAINT_TAIL | $\textcolor{yellow}{q_{0}[\textsf{tail}]}$ | $\textcolor{yellow}{q_{1}[\textsf{tail}]}$ |
QUOTIENT_HIGH_LIMBS_RANGE_CONSTRAINT_TAIL | $\textcolor{yellow}{q_{2}[\textsf{tail}]}$ | $c^{\text{hi}}[5]$ (reassigned) |
The tail microlimbs (shown in yellow) enforce tight range constraints by ensuring top limbs use exactly the required number of bits (explained in the Decomposition Relation section of RELATIONS.md).
Column reuse optimization: Some columns are reassigned in odd rows to hold tail microlimbs for limbs that don't need all 5 microlimbs. For example, limb $P_{x, 3}$ is only 50 bits (= 3×14 + 8), requiring only 4 microlimbs. The 5th microlimb column P_X_HIGH_LIMBS_RANGE_CONSTRAINT_4 at odd rows is therefore reassigned to hold the tail microlimb for $P_{x,3}$ (and carry values $c^{\text{lo}}[4]$, $c^{\text{hi}}[4]$, etc.).
Some columns are "virtual" and not explicitly stored in the witness trace. Instead, they are computed on-the-fly during relation evaluation using existing columns. These include:
The mini-circuit layout is illustrated below:
EccOpQueue transcriptColor coding in the diagram:
$$ \begin{array}{rlllll} z_1 & \overbrace{ \textcolor{violet}{ \boxed{ \hspace{0.95cm} } } }^{4} & \textsf{\scriptsize $\longleftarrow$ shiftability zeros} & \overbrace{ \textcolor{violet}{ \boxed{ \hspace{1.45cm} } } }^{13} & \overbrace{ \textcolor{violet}{ \boxed{ \hspace{3.85cm} } } }^{64} \[2pt] r_{\textsf{start}} & \textcolor{grey}{ \boxed{ \begin{array}{c} \hspace{0.6cm} \ \end{array} } } & \textsf{\scriptsize $\longleftarrow$ start randomness} & \textcolor{violet}{ \boxed{ \begin{array}{c} \hspace{1.1cm} \ \end{array} } } & \textcolor{violet}{ \boxed{ \begin{array}{c} \hspace{3.5cm} \ \end{array} } } \ \[-10pt] n - r_{\textsf{start}} - r_{\textsf{end}} - z_1 & \textcolor{orange}{ \boxed{ \begin{array}{c} \hspace{0.6cm} \ \ \ \ \ \ \ \end{array} } } & \textsf{\scriptsize $\longleftarrow$ main ops} & \textcolor{orange}{ \boxed{ \begin{array}{c} \hspace{1.1cm} \ \ \ \ \ \ \ \end{array} } } & \textcolor{orange}{ \boxed{ \begin{array}{c} \hspace{3.5cm} \ \ \ \ \ \ \ \end{array} } } \ \[-10pt] r_{\textsf{end}} & \textcolor{grey}{ \boxed{ \begin{array}{c} \hspace{0.6cm} \ \end{array} } } & \textsf{\scriptsize $\longleftarrow$ end randomness} & \textcolor{violet}{ \boxed{ \begin{array}{c} \hspace{1.1cm} \ \end{array} } } & \textcolor{violet}{ \boxed{ \begin{array}{c} \hspace{3.5cm} \ \end{array} } } \end{array} $$
In our implementation, mini-circuit size is $n = 2^{13}$. We have $z_1 = 2$ (two zero rows at the start to ensure shiftability), $r_{\textsf{start}} = 6$ (rows for three random ops at start), and $r_{\textsf{end}} = 4$ (rows for two random ops at end). Thus, the number of main operation rows is $n - r_{\textsf{start}} - r_{\textsf{end}} - z_1 = 8180$.
The random ops serve dual purposes for zero-knowledge:
1. Merge Protocol ZK (Grey boxes in 4 OP columns):
2. ZK Sumcheck Masking (Initially purple, then filled with random for non-OP columns):
NUM_DISABLED_ROWS_IN_SUMCHECK = 4 (denoted as $m$ in the Lagrange table below)The circuit uses Lagrange polynomials to control which constraints are active: ($I_{\text{size}} = 16$ is the number of columns concatenated together)
| Polynomial | Description | Active Rows |
|---|---|---|
lagrange_first | First row | $i = 0$ |
lagrange_real_last | Last row in full circuit (before masking) | $i = N -$ MAX_RANDOM_VALUES_PER_ORDERED $- 1 = 2^{17} - 64 - 1 = 131007$ |
lagrange_last | Last row in full circuit | $i = 2^{17} - 1$ |
lagrange_masking | Scattered masking rows in full circuit | $i \in \lbrace j \cdot 2^{13} + k : j \in [0,16), k \in [2^{13} - m, 2^{13})\rbrace$ |
lagrange_mini_masking | Masking rows in mini circuit | $i \in [z_1, \ z_1 + r_{\textsf{start}}) \cup [n - r_{\textsf{end}}, \ n)$ |
lagrange_even_in_minicircuit | Even indices in real mini-circuit | $i \in \lbrace u \ \mid \ u \ \bmod \ 2 = 0, \ (z_1 + r_{\textsf{start}}) \leq u < n - r_{\textsf{end}}\rbrace$ |
lagrange_odd_in_minicircuit | Odd indices in real mini-circuit | $i \in \lbrace u \ \mid \ u \ \bmod \ 2 = 1, \ (z_1 + r_{\textsf{start}}) \leq u < n - r_{\textsf{end}}\rbrace$ |
lagrange_last_in_minicircuit | Last row in mini-circuit | $i = 8191$ (mini) |
lagrange_result_row | Row containing final accumulator result | $i = (z_1 + r_{\textsf{start}})$ |
lagrange_last_in_minicircuit | Last real row in mini-circuit | $i = (n - r_{\textsf{end}}) - 1$ |
lagrange_ordered_masking | Contiguous masking at end of circuit | $i \in [N - 64, N)$ |
The Translator must range-constrain approximately 64 different microlimb sets using permutation argument (and the delta range constraint). The permutation argument's degree equals $1 +$ NUM_COLS, where NUM_COLS is the number of columns being permuted:
$$ z_{\textsf{perm}}[i+1] \cdot \prod_{j=1}^{\textsf{NUM_COLS}} (\textsf{ordered}[j] + \gamma) = z_{\textsf{perm}}[i] \cdot \prod_{j=1}^{\textsf{NUM_COLS}} (\textsf{concatenated}[j] + \gamma) $$
The Problem: Permuting all ~64 microlimb columns simultaneously would require us to commit to all of them. Further, since the relation degree would be $1 + 64 = 65$, computing the sumcheck univariates could be a significant overhead for the prover. The prover would need to then commit to the univariates (instead of sending evaluations directly).
The Solution: Concatenate 16 logical columns into one polynomial, and create 4 such polynomials (plus 1 for the extra column). Each group can then perform an independent permutation check with degree $1 + 5 = 6$ (or 7 with Lagrange selector). This reduces the relation degree from 65 to 7.
To compute the concatenated polynomials, we group 16 polynomials together and concatenate them end-to-end (lane bits as MSB). Consider the following 16 polynomials each of size $n=2^{13}$ in the mini-circuit:
$$ \newcommand{\arraystretch}{1.2} \begin{array}{|c|c|c|c|c|c|} \hline \textsf{index} & \textsf{poly 1} & \textsf{poly 2} & \textsf{poly 3} & \ldots & \textsf{poly 16} \ \hline 0 & \textcolor{skyblue}{a_0} & \textcolor{orange}{b_0} & \textcolor{lightgreen}{c_0} & \quad \ldots \quad & \textcolor{firebrick}{p_0} \ 1 & \textcolor{skyblue}{a_1} & \textcolor{orange}{b_1} & \textcolor{lightgreen}{c_1} & \quad \ldots \quad & \textcolor{firebrick}{p_1} \ 2 & \textcolor{skyblue}{a_2} & \textcolor{orange}{b_2} & \textcolor{lightgreen}{c_2} & \quad \ldots \quad & \textcolor{firebrick}{p_2} \ 3 & \textcolor{skyblue}{a_3} & \textcolor{orange}{b_3} & \textcolor{lightgreen}{c_3} & \quad \ldots \quad & \textcolor{firebrick}{p_3} \[5pt] \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \[5pt] n-1 & \textcolor{skyblue}{a_{n-1}} & \textcolor{orange}{b_{n-1}} & \textcolor{lightgreen}{c_{n-1}} & \quad \ldots \quad & \textcolor{firebrick}{p_{n-1}} \ \hline \end{array} \quad \longrightarrow \quad \begin{array}{|c|c|c|} \hline \textsf{lane} & \textsf{index} & \textsf{concatenated} \ \hline 0 & 0 & \textcolor{skyblue}{a_0} \ 0 & 1 & \textcolor{skyblue}{a_1} \ 0 & 2 & \textcolor{skyblue}{a_2} \ \vdots & \vdots & \vdots \[3pt] 0 & n-1 & \textcolor{skyblue}{a_{n-1}} \ \hline 1 & n & \textcolor{orange}{b_0} \ 1 & n+1 & \textcolor{orange}{b_1} \ 1 & n+2 & \textcolor{orange}{b_2} \ \vdots & \vdots & \vdots \[3pt] 1 & 2n-1 & \textcolor{orange}{b_{n-1}} \ \hline \vdots & \vdots & \vdots \ \hline 15 & 15n & \textcolor{firebrick}{p_0} \ 15 & 15n+1 & \textcolor{firebrick}{p_1} \ 15 & 15n+2 & \textcolor{firebrick}{p_2} \ \vdots & \vdots & \vdots \[3pt] 15 & 16n-1 & \textcolor{firebrick}{p_{n-1}} \ \hline \end{array} $$
For 64 microlimb columns, we have 4 groups of 16 columns each, resulting in four concatenated polynomials each of size $16n = 2^{17}$. The prover commits to these 5 concatenated polynomials (4 range constraint groups + 1 extra). Each of these groups performs an independent permutation check:
The permutation argument verifies that within each group, the concatenated values are a permutation of the ordered (sorted) values. Due to concatenation, the total circuit size increases 16×, requiring more zero-padding. Concatenation trades circuit size (inexpensive) for relation degree (expensive). The 16× size increase is acceptable given the 9× degree reduction.
Effect on Commitment Scheme: The prover commits to the 5 concatenated polynomials. This reduces the proof size and recursive verification cost compared to committing to 64 individual microlimb wires. The verifier reconstructs evaluations of the concatenated polynomials from individual wire evaluations using Lagrange decomposition over the top 4 sumcheck challenges.
This section details how the Translator circuit's witness polynomials are populated and how zero-knowledge is achieved through masking.
Witness generation transforms the EccOpQueue from the Mega circuit into the 92 polynomials required by the Translator circuit:
Note: Witness generation happens in the mini-circuit size (2¹³ = 8,192 rows), then is expanded to full circuit size (2¹⁷ = 131,072 rows) through concatenation and zero-padding.
The prover receives the EccOpQueue from the Mega circuit. Each entry contains:
$$\texttt{UltraOp} = \lbrace \texttt{op}, P_x, P_y, z_1, z_2\rbrace$$
For operation $i$ at rows $2i$ (even) and $2i+1$ (odd), populate:
Even row ($2i$):
$$ \begin{aligned} \texttt{OP}[2i] &= \texttt{op}_i \ \texttt{X_LO_Y_HI}[2i] &= P_{x,\text{lo}} = P_x \bmod 2^{136} \ \texttt{X_HI_Z_1}[2i] &= P_{x,\text{hi}} = \lfloor P_x / 2^{136} \rfloor \ \texttt{Y_LO_Z_2}[2i] &= P_{y,\text{lo}} = P_y \bmod 2^{136} \end{aligned} $$
Odd row ($2i+1$):
$$ \begin{aligned} \texttt{OP}[2i+1] &= 0 \ \texttt{X_LO_Y_HI}[2i+1] &= P_{y,\text{hi}} = \lfloor P_y / 2^{136} \rfloor \ \texttt{X_HI_Z_1}[2i+1] &= z_1 \ \texttt{Y_LO_Z_2}[2i+1] &= z_2 \end{aligned} $$
Each 136-bit transcript value is further decomposed into two 68-bit limbs. For $P_{x,\text{lo}}$:
$$P_{x,\text{lo}} = P_{x,0}^{\text{lo}} + 2^{68} \cdot P_{x,1}^{\text{lo}}$$
where:
Even row ($2i$) limb assignments:
$$ \begin{aligned} \texttt{P_X_LOW_LIMBS}[2i] &= P_{x,0}^{\text{lo}} \ \texttt{P_X_HIGH_LIMBS}[2i] &= P_{x,0}^{\text{hi}} \ \texttt{P_Y_LOW_LIMBS}[2i] &= P_{y,0}^{\text{lo}} \ \texttt{P_Y_HIGH_LIMBS}[2i] &= P_{y,0}^{\text{hi}} \ \texttt{Z_LOW_LIMBS}[2i] &= z_{1,0} \ \texttt{Z_HIGH_LIMBS}[2i] &= z_{1,1} \end{aligned} $$
Odd row ($2i+1$) limb assignments:
$$ \begin{aligned} \texttt{P_X_LOW_LIMBS}[2i+1] &= P_{x,1}^{\text{lo}} \ \texttt{P_X_HIGH_LIMBS}[2i+1] &= P_{x,1}^{\text{hi}} \ \texttt{P_Y_LOW_LIMBS}[2i+1] &= P_{y,1}^{\text{lo}} \ \texttt{P_Y_HIGH_LIMBS}[2i+1] &= P_{y,1}^{\text{hi}} \ \texttt{Z_LOW_LIMBS}[2i+1] &= z_{2,0} \ \texttt{Z_HIGH_LIMBS}[2i+1] &= z_{2,1} \end{aligned} $$
For each even row $2i$, compute the accumulator update and quotient. The accumulator evolves as:
$$a^{\text{curr}} = a^{\text{prev}} \cdot x + \texttt{op} + P_x \cdot v + P_y \cdot v^2 + z_1 \cdot v^3 + z_2 \cdot v^4 \pmod{q}$$
The current and the previous accumulators are decomposed into 4 limbs each:
$$ \begin{aligned} a^{\text{curr}} &= a_0^{\text{curr}}
Since we're working in $\mathbb{F}_r$ (not $\mathbb{F}_q$), we must compute the quotient $\mathcal{Q}$ such that:
$$a^{\text{prev}} \cdot x + \texttt{op} + P_x \cdot v + P_y \cdot v^2 + z_1 \cdot v^3 + z_2 \cdot v^4 = \mathcal{Q} \cdot q + a^{\text{curr}}$$
$$ \implies \mathcal{Q} = \left\lfloor \frac{a^{\text{prev}} \cdot x + \texttt{op} + P_x \cdot v + P_y \cdot v^2 + z_1 \cdot v^3 + z_2 \cdot v^4}{q} \right\rfloor $$
The quotient is then decomposed into 4 limbs (68 + 68 + 68 + 52 bits):
$$\mathcal{Q} = q_0 + 2^{68} \cdot q_1 + 2^{136} \cdot q_2 + 2^{204} \cdot q_3$$
Why 256 bits suffices for the quotient: The scalars $z_1, z_2$ are constrained to be 128-bit values while the points $P_x, P_y$ are constrained to be less than the field modulus $q$. The evaluation challenge $x$ and batching challenge $v$ both should be 127-bit values (derived from Fiat-Shamir), however a malicious prover can try to set them close to $q$ to maximize the numerator. Thus, the maximum numerator in the quotient calculation can be approximated as follows: The evaluation challenge $x$ and batching challenge $v$ are both 128-bit values (derived from Fiat-Shamir). The maximum numerator in the accumulation step is dominated by the term $P_y \cdot v^2$, giving approximately: $$N_{\max} \approx 3 \cdot q^2 + 2 \cdot q \cdot 2^{128}$$ Therefore, the maximum quotient is: $$\mathcal{Q}_{\max} = \left\lfloor \frac{N_{\max}}{q} \right\rfloor \approx 3q + 2^{129} < 3 \cdot2^{254} + 2^{129} < 2^{256}$$ Thus, 256 bits provides sufficient range with a 2-bit safety margin. The circuit enforces this constraint via range checks on the quotient limbs (see RELATIONS.md).
Carry computation: The relation-wide limbs $c^{\text{lo}}$ and $c^{\text{hi}}$ (84 bits each) capture overflow from the mod $2^{136}$ checks:
$$c^{\text{lo}} = \left\lfloor \frac{T_0 + 2^{68} \cdot T_1}{2^{136}} \right\rfloor, \quad c^{\text{hi}} = \left\lfloor \frac{c^{\text{lo}} + T_2 + 2^{68} \cdot T_3}{2^{136}} \right\rfloor$$
where $T_0, T_1, T_2, T_3$ are the limb contributions defined in RELATIONS.md.
Each 68-bit limb is decomposed into five 14-bit microlimbs plus a tail microlimb for range tightening. For a general 68-bit limb $\ell$:
$$\ell = \sum_{k=0}^{4} 2^{14k} \cdot m_k$$
where each $m_k \in [0, 2^{14})$ and $m_4 \in [0, 2^{12})$ (since $68 = 14 \times 4 + 12$).
Tail microlimb: To enforce $m_4 < 2^{12}$, compute:
$$m_{\text{tail}} = m_4 \cdot 2^{14-12} = m_4 \cdot 4$$
The decomposition relation enforces $m_{\text{tail}} \in [0, 2^{14})$, which implies $m_4 \in [0, 2^{12})$. For limbs with fewer bits, the tail microlimb is adjusted accordingly.
The 64 microlimb columns are organized into 4 groups of 16 columns each. Each group is concatenated into a single polynomial at full circuit size.
Concatenation formula: For group polynomials $\lbrace p_0, p_1, \ldots, p_{15}\rbrace$ each of mini-size $n = 2^{13}$:
$$p_{\text{concatenated}}[j \cdot n + k] = p_j[k] \quad \text{for } j \in [0, 16), \ k \in [0, n)$$
This expands the circuit from mini-size $2^{13}$ to full size $2^{17} = 2^{13} \times 16$.
Illustration: We have a total of 64 microlimb columns, each with $n = 2^{13}$ rows (mini-circuit size). We illustrate the microlimb distribution and concatenation process below:
$$ \begin{array}{rllll} n - m & \overbrace{ \textcolor{orange}{ \boxed{ \begin{array}{ccccc} \ \ \ & & W & & \ \ \ \ \end{array} } } }^{I_{\textsf{size}}} \ \overbrace{ \textcolor{orange}{ \boxed{ \begin{array}{ccccc} \ \ \ & & W & & \ \ \ \ \end{array} } } }^{I_{\textsf{size}}} \ \overbrace{ \textcolor{orange}{ \boxed{ \begin{array}{ccccc} \ \ \ & & W & & \ \ \ \ \end{array} } } }^{I_{\textsf{size}}} \ \overbrace{ \textcolor{orange}{ \boxed{ \begin{array}{ccccc} \ \ \ & & W & & \ \ \ \ \end{array} } } }^{I_{\textsf{size}}} \[2pt] m & \textcolor{grey}{ \boxed{ \begin{array}{ccccc} & & M & & \ \end{array} } } \ \textcolor{grey}{ \boxed{ \begin{array}{ccccc} & & M & & \ \end{array} } } \ \textcolor{grey}{ \boxed{ \begin{array}{ccccc} & & M & & \ \end{array} } } \ \textcolor{grey}{ \boxed{ \begin{array}{ccccc} & & M & & \ \end{array} } } \end{array}
\xrightarrow[]{\textsf{concatenated polys}}
\begin{array}{ll} I_1 \quad I_2 \quad I_3 \quad I_4 \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} & n - m \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} & m \[5pt] \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \[10pt] \quad\vdots & \scriptstyle{\times\,16\text{ lanes}} \[10pt] \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \end{array} $$
The permutation argument requires proving that the concatenated microlimbs equal the sorted microlimbs. The prover constructs 5 ordered polynomials by collecting microlimbs from all 64 columns, sorting them, and distributing across ordered polynomials with inserted step values. We first describe the mathematical setup and then illustrate the construction steps.
Constants:
Step sequence: The sorted steps $\mathcal{S} = \lbrace s_0, s_1, \ldots, s_{5461}\rbrace$ where: $$s_i = 3i \quad \text{for } i \in [0, 5461], \quad s_{5461} = 16{,}383 = 2^{14} - 1$$
This ensures coverage of all values in $[0, 2^{14})$ with max gap of 3.
For each group $g \in \lbrace 0, 1, 2, 3\rbrace$, collect all microlimbs from its 16 polynomials:
$$\mathcal{M}_g = \bigcup_{j=0}^{15} \Big\lbrace p_{g,j}[i] : i \in [0, (n-m)) \Big\rbrace$$
where $p_{g,j}$ is the $j$-th polynomial in group $g$. Size of each group microlimb set:
$$|\mathcal{M}_g| = 16 \times (n - m)$$
and total microlimbs across all groups: $$|\mathcal{M}_0 \cup \mathcal{M}_1 \cup \mathcal{M}_2 \cup \mathcal{M}_3| = 64 \times (n - m).$$
Each ordered polynomial has size $N$ but must accommodate:
Capacity per ordered polynomial (for circuit microlimbs): $$C_{\text{capacity}} = N_{\text{no-mask}} - N_{\text{steps}} = N_{\text{no-mask}} - 5{,}462$$
This is the maximum number of witnesses each ordered polynomial can hold before adding step values.
For groups 0-3, construct ordered_range_constraints_i by:
Mathematically, for $g \in \lbrace 0, 1, 2, 3\rbrace$:
$$ \text{ordered}[g]_{\text{unsorted}} = \begin{cases} \mathcal{M}_g[k] & \text{if } k < C_{\text{capacity}} \ \mathcal{S}[k - C_{\text{capacity}}] & \text{if } C_{\text{capacity}} \leq k < N_{\text{no-mask}} \ 0 & \text{if } k \geq N_{\text{no-mask}} \text{ (masking region)} \end{cases} $$
Then sort: $$\text{ordered}[g] = \text{sort}(\text{ordered}[g]_{\text{unsorted}})$$
Overflow microlimbs: If $|\mathcal M_g| > C_{\text{capacity}}$, the excess microlimbs go to group 4:
$$\mathcal{M}_{g,\text{overflow}} = \left\lbrace \mathcal{M}_g[k] : k \geq C_{\text{capacity}} \right\rbrace$$
$$|\mathcal{M}_{g,\text{overflow}}| = |\mathcal{M}_g| - C_{\text{capacity}}$$
The 5th ordered polynomial (ordered_range_constraints_4) collects all overflow:
$$\mathcal{M}_{\text{overflow}} = \bigcup_{g=0}^{3} \mathcal{M}_{g,\text{overflow}}$$
Size of overflow: $$|\mathcal{M}_{\text{overflow}}| = 4 \times |\mathcal{M}_{g,\text{overflow}}| = 4 \times (16 \times (n - m) - C_{\text{capacity}})$$
Then construct:
$$ \text{ordered}[4]_{\text{unsorted}} = \begin{cases} \mathcal{M}_{\text{overflow}}[k] & \text{if } k < |\mathcal{M}_{\text{overflow}}| \ \mathcal{S}[k - |\mathcal{M}_{\text{overflow}}|] & \text{if } |\mathcal{M}_{\text{overflow}}| \leq k < |\mathcal{M}_{\text{overflow}}| + N_{\text{steps}} \ 0 & \text{otherwise} \end{cases} $$
Then sort: $$\text{ordered}[4] = \text{sort}(\text{ordered}[4]_{\text{unsorted}})$$
Illustration: We start with the 4 concatenated range constraint polynomials constructed earlier:
$$ \begin{array}{ll} I_1 \quad I_2 \quad I_3 \quad I_4 \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \[5pt] \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \[10pt] \quad\vdots \[10pt] \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \end{array}
\xrightarrow[]{\textsf{add extra numerator}}
\begin{array}{ll} I_1 \quad I_2 \quad I_3 \quad I_4 \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \[5pt] \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \[10pt] \quad\vdots \[10pt] \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{orange}{\boxed{\begin{array}{c}\ \\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \ \textcolor{gray}{\boxed{\begin{array}{c}\[-3pt]\end{array}}} \end{array}
\begin{array}{l} I_5 \ \textcolor{lightgreen}{ \boxed{ \begin{array}{c} s \[1pt] \end{array} }} \ \[-10pt] \textcolor{lightgreen}{ \boxed{ \begin{array}{c} s \[1pt] \end{array} }} \ \[-10pt] \textcolor{lightgreen}{ \boxed{ \begin{array}{c} s \[1pt] \end{array} }} \ \[-10pt] \textcolor{lightgreen}{ \boxed{ \begin{array}{c} s \[1pt] \end{array} }} \ \[-10pt] \textcolor{lightgreen}{ \boxed{ \begin{array}{c} s \[1pt] \end{array} }} \ \[-13pt] \textcolor{violet}{ \boxed{ \begin{array}{c} \ \ z \ \[10pt] \end{array} }} \end{array}
\xrightarrow[]{\textsf{sort into ordered polys}}
\begin{array}{lrrrrr} O_1 \quad O_2 \ \ O_3 \quad O_4 \ \textcolor{orange}{ \boxed{ \begin{array}{c} \ \ \ \ \ \ \[25pt] \end{array} }} \ \textcolor{orange}{ \boxed{ \begin{array}{c} \ \ \ \ \ \ \[25pt] \end{array} }} \ \textcolor{orange}{ \boxed{ \begin{array}{c} \ \ \ \ \ \ \[25pt] \end{array} }} \ \textcolor{orange}{ \boxed{ \begin{array}{c} \ \ \ \ \ \ \[25pt] \end{array} }} \ \[-10pt] \textcolor{lightgreen}{ \boxed{ \begin{array}{c} \[1pt] \end{array} }} \ \textcolor{lightgreen}{ \boxed{ \begin{array}{c} \[1pt] \end{array} }} \ \textcolor{lightgreen}{ \boxed{ \begin{array}{c} \[1pt] \end{array} }} \ \textcolor{lightgreen}{ \boxed{ \begin{array}{c} \[1pt] \end{array} }} \ \[-10pt] \hline\hline \textcolor{gray}{ \boxed{ \begin{array}{c} \[-6pt]\[-6pt] \end{array} }} \ \textcolor{gray}{ \boxed{ \begin{array}{c} \[-6pt]\[-6pt] \end{array} }} \ \textcolor{gray}{ \boxed{ \begin{array}{c} \[-6pt]\[-6pt] \end{array} }} \ \textcolor{gray}{ \boxed{ \begin{array}{c} \[-6pt]\[-6pt] \end{array} }} \ \[-10pt] \textcolor{violet}{ \boxed{ \begin{array}{c} \[-2pt] \end{array} }} \ \textcolor{violet}{ \boxed{ \begin{array}{c} \[-2pt] \end{array} }} \ \textcolor{violet}{ \boxed{ \begin{array}{c} \[-2pt] \end{array} }} \ \textcolor{violet}{ \boxed{ \begin{array}{c} \[-2pt] \end{array} }} \end{array}
\begin{array}{l} O_5 \ \textcolor{orange}{ \boxed{ \begin{array}{c} \[1pt] \end{array} }} \ \[-10pt] \textcolor{orange}{ \boxed{ \begin{array}{c} \[1pt] \end{array} }} \ \[-10pt] \textcolor{orange}{ \boxed{ \begin{array}{c} \[1pt] \end{array} }} \ \[-10pt] \textcolor{orange}{ \boxed{ \begin{array}{c} \[1pt] \end{array} }} \ \[-12pt] \textcolor{lightgreen}{ \boxed{ \begin{array}{c} \[1pt] \end{array} }} \ \[-13pt] \textcolor{violet}{ \boxed{ \begin{array}{c} \[10pt] \end{array} }} \ \[-10pt] \hline\hline \textcolor{gray}{ \boxed{ \begin{array}{c} \[-6pt]\[-6pt] \end{array} }} & \longleftarrow {\scriptsize \textsf{randomness of size}} \left\lfloor\frac{4 \cdot m \cdot I_{\textsf{size}}}{5}\right\rfloor \ \[-10pt] \textcolor{violet}{ \boxed{ \begin{array}{c} \[-2pt] \end{array} }} \end{array} $$
In our case, we have $m=4$ and $I_{\textsf{size}}=16$ which results in $(m \cdot I_{\textsf{size}}) = 64$ masked rows in each concatenated polynomial. Thus, each ordered polynomial will have at least $\left\lfloor\frac{4 \cdot 64}{5}\right\rfloor = 51$ masked rows. The remainder masked rows are added to the respective ordered polynomials. The masking rows in each ordered polynomial are padded with zero values to ensure the multiset equality holds.
As illustrated, the two sets of concatenated and ordered polynomials satisfy the multiset equality: $$\bigcup_{i=1}^5 I_i = \bigcup_{i=1}^5 O_i.$$
To achieve zero-knowledge, the translator uses two independent masking mechanisms:
To hide polynomial evaluations used in ZK sumcheck, random values are added to the last $m = r_{\textsf{end}} = 4$ rows of the mini-circuit for all non-OP-queue wires (13 limb decomposition columns, 64 microlimb columns).
lagrange_mini_masking marks these last 4 rows as maskedFor the permutation argument over microlimbs, a separate masking mechanism is used. For each of the witness polynomials, the masking region is defined as the last $m = r_{\textsf{end}}$ rows of the mini-circuit size, indexed as:
$$[n - m, \ n).$$
With concatenation, the 4 concatenated polynomials have random values at positions:
$$[N - m \cdot I_{\textsf{size}}, \ N).$$
Where $m = r_{\textsf{end}} = 4$ (the same 4 rows used for ZK sumcheck masking).
The ordered polynomials must be committed. To maintain zero-knowledge, the prover redistributes the random values from the 4 concatenated to the 5 ordered polynomials. As illustrated above, each ordered polynomial receives approximately an equal share of the randomness from the concatenated polynomials. The total number of random values in the concatenated polynomials:
$$M = 4 \cdot m \cdot I_{\textsf{size}}.$$
To distribute these $M$ random values to 5 ordered polynomials, each ordered polynomial receives $\left\lfloor\frac{M}{5}\right\rfloor$ random values in its masking region. The remaining random values (if $M$ is not divisible by 5) are distributed one per ordered polynomial starting from the first. Further, since
$$ \underbrace{(m \cdot I_{\textsf{size}})}_{\textsf{size of masking region}} > \underbrace{\left\lfloor \left(\frac{4}{5} \cdot m \cdot I_{\textsf{size}}\right) \right\rfloor}_{\textsf{size of randomness in ordered polys}}, $$
the remaining positions in the ordered masking region are filled with zeros.
Note: The same random values appear in both concatenated and ordered polynomials (just at different positions within the masking region). This is why the $\beta \cdot L_{\text{mask}}$ term is needed in the permutation relation - see RELATIONS.md for details.
Some positions in the ordered masking region contain random values, others contain zeros. The ordered_extra_range_constraints_numerator compensates for these zeros in the permutation check.
Several polynomials are precomputed and independent of the witness.
Define row-specific selectors:
$$ \begin{aligned} \texttt{lagrange_first}[i] &= \begin{cases} 1 & i = 0 \ 0 & \text{otherwise} \end{cases} \ \texttt{lagrange_last}[i] &= \begin{cases} 1 & i = 2^{17} - 1 \ 0 & \text{otherwise} \end{cases} \ \texttt{lagrange_even}[i] &= \begin{cases} 1 & i \in [0, 2^{13}), \ i \text{ even} \ 0 & \text{otherwise} \end{cases} \ \texttt{lagrange_odd}[i] &= \begin{cases} 1 & i \in [0, 2^{13}), \ i \text{ odd} \ 0 & \text{otherwise} \end{cases} \end{aligned} $$
This polynomial contains the "step values" repeated to balance the permutation:
$$\texttt{ordered extra}[i \cdot 5 + j] = \text{sorted steps}[i] \quad \text{for } i \in [0, 5462), \ j \in [0, 5)$$
where $\text{sorted steps} = \lbrace 0, 3, 6, 9, \ldots, 16383\rbrace$.
This ensures the multisets balance:
Constraints for the translator VM are specified in RELATIONS.md.
1.9.8