OpenAI tvrdi da je postigao proboj u kriptografiji. Prijeti li to Bitcoinu?

OpenAI je 26. listopada objavio da je njezin AI sustav oborio hipotezu eksponencijalnog vremena (ETH), dugogodišnju pretpostavku o težini rješavanja određenih logičkih problema. Tvrdnja je izazvala pozornost jer bi mogla utjecati na razumijevanje računalne složenosti, ali i zato što su istraživači najavili neovisnu provjeru. U priopćenju se ističe da otkriveno ubrzanje SAT rješavanja ne dokazuje praktičan napad na bitcoin rudarenje ni na potpise za trošenje. Takođerr, ETH u ovom kontekstu nije kriptovaluta ether, nego hipoteza eksponencijalnog vremena.

Objava je uslijedila 26. listopada, a rukopis je datiran 17. listopada i revidiran 25. listopada. U njemu se tvrdi deterministički algoritam koji točno broji zadovoljavajuća pridruživanja fiksno širokih logičkih formula u subeksponencijalnom vremenu i polinomijalnom prostoru. Jednostavnije rečeno, vrijeme izvršavanja raste sporije od eksponencijalne granice kako problem postaje veći. OpenAI navodi da je rezultat verificiran u Leanu, pomoćniku za dokazivanje, no napomena o opsegu opisuje slabiju vremensku granicu od najoštrije tvrdnje iz rukopisa. Istraživači koji organiziraju provjeru zajednice izričito su odbili to certificirati.

Kontekst

Hipoteza eksponencijalnog vremena tvrdi da rješavanje takozvanih 3-SAT problema u najgorem slučaju zahtijeva eksponencijalno vrijeme s obzirom na broj varijabli. Riječ je o problemu u kojem računalo mora pronaći istinite ili neistinite vrijednosti koje zadovoljavaju skup logičkih pravila. Otkrivena granica ne uspostavlja polinomijalni algoritam niti rješava pitanje P=NP, odnosno može li se svaki problem odluke čija se predložena rješenja mogu provjeriti u polinomijalnom vremenu takođerr riješiti u polinomijalnom vremenu. U bitcoin kontekstu treba razlikovati rudarenje i potpise. Rudari traže hash zaglavlja bloka ispod ciljne vrijednosti, dok potpisi uspostavljaju ovlast za trošenje.

Sustavi potpisa uključuju ECDSA i Schnorr nad eliptičnom krivuljom secp256k1, kako je opisano u BIP340. Tamošnje sigurnosne pretpostavke odnose se na diskretne logaritme eliptičnih krivulja i hash funkcije.

Ključne brojke

Objava je 26. listopada, rukopis 17. listopada, a revizija 25. listopada. Analiza CryptoSlatea ograničena je na uvodne stranice 1–8, ne na cijeli dokaz. Bitcoin prilagodba težine ponovno izračunava rudarski cilj svakih 2.016 blokova. Organizatori spominju mogućnost napretka unutar 12 mjeseci, ali i da ga ne mora biti.

Što to znači

Obaranje pretpostavke o rješavanju SAT problema u najgorem slučaju samo po sebi ne pokazuje kako pobijediti konkretne mehanizme bitcoina. Praktičan napad i dalje bi trebao prikladno kodiranje, implementaciju i usporedbu troškova za konkretan problem. Broj varijabli u SAT formuli nije istovjetan duljini bita kriptografskog ključa ili hasha. Leanov opseg mjeri granicu pomoću varijabli kodirane formule i duljine ulaza, pa bi zamjena poznatim kripto brojem bitova preskočila rad potreban za predstavljanje stvarnog problema. Prilagodba težine tiče se proizvodnje blokova, ne ovlasti za potpise, i ne bi učinila privatnu rudarsku prednost nevažnom.

Što slijedi

Ryan Williams, koji piše kao @rrwilliams, rekao je da su on, Russell Impagliazzo i Mohan Paturi zamoljeni da organiziraju otvorenu, neovisnu provjeru bez NDA-a i naknade. U zasebnoj objavi rekao je da je zamolio OpenAI da provjeri jesu li postojeći kriptosustavi ugroženi te prenio da su očito sigurni. To je njegov prikaz iz druge ruke, a ne neovisna kriptografska revizija. OpenAI navodi da praktična poboljšanja zahtijevaju znatna daljnja istraživanja. Na pitanje o koristima za razvijatelje, @rrwilliams je rekao da ne zna, dopuštajući i napredak unutar 12 mjeseci i izostanak takvog razvoja. Organizatori namjeravaju objavljivati nalaze kako provjera bude napredovala.