Proof of Sequential Memory Execution (PoSME)

1.1.1. Proofs of Sequential Work

PoSW [CohenPietrzak2018] proves traversal of a depth-robust graph via Fiat-Shamir-sampled Merkle proofs. PoSME differs: the graph is a mutable arena (not a static DAG), the access pattern is data-dependent (not fixed), and each node carries a causal hash binding its value to its full write history.¶

1.1.2. Memory-Hard Functions

Functions like Argon2id and scrypt resist ASIC acceleration by imposing high memory requirements. Argon2id [RFC9106] resists TMTO via memory-hardness [Boneh2016], with a single-pass TMTO penalty of approximately 2x. PoSME uses a custom logarithmic skip-link initialization (Section 3.2) to ensure Omega(sqrt(N)) space-hardness from the first step. The ongoing computation uses pointer-chasing with in-place writes, creating a latency-bound bottleneck. PoSME's TMTO penalty is $1 + 2\rho(1-\alpha)^2/\alpha$ for an adversary storing $\alpha N$ blocks, where $\rho = K/N$ is the write density.¶

1.1.3. Proofs of Space-Time

Proofs of Space-Time (PoST) [Chia2024] [Spacemesh2023] enforce both sequential time and persistent storage by requiring a Prover to repeatedly prove possession of stored data over a sequence of time intervals. PoST operates over a static graph: the stored data does not change between proofs, and the graph structure is fixed before execution. PoSME differs in that the arena is mutable (each step modifies it), the access pattern is data- dependent (addresses are determined by arena contents, not pre-computed), and each block carries a causal hash binding its current value to its write history. These differences make PoSME a different construction with different TMTO characteristics, not a strict improvement over PoST.¶

1.1.4. Cumulative Memory Complexity

Alwen, Blocki, and Pietrzak [AlwenBlockPietrzak2017] formalized cumulative memory complexity for static graph pebbling games. PoSME's causal dependency DAG is dynamic (edges are created during execution), requiring a new pebbling framework. The dynamic pebbling analysis is provided in Section 5.4.¶

3.3.1. Intra-Step Bank Collisions

Standard memory controllers achieve high bandwidth by interleaving sequential reads across multiple hardware banks, keeping multiple row-buffers open. PoSME explicitly defeats this optimization to enforce a strict latency floor.¶

The force_bank_mapping(raw_a, bank_id, params) function modifies the specific bits of the logical address raw_a that the memory controller uses for bank selection, replacing them with bank_id.¶

By forcing all $d$ reads and the final write to target the same physical bank but different pseudo-random rows, the memory controller suffers a "Bank Conflict" on every access. This forces a physical Row Precharge ($t_{RP}$) and RAS-to-CAS Delay ($t_{RCD}$) penalty for every hop, anchoring the execution time to the thermodynamic limits of the DRAM capacitor rather than the logic speed of the processor.¶

3.3.2. Spatial Neighborhood Entanglement

The write step cryptographically binds the updated block to the current state of its logical neighbors, A[w-1] and A[w+1].¶

This transforms the Time-Memory Trade-Off (TMTO) penalty from a self-contained write chain into a spatial cascade. If an adversary discards a subset of the arena, recomputing a single missing block $w$ requires knowing the causal hashes of its neighbors at the exact moment of the write. If those neighbors were also discarded, the recomputation propagates outward: $w-1 \to w-2 \to \cdots$ and $w+1 \to w+2 \to \cdots$, until reaching stored blocks on each side. For an adversary storing $\alpha N$ blocks, the expected cascade width is $2(1-\alpha)/\alpha$, and each block costs $\rho$ hash evaluations to replay (see Theorem 3, Section 5.4.3). This cascade is sequential (Theorem 4, Section 5.4.4), adding directly to the adversary's critical path.¶

3.3.3. Timing Entropy Attestation

Because commodity DRAM requires periodic electrical refresh cycles ($t_{REFW}$), a genuine physical execution will exhibit unavoidable, stochastic latency spikes.¶

The Prover measures the execution time of the read/write loop using a monotonic, high-resolution hardware counter (e.g., the RDTSC instruction on x86 architectures). This inter-arrival time, delta_t, is folded directly into the transcript $T_t$. A Verifier auditing the transcript can perform statistical variance testing on the distribution of delta_t values. An ASIC attempting to simulate execution entirely within ultra-fast, deterministic SRAM will lack this specific jitter profile, allowing the Verifier to reject perfectly clean transcripts as physically impossible.¶

3.3.4. Transcript Chain

The transcript chain T_t binds all steps causally:¶

T_t = H(T_{t-1} || I2OSP(t, 4) || cursor || root_t)

T_t incorporates root_t (the Merkle root after the write) and cursor (which depends on the arena state at step t). Computing T_t requires computing all prior steps.¶

5.4.1. Sequential Floor

The transcript chain T_0 through T_K must be computed sequentially to produce T_K before Fiat-Shamir challenges are derived. This is an $\Omega(K)$ lower bound regardless of storage.¶

5.4.2. Spatial Cascade TMTO

Each step writes 1 block at a uniformly random address (Theorem 2). After $K$ steps with write density $\rho = K/N$, each block has been written $\rho$ times on average. Because each write is bound to its spatial neighbors' causal hashes, missing blocks cannot be recomputed in isolation.¶

Theorem 3 (Section 5.4.3) establishes the TMTO ratio:¶

TMTO(alpha) = 1 + 2*rho*(1-alpha)^2 / alpha

K MUST be at least N ($\rho \ge 1$) for meaningful TMTO resistance. Values of $\rho \ge 4$ are RECOMMENDED.¶

5.4.3. Per-Step Recomputation Cost

Theorem 2 (Address Uniformity). In the random oracle model, the addresses $a_{t,j} = \text{XOF}(\text{cursor}_t, j) \bmod N$ used for pointer-chase reads satisfy:¶

1. Independence. For distinct pairs $(t_1, j_1) \ne (t_2, j_2)$, the addresses $a_{t_1,j_1}$ and $a_{t_2,j_2}$ are pairwise independent, except with probability at most $\binom{Kd}{2} / 2^{257}$ (birthday bound on cursor collisions in the 256-bit hash space).¶

2. Uniformity. Each address $a_{t,j}$ has statistical distance at most $N / 2^{64}$ from the uniform distribution over $[0, N)$. For $N \le 2^{48}$, this bound is at most $2^{-16}$.¶

Consequently, for any adversary subset of stored blocks of size $\alpha \cdot N$, a random read misses the stored set with probability $(1 - \alpha) \pm N/2^{64}$.¶

Proof. In the random oracle model, $H$ maps distinct inputs to independent, uniformly random 256-bit outputs. Define $X_{t,j} = H(\text{cursor}t | \text{I2OSP}(j, 4))$. The inputs are distinct across $j$ (for fixed $t$) by the index suffix, and across $t$ (for any $j$) whenever $\text{cursor}_t \ne \text{cursor}{t'}$. Since $\text{cursor}t = H(\text{cursor}{t-1} | \cdots)$ is itself a hash output, cursor collision probability across all $K$ steps is at most $\binom{K}{2} / 2^{256}$, which is negligible. Given distinct inputs, the outputs $X_{t,j}$ are independent uniform 256-bit strings, establishing claim (1).¶

For claim (2): XOF truncates $X_{t,j}$ to its first 8 bytes, yielding a uniform value $U$ in $[0, 2^{64})$. The address is $U \bmod N$. The number of integers in $[0, 2^{64})$ mapping to any particular residue $r \in [0, N)$ is either $\lfloor 2^{64}/N \rfloor$ or $\lceil 2^{64}/N \rceil$. The maximum deviation from the ideal probability $1/N$ is at most $1/2^{64}$, giving statistical distance at most $N/2^{64}$ over the full distribution. For $N \le 2^{48}$, this is at most $2^{-16}$, which is negligible for all recommended profiles.¶

Theorem 3 (Spatial Cascade TMTO). In the random oracle model, under Theorem 2, consider an adversary that maintains $\alpha \cdot N$ arena blocks in working memory ($0 < \alpha < 1$) and stores all $K$ transcript values. The adversary's expected computation per step is:¶

C_step >= d * (1 + (1-alpha) * 2*rho / alpha)

where $\rho = K/N$ is the write density.¶

Proof. The proof proceeds in three parts.¶

Part 1: Write chain cost. When a read at step $t$ targets a block $w$ not in the adversary's working memory, the adversary must reconstruct $w$'s current state. Block $w$ was written $\rho$ times on average (each of $K$ steps writes to a uniformly random block by Theorem 2). The adversary knows the cursor at every step (stored), so replaying one write requires one hash evaluation given the block's previous state and the cursor. Tracing $w$'s temporal write chain from initialization to the current epoch costs $\rho$ hash evaluations.¶

Part 2: Spatial cascade. Each write to block $w$ at step $t'$ depends on the causal hashes of $A[w-1]$ and $A[w+1]$ at time $t'$ (Section 3.3.2). These are historical states: the causal hash of $w$'s neighbor at the moment $w$ was written, not the neighbor's current state. Even if $w-1$ is currently in the adversary's working memory, its state at time $t'$ is not recoverable from its current state (hash chains are irreversible). Therefore, to replay $w$'s write chain, the adversary must also replay the full temporal chain of $w-1$ (so that $w-1$'s state at each of $w$'s write times is available).¶

Block $w-1$'s temporal chain depends on $w-2$'s historical causal hashes (its own spatial neighbor). If $w-2$ is not stored, this cascades further: $w-2 \to w-3 \to \cdots$. The cascade extends outward in one direction until reaching a block that is in the adversary's working memory; that block's full temporal chain is available (the adversary maintains it by construction).¶

The same cascade extends in the opposite direction: $w+1 \to w+2 \to \cdots$. The cascade width in each direction follows a geometric distribution with success probability $\alpha$ (each successive neighbor is stored with probability $\alpha$, independently by Theorem 2's uniformity guarantee on write addresses). The expected cascade width in one direction is $(1-\alpha)/\alpha$. For all recommended profiles ($N \ge 2^{20}$), this is negligible relative to $N$ for any $\alpha > 2^{-19}$; ring wrap-around does not affect the bound in practice. Each block in the cascade requires $\rho$ hash evaluations to replay its temporal chain.¶

Part 3: Expected per-step cost. At each of the $K$ steps, the Prover makes $d$ reads. Each read targets a uniformly random block, which is absent from the adversary's working memory with probability $(1-\alpha)$. Each miss triggers a spatial cascade of expected total width $2(1-\alpha)/\alpha$ blocks, each costing $\rho$ hash evaluations.¶

The expected computation per step is:¶

C_step = d + d*(1-alpha) * (2*(1-alpha)/alpha) * rho
       = d * (1 + 2*rho*(1-alpha)^2 / alpha)

For $(1-\alpha) \approx 1$ (small $\alpha$), this simplifies to $d \cdot (1 + 2\rho/\alpha)$. The TMTO ratio (adversary cost divided by honest cost $d$) is:¶

TMTO(alpha) = 1 + 2*rho*(1-alpha)^2 / alpha

For $\alpha < 1/(2\rho)$, the TMTO ratio exceeds $2\rho^2$, making space reduction more expensive than honest execution with full storage.¶

5.4.4. Sequential Cascade Latency

Theorem 4 (Sequential Cascade Latency). The spatial cascade of Theorem 3 adds to the adversary's sequential critical path. An adversary resolving a cascade of width $L$ blocks incurs at least $L \cdot \rho$ sequential hash evaluations that cannot be parallelized.¶

Proof. To replay block $w$'s temporal chain, the adversary needs the causal hashes of $w-1$ at each of $w$'s write times. These causal hashes are outputs of $w-1$'s own temporal chain. Therefore, $w-1$'s full temporal chain ($\rho$ sequential hash evaluations) must complete before $w$'s chain can begin. By the same argument, $w-2$'s chain must complete before $w-1$'s, and so on. For a cascade of width $L$ blocks, the critical path is $L$ sequential temporal chains of $\rho$ links each, totaling $L \cdot \rho$ sequential hash evaluations. Parallel hardware does not reduce this latency because each chain link depends on the output of the previous link (hash chaining) and the completion of the adjacent block's chain (spatial dependency).¶

This result is significant because it means spatial entanglement converts a work penalty into a latency penalty: the adversary not only performs more total computation but takes more wall-clock time, directly undermining the sequential execution guarantee.¶

5.4.5. Checkpoint Dominance

Theorem 5 (Checkpoint Dominance). Under spatial entanglement, partial-arena checkpoints are strictly suboptimal. For any adversary using checkpoints of $\alpha \cdot N$ blocks ($\alpha < 1$) at interval $C$ steps, the space-time product $S \times T$ satisfies:¶

S * T >= (2*rho*(1-alpha) + alpha) * S_full * T_full

where $S_{full} \times T_{full}$ is the space-time product for full-arena checkpoints. For $\rho \ge 1$, this exceeds $S_{full} \times T_{full}$, with the gap increasing linearly in $\rho$.¶

Proof. A full-checkpoint adversary stores all $N$ blocks at interval $C$, giving storage $S_{full} = (K/C) \cdot N \cdot B$ and replay cost $T_{full} = Q \cdot C \cdot d / 2$ per proof generation. The product $S_{full} \cdot T_{full}$ is independent of $C$ (the standard time-space tradeoff).¶

A partial-checkpoint adversary stores $\alpha N$ blocks at interval $C$. Storage: $S = \alpha \cdot S_{full}(C)$. When replaying from a partial checkpoint, each of the $C/2$ replayed steps incurs spatial cascade overhead per Theorem 3. Replay cost per challenge: $T = T_{full}(C) \cdot (1 + 2\rho(1-\alpha)/\alpha)$.¶

The product:¶

S * T = alpha * S_full * T_full * (1 + 2*rho*(1-alpha)/alpha)
      = S_full * T_full * (alpha + 2*rho*(1-alpha))
      = S_full * T_full * (2*rho + alpha*(1 - 2*rho))

For $\rho \ge 1$: the coefficient $(1 - 2\rho) \le -1$, so the product is minimized at $\alpha = 1$ (full checkpoints), where it equals $S_{full} \times T_{full}$. Any $\alpha < 1$ strictly increases the product. For $\alpha \to 0$, the ratio approaches $2\rho$, meaning the adversary's space-time product is $2\rho$ times worse than with full checkpoints.¶

Corollary. Spatial entanglement forces the adversary into an all-or-nothing checkpointing strategy: either store the complete arena at each checkpoint or forgo checkpointing entirely. There is no useful middle ground.¶

5.4.6. Dynamic Pebbling Game

PoSME's causal DAG is dynamic: edges are created during execution based on data-dependent addressing. In the random oracle model (Theorem 2), each step creates d edges to uniformly random targets. The pebbling game is:¶

1. N block nodes (arena) and K step nodes.¶

2. At step t, the game reveals d random read addresses.¶

3. To execute step t, the adversary must have pebbles on all d read addresses and on the write target's spatial neighbors (stored or recomputed via spatial cascade).¶

4. The adversary maintains auxiliary state (cursors, write index) of at most K * 32 bytes.¶

Without spatial entanglement, the per-miss recomputation cost is $\rho$ (linear write chain), giving a TMTO ratio of $1 + (1-\alpha) \cdot (2\rho + 1)$. With spatial entanglement, Theorem 3 establishes the tighter bound $1 + 2\rho(1-\alpha)^2/\alpha$, and Theorem 4 proves this overhead is sequential (cannot be parallelized). Theorem 5 further shows that partial-arena checkpoints are strictly dominated by full-arena checkpoints.¶

5.5.1. Wafer-Scale Threshold

The ultimate latency floor for an adversary is on-die signal propagation. Optimal ASIC designs that integrate massive SRAM (1-5ns access) could achieve a 10-45x advantage over commodity DDR5. Wafer-scale integration, as demonstrated by the Cerebras Wafer-Scale Engine, is the existence proof for this threshold. PoSME's security is durable because spatial entanglement (Theorem 3) imposes a TMTO recomputation penalty that scales as $1/\alpha$, ensuring that any latency-based speedup is countered by the prohibitive cost of discarding state. Furthermore, the cascade latency (Theorem 4) is sequential, so the adversary cannot hide recomputation behind parallelism.¶

7.2.1. Design Trade-off: N vs rho

Arena size N and write density rho = K/N are independent knobs controlling different security properties:¶

• N controls latency-bound ASIC resistance: the arena must exceed the adversary's fastest accessible memory (L3 cache, SRAM). Larger N requires more Prover RAM.¶

• rho controls TMTO resistance: penalty = 1 + 2*rho*(1-alpha)^2/alpha for an adversary storing alpha*N blocks (Theorem 3). Higher rho requires more steps (longer wall time) but no additional RAM.¶

7.2.2. Parameter Profiles

Three profiles are defined. All profiles share fixed parameters: block size B = 64 bytes, reads per step d = 8, bank count B_banks = 16, hash function H = BLAKE3.¶

The Standard and Enhanced profiles exceed consumer L3 caches (16-36 MiB as of 2024) and provide latency-bound ASIC resistance via arena size and HBM latency bounds. The Maximum profile (1 GiB) exceeds all current L3 caches and limits GPU throughput via the capacity-bandwidth bound.¶

7.2.3. Memory Budget

The Prover's peak memory comprises three components:¶

The root chain is written sequentially during pass 1 and read sequentially during pass 2. Implementations MAY stream the root chain to persistent storage to reduce peak RAM by K * 32 bytes, at the cost of additional I/O.¶

Peak RAM by profile (with root chain streaming):¶