# UltraHonk Verifier — Protocol steps

## 0 Preliminaries

### 0.1 Fields and Groups

Let $p = \mathtt{0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001}$ be prime, and let $\mathbb{F} = \mathbb{Z}/p\mathbb{Z}$ be the scalar field.

Let $q = \mathtt{0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47}$ be the order of the base field of the BN254 curve.

Let $\mathbb{G}_1, \mathbb{G}_2$ be groups of order $p$ and $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ an efficiently computable non-degenerate bilinear pairing. Fix generators $G_1 \in \mathbb{G}_1$ and $G_2 \in \mathbb{G}_2$.

### 0.2 Notation

For $a \in \mathbb{F}$, we write $[a]_1 = a \cdot G_1$ and $[a]_2 = a \cdot G_2$.

For a polynomial $f \in \mathbb{F}[X]$ (or multilinear $f \in \mathbb{F}[X_1, \ldots, X_k]$), write $[f]_1$ to denote its KZG commitment in $\mathbb{G}_1$. Furthermore, we write $f'$ to denote the shifted polynomial defined by $f'(X) := f(\omega X)$, where $\omega$ is the primitive $n$-th root of unity.

For a polynomial $f$ and a point $\mathbf{u}$, write $\bar{f}$ to denote the evaluation $f(\mathbf{u})$ when the evaluation point is clear from context.

### 0.3 Hash and Challenge Extraction

Let $H : \{0,1\}^* \to \mathbb{F}$ be a cryptographic hash function.

Given $c \in \mathbb{F}$, we define $\mathsf{split}(c) = (c_{\mathrm{lo}}, c_{\mathrm{hi}})$ where:
$$c_{\mathrm{lo}} = \tilde{c} \mod 2^{128}, \qquad c_{\mathrm{hi}} = \lfloor \tilde{c} / 2^{128} \rfloor$$
and $\tilde{c} \in [0, p)$ is the canonical integer representation of $c$.

When we write "extract $(a, b)$ from $c$", this means $(a, b) = \mathsf{split}(c)$.

When we write "extract $(a, \cdot)$ from $c$", this means $a = c_{\mathrm{lo}}$ and the high part is discarded.

### 0.4 Circuit Parameters

Let $d = 28$ be the maximum supported log-circuit-size.

Let $n$ be the actual circuit size (a power of 2), and let $\ell = \log_2 n$ denote its logarithm, where $\ell \le d$.

Let $k$ be the number of user-provided public inputs. Every proof additionally contains 16 pairing point objects that are treated as public inputs for the purpose of the protocol. The total public inputs size is $k_{\mathrm{total}} = k + 16$.

## 1 Polynomials
The protocol operates over 40 polynomials in multilinear form. These are:

**Precomputed polynomials (27):**

| Index | Polynomial | Description |
|-------|------------|-------------|
| 0 | $q_M$ | Multiplication selector |
| 1 | $q_C$ | Constant selector |
| 2 | $q_L$ | Left selector |
| 3 | $q_R$ | Right selector |
| 4 | $q_O$ | Output selector |
| 5 | $q_4$ | Fourth wire selector |
| 6 | $q_K$ | Lookup selector |
| 7 | $q_A$ | Arithmetic selector |
| 8 | $q_D$ | Delta range selector |
| 9 | $q_E$ | Elliptic curve selector |
| 10 | $q_X$ | Auxiliary selector |
| 11 | $q_{p,\text{ext}}$ | Poseidon2 external selector |
| 12 | $q_{p,\text{int}}$ | Poseidon2 internal selector |
| 13–16 | $\sigma_1, \sigma_2, \sigma_3, \sigma_4$ | Permutation polynomials |
| 17–20 | $\iota_1, \iota_2, \iota_3, \iota_4$ | Identity polynomials |
| 21–24 | $\tau_1, \tau_2, \tau_3, \tau_4$ | Table polynomials |
| 25 | $L_0$ | First Lagrange polynomial |
| 26 | $L_{n-1}$ | Last Lagrange polynomial |

**Witness polynomials (8):**

| Index | Polynomial | Description |
|-------|------------|-------------|
| 27 | $w_1$ | Left wire |
| 28 | $w_2$ | Right wire |
| 29 | $w_3$ | Output wire |
| 30 | $w_4$ | Fourth wire |
| 31 | $z$ | Permutation grand product |
| 32 | $h_{\mathrm{inv}}$ | Lookup inverses |
| 33 | $h_{\mathrm{cnt}}$ | Lookup read counts |
| 34 | $h_{\mathrm{tag}}$ | Lookup read tags |

**Shifted polynomials (5):**

| Index | Polynomial | Description |
|-------|------------|-------------|
| 35 | $w'_1$ | Left wire, shifted |
| 36 | $w'_2$ | Right wire, shifted |
| 37 | $w'_3$ | Output wire, shifted |
| 38 | $w'_4$ | Fourth wire, shifted |
| 39 | $z'$ | Grand product, shifted |

## 2 Verification Key

The verification key $vk$ consists of **commitments** in $\mathbb{G}_1$ to the following preprocessed polynomials:

**Selector polynomials:**
$$[q_M]_1,\, [q_C]_1,\, [q_L]_1,\, [q_R]_1,\, [q_O]_1,\, [q_4]_1$$
$$[q_K]_1,\, [q_A]_1,\, [q_D]_1,\, [q_E]_1,\, [q_X]_1,\, [q_{p,\text{ext}}]_1,\, [q_{p,\text{int}}]_1$$

**Permutation polynomials:**
$$[\sigma_1]_1,\, [\sigma_2]_1,\, [\sigma_3]_1,\, [\sigma_4]_1$$

**Identity polynomials:**
$$[\iota_1]_1,\, [\iota_2]_1,\, [\iota_3]_1,\, [\iota_4]_1$$

**Table polynomials:**
$$[\tau_1]_1,\, [\tau_2]_1,\, [\tau_3]_1,\, [\tau_4]_1$$

**Lagrange polynomials:**
$$[L_0]_1,\, [L_{n-1}]_1$$

**Structured reference string (SRS):**

The verifier uses two fixed $\mathbb{G}_2$ elements from the SRS:
- $[1]_2$: the generator $G_2$
- $[\chi]_2$: the element corresponding to the SRS secret

These are hardcoded constants in the verifier contract.

## 3 Proof

The proof $\pi$ consists of:

**Wire commitments:** $[w_1]_1,\, [w_2]_1,\, [w_3]_1,\, [w_4]_1$

**Grand product commitment:** $[z]_1$

**Lookup commitments:** $[h_{\mathrm{cnt}}]_1,\, [h_{\mathrm{tag}}]_1, \,
[h_{\mathrm{inv}}]_1$

**Sumcheck univariates:** $S^{(i)} = (S^{(i)}_0, \ldots, S^{(i)}_7) \in \mathbb{F}^8$ for $i = 0, \ldots, d-1$, representing evaluations of a degree-7 univariate polynomial $S^{(i)}(X)$ at the points $X = 0, 1, \ldots, 7$.

**Claimed evaluations:** $\mathbf{v} = (v_0, \ldots, v_{39}) \in \mathbb{F}^{40}$

The evaluations correspond to polynomials in the following order:

| Index | Symbol | Polynomial |
|-------|--------|------------|
| 0 | $\bar{q}_M$ | Multiplication selector |
| 1 | $\bar{q}_C$ | Constant selector |
| 2 | $\bar{q}_L$ | Left selector |
| 3 | $\bar{q}_R$ | Right selector |
| 4 | $\bar{q}_O$ | Output selector |
| 5 | $\bar{q}_4$ | Fourth wire selector |
| 6 | $\bar{q}_K$ | Lookup selector |
| 7 | $\bar{q}_A$ | Arithmetic selector |
| 8 | $\bar{q}_D$ | Delta range selector |
| 9 | $\bar{q}_E$ | Elliptic curve selector |
| 10 | $\bar{q}_X$ | Auxiliary selector |
| 11 | $\bar{q}_{p,\text{ext}}$ | Poseidon2 external selector |
| 12 | $\bar{q}_{p,\text{int}}$ | Poseidon2 internal selector |
| 13–16 | $\bar{\sigma}_1, \ldots, \bar{\sigma}_4$ | Permutation polynomials |
| 17–20 | $\bar{\iota}_1, \ldots, \bar{\iota}_4$ | Identity polynomials |
| 21–24 | $\bar{\tau}_1, \ldots, \bar{\tau}_4$ | Table polynomials |
| 25 | $\bar{L}_0$ | First Lagrange polynomial |
| 26 | $\bar{L}_{n-1}$ | Last Lagrange polynomial |
| 27–30 | $\bar{w}_1, \ldots, \bar{w}_4$ | Wire polynomials |
| 31 | $\bar{z}$ | Permutation grand product |
| 32 | $\bar{h}_{\mathrm{inv}}$ | Lookup inverses |
| 33 | $\bar{h}_{\mathrm{cnt}}$ | Lookup read counts |
| 34 | $\bar{h}_{\mathrm{tag}}$ | Lookup read tags |
| 35–38 | $\bar{w}'_1, \ldots, \bar{w}'_4$ | Shifted wire polynomials |
| 39 | $\bar{z}'$ | Shifted grand product |

**Gemini commitments:** $[A_1]_1, \ldots, [A_{d-1}]_1$

**Gemini evaluations:** $\bar{a}_0, \ldots, \bar{a}_{d-1} \in \mathbb{F}$

**Opening quotients:** $[Q]_1,\, [W]_1$

**Pairing point objects:** $(p_1, \ldots, p_{16}) \in \mathbb{F}^{16}$

## 4 Verifier

**Input:** Public values $(x_1, \ldots, x_k) \in \mathbb{F}^k$, verification key $vk$ and the proof $\pi$.

### 4.1 Challenge Derivation

Here we assume that the verifier derives all challenges non-interactively via Fiat-Shamir. The challenges are computed sequentially, with each new hash incorporating the previous challenge and additional proof elements.

#### Eta challenges

Compute:
$$c_0 = H(n, k_{\text{total}}, 1, x_1, \ldots, x_k, p_1, \ldots, p_{16}, [w_1]_1, [w_2]_1, [w_3]_1)$$

> The third input is fixed to 1, called the public input offset. There is an open Github issue to clean this up [here](https://github.com/AztecProtocol/barretenberg/issues/1281).

Extract $(\eta, \eta_2)$ from $c_0$. Compute $c_1 = H(c_0)$ and extract $(\eta_3, \cdot)$ from $c_1$.

#### Beta and Gamma challenges

Compute:
$$c_2 = H(c_1, [h_{\mathrm{cnt}}]_1, [h_{\mathrm{tag}}]_1, [w_4]_1)$$

Extract $(\beta, \gamma)$ from $c_2$.

#### Alpha challenges

Compute the sequence:
$$c_{3,0} = H(c_2, [h_{\mathrm{inv}}]_1, [z]_1), \quad c_{3,i} = H(c_{3,i-1}) \text{ for } i = 1, \ldots, 12$$

Extract $(\alpha_{2i}, \alpha_{2i+1})$ from $c_{3,i}$ for each $i = 0, \ldots, 11$, to obtain $\alpha_0, \ldots, \alpha_{23}$. Then extract $(\alpha_{24}, \cdot)$ from $c_{3,12}$ to have a total of 25 alpha challenges.

#### Gate challenges

Compute the sequence:
$$c_{4,0} = H(c_{3,12}), \quad c_{4,i} = H(c_{4,i-1}) \text{ for } i = 1, \ldots, d-1$$

Extract $(g_i, \cdot)$ from $c_{4,i}$, obtaining gate challenges $g_0, \ldots, g_{d-1}$.

#### Sumcheck challenges

For $i = 0, \ldots, d-1$, compute:
$$c_{5,i} = H(\hat{c}, S^{(i)}_0, \ldots, S^{(i)}_7) \quad \text{where } \hat{c} = \begin{cases} c_{4,d-1} & i = 0 \\ c_{5,i-1} & i > 0 \end{cases}$$

Extract $(u_i, \cdot)$ from $c_{5,i}$ to obtain sumcheck challenges $u_0,..,u_{d-1}$.

#### Rho challenge

Compute $c_6 = H(c_{5,d-1}, v_0, \ldots, v_{39})$ and extract $(\rho, \cdot)$.

#### Gemini challenge

Compute $c_7 = H(c_6, [A_1]_1, \ldots, [A_{d-1}]_1)$ and extract $(r, \cdot)$.

#### Shplonk Nu challenge

Compute $c_8 = H(c_7, \bar{a}_0, \ldots, \bar{a}_{d-1})$ and extract $(\nu, \cdot)$.

#### Shplonk Z challenge

Compute $c_9 = H(c_8, [Q]_1)$ and extract $(\zeta, \cdot)$.

### 4.2 Public Input Contribution

Recall that $(x_1, \ldots, x_k)$ are the public inputs, $(p_1,..,p_{16})$ the pairing point objects and $n$ the circuit size.

For $i = 1, \ldots, k$:
$$\delta_i^{(\text{num})} = x_i + \gamma + \beta(n + i), \qquad \delta_i^{(\text{den})} = x_i + \gamma - \beta (i+1)$$

> Note: these formula's are only correct under the condition that public input offset is fixed to 1.

For $j = k, \ldots, k+16$, continuing the deltas:
$$\delta_j^{(\text{num})} = p_j + \gamma + \beta(n + j), \qquad \delta_j^{(\text{den})} = p_j + \gamma - \beta(j + 1)$$

Compute the public input delta:
$$\delta = \prod_{m=1}^{k_{\text{total}}} \frac{\delta_m^{(\text{num})}}{\delta_m^{(\text{den})}}$$

## 4.3 Sumcheck Protocol

Recall that we have sumcheck univariates $S^{(i)} = (S^{(i)}_0, \ldots, S^{(i)}_7) \in \mathbb{F}^8$ for $i = 0, \ldots, d-1$, sumcheck challenges $(u_0, \ldots, u_{d-1})$ and gate challenges $(g_0, \ldots, g_{d-1})$.

**Initialize:** $\theta_0 = 0, \psi_0 = 1$.

**For** $i = 0, \ldots, d-1$:

1. **Check sum:** Verify $S^{(i)}_0 + S^{(i)}_1 = \theta_i$

2. **Compute next target:** Compute via barycentric interpolation:
$$\theta_{i+1} = S^{(i)}(u_i) = \left(\prod_{j=0}^{7}(u_i - j)\right) \sum_{j=0}^{7} \frac{S^{(i)}_j}{D_j (u_i - j)}$$

where the Lagrange denominators are:
$$D_j = \prod_{k \neq j}(j - k) = \{-5040, 720, -240, 144, -144, 240, -720, 5040\}$$ because the evaluation points are $\{0,1,2,3,4,5,6,7\}$.

3. **Update pow polynomial evaluation:**
$$\psi_{i+1} = \psi_i (1 + u_i(g_i - 1))$$

Set $\psi = \psi_d$.

### 4.4 Sumcheck Protocol — Relations

See section $2$, $3$ and $4.1$ for details on the variables used here.

#### 4.4.1 Arithmetic relation

$$R_0 = \bar{q}_A \psi \left( \frac{(3 - \bar{q}_A) \bar{q}_M \bar{w}_1 \bar{w}_2}{2} + \bar{q}_L \bar{w}_1 + \bar{q}_R \bar{w}_2 + \bar{q}_O \bar{w}_3 + \bar{q}_4 \bar{w}_4 + \bar{q}_C + (\bar{q}_A - 1)\bar{w}'_4 \right)$$

$$R_1 =\bar{q}_A \psi (\bar{w}_1 + \bar{w}_4 - \bar{w}'_1 + \bar{q}_M)(\bar{q}_A - 1)(\bar{q}_A - 2)$$

#### 4.4.2 Permutation

$$R_2 = \psi \left( (\bar{z} + \bar{L}_0)\prod_{j=1}^{4}(\bar{w}_j + \bar{\iota}_j \beta + \gamma) - (\bar{z}' + \bar{L}_{n-1} \delta) \prod_{j=1}^{4}(\bar{w}_j + \bar{\sigma}_j \beta + \gamma) \right)$$

$$R_3 = \bar{L}_{n-1} \bar{z}' \psi$$

#### 4.4.3 Lookup

Define:
$$T = \bar{\tau}_1 + \gamma + \bar{\tau}_2\eta + \bar{\tau}_3\eta_2 + \bar{\tau}_4\eta_3$$

$$W = \bar{w}_1 + \gamma + \bar{q}_R \bar{w}'_1 + (\bar{w}_2 + \bar{q}_M \bar{w}'_2)\eta + (\bar{w}_3 + \bar{q}_C \bar{w}'_3)\eta_2 + \bar{q}_O \eta_3$$

Then,
$$R_4 = \psi \left( \bar{h}_{\mathrm{inv}} W T - (\bar{h}_{\mathrm{tag}} + \bar{q}_K - \bar{h}_{\mathrm{tag}} \bar{q}_K) \right)$$

$$R_5 = \bar{q}_K \bar{h}_{\mathrm{inv}} T - \bar{h}_{\mathrm{cnt}} \bar{h}_{\mathrm{inv}} W$$

#### 4.4.4 Delta Range

Define $\Delta_1 = \bar{w}_2 - \bar{w}_1$, $\Delta_2 = \bar{w}_3 - \bar{w}_2$, $\Delta_3 = \bar{w}_4 - \bar{w}_3$, $\Delta_4 = \bar{w}'_1 - \bar{w}_4$.

For $j=1,\dots,4$:
$$R_{5+j} = \bar{q}_D \psi \Delta_j (\Delta_j - 1)(\Delta_j - 2)(\Delta_j - 3)$$

#### 4.4.5 Elliptic Curve

Define:
$$X_{\mathrm{add}} = (\bar{w}'_2 + \bar{w}'_1 + \bar{w}_2)(\bar{w}'_1 - \bar{w}_2)^2 - \bar{w}'^2_4 - \bar{w}_3^2 + 2 \bar{w}_3 \bar{w}'_4 \bar{q}_L$$

$$Y_{\mathrm{add}} = (\bar{w}_3 + \bar{w}'_3)(\bar{w}'_1 - \bar{w}_2) + (\bar{w}'_2 - \bar{w}_2)(\bar{w}'_4 \bar{q}_L - \bar{w}_3)$$

$$X_{\mathrm{dbl}} = 4\bar{w}_3^2(\bar{w}'_2 + 2\bar{w}_2) - 9\bar{w}_2 (\bar{w}_3^2 + 17)$$

$$Y_{\mathrm{dbl}} = 3\bar{w}_2^2(\bar{w}_2 - \bar{w}'_2) - 2\bar{w}_3(\bar{w}_3 + \bar{w}'_3)$$

Then,
$$R_{10} = \bar{q}_E \psi \left( (1 - \bar{q}_M) X_{\mathrm{add}} + \bar{q}_M X_{\mathrm{dbl}} \right)$$

$$R_{11} = \bar{q}_E \psi \left( (1 - \bar{q}_M) Y_{\mathrm{add}} + \bar{q}_M Y_{\mathrm{dbl}} \right)$$

#### 4.4.6 Auxiliary

**Constants:** $B = 2^{68}$, $b = 2^{14}$

**Non-native field:**
$$c_p = \bar{w}_1 \bar{w}'_2 + \bar{w}'_1 \bar{w}_2, \quad N_1 = (B c_p + \bar{w}'_1 \bar{w}'_2 - \bar{w}_3 - \bar{w}_4) \bar{q}_O$$
$$N_2 = ((\bar{w}_1 \bar{w}_4 + \bar{w}_2 \bar{w}_3 - \bar{w}'_3)B - \bar{w}'_4 + c_p) \bar{q}_4, \quad N_3 = (B c_p + \bar{w}'_1 \bar{w}'_2 + \bar{w}_4 - \bar{w}'_3 - \bar{w}'_4) \bar{q}_M$$
$$\mathcal{N} = (N_1 + N_2 + N_3) \bar{q}_R$$

**Limb accumulation:**
$$L_1 = (((({\bar{w}'_2} b + \bar{w}'_1)b + \bar{w}_3)b + \bar{w}_2)b + \bar{w}_1 - \bar{w}_4) \bar{q}_4$$
$$L_2 = ((((\bar{w}'_3 b + \bar{w}'_2)b + \bar{w}'_1)b + \bar{w}_4)b + \bar{w}_3 - \bar{w}'_4) \bar{q}_M, \quad \mathcal{L} = (L_1 + L_2) \bar{q}_O$$

**Memory:**
$$M_p = \bar{q}_C + \bar{w}_1 \eta + \bar{w}_2 \eta_2 + \bar{w}_3 \eta_3, \quad M = M_p - \bar{w}_4$$
$$\Delta_I = \bar{w}'_1 - \bar{w}_1, \quad \Delta_R = \bar{w}'_4 - \bar{w}_4 $$
$$\mathcal{M}_{\mathrm{mono}} = \Delta_I^2 - \Delta_I, \quad \mathcal{M}_{\mathrm{adj}} = (1 - \Delta_I) \Delta_R$$

**ROM:**
$$\mathcal{R}_{\mathrm{ROM}} = M \bar{q}_L \bar{q}_R$$

**RAM:**
$$a = \bar{w}_4 - M_p, \quad a' = \bar{w}'_4 - (\bar{w}'_1 \eta + \bar{w}'_2 \eta_2 + \bar{w}'_3 \eta_3)$$
$$\Delta_T = \bar{w}'_2 - \bar{w}_2, \quad \Delta_V = \bar{w}'_3 - \bar{w}_3, \quad \mathcal{A} = (a^2 - a) \bar{q}_A$$
$$\mathcal{M}_{\mathrm{read}} = \Delta_V(1 - \Delta_I)(1 - a'), \quad \mathcal{M}_{\mathrm{bool}} = a'^2 - a'$$
$$\mathcal{T} = (1 - \Delta_I)\Delta_T - \bar{w}_3$$

**Combined:**

$$\mathcal{X} = \mathcal{R}_{\mathrm{ROM}} + \mathcal{T} \bar{q}_4 \bar{q}_L + M \bar{q}_M \bar{q}_L + \mathcal{A}, \quad \mathcal{Y} = \mathcal{X} + \mathcal{N} + \mathcal{L}, \quad \Phi = \bar{q}_X \psi$$
$$R_{12} = \mathcal{Y} \Phi, \quad R_{13} = \mathcal{M}_{\mathrm{adj}} \bar{q}_L \bar{q}_R \Phi, \quad R_{14} = \mathcal{M}_{\mathrm{mono}} \bar{q}_L \bar{q}_R \Phi$$
$$R_{15} = \mathcal{M}_{\mathrm{read}} \bar{q}_A \Phi, \quad R_{16} = \mathcal{M}_{\mathrm{mono}} \bar{q}_A \Phi, \quad R_{17} = \mathcal{M}_{\mathrm{bool}} \bar{q}_A \Phi$$

#### 4.4.7 Poseidon2 External

Define:
$$s_1 = \bar{w}_1 + \bar{q}_L, \quad s_2 = \bar{w}_2 + \bar{q}_R, \quad s_3 = \bar{w}_3 + \bar{q}_O, \quad s_4 = \bar{w}_4 + \bar{q}_4$$
$$y_j = s_j^5 \quad \text{ for } j = 1,\ldots,4, \quad \Omega_{p,\text{ext}} = \bar{q}_{p,\text{ext}} \psi$$
$$t_0 = y_1 + y_2, \quad t_1 = y_3 + y_4, \quad t_2 = 2y_2 + t_1, \quad t_3 = 2y_4 + t_0$$
$$v_1 = t_3 + v_2, \quad v_2 = 4t_0 + t_2, \quad v_3 = t_2 + v_4, \quad v_4 = 4t_1 + t_3$$
Then we have the following evaluations:
$$R_{18} = \Omega_{p,\text{ext}} (v_1 - \bar{w}'_1), \quad R_{19} = \Omega_{p,\text{ext}} (v_2 - \bar{w}'_2)$$
$$R_{20} = \Omega_{p,\text{ext}} (v_3 - \bar{w}'_3), \quad R_{21} = \Omega_{p,\text{ext}} (v_4 - \bar{w}'_4)$$

#### 4.4.8 Poseidon2 Internal

We have the following constants:
$$\begin{aligned}
d_1 &= \mathtt{0x10dc6e9c006ea38b04b1e03b4bd9490c0d03f98929ca1d7fb56821fd19d3b6e7} \\
d_2 &= \mathtt{0x0c28145b6a44df3e0149b3d0a30b3bb599df9756d4dd9b84a86b38cfb45a740b} \\
d_3 &= \mathtt{0x00544b8338791518b2c7645a50392798b21f75bb60e3596170067d00141cac15} \\
d_4 &= \mathtt{0x222c01175718386f2e2e82eb122789e352e105a3b8fa852613bc534433ee428b}
\end{aligned}$$

Define:
$$y = (\bar{w}_1 + \bar{q}_L)^5, \quad \Sigma = y + \bar{w}_2 + \bar{w}_3 + \bar{w}_4, \quad \Omega_{p,\text{int}} = \bar{q}_{p,\text{int}} \psi$$
$$m_1 = y d_1 + \Sigma, \quad m_2 = \bar{w}_2 d_2 + \Sigma, \quad m_3 = \bar{w}_3 d_3 + \Sigma, \quad m_4 = \bar{w}_4 d_4 + \Sigma$$
Then we have the following evaluations:
$$R_{22} = \Omega_{p,\text{int}} (m_1 - \bar{w}'_1), \quad R_{23} = \Omega_{p,\text{int}} (m_2 - \bar{w}'_2)$$
$$R_{24} = \Omega_{p,\text{int}} (m_3 - \bar{w}'_3), \quad R_{25} = \Omega_{p,\text{int}} (m_4 - \bar{w}'_4)$$

#### 4.4.9 Batched Relation Sum

Using challenges $\alpha_0, \ldots, \alpha_{24}$ from Round 3:
$$\bar{F} = R_0 + \sum_{j=1}^{25} \alpha_{j-1} R_j$$

Verify that $\bar{F} = \psi$.

### 4.5 Verify Shplemini

Recall that from the proof we have claimed evaluations $\mathbf{v} = (v_0, \ldots, v_{39}) \in \mathbb{F}^{40}$ and gemini evaluations $\bar{a}_0, \ldots, \bar{a}_{d-1} \in \mathbb{F}$, and that we additionally have the generated challenges $r$, $\rho$, $\zeta$ and $\nu$.

Compute $r_j = r^{2^j}$ for $j = 0, \ldots, d-1$.

Compute the batched evaluation:
$$\bar{e} = \sum_{i=0}^{39} \rho^i v_i$$

For $i = \ell-1, \ell-2, \ldots, 0$:
$$G_i = \frac{2 r_i e - \bar{a}_i (r_i(1-u_i) - u_i)}{r_i(1-u_i) + u_i} \quad \text{where } e = \begin{cases} \bar{e} & i = \ell-1 \\ G_{i+1} & \text{otherwise} \end{cases}$$

For $j = 0, 1, \ldots, \ell-1$ let $D^+_j = (\zeta - r_j)^{-1}$ and $D^-_j = (\zeta + r_j)^{-1}$.

For $j = 1, \ldots, \ell-1$:
$$\xi_j = - \nu^{2j+1} D^-_j - \nu^{2j} D^+_j$$
Define:
$$\lambda = D^+_0 + \nu D^-_0, \qquad \mu = r^{-1}(D^+_0 - \nu D^-_0)$$
$$\kappa = G_0 D^+_0 + \bar{a}_0 \nu D^-_0 + \sum_{j=1}^{\ell-1}\bigl(\nu^{2j} G_j D^+_j + \nu^{2j+1} \bar{a}_j D^-_j \bigr)$$

Finally, compute:
$$[D]_1 = [Q]_1 - \lambda \sum_{i=0}^{34} \rho^i [C_i]_1 - \mu \sum_{i=0}^{4} \rho^{35+i} [C'_i]_1 + \sum_{j=1}^{\ell-1} \xi_j [A_j]_1 + \kappa [1]_1 + \zeta [W]_1$$
where $[C_0]_1, \ldots, [C_{34}]_1$ are the 35 unshifted polynomial commitments in order:
$$[C_0]_1, \ldots, [C_{12}]_1 = [q_M]_1, [q_C]_1, [q_L]_1, [q_R]_1, [q_O]_1, [q_4]_1, [q_K]_1, [q_A]_1, [q_D]_1, [q_E]_1, [q_X]_1, [q_{p,\text{ext}}]_1, [q_{p,\text{int}}]_1$$
$$[C_{13}]_1, \ldots, [C_{16}]_1 = [\sigma_1]_1, \ldots, [\sigma_4]_1$$
$$[C_{17}]_1, \ldots, [C_{20}]_1 = [\iota_1]_1, \ldots, [\iota_4]_1$$
$$[C_{21}]_1, \ldots, [C_{24}]_1 = [\tau_1]_1, \ldots, [\tau_4]_1$$
$$[C_{25}]_1, [C_{26}]_1 = [L_0]_1, [L_{n-1}]_1$$
$$[C_{27}]_1, \ldots, [C_{30}]_1 = [w_1]_1, \ldots, [w_4]_1$$
$$[C_{31}]_1, \ldots, [C_{34}]_1 = [z]_1, [h_{\mathrm{inv}}]_1, [h_{\mathrm{cnt}}]_1, [h_{\mathrm{tag}}]_1$$
and $[C'_0]_1, \ldots, [C'_4]_1 = [w_1]_1, [w_2]_1, [w_3]_1, [w_4]_1, [z]_1$ for the shifted polynomials.

### 4.6 Pairing Check

**Verify:**
$$e\bigl([D]_1,\; [1]_2\bigr) = e\bigl([W]_1,\; [\chi]_2\bigr)$$

### 4.7 Verification result

The verifier accepts the proof if and only if:
1. All sumcheck rounds pass (section 4.3, step 1 of loop)
2. The batched relation sum equals the final round target (section 4.4.9)
3. The pairing check holds (section 4.6)

## Appendix A: Variable Mapping

### A.1 Constants

| Writeup | Solidity | Sway |
| ------- | ----------------------------- | ----------------------------- |
| $p$ | `MODULUS`, `P` | `MODULUS` |
| $q$ | `Q` | `Q` |
| $d$ | `CONST_PROOF_SIZE_LOG_N` | `CONST_PROOF_SIZE_LOG_N` |
| $B$ | `LIMB_SIZE` | `LIMB_SIZE` |
| $b$ | `SUBLIMB_SHIFT` | `SUBLIMB_SHIFT` |
| $d_1$ | `INTERNAL_MATRIX_DIAGONAL[0]` | `INTERNAL_MATRIX_DIAGONAL[0]` |
| $d_2$ | `INTERNAL_MATRIX_DIAGONAL[1]` | `INTERNAL_MATRIX_DIAGONAL[1]` |
| $d_3$ | `INTERNAL_MATRIX_DIAGONAL[2]` | `INTERNAL_MATRIX_DIAGONAL[2]` |
| $d_4$ | `INTERNAL_MATRIX_DIAGONAL[3]` | `INTERNAL_MATRIX_DIAGONAL[3]` |

### A.2 Verification Key

| Writeup | Solidity | Sway |
|---------|----------|------|
| $n$ | `circuitSize` | `circuit_size` |
| $\ell$ | `logCircuitSize` | `log_circuit_size` |
| $k_{\mathrm{total}}$ | `publicInputsSize` | `NUMBER_OF_PUBLIC_INPUTS` |
| $[q_M]_1$ | `qm` | `qm` |
| $[q_C]_1$ | `qc` | `qc` |
| $[q_L]_1$ | `ql` | `ql` |
| $[q_R]_1$ | `qr` | `qr` |
| $[q_O]_1$ | `qo` | `qo` |
| $[q_4]_1$ | `q4` | `q4` |
| $[q_K]_1$ | `qLookup` | `q_lookup` |
| $[q_A]_1$ | `qArith` | `q_arith` |
| $[q_D]_1$ | `qDeltaRange` | `q_delta_range` |
| $[q_E]_1$ | `qElliptic` | `q_elliptic` |
| $[q_X]_1$ | `qAux` | `q_aux` |
| $[q_{p,\text{ext}}]_1$ | `qPoseidon2External` | `q_poseidon2_external` |
| $[q_{p,\text{int}}]_1$ | `qPoseidon2Internal` | `q_poseidon2_internal` |
| $[\sigma_1]_1$ | `s1` | `s1` |
| $[\sigma_2]_1$ | `s2` | `s2` |
| $[\sigma_3]_1$ | `s3` | `s3` |
| $[\sigma_4]_1$ | `s4` | `s4` |
| $[\iota_1]_1$ | `id1` | `id1` |
| $[\iota_2]_1$ | `id2` | `id2` |
| $[\iota_3]_1$ | `id3` | `id3` |
| $[\iota_4]_1$ | `id4` | `id4` |
| $[\tau_1]_1$ | `t1` | `t1` |
| $[\tau_2]_1$ | `t2` | `t2` |
| $[\tau_3]_1$ | `t3` | `t3` |
| $[\tau_4]_1$ | `t4` | `t4` |
| $[L_0]_1$ | `lagrangeFirst` | `lagrange_first` |
| $[L_{n-1}]_1$ | `lagrangeLast` | `lagrange_last` |

### A.3 Proof

| Writeup | Solidity | Sway |
|---------|----------|------|
| $[w_1]_1$ | `w1` | `w1` |
| $[w_2]_1$ | `w2` | `w2` |
| $[w_3]_1$ | `w3` | `w3` |
| $[w_4]_1$ | `w4` | `w4` |
| $[z]_1$ | `zPerm` | `z_perm` |
| $[h_{\mathrm{inv}}]_1$ | `lookupInverses` | `lookup_inverses` |
| $[h_{\mathrm{cnt}}]_1$ | `lookupReadCounts` | `lookup_read_counts` |
| $[h_{\mathrm{tag}}]_1$ | `lookupReadTags` | `lookup_read_tags` |
| $S^{(i)}_j$ | `sumcheckUnivariates[i][j]` | `sumcheck_univariates[i][j]` |
| $v_i$ | `sumcheckEvaluations[i]` | `sumcheck_evaluations[i]` |
| $[A_i]_1$ | `geminiFoldComms[i]` | `gemini_fold_comms[i]` |
| $\bar{a}_i$ | `geminiAEvaluations[i]` | `gemini_a_evaluations[i]` |
| $[Q]_1$ | `shplonkQ` | `shplonk_q` |
| $[W]_1$ | `kzgQuotient` | `kzg_quotient` |
| $p_i$ | `pairingPointObject[i]` | `pairing_point_object[i]` |

### A.4 Transcript

| Writeup | Solidity | Sway |
|---------|----------|------|
| $\eta$ | `eta` | `eta` |
| $\eta_2$ | `etaTwo` | `eta_two` |
| $\eta_3$ | `etaThree` | `eta_three` |
| $\beta$ | `beta` | `beta` |
| $\gamma$ | `gamma` | `gamma` |
| $\delta$ | `publicInputsDelta` | `public_inputs_delta` |
| $\alpha_i$ | `alphas[i]` | `alphas[i]` |
| $g_i$ | `gateChallenges[i]` | `gate_challenges[i]` |
| $u_i$ | `sumCheckUChallenges[i]` | `sumcheck_u_challenges[i]` |
| $\rho$ | `rho` | `rho` |
| $r$ | `geminiR` | `gemini_r` |
| $\nu$ | `shplonkNu` | `shplonk_nu` |
| $\zeta$ | `shplonkZ` | `shplonk_z` |

### A.5 Wire Indices

| Writeup | Solidity | Sway | Index |
|---------|----------|------|-------|
| $\bar{q}_M$ | `Q_M` | `WIRE_Q_M` | 0 |
| $\bar{q}_C$ | `Q_C` | `WIRE_Q_C` | 1 |
| $\bar{q}_L$ | `Q_L` | `WIRE_Q_L` | 2 |
| $\bar{q}_R$ | `Q_R` | `WIRE_Q_R` | 3 |
| $\bar{q}_O$ | `Q_O` | `WIRE_Q_O` | 4 |
| $\bar{q}_4$ | `Q_4` | `WIRE_Q_4` | 5 |
| $\bar{q}_K$ | `Q_LOOKUP` | `WIRE_Q_LOOKUP` | 6 |
| $\bar{q}_A$ | `Q_ARITH` | `WIRE_Q_ARITH` | 7 |
| $\bar{q}_D$ | `Q_RANGE` | `WIRE_Q_RANGE` | 8 |
| $\bar{q}_E$ | `Q_ELLIPTIC` | `WIRE_Q_ELLIPTIC` | 9 |
| $\bar{q}_X$ | `Q_AUX` | `WIRE_Q_AUX` | 10 |
| $\bar{q}_{p,\text{ext}}$ | `Q_POSEIDON2_EXTERNAL` | `WIRE_Q_POSEIDON2_EXTERNAL` | 11 |
| $\bar{q}_{p,\text{int}}$ | `Q_POSEIDON2_INTERNAL` | `WIRE_Q_POSEIDON2_INTERNAL` | 12 |
| $\bar{\sigma}_1$ | `SIGMA_1` | `WIRE_SIGMA_1` | 13 |
| $\bar{\sigma}_2$ | `SIGMA_2` | `WIRE_SIGMA_2` | 14 |
| $\bar{\sigma}_3$ | `SIGMA_3` | `WIRE_SIGMA_3` | 15 |
| $\bar{\sigma}_4$ | `SIGMA_4` | `WIRE_SIGMA_4` | 16 |
| $\bar{\iota}_1$ | `ID_1` | `WIRE_ID_1` | 17 |
| $\bar{\iota}_2$ | `ID_2` | `WIRE_ID_2` | 18 |
| $\bar{\iota}_3$ | `ID_3` | `WIRE_ID_3` | 19 |
| $\bar{\iota}_4$ | `ID_4` | `WIRE_ID_4` | 20 |
| $\bar{\tau}_1$ | `TABLE_1` | `WIRE_TABLE_1` | 21 |
| $\bar{\tau}_2$ | `TABLE_2` | `WIRE_TABLE_2` | 22 |
| $\bar{\tau}_3$ | `TABLE_3` | `WIRE_TABLE_3` | 23 |
| $\bar{\tau}_4$ | `TABLE_4` | `WIRE_TABLE_4` | 24 |
| $\bar{L}_0$ | `LAGRANGE_FIRST` | `WIRE_LAGRANGE_FIRST` | 25 |
| $\bar{L}_{n-1}$ | `LAGRANGE_LAST` | `WIRE_LAGRANGE_LAST` | 26 |
| $\bar{w}_1$ | `W_L` | `WIRE_W_L` | 27 |
| $\bar{w}_2$ | `W_R` | `WIRE_W_R` | 28 |
| $\bar{w}_3$ | `W_O` | `WIRE_W_O` | 29 |
| $\bar{w}_4$ | `W_4` | `WIRE_W_4` | 30 |
| $\bar{z}$ | `Z_PERM` | `WIRE_Z_PERM` | 31 |
| $\bar{h}_{\mathrm{inv}}$ | `LOOKUP_INVERSES` | `WIRE_LOOKUP_INVERSES` | 32 |
| $\bar{h}_{\mathrm{cnt}}$ | `LOOKUP_READ_COUNTS` | `WIRE_LOOKUP_READ_COUNTS` | 33 |
| $\bar{h}_{\mathrm{tag}}$ | `LOOKUP_READ_TAGS` | `WIRE_LOOKUP_READ_TAGS` | 34 |
| $\bar{w}'_1$ | `W_L_SHIFT` | `WIRE_W_L_SHIFT` | 35 |
| $\bar{w}'_2$ | `W_R_SHIFT` | `WIRE_W_R_SHIFT` | 36 |
| $\bar{w}'_3$ | `W_O_SHIFT` | `WIRE_W_O_SHIFT` | 37 |
| $\bar{w}'_4$ | `W_4_SHIFT` | `WIRE_W_4_SHIFT` | 38 |
| $\bar{z}'$ | `Z_PERM_SHIFT` | `WIRE_Z_PERM_SHIFT` | 39 |