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

1. Il Problema

Esiste una necessità critica in vari sistemi (mining ASIC-resistant, attestazione dell'autore, resistenza ai Sybil, ritardi verificabili) di provare che una parte ha eseguito un calcolo sequenziale sostenuto sotto vincoli di risorse concreti. Le primitive crittografiche esistenti presentano lacune significative:

• VDF (Verifiable Delay Functions): Certificano il tempo sequenziale ma sono insensibili alla memoria; un ASIC può accelerarle arbitrariamente tramite ALU più veloci.
• PoSW (Proofs of Sequential Work): Dimostrano la traversa di un grafo ma su memoria statica e immutabile.
• MHF (Memory-Hard Functions): Come Argon2id, aumentano il costo per valutazione tramite pressione sulla memoria, ma sono primitive "single-shot" senza un sistema di prova a catena.

Comporre queste primitive non risolve il problema perché le loro proprietà non si rafforzano a vicenda. Manca un primitivo che combini stato mutabile, indirizzamento dipendente dai dati e vincoli di latenza per limitare l'efficienza degli ASIC.

2. Metodologia e Costruzione (PoSME)

Il paper introduce PoSME (Proof of Sequential Memory Execution), una primitiva crittografica che enforces la computazione sequenziale tramite "pointer chasing" (inseguimento di puntatori) vincolato alla latenza su un'arena mutabile.

Principi Chiave di Design:

1. Pointer Chasing Dipendente dai Dati: L'indirizzo di ogni lettura successiva dipende dal valore della lettura corrente. Questo crea una catena sequenziale stretta che non può essere parallelizzata.
2. Arena Mutabile: A differenza dei grafi statici, l'arena evolve ad ogni passo. Ricalcolare un blocco espulso richiede di riprodurre la sua catena di scrittura, rendendo lo stoccaggio dell'arena necessario.
3. Legame Causale Symbiotico: Ogni scrittura vincola il valore dei dati e la sua cronologia di scrittura temporale (hash causale) in modo reciproco. Un attaccante non può falsificare un blocco senza falsificare l'intera sua discendenza causale.

Architettura Tecnica:

• Arena Ipercubica: L'arena è mappata su un ipercubo booleano di dimensione $d_{hc}$ ($N = 2^{d_{hc}}$).
• Funzione Step: Ogni passo esegue $d$ letture sequenziali. L'indirizzo è derivato dall'hash dell'output precedente. Dopo le letture, un blocco viene modificato "in-place" (symbiotic bind) aggiornando sia il dato che l'hash causale.
• Vincolo di Latenza: Il collo di bottiglia è la latenza di accesso casuale alla DRAM (40-50 ns su DDR5), non la larghezza di banda. Il calcolo dell'hash (BLAKE3) richiede solo ~3 ns (<3.5% del costo totale), rendendo l'ottimizzazione hardware basata sulla velocità di calcolo inefficace.
• Verifica Efficiente:
  • Modo Classico: Utilizza prove di Merkle e Fiat-Shamir (dimensione della prova scalabile).
  • Modo IVC (Incrementally Verifiable Computation): Sfrutta la struttura a campo binario e il folding (tramite Binius) per ottenere una prova di dimensione costante $O(1)$, indipendentemente dal numero di passi $K$.

3. Contributi Chiave

1. Nuova Costruzione: PoSME è il primo primitivo a combinare stato mutabile, indirizzamento a pointer-chase e binding causale symbiotico, formalizzato su un ipercubo booleano.
2. Sicurezza Spazio-Tempo: Viene dimostrato un limite inferiore formale $S \cdot T = \Omega(K^2)$ per grafi causali dinamici. Questo significa che ridurre lo spazio di archiviazione porta a un aumento esponenziale del tempo di calcolo.
3. Validazione ROM: L'assunzione di uniformità della Random Oracle (ROM) è validata matematicamente e empiricamente su scala di produzione ($N=2^{24}$, 5.4 miliardi di letture), con statistiche $\chi^2$ indistinguibili dalla perfetta uniformità.
4. Validazione Hardware: Test su 17 piattaforme CPU e 4 architetture GPU dimostrano che l'hardware GPU è 14-19 volte più lento delle CPU consumer per questo carico di lavoro.
5. Resistenza ASIC: Il vantaggio degli ASIC è limitato a circa 2x (dovuto alla fisica della DRAM e non alla velocità di calcolo), contro i 8-16x di funzioni come Argon2id.

4. Risultati Sperimentali e Analisi

• Performance CPU vs GPU:
  • Le GPU (anche H100, A100) sono drasticamente più lente (fattore 14-19x) rispetto alle CPU consumer (es. Apple M-series, Intel/AMD) perché il collo di bottiglia è la latenza di accesso casuale, non la larghezza di banda.
  • Le GPU soffrono di un "collo di bottiglia di capacità": la VRAM limitata impedisce di eseguire molte istanze in parallelo per compensare la latenza.
• Resistenza Time-Memory Tradeoff (TMTO):
  • Con un parametro di densità di scrittura $\rho=4$, un attaccante che non memorizza l'arena subisce un penalty di 10x nel tempo di calcolo rispetto a chi la memorizza.
  • L'analisi introduce il concetto di "Temporal Staleness": anche se un attaccante memorizza il 95% dell'arena, i dati diventano obsoleti a causa delle riscritture casuali, aumentando esponenzialmente il costo di ricalcolo.
• Verifica:
  • La verifica classica richiede ~6 ms su desktop.
  • La verifica IVC (folding) è $O(1)$ e richiede solo poche kilobyte di prova, rendendo il sistema scalabile per clienti leggeri.

5. Significato e Implicazioni

PoSME colma un vuoto fondamentale nella crittografia delle prove di lavoro sequenziale:

• Democrazia Hardware: Livella il campo di gioco rendendo le CPU consumer più efficienti delle GPU e degli ASIC per questo specifico compito, grazie alla dipendenza dalla latenza della memoria DRAM.
• Fondazione per Applicazioni: Fornisce una base per:
  • Ritardi Verificabili (VDF): Se combinato con wrapper esterni (es. TEE o beacon di casualità).
  • Attestazione dell'Autore: Prova che un contenuto è stato generato sequenzialmente nel tempo.
  • Resistenza Sybil: Impedisce la creazione di identità multiple a basso costo.
• Sicurezza Dinamica: Risolve il problema teorico dei grafi causali dinamici, fornendo limiti di sicurezza rigorosi per strutture di memoria che cambiano durante l'esecuzione, un'area precedentemente non coperta dalle analisi di complessità cumulativa della memoria (CMC) statiche.

In sintesi, PoSME rappresenta un avanzamento significativo verso primitive di prova di lavoro che sono intrinsecamente resistenti all'accelerazione hardware massiccia, spostando il vincolo di sicurezza dalla potenza di calcolo alla fisica della memoria.