KERNEL — Formal Specification & Threat Model

Version 1.0 · a provably-fair, two-party tactical duel

This document specifies KERNEL precisely enough to reimplement it from scratch and to audit its security claims. It matches the reference implementation (kernel.html) exactly. It is deliberately explicit about the boundary between what is mathematically guaranteed and what is design judgement.

1. Design thesis

Most competitive games treat cheating as an ongoing enforcement problem: anti-cheat software, server authority, statistical detection, bans. KERNEL takes the opposite approach — it removes the possibility of whole classes of cheating by construction, so there is nothing to enforce.

The core move is to make each turn a cryptographic commit–reveal over simultaneous orders, resolved by a deterministic, integer-only function of committed inputs, with tie-breaks drawn from a jointly-seeded verifiable hash. From this, four common cheat classes become structurally impossible rather than merely policed.

2. What is proven vs. what is assumed

Honesty about scope is part of the design.

Guaranteed (given a secure hash function and at least one honest party):

No player can act on the opponent's orders before committing to their own.
No player can bias a tie-break in their favour.
No player can alter the recorded history of a match without detection.
The match result is a reproducible function of committed inputs — anyone can recompute it.
A player who reveals orders inconsistent with their commitment is detected.

Assumed (standard cryptographic and transport assumptions):

SHA-256 is preimage- and collision-resistant. (Substitute any such hash.)
Each party draws its per-turn nonce from a source the opponent cannot predict.
The message channel between peers is reliable and order-preserving per peer (WebRTC data channels and same-origin BroadcastChannel both satisfy this). The protocol tolerates a peer that drops, duplicates, reorders relative to the other peer, or garbles messages — see §7.

Not claimed:

The mathematics does not prove the game is fun or that its balance is ideal. Balance and feel are design parameters (§10), to be tuned empirically.
Two-party trustless play cannot prevent a player from aborting (refusing to reveal); it can only penalise it deterministically (§7.7). This is a fundamental limit of two-party protocols without escrow, not an implementation gap.

3. Game definition

3.1 Board

A 7 × 7 toroidal grid. Coordinates (x, y) with x, y ∈ {0..6}. All movement wraps: the neighbour arithmetic is mod 7. The torus is vertex-transitive — every cell is equivalent under the symmetry group — so there are no corners or edges and therefore no positional advantage from the board itself. Let G = 7.

3.2 Units and sides

Two sides, P ("blue", the host) and A ("coral", the guest). Each fields UNITS = 3 units.

Side	Unit start positions
`P`	`(0,2) (0,3) (0,4)`
`A`	`(6,2) (6,3) (6,4)`

Three neutral relay nodes sit at (3,1) (3,3) (3,5) — the vertical centre line, symmetric under the 180° rotation that swaps the two starts.

3.3 Orders

Each tick, a side submits one order per unit: a move and a stance.

move ∈ {H, N, S, E, W} where H = hold, and the four directions apply the offset (wrapping mod 7): N: (0,−1), S: (0,+1), E: (+1,0), W: (−1,0).
stance ∈ {0, 1, 2} = {Pierce, Shield, Sweep}.

The canonical serialisation of an orders array is canon(orders) = orders.map(o => o.move + o.stance).join(",") — e.g. "E0,S1,H2".

3.4 Intransitive combat

Stance combat is a symmetric cyclic (rock–paper–scissors) relation:

Pierce (0) beats Shield (1) beats Sweep (2) beats Pierce (0)
beats(a, b) ≡ (a + 1) mod 3 == b

This is a symmetric zero-sum game with no dominant strategy and a unique mixed equilibrium of ⅓ / ⅓ / ⅓. A player cannot be exploited on stance if they play uniformly at random, and cannot gain by deviating from it. The reference AI plays exactly this mixture (§9).

3.5 Tick resolution (deterministic)

Given the current state, both sides' orders, and a seed (§5), a tick resolves in fixed phases. The procedure is total (defined on all inputs) and integer-only (no floating point in any state-affecting computation), so it is bit-identical on every machine.

Intra-side movement. For each side independently: holding units claim their current cell; then moving units claim their target cell if unclaimed, otherwise they stay (a unit never displaces a same-side unit). This yields provisional positions.
Head-on swaps. If a P unit and an A unit would trade cells (each moving into the other's origin), both bounce back to their origins. Stance is logged for flavour but does not change the outcome.
Same-cell combat. If a P unit and an A unit occupy the same provisional cell, the stance relation decides the winner (ties → §5). The winner keeps the cell. A losing holder is pushed one cell along the attacker's approach vector if that cell is free, otherwise the assault is repelled and both return to origin. A losing mover retreats to its origin.
Separation. Any residual co-located pair — opposing or same-side, which can arise when a bounce/retreat lands on a now-occupied origin — is resolved deterministically: a seed byte decides which unit yields, and it relocates to the first free cell (preferring its origin, then von-Neumann neighbours, then a row-major scan). Each relocation lands on a globally free cell, so collisions strictly decrease; the loop is bounded (≤ 40 iterations, far above the worst case for 6 units on 49 cells). After this phase no two units share a cell — a machine-checked invariant (§12).
Relay control. Each relay is controlled this tick by the side solely occupying it. If both sides occupy it, control is decided by tie-break (§5).
Scoring. Each side gains +1 per relay it controls this tick.

3.6 Anti-snowball momentum

Let gap = |score_P − score_A|. Define an integer tier: 0 if gap ≤ 2, 1 if 3 ≤ gap ≤ 4, 2 if gap ≥ 5. When tier ≥ 1, the trailing side wins all stance ties and relay-contest ties (instead of the coin flip). Tiers are integers, not floats, to preserve exact determinism. This bounds runaway leads without ever making a deficit insurmountable or the tie-break exploitable (it is a public function of the public score).

3.7 Victory

A side wins immediately upon reaching TARGET = 10 control with a strictly greater score than the opponent.
If the match reaches MAXTICK = 40 ticks, the higher score wins (a tie resolves to P).
Additionally (protocol layer, §7): a side wins if the opponent forfeits by reveal-timeout, or is caught revealing inconsistently with their commitment.

4. Determinism guarantee

Every state-affecting quantity is an integer or a hash hex-string. Tie-breaks consume bytes from seed by index, never from any local clock or Math.random. Consequently:

Given identical (state, ordersP, ordersA, seed), resolveTick produces an identical next state on any conforming implementation.

This is what lets two mutually-distrusting clients run the game with no server and no authority: each computes the next state from the exchanged inputs and they cannot diverge. It is also what makes a match a portable, re-checkable artifact (§8).

5. Verifiable randomness

Per-turn nonces are 8 random bytes, hex-encoded (16 characters). For tick t with committed nonces nonce_P and nonce_A:

seed(t) = SHA-256( nonce_P ‖ nonce_A ‖ ":" ‖ t )      // 64 hex chars

Both parties learn both nonces only after both have committed, so neither can steer the seed: changing your nonce to bias one flip randomises all of them, and you are bound to your nonce by your commitment. Any tie within a tick draws the next byte:

byte_k = int16( seed[(2k mod 64) .. (2k mod 64)+2] );   winner = P if (byte_k & 1) else A

with k incrementing per tie decision within the tick. Anyone replaying the match can recompute the exact byte that decided any coin flip.

6. Commitment scheme

For a side's orders and its fresh nonce:

commit = SHA-256( canon(orders) ‖ "|" ‖ nonce )

Hiding: the commitment reveals nothing about the orders (preimage resistance). Binding: the side cannot later open the commitment to different orders (collision resistance). These two properties are the entire basis of simultaneity and cheat-detection.

7. The two-party protocol

Both peers run the same state machine; it is symmetric. The host controls P, the guest controls A. Messages:

{ t:"commit", tick, commit }                 // 64-hex commitment
{ t:"reveal", tick, orders, nonce }          // opening of the commitment
{ t:"chain",  tick, head }                   // this peer's chain head for a resolved tick

7.1 Per-tick sequence

Plan. The local player chooses orders for their own units.
Commit. Compute commit, store (orders, nonce, commit) locally, send commit.
Await. On receiving the peer's commit, store it. A reveal is sent only once both commitments exist — this is the point simultaneity is enforced.
Reveal. Send {reveal, orders, nonce}. Start the reveal-timeout (§7.7).
Verify. On the peer's reveal, check SHA-256(canon(orders) ‖ "|" ‖ nonce) == storedPeerCommit and that orders is structurally valid. Failure ends the match in the local player's favour (§7.6).
Resolve. With both openings known, compute seed(t), run resolveTick, append to the ledger (§8), advance the tick, and send {chain, head}.
Agree. On the peer's {chain}, compare its head to the local ledger's head for that tick and surface agreement/divergence. (Divergence is impossible between two honest clients by §4; the check exists to make any implementation bug or tampering visible.)

7.2 Seed and order mapping

Both peers derive identical inputs regardless of which side they are:

pOrders / aOrders  ← local vs peer, keyed by whether localSide == P
pNonce  / aNonce   ← likewise
seed = SHA-256( pNonce ‖ aNonce ‖ ":" ‖ t )     // P-nonce always first

7.3 Attacker model

The adversary is a player who fully controls their own client: they can read and modify their own memory, craft arbitrary messages, drop or delay their own messages, and inspect anything their client legitimately receives. They cannot break SHA-256 or predict the honest party's nonce. We analyse each attack.

7.4 Attacks eliminated by construction

Attack	Why it cannot work in KERNEL
Aimbot / input-timing exploit	There is no aim and no reaction window. Orders are simultaneous and committed before either is revealed.
Wallhack / maphack	No hidden state is streamed to the client ahead of time. Everything a client holds is either public or its own secret; reading its own memory yields nothing unfair.
RNG rigging	Every tie-break is a public function of both nonces and the tick, verifiable after the fact. One honest nonce suffices to keep it unbiased.
Meta-solving / dominant strategy	Stance combat has a unique ⅓ mixed equilibrium; there is no strategy to "solve" and no exploit on a uniform-random opponent.
Early-information reaction	A `reveal` is never emitted until both commitments are exchanged, so no side can condition its orders on the other's.

7.5 Tamper / replay

The ledger is a hash chain (§8). Altering any past order, nonce, seed, or state changes that tick's stateHash and every subsequent headHash, which fails re-verification. A recorded match cannot be edited undetectably.

7.6 Byzantine input hardening

A conforming client must not be crashable or foolable by a malicious peer. The reference controller enforces:

Wrong-tick messages are ignored.
Duplicate commits or reveals are ignored (a commitment cannot be changed after the fact; a reveal cannot be re-submitted).
Reveal-before-commit is ignored.
Malformed commitments (not a 64-char string) are ignored; malformed orders (wrong shape, illegal move/stance) end the match in the honest player's favour.
Any unexpected exception while handling a peer message is swallowed — a malicious peer can never crash the match.

These are exercised by a fuzz suite that injects garbage mid-match across hundreds of games (§12).

7.7 The one residual attack: aborting

Commit–reveal's sole unavoidable weakness in a two-party setting is a player who has seen that both sides are committed, computes that the tick will go against them, and refuses to reveal. This cannot be prevented without escrow or a third party. KERNEL penalises it deterministically:

Once both commitments are exchanged, a reveal-timeout starts. If the peer does not reveal in time, the honest player wins by forfeit.
Because refusing is strictly losing (forfeit ≥ whatever the bad tick would have cost), a rational player always reveals.

This is the theoretically correct handling for two-party trustless play, and it is real in the implementation, not stubbed.

8. Ledger and portable match proofs

8.1 Chain

Each resolved tick appends a record and extends a hash chain:

stateHash(t) = SHA-256( serialize(state_after_t) )
head(0)      = "genesis"
head(t)      = SHA-256( head(t−1) ‖ "|" ‖ pCommit ‖ "|" ‖ aCommit ‖ "|" ‖ seed(t) ‖ "|" ‖ stateHash(t) )
serialize(s) = JSON { t, P, A, c, sp, sa }   // tick, positions, control, scores

8.2 Proof format

A match exports to a self-describing JSON proof:

{
  "format": "KERNEL match proof v1",
  "params": { "G": 7, "UNITS": 3, "TARGET": 10, "MAXTICK": 40 },
  "genesis": "genesis",
  "result": { "winner": "P", "reason": "...", "scoreP": 10, "scoreA": 6, "ticks": 24 },
  "ticks": [
    { "tick": 1, "pOrders": [...], "aOrders": [...],
      "pNonce": "...", "aNonce": "...",
      "pCommit": "...", "aCommit": "...",
      "seed": "...", "stateHash": "...", "headHash": "..." }
  ],
  "headHash": "..."
}

8.3 Independent verification algorithm

Anyone — including a party who never played — can verify a proof with only a SHA-256 function and the rules above:

verify(proof):
    st ← initialState();  head ← proof.genesis;  expect ← 1
    for each e in proof.ticks:
        assert e.tick == expect
        assert validOrders(e.pOrders) and validOrders(e.aOrders)
        assert SHA-256(canon(e.pOrders) ‖ "|" ‖ e.pNonce) == e.pCommit
        assert SHA-256(canon(e.aOrders) ‖ "|" ‖ e.aNonce) == e.aCommit
        assert SHA-256(e.pNonce ‖ e.aNonce ‖ ":" ‖ st.tick) == e.seed
        resolveTick(st, e.pOrders, e.aOrders, e.seed)
        assert SHA-256(serialize(st)) == e.stateHash
        head ← SHA-256(head ‖ "|" ‖ e.pCommit ‖ "|" ‖ e.aCommit ‖ "|" ‖ e.seed ‖ "|" ‖ e.stateHash)
        assert head == e.headHash
        st.tick ← st.tick + 1;  expect ← expect + 1
    assert head == proof.headHash
    return VALID with final score (st.scoreP, st.scoreA)

Verification re-executes the game; it does not trust any stored positions or scores, only recomputes them. This makes fairness portable: a match is a cryptographic artifact any third party can check. The reference implementation ships this verifier in-app (menu → Verify a saved match proof).

9. Reference AI

The AI uses public board state only. It assigns its three units to the three relays via the minimum-total-distance assignment (brute-forcing the 3! = 6 permutations), lightly preferring relays it already holds, then steps each unit toward its target — spreading to contest all three relays. Its stance is drawn uniformly at random and is deliberately never "optimised": the ⅓ mixture is the unexploitable equilibrium, so a smarter stance policy could only make it worse (exploitable) or no better. The AI is therefore a strong positional opponent that remains mathematically fair.

10. Parameters and tuning

All of the following are constants near the top of the reference script and can be changed without touching the security machinery:

Constant	Meaning	Reference value
`G`	grid size (torus is `G × G`)	7
`UNITS`	units per side	3
`TARGET`	control needed to win	10
`MAXTICK`	tick cap	40
momentum tiers	gap→tier thresholds	`≤2→0, 3–4→1, ≥5→2`
reveal timeout	forfeit window (2-player)	45 s
relay layout	neutral node positions	`(3,1)(3,3)(3,5)`

Tuning these changes balance and feel — the design layer. None of them affects the security layer (commitment, verifiable seed, determinism, chain, forfeit), which holds for any parameter choice.

11. Limits and the server tier

This specification describes a fully trustless, serverless two-party game — the maximum that a single self-contained artifact can be. A production deployment would add infrastructure without changing the trust model, because clients never rely on a server for fairness:

Signaling / matchmaking. A lightweight server to exchange connection offers and pair players, replacing manual copy-paste connection. It sees only connection metadata, never game secrets.
Relay (TURN). For players behind restrictive NATs where direct peer-to-peer fails.
Optional notarised ledger. Peers may publish their agreed headHash per tick to a public log so disputes are adjudicable by anyone, and abandoned matches carry a public record. Still not trusted — merely a witness.
Ratings / anti-abort economics. Ladder systems can attach a rating penalty to forfeits, further disincentivising the one residual attack (§7.7).

None of these can make the game more fair than the cryptographic core already does; they improve reach, convenience, and dispute resolution.

12. Verification summary

The reference implementation was checked empirically, not just argued:

Resolver invariants — 8,000+ randomised games: zero crashes, zero opposing overlaps, zero same-side overlaps, zero off-board units; bit-identical determinism on repeated identical inputs; balanced win rates (~49/51) confirming board symmetry.
Protocol — two independent controllers wired through a message bus: 200 honest games stayed perfectly synchronised (0 desyncs, all ticks verified); deterministic replay reproduced the chain head exactly; a tampered reveal was caught with the honest side declared winner; a silent peer forfeited on timeout; both peers independently derived identical seeds and chain heads.
Portable proofs — honest matches export proofs that verify as authentic; tampering with orders, a state hash, the final chain head, or injecting a fabricated tick are each detected at the exact failing tick.
Byzantine hardening — hundreds of games with garbage/duplicate/out-of-order/malformed messages injected mid-match: the client never crashed and never resolved a tick against structurally-invalid opponent orders; an unopenable commitment resolves to a forfeit, not a hang.

KERNEL is an original design. This specification and the reference implementation are yours to own, rename, reskin, extend, or build a server tier around. The security properties in §7 hold for any parameter choice in §10.

FilesExpand file tree

SPECIFICATION.md

Latest commit

History