Timed challenge-response and memory-occupation challenges

How it works

A timed challenge asks a device something it can answer correctly, within a deadline, only if it holds certain data locally or dedicates certain resources to the answer ^{1 3 5}. Three families of primitives exist:

• In timed attestation, as in SWATT, the verifier sends a random seed, and the device computes a checksum over its memory in a pseudorandom order ⁵. If memory has been altered, the extra work shows up as a detectable delay ⁵.
• In a proof of space, a prover shows that it dedicates "a significant amount of disk space as opposed to computation" ⁷. Constructions use graphs that are hard to pebble, and Merkle hash trees ⁷.
• Some proofs of secure erasure fill memory and then run timed rounds, accepting only answers that arrive within a round-trip bound ^{8 9}; see Memory wiping and proofs of secure erasure.

For AI facilities, the MIRI system overview describes two uses of memory challenges: "A) verifying presence of information B) verifying the absence of free memory/storage" ¹. Response time is the main evidence, because answering from another device is measurably slower ¹. The overview cites average NVMe read latencies of a few microseconds against about 100 ns for DRAM ¹. For the absence case, incompressible data is loaded until capacity is full, and random samples are challenged ¹.

Monfared et al. propose four GPU probes ³:

• memory-hard puzzles inspired by proof of work, which reveal parallel effort;
• verifiable-delay-function workloads, which measure sequential execution;
• matrix-multiplication timing, which reflects tensor-core performance;
• a VRAM-residency test.

In the residency test, a large challenge dataset is loaded into GPU memory ³. At random times, fresh challenges require keyed, memory-hard computation over it, and response times show whether it is still resident ³.

What it establishes

A capacity-filling challenge that is answered on time bounds how much free memory a device had at that moment ¹. Monfared et al. argue that timing variations can expose GPU engagement, complementing other accountability mechanisms ³; see Declared hardware is idle or shut down. The AI 2040 plan says memory-challenge verification "has the promise of potentially also not requiring a hardware retrofit, but seems likely to face some difficulties with verifying completeness" ².

A presence check does not show that nothing else is stored ¹. The overview notes that data could be pre-staged into local memory before a challenge, which only an unpredictable, capacity-filling challenge rules out ¹.

Threat model

• Known device. SWATT's verifier must know the device's clock speed, instruction set, memory architecture and expected memory contents ⁵.
• Cryptographic model. Proofs of space are proved secure in the random oracle model, with one additional mild assumption ⁷.
• Compromised stack. Monfared et al. consider host and GPU firmware that "may be modified, virtualized, or colluding" ³.
• No remote helpers. In data centres, remote memory access is the key helper to exclude ¹. Its round trips of about 1–2 µs compare with about 70–200 ns for local DRAM, and the overview says verification "depends on the ability to rule out RDMA, either via response latency or physical disconnection" ¹.

Limitations

• Broken embedded schemes. Castelluccia et al. implemented attacks based on a return-oriented rootkit and on code compression, together with specific attacks on SWATT and ICE-based schemes ⁶. They conclude that secure time-based attestation is "very difficult, if not impossible, to design correctly" ⁶. Perito and Tsudik cite such weaknesses as motivation for proofs of secure erasure ¹⁰.
• Coverage. Castelluccia et al. argue that "all memories (RAM, ROM, EEPROM) have to be attested" ⁶.
• Overhead. The VRAM-residency test "intentionally incurs substantial memory overhead" ³, and filling a pod's volatile memory takes tens of minutes ¹.
• Unquantified error rates. Monfared et al. do not define thresholds or statistical tests ³.