# Mercury

Le schéma d’engagement polynomial. La page fixe ce que les articles Mercury et BDFG20 laissent ouvert : le découpage des variables, l’engagement en tant qu’engagement KZG de la table d’évaluation, le protocole d’ouverture complet et son ordonnancement de transcription en seize étapes, la preuve de 704 octets et la vérification de couplage fusionnée à deux paires du vérificateur. Elle ajoute un lot de nombreuses colonnes en un même point, utilisé par chaque shard, et une forme différée de douze entrées d’accumulateur, que l’arbre de récursion replie au lieu d’effectuer le couplage. Les coûts et la sécurité concluent la page.

> Le texte normatif ci-dessous est tenu à jour en anglais, langue canonique de la spécification.

## Mercury

> The commitment every column is opened with: parameters, the opening protocol, the BDFG20 batch, k-column batching and the deferred accumulator recursion folds.
>
> Normative specification of Apogee VM v1.0.0 (source: docs/spec/mercury.md).

Every committed column is opened with Mercury (Eagen and Gabizon, ePrint 2025/385), finished by
the batched KZG opening of BDFG20 (Boneh, Drake, Fisch and Gabizon, ePrint 2020/081). This page
pins what the papers leave open, and adds a batch of `k` columns at one point and the deferred
form the recursion tree folds. `crates/pcs` is the prover, the curve side and the pairings;
`crates/pcs-verify`, `no_std`, is the verifier's field side, which the recursion guest links.

## 1. Parameters and the variable split

`n = 2^{2t}` evaluations with `1 ≤ t ≤ 27`, `b = 2^t = √n`, `s = 2t` variables; `u ∈ Fr^s` is the
opening point and `v` the claimed value. `pcs_verify::check_num_vars` refuses every other variable
count (`PcsError::UnsupportedNumVars`) and never pads, which is why every trace height is an even
power of two ([program.md](https://apogee.gweb3networks.com/docs/auditors/spec/program) §7). The ceiling, `pcs_verify::MAX_NUM_VARS = 54`, is where
`Fr`'s 2-adicity of 28 runs out of the `2b`-th roots of unity §3.1 needs, and it keeps `2^{|u|}` in
range for a `u` the verifier is handed.

The evaluation table is read as coefficients, and variable `m` is bit `m` of an index
([primitives.md](https://apogee.gweb3networks.com/docs/auditors/spec/primitives) §6). Write an index `i + j·b` with `i` the low `t` bits, as
Mercury §3.1 does; its evaluation is the coefficient of `X^{i+j·b}`. The point splits the same way:
**`u1`** is its first half, `u_0..u_{t−1}`, and pairs with `i`; **`u2`** is `u_t..u_{2t−1}` and
pairs with `j`.

```text
f(X) = Σ_{i<b} X^i·f_i(X^b),    f_i(X) = Σ_{j<b} f_{i+j·b}·X^j
f̂(u) = Σ_{i,j<b} eq(i, u1)·eq(j, u2)·f_{i+j·b}
```

`pcs::open` returns what `poly::MultilinearPoly::evaluate` gives at `u`, and a verifier handed the
two halves swapped rejects.

## 2. Commitment

`pcs::commit` returns `[f(x)]_1` for §1's `f(X)`, an MSM over the first `n` SRS powers: exactly the
KZG commitment of the evaluation table read as coefficients (`srs::kzg::kzg_commit`), with no second
scheme behind it. It refuses an SRS of fewer than `n` powers (`SrsTooSmall`). A column backed by
`U1`, `U8`, `U16` or `U32` (`poly::PolyBacking`) is widened to `u32` and committed through
`curve::msm::msm_small_u32`, never lifted to `Fr`; an `Fr` backing goes through `curve::msm::msm`.

The map from a table to its commitment is `Fr`-linear, which §5 uses, and a zero coefficient adds
nothing: a column extended by zero rows keeps its commitment. So the generic table's commitments
serve every height that holds the table ([lookup.md](https://apogee.gweb3networks.com/docs/auditors/spec/lookup) §9), and `pcs::commit_stack`
commits a recursion stack without building it.

## 3. The opening protocol

### 3.1 The polynomials

| | definition | coefficients | sent as |
| --- | --- | --- | --- |
| `h` | `Σ_i eq(i, u1)·f_i(X)`; its `X^j` coefficient is `f̂(u1, j)` | `b` | `h` |
| `q`, `g` | `f = (X^b − α)·q + g`, so `g = Σ_i f_i(α)·X^i` | `n − b`, `b` | `q`, `g` |
| `S` | the symmetrized witness below | `b − 1` | `s` |
| `D` | `X^{b−1}·g(1/X)`: `g` reversed | `b` | `d` |
| `H` | `(f − (z^b − α)·q − g_z)/(X − z)` | `n − 1` | `pi_z` |
| `W`, `W′` | §3.3 | `b − 1` each | `w`, `w_prime` |

`P_u(X) = Σ_{i<b} eq(i, u)·X^i = Π_{m<t}(u_m·X^{2^m} + 1 − u_m)`, so `⟨P_u, g⟩ = ĝ(u)` for `g` of
fewer than `b` coefficients (Mercury §4.2). The prover uses its coefficients, `poly::eq_table(u)`;
the verifier evaluates the product in `O(t)`.

The fold (Mercury §5) divides every `f_i` by `X − α`, `b` Horner divisions advanced together in
one pass over the rows, with no transform. Then `ĝ(u1) = h(α)` and `ĥ(u2) = f̂(u) = v`, and one
`S` proves both inner products (Mercury §4.1), the left side's constant coefficient being
`2·(⟨g, P_u1⟩ + γ·⟨h, P_u2⟩)`:

```text
g(X)·P_u1(1/X) + g(1/X)·P_u1(X) + γ·(h(X)·P_u2(1/X) + h(1/X)·P_u2(X))
    = 2·(h(α) + γ·v) + X·S(X) + S(1/X)/X
```

`S` is coefficients `b..2b−2` of `X^{b−1}` times the left side, computed with four forward
transforms of size `2b` and one inverse; no transform in an opening is larger
(`crates/pcs/src/fft.rs`, over `constants::FR_TWO_ADIC_ROOT_OF_UNITY`).

### 3.2 The transcript schedule

`pcs::open` and `pcs_verify::scalars` run this Fiat–Shamir schedule step for step. A point or a
list of points is one message ([transcript.md](https://apogee.gweb3networks.com/docs/auditors/spec/transcript) §4).

| # | | tag | message |
| --- | --- | --- | --- |
| 1 | absorb | `MERCURY_INSTANCE` | `n` |
| 2 | absorb | `COMMITMENT` | `cm`, as passed: `open` never recommits it |
| 3 | absorb | `EVALUATION_CLAIM` | `u_0..u_{s−1}`, then `v` |
| 4 | absorb | `PCS_OPENING` | `h` |
| 5 | squeeze | `MERCURY_ALPHA` | `α` |
| 6 | absorb | `PCS_OPENING` | `[q, g]` |
| 7 | squeeze | `MERCURY_GAMMA` | `γ` |
| 8 | absorb | `PCS_OPENING` | `[s, d]` |
| 9 | squeeze | `MERCURY_Z` | `z`, by §3.4's rule |
| 10 | absorb | `PCS_OPENING` | `g_z, g_{1/z}, h_z, h_{1/z}, s_z, s_{1/z}`, one message |
| 11 | absorb | `PCS_OPENING` | `pi_z`, before `δ` although the batch does not read it |
| 12 | squeeze | `BDFG_BATCH` | `δ` |
| 13 | absorb | `PCS_OPENING` | `w` |
| 14 | squeeze | `BDFG_POINT` | `z′` |
| 15 | absorb | `PCS_OPENING` | `w_prime` |
| 16 | squeeze | `PAIRING_MERGE` | `ρ`, after all eight points and six values |

The prover draws `ρ` too and discards it, so both sides leave the transcript in one state and an
opening composes inside a larger transcript, the shard transcript ([proof.md](https://apogee.gweb3networks.com/docs/auditors/spec/proof) §4).

### 3.3 The BDFG20 batch

Mercury §6 step 4(e) leaves the batched KZG opening to BDFG20 §4. The point set is
`T = {z, 1/z, α}`, and the four polynomials are batched in this order, which fixes the power of
`δ` each carries (`pcs_verify::bdfg::items`, which both sides read):

| `i` | `f_i` | `S_i` | `Z_{T∖S_i}` | `r_i` interpolates |
| --- | --- | --- | --- | --- |
| 0 | `g` | `{z, 1/z}` | `X − α` | `g_z`, `g_{1/z}` |
| 1 | `h` | `{z, 1/z, α}` | `1` | `h_z`, `h_{1/z}`, `h_α` |
| 2 | `S` | `{z, 1/z}` | `X − α` | `s_z`, `s_{1/z}` |
| 3 | `D` | `{z}` | `(X − 1/z)(X − α)` | `D_z` |

```text
F(X) = Σ_i δ^i·Z_{T∖S_i}(X)·(f_i(X) − r_i(X))                          W  = [(F/Z_T)(x)]_1
L(X) = Σ_i δ^i·Z_{T∖S_i}(z′)·(f_i(X) − r_i(z′)) − Z_T(z′)·(F/Z_T)(X)    W′ = [(L/(X − z′))(x)]_1
```

Both divisions are exact for an honest prover, and `open` asserts it
(`pcs_verify::bdfg::{quotient, linearization}`).

### 3.4 Challenges and derived values

Mercury draws `z ∈ F*`; here `z` is drawn again under `MERCURY_Z` while it is zero
(`pcs_verify::challenge_z`). `T` needs three distinct points, so both sides refuse with
`PcsError::DegenerateChallenge` when `z² = 1`, `z = α` or `z·α = 1` (`pcs_verify::degenerate`):
probability about `2^−252`, and a loss of completeness only. The recursion tape draws `z` once and
asserts all four conditions (`verifier_core::tape::mercury_scalars`).

The verifier is not sent `h(α)` or `D(z)`: it derives them, as Mercury §6 step 4(c) does
(`pcs_verify::derive_h_alpha`), and the prover builds the batch around the same derived values.

```text
D_z = z^{b−1}·g_{1/z}
h_α = (g_z·P_u1(1/z) + g_{1/z}·P_u1(z) + γ·(h_z·P_u2(1/z) + h_{1/z}·P_u2(z) − 2v)
       − z·s_z − s_{1/z}/z) / 2
```

Opening `D` at `z` to `D_z` is the degree check on `g` (Mercury §4.3); opening `h` at `α` to `h_α`
is §3.1's identity at `z`.

## 4. The proof and the verifier's checks

`pcs::MercuryProof` is eight points and six values. Its field order is its byte order and its
transcript order, and `to_bytes` writes `pcs::PROOF_BYTES = 704` bytes for every `n` and `k`:

```text
h  q  g  s  d  pi_z  w  w_prime                 8 × 64 bytes, G1 uncompressed (primitives.md §3)
g_z  g_inv_z  h_z  h_inv_z  s_z  s_inv_z        6 × 32 bytes, canonical Fr (primitives.md §1)
```

`from_bytes` returns `None` unless every point decodes through `curve::G1Affine::from_bytes`
(canonical and on the curve; G1's cofactor is 1) and every value through `field::Fr::from_bytes`.

Two relations are checked, each written `e(A, [1]_2) = e(B, [x]_2)` so that both G2 arguments are
SRS constants: the fold identity at `z` (Mercury §6 step 4(f), its `z` term moved into G1) and the
BDFG20 batch (BDFG20 §4.1). They merge under `ρ` into one `curve::pairing::pairing_check` of two
pairs:

```text
A1 = cm − (z^b − α)·q − g_z·[1]_1 + z·pi_z                  B1 = pi_z
A2 = Σ_i c_i·cm_i − K·[1]_1 − Z_T(z′)·w + z′·w_prime        B2 = w_prime
     cm_i = g, h, s, d    c_i = δ^i·Z_{T∖S_i}(z′)    K = Σ_i c_i·r_i(z′)
     Z_T(z′) = (z′ − z)(z′ − 1/z)(z′ − α)
accept iff  e(A1 + ρ·A2, [1]_2)·e(−(B1 + ρ·B2), [x]_2) = 1
```

If either relation is false the merged one holds for at most one `ρ`, and `ρ` follows every proof
element. The verifier reads three SRS points, `srs::SrsVerifier`'s `[1]_1`, `[1]_2` and `[x]_2`,
and does no G2 arithmetic.

`pcs::verify` refuses, in order: a `u` whose length is not an instance's (§1), before anything is
absorbed (`UnsupportedNumVars`); a proof point or `cm` off the curve (`InvalidPoint`), checked
again because a proof built in memory has met no decoder; a degenerate `T`
(`DegenerateChallenge`); a failed pairing check (`VerificationFailed`), which does not say which
relation failed.

## 5. Batching `k` columns at one point

Not in the papers. `k` commitments to columns of one size, opened at one point `u`, are one
Mercury instance with one proof (`pcs::batch_open`, `pcs::batch_verify`); a shard proof's opening
is one such batch ([proof.md](https://apogee.gweb3networks.com/docs/auditors/spec/proof) §5). Three steps precede §3.2's sixteen
(`pcs_verify::batch_preamble`):

| # | | tag | message |
| --- | --- | --- | --- |
| B1 | absorb | `COMMITMENT` | `cm_0..cm_{k−1}`, as passed, one message of `4k` limbs |
| B2 | absorb | `EVALUATION_CLAIM` | `u_0..u_{s−1}`, then `v_0..v_{k−1}` |
| B3 | squeeze | `MERCURY_BATCH` | `ρ` |

The opening then runs on `(cm*, u, v*)`, with `cm* = Σ_i ρ^i·cm_i` and `v* = Σ_i ρ^i·v_i`.

- `ρ` follows every commitment and every claimed value. Column `i` carries `ρ^i`, column 0
  carrying 1, so a reordered or shortened list is a different statement.
- The list is one message, so its length `4k` fixes `k`, and then `s` from B2's `s + k` scalars:
  the absorbed stream is injective.
- `ρ = 0` is not redrawn: it checks column 0 alone, and is one of the roots the bound below
  counts.
- A batch of one is a different transcript from a bare opening; their proofs do not interchange.

The batch is sound: by §2's linearity `cm*` commits to `f* = Σ_i ρ^i·f_i`, and evaluation at `u`
is linear, so `v* − f̂*(u) = Σ_i (v_i − f̂_i(u))·ρ^i`, a polynomial in `ρ` of degree at most
`k − 1` fixed before `ρ` is drawn. A false claim survives with probability at most `(k − 1)/|Fr|`.

The prover builds `f*` as one `Fr` column and opens it once; mixed sizes are refused
(`MixedColumnSizes`). The verifier refuses an empty list (`EmptyBatch`) or a value count that
differs (`BatchLengthMismatch`), checks every `cm_i` on the curve before summing, derives `cm*` by
a `k`-point MSM and runs §4 on it. `pcs::batch_open_stacked` opens recursion stacks at `u ‖ r`
([recursion.md](https://apogee.gweb3networks.com/docs/auditors/spec/recursion) §1.3); `batch_open` is it at `r = []`, one column a stack.

## 6. Deferred verification and the accumulator

### 6.1 The twelve entries

Deferring a verification runs every check of §4 but the pairing and keeps the relation's terms:
twelve `pcs::AccumulatorEntry { side, scalar, point }`, `side` a `pcs::PairingSide`, `G2One` for
`[1]_2` or `G2X` for `[x]_2`. The points are `[cm, h, q, g, s, d, pi_z, w, w_prime, [1]_1]`, as
`pcs_verify::ENTRY_POINTS` indexes them, and the scalars are `pcs_verify::scalars`'s, in §4's
notation:

| # | side | point | scalar | # | side | point | scalar |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | `G2One` | `cm` | `1` | 6 | `G2One` | `pi_z` | `z` |
| 1 | `G2One` | `h` | `ρ·c_1` | 7 | `G2One` | `w` | `−ρ·Z_T(z′)` |
| 2 | `G2One` | `q` | `−(z^b − α)` | 8 | `G2One` | `w_prime` | `ρ·z′` |
| 3 | `G2One` | `g` | `ρ·c_0` | 9 | `G2One` | `[1]_1` | `−(g_z + ρ·K)` |
| 4 | `G2One` | `s` | `ρ·c_2` | 10 | `G2X` | `pi_z` | `1` |
| 5 | `G2One` | `d` | `ρ·c_3` | 11 | `G2X` | `w_prime` | `ρ` |

The `G2One` terms sum to `A1 + ρ·A2` and the `G2X` terms to `B1 + ρ·B2`; entry 9 carries both
relations' `[1]_1`, and entry 2 is zero exactly when `z^b = α`, which is legal. A batch derives
`cm*` first, so entry 0 is `cm*` and a check is `ENTRIES_PER_CHECK = 12` entries whatever `k`.
`pcs::verify` and `pcs::batch_verify` spend the entries at once; `pcs::verify_deferred` and
`pcs::batch_verify_deferred` return them.

### 6.2 What uses it

- Base verification pairs: `crates/verifier` runs `pcs::batch_verify` for each shard, and no
  `ShardProof` or `BlockProof` carries an entry.
- The recursion tree folds. A shard's tape computes the twelve scalars over field cells
  (`verifier_core::tape::mercury_scalars`), `cm*` being a hint; the node folds them with the batch
  check `cm* = Σ_i ρ^i·cm_i` ([recursion.md](https://apogee.gweb3networks.com/docs/auditors/spec/recursion) §8.3), and one pairing check at the top
  discharges every shard's ([recursion.md](https://apogee.gweb3networks.com/docs/auditors/spec/recursion) §9). Natively, `host::recursion` runs
  `pcs::batch_verify_deferred` on each shard for its `cm*`.
- Nothing else: `pcs::verify_deferred`, §6.3's word form, `pcs::accumulator_digest` and
  `pcs::discharge` are called only by `crates/pcs`'s tests and `tools/kat-gen`.

### 6.3 The word form and `discharge`

A list is grouped into deferred checks, `checks[j]` being group `j`'s entry count, and written as
canonical `Fr` words (`pcs::accumulator_words`, inverse `pcs::accumulator_from_words`):

```text
group:  count  entry_0 .. entry_{count−1}
entry:  side  scalar  x_lo  x_hi  y_lo  y_hi       side 0 = G2One, 1 = G2X; ENTRY_WORDS = 6
```

A word is 32 bytes, so an entry is 192, and the limbs are the point's transcript form
([transcript.md](https://apogee.gweb3networks.com/docs/auditors/spec/transcript) §4). There is no header, so two lists concatenate into a list whose
checks keep their groups. Decoding refuses a count of `2^64` or more or one that overruns, a side
other than 0 or 1, a limb of `2^128` or more other than the sentinel, a partial sentinel, the
all-zero quadruple (infinity has one spelling), and a point that is not canonical or not on the
curve. The digest is the words as one `ACCUMULATOR_DIGEST` message in a fresh sponge, then a raw
`sample`; covering the count words, it binds the grouping.

```text
discharge(vsrs, entries, checks):
  every entry's point on the curve, before anything else
  ν = fresh sponge: absorb ACCUMULATOR_DIGEST [digest], challenge ACCUMULATOR_MERGE
  A = Σ_j ν^j·(group j's G2One terms)      B = Σ_j ν^j·(group j's G2X terms)
  accept iff e(A, [1]_2)·e(−B, [x]_2) = 1
```

An entry's point is a claim: absorption binds only its limbs, and an entry built in memory has met
no decoder. The weight keeps the checks apart: at weight 1, two checks with equal and opposite
errors pass together, and weighted, a false group passes only where `ν` is a root of a nonzero
polynomial of degree below the group count. `ν` is a function of the words because `discharge`
takes no transcript. An empty list discharges.

## 7. Cost and security

| | |
| --- | --- |
| prover, field | `O(n)`: a pass for `h`, the fold, `H`'s division; `S` in `O(b log b)` |
| prover, MSMs | `2n + 5b − 4` scalar multiplications: `q` `n − b`, `pi_z` `n − 1`, `h`, `g`, `d` `b` each, `s`, `w`, `w_prime` `b − 1` each. A commitment is one more MSM of `n` |
| batch of `k` | `k` multiply-adds a coefficient for `f*` and a `k`-point MSM for `cm*`, then one opening |
| verifier | `O(t)` field operations, MSMs of ten points and of two (and of `k`), one two-pair pairing check |
| measured | `n = 2^22`: commit 1.30 s, open 2.89 s. 16 columns of `2^20`: a batch opens in 1.01 s and verifies in 4.8 ms, 16 single openings take 9.79 s and 62 ms. 18-core Apple M5 Pro; `bench mercury`, `bench mercury-batch` |

Knowledge soundness holds in the algebraic group model under q-DLOG (Mercury §6, BDFG20 §4), with
Fiat–Shamir over the Poseidon2 transcript in the random-oracle model and an SRS whose `x` nobody
knows ([srs.md](https://apogee.gweb3networks.com/docs/auditors/spec/srs) §3). The statistical terms are Schwartz–Zippel over `α`, `z` and `z′`, of
order a committed polynomial's degree over `|Fr|`, a few `1/|Fr|` for `γ`, `δ` and the merge `ρ`,
`(k − 1)/|Fr|` for a batch and the group count over `|Fr|` for `ν`: each is below `2^−220` for
every instance in use, and the level is BN254's ([architecture.md](https://apogee.gweb3networks.com/docs/auditors/spec/architecture) §4).
Nothing is hiding and nothing is blinded.

Mercury's SRS has exactly `n` powers; here one SRS serves every size, so a prover can commit to a
polynomial of degree `n` or more, and no degree bound is checked. None is needed: Mercury §6's
argument goes through with its Schwartz–Zippel terms over that degree, and the opening at `u` is
the multilinear extension of the polynomial's first `n` coefficients. A commitment binds that
truncation, which is linear, so §5's argument holds for it too.