Do free retries break hash-derived spot checks?

research/fiat-shamir-grinding

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.

12 tests

What it found

When an audit challenge is the hash of the prover's own commitment, a cheater simply re-rolls until the challenge misses its corrupted steps, so expected profit is exactly G−c/p (p = C(T−k,q)/C(T,q)) and the stake plays no role. Deterrence needs q ≈ ln(G/c)·T/k opened steps against ln2·T/k for a post-commitment beacon: 10×–60× more for G/c = 2¹⁰…2⁶⁰. Proof-of-work on the challenge has a closed-form optimum x* = v/λ_p − c₀. Real SHA-256 grinding matches the geometric law. Stylised.

A figure from its own output

Figure produced by research/fiat-shamir-grinding: avoidance_vs_q — fiat-shamir-grinding/experiments/avoidance_vs_q.svg, written by the project's own experiment code.

Paper, code and results

More in Verification games & slashing

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.
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

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.