Upper bound · RISC-V cycles verified
- Claim
- 362 cycles record
- Instructions
- 12,340
- Embedded data
- 104 B
- Submitter
- scaraven
- Assisted by
- Claude Fable 5.1 (design search), Claude Opus 5.5 (Lean implementation)
- Commit
2d70c274c5inhttps://github.com/leanEthereum/ots.golf-submissions.git- Pull request
- #29
- Code
- View source on GitHub
- Queued
- 2026-09-23 11:34:50 UTC
- Finished
- 2026-09-23 11:47:09 UTC · 730 s
Description
This lowers the RISC-V bound to 362 cycles (record 364, #28) with a new chain-memory layout on top of the 372-cycle construction of #27 (dense pair dispatch, mixed 192/160-bit states, sum-157 index), which builds on #26 and on the paired dispatch of #24.
Idea
In the 372 image, 24 of the 32 chains are packed 160-bit values: each one's first hash moves it from its 20-byte wire slot into a 24-byte working cell, and a redirect ADDI x10, x12, 8 follows. That redirect is paid 24 times. Here the wire order is chosen so that most chains hash in place, with no move and no redirect.
- A hash writes 32 bytes at an 8-aligned
x12, but it reads its input fromx10, which has no alignment requirement. A chain can therefore run in place with any input offsetj = x10 − x12(0..12 for a 160-bit state, 0..8 for a 192-bit state). Its 32-byte block then extendsjbytes below the state and the rest above it. - The wire interleaves values in a repeating 64-byte unit:
moved narrow value (20 B) | in-place narrow (j = 12) | in-place wide (j = 0). The moved value is read first. The narrow chain above it then overwrites its top 12 bytes, and the wide chain below it overwrites its bottom 8 bytes. So every stale byte of the unit is covered by some chain's final answer, which is the same for every digit vector. The root input stays byte-identical to the one fixed at key generation. - 11 narrow chains and all 8 wide chains now run in place, and only 13 chains are moved (13 redirects instead of 24). Two moved chains land inside a three-value gap of the wire rather than above the signature, which saves 48 bytes of root input.
- The bottom wide chain runs last. It spills into the already-consumed second half of the nonce, outside the root input. That leaves
x10equal to the root input's start, so the root step needs noADDI x10. - The root input is 928 bytes (7424 bits, 15 blocks, 2 more than the 372 image): it holds 20 full 256-bit answers and 12 answer slices of 192 bits. Every chain's top is bound by at least 192 bits.
Accounting
- Index phase: 40 cycles, unchanged.
- Chains: 189 hashes + 64 pointer instructions + 13 redirects + 32 dispatch + 1 width change = 299 cycles.
- Root (
ADDI x11, x13, 1920+ 15 blocks) and decision: 23 cycles. - Total 362. The image is 12340 instructions + 104 data bytes = 49464 bytes. The record's row groups are unchanged.
The accepted set (32 four-bit digits, sum 157), availability bound and index encoding are those of #27. The scheme changes are the per-chain position of the next state inside each answer (slice offsets 0/32/64/96 bits), the wire permutation (32-bit units, kernel-checked inverse), and the root input: a table-driven concatenation whose generic extraction lemma gives the security proof a 192-bit slice of every top. Root cost 15, key generation 1039 and verification 205 compressions. See NOTES.md.
Validation
- The layout was first validated in a Python emulator of the pinned machine. Every accepting run costs exactly 362, and no rejecting run costs more. Every single-bit flip of whole signatures is rejected, the root input is identical to key generation's on every run, and a byte-ownership replay shows no unread byte is overwritten and no signature byte is ignored.
- The Lean certificate builds, and passes the stub statement, axiom check (
propext,Classical.choice,Quot.sound) and the pinned comparator, on a CI mirror of the verifier against coreda1418b: https://github.com/scaraven/ots.golf-submissions/actions/runs/35853511164 (commit 5ed006d; this PR's root is identical exceptNOTES.md). - This PR requests the hosted check.