pith. sign in

arxiv: 2604.15751 · v1 · submitted 2026-04-17 · 💻 cs.CR · cs.DC

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

David L. Condrey This is my paper

Pith reviewed 2026-05-10 08:49 UTC · model grok-4.3

classification 💻 cs.CR cs.DC
keywords proof of sequential memory executionpointer chasingcausal hash bindingtime-memory tradeoff resistanceASIC advantage boundverifiable delaySybil resistancelatency-bound computation
0
0 comments X

The pith

PoSME forces sustained sequential memory steps by chasing data-dependent pointers and binding each write to its own causal hash.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces PoSME as a cryptographic primitive that makes each computation step read from an address determined by prior results, then write a block whose value and hash must be generated together before the next address can be known. This structure is meant to prevent shortcuts, parallel execution, or memory-time tradeoffs while keeping the entire process verifiable through a chained transcript. A reader would care because the method claims to deliver strict sequential enforcement and hardware asymmetry without any trusted setup or special hardware assumptions. The work positions this as a building block for verifiable delays, authorship proofs, and Sybil resistance in distributed systems.

Core claim

PoSME achieves three properties through latency-bound pointer chasing over a mutable arena with symbiotic value-hash binding: strict linear enforcement of sequential memory steps, high resistance to time-memory tradeoffs with a formal quadratic space-time lower bound, and an ASIC advantage strictly limited by DRAM random-access latency rather than bandwidth or parallelism.

What carries the argument

Symbiotic binding of each written block's value to its causal hash inside data-dependent pointer chasing over a mutable memory arena.

If this is right

  • Each step must complete before the next address is known, enforcing strict sequential execution.
  • Time-memory tradeoffs incur at least a tenfold penalty at write density of 4, with quadratic scaling in steps.
  • ASIC implementations gain no advantage beyond the inherent DRAM access latency limit.
  • The construction requires no trusted setup and directly supports verifiable delay functions.
  • The transcript enables authorship attestation and Sybil resistance applications.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The quadratic bound could make PoSME suitable for memory-hard sequential proofs in decentralized ledgers where parallelism must be penalized.
  • Hardware asymmetry between CPUs and GPUs shown in benchmarks suggests possible use in client puzzles that favor general-purpose processors.
  • The mutable arena plus causal binding might extend to verifiable execution traces that tie computation order to physical memory access patterns.

Load-bearing premise

That data-dependent pointer chasing in a mutable arena cannot be parallelized, prefetched, or otherwise optimized to break the latency-bound model or the quadratic space-time bound.

What would settle it

A concrete ASIC or optimized algorithm that completes N steps of PoSME with total time and memory cost growing only linearly rather than quadratically, or with effective latency per step below typical DRAM random-access times.

Figures

Figures reproduced from arXiv: 2604.15751 by David L. Condrey.

Figure 1
Figure 1. Figure 1: Hardware advantage over consumer CPU (log scale). P [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Per-read cost across six memory technologies. Hash (3 ns, red) is [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
read the original abstract

We introduce PoSME (Proof of Sequential Memory Execution), a cryptographic primitive that enforces sustained sequential computation via latency-bound pointer chasing over a mutable arena. Each step reads data-dependent addresses, writes a block whose value and causal hash are mutually dependent (symbiotic binding), and chains the result into a global transcript. This yields three properties: (1) strict linear sequential memory-step enforcement, (2) high time-memory trade-off resistance (a tenfold penalty at a write density of 4, with a formal space-time lower bound that scales quadratically with the number of steps), and (3) a tight ASIC advantage bound by DRAM random-access latency rather than bandwidth. Benchmarks across 17 CPU platforms and 4 GPU architectures demonstrate that hash computation is under 3.5 percent of step cost and GPU hardware is 14 to 19 times slower than a consumer CPU. POSME requires no trusted setup and provides a foundation for verifiable delay, authorship attestation, and Sybil resistance.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 1 invented entities

The central claim rests on the unproven effectiveness of symbiotic hash binding and the assumption that DRAM random-access latency dominates all optimizations; these are new constructs introduced in the paper without independent evidence supplied in the abstract.

free parameters (1)
  • write density parameter
    The tenfold penalty is stated at a write density of 4; this value appears chosen to illustrate the trade-off and may be fitted to observed behavior.
axioms (2)
  • domain assumption Pointer chasing remains strictly latency-bound under data-dependent addressing
    Invoked to support the ASIC advantage bound and sequential enforcement.
  • ad hoc to paper Symbiotic binding between block value and causal hash prevents all non-sequential shortcuts
    Core to the claimed time-memory resistance; introduced without prior citation in the abstract.
invented entities (1)
  • symbiotic binding no independent evidence
    purpose: To mutually constrain value and hash so that neither can be computed independently
    New construct introduced to enforce sequentiality; no independent falsifiable evidence provided in abstract.

pith-pipeline@v0.9.0 · 5471 in / 1613 out tokens · 61980 ms · 2026-05-10T08:49:04.636123+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    Verifiable delay functions,

    D. Boneh, J. Bonneau, B. B ¨unz, and B. Fisch, “Verifiable delay functions,” inCRYPTO 2018, LNCS 10991, pp. 757–788, 2018

    work page 2018

  2. [2]

    Simple proofs of sequential work,

    B. Cohen and K. Pietrzak, “Simple proofs of sequential work,” in EUROCRYPT 2018, LNCS 10821, pp. 451–467, 2018

    work page 2018

  3. [3]

    Argon2: new generation of memory-hard functions for password hashing and other applications,

    A. Biryukov, D. Dinu, and D. Khovratovich, “Argon2: new generation of memory-hard functions for password hashing and other applications,” inIEEE EuroS&P, pp. 292–302, 2016

    work page 2016

  4. [4]

    Bandwidth hard functions for ASIC resistance,

    L. Ren and S. Devadas, “Bandwidth hard functions for ASIC resistance,” inTCC 2017, LNCS 10677, pp. 466–492, 2017

    work page 2017

  5. [5]

    Depth-robust graphs and their cumulative memory complexity,

    J. Alwen, J. Blocki, and K. Pietrzak, “Depth-robust graphs and their cumulative memory complexity,” inEUROCRYPT 2017, LNCS 10212, pp. 3–32, 2017

    work page 2017

  6. [6]

    DDR5 SDRAM standard,

    JEDEC Solid State Technology Association, “DDR5 SDRAM standard,” JESD79-5D, 2020

    work page 2020

  7. [7]

    Understanding and improving the latency of DRAM-based memory systems,

    K. K. Changet al., “Understanding and improving the latency of DRAM-based memory systems,” arXiv:1712.08304, 2017

    work page arXiv 2017

  8. [8]

    Stronger key derivation via sequential memory-hard func- tions,

    C. Percival, “Stronger key derivation via sequential memory-hard func- tions,” inBSDCan, 2009

    work page 2009

  9. [9]

    Proofs of space,

    S. Dziembowski, S. Faust, V . Kolmogorov, and K. Pietrzak, “Proofs of space,” inCRYPTO 2015, LNCS 9216, pp. 585–605, 2015

    work page 2015

  10. [10]

    BLAKE3: one function, fast everywhere,

    J. O’Connoret al., “BLAKE3: one function, fast everywhere,” 2020, https://github.com/BLAKE3-team/BLAKE3-specs

    work page 2020

  11. [11]

    Efficient verifiable delay functions,

    B. Wesolowski, “Efficient verifiable delay functions,” inEUROCRYPT 2019, LNCS 11478, pp. 379–407, 2019

    work page 2019

  12. [12]

    Succinct arguments over towers of binary fields,

    B. E. Diamond and J. Posen, “Succinct arguments over towers of binary fields,” Cryptology ePrint Archive, Report 2023/1784, 2023

    work page 2023

  13. [13]

    Communication complexity of pointer chasing via the fixed- set lemma,

    E. Viola, “Communication complexity of pointer chasing via the fixed- set lemma,” arXiv:2507.08919, 2025

    work page arXiv 2025

  14. [14]

    Towards practical data-dependent memory- hard functions with optimal sustained space trade-offs in the parallel random oracle model,

    J. Blocki and B. Holman, “Towards practical data-dependent memory- hard functions with optimal sustained space trade-offs in the parallel random oracle model,” arXiv:2508.06795, 2025

    work page arXiv 2025

  15. [15]

    Balloon Hashing: a memory-hard function providing provable protection against sequential attacks,

    D. Boneh, H. Corrigan-Gibbs, and S. Schechter, “Balloon Hashing: a memory-hard function providing provable protection against sequential attacks,” inASIACRYPT 2016, LNCS 10031, pp. 220–248, 2016

    work page 2016

  16. [16]

    Proof of Space and Time Whitepaper,

    Chia Network, “Proof of Space and Time Whitepaper,” 2021, https: //www.chia.net/whitepaper/

    work page 2021

  17. [17]

    The Spacemesh Protocol,

    Spacemesh Team, “The Spacemesh Protocol,” 2023, https://spacemesh. io/whitepaper/

    work page 2023

  18. [18]

    Pricing via processing or combatting junk mail,

    C. Dwork and M. Naor, “Pricing via processing or combatting junk mail,” inCRYPTO 1992, LNCS 740, pp. 139–147, 1993

    work page 1992

  19. [19]

    Simple verifiable delay functions,

    K. Pietrzak, “Simple verifiable delay functions,” inITCS 2019, LIPIcs 124, pp. 60:1–60:15, 2019

    work page 2019

  20. [20]

    Rounds in communication complexity revisited,

    N. Nisan and A. Wigderson, “Rounds in communication complexity revisited,” inSTOC 1991, pp. 419–429, 1991

    work page 1991

  21. [21]

    RandomX: design and analysis,

    tevador, “RandomX: design and analysis,” 2019, https://github.com/ tevador/RandomX/blob/master/doc/design.md

    work page 2019

  22. [22]

    How to prove yourself: practical solutions to identification and signature problems,

    A. Fiat and A. Shamir, “How to prove yourself: practical solutions to identification and signature problems,” inCRYPTO 1986, LNCS 263, pp. 186–194, 1987

    work page 1986

  23. [23]

    A digital signature based on a conventional encryption function,

    R. C. Merkle, “A digital signature based on a conventional encryption function,” inCRYPTO 1987, LNCS 293, pp. 369–378, 1988

    work page 1987

  24. [24]

    Multivariate lookups based on logarithmic derivatives,

    U. Hab ¨ock, “Multivariate lookups based on logarithmic derivatives,” Cryptology ePrint Archive, Report 2022/1530, 2022

    work page 2022

  25. [25]

    Nova: recursive zero-knowledge arguments from folding schemes,

    A. Kothapalli, S. Setty, and I. Tzialla, “Nova: recursive zero-knowledge arguments from folding schemes,” inCRYPTO 2022, LNCS 13510, pp. 359–388, 2022

    work page 2022

  26. [26]

    High parallel complexity graphs and memory-hard functions,

    J. Alwen and V . Serbinenko, “High parallel complexity graphs and memory-hard functions,” inSTOC 2015, pp. 595–603, 2015

    work page 2015

  27. [27]

    Sustained space complexity,

    J. Alwen, J. Blocki, and K. Pietrzak, “Sustained space complexity,” in EUROCRYPT 2018, LNCS 10821, pp. 99–130, 2018

    work page 2018

  28. [28]

    Bitcoin: a peer-to-peer electronic cash system,

    S. Nakamoto, “Bitcoin: a peer-to-peer electronic cash system,” 2008, https://bitcoin.org/bitcoin.pdf

    work page 2008

  29. [29]

    Hashcash – a denial of service counter-measure,

    A. Back, “Hashcash – a denial of service counter-measure,” 2002, http: //www.hashcash.org/papers/hashcash.pdf

    work page 2002

  30. [30]

    Hardware architecture and software stack for PIM based on commercial DRAM technology,

    S. Leeet al., “Hardware architecture and software stack for PIM based on commercial DRAM technology,” inISCA 2021, pp. 43–56, 2021

    work page 2021

  31. [31]

    Scrypt is maximally memory-hard,

    J. Alwen, B. Chen, K. Pietrzak, L. Reyzin, and S. Tessaro, “Scrypt is maximally memory-hard,” inEUROCRYPT 2017, LNCS 10212, pp. 33– 62, 2017

    work page 2017

  32. [32]

    NVIDIA H100 Tensor Core GPU architecture,

    NVIDIA Corporation, “NVIDIA H100 Tensor Core GPU architecture,” Whitepaper, 2022

    work page 2022