💻 computer science

A Complexity-Theoretic Approach to Proofs of Space

Dit artikel presenteert een elementair raamwerk voor het construeren van veilige Proofs of Space (PoS) zonder te vertrouwen op het random oracle model, waarmee wordt aangetoond dat dergelijke protocollen gebouwd kunnen worden uit een combinatie van standaard cryptografische aannames (zoals botsingsbestendige hashfuncties of SNARGs) en specifieke derandomisatie complexiteitsaannames.

Oorspronkelijke auteurs: Marshall Ball, Jiaxin Guan

Gepubliceerd 2026-08-11

📖 7 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Marshall Ball, Jiaxin Guan

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

De Grote Digitale Opslagroof

Stel je een wereld voor waarin je kunt bewijzen dat je een enorme bibliotheek aan boeken bezit zonder ooit een enkele pagina te laten zien. Dit is de kern van Proofs of Space, een concept binnen het vakgebied van de cryptografie en informatica. Het is als een digitale huisbaas die wil controleren of een huurder daadwerkelijk een magazijn vol meubels heeft, en niet slechts een slimme tekening van meubels. De huisbaas (de Verifier) moet er zeker van zijn dat de huurder (de Prover) een enorme hoeveelheid persistent geheugen gebruikt om data op te slaan, in plaats van alleen een klein briefje bij te houden met de tekst "ik heb de meubels" en die meubels vervolgens magisch te toveren wanneer erom wordt gevraagd.

Jarenlang vertrouwde de enige manier om deze digitale magazijnen te bouwen op een magisch, denkbeeldig hulpmiddel genaamd een "Random Oracle". Denk aan dit als een magische zwarte doos die telkens wanneer je een vraag stelt, een perfect willekeurig en onvoorspelbaar antwoord uitspuugt. Hoewel dit nuttig is voor de theorie, is het alsof je een huis bouwt op een fundament van pure magie; we weten niet of het in de echte wereld stand zou houden. De grote vraag voor wetenschappers was: Kunnen we een veilige Proof of Space bouwen met behulp van alleen echte, fysieke wetten van de informatica, zonder te vertrouwen op magische dozen? Dit artikel duikt in die exacte vraag, gebruikmakend van de instrumenten van de complexiteitstheorie — de studie van hoe moeilijk problemen op te lossen zijn — om te zien of we deze bewijzen vanaf de basis kunnen construeren.

Het Grote Idee van het Papier: De "Diepe" String

De auteurs, Marshall Ball en Jiaxin Guan, presenteren een nieuw, elementair kader voor het bouwen van Proofs of Space zonder magie. Hun belangrijkste bevinding is dat je deze bewijzen kunt creëren als je twee specifieke ingrediënten hebt: een cryptografische aanname (zoals botsingsbestendige hashfuncties) en een "derandomisatie"-aanname (het geloof in hoe moeilijk bepaalde computerproblemen zijn voor krachtige, niet-deterministische machines).

Om hun truc te begrijpen, stel je voor dat je moet bewijzen dat je een enorme, rommelige zandstapel (de data) hebt. De oude methode vereiste een magische doos om te garanderen dat het zand niet gecomprimeerd kon worden. De auteurs realiseren zich dat we in de echte wereld niet hoeven te eisen dat het zand onmogelijk te comprimeren is; we hebben alleen nodig dat het moeilijk is om snel te comprimeren.

Ze introduceren het concept Computationele Diepte. Denk aan een string van data als een verhaal.

De Opzet: De Prover neemt een kleine zaad (een korte samenvatting van een verhaal) en besteedt een lange tijd (Fase 1) aan het uitbreiden hiervan tot een enorme, gedetailleerde roman (de data).
De Catch: De Verifier vraagt vervolgens om specifieke pagina's uit die roman.
De Valstrik: Als de Prover de hele roman niet daadwerkelijk heeft geschreven en alleen de korte samenvatting heeft bewaard, zou hij de pagina's vanaf nul moeten herschrijven. Maar de Verifier geeft hem slechts een minimale hoeveelheid tijd (Fase 2) om dit te doen.

De auteurs laten zien dat, als we aannemen dat bepaalde moeilijke problemen bestaan (specifiek, dat sommige problemen te moeilijk zijn voor "niet-deterministische" circuits om snel op te lossen), je een functie kunt maken die een korte zaad in een lange string verandert. Deze string is "diep": deze kan gegenereerd worden uit een korte zaad als je de tijd hebt, maar kan niet gereconstrueerd worden uit een korte zaad als je haast hebt. Het is als een puzzel die een jaar duurt om op te lossen, maar slechts een minuut om te controleren; als je probeert de puzzel in een minuut op te lossen, lukt dat simpelweg niet.

Hoe het Bewijs Werkt: De "Merkle Tree" en de "Magische Toverspreuk"

Het papier beschrijft een tweestaps-protocol om deze "diepte" te testen.

Fase 1: De Opzet (Het Lange Wachten)
De Verifier stuurt een willekeurige zaad naar de Prover. De Prover besteedt een lange tijd (laten we zeggen uren) aan het gebruiken van hun speciale "diepe" functie om die zaad om te zetten in een enorm bestand met data. Ze bouwen vervolgens een Merkle Tree bovenop deze data. Stel je de Merkle Tree voor als een digitale vingerafdruk van het volledige bestand. Het is als een stamboom waarbij elk blad een stukje data is, en elke tak een hash (een unieke digitale vingerafdruk) van de twee takken eronder is. Helemaal bovenaan staat een enkele "Root" hash die het volledige bestand vertegenwoordigt. De Prover slaat dit enorme bestand en de Root op.

Fase 2: De Controle (De Snelle Quiz)
De Verifier vraagt plotseling om specifieke pagina's uit het bestand (willekeurige indices). De Prover moet die pagina's snel leveren, samen met het "pad" door de Merkle Tree dat bewijst dat die pagina's bij het originele bestand horen.

Hier blinkt de vindingrijkheid van de auteurs uit. Om de Prover te voorkomen dat hij het protocol probeert te omzeilen (door alleen de korte zaad te bewaren en de pagina's te proberen te raden), voegen ze een Succinct Argument toe (een kort bewijs).

Optie A (De Sterkere Aanname): Ze gebruiken een "SNARG" (een zeer kort, niet-interactief bewijs) om te bewijzen dat de Root hash daadwerkelijk afkomstig is van het bestand dat door de zaad is gegenereerd. Dit vereist een sterke aanname over het bestaan van bepaalde cryptografische instrumenten, maar houdt de opslagoverhead laag.
Optie B (De Zwakkere Aanname): Ze gebruiken een "Kilian-stijl" argument gebaseerd op botsingsbestendige hashfuncties. Dit is een meer standaard, "veiligere" aanname, maar dwingt de eerlijke Prover om iets meer data op te slaan (een "PCP" string) om te bewijzen dat de Merkle tree correct is opgebouwd.

Wat Ze Uitsluiten en Wat Ze Bewijzen

Het papier betoogt expliciet tegen het idee dat Proofs of Space moeten vertrouwen op het Random Oracle-model. Ze laten zien dat de "magische doos" niet noodzakelijk is. In plaats daarvan bewijzen ze dat, mits we de "derandomisatie-aanname" accepteren (dat sommige problemen moeilijk zijn voor niet-deterministische circuits), Proofs of Space mogelijk zijn.

Ze adresseren ook een specif kind van poging om het protocol te omzeilen: wat als de Prover een heel klein beetje data opslaat en probeert het grote bestand "on the fly" te comprimeren? De auteurs bewijzen dat als de Prover de Verifier ervan kan overtuigen dat het bewijs klopt, hij een aanzienlijke hoeveelheid data moet hebben opgeslagen. Specifiek laten ze zien dat een Prover die probeert het protocol te omzeilen, niet significant minder data kan opslaan dan de eerlijke prover (bijvoorbeeld: als de eerlijke prover $N$ bits opslaat, kan een Prover die het protocol probeert te omzeilen niet veel minder dan $N$ bits opslaan, afhankelijk van de specifieke constructie die wordt gebruikt).

De Kernboodschap

Dit papier beweert niet een commercieel product te hebben gebouwd dat vandaag al klaar is voor je smartphone. In plaats daarvan biedt het een theoretisch blauwdruk. Het demonstreert dat de "onmogelijke" taak om te bewijzen dat je een magazijn aan data bezit zonder magie, eigenlijk mogelijk is, mits we bepaalde standaard overtuigingen over de moeilijkheid van computerproblemen accepteren.

Ze laten zien dat:

Het werkt: Je kunt deze bewijzen bouwen met behulp van "computationele diepte" in plaats van magie.
Het efficiënt is: De eerlijke gebruiker hoeft niets te extreems te doen, hoewel hij de data wel moet opslaan.
Het veilig is: Als iemand probeert het protocol te omzeilen door minder data op te slaan, zegt de wiskunde dat hij bijna zeker betrapt zal worden, ervan uitgaande dat de onderliggende moeilijke problemen ook moeilijk blijven.

Kortom, Ball en Guan hebben de "Proof of Space" uit de sfeer van magische zwarte dozen gehaald en stevig geplant in de bodem van de complexiteitstheorie, waarmee ze ons laten zien dat we, met de juiste aannames, digitale magazijnen kunnen bouwen die zo veilig zijn als de wetten van de berekenbaarheid toelaten.

Technische Samenvatting: Een Complexiteitstheoretische Benadering van Proofs of Space

Probleemstelling
Proofs of Space (PoS), geïntroduceerd door Dziembowski et al. [DFKP15], zijn protocollen met twee fasen die een Prover in staat stellen een efficiënte Verifier te overtuigen dat het een aanzienlijke hoeveelheid persistente geheugen heeft gealloceerd. Het protocol bestaat uit een initialisatiefase (lange duur) waarin de Prover gegevens opslaat, en een executiefase (korte duur) waarin de Verifier de Prover uitdaagt om te bewijzen dat de gegevens nog steeds opgeslagen zijn.

Een kritieke beperking van bestaande PoS-protocollen is dat hun beveiligingsbewijzen zwaar leunen op het Random Oracle Model (ROM) of ad hoc cryptografische aannames. Specifiek zijn ze afhankelijk van de gelijktijdige oncomprimeerbaarheid en extraheerbaarheid van random oracle-queries. Tot op heden zijn er geen constructies bekend die veilig zijn in het plain model (zonder random oracles) op basis van enkel standaard cryptografische aannames. Er is een gebrek aan zuivere, falsifieerbare aannames met betrekking tot cryptografische hashfuncties die volstaan voor de bewijsbare veiligheid van deze constructies.

Methodologie en Raamwerk
Dit artikel presenteert een elementair raamwerk voor het construeren van PoS in het plain model door derandomisatie-aannames te combineren met cryptografische aannames. De kerninzicht is dat een PoS een string $\sigma$ vereist die paradoxaal genoeg zowel comprimeerbaar is vanuit een korte beschrijving (gegeven voldoende tijd $T$ ) als oncomprimeerbaar vanuit een iets kortere beschrijving (binnen een korte tijd $t$ ).

De auteurs formaliseren dit met het complexiteitstheoretische begrip computationele diepte (geïntroduceerd door Antunes et al. [AFvMV06]). Zij zoeken naar een functie $f$ met een hoge computationele diepte:

Lange-tijd compressibiliteit: $f(x)$ kan berekend worden vanuit een korte seed $x$ in tijd $T$ .
Korte-tijd oncomprimeerbaarheid: $f(x)$ kan niet gereconstrueerd worden vanuit een beschrijving die korter is dan $|f(x)|$ binnen tijd $t$ , zelfs niet gegeven $x$ .

De constructie verloopt in drie stappen:

Het construeren van High-Depth Functies:
De auteurs maken gebruik van seed-extenderende Pseudorandom Generators (PRGs) tegen niet-deterministische distinguishers. Onder de aanname dat $E = \text{DTIME}[2^{O(n)}]$ een exponentiële grootte vereist voor niet-deterministische circuits (een standaard aanname gebruikt om aan te tonen dat $\text{AM} = \text{NP}$ ), construeren zij PRGs die moeilijk zijn voor niet-deterministische circuits.
- Om een overweldigende waarschijnlijkheid van oncomprimeerbaarheid te bereiken (in plaats van slechts een merkbare fout), gebruiken zij multiplicatieve PRGs tegen niet-deterministische distinguishers. Deze behouden de waarschijnlijkheid van verwaarloosbare gebeurtenissen, waardoor de output van de PRG met overweldigende waarschijnlijkheid oncomprimeerbaar blijft.
- Om om te gaan met benaderde oncomprimeerbaarheid (resistentie tegen Hamming-afstandfouten), componeren zij de PRG met list-decodable error-correcting codes (ECC). Dit zorgt ervoor dat zelfs als een tegenstander een string dicht bij $f(x)$ herstelt, de oorspronkelijke string oncomprimeerbaar blijft.
De Extractie Lemma:
Een centrale technische bijdrage is de Extraction Lemma (Lemma 11). Deze stelt dat als een prover een kleine staat $S$ kan behouden en met een niet-verwaarloosbare waarschijnlijkheid succesvol antwoord geeft op verificatie-uitdagingen, de onderliggende string $y = f(x)$ ongeveer compressibel is.
- De lemma gebruikt een Hitting Set Generator (HSG) om deterministisch een verzameling "nuttige" challenge-indices te selecteren die een groot deel van de opgeslagen string dekken.
- Dit stelt een extractor in staat om de meeste bits van $y$ te herstellen uit de kleine staat van de prover binnen tijd $t$ , wat in tegenspraak is met de veronderstelde oncomprimeerbaarheid van $f$ .
Protocol Instantiatie:
Het raamwerk wordt geïnstantieerd in twee specifieke PoS-protocollen, die verschillen in hun cryptografische aannames en opslagoverhead:
- Constructie 1 (SNARG-gebaseerd): Gebruikt een Semi-Universal Non-Interactive Argument (SNARG) voor $P$ . De Prover slaat de Merkle-root van $f(x)$ op en een beknopt bewijs dat de root overeenkomt met $f(x)$ . Dit leunt op het bestaan van SNARGs voor $P$ (een sterke aanname), maar biedt bijna optimale opslag voor de eerlijke prover ( $N$ bits).
- Constructie 2 (Kilian-gebaseerd): Gebruikt Kilian's interactieve argument systeem gebaseerd op PCPs en Collision-Resistant Hash Functions (CRHF). De Prover moet de PCP-string van de berekening $f(x)$ opslaan, wat leidt tot hogere eerlijke opslagvereisten ( $N + \tilde{O}(T)$ ), maar leunt op zwakkere cryptografische aannames (CRHF + derandomisatie).

Belangrijkste Resultaten
Het artikel stelt de volgende stellingen vast (informeel):

Stelling 1: Uitgaande van de aanname dat $E$ moeilijk is voor exponentiële grootte niet-deterministische circuits, bestaan er expliciete functies die tijd- $t$ oncomprimeerbaar zijn tot grootte $N - O(\rho N \log(1/\rho))$ .
Stelling 2 (SNARG instantiatie): Uitgaande van de aanname dat $E$ moeilijk is voor exponentiële grootte niet-deterministische circuits, one-way functies, en een semi-universele SNARG voor $P$ , bestaat er een PoS waarbij de eerlijke prover $N$ bits opslaat, en het schema veilig is tegen elke prover die $(1-o(1))N$ bits gebruikt.
Stelling 3 (CRHF instantiatie): Uitgaande van de aanname dat $E$ moeilijk is voor exponentiële grootte niet-deterministische circuits en collision-resistant hash functies, bestaat er een PoS waarbij de eerlijke prover $N$ bits opslaat, en het schema veilig is tegen elke prover die $N^{1/c}$ bits gebruikt (voor een constante $c$ ).

Betekenis en Claims
De auteurs benadrukken dat hun werk een pedagogisch zuivere, generieke haalbaarheid biedt voor PoS in het plain model.

Het doorbreken van de ROM-barrière: Zij demonstreren dat PoS geconstrueerd kan worden zonder random oracles, door vertrouwen te stellen op standaard derandomisatie-aannames (hardheid van $E$ tegen niet-deterministische circuits) gecombineerd met standaard cryptografische primitieven.
Trade-offs: Het artikel belicht de trade-off tussen cryptografische aannames en opslagefficiëntie. De SNARG-gebaseerde aanpak minimaliseert de opslag van de eerlijke prover, maar vereist sterkere aannames. De Kilian-gebaseerde aanpak gebruikt zwakkere aannames (CRHF) maar vereist dat de eerlijke prover een PCP van de berekening opslaat, wat de opslag aanzienlijk verhoogt.
Beperkingen: De auteurs geven expliciet aan dat hun focus ligt op theoretische haalbaarheid, niet op geavanceerde dreigingsmodellen of praktische protocollen. Zij merken op dat het niet onmiddellijk duidelijk is hoe deze ideeën kunnen worden aangepast om Memory-Hard Functions (MHFs) te construeren, een gerelateerd object dat vaak uit ROM-gebaseerde PoS wordt afgeleid. Daarnaast erkennen zij dat het afhandelen van compositie (één enkele prover die met veel verifiers interacteert) verder werk vereist om te waarborgen dat de opslagkosten niet worden geamortiseerd.

Samenvattend overbrugt dit werk de kloof tussen complexiteitstheorie en cryptografische protocollen, door aan te tonen dat de "hardheid" die vereist is voor Proofs of Space kan worden afgeleid van fundamentele derandomisatie-aannames in plaats van heuristische random oracle-modellen.

De Grote Digitale Opslagroof

Het Grote Idee van het Papier: De "Diepe" String

Hoe het Bewijs Werkt: De "Merkle Tree" en de "Magische Toverspreuk"

Wat Ze Uitsluiten en Wat Ze Bewijzen

De Kernboodschap

Meer zoals dit