How big should a random verifier committee be?

research/committee-sampling

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.

11 tests

What it found

Drawing m verifiers from a pool of N with B Byzantine, majority capture is exactly hypergeometric: zero once m ≥ 2B+1 and up to 26× below the with-replacement binomial (N=100, B=30, m=41: 1.4×10⁻⁴ vs 3.6×10⁻³). For failure 2⁻⁴⁰ the exact size is a steady ≈0.90 of ln(1/ε)/KL(½‖β) while Hoeffding over-sizes it up to 2.2×. With stake-weighted draws only the Byzantine stake share counts: 20 of 100 nodes at 4× stake capture a 41-member committee half the time. A threshold-t rule trades wrong acceptance (2.7×10⁻⁷ to 1.1×10⁻¹⁶) against stalls (2.7×10⁻⁷ to 3.3×10⁻²). Static adversary, exact computation.

A figure from its own output

Figure produced by research/committee-sampling: capture — committee-sampling/experiments/capture.svg, written by the project's own experiment code.

Paper, code and results

More in Verification games & slashing

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.
Can a bond tell reliable hardware from unreliable?Can a bond tell reliable hardware from unreliable? Single crossing runs the wrong way: reliable rent (θ_H−θ_L)(c+(1+ρ)s_H)/(1−θ_H) is minimised at zero stake, a flat wage is optimal, and a deterrence stake scales rent by (c+(1+ρ)s)/c.
How many milestones does an unenforced job need?Milestone payments without enforcement: a split pre-payment needs only the pooled relationship value (C/(W_r+W_w) vs P/W_r, C/W_w), and front-loading makes the milestone count logarithmic, ⌈ln(1+(V−C)/W)/ln(V/C)⌉ (17 vs 100 at W=1).
What is the cheapest payment-and-audit protocol that makes honest ML training an equilibrium?Research programme: incentive-compatible verification of outsourced ML training; first measurement on real training finds a tolerance-tau referee passes a skip-steps cheat on 30% of steps at tau = 1e-2 while the held-out loss stays within one seed std, and the loss only suffers at tau about 10x the worst benign drift; milestone 4 prices contracts by linear programme: with a tolerance, audit-only cannot enforce full effort and the joint contract beats both checks only when the score is precise (4 of 45 cells); milestone 6: against a coordinating majority replication adds no deterrence beyond the audit and the stake is flat in the number of workers (140 cells); milestone 5: an agreement term between redundant workers is worth nothing beyond the audit once cheats copy one trajectory (0 of 1,349 random instances), and a proved one-sided bound max(C, g/p - S) holds in 2,755 instances but is vacuous for a noisy score
Economics of refereed verificationInspection-game economics of refereed verification: stake substitutes for re-execution, extra verifiers free-ride, and optimal tolerance/stake under floating-point drift.
Bribing the verifiersBribing verifiers in refereed verification: closed-form bribe floor, a sharp collusion-proof stake that falls as 1/m, and jackpots that raise the floor one-for-one.

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.