💻 computer science

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

Die Arbeit stellt PoSME vor, ein kryptografisches Primitive, das durch latenzgebundenen Pointer-Chasing in einem veränderbaren Speicherbereich sequentielle Berechnungen erzwingt, ASIC-Vorteile begrenzt und eine vertrauenslose Grundlage für verifizierbare Verzögerungen sowie Sybil-Resistenz bietet.

Ursprüngliche Autoren: David L. Condrey

Veröffentlicht 2026-04-20

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: David L. Condrey

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie wollen beweisen, dass Sie eine sehr langweilige, aber wichtige Aufgabe erledigt haben: Sie müssen einen riesigen, sich ständig verändernden Schatzkeller durchsuchen, um einen bestimmten Schatz zu finden.

Das Papier beschreibt eine neue Methode namens PoSME (Proof of Sequential Memory Execution). Hier ist die Erklärung in einfachen Worten, mit ein paar bildhaften Vergleichen:

1. Das Problem: Warum ist das schwierig?

Bisherige Methoden, um zu beweisen, dass jemand Zeit und Rechenleistung investiert hat, hatten zwei große Schwächen:

Zu schnell für Spezialchips: Manche Aufgaben lassen sich auf teuren Spezial-Chips (ASICs) oder Grafikkarten (GPUs) extrem schnell erledigen, weil diese Chips wie Rennwagen sind, während normale Computer wie Fahrräder sind.
Zu wenig Speicher: Andere Aufgaben zwingen den Computer, viel Speicher zu nutzen, aber man kann sie trotzdem umgehen, indem man einfach die Ergebnisse vorher berechnet und speichert.

PoSME ist wie ein neuer, fairer Wettbewerb, bei dem weder der Rennwagen noch der vorher berechnete Schatz hilft.

2. Die Lösung: Ein sich verändernder Labyrinth-Schloss

Stellen Sie sich einen riesigen Raum mit 1 Milliarde Schubladen vor (das ist der "Speicher").

Der Schlüssel ist dynamisch: Um die nächste Schublade zu öffnen, müssen Sie den Inhalt der aktuellen Schublade lesen. Aber hier ist der Trick: Der Inhalt der Schublade ändert sich sofort, nachdem Sie ihn gelesen haben!
Die Kette: Wenn Sie Schublade A öffnen, lesen Sie einen Hinweis, der Ihnen sagt, wo Schublade B ist. Aber sobald Sie Schublade B öffnen, verändert sich Schublade A ein wenig.
Der "Symbiotische" Effekt: Jede Schublade enthält nicht nur einen Gegenstand, sondern auch einen "Zeitstempel", der beweist, dass sie genau in dieser Reihenfolge geöffnet wurde. Man kann nicht einfach eine Schublade nachmachen, ohne den ganzen Weg dorthin neu zu gehen.

3. Warum können Grafikkarten (GPUs) nicht gewinnen?

Das ist das Geniale an PoSME:

Grafikkarten sind wie riesige Schwärme von Ameisen: Sie können tausende Dinge gleichzeitig tun, aber sie sind langsam, wenn sie nacheinander Dinge tun müssen, die voneinander abhängen.
Der Flaschenhals ist das Warten: Um die nächste Schublade zu finden, muss der Computer warten, bis der Speicher (RAM) die Daten liefert. Das dauert etwa 50 Nanosekunden. Das ist wie das Warten auf eine Pizza, die erst gebacken werden muss.
Das Ergebnis: Selbst eine super-teure Grafikkarte muss warten, bis die Pizza fertig ist. Ein normaler Laptop muss auch warten. Da das Warten der langsamste Teil ist, sind beide fast gleich schnell. Die Grafikkarte ist hier sogar 14- bis 19-mal langsamer als ein normaler Computer, weil sie für das "Warten" nicht gebaut ist.

4. Warum sind teure Spezial-Chips (ASICs) machtlos?

Man könnte denken: "Bauen wir einen Chip, der nur darauf spezialisiert ist, diese Schubladen zu öffnen!"

Das physikalische Limit: Selbst der schnellste Chip der Welt kann nicht schneller sein als die Zeit, die ein elektrisches Signal braucht, um vom Prozessor zum Speicher und zurück zu fliegen. Das ist wie der Unterschied zwischen einem Sportwagen und einem LKW: Der Sportwagen ist schneller, aber wenn die Straße (der Speicher) nur so breit ist, dass nur ein Auto hindurchpasst, bringt die Geschwindigkeit nichts.
Der Preis: Um einen Chip zu bauen, der nur 30% schneller ist als ein normaler Laptop, müsste man Millionen investieren. Das lohnt sich wirtschaftlich nicht. PoSME macht den Wettbewerb also "fair" durch reine Physik.

5. Was bringt uns das?

PoSME ist wie ein unfälschbarer Zeitstempel:

Für Kryptowährungen: Es verhindert, dass Reiche mit teuren Farmen das Netzwerk kontrollieren (Sybil-Resistenz).
Für Urheberrechte: Es kann beweisen, dass ein Text oder eine Idee wirklich zu einem bestimmten Zeitpunkt erstellt wurde und nicht nachträglich gefälscht wurde.
Für Verzögerungen: Es garantiert, dass eine bestimmte Aufgabe wirklich eine bestimmte Zeit gedauert hat, egal wie stark die Hardware ist.

Zusammenfassung in einem Satz

PoSME ist ein digitales Rätsel, das so konstruiert ist, dass man es nicht schneller lösen kann, indem man mehr Rechenpower oder teure Spezialchips benutzt; man muss einfach nur warten und Speicher nutzen, genau wie ein normaler Mensch mit einem normalen Laptop. Es macht den Wettbewerb fair, indem es die Physik des Speichers zum Richter macht.

1. Problemstellung

Viele kryptografische Systeme benötigen den Nachweis, dass eine Partei eine anhaltende, sequenzielle Berechnung unter konkreten Ressourcenbeschränkungen durchgeführt hat. Dies ist essenziell für:

ASIC-resistentes Mining.
Nachweis der Urheberschaft (Authorship Attestation).
Sybil-Resistenz.
Verifizierbare Verzögerung (Verifiable Delay).

Bestehende Primitive decken jedoch nur Teilaspekte ab:

VDFs (Verifiable Delay Functions): Zertifizieren sequenzielle Zeit, ignorieren aber den Speicherbedarf. ASICs können hier durch schnellere ALUs willkürliche Geschwindigkeitsvorteile erzielen.
PoSW (Proofs of Sequential Work): Beweisen das Durchlaufen eines Graphen, nutzen aber statischen, unveränderlichen Speicher.
MHFs (Memory-Hard Functions, z.B. Argon2id): Erhöhen die Kosten durch Speicherdruck, sind aber meist „Single-Shot"-Primitive ohne Kettensystem und bieten nur einen begrenzten ASIC-Schutz (8–16×).

Es fehlt eine primitive, die sequenzielle Schritte, Speicherhärte, veränderlichen Zustand (Mutability) und einen effizienten Verifizierungsmechanismus ohne vertrauenswürdige Einrichtung (Trusted Setup) kombiniert.

2. Methodik: PoSME-Konstruktion

PoSME (Proof of Sequential Memory Execution) löst dieses Problem durch eine neuartige Architektur, die auf drei Kernprinzipien basiert:

A. Datenabhängiges Pointer Chasing

Der Speicheradressen für den nächsten Lesevorgang hängen vom Wert des aktuellen Lesevorgangs ab. Dies erzwingt eine strikte sequenzielle Kette, die nicht parallelisiert werden kann.

Arena: Ein veränderlicher Speicherbereich (Arena) mit $N$ Blöcken, abgebildet auf einen booleschen Hyperwürfel ( $N=2^{d_{hc}}$ ).
Schritt-Funktion: In jedem Schritt $t$ werden $d$ Blöcke sequenziell gelesen. Die Adresse des nächsten Blocks wird durch Hashing des vorherigen Cursors und des gelesenen Datenwerts bestimmt.

B. Veränderlicher Arena-Zustand (Mutable State)

Im Gegensatz zu statischen Graphen ändert sich der Zustand der Arena bei jedem Schritt.

In-Place-Modifikation: Gelesene Blöcke werden sofort überschrieben.
Konsequenz: Ein Angreifer, der einen Block aus dem Speicher verwirft, kann ihn nicht einfach neu berechnen, da der neue Wert von der gesamten vorherigen Schreibhistorie abhängt. Eine Neu-Berechnung erfordert das Replay der gesamten Schreibkette.

C. Symbiotische Kausale Hash-Bindung

Jeder Schreibvorgang bindet den Datenwert und einen „kausalen Hash" (Zeithistorie) untrennbar aneinander.

Bidirektionale Abhängigkeit: Der neue Datenwert enthält den alten kausalen Hash, und der neue kausale Hash enthält den Cursor.
Sicherheit: Ein Angreifer kann keinen einzelnen Block fälschen, ohne auch die gesamte kausale Abstammungslinie zu fälschen. Dies verdoppelt die Kosten für Neu-Berechnungen bei Cache-Misses (Faktor 2).

D. Verifizierungsmodi

Klassischer Modus: Nutzt Fiat-Shamir und Merkle-Bäume. Die Beweisgröße skaliert mit der Rekursionstiefe $R$ und der Anzahl der Herausforderungen $Q$ (ca. 8–70 MB).
IVC-Modus (Incrementally Verifiable Computation): Nutzt binäre Feld-Faltung (Binius). Dies ermöglicht eine konstante Beweisgröße ( $O(1)$ ) von wenigen Kilobytes, unabhängig von der Schrittzahl $K$ , indem jeder Schritt in einen akkumulierten Beweis „gefaltet" wird.

3. Schlüsselbeiträge

Neue Konstruktion: PoSME ist das erste Primitive, das veränderlichen Arena-Zustand, datenabhängiges Pointer-Chasing und symbiotische kausale Bindung kombiniert.
Raum-Zeit-Sicherheit: Es wird eine formale untere Schranke für das Produkt aus Speicher ( $S$ ) und Zeit ( $T$ ) bewiesen: $S \cdot T = \Omega(K^2)$ . Dies gilt auch für adaptive Angreifer und dynamische kausale DAGs.
Validierung der Random Oracle (ROM): Die Annahme einer gleichmäßigen Verteilung der Adressen wird mathematisch und empirisch (bei $N=2^{24}$ , 5,4 Milliarden Lesevorgängen) bestätigt ( $\chi^2/df \approx 1,0004$ ).
Hardware-Validierung: Tests auf 17 CPU- und 4 GPU-Plattformen zeigen, dass GPUs bei dieser Arbeit 14–19-mal langsamer sind als Consumer-CPUs.
IVC-Arithmetisierung: Ein konkreter Entwurf für Binius (144.512 boolesche Constraints pro Schritt) ermöglicht effiziente Faltung ohne Bit-Zerlegung.

4. Ergebnisse und Leistungsbewertung

Hardware-Leistung und ASIC-Resistenz

Latenz-Bindung: Der Flaschenhals ist die DRAM-Zufallszugriffs-Latenz (40–50 ns), nicht die Hash-Berechnung (ca. 3 ns, < 3,5 % der Kosten).
GPU-Nachteile: GPUs sind für sequenzielle Pointer-Chasing-Aufgaben ungeeignet. Ihre hohe Bandbreite ist irrelevant, da die Aufgabe latenzgebunden ist. Zudem wird der Durchsatz durch die VRAM-Kapazität begrenzt (Capacity-Bound), nicht durch die Bandbreite.
ASIC-Vorteil: Der potenzielle Vorteil von ASICs wird auf ca. 2× begrenzt (basierend auf dem physikalischen Unterschied zwischen DDR5 und HBM3 Latenz), im Gegensatz zu 8–16× bei Argon2id. Ein 1,3× Vorteil für HBM3-basierte ASICs ist wirtschaftlich irrational, da keine kommerziellen ASICs für sequenzielle Kernen existieren.

Speicherkomplexität (TMTO)

Bei einer Schreibdichte $\rho = 4$ (jeder Block wird im Durchschnitt 4-mal überschrieben) und ohne Speicher ( $\alpha=0$ ) beträgt der Zeitstrafe-Faktor 10× im Vergleich zum ehrlichen Prover.
Selbst bei Speicherung von 87,5 % des Speichers ( $\alpha=7/8$ ) führt die „temporale Staleness" (Veraltetheit gespeicherter Daten durch Neu-Schreiben) zu einer exponentiellen Steigerung der Neu-Berechnungskosten.

Verifizierung

Klassisch: $O(Q \cdot d^R \cdot \log N)$ Hash-Operationen.
IVC: $O(1)$ Feldoperationen. Die Faltung kann parallelisiert werden (3 Threads auf AVX-512), um mit der Pointer-Chase-Latenz Schritt zu halten.

5. Bedeutung und Fazit

PoSME schließt eine kritische Lücke in der Kryptografie, indem es die Vorteile von VDFs, PoSW und MHFs vereint, ohne deren Nachteile zu haben.

Einzigartige Eigenschaften: Es erzwingt gleichzeitig sequenzielle Speicher-Schritte, bietet hohe TMTO-Resistenz (10×) und begrenzt den ASIC-Vorteil auf das physikalische Limit des Speichers (Latenz), nicht auf Rechengeschwindigkeit.
Anwendungen: PoSME bildet die Grundlage für verifizierbare Verzögerungen, Urheberschaftsnachweise und Sybil-Resistenz in dezentralen Systemen.
Zukunftsaussichten: Die binäre Feld-Struktur ist kompatibel mit zukünftigen „Processing-in-Memory"-Architekturen, was die Latenzgrenze weiter senken könnte.

Zusammenfassend bietet PoSME einen robusten, vertrauenslosen Nachweis für sequenzielle Arbeit, der durch die physikalischen Grenzen des Speichers (DRAM-Latenz) geschützt ist und damit eine neue Ära der ASIC-resistenten und speicherharten Kryptografie einleitet.