Proof of Sequential Memory Execution (PoSME)

1.1. Related Work

3.1. Arena Block Format

Each arena block is a pair:¶

block = {
    data:   bytes[32],
    causal: bytes[32]
}

The data field stores the block's computational value. The causal field stores the causal hash chain: a running digest binding the block's current value to the cursor of the step that last wrote it.¶

3.2. Arena Initialization

The arena is initialized deterministically from a public seed s:¶

for i in 0..N-1:
    if i == 0:
        A[0].data = H("PoSME-init-v1" || s || I2OSP(0, 4))
    else:
        A[i].data = H("PoSME-init-v1" || s || I2OSP(i, 4)
                      || A[i-1].data
                      || A[floor(i/2)].data)
    A[i].causal = H("PoSME-causal-v1" || s || I2OSP(i, 4))

root_0 = MerkleRoot(A)
T_0 = H("PoSME-transcript-v1" || s || root_0)

The initialization references both the preceding block (A[i-1]) and a logarithmic skip-link (A[floor(i/2)]). This creates a dependency DAG of depth log(N) and width N, requiring Omega(sqrt(N)) space to evaluate (the DAG cannot be streamed in constant space because each block depends on a block approximately N/2 positions behind it). A custom initialization is used rather than Argon2id because Argon2id's fixed internal graph does not provide this skip-link structure; the logarithmic back-references are necessary for the space-hardness property.¶

The Verifier can independently compute root_0 and T_0 from the seed, providing a trusted anchor for all subsequent verification.¶

3.3. Step Function

The step function is the core of PoSME. It enforces sequentiality via pointer-chasing, hardware parity via forced intra-step bank collisions, and geometric TMTO resistance via spatial neighborhood entanglement.¶

At each step t in {1, ..., K}:¶

STEP(t):
    cursor = T_{t-1}

    // 1. Determine Target Bank
    // Use the first 4 bytes of XOF to select 1 of B_banks
    bank_id = OS2IP(XOF(cursor, 0)) mod params.B_banks

    // Start high-resolution cycle counter
    t_start = RDTSC()

    // 2. Intra-Step Bank Collision Reads
    addrs = []
    for j in 0..d-1:
        // Generate pseudo-random address
        raw_a = OS2IP(XOF(cursor, j + 1)) mod params.N

        // Mutate raw_a to ensure it maps to bank_id
        a = force_bank_mapping(raw_a, bank_id, params)
        addrs.append(a)

        val = A[a]
        cursor = H(cursor || val.data || val.causal)

    // 3. Write with Spatial Neighborhood Entanglement
    raw_w = OS2IP(XOF(cursor, d + 1)) mod params.N
    w = force_bank_mapping(raw_w, bank_id, params)
    old = A[w]

    // Incorporate causal hashes of logical neighbors
    n_prev = A[(w - 1) mod params.N].causal
    n_next = A[(w + 1) mod params.N].causal

    new_data = H(old.data || cursor || old.causal
                  || n_prev || n_next)
    new_causal = H(old.causal || cursor || I2OSP(t, 4)
                    || n_prev || n_next)
    A[w] = {data: new_data, causal: new_causal}

    // Stop cycle counter to capture physical latency jitter
    t_end = RDTSC()
    delta_t = t_end - t_start

    // 4. Update Commitments
    root_t = MerkleUpdate(root_{t-1}, w, A[w])
    T_t = H(T_{t-1} || I2OSP(t, 4) || cursor || root_t || I2OSP(delta_t, 8))

    // 5. Log step for Prover transcript
    log[t] = {addrs, w, old, A[w], cursor, root_t, delta_t}

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

3.4. Root Chain Commitment

The Prover commits to the sequence of ALL K arena roots:¶

R = [root_0, root_1, ..., root_K]
C_roots = MerkleRoot(R)

This root chain commitment binds the Prover to a specific sequence of arena states BEFORE Fiat-Shamir challenges are derived. The challenges depend on (T_K, C_roots), and both must be fixed before the Prover knows which steps will be challenged.¶

3.5. Proof Generation

PROVE(K, Q, R_depth):
    C_roots = MerkleRoot([root_0, ..., root_K])
    challenges = FS(T_K, C_roots, Q)
    proof = {params, T_K, C_roots, step_proofs: []}

    for c in challenges:
        sp = make_step_proof(c, R_depth)
        proof.step_proofs.append(sp)
    return proof

make_step_proof(step, depth):
    sp = {
        step_id: step,
        cursor_in: T_{step-1},
        cursor_out: log[step].cursor,
        root_before: root_{step-1},
        root_after: log[step].root_t,
        root_chain_paths: [
            MerklePath(C_roots, step-1),
            MerklePath(C_roots, step)
        ],
        reads: [],
        write: {addr, old, new,
                merkle_path: MerklePath(root_{step-1}, w)},
        writers: []
    }
    for j in 0..d-1:
        sp.reads.append({
            addr, block, merkle_path:
                MerklePath(root_{step-1}, addr)})
        if depth > 0:
            ws = last_writer(addr, step)
            if ws == 0:
                sp.writers.append({type: "init",
                    init_path: MerklePath(root_0, addr)})
            else:
                sp.writers.append({type: "step",
                    proof: make_step_proof(ws, depth-1)})
        else:
            sp.writers.append({type: "leaf",
                writer_step: last_writer(addr, step),
                merkle_path: MerklePath(
                    root_{ws}, addr)})
    return sp

4.1. Verification Procedure

The Verifier receives (seed, params, T_K, C_roots, proof):¶

VERIFY(seed, params, T_K, C_roots, proof):
    // 1. Trusted anchor
    root_0 = compute_init_root(seed, params.N)
    T_0 = H("PoSME-transcript-v1" || seed || root_0)

    // 2. Verify root_0 in root chain
    assert MerkleVerify(C_roots, 0, root_0,
                        proof.root_0_path)

    // 3. Recompute challenges
    challenges = FS(T_K, C_roots, params.Q)

    // 4. Verify each challenged step
    for sp in proof.step_proofs:
        verify_step(sp, C_roots, root_0, params)

verify_step(sp, C_roots, root_0, params):
    // A. Verify roots are in the root chain
    assert MerkleVerify(C_roots, sp.step_id - 1,
                        sp.root_before,
                        sp.root_chain_paths[0])
    assert MerkleVerify(C_roots, sp.step_id,
                        sp.root_after,
                        sp.root_chain_paths[1])

    // B. Verify read Merkle proofs
    for j in 0..d-1:
        assert MerkleVerify(sp.root_before,
            sp.reads[j].addr, sp.reads[j].block,
            sp.reads[j].merkle_path)

    // C. Replay pointer-chase
    cursor = sp.cursor_in
    for j in 0..d-1:
        a = OS2IP(XOF(cursor, j)) mod N
        assert a == sp.reads[j].addr
        cursor = H(cursor || sp.reads[j].block.data
                           || sp.reads[j].block.causal)

    // D. Verify symbiotic write
    w = OS2IP(XOF(cursor, d)) mod N
    assert w == sp.write.addr
    assert MerkleVerify(sp.root_before, w,
                        sp.write.old, sp.write.merkle_path)
    assert sp.write.new.data == H(sp.write.old.data
                                   || cursor
                                   || sp.write.old.causal)
    assert sp.write.new.causal == H(sp.write.old.causal
                                     || cursor
                                     || I2OSP(sp.step_id, 4))

    // E. Verify Merkle root update
    assert sp.root_after == MerkleUpdate(
        sp.root_before, w, sp.write.new)

    // F. Compute and store transcript value for cross-check
    T_c = H(sp.cursor_in || I2OSP(sp.step_id, 4)
            || cursor || sp.root_after)
    // If another challenged step c' has cursor_in == T_c,
    // verify they match. If sp.step_id == K, verify
    // T_c == T_K (the public final transcript).
    stored_transcripts[sp.step_id] = T_c

    // G. Recursive causal provenance
    for j in 0..d-1:
        verify_writer(sp.writers[j], sp.reads[j],
                      C_roots, root_0, params)

4.2. Verification Cost

For Q challenges with recursion depth R:¶

• Root chain proofs: O(Q * log K) per challenged step¶

• Arena Merkle proofs: O(Q * d^R * log N)¶

• Cursor replays: O(Q * d^R * d)¶

• No arena memory allocation¶

For Q=128, d=8, R=3, N=2^24, K=4*N=2^26:¶

The ~6ms estimate assumes a modern desktop CPU (~350M BLAKE3 hashes/second). On constrained platforms (mobile: 60-300ms; WASM: 120ms-600ms), verification is slower but still practical. No memory allocation beyond the proof data is required.¶

5.1. Threat Model

The adversary is a probabilistic polynomial-time algorithm with random oracle access to H. The adversary receives the public seed s and parameters (N, K, d, Q, R). Its goal is to produce (T_K, C_roots, proof) that passes VERIFY (Section 4.1) while either:¶

1. Forgery: producing T_K' != T_K (the honestly computed transcript), or¶

2. Space reduction: using less than N * B bits of arena storage at some point during computation.¶

The adversary may use custom hardware with faster memory (lower latency) than the honest Prover. The ASIC resistance analysis (Section 5.5) bounds the resulting speedup.¶

5.2. Forgery Prevention

The causal hash mechanism prevents block value fabrication. To forge a block's causal hash, the adversary needs the cursor of the step that wrote it. That cursor depends on d blocks read at the writer step, each with their own causal hashes requiring their own writers' cursors, recursively. Symbiotic binding strengthens this: forging data requires old_causal, and forging old_causal requires the prior writer's cursor. Neither field can be independently fabricated.¶

The root chain commitment (Section 3.4) binds the Prover to ALL K arena roots before challenges are derived. C_roots is an input to the Fiat-Shamir challenge derivation, so the Prover cannot fabricate roots after seeing challenges.¶

Theorem 1 (Soundness). Any adversary producing (T_K', C_roots', proof') with T_K' != T_K that passes VERIFY has advantage at most K * epsilon_cr, where epsilon_cr is the collision-finding advantage against H.¶

Proof sketch. If verification passes with T_K' != T_K, there exists a step c where T_{c-1}' = T_{c-1} but T_c' != T_c (the first divergence). At step c, the Verifier checks that T_c = H(T_{c-1} || c || cursor || root_c). If the adversary's inputs differ from the honest inputs but produce the same T_c, this is a collision in H. If the adversary's inputs differ and produce a different T_c, then T_c' != T_c, contradicting acceptance. The adversary has K steps at which to attempt this, giving the union bound K * epsilon_cr.¶

A full derivation is provided in the companion analysis (to appear as IACR ePrint).¶

5.3. Recomputation Cost

Separately from forgery prevention, the combination of causal hashes and spatial neighborhood entanglement imposes a geometric increase on the cost of recomputing missing blocks.¶

Without spatial entanglement, an adversary recomputing a missing block traverses its write chain at cost O(rho) hashes. With Spatial Neighborhood Entanglement (Section 3.3.2), every write to block $w$ depends on the causal hashes of its physical neighbors $A[w-1]$ and $A[w+1]$. If those neighbors are also missing from storage, the Prover must recursively recompute their states, triggering a "Trophic Cascade" of recomputation.¶

This shifts the TMTO penalty from linear to geometric. For an adversary with zero storage ($\alpha=0$), recomputing a single challenged block requires recovering the entire spatial web of dependencies, making storage reduction exponentially prohibitive relative to the write density rho.¶

5.4. TMTO Lower Bound

An adversary storing alpha * N blocks faces a two-layer penalty:¶

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

T_adv >= K * d * (1 + (1-alpha) * (2*rho + 1))

5.5. ASIC Resistance

PoSME is anchored in a physics-bounded latency floor. While computation throughput improves exponentially with transistor scaling, random-access memory latency is constrained by the fundamental thermodynamics of charge-sensing in capacitors.¶

The per-hop bottleneck is determined by the mandatory bank conflict (Section 3.3.1), which forces the DRAM controller to execute a full Row Precharge ($t_{RP}$) and RAS-to-CAS Delay ($t_{RCD}$) for every sequential read. These timings are physical constants of DRAM cell operation that do not scale with logic shrinks. Even an adversary with wafer-scale on-die integration (Section 5.5.1) faces a latency floor constrained by signal propagation across the die and the settling time of the memory cells.¶

Consequently, the ASIC advantage is not a function of "better hardware," but rather the physical limit of signal propagation and charge sensing. By forcing intra-step bank collisions, PoSME ensures that even the most optimized controller spends the majority of its wall-clock time in a stalled state, waiting for the physical laws of DRAM to resolve the next address.¶

5.6. Sequentiality

Intra-step: The d reads form a pointer-chasing chain; read j+1's address depends on read j's result.¶

Inter-step: T_t feeds into address generation for step t+1.¶

Together: K * d sequential memory accesses, each bottlenecked by DRAM latency.¶

7.1. Proof Size Optimization

The recursion depth R and challenge count Q present a direct tradeoff between security margin and proof size. Table 6 provides concrete MiB- per-proof costs for implementers.¶

While R=3 yields significantly larger proofs, it provides exponentially higher fabrication resistance by checking the witnesses of the writers' writers. For bandwidth-constrained environments (e.g., light clients), R=2 with Q=128 offers a compact ~8 MiB proof while maintaining high confidence.¶

7.2. Recommended Parameters

PoSME's security properties have different parameter dependencies. TMTO resistance (Section 5.4) depends on the write density rho = K/N and is independent of arena size. ASIC resistance can be achieved through arena size exceeding the adversary's fastest memory (Section 5.5). Applications SHOULD select parameters based on their threat model.¶

7.3. Parameter Validation

Verifiers MUST reject proofs with parameters below these minimums:¶

7.4. Performance Estimates

The following properties are machine-independent:¶

Reference timings (Apple M-series, DDR5; will vary by hardware):¶

Verifier time is independent of profile (depends on Q, d, R, N):¶

A reference benchmark with pre-compiled binaries is provided as ancillary material (anc/README.md).¶

8.1. Work vs. Time

PoSME proves sequential memory execution, not elapsed time. An adversary with faster memory (lower latency) completes the same computation in less wall-clock time. The ASIC advantage is bounded (approximately 2x) but nonzero. Applications requiring temporal guarantees MUST combine PoSME with an external time-binding mechanism such as hardware-attested timestamps.¶

Hardware-independent time-binding is impossible: deterministic computation produces identical output regardless of hardware speed, and self-reported timing is forgeable.¶

8.2. Seed Requirements

The seed MUST be externally fixed or derived from an unpredictable source. A Prover-controlled seed enables grinding for favorable arena initializations with reduced effective working sets.¶

8.3. Verification Complexity

We conjecture that O(1) verification under hash-only assumptions is not achievable for sequential pointer-chasing computations of the type PoSME specifies. The verification complexity in this document is O(Q * d^R * log N). O(log^2 K) verification is believed achievable via FRI/STARK-based commitment (requiring field arithmetic but no trusted setup) and is left as a future optimization. A formal impossibility proof for constant-size hash-only verification of PoSME remains open.¶

8.4. Verifier Resource Limits

Verifiers SHOULD implement rate limiting and MUST reject proofs with parameters exceeding configured thresholds before allocating resources for verification.¶

8.5. Open Problems

The dynamic pebbling game (Section 5.4.4) provides a framework for TMTO analysis, but a machine-checked proof of the space-time lower bound remains open. The adversary's optimal caching strategy (which blocks to store, when to checkpoint) has not been formally optimized. Block access distribution uniformity under hash-derived addressing requires formal characterization (see Conjecture 1); skewed distributions may enable hot-block caching. Host-as- critical-path mechanisms for ASIC resistance at cache-resident arena sizes (where arena fits within on-die SRAM) are out of scope for this draft. Such mechanisms require the host's computation to gate the next prover step rather than supply ancillary entropy. This is deferred to future work. The tight relationship between committed step frequency C, write density rho, and the optimal adversary strategy requires further analysis.¶

9.1. Bank Mapping and Conflicts

The effectiveness of intra-step bank collisions (Section 3.3.1) depends on the accuracy of the force_bank_mapping logic. Memory controllers typically use specific physical address bits for bank selection (e.g., bits 13-16 on many DDR4/DDR5 platforms).¶

Prover implementations SHOULD use platform-specific knowledge or calibration loops to identify these bits. If the exact mapping is unknown, the Prover MAY use a XOR-sum of multiple candidate bit ranges to increase the probability of a physical bank conflict. Verifiers DO NOT check physical mapping accuracy; they only check the logical consistency of the derived addresses according to the protocol parameters.¶

9.2. Timing Counters

Provers MUST use the highest-resolution monotonic hardware counter available to capture delta_t.¶

• x86_64: The RDTSC or RDTSCP instructions.¶

• AArch64: The CNTPCT_EL0 system register.¶

The resulting delta_t SHOULD NOT be normalized or filtered. Raw cycle counts are required to preserve the stochastic jitter profile arising from DRAM refresh cycles ($t_{REFW}$) and OS-level noise.¶

9.3. Cache Management

To ensure the arena computation is bottlenecked by DRAM latency rather than CPU cache hits, the arena size $N$ SHOULD be configured to exceed the Prover's L3 cache capacity. For Standard and Maximum profiles, the arena sizes (64 MiB to 1 GiB) are specifically chosen to exceed the 16-96 MiB caches typical of commodity processors.¶

Provers MAY use cache-bypass instructions (e.g., MOVNTI on x86) for arena writes to further enforce DRAM-bounded execution.¶

11.1. Normative References

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/rfc/rfc2119>.

[RFC8017]

Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10.17487/RFC8017, November 2016, <https://www.rfc-editor.org/rfc/rfc8017>.

[RFC8174]

Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

[RFC8610]

Birkholz, H., Vigano, C., and C. Bormann, "Concise Data Definition Language (CDDL): A Notational Convention to Express Concise Binary Object Representation (CBOR) and JSON Data Structures", RFC 8610, DOI 10.17487/RFC8610, June 2019, <https://www.rfc-editor.org/rfc/rfc8610>.

[RFC8949]

Bormann, C. and P. Hoffman, "Concise Binary Object Representation (CBOR)", STD 94, RFC 8949, DOI 10.17487/RFC8949, December 2020, <https://www.rfc-editor.org/rfc/rfc8949>.

11.2. Informative References

[AlwenBlockPietrzak2017]

Alwen, J., Blocki, J., and K. Pietrzak, "Depth-Robust Graphs and Their Cumulative Memory Complexity", EUROCRYPT 2017, LNCS 10212, pp. 3-32, 2017, <https://doi.org/10.1007/978-3-319-56617-7_1>.

[Biryukov2016]

Biryukov, A., Dinu, D., and D. Khovratovich, "Argon2: New Generation of Memory-Hard Functions for Password Hashing and Other Applications", IEEE EuroS&P pp. 292-302, 2016, <https://doi.org/10.1109/EuroSP.2016.31>.

[Boneh2016]

Boneh, D., Corrigan-Gibbs, H., and S. Schechter, "Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks", ASIACRYPT 2016, 2016, <https://doi.org/10.1007/978-3-662-53887-6_8>.

[Boneh2018]

Boneh, D., Bonneau, J., Bunz, B., and B. Fisch, "Verifiable Delay Functions", CRYPTO 2018, 2018, <https://doi.org/10.1007/978-3-319-96884-1_25>.

[Chia2024]

Chia Network, "The Chia Network Green Paper", 2024, <https://docs.chia.net/green-paper-abstract>.

[CohenPietrzak2018]

Cohen, B. and K. Pietrzak, "Simple Proofs of Sequential Work", EUROCRYPT 2018, LNCS 10821, pp. 451-467, 2018, <https://doi.org/10.1007/978-3-319-78375-8_15>.

[JESD238]

JEDEC Solid State Technology Association, "High Bandwidth Memory (HBM3) DRAM", JEDEC JESD238B01, 2022, <https://www.jedec.org/standards-documents/docs/jesd238b01>.

[JESD79-5]

JEDEC Solid State Technology Association, "DDR5 SDRAM Standard", JEDEC JESD79-5D, 2020, <https://www.jedec.org/standards-documents/docs/jesd79-5d>.

[RenDevadas2017]

Ren, L. and S. Devadas, "Bandwidth Hard Functions for ASIC Resistance", TCC 2017, LNCS 10677, pp. 466-492, 2017, <https://doi.org/10.1007/978-3-319-70500-2_16>.

[RFC6962]

Laurie, B., Langley, A., and E. Kasper, "Certificate Transparency", RFC 6962, DOI 10.17487/RFC6962, June 2013, <https://www.rfc-editor.org/rfc/rfc6962>.

[RFC9106]

Biryukov, A., Dinu, D., Khovratovich, D., and S. Josefsson, "Argon2 Memory-Hard Function for Password Hashing and Proof-of-Work Applications", RFC 9106, DOI 10.17487/RFC9106, September 2021, <https://www.rfc-editor.org/rfc/rfc9106>.

[Spacemesh2023]

Spacemesh Team, "The Spacemesh Protocol", 2023, <https://github.com/spacemeshos/protocol>.

[Wesolowski2019]

Wesolowski, B., "Efficient Verifiable Delay Functions", EUROCRYPT 2019, 2019, <https://doi.org/10.1007/978-3-030-17659-4_13>.