💻 computer science

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

Het paper introduceert PoSME, een cryptografisch primitief dat sequentiële berekening afdwingt via latency-gebonden pointer-chasing in een mutabele arena, waardoor het weerstand biedt tegen tijd-geheugen trade-offs en ASIC-voordelen beperkt worden tot DRAM-latency, zonder dat een vertrouwd opzetproces nodig is.

Oorspronkelijke auteurs: David L. Condrey

Gepubliceerd 2026-04-20

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: David L. Condrey

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

PoSME: De "Onmogelijke" Schatkaart

Stel je voor dat je een schatkaart wilt bewijzen die je hebt gevonden. In de digitale wereld willen we vaak bewijzen dat iemand echt veel werk heeft verzet, zonder dat ze kunnen valsspelen of dat een supercomputer het in een seconde kan nabootsen.

Tot nu toe hadden we twee soorten bewijzen:

Rekenkracht-bewijzen: "Ik heb dit moeilijke raadsel opgelost." (Dit kan een dure computerchip heel snel doen).
Opslag-bewijzen: "Ik heb een enorme hoeveelheid data opgeslagen." (Dit is goedkoop te kopiëren).

PoSME is een nieuw soort bewijs dat een slimme combinatie is: het dwingt de computer om tijd te verspillen door geheugen te gebruiken, en het maakt het onmogelijk om dit te versnellen met dure chips.

Hier is hoe het werkt, stap voor stap:

1. De Levende Schatkaart (Het Mutable Arena)

Stel je een gigantisch bibliotheekgebouw voor met 1 miljard boeken (het geheugen).

Oude methode: Je leest een boek, schrijft een antwoord op een briefje en dat was het. De boeken bleven staan zoals ze waren.
PoSME-methode: Elke keer als je een boek leest, verander je het boek zelf. Je schrijft een nieuwe zin erin, maar die zin hangt af van wat je net las.
- De analogie: Het is alsof je een pad door een bos loopt, maar elke keer als je een boom raakt, verandert die boom van kleur en vorm. Als je morgen terugkomt, is het bos er heel anders uit. Je kunt het pad niet "opnieuw" lopen zonder het bos opnieuw te bouwen.

2. De Blindelings Zoeker (Pointer Chasing)

In een normaal spel kun je vaak meerdere dingen tegelijk doen. Bij PoSME moet je blindelings zoeken.

Je leest een boek op plek A.
De tekst in dat boek vertelt je pas waar je het volgende boek moet zoeken (plek B).
Pas als je plek B hebt gevonden en gelezen, weet je waar plek C zit.
Het probleem: Je kunt niet "in één keer" naar plek A, B en C springen. Je moet wachten tot je de code van A hebt, dan naar B, dan naar C. Dit is een strikte keten. Je kunt dit niet versnellen door meer mensen (of computerkernen) in te zetten, omdat de volgende stap pas bestaat nadat de vorige klaar is.

3. De Onlosmakelijke Band (Symbiotic Binding)

Elk boek in de bibliotheek heeft nu twee dingen:

De inhoud (de data).
Een "stempel" (de causale hash) dat bewijst welke boeken er eerder zijn gelezen.

De analogie: Het is alsof je een brief schrijft, maar de inkt van je brief is gemaakt van de inkt van de vorige brief die je las. Als je de vorige brief wilt vervalsen, moet je ook de hele geschiedenis van alle vorige brieven opnieuw schrijven. Je kunt geen losse pagina's vervalsen zonder dat de hele keten instort.

Waarom is dit zo slim? (De "Hardware" Valstrik)

Het paper laat zien dat dit systeem heel goed werkt tegen hackers met dure apparatuur.

De Bottleneck is Wachten, niet Rekenen:
De grootste vertraging in dit proces is niet het rekenen (het schrijven van de tekst), maar het wachten tot de bibliotheekmedewerker (het geheugen/DRAM) het juiste boek uit de kast haalt.
- Analogie: Het is alsof je een brief moet schrijven, maar je moet elke zin wachten tot iemand een boek uit een kamer van 50 meter afstand haalt. Het schrijven duurt 3 seconden, maar het wachten duurt 50 seconden.
- Gevolg: Het maakt niet uit of je een supersnelle pen (een snelle processor) hebt. Je bent nog steeds beperkt door de snelheid van de persoon die de boeken haalt.
Waarom GPUs (Videokaarten) falen:
Videokaarten zijn geweldig om duizenden dingen tegelijk te doen (zoals duizenden rekeningen tegelijk oplossen). Maar bij PoSME moet je dingen achter elkaar doen.
- De test: Het paper toont aan dat een krachtige NVIDIA H100 videokaart 14 tot 19 keer langzamer is dan een gewone consumenten-laptop voor dit specifieke spelletje. De videokaart heeft te veel "wacht-tijd" en te weinig "boeken" (geheugen) om tegelijkertijd veel spellen te spelen.
Waarom dure chips (ASICs) te duur zijn:
Om dit sneller te maken, moet je een chip bouwen die extreem snel boeken kan halen. Maar de fysieke wetten van geheugen (DRAM) maken dat je niet veel sneller kunt worden dan een gewone computer. De kosten om een chip te bouwen die 30% sneller is, zijn zo hoog dat het economisch onzinnig is voor een hacker.

De Drie Grote Voordelen

Tijdsbewijs: Je kunt niet "cheaten" door meer rekenkracht te gebruiken. Je moet echt de tijd nemen om door de keten te lopen.
Opslag-dwang: Je moet het hele bibliotheekgebouw (het geheugen) bijhouden. Als je boeken weggooit om ruimte te besparen, moet je ze later opnieuw "schrijven" (rekenen), wat veel tijd kost.
Veiligheid: Zelfs als je een supercomputer hebt, ben je niet sneller dan een gewone laptop. Dit maakt het perfect voor eerlijke systemen (zoals crypto-mijnbouw of het bewijzen van auteurschap) waar niemand een voorsprong mag hebben.

Kortom

PoSME is een digitaal spelletje waarbij je een levend, veranderend bos moet doorkruisen. Je kunt niet vliegen, je kunt niet teleporteren, en je kunt niet sneller lopen door meer mensen mee te nemen. Je moet gewoon lopen, stap voor stap, en wachten tot de volgende stap zich openbaart.

Het paper bewijst wiskundig en met echte tests dat dit de enige manier is om te garanderen dat iemand echt tijd en geheugen heeft gebruikt, zonder dat dure apparatuur hen een oneerlijke voorsprong geeft. Het is de "eerlijke" manier om digitale arbeid te meten.

1. Probleemstelling

Bestaande cryptografische primitieven voor het bewijzen van sequentiële arbeid (zoals Verifiable Delay Functions - VDFs, Proofs of Sequential Work - PoSW, en Memory Hard Functions - MHFs) hebben elk een beperking die hen ongeschikt maakt voor specifieke toepassingen zoals ASIC-resistente mining, auteurschap-attestatie en Sybil-resistentie:

VDFs: Bewijzen tijd, maar zijn niet geheugen-intensief; ASICs kunnen hier enorm versnellen door snellere rekenkracht.
PoSW: Bewijzen traversie van een grafiek, maar over statisch, onveranderlijk geheugen.
MHFs (zoals Argon2id): Verhogen de kosten via geheugendruk, maar zijn "single-shot" en hebben geen kettingbewijs-systeem.
Gemeenschappelijk probleem: Geen enkele bestaande methode combineert sequentiële stappen, geheugen-intensiviteit, mutabele staat (veranderlijk geheugen) en efficiënte verificatie tegelijkertijd.

Het doel is een primitief te creëren dat dwingt tot langdurige, sequentiële berekening waarbij de bottleneck de latentie van willekeurige geheugentoegang is (DRAM), en niet de bandbreedte of rekenkracht.

2. Methodologie: PoSME Constructie

PoSME (Proof of Sequential Memory Execution) lost dit op door een mutabele arena te gebruiken waar data-afhankelijke pointer-chasing plaatsvindt, gekoppeld aan een symbiotische causale hash-binding.

Mutabele Arena: In tegenstelling tot statische grafieken, evolueert de staat van het geheugen bij elke stap. Een blok wordt niet alleen gelezen, maar ook herschreven. Dit dwingt de bewijzer (Prover) om het geheugen te bewaren, omdat de waarde van een blok onvoorspelbaar verandert tijdens de uitvoering.
Data-afhankelijke Pointer Chasing: De locatie van de volgende lezing wordt bepaald door de hash van de vorige lezing. Dit creëert een strikte sequentiële keten die niet paralleliseerbaar is.
Symbiotische Causale Binding: Bij elke schrijfstap worden de data en de "causale hash" (de geschiedenis van schrijfbewerkingen) aan elkaar gekoppeld. De nieuwe data is afhankelijk van de oude causale hash, en de nieuwe causale hash is afhankelijk van de nieuwe data. Een aanvaller kan geen enkel blok vervalsen zonder de volledige causale lijn te vervalsen.
Hypercube Structuur: De arena wordt gemodelleerd als een Booleaanse hypercube. Dit maakt het mogelijk om de staat als een multilineaire polynoom te beschrijven, wat essentieel is voor efficiënte verificatie via binaire-veld folding (Binius).
Verificatiemodi:
1. Klassiek: Gebruikt Merkle-bomen en Fiat-Shamir (proof size schaalt met recursiediepte).
2. IVC (Incrementally Verifiable Computation): Gebruikt Binius en binaire-veld folding om een constante bewijsgrootte ( $O(1)$ ) te bereiken, ongeacht het aantal stappen.

3. Belangrijkste Bijdragen

Novel Constructie: De eerste primitief die mutabele staat, data-afhankelijke pointer-chasing en symbiotische causale binding combineert, formeel gedefinieerd over een Booleaanse hypercube.
Ruimte-Tijd Veiligheid: Een formeel bewijs van een ondergrens van $S \cdot T = \Omega(K^2)$ voor dynamische causale DAG's. Dit bewijs is uitgebreid naar adaptieve aanvallen zonder verlies van factoren.
ROM Validatie: Wiskundige en empirische validatie dat de adresgeneratie uniform is (gebaseerd op de Random Oracle Model aanname), zelfs op de aanbevolen schaal ( $N=2^{24}$ ).
Hardware Validatie: Uitgebreide benchmarks op 17 CPU-platforms en 4 GPU-architecturen die aantonen dat GPU's 14-19 keer langzamer zijn dan consumenten-CPU's voor deze workload.
IVC Ontwerp: Een concreet arithmetisatieontwerp (met Binius) dat $O(1)$ verificatie mogelijk maakt met een bewijsgrootte van slechts enkele kilobytes.

4. Resultaten en Empirische Validatie

Hardware Voordelen:
- GPU's: GPU's zijn 14-19x langzamer dan CPU's bij PoSME. Dit komt omdat GPU's geoptimaliseerd zijn voor parallelle doorvoer (bandbreedte), terwijl PoSME gebonden is aan sequentiële latentie.
- ASIC-resistentie: De bottleneck is de DRAM-random-access latentie (40-50 ns op DDR5). Hash-berekening is minder dan 3,5% van de totale kost. Zelfs met snellere geheugentechnologieën (zoals HBM3) is het voordeel slechts 1,3x ten opzichte van DDR5. Er bestaat geen commercieel verkrijgbare hardware die een consumenten-CPU verslaat.
- Capaciteit vs. Bandbreedte: Een aanvaller kan niet simpelweg meer GPU's parallel draaien, omdat elke instantie een unieke, grote arena (1 GiB) nodig heeft. Dit maakt de aanval een capaciteitsprobleem (VRAM-geheugen) in plaats van een bandbreedteprobleem. GPU's hebben te weinig VRAM om veel instanties parallel te draaien.
Time-Memory Trade-off (TMTO): Bij een schrijfdichtheid van $\rho=4$ (elk blok wordt gemiddeld 4 keer overschreven) is de TMTO-resistentie 10x. Dit betekent dat een aanvaller die minder geheugen opslaat, 10 keer meer rekentijd nodig heeft dan een eerlijke proefnemer.
Verificatie:
- Klassieke verificatie duurt enkele milliseconden op desktops.
- IVC-verificatie is $O(1)$ en onafhankelijk van het aantal stappen $K$ .

5. Betekenis en Toepassingen

PoSME vult een cruciale lacune in de cryptografische primitieven:

ASIC-resistentie: Door de bottleneck te verleggen van rekenkracht naar geheugenlatentie, wordt de economische haalbaarheid van ASICs voor deze specifieke taken onmogelijk gemaakt.
Verifieerbare Vertraging: Het biedt een basis voor systemen die bewijzen dat een bepaalde hoeveelheid tijd is verstreken, zonder vertrouwde setup.
Sybil-resistentie en Auteurschap: Het kan worden gebruikt om te bewijzen dat een entiteit een specifieke hoeveelheid werk heeft verricht, wat nuttig is voor het voorkomen van botsnetwerken en het attesteren van menselijke auteurschap.
Toekomstbestendigheid: De constructie is compatibel met opkomende technologieën zoals "Processing-in-Memory" (PIM), waarbij de latentie nog verder zou kunnen dalen, maar de fundamentele fysieke beperkingen van geheugentoegang behouden blijven.

Conclusie: PoSME is een doorbraak die sequentiële arbeid, geheugen-intensiviteit en mutabiliteit combineert in een primitief dat fundamenteel gebaseerd is op de fysieke beperkingen van geheugenlatentie, waardoor het extreem resistent is tegen versnelling door gespecialiseerde hardware zoals GPU's en ASICs.