OpenAI rivendica una svolta crittografica, nessuna minaccia immediata per Bitcoin
OpenAI sostiene che il suo sistema di intelligenza artificiale abbia confutato l'ipotesi del tempo esponenziale (ETH), un assunto di lunga data sulla difficoltà computazionale di alcuni problemi logici. L'annuncio del 26 ottobre ha spinto i ricercatori a organizzare una verifica indipendente. Il risultato divulgato non dimostra un attacco praticabile a Bitcoin. Qui ETH indica l'ipotesi del tempo esponenziale, non Ether.
L'ipotesi riguarda 3SAT, che chiede ai computer di assegnare valori vero o falso in grado di soddisfare un insieme di condizioni logiche. Secondo l'ipotesi, le soluzioni nel caso peggiore richiedono un tempo che cresce esponenzialmente con il numero di variabili. Il manoscritto, datato 17 ottobre e rivisto il 25 ottobre, rivendica un algoritmo deterministico per contare esattamente le assegnazioni soddisfacenti di formule booleane a larghezza fissa. Il manoscritto parla di tempo di esecuzione subesponenziale e di requisiti di spazio polinomiale. Un tempo subesponenziale cresce più lentamente di un limite esponenziale all'aumentare delle dimensioni del problema, ma ciò non significa che i computer attuali possano risolverlo facilmente. Il limite divulgato non stabilisce un algoritmo in tempo polinomiale né risolve P=NP. La domanda P=NP chiede se ogni problema decisionale con soluzioni verificabili in tempo polinomiale abbia anche soluzioni calcolabili in tempo polinomiale.
OpenAI afferma che l'assistente di dimostrazione Lean ha verificato il risultato. La nota sull'ambito di Lean descrive però un limite di tempo subesponenziale più debole della rivendicazione più forte del manoscritto. I ricercatori che organizzano la verifica indipendente hanno dichiarato esplicitamente di non certificare il risultato. La lettera degli organizzatori afferma: "La nostra partecipazione non deve essere considerata una certificazione della tesi". CryptoSlate ha esaminato solo le pagine introduttive 1-8, non la dimostrazione completa.
L'attività di mining di Bitcoin e l'autorizzazione a spendere coinvolgono compiti di sicurezza diversi. I miner cercano un hash dell'intestazione del blocco inferiore a un obiettivo. Le firme dimostrano il permesso di spendere. Bitcoin usa firme ECDSA e Schnorr sulla curva ellittica secp256k1, come descritto nel BIP340. Le ipotesi di sicurezza del BIP340 riguardano logaritmi discreti su curve ellittiche e funzioni hash. Il recupero della chiave chiede se un attaccante possa ottenere una chiave privata dalla corrispondente chiave pubblica. Confutare un assunto SAT nel caso peggiore non dimostra di per sé un modo per aggirare questi specifici meccanismi di sicurezza. Un attacco pratico richiederebbe una codifica adeguata, un'implementazione funzionante e un confronto dei costi per il compito preso di mira. Il numero di variabili di una formula SAT non può essere sostituito alla lunghezza in bit di una chiave crittografica o di un hash. La nota sull'ambito di Lean esprime il limite in termini di variabili e lunghezza dell'input della formula codificata. Inserire un conteggio di bit crittografico nel limite aggirerebbe la necessaria rappresentazione del problema reale.
Bitcoin corregge l'obiettivo di mining ogni 2.016 blocchi. La correzione governa la produzione dei blocchi, non l'autorizzazione tramite firme. Non eliminerebbe comunque l'importanza di un vantaggio privato nel mining. Il 7 ottobre Justin Drake ha esortato a prepararsi alla "bunker mode" dopo un precedente annuncio matematico di OpenAI. L'avvertimento di Drake riguardava un potenziale attacco futuro; quel precedente annuncio non aveva dimostrato alcuna rottura pratica di ECDSA o RSA. La tesi di OpenAI del 26 ottobre riguarda un risultato separato.
Ryan Williams ha riferito che lui, Russell Impagliazzo e Mohan Paturi erano stati incaricati di organizzare una verifica aperta e indipendente, senza accordi di riservatezza né pagamenti. Williams ha inoltre affermato di aver chiesto a OpenAI di verificare se i sistemi crittografici esistenti fossero compromessi e di aver riferito che sarebbero rimasti apparentemente sicuri. La ricostruzione di Williams è un'informazione di seconda mano su una verifica richiesta a OpenAI, non un audit crittografico indipendente. OpenAI afferma che servono ulteriori e sostanziali ricerche per ottenere miglioramenti pratici. Williams ha detto di non sapere se gli sviluppatori ne trarranno vantaggi, lasciando aperte sia la possibilità di progressi entro 12 mesi sia quella di nessuno sviluppo di questo tipo. Gli organizzatori intendono pubblicare i risultati nel corso della verifica.
