💻 computer science

PoSME: Proof of Sequential Memory Execution via Latency-Bound Pointer Chasing with Causal Hash Binding

The paper introduces PoSME, a cryptographic primitive that enforces strict sequential memory execution through latency-bound pointer chasing and symbiotic hash binding, effectively resisting time-memory trade-offs and ASIC advantages by leveraging DRAM latency rather than bandwidth to enable verifiable delay and Sybil resistance.

Original authors: David L. Condrey

Published 2026-04-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: David L. Condrey

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to prove to a friend that you spent a long, specific amount of time doing a very boring, repetitive task. You can't just say, "I did it," because they can't see you. You need a Proof of Sequential Memory Execution (PoSME).

Think of PoSME not as a math puzzle, but as a giant, living maze that changes every time you take a step.

Here is the breakdown of how it works, using simple analogies:

1. The Setup: A Giant, Shifting Maze

Imagine a massive warehouse (the "Arena") filled with millions of lockers.

The Old Way (Static Puzzles): Most previous systems were like a static maze. You could memorize the whole map, or if you forgot a part, you could just look it up in a book. If you had a super-fast computer (an ASIC), you could solve it instantly.
The PoSME Way (Mutable Arena): In PoSME, the maze is alive. Every time you open a locker, you don't just read what's inside; you change it. You write a new note inside, and that new note changes the map for the next step.

2. The Rules: The "Pointer Chase"

You are given a starting key (a seed). To prove you did the work, you have to follow a strict set of rules for thousands of steps:

Look: You look at the note in your current locker.
Decide: The note tells you exactly which other locker to go to next. You can't skip ahead; you must go to the specific locker the note points to.
Change: You go to that new locker, read what's there, and then rewrite the note inside it based on what you just read.
Chain: You take a tiny piece of the new note and attach it to your "receipt" (the transcript).

Because the next locker depends entirely on what you just read, you cannot do this in parallel. You can't have 1,000 people working on different parts of the maze at the same time. You have to do it one step at a time, in order.

3. The "Symbiotic" Lock

Here is the clever part: The note you write isn't just random text. It's a two-part lock.

Part A is the Data (what you read).
Part B is the Causal Hash (a receipt proving when and how you wrote it).

These two are "symbiotic," meaning they are glued together. You cannot fake the data without the receipt, and you cannot fake the receipt without the data. If an attacker tries to skip a step and just guess the final answer, the "receipt" won't match the "data," and the whole chain breaks.

4. Why Computers Can't Cheat (The "Latency" Trap)

This is the most important part. Why can't a super-fast computer (like a GPU or a custom chip) solve this quickly?

The Bottleneck: The problem isn't how fast you can think (calculate); it's how fast you can run to the locker.
The Analogy: Imagine you are in a library. The librarian (the computer) is incredibly fast at reading books. But the books are scattered across a massive campus.
- Old Systems: The books were all on one shelf. The librarian could read them instantly.
- PoSME: The books are scattered randomly across a huge campus. Every time the librarian needs a book, they have to physically run to a random building, find the right room, and open the door.
The Physics Limit: The speed of light and the physical distance in the computer's memory (RAM) create a hard limit. Even if your brain is 1,000x faster, you still have to wait for the signal to travel to the memory chip and back. This is called Latency.
The Result: A super-fast GPU is actually slower at this than a normal laptop. Why? Because GPUs are like a swarm of 10,000 ants trying to run to the library at once. They get in each other's way, and the library doors can only open one at a time. A single, steady human (a CPU) is actually more efficient at this specific "run-and-fetch" task.

5. The "Time Travel" Problem (Why You Can't Cheat by Deleting Data)

An attacker might think: "I'll just delete some lockers to save space, and if I need one later, I'll just re-calculate it."

The Catch: Because the maze changes every step, if you delete a locker, you can't just re-calculate it. You have to re-do all the steps that led to that locker, because every step changed the previous ones.
The Penalty: If you try to save space by deleting data, the time it takes to re-calculate the missing pieces grows exponentially. It's like trying to un-bake a cake; you can't just take out the flour, you have to bake the whole cake again from scratch.

Summary: Why Does This Matter?

PoSME is a new tool for the digital world that solves three big problems at once:

It proves time: You can't fake the time it took to do the work because the "running to the locker" part is physically limited by the speed of memory chips.
It stops cheating: It makes it impossible for powerful super-computers (ASICs) to cheat and solve the puzzle faster than a normal person.
It proves ownership: It proves that someone actually did the work sequentially, step-by-step, without needing a trusted third party to watch them.

In a nutshell: PoSME turns a computer into a "time machine" that forces you to walk a long, winding path where every step changes the path behind you. You can't fly over it, you can't teleport, and you can't do it faster than the speed of light allows.

1. Problem Statement

Existing cryptographic primitives for proving sequential work suffer from specific limitations that prevent them from simultaneously satisfying three critical requirements: sequential time enforcement, memory hardness, and ASIC resistance.

Verifiable Delay Functions (VDFs): Prove time but are insensitive to memory; ASICs can accelerate them via faster Arithmetic Logic Units (ALUs).
Proofs of Space (PoS/PoSW): Prove storage over static graphs but do not enforce sustained sequential computation or mutable state.
Memory-Hard Functions (MHFs): Like Argon2id, they increase cost via memory pressure but are "single-shot" primitives without a chain-proof system, offering only 8–16× ASIC resistance.
The Gap: There is no primitive that enforces sustained sequential computation over a mutable state, resists Time-Memory Trade-Off (TMTO) attacks effectively, and is bounded by DRAM latency rather than bandwidth or compute power.

2. Methodology: The PoSME Construction

The authors propose PoSME, a cryptographic primitive that enforces sequential execution through a mutable arena and data-dependent pointer chasing.

Core Design Principles

Mutable Arena State: Unlike static graphs, the memory arena evolves at every step. Recomputing an evicted block requires replaying its entire write chain, making storage essential.
Data-Dependent Pointer Chasing: The address of the next read is determined by the hash of the current read's output. This creates a strict sequential chain that cannot be parallelized.
Symbiotic Causal Binding: Every write operation binds the new data value and a "causal hash" (representing write history) together. Neither can be fabricated without the other, doubling the recomputation cost on cache misses.

Technical Architecture

Arena Structure: The memory is mapped to a Boolean hypercube of dimension $d_{hc}$ ( $N = 2^{d_{hc}}$ blocks).
Step Function:
- The prover performs $d$ sequential reads where the address $v_{j+1}$ depends on the hash of the previous read's data and causal hash.
- A write operation occurs at a derived coordinate, updating the block's data and causal hash symbiotically.
- A global transcript is updated with a causal hash of the step.
Initialization: The arena is initialized deterministically from a seed $s$ using a skip-link DAG (binary tree structure) to ensure a known termination condition for recomputation.
Verification Modes:
- Classical: Uses Fiat-Shamir sampled Merkle proofs. Proof size scales with recursion depth ( $R$ ) and challenge count ( $Q$ ).
- IVC (Incrementally Verifiable Computation): Utilizes Binius (a binary-field succinct argument system) to fold the proof of step $t$ into step $t-1$ . This achieves $O(1)$ proof size (constant kilobytes) regardless of the number of steps $K$ , without requiring a trusted setup.

3. Key Contributions

A. Formal Security Proofs

Space-Time Lower Bound: The authors prove a formal lower bound of $S \cdot T = \Omega(K^2)$ for dynamic causal DAGs. This means an adversary reducing storage ( $S$ ) must pay a quadratic penalty in computation time ( $T$ ).
Temporal Staleness: A novel proof (Theorem 4) showing that even if an adversary stores a large fraction of the arena, the historical state required for recomputation becomes "stale" due to random writes. This eliminates the "critical threshold" found in static graph proofs, ensuring exponential recomputation costs even for high storage fractions (e.g., 95% storage still incurs massive penalties).
Adaptive Resistance: The security holds even against adaptive adversaries who choose storage sets dynamically based on prior outputs, as the Random Oracle Model (ROM) ensures read addresses remain uniform and unpredictable.

B. Hardware Resistance Analysis

Latency-Bound: The bottleneck is DRAM random-access latency (40–50 ns), not hash computation (< 3.5% of cost) or bandwidth.
TMTO Resistance: At a write density $\rho=4$ , the system offers 10× resistance to time-memory trade-offs.
ASIC Bound: The theoretical advantage for custom ASICs is limited to ~2× (determined by DRAM physics), compared to 8–16× for bandwidth-bound functions like Argon2id.

C. Empirical Validation

Platform Benchmarks: Tested across 17 CPU platforms and 4 GPU architectures (including NVIDIA H100).
GPU Inefficiency: GPUs are 14–19× slower than consumer CPUs for this workload. This is because GPUs are optimized for parallel throughput, whereas PoSME is strictly sequential and latency-bound.
Capacity Choke: While GPUs have high bandwidth, they are limited by VRAM capacity. Running many parallel instances is infeasible because each requires a unique 1 GiB arena, choking the attack on capacity rather than bandwidth.

4. Results

Metric	Result	Significance
Sequential Steps	$\Omega(K)$	Enforced via pointer chasing; no parallelization possible.
TMTO Resistance	10× (at $\rho=4$ )	Adversaries cannot trade storage for speed effectively.
ASIC Advantage	~2×	Limited by DRAM latency, not ALU speed.
GPU vs. CPU	14–19× Slower	Consumer CPUs outperform high-end GPUs (H100/A100).
Proof Size	$O(1)$ (IVC mode)	Constant size (few KB) via Binius folding; no trusted setup.
Hash Overhead	< 3.5%	Computation is dominated by memory access latency.
ROM Uniformity	$\chi^2/df \approx 1.0004$	Empirically validated address distribution matches theoretical uniformity.

5. Significance and Applications

Fills a Critical Gap: PoSME is the first primitive to simultaneously offer sequentiality, memory hardness, and mutable state, making it suitable for applications where existing primitives fail.
Sybil Resistance & Authorship Attestation: Because GPUs and ASICs cannot significantly accelerate the process, PoSME ensures that "proof of work" is performed by general-purpose hardware, preventing centralized mining farms from dominating.
Verifiable Delay: While PoSME proves sequential steps, it can be combined with a standard VDF or Trusted Execution Environments (TEEs) to create a robust Verifiable Delay Function (VDF) with economic guarantees against acceleration.
Future-Proofing: The latency-bound nature makes PoSME resilient to future bandwidth improvements, as the bottleneck is the physical speed of light in DRAM (latency), which has improved very slowly compared to bandwidth.

Conclusion

PoSME represents a paradigm shift in sequential proof systems. By leveraging mutable state, symbiotic causal binding, and latency-bound pointer chasing, it achieves a level of ASIC resistance and TMTO security previously unattainable. The empirical demonstration that consumer CPUs outperform massive GPU clusters challenges the assumption that parallel hardware is always superior for cryptographic work, offering a robust foundation for decentralized consensus, verifiable delays, and anti-Sybil mechanisms.