Mercury, Both Ways at Once

Mercury opens a multilinear polynomial with a proof that does not grow with the polynomial: five commitments, three opening elements, six field numbers — whether the witness has thirty-two entries or a billion. This page runs one whole opening on a five-variable instance over a 27 481-element field and prints every number it touches: the 4 × 8 table, the halfway vector, both routes to the single value that pins it down, the four Horner divisions, the compression polynomial, and the two pairing equations at the end. Thirty-nine steps, forward and back.

Sumcheck-based systems are fast because their prover work is linear, and they end by needing one multilinear polynomial opened at one random point. The existing ways to serve that ending each give something up. gemini and zeromorph keep the prover linear but send a commitment per variable, so the proof grows as O(log n) and so does the verifier's group work. The univariate route keeps the proof constant but pays an FFT, putting O(n log n) field operations back into a prover chosen for not having them.

Mercury takes neither trade. The proof is a constant number of elements, the prover does O(n) field operations and 2n + O(√n) scalar multiplications, and the commitment is an ordinary KZG commitment to the same coefficient vector — so a system already committing that way changes what it does at opening time and nothing else.

The technique underneath is a way of folding a witness by many variables at once and proving the fold was honest, using univariate polynomial division. Proof size and prover time do not depend on the folding factor, which is what makes folding halfway in a single step affordable.

Reshape the n values into a table and split the evaluation point to match. The ordinary fold-to-one procedure then becomes a single matrix expression, v = Ψu₁T F Ψu₂, and the vector reached halfway through — after the first block of folding rounds — is h = Ψu₁T F. The prover computes it in one pass and commits to it. The verifier, holding only a commitment to the original polynomial, has no way to tell whether that h came from the table or from the prover's imagination.

The resolution is to fold the table a second time, along the other axis, by weights the verifier chooses after h is fixed: powers of a random α, giving g = F A. Two numbers can now be formed from the same table. Evaluate the halfway vector at α, or evaluate the folded vector as a multilinear at u₁. Both are Ψu₁T F A — the same double sum, taken in a different order — so both are the same number, and a prover who altered h must match a value computed along a path that never touched it.

The page draws this as a grid with weights in its margins. The left margin folds rows, the top margin folds columns, and the two folded results run out along the right edge and the bottom edge. The corner where they meet is reachable from both directions, and it holds one number. On the walkthrough it is the cell that lights up violet.

The cross-check only helps if g is genuinely the fold of the committed table, and there is a cheap way to get exactly that. Modulo Xb₁ − α, the indeterminate Xb₁ is α. Since the univariate encoding puts the flat index in the exponent, Xi+jb₁ reduces to αjXi: every entry of column j picks up αj, and every column lands on the monomial belonging to its own row. The remainder of f under that modulus is the folded vector, coefficient for coefficient.

So the fold is not proved by a circuit or a sumcheck. It is proved by a division identity, f = (X4 − α)q + g, which a KZG verifier tests at one point with one pairing equation. The quotient costs nothing exotic either: dividing by a linear polynomial is Horner's rule, run once per row, and the coefficients of q are the row quotients interleaved back together. That is the whole of the O(n) field work — twenty-eight multiply-adds on this instance — four rows by seven steps — and the page shows all four tapes.

One condition makes the remainder unique, and it has to be proved rather than assumed. Any multiple of X4 − α can be moved between q and g without disturbing the identity, so the prover must also show deg g < 4. The witness is the reversal D(X) = X3g(1/X), which is a polynomial exactly when that bound holds — and which cannot be committed at all when it does not, because the reference string carries no negative powers of the trapdoor.

Two claims survive to the end, and both are inner products of committed coefficient lists: ⟨Pu₁, g⟩ = ĝ(u₁) and ⟨Pu₂, h⟩ = v. An inner product is the constant coefficient of a(X)b(1/X), so a single committed witness S carrying the other powers reduces both to one equation, batched under one challenge γ.

The consequence is the part of the paper worth slowing down for. The verifier does not receive h(α) — the number the linchpin turns on. It reconstructs it from that batched identity, and then requires the committed h to open to the reconstructed value at α. That is why h is opened at three points while everything else is opened at one or two, and it is where a tampered halfway vector is finally caught. The page runs that failure on demand.

The table is the spine of the display and stays on screen throughout, with whichever axis is being folded lit. Beside it, a fixed diagram of the two threads keeps both routes and their meeting point visible from the first step to the last; under it, a trust chain fills in as each link is established — cm to g by the division, g to h by the linchpin, h to v by the second inner product. A transcript panel lists messages in the order they were sent, so it is clear which challenges were drawn after which commitments, and a running tally shows the proof reaching eight group elements and six field elements and stopping there.

Directly beneath the table, a working block performs the current step's arithmetic rather than describing it — the four products of h0 with their running sum, Horner's recurrence line by line down a row, the five terms the verifier adds and halves to recover h(α) without being told it. At the linchpin it prints both routes side by side: eight terms folding the rows, four folding the columns, and the same number under each. Every factor carries the address of the cell it was read from, so hovering a term lights those cells in the table and hovering a cell lights the terms that read it — the formula and the highlight are one object rather than two descriptions of one. The six reference views below it dim to whatever the step is actually reading.

Stepping is exact in both directions. The whole opening is computed once, up front; a step is only a view onto it, so going back restores every value rather than replaying anything. Reseed draws a fresh table, point and challenges. Cheat hands the protocol to a prover that has moved one coefficient of the halfway vector — leaving the table, the point and every challenge untouched, so the only thing that changes on screen is what breaks.

• Real. The field arithmetic, the folds, the division, S and D, the commitments as actual points on an actual pairing-friendly curve, the batched multi-point opening, and both verifier checks — computed as pairings in a twelfth-degree extension, not asserted.
• Checked, not sampled. Every polynomial identity is formed and compared coefficient by coefficient, including the ones a verifier would only ever test at a point. The division identity is expanded in full; the symmetrised inner-product identity is expanded in full; and the derived values D(z) and h(α) are recomputed the way the verifier recomputes them rather than copied from the prover's side.
• Small on purpose. The curve is a Barreto–Naehrig curve at parameter x = 5 rather than the 62-bit parameter of BN254, so p = 27 631 and r = 27 481 and every number on the page is at most five digits. Statistical soundness is about seven bits, cryptographic security is zero — a discrete logarithm in a group of that order is instant — and the reference string's trapdoor is printed in the spec sheet, because a real ceremony's is the one thing nobody may know. That is a feature of the exposition and a disqualification for every other use.
• Rectangular, not square. The paper assumes n = 22t so both halves of the split have the same size; five variables do not allow it, so the page splits 2 and 3 and carries b₁ = 4 and b₂ = 8 separately. The identities are unchanged, but the two are no longer interchangeable, and the page keeps them apart: b₁ governs everything touching the division, b₂ everything counting columns. The one place they meet is deg S ≤ max(b₁, b₂) − 2.

Correctness is the whole of what this page offers, so it was established before it shipped rather than asserted afterwards.

• The shipped script is the tested script. The four modules that make up the inline code are the same files a Node harness requires, so what runs in the browser is what the tests ran against rather than a copy of it.
• Every identity, over every seed. Twelve thousand assertions across 301 instances: v reached three independent ways, the linchpin, the division identity as coefficient vectors, the quotient recovered a second time by generic monic long division, the S identity across all fifteen Laurent powers, and the verifier's step-4c reconstruction against the true evaluation.
• A cross-check of the protocol against the paper was written independently from the text, in the rectangular form, and agreed — including the two places the square case hides a distinction: the modulus exponent is b₁ while the fold weights number b₂, and the batched opening covers h at three points, which the paper states only implicitly.
• The curve was derived, not pasted. Point counting over all 27 631 values of x confirms the order is exactly r; the embedding degree is checked to be twelve; ξ = 4 + u is confirmed neither a square nor a cube; and the pairing is exercised for non-degeneracy, exact order r in GT, and bilinearity on forty-five random scalar pairs.
• Both outcomes were measured. Twenty-four full openings verify by real pairings; twenty-four openings from a tampering prover are rejected, and the rejection lands on the batched opening rather than on the division check — which is the behaviour the soundness argument predicts. A wider sweep built forty thousand openings, honest and tampering, across twenty thousand seeds: every verdict correct, nothing thrown.
• A 29-check self-test runs in the browser on every load and every reseed, and the spec sheet prints its output. Under Cheat it asserts the opposite polarity rather than excusing itself — that the linchpin is broken, that the S identity fails at exactly the constant power, and that the batched opening rejects — so the panel stays green by making the stronger claim rather than the weaker one. It re-checks the curve parameters — the embedding degree, both group orders, the pairing's non-degeneracy and its bilinearity — along with the linchpin, the Laurent identity and both pairing equations, so the numbers above the fold are visibly checked rather than claimed. Three of the checks are aimed at the working block itself: every sum it prints is re-added and compared against a total the instance recorded independently of it, every factor has to address a cell that exists, and every step that dims a reference view has to be pointing at something inside the view it opened.

It is an exposition, not an implementation. The polynomial arithmetic is schoolbook, commitments are computed by direct scalar multiplication rather than by any multi-scalar method, curve arithmetic is affine, and S is built by direct correlation rather than by the FFT of Claim 4.1 — which in this field does not exist anyway, since r − 1 = 23·3·5·229 leaves a 2-adicity of three. The pairing is the reduced Tate pairing rather than the optimal ate, because a fifteen-bit r makes Miller's algorithm free and the plain form needs no Frobenius corrections. None of that is how a library would be written, and the spec sheet says where the two part ways.

It is also not a security argument. The knowledge-soundness proof lives in the paper. What a page can show is the mechanism the proof is about — which check catches which lie, and in what order the challenges have to arrive for the argument to hold at all.

Source: Liam Eagen and Ariel Gabizon, MERCURY: A multilinear Polynomial Commitment Scheme with constant proof size and linear field work, IACR ePrint 2025/385. The batched multi-point opening is Section 4 of Boneh, Drake, Fisch and Gabizon, ePrint 2020/081.