The competition is live in beta.

ots.golf

← Back to leaderboard

Upper bound · leanISA cycles verified

Claim
170549 cycles record
Instructions
131,072
Submitter
scaraven
Assisted by
Claude
Commit
86ed7c9a91 in https://github.com/leanEthereum/ots.golf-submissions.git
Pull request
#31
Code
View source on GitHub
Queued
2026-09-23 19:23:07 UTC
Finished
2026-09-23 19:27:02 UTC · 221 s

Description

Completes the leanISA Winternitz baseline drafted in #23 by @TomWambsgans and claims 170549 cycles on upper-leanisa (first entry on this track). Tom's four commits are kept with their authorship; only formal/Submissions/UpperLeanIsa/ changes.

Scheme: unchanged from #23 (Algorithms.lean): 34 chains of 128-bit words, 32 base-256 message digits plus two checksum digits, chain steps tagged with chain id and position, an MD-style root fold with distinct metadata, and every query in the exact 896-bit BLAKE2S shape.

What this PR adds - secure (Security.lean): #23's ingredients (records, exposure/hidden partition, resampling, hidden-word and second-preimage charges) assembled in two stages. Stage A is a supermartingale over public-data fibers via master_family. Stage B uses identical-until-bad on the exposed run, plus a cut-relative forgery lemma (Events.events_stB): an accepted fresh pair is either a hidden-word hit or a cut-target hit. There are two charges of 2⁻¹²⁹ per compression, so the bound is probTrue ≤ B/2¹²⁸ < B/2¹²⁷. Key generation is bridged to a uniform average over records in KeygenBridge.lean. - Bytecode (MachineProgram.lean): straight-line code with fp = 1 throughout and a single final JUMP to the sentinel. - Each chain executes all 255 steps. A thermometer mux feeds in the signature word at the signed digit; earlier positions hash that word as dummies. - Digits are tied to the pinned message cells by XOR-accumulating shifted byte constants. - The checksum is checked through powers of g: g^C = g^(256·c_hi) · g^(c_lo). - 92093 instructions, 8704 BLAKE2S. - Cycles (MachineRun.lean): every completing run executes exactly those instructions on every answer path. Cost is 92093 + 9·8704 = 170429, plus the 120-cycle boundary charge, for 170549. - Sound / Faithful (ConstraintMath, MachineProver, MachineSound, MachineFaithful): - The constraints force the verifier's digits, chain values and root on any committed image, at any admissible memory size. - The honest prover's image satisfies every constraint exactly when the verifier accepts. - seeded_rows: 2^17 + 2^17 < 2^20.

It is a deliberately simple baseline, not a cycle-optimised one.

Validation: on a private CI mirror of the hosted verifier, run against the pinned contract da1418bf, this exact root passed every step: - policy check; - lake build Submissions.UpperLeanIsa.Solution; - stub statements and axioms (only propext, Quot.sound, Classical.choice); - comparator with kernel replay.