Submission

A submission contains:

• Four RISC-V programs: keygen, sign, expand, and verify.
• Four integers: S (signature size in bytes), W (witness size in bytes), K (cache size in bytes), and C (verification cycles).
• Six byte offsets specifying where RISC-V inputs and outputs reside in memory.
• Lean 4 proofs for every required statement.

Goal: minimize S × C.

Parameters

Programs

Model and costs

Random oracle

All programs and the security game's adversary share one random oracle H, mapping each input of 64·k bytes (k ≥ 1) to an independent uniform 32-byte answer. Security is proved in Lean in this model and counts calls to H.

RISC-V programs

Each program is an RV64IM program with one extra instruction, HASH(input, n, output), issued as a system call. It reads n bytes starting at address input, queries H on them, and writes the 32-byte answer at address output. The input and output addresses must both be multiples of 8, and n must be a nonzero multiple of 64. Hashing n bytes costs n / 64 compressions.

Verification also pays for its witness: ⌈W / 256⌉ cycles.

Required Lean statements

Honest experiment

Experiment: For any secretKey, message, and oracle H:

1. keygen(secretKey) returns the public key and cache.
2. sign(secretKey, cache, message) returns the signature.
3. expand(message, public key, signature) returns the witness.
4. verify(message, public key, witness) returns the verdict.

Stop at the first failure. The experiment succeeds when all stages succeed and verification accepts.

$N_P$ counts program P's compressions; it is zero if P is never reached. $B_P$ denotes P's named budget.

1. CompletenessLean statementFor every secret key, ${\mathrm{Pr}}_H\left[\text{success for every message}\right]\ge 1-\epsilon$.
2. Compression budgetsLean statementFor every secret key and P in {keygen, sign, expand}: ${𝔼}_{H,M}\left[2^{N_P/B_P}\right]\le 2$

${\mathrm{Pr}}_H$ is over H; ${𝔼}_{H,M}$ is over an independently sampled random oracle H and uniform 32-byte message M.

Remark. After H is fixed, adaptively chosen messages may cost much more than this average. Any scheme can rule this out by signing the message hashed with a salt derived from the secret key and the message, and carried in the signature. This costs only 16 signature bytes and one hash, so we prefer to rely on this heuristic rather than complicating the rules.

3. Verification cyclesLean statementFor every secret key, message, and oracle, if the experiment succeeds, verify's cycles plus the witness charge ⌈W / 256⌉ are at most C.

Security

Experiment: Let A be a classical probabilistic adversary with unrestricted computation and an integer hash-call budget Q ≥ 1.

1. Sample H and a uniform secret key independently. Initialize an empty transcript T and count every call to H throughout the experiment.
2. Run keygen(secretKey). Failure ends the experiment without a win; otherwise give A the public key and cache.
3. A may then adaptively query two oracles:
   random_oracle(input_A)

   For an input_A of 64·k bytes, return H(input_A).

   signing_oracle(message_A, cache_A)

   Run sign(secretKey, cache_A, message_A) with the original secret key. Return the signature or failure. Add each returned (message_A, signature) to T. Allow at most $L$ requests.

4. A makes one final submission in either form:
   Witness weak unforgeability

   Submit (message_A, witness_A). Win if:

   • verify(message_A, public key, witness_A) accepts
   • no pair in T has message message_A
   • the total hash-call count is at most Q

   Signature strong unforgeability

   Submit (message_A, signature_A). Win if:

   • expand(message_A, public key, signature_A) returns a witness that verify accepts
   • (message_A, signature_A) is not in T
   • the total hash-call count is at most Q

The total hash-call count includes key generation, signing, A's queries, and final expansion and verification when performed.

Termination

RISC-V interface

Use RV64I and the M extension. Each program’s image must be smaller than $P_{\text{max}}$: four bytes per instruction plus embedded-data bytes.

Code and memory

Code occupies a separate, immutable instruction address space. Instruction i is at 0x1000 + 4 × i. Memory occupies 0x000000–0xFFFFFF (16 MiB).

Load D embedded bytes at $\mathrm{data\_base}=16\times \lfloor \frac{\mathrm{0x1000000}-D}{16}\rfloor$. Initially, sp = data_base and PC = 0x1000; all other registers are zero.

Inputs and outputs

Each submission specifies six byte offsets, shared by all four programs: δ_message, δ_{secret key}, δ_{public key}, δ_cache, δ_signature, δ_witness. Each gives the memory address where that object is written or read. The buffers have the sizes in Parameters, start at 8-byte-aligned addresses, do not overlap, and end at or below data_base for every program.

Before each execution, memory is zero except for embedded data and the inputs listed under Programs; unused object buffers remain zero.

Example: before sign, write the secret key, cache, and message at their offsets. On success, read the signature at δ_signature.

HALT ends execution with exit code a0: 0 means success and any other value failure. For verify, these mean acceptance and rejection, respectively.

System calls

ECALL selects one of two services through t0:

HASH writes H's 32-byte answer at the output address. Any other t0 fails.

Further details

Proof checking

The certificate must pass Lean's kernel against the organizer's definitions. Its transitive axiom dependencies may contain only propext, Classical.choice, and Quot.sound.

Instructions

Encodings are 32 bits. Fetching outside the code or at a non-4-byte-aligned address fails. FENCE has no effect; EBREAK fails.

Registers

x0–x31 are 64 bits. x0 always reads zero and ignores writes. Aliases are sp = x2, t0 = x5, and a0–a2 = x10–x12. PC is separate.

Memory access

Addresses count bytes; multi-byte integers are little-endian. Accesses of 1, 2, 4, or 8 bytes require alignment to their size. Misaligned accesses fail.

Bounds

Every memory access and buffer must fit completely in memory. For unsigned byte address p and length n, require $p+n\le \mathrm{0x1000000}$. Instruction arithmetic and effective-address calculation follow RV64IM.

HASH arguments

Addresses and byte length n are unsigned 64-bit values. The input and output addresses must both be 8-byte aligned, and n must be a nonzero multiple of 64. The input's n bytes and the output's 32 bytes must fit entirely in memory.

HASH execution

Read the n input bytes in increasing address order; they are H's input. Read all input before writing the answer, so buffers may overlap. Preserve registers and advance PC by 4.

Faults

An encoding outside RV64IM (such as compressed, A, F, D, CSR, or FENCE.I), invalid HASH arguments, or any other fault ends the run as a failure; for verify, a rejection.

Lean project

SigGolf.Certificate submission C in SigGolf/Statements.lean is the competition claim for the exact four program images and declared sizes. Besides the five statements above, it contains Admission: the size maxima, the program size limit, and the buffer layout rules. SigGolf/Security.lean defines the attacker and both forgery experiments; SigGolf/Riscv.lean defines execution and costs. In Lean, the adversary is an OracleComp over coins, H, and the signing oracle: a computation that makes finitely many queries and then submits a forgery or gives up. A strategy that could run for ever is represented by its truncations, which give up where they are cut. Giving up never wins, and such a strategy's win probability is the limit of its truncations', so the bound over all adversaries bounds every adaptive strategy.

Build the statements and regression checks with lake build SigGolf SigGolfTests. Dependencies are pinned in lake-manifest.json. These files define the requirements; they do not certify a particular signature scheme. Submissions are verified from the sig.golf-submissions repository.

Known limitations

Quantum security

The security game only considers classical adversaries. NIST level 1 requires ≈ 64 bits of security against quantum adversaries.

Single-user security

The security game targets a single key, but a real attacker can target many users at once. The standard defense starts every hash with a per-key public parameter, so work against one user is useless against others. Drake's trick makes this cheap: a 16-byte parameter in the public key, padded with 48 zero bytes, fills the first 64-byte block of every hash, so its hash state is computed once and reused. Multi-user security then costs one compression and 16 bytes of public key.

MPC for threshold signing

The keygen and signing budgets let reasonably weak devices, such as hardware wallets, sign. Threshold signing runs keygen and sign inside multi-party computation (MPC), where hashing secret data costs far more. MPC precomputation followed by grinding on public values at signing can help (see RivaLabs).

Trading lifetime for faster keygen and signing

Hypertree pruning replaces most hypertree leaves with cheap placeholder hashes and grinds the randomizer until each message lands on a kept leaf, which speeds up keygen and signing without changing verification but lowers the safe number of signatures.

Choice of hash function

The oracle H takes inputs made of 64-byte blocks, returns 32-byte answers, and costs one compression per block. This cost model is accurate for BLAKE2s, for BLAKE3 on inputs up to 1 KiB, and for the SHA-256 compression function, but less precise for standard SHA-256, whose padding adds a block to every input, and for SHA-3, which absorbs 136 bytes per permutation.

Choice of ISA and metering

RV64IM, the cost of each instruction, and details such as where HASH reads its inputs are one choice among many, and may not match a given zkVM.

Delegating hashes of public values

The budgets assume the enclave, such as a hardware wallet, computes every hash. Hashes of public values, typically for grinding, could be offloaded to a powerful host, possibly with a SNARK proving correctness.

127 bits of security

Schemes built on 128-bit hash digests, such as SLH-DSA's 128-bit parameter sets, reach 127 bits of security rather than 128: an adversary can try to guess second preimages, and this bound is tight. This note gives a security proof and a matching attack.