Germain Ring

How it fits together

A two-part challenge: a liveness signal from hand motion, and a proof of work whose output is a cryptographically useful prime. The verifier recomputes everything from the bundle, including the stimulus the human was chasing. Nothing is taken on trust from the prover.

What is different here

• The stimulus is a transcript, not a script. In the Pursuit task the target jumps four times, and jump k lands at a spot derived from SHA-256(challenge ‖ k ‖ trace-so-far). Nobody can know where it will land until it lands, because the landing spot depends on what the hand did up to that moment. A recorded trace is therefore unreplayable, a synthesised trace has to be synthesised online, and the verifier can regenerate the stimulus and check that every response came after it. This is Fiat–Shamir with a human in the loop.
• Reaction time from rest. The target stands still for 500 ms before each jump and 350 ms after. The hand settles, the jump becomes a step input, and the reaction time is the onset of motion from a quiet baseline. A response under 100 ms is not a human; it is a client that read the landing spot from memory.
• Lag-aligned residual. The pursuit lag is estimated by cross-correlating hand and target velocity. Subtract the lag-shifted target from the hand and look at what is left: a copy-with-delay bot leaves white noise, a hand leaves the smooth dynamics of a mass on a spring. The residual's lag-1 autocorrelation on a device-rate-independent grid must clear 0.5 and its RMS must exceed 1.5 px.
• Constant-speed target. The smooth path is reparametrised by arc length, so the target itself violates the two-thirds power law that hand movements obey (speed ∝ curvature^−⅓). The fitted exponent is reported, not gated, until it has been calibrated on real hands.
• Risk-adaptive work. Environment signals set the proof-of-work width. A human on an ordinary device gets the cheap tier; a suspicious client pays more. Every tier mints a safe-prime candidate.

1. Challenge

A 32-byte nonce. Here the page generates it; in deployment the server issues it with a timestamp and refuses stale or reused ones. Every later value is bound to it.

2. Trace

Pointer samples: elapsed ms as uint32, and x, y in canvas-centred coordinates quantised to ¼ px as int16. Canonical form "GRT2" ‖ task ‖ scale×4 ‖ n ‖ samples, where scale is the ring radius or the field size. Seed is SHA-256(challenge ‖ trace). The nonce supplies the unpredictability; the trace supplies the binding to a specific act of tracking.

3. Human gate

Pursuit: completed (8.5 s, four jumps), median tracking error ≤ 70 px, still moving in the 150 ms before each jump (a frozen transcript would let a client precompute the landing spot), pursuit lag between 60 and 600 ms, lag-aligned residual continuity, and reaction times with a 100 ms floor, a 900 ms median ceiling and arrival within 1.5 s. Ring: the earlier eight thresholds, three of which reject machines that are too good and two of which reject motion without inertia.

Try the simulations. In Pursuit, the reader copies the target exactly and fails on lag, residual and reaction time; the delayed copy adds 160 ms and white noise and fails on the residual; the filtered bot, a mass-on-a-spring model of a hand, passes. That is the frontier. Against a client that runs a good hand model in real time, the remaining defences are the environment score, the work, and, in deployment, a passkey assertion bound to the same challenge.

4. Environment

Collected on the client, so they are claims, not proof: trusted input events (synthesised DOM events are flagged), the automation flag, pointer type and contact pressure, input cadence (real devices cluster on a few intervals; synthetic streams are often uniformly random), frame rate. They feed a risk score that picks the work width. A bot can lie about all of it; what it cannot do is lie its way to a cheaper tier without also lying consistently with the trace, and the trace is verified.

5. Proof of work

Candidate i is SHA-256(seed ‖ i) masked to the chosen width, top bit set, then adjusted to p ≡ 5 (mod 6), the only residue class a Sophie Germain prime above 3 can occupy. The prover walks i = 0, 1, 2, … until both p and 2p+1 pass Miller–Rabin against the first twelve prime bases. The verifier needs only the index: it rederives the one candidate and runs the same two tests.

Expected trials follow the Hardy–Littlewood density for Sophie Germain primes, 2C₂ N / lnN ln2N, multiplied by six for the residue restriction. The search has a geometric tail, so a single hunt can land well above or below the figure.

6. Why Sophie Germain primes

Because the by-product is worth keeping. 2p+1 is a safe prime, which is exactly what a Diffie–Hellman or Schnorr group wants as its modulus: the group of order p has no small subgroups to leak into. A proof of work that mints safe-prime candidates is work someone might actually want done.

What the verifier checks

1. Challenge is 32 bytes of hex. (A server would also check it issued this one, recently, once.)
2. Trace decodes, and SHA-256(challenge ‖ trace) equals the claimed seed.
3. For Pursuit, the stimulus is regenerated from the challenge and the trace prefixes; the gate is recomputed against it. For Ring, the gate is recomputed from the trace.
4. Candidate at the claimed index and width equals the claimed p, and q = 2p+1.
5. p and q both pass Miller–Rabin.

Twelve fixed MR bases are deterministic below about 3.3 × 10²⁴; above that the error bound per composite is 4⁻¹². A production verifier would use random bases or BPSW.