💻 computer science

A Complexity-Theoretic Approach to Proofs of Space

Questo articolo presenta un framework elementare per la costruzione di Proof of Space (PoS) sicure senza fare affidamento sul modello dell'oracolo casuale, dimostrando che tali protocolli possono essere costruiti combinando assunzioni crittografiche standard (come le funzioni hash resistenti alle collisioni o i SNARG) e specifiche assunzioni di complessità sulla derandomizzazione.

Autori originali: Marshall Ball, Jiaxin Guan

Pubblicato 2026-08-11

📖 7 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Marshall Ball, Jiaxin Guan

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Il Grande Furto del Deposito Digitale

Immaginate un mondo in cui potete dimostrare di possedere una biblioteca di libri immensa senza mai mostrare una singola pagina. Questo è il cuore delle Proof of Space (Prove di Spazio), un concetto nel campo della crittografia e dell'informatica. È come un proprietario immobiliare digitale che vuole assicurarsi che un inquilino abbia effettivamente un magazzino pieno di mobili, e non solo un disegno intelligente di mobili. Il proprietario (il Verificatore) deve essere sicuro che l'inquilino (il Prover) stia utilizzando una enorme quantità di memoria persistente per archiviare dati, invece di tenere solo un piccolo appunto che dice "ho i mobili" e poi far apparire magicamente i mobili solo quando richiesto.

Per anni, l'unico modo per costruire questi magazzini digitali si è basato su uno strumento magico e immaginario chiamato "Random Oracle" (Oracolo Casuale). Pensate a questo come a una scatola nera magica che sputa fuori risposte perfettamente casuali e imprevedibili ogni volta che fate una domanda. Sebbene utile per la teoria, è come costruire una casa su fondamenta di pura magia; non sappiamo se resisterebbe nel mondo reale. La grande domanda per gli scienziati è stata: possiamo costruire una Proof of Space sicura usando solo le leggi fisiche reali dell'informatica, senza fare affidamento su scatole magiche? Questo articolo si addentra proprio in questa domanda, usando gli strumenti della teoria della complessità — lo studio di quanto siano difficili i problemi da risolvere — per vedere se possiamo costruire queste prove partendo da zero.

La Grande Idea dell'Articolo: La Stringa "Profonda"

Gli autori, Marshall Ball e Jiaxin Guan, presentano un nuovo framework elementare per costruire Proof of Space senza magia. La loro scoperta principale è che potete creare queste prove se disponete di due ingredienti specifici: un'assunzione crittografica (come le funzioni hash resistenti alle collisioni) e un'assunzione di "derandomizzazione" (la convinzione di quanto siano difficili certi problemi informatici per macchine potenti e non deterministiche).

Per capire il loro trucco, immaginate di dover dimostrare di avere un enorme e disordinato mucchio di sabbia (i dati). Il vecchio metodo richiedeva una scatola magica per garantire che la sabbia non potesse essere compressa. Gli autori si rendono conto che, nel mondo reale, non abbiamo bisogno che la sabbia sia impossibile da comprimere; abbiamo solo bisogno che sia difficile da comprimere velocemente.

Introducono il concetto di Profondità Computazionale. Pensate a una stringa di dati come a una storia.

La Preparazione: Il Prover prende un piccolo seme (un breve riassunto della storia) e trascorre molto tempo (Fase 1) per espanderlo in un enorme e dettagliato romanzo (i dati).
L'Imprevisto: Il Verificatore chiede poi pagine specifiche da quel romanzo.
La Trappola: Se il Prover non ha scritto realmente tutto il romanzo e ha solo conservato il breve riassunto, dovrebbe riscrivere le pagine da zero. Ma il Verificatore gli concede solo un tempo brevissimo (Fase 2) per farlo.

Gli autori dimostrano che, se si assume l'esistenza di certi problemi difficili (specificamente, che alcuni problemi siano troppo difficili da risolvere rapidamente per circuiti "non deterministici"), si può creare una funzione che trasforma un breve seme in una lunga stringa. Questa stringa è "profonda": può essere generata da un breve seme se si ha molto tempo, ma non può essere ricostruita da un breve seme se si ha fretta. È come un puzzle che richiede un anno per essere risolto, ma solo un minuto per essere controllato; se provi a risolverlo in un minuto, semplicemente non ci riesci.

Come Funziona la Prova: L' "Albero di Merkle" e l' "Incantesimo Magico"

L'articolo delinea un protocollo in due fasi per testare questa "profondità".

Fase 1: La Preparazione (La Lunga Attesa)
Il Verificatore invia un seme casuale al Prover. Il Prover trascorre molto tempo (diciamo, ore) usando la sua speciale "funzione profonda" per trasformare quel seme in un enorme file di dati. Successivamente, costruisce un Albero di Merkle sopra questi dati. Immaginate l'Albero di Merkle come l'impronta digitale di un intero file. È come un albero genealogico dove ogni foglia è un pezzo di dato, e ogni ramo è un hash (un'impronta digitale unica) dei due rami sottostanti. In cima a tutto c'è un singolo "Root" (Radice) hash che rappresenta l'intero file. Il Prover memorizza questo enorme file e la Radice.

Fase 2: Il Controllo (Il Quiz Rapido)
Il Verificatore chiede improvvisamente alcune pagine specifiche dal file (indici casuali). Il Prover deve fornire rapidamente quelle pagine e il "percorso" attraverso l'Albero di Merkle che prova che quelle pagine appartengono al file originale.

È qui che l'arguzia degli autori brilla. Per impedire al Prover di tentare di aggirare il protocollo (ovvero conservando solo il breve seme e cercando di indovinare le pagine), aggiungono un Argomento Succinto (una prova breve).

Opzione A (L'Assunzione Più Forte): Usano un "SNARG" (una prova molto breve e non interattiva) per provare che la Radice hash inviata proviene effettivamente dal file generato dal seme. Ciò richiede un'assunzione forte sull'esistenza di certi strumenti crittografici, ma mantiene basso l'overhead di archiviazione.
Opzione B (L'Assunzione Più Debole): Usano un argomento in stile "Kilian" basato su funzioni hash resistenti alle collisioni. Questa è un'assunzione più standard, più "sicura", ma costringe il Prover onesto a memorizzare un po' più di dati (una stringa "PCP") per provare che l'albero di Merkle sia stato costruito correttamente.

Cosa Escludono e Cosa Dimostrano

L'articolo argomenta esplicitamente contro l'idea che le Proof of Space debbono necessariamente fare affidamento sul modello dell'Oracolo Casuale. Dimostrano che la "scatola magica" non è necessaria. Invece, dimostrano che, se accettiamo l'assunzione di derandomizzazione (che alcuni problemi siano difficili per i circuiti non deterministici), allora le Proof of Space sono possibili.

Affrontano anche un tipo specifico di tentativo di aggirare il protocollo: cosa succede se il Prover memorizza una piccolissima quantità di dati e cerca di "comprimere" il grande file al volo? Gli autori dimostrano che, se il Prover riesce a convincere il Verificatore ad accettare, deve aver memorizzato una quantità significativa di dati. Nello specifico, dimostrano che un Prover che tenta di aggirare il protocollo non può memorizzare significativamente meno dati rispetto al Prover onesto (ad esempio, se il Prover onesto memorizza $N$ bit, un Prover che tenta di aggirare il protocollo non può cavarsela memorizzando molto meno di $N$ bit, a seconda della specifica costruzione utilizzata).

In Sintesi

Questo articolo non sostiene di aver costruito un prodotto commerciale pronto per il vostro smartphone oggi. Inveve, fornisce un progetto teorico. Dimostra che l'impresa "impossibile" di dimostrare di possedere un magazzino di dati senza ricorrere alla magia è in realtà possibile, a patto di accettare certe assunzioni standard sulla difficoltà dei problemi informatici.

Dimostrano che:

Funziona: Si possono costruire queste prove usando la "profondità computazionale" invece della magia.
È efficiente: L'utente onesto non deve fare nulla di troppo folle, sebbene debba memorizzare i dati.
È sicura: Se qualcuno tenta di aggirare il protocollo memorizzando meno dati, la matematica dice che verrà quasi certamente scoperto, assumendo che i problemi difficili sottostanti rimangano tali.

In breve, Ball e Guan hanno portato la "Proof of Space" fuori dal regno delle scatole nere magiche e l'hanno piantata saldamente nel terreno della teoria della complessità, mostrandoci che, con le giuste assunzioni, possiamo costruire magazzini digitali sicuri quanto le leggi della computazione permettono.

Sintesi Tecnica: Un approccio basato sulla teoria della complessità alle Prove di Spazio

Enunciato del Problema
Le Prove di Spazio (PoS - Proofs of Space), introdotte da Dziembowski et al. [DFKP15], sono protocolli a due fasi che permettono a un Prover di convincere un Verificatore efficiente di aver allocato una quantità significativa di memoria persistente. Il protocollo consiste in una fase di inizializzazione (di lunga durata) in cui il Prover memorizza i dati, e una fase di esecuzione (di breve durata) in cui il Verificatore sfida il Prover a dimostrare che i dati sono ancora memorizzati.

Un limite critico degli esistenti protocolli PoS è che le loro prove di sicurezza si basano pesantemente sul Modello di Oracolo Casuale (ROM - Random Oracle Model) o su assunzioni crittografiche ad hoc. Nello specifico, esse dipendono dalla simultanea incomprimibilità ed estraibilità delle query all'oracolo casuale. Ad oggi, non si conoscono costruzioni che siano sicure nel modello "plain" (senza oracoli casuali) basandosi solo su assunzioni crittografiche standard. Esiste una mancanza di assunzioni pulite e falsificabili riguardanti le funzioni di hash crittografiche che siano sufficienti per la sicurezza dimostrabile di queste costruzioni.

Metodologia e Framework
Questo articolo presenta un framework elementare per costruire PoS nel modello plain combinando assunzioni di derandomizzazione con assunzioni crittografiche. L'intuizione centrale è che una PoS richiede una stringa $\sigma$ che sia paradossalmente sia comprimibile da una descrizione breve (dato un tempo sufficiente $T$ ) sia incomprimibile da qualsiasi descrizione leggermente più breve (entro un tempo $t$ ).

Gli autori formalizzano questo concetto utilizzando la nozione di profondità computazionale (introdotta da Antunes et al. [AFvMV06]). Essi cercano una funzione $f$ con alta profondità computazionale:

Comprimibilità a lungo termine: $f(x)$ può essere computata da un seed corto $x$ in tempo $T$ .
Incomprimibilità a breve termine: $f(x)$ non può essere ricostruita da alcuna descrizione più corta di $|f(x)|$ entro il tempo $t$ , anche dato $x$ .

La costruzione procede in tre fasi principali:

Costruzione di Funzioni ad Alta Profondità:
Gli autori utilizzano generatori di numeri pseudocasuali (PRG) di estensione del seed contro distinguuitori nondeterministici. Sotto l'assunzione che $E = \text{DTIME}[2^{O(n)}]$ richieda circuiti nondeterministici di dimensione esponenziale (un'assunzione standard usata per dimostrare $\text{AM} = \text{NP}$ ), essi costruiscono PRG che sono difficili per i circuiti nondeterministici.
- Per ottenere una probabilità schiacciante di incomprimibilità (anziché solo una probabilità non trascurabile), impiegano PRG moltiplicativi contro distinguuitori nondeterministici. Questi preservano la probabilità di eventi trascurabili, garantendo che l'output del PRG rimanga incomprimibile con probabilità schiacciante.
- Per gestire l'incomprimibilità approssimativa (resilienza agli errori di distanza di Hamming), compongono il PRG con codici correttori di errori (ECC) decodificabili in lista. Ciò assicura che anche se un avversario recupera una stringa vicina a $f(x)$ , la stringa originale rimanga incomprimibile.
Il Lemma di Estrazione:
Un contributo tecnico centrale è il Lemma di Estrazione (Lemma 11). Esso afferma che se un prover può mantenere uno stato piccolo $S$ e rispondere con successo alle sfide di verifica con probabilità non trascurabile, allora la stringa sottostante $y = f(x)$ è approssimativamente comprimibile.
- Il lemma utilizza un Generatore di Insiemi di Colpi (HSG - Hitting Set Generator) per selezionare deterministicamente un insieme di indici di sfida "utili" che coprano una grande frazione della stringa memorizzata.
- Ciò permette a un estrattore di recuperare la maggior parte dei bit di $y$ dal piccolo stato del prover entro il tempo $t$ , contraddicendo l'assunta incomprimibilità di $f$ .
Istanziazione del Protocollo:
Il framework viene istanziato in due specifici protocolli PoS, che differiscono per le loro assunzioni crittografiche e l'overhead di memorizzazione:
- Costruzione 1 (basata su SNARG): Utilizza un Argomento Non Interattivo Semi-Universale (SNARG - Semi-Universal Non-Interactive Argument) per $P$ . Il Prover memorizza la radice di Merkle di $f(x)$ e una prova succinta che la radice corrisponda a $f(x)$ . Questo si basa sull'esistenza di SNARG per $P$ (un'assunzione forte) ma offre una memorizzazione quasi ottimale per il prover onesto ( $N$ bit).
- Costruzione 2 (basata su Kilian): Utilizza l'argomento interattivo di Kilian basato su PCP e Funzioni di Hash Resistenti alle Collisioni (CRHF - Collision-Resistant Hash Functions). Il Prover deve memorizzare la stringa PCP della computazione $f(x)$ , portando a requisiti di memorizzazione onesta più elevati ( $N + \tilde{O}(T)$ ), ma si basa su assunzioni crittografiche più deboli (CRHF + derandomizzazione).

Risultati Chiave
L'articolo stabilisce i seguenti teoremi (informalmente):

Teorema 1: Assumendo che $E$ sia difficile per circuiti nondeterministici di dimensione esponenziale, esistono funzioni esplicite che sono incomprimibili nel tempo- $t$ per dimensione $N - O(\rho N \log(1/\rho))$ .
Teorema 2 (Istanziazione SNARG): Assumendo che $E$ sia difficile per circuiti nondeterministici di dimensione esponenziale, funzioni mono-direzionali e un SNARG semi-universale per $P$ , esiste una PoS dove il prover onesto memorizza $N$ bit, e lo schema è sicuro contro qualsiasi prover che utilizzi $(1-o(1))N$ bit.
Teorema 3 (Istanziazione CRHF): Assumendo che $E$ sia difficile per circuiti nondeterministici di dimensione esponenziale e funzioni resistenti alle collisioni, esiste una PoS dove il prover onesto memorizza $N$ bit, e lo schema è sicuro contro qualsiasi prover che utilizzi $N^{1/c}$ bit (per una costante $c$ ).

Significato e Rivendicazioni
Gli autori sottolineano che il loro lavoro fornisce un risultato di fattibilità generica e pedagogicamente pulito per le PoS nel modello plain.

Rompere la barriera del ROM: Dimostrano che le PoS possono essere costruite senza oracoli casuali, affidandosi invece a standard assunzioni di derandomizzazione (difficoltà di $E$ contro circuiti nondeterministici) combinate con standard primitivi crittografici.
Trade-off: Il articolo evidenzia il compromesso tra assunzioni crittografiche ed efficienza di memorizzazione. L'approccio basato su SNARG minimizza la memorizzazione del prover onesto ma richiede assunzioni più forti. L'approccio basato su Kilian utilizza assunzioni più deboli (CRHF) ma richiede al prover onesto di memorizzare un PCP della computazione, aumentando significativamente la memorizzazione.
Limitazioni: Gli autori dichiarano esplicitamente che il loro focus è sulla fattibilità teorica, non su modelli di minaccia sofisticati o protocolli pratici. Notano che non è immediatamente chiaro come adattare queste idee per costruire Funzioni di Difficoltà di Memoria (MHF - Memory-Hard Functions), un oggetto correlato spesso derivato da PoS basate su ROM. Inoltre, riconoscono che gestire la composizione (un singolo prover che interagisce con molti verificatori) richiede ulteriore lavoro per garantire che i costi di memorizzazione non si ammortizzino.

In sintesi, questo lavoro colma il divario tra la teoria della complessità e i protocolli crittografici, mostrando che la "difficoltà" richiesta per le Prove di Spazio può essere derivata da assunzioni fondamentali di derandomizzazione piuttosto che da euristici modelli di oracolo casuale.