A conclusive fraud proof by bisection

Status: hypotheses recorded before the run.

Why

E024's audit catches a single-layer cheat 4.2% of the time, and leans on the stake to make that enough. The economics work, but the verdict is probabilistic: we can never say "this provider cheated", only "cheating is negative expected value."

Optimistic rollups do not settle for that. Arbitrum resolves a dispute by bisection: the two parties binary-search to the first step where their states differ, and an arbiter adjudicates that single step. The outcome is conclusive, and the arbiter's work is O(1) rather than O(job).

That construction has never applied to neural inference, for the reason this whole programme is about: it requires that two honest parties computing the same thing get the same bytes, and in floating point they do not. E018 measured honest CPU/GPU disagreement at 1 run in 10.

Under the numeric contract they agree exactly. So the machinery becomes available, and unlike EigenAI's optimistic re-execution the two parties need not share hardware — which is their stated future work, quoted in docs/literature.md.

E024 already commits to every layer output in a Merkle tree. That is precisely the structure a bisection game needs, built for a different reason.

The protocol

1. Provider P runs the job, commits root_P over its L layer outputs
2. Challenger C runs it too, commits root_C
3. root_P == root_C → agreement, and under the contract that is exact, not approximate. Done.
4. Otherwise binary-search for the first layer where their committed digests differ. Each round exchanges one digest and its Merkle path.
5. At the first divergent layer k, both parties agree on the state entering k and disagree on the state leaving it
6. The arbiter recomputes layer k alone and rules

What this does and does not buy

It does not reduce the challenger's cost. C runs the whole job — that is what makes it a challenger. Bisection makes the arbiter cheap and the verdict certain. This is the same trade Arbitrum makes.

So the two mechanisms are complementary, not alternatives:

The audit is the always-on cheap check. The bisection is what a dispute escalates to.

Hypotheses, recorded before looking

H1. Bisection isolates the first divergent layer in exactly ceil(log2(L)) = 5 rounds at L = 24.

H2. Total traffic is a few hundred bytes — orders of magnitude below E024's 0.115 MB layer opening, because only digests and paths move, never a tensor. The one tensor that must eventually move is the input to the disputed layer.

H3. The arbiter recomputes exactly one layer, independent of L and of how many layers were cheated.

H4. A lying challenger is caught by the same machinery. The arbiter decides which party is wrong, not merely that they disagree — otherwise the protocol is a griefing vector, since anyone could dispute an honest job for free.

H5. If the provider cheats on layer k, the first divergent layer is k. A perturbation at k should propagate to every later layer, so the search lands exactly on the cheat rather than somewhere downstream. This is the one I am least sure of — if a cheat can be masked at some later layer, the bisection would blame the wrong layer and the fraud proof would name an innocent step.

What would falsify the approach

If H5 fails — if bisection can land on a layer that is not where the cheating happened — then the fraud proof identifies the wrong step, and slashing on it would punish honest work. That would be disqualifying, not a detail.

If H4 fails, the protocol is a denial-of-service tool: free disputes against honest providers with no consequence for the liar.

All five hypotheses confirmed, including H5, which was the one that could have disqualified the approach.

Bisection turns E024's probabilistic audit into a conclusive one at essentially the same bandwidth. The price is not bytes: it is that someone has to have actually run the job.

The result

Qwen2.5-0.5B, 24 layers, under NC-0.5.

The comparison that matters

Same bandwidth, same arbiter cost, and the outcome goes from probabilistic to conclusive. The entire extra cost is the challenger's re-execution.

That is the honest accounting, and it is the same trade Arbitrum makes: the challenger does full work off-chain so the arbiter does O(1) work on-chain. Bisection does not make verification cheap. It makes adjudication cheap, and the ruling certain.

So the two mechanisms are complementary rather than competing. The random audit is the always-on check that makes cheating unprofitable. Bisection is what a dispute escalates to when someone is willing to pay to prove it.

H5 — does the search land on the actual cheat?

This was the hypothesis worth worrying about. If a perturbation at layer k could be masked further down, bisection would name the first layer where the digests happen to diverge, which might not be where the cheating happened — and slashing on that would punish honest work.

24/24 correct. Perturbing a single int64 by 1 at layer k propagates to every subsequent layer, so the first divergence is always exactly k.

Worth being precise about why. Under the contract each layer is a deterministic integer function, so a changed input gives a changed output unless it hits a genuine collision. Nothing here is probabilistic in the way a float pipeline would be, where a small perturbation can be rounded away and vanish. The same exactness that makes heterogeneous verification possible is what makes the fraud proof point at the right layer.

H4 — the griefing check

A challenger that disputes an honest job is ruled against, by the same machinery: the arbiter recomputes the disputed layer and compares its own digest against what each side committed. It names which party is wrong, not merely that they disagree.

Without this the protocol would be a denial-of-service tool — free disputes against honest providers. With it, a false dispute is as slashable as a false result, which is what makes the challenger role safe to open up.

H2 — traffic, scored honestly

Predicted "a few hundred bytes" of protocol overhead; measured 1,920 B. The right order, the wrong number. Traffic is 2 parties × ⌈log₂L⌉ rounds × (1 + ⌈log₂L⌉) × 32 bytes, so it grows as O(log²L) — 1.9 KB at 24 layers, about 3.6 KB at 80. Negligible either way; the disputed tensor dominates by 60×.

What gets better with depth

Both scale the right way:

• rounds grow as log₂L — 5 at 24 layers, 7 at 128
• the arbiter's share is 1/L — it falls as models get deeper

A deeper model makes bisection cheaper, not more expensive. That is the opposite of re-execution, and the opposite of E024's detection probability, which also falls as 1/L but in the wrong direction.

What this does not settle

• Someone must re-execute. Bisection has nothing to adjudicate until a second party has done the whole job. Who pays for that, and what they earn for a successful challenge, is an economic design we have not done.
• Both parties must commit before disputing. The protocol relies on each side's digests being checked against a root fixed in advance. A party allowed to commit late can adapt its story.
• Not deployed. Same caveat as everything else here: this runs in the research repo, not in v1.
• One perturbation model. We cheat by adding 1 to a single element. A cheat designed to collide with the honest digest would defeat this, but that is a SHA-256 preimage problem, not a protocol weakness.