💻 computer science

A Complexity-Theoretic Approach to Proofs of Space

Dieses Paper präsentiert ein elementares Framework für die Konstruktion sicherer Proofs of Space (PoS), ohne sich auf das Random-Oracle-Modell zu verlassen, und zeigt auf, dass solche Protokolle aus einer Kombination von Standard-Kryptographie-Annahmen (wie kollisionsresistenten Hashfunktionen oder SNARGs) und spezifischen Derandomisierungs-Komplexitätsannahmen aufgebaut werden können.

Ursprüngliche Autoren: Marshall Ball, Jiaxin Guan

Veröffentlicht 2026-08-11

📖 7 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Marshall Ball, Jiaxin Guan

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

Der große digitale Speicher-Raubüberfall

Stellen Sie sich eine Welt vor, in der Sie beweisen können, dass Sie eine riesige Bibliothek an Büchern besitzen, ohne jemals eine einzige Seite zeigen zu müssen. Dies ist der Kern von Proofs of Space (Speicherbeweisen), einem Konzept aus dem Bereich der Kryptographie und Informatik. Es ist wie ein digitaler Vermieter, der sicherstellen möchte, dass ein Mieter tatsächlich ein Lagerhaus voller Möbel besitzt und nicht nur eine geschickte Zeichnung von Möbeln. Der Vermieter (der Verifizierer) muss sicher sein, dass der Mieter (der Prover/Beweiser) eine enorme Menge an permanentem Speicher verwendet, um Daten zu speichern, anstatt nur eine kleine Notiz aufzubewahren, auf der steht „Ich habe die Möbel“, und diese Möbel dann magisch heraufzubeschwören, sobald man danach fragt.

Jahrelang basierte der einzige Weg, diese digitalen Lagerhäuser zu bauen, auf einem magischen, imaginären Werkzeug namens „Random Oracle“ (Zufallsorakel). Stellen Sie sich dies als eine magische Blackbox vor, die jedes Mal, wenn man eine Frage stellt, perfekt zufällige, unvorhersehbare Antworten ausspuckt. Während dies für die Theorie nützlich ist, ist es so, als würde man ein Haus auf einem Fundament aus reiner Magie bauen; wir wissen nicht, ob es in der realen Welt standhalten würde. Die große Frage für Wissenschaftler war: Können wir einen sicheren Proof of Space unter Verwendung der echten, physischen Gesetze des Computings aufbauen, ohne uns auf magische Boxen zu verlassen? Dieses Paper taucht genau in diese Frage ein und nutzt die Werkzeuge der Komplexitätstheorie – der Lehre davon, wie schwer Probleme zu lösen sind – um zu sehen, ob wir diese Beweise von Grund auf konstruieren können.

Die große Idee des Papers: Der „tiefe“ String

Die Autoren, Marshall Ball und Jiaxin Guan, präsentieren einen neuen, elementaren Rahmen für den Aufbau von Proofs of Space ohne Magie. Ihr Hauptergebnis ist, dass man diese Beweise erstellen kann, wenn man zwei spezifische Zutaten hat: eine kryptographische Annahme (wie kollisionsresistente Hash-Funktionen) und eine „Derandomisierungs“-Annahme (den Glauben daran, wie schwer bestimmte Computerprobleme für leistungsstarke, nicht-deterministische Maschinen sind).

Um ihren Trick zu verstehen, stellen Sie sich vor, Sie müssten beweisen, dass Sie einen riesigen, unordentlichen Haufen Sand (die Daten) besitzen. Der alte Weg erforderte eine magische Box, um zu garantieren, dass der Sand nicht komprimierbar ist. Die Autoren erkennen, dass wir in der realen Welt nicht benötigen, dass der Sand unmöglich zu komprimieren ist; wir müssen nur sicherstellen, dass es schwer ist, ihn schnell zu komprimieren.

Sie führen das Konzept der Computational Depth (rechnerischen Tiefe) ein. Betrachten Sie einen String von Daten wie eine Geschichte:

Das Setup: Der Prover nimmt einen winzigen Seed (eine kurze Zusammenfassung der Geschichte) und verbringt eine lange Zeit (Phase 1), um ihn in einen massiven, detaillierten Roman (die Daten) zu expandieren.
Der Haken: Der Verifier fragt dann nach spezifischen Seiten aus diesem Roman.
Die Falle: Wenn der Prover den ganzen Roman nicht tatsächlich geschrieben und stattdessen nur die kurze Zusammenfassung aufbewahrt hat, müsste er die Seiten von Grund auf neu schreiben. Aber der Verifier gibt ihm nur eine winzige Menge Zeit (Phase 2), um dies zu tun.

Die Autoren zeigen, dass man – sofern man annimmt, dass bestimmte harte Probleme existieren (speziell, dass einige Probleme zu schwer für „nicht-deterministische“ Schaltkreise sind, um sie schnell zu lösen) – eine Funktion erstellen kann, die einen kurzen Seed in einen langen String verwandelt. Dieser String ist „tief“: Er kann aus einem kurzen Seed generiert werden, wenn man viel Zeit hat, aber er kann nicht aus einem kurzen Seed rekonstruiert werden, wenn man es eilig hat. Es ist wie ein Rätsel, für dessen Lösung man ein Jahr braucht, das man aber in einer Minute überprüfen kann; wenn man versucht, es in einer Minute zu lösen, schafft man es einfach nicht.

Wie der Beweis funktioniert: Der „Merkle-Baum“ und der „Zauberspruch“

Das Paper skizziert ein zweistufiges Protokoll, um diese „Tiefe“ zu testen.

Phase 1: Das Setup (Das lange Warten)
Der Verifier sendet einen zufälligen Seed an den Prover. Der Prover verbringt eine lange Zeit (sagen wir, Stunden), um mit seiner speziellen „tiefen“ Funktion diesen Seed in eine massive Datei aus Daten zu verwandeln. Er baut dann einen Merkle-Baum über diese Daten. Stellen Sie sich den Merkle-Baum als digitalen Fingerabdruck der gesamten Datei vor. Es ist wie ein Stammbaum, bei dem jedes Blatt ein Datenteil ist und jeder Zweig ein Hash (ein einzigartiger digitaler Fingerabdruck) der zwei darunter liegenden Zweige ist. Ganz oben steht ein einzelner „Root“-Hash, der die gesamte Datei repräsentiert. Der Prover speichert diese massive Datei und den Root.

Phase 2: Die Prüfung (Das schnelle Quiz)
Der Verifier fragt plötzlich nach spezifischen Seiten aus der Datei (zufällige Indizes). Der Prover muss diese Seiten schnell bereitstellen und den „Pfad“ durch den Merkle-Baum liefern, der beweist, dass diese Seiten zum ursprünglichen File gehören.

Hier zeigt sich die Cleverness der Autoren. Um den Prover daran zu hindern, das Protokoll zu umgehen (indem er einfach den kurzen Seed behält und versucht, die Seiten zu erraten), fügen sie ein Succinct Argument (ein kurzes Argument/Beweis) hinzu.

Option A (Die stärkere Annahme): Sie verwenden einen „SNARG“ (einen sehr kurzen, nicht-interaktiven Beweis), um zu beweisen, dass der Root-Hash tatsächlich aus der durch den Seed generierten Datei stammt. Dies erfordert eine starke Annahme über die Existenz bestimmter kryptographischer Werkzeuge, hält aber den Speicher-Overhead gering.
Option B (Die schwächere Annahme): Sie verwenden ein „Kilian-Stil“-Argument, das auf kollisionsresistenten Hash-Funktionen basiert. Dies ist eine standardmäßigere, „sicherere“ Annahme, zwingt den ehrlichen Prover jedoch dazu, etwas mehr Daten (einen „PCP“-String) zu speichern, um zu beweisen, dass der Merkle-Baum korrekt aufgebaut wurde.

Was sie ausschließen und was sie beweisen

Das Paper argumentiert explizit gegen die Vorstellung, dass Proofs of Space zwingend auf dem Random-Oracle-Modell basieren müssen. Sie zeigen, dass die „magische Box“ nicht notwendig ist. Stattdessen beweisen sie, dass Proofs of Space möglich sind, sofern wir die „Derandomisierungs-Annahme“ akzeptieren (dass manche Probleme zu schwer für nicht-deterministische Schaltkreise sind).

Sie adressen auch eine spezifische Art des Versuchs, das Protokoll zu umgehen: Was, wenn der Prover nur ein winziges Stück an Daten speichert und versucht, die große Datei „on the fly“ zu komprimieren? Die Autoren beweisen, dass, falls der Prover den Verifier davon überzeugen kann, das Protokoll zu akzeptieren, er eine signifikante Menge an Daten gespeichert haben muss. Speziell zeigen sie, dass ein Prover, der versucht das Protokoll zu umgehen, nicht wesentlich weniger Daten speichern kann als der ehrliche Prover (z. B. wenn der ehrliche Prover $N$ Bits speichert, kann ein Prover, der versucht das Protokoll zu umgehen, nicht viel weniger als $N$ Bits speichern, abhängig der spezifischen Konstruktion).

Das Fazit

Dieses Paper behauptet nicht, ein kommerzielles Produkt gebaut zu haben, das heute bereit für Ihr Smartphone ist. Stattdessen liefert es einen theoretischen Bauplan. Es demonstriert, dass die „unmögliche“ Aufgabe, zu beweisen, dass man ein Lagerhaus voller Daten besitzt, ohne Magie zu nutzen, tatsächlich möglich ist – vorausgesetzt, wir akzeptieren bestimmte Standard-Annahmen über die Schwierigkeit von Computerproblemen.

Sie zeigen:

Es funktioniert: Man kann diese Beweise mithilfe von „Computational Depth“ statt Magie erstellen.
Es ist effizient: Der ehrliche Nutzer muss nichts allzu Abwegiges tun, obwohl er die Daten speichern muss.
Es ist sicher: Wenn jemand versucht, das Protokoll durch weniger Datenspeicherung zu umgehen, besagt die Mathematik, dass er höchstwahrscheinlich erwischt wird, sofern die zugrunde liegenden harten Probleme weiterhin hart bleiben.

Kurz gesagt: Ball und Guan haben den „Proof of Space“ aus der Sphäre der magischen Blackboxes geholt und fest im Boden der Komplexitätstheorie verankert. Sie zeigen uns, dass wir mit den richtigen Annahmen digitale Lagerhäuser bauen können, die so sicher sind, wie es die Gesetze der Berechnung erlauben.

Technisches Resümee: Ein komplexitätstheoretischer Ansatz für Proofs of Space

Problemstellung
Proofs of Space (PoS), eingeführt von Dziembowski et al. [DFKP15], sind zweiphasige Protokolle, die es einem Prover ermöglichen, einen effizienten Verifier davon zu überzeugen, dass er eine signifikante Menge an persistentem Speicher allokiert hat. Das Protokoll besteht aus einer Initialisierungsphase (lange Dauer), in der der Prover Daten speichert, und einer Ausführungsphase (kurze Dauer), in der der Verifier den Prover herausfordert, den Nachweis zu erbringen, dass die Daten noch gespeichert sind.

Eine kritische Einschränkung bestehender PoS-Protokolle ist, dass ihre Sicherheitsbeweise stark auf dem Random Oracle Model (ROM) oder ad-hoc kryptographischen Annahmen beruhen. Speziell hängen sie von der simultanen Inkompressibilität und Extrahierbarkeit von Random-Oracle-Abfragen ab. Bis heute sind keine Konstruktionen bekannt, die im Plain Model (ohne Random Oracles) allein auf Basis standardmäßiger kryptographischer Annahmen sicher sind. Es mangelt an sauberen, falsifizierbaren Annahmen bezüglich kryptographischer Hash-Funktionen, die für die beweisbare Sicherheit dieser Konstruktionen ausreichen würden.

Methodik und Framework
Dieses Paper präsentiert ein elementares Framework zur Konstruktion von PoS im Plain Model durch die Kombination von Derandomisierungs-Annahmen mit kryptographischen Annahmen. Die zentrale Erkenntnis ist, dass ein PoS einen String $\sigma$ erfordert, der paradoxerweise sowohl komprimierbar aus einer kurzen Beschreibung (bei ausreichender Zeit $T$ ) als auch inkompressibel aus einer etwas kürzeren Beschreibung (innerhalb einer kurzen Zeit $t$ ) ist.

Die Autoren formalisieren dies mithilfe des komplexitätstheoretischen Begriffs der computational depth (berechnet durch Antunes et al. [AFvMV06]). Sie suchen eine Funktion $f$ mit hoher Computational Depth:

Langzeit-Komprimierbarkeit: $f(x)$ kann aus einem kurzen Seed $x$ in Zeit $T$ berechnet werden.
Kurzzeit-Inkompressibilität: $f(x)$ kann nicht aus einer kürzeren Beschreibung als $|f(x)|$ innerhalb der Zeit $t$ rekonstruiert werden, selbst wenn $x$ gegeben ist.

Die Konstruktion erfolgt in drei Hauptschritten:

Konstruktion von High-Depth-Funktionen:
Die Autoren nutzen Seed-extending Pseudorandom Generators (PRGs) gegen nicht-deterministische Distinguisher. Unter der Annahme, dass $E = \text{DTIME}[2^{O(n)}]$ exponentielle Größe nicht-deterministischer Schaltkreise erfordert (eine Standardannahme, um $\text{AM} = \text{NP}$ zu zeigen), konstruieren sie PRGs, die hart für nicht-deterministische Schaltkreise sind.
- Um eine überwältigende Wahrscheinlichkeit der Inkompressibilität (statt nur einer merklichen Fehlerrate) zu erreichen, verwenden sie multiplikative PRGs gegen nicht-deterministische Distinguisher. Diese bewahren die Wahrscheinlichkeit vernachlässigbarer Ereignisse, wodurch sichergestellt wird, dass der Output des PRG mit überwältigender Wahrscheinlichkeit inkompressibel bleibt.
- Um die approximative Inkompressibilität (Resilienz gegenüber Hamming-Distanz-Fehlern) zu handhaben, komponieren sie den PRG mit list-decodable error-correcting codes (ECC). Dies stellt sicher, dass selbst wenn ein Angreifer einen String rekonstruiert, der nahe an $f(x)$ liegt, der ursprüngliche String inkompressibel bleibt.
Das Extraction Lemma:
Ein zentraler technischer Beitrag ist das Extraction Lemma (Lemma 11). Es besagt, dass, falls ein Prover in der Lage ist, einen kleinen Zustand $S$ beizubehalten und Herausforderungen der Verifikation mit einer nicht-vernachlässigbaren Wahrscheinlichkeit erfolgreich zu beantworten, der zugrunde liegende String $y = f(x)$ annähernd komprimierbar ist.
- Das Lemma nutzt einen Hitting Set Generator (HSG), um deterministisch eine Menge von „nützlichen“ Challenge-Indizes auszuwählen, die einen großen Teil des gespeicherten Strings abdecken.
- Dies ermöglicht es einem Extractor, die meisten Bits von $y$ aus dem kleinen Zustand des Provers innerhalb der Zeit $t$ zu rekonstruieren, was im Widerspruch zur angenommenen Inkompressibilität von $f$ steht.
Protokoll-Instanziierung:
Das Framework wird in zwei spezifische PoS-Protokolle instanziiert, die sich in ihren kryptographischen Annahmen und dem Speicher-Overhead unterscheiden:
- Konstruktion 1 (SNARG-basiert): Verwendet einen Semi-Universal Non-Interactive Argument (SNARG) für $P$ . Der Prover speichert die Merkle-Root von $f(x)$ und einen prägnanten Beweis, dass die Root zu $f(x)$ gehört. Dies stützt sich auf die Existenz von SNARGs für $P$ (eine starke Annahme), bietet aber einen nahezu optimalen Speicherbedarf für den ehrlichen Prover ( $N$ Bits).
- Konstruktion 2 (Kilian-basiert): Verwendet Kilians interaktives Argumentationssystem basierend auf PCPs und Collision-Resistant Hash Functions (CRHF). Der Prover muss den PCP-String der Berechnung $f(x)$ speichern, was zu höheren ehrlichen Speicheranforderungen führt ( $N + \tilde{O}(T)$ ), aber auf schwächere kryptographische Annahmen (CRHF + Derandomisierung) zurückgreift.

Wichtigste Ergebnisse
Das Paper etabliert folgende Theoreme (informell):

Theorem 1: Unter der Annahme, dass $E$ hart für exponentielle Größe nicht-deterministischer Schaltkreise ist, existieren explizite Funktionen, die Zeit- $t$ inkompressibel zu Größe $N - O(\rho N \log(1/\rho))$ sind.
Theorem 2 (SNARG-Instanziierung): Unter der Annahme, dass $E$ hart für exponentielle Größe nicht-deterministischer Schaltkreise, One-Way Functions und ein semi-universeller SNARG für $P$ existieren, gibt es ein PoS, bei dem der ehrliche Prover $N$ Bits speichert und das Schema gegen jeden Prover sicher ist, der $(1-o(1))N$ Bits verwendet.
Theorem 3 (CRHF-Instanziierung): Unter der Annahme, dass $E$ hart für exponentielle Größe nicht-deterministischer Schaltkreise und Collision-Resistant Hash Functions existieren, gibt es ein PoS, bei dem der ehrliche Prover $N$ Bits speichert und das Schema gegen jeden Prover sicher ist, der $N^{1/c}$ Bits verwendet (für eine Konstante $c$ ).

Bedeutung und Ansprüche
Die Autoren betonen, dass ihre Arbeit ein pädagogisch klares, generisches Machbarkeitsergebnis für PoS im Plain Model liefert.

Durchbrechen der ROM-Barriere: Sie zeigen, dass PoS ohne Random Oracles konstruiert werden kann, indem stattdessen Standard-Derandomisierungs-Annahmen (Härte von $E$ gegen nicht-deterministische Schaltkreise) mit Standard-kryptographischen Primitiven kombiniert werden.
Trade-offs: Das Paper hebt den Trade-off zwischen kryptographischen Annahmen und Speichereffizienz hervor. Der SNARG-basierte Ansatz minimiert den Speicher des ehrlichen Provers, erfordert jedoch stärkere Annahmen. Der Kilian-basierte Ansatz nutzt schwächere Annahmen (CRHF), erfordert aber, dass der ehrliche Prover einen PCP der Berechnung speichert, was den Speicherbedarf erheblich erhöht.
Limitierungen: Die Autoren geben explizit an, dass ihr Fokus auf der theoretischen Machbarkeit liegt und nicht auf hoch entwickelten Bedrohungsmodellen oder praktischen Protokollen. Sie merken an, dass es nicht unmittelbar klar ist, wie diese Ideen zu konstruieren sind, um Memory-Hard Functions (MHFs) zu erzeugen – ein verwandtes Objekt, das oft aus ROM-basierten PoS abgeleitet wird. Zudem räumen sie ein, dass die Handhabung der Komposition (ein einzelner Prover, der mit vielen Verifiern interagiert) weitere Arbeit erfordert, um sicherzustellen, dass die Speicherkosten nicht amortisiert werden.

Zusammenfassend lässt sich sagen, dass diese Arbeit die Lücke zwischen Komplexitätstheorie und kryptographischen Protokollen schließt, indem sie zeigt, dass die für Proofs of Space erforderliche „Härte“ aus fundamentalen Derandomisierungs-Annahmen abgeleitet werden kann anstatt aus heuristischen Random-Oracle-Modellen.