How wide should a dispute bisect?

research/dispute-arity

K-ary bisection dispute games: optimal arity solves k ln k − k + 1 = a/b (binary only if a/b ≤ 0.386), 1.9–6× cheaper than binary at T=10⁶, adaptive schedules gain ≤1%, leaf-size trade-off, latency as extra round cost.

10 tests

What it found

Arity and leaf size of k-ary bisection dispute games for refereed verification: the optimal arity solves k ln k − k + 1 = a/b (binary only if a/b ≤ 2ln2−1), arity 10 is 1.9× cheaper than binary at a million steps and 6× at a/b=1000, exact adaptive schedules gain at most about 1%, early-stopping with referee re-execution saves 9–56%, and latency just widens arity. Verified on an executable SHA-256 dispute. Stylised.

A figure from its own output

Figure produced by research/dispute-arity: optimal_arity — dispute-arity/experiments/optimal_arity.svg, written by the project's own experiment code.

Paper, code and results

More in Verification games & slashing

Can stake shorten a challenge window when proposers can be bribed?Optimistic-verification challenge windows with bribable proposers: exact gamble-then-bribe attacker recursion, closed-form window, stake cannot shorten it under an exogenous bribe price (63 blocks for S=10…1600), bounty-funded priority fees give S·w ≈ G/((1−ρ)θ).
How much does an appeal ladder of juries buy, and what must appeals cost?Escalating jury appeal ladders with fee-priced appeals: an exact fee window makes error ∏(1−M_k), 11 jurors is the smallest deterring panel at prize 100, 3→11→27 errs 2.4e-4 at 5.8 expected seats vs 12.6% for one 7-seat panel, shared jury bias sets a floor ρ(1−a).
Do free retries break hash-derived spot checks?Hash-derived audit challenges under free retries: cheat profit exactly G − c/p, deterrence needs ln(G/c)·T/k opened steps vs ln2·T/k for a beacon (10×–60×), stake is irrelevant, and the proof-of-work optimum is x* = v/λ_p − c0.
When do verifiers complement rather than substitute?Verifiers as informational complements: decision value is zero below a closed-form committee size while mutual information is submodular; myopic hiring buys nothing and leave-one-out pay is a sawtooth that vanishes.
How big should a random verifier committee be?Verifier committees from a finite pool: exact hypergeometric capture (zero once m ≥ 2B+1, up to 26× below binomial), exact size ≈0.90 of ln(1/ε)/KL(½‖β) vs Hoeffding up to 2.2× too large, stake-weighted draws depend only on Byzantine stake share (20 of 100 nodes at 4× stake capture a 41-committee w.p. ½), and the threshold safety/liveness trade-off.
Are reward pools identity-proof?Identity splitting vs merging under stake-weighted pools: split-invariant iff the weight is linear in stake, per-head optimum √(Rn/c)−n, sharp deterrence fee Rn/((n+1)(n+2)), wagering split-neutral.

All 19 Verification games & slashing projects →

Other research topics

Proper scoring & elicitation28 Effort & peer prediction9 Verification games & slashing19 Detection & tolerances14 Markets as routers13 Prediction-market design9 Paying contributors8 Decentralised training systems23 Digital twins & sim-to-real164 LLM chip design loops40 Robot manufacturing loops53 Ambient AI assistant46 Self-replicating manufacturing34 Simulation-first design64 Engineered clothing45 Task-specific AI accelerators40 Algorithmic chip-design loops42 Open-source purpose-built robots44 The software-engineering loop43 Adversarial human imitation41 Open-source residential construction41 Autonomous multi-angle capture34 Sensing, imaging and 3D31 Energy supply and dense energy storage39 Robot societies among people31 Agentic co-design of low-cost robots27 Laundry-hanging robots25 Machine learning on qualitative data23 Robots on the building site27 Civilizations & group psychology1 History & human sciences1

Produced with AI assistance (Claude). Results are from the code in this repository and are simulated or stylised unless the abstract says otherwise; nothing here implies affiliation with or endorsement by any lab, researcher or company cited. MIT licensed.