« ETH est faux » : Le papier d’OpenAI qui a fait paniquer la crypto

Encyclopédie du Coin Améliorez vos connaissances sur les cryptos

La seconde monnaie du marché n’a pas bougé d’un cheveu. L’ETH des théoriciens vacille, et cette histoire-là vaut bien mieux que le malentendu.

Reprenons depuis le début. Chez les informaticiens, l’ Exponential Time Hypothesis est une conjecture formulée en 1999 par Russell Impagliazzo et Ramamohan Paturi. Selon elle, un problème logique appelé 3-SAT ne se résout pas beaucoup plus vite qu’en essayant toutes les combinaisons. Des centaines de papiers académiques s’appuient dessus.

OpenAI affirme désormais le contraire. Son équipe décrit un algorithme déterministe qui compte toutes les solutions de problèmes de type 3-SAT en temps dit sous-exponentiel. La trouvaille date du 16 octobre, et sa vérification dans l’assistant de preuve Lean du 17. Le papier révisé le 25 octobre est en ligne sur le dépôt GitHub d’OpenAI .

Et là, le court-circuit. Sur X, un certain Takumi lâche « Damn algo traders just slaughtered $ETH ». Autrement dit, « les traders algo viennent de massacrer l’ETH ». Andrew Jiang renchérit d’un « Vitalik has been real quiet since this came out ». Comprendre : Vitalik est bien silencieux depuis que c’est sorti. Lu trop vite, le titre ressemble à une nécrologie.

Sauf que le cours n’a rien vu. L’ether s’échangeait autour de 2 350 dollars ce mercredi 28 octobre à 14 heures selon CoinGecko, quasi stable sur 24 heures. Pendant ce temps, les développeurs d’Ethereum s’occupaient du correctif de Glamsterdam sur les dépôts de staking.

Première précision pour les détenteurs d’ether. La cryptographie d’Ethereum ne repose pas sur l’ETH des théoriciens. Les signatures ECDSA tiennent à la difficulté du logarithme discret sur courbes elliptiques. Les preuves à divulgation nulle de connaissance reposent, elles, sur d’autres hypothèses encore. Un algorithme plus rapide pour compter les solutions de 3-SAT ne donne à personne votre clé privée. Le vrai sujet de fond pour la blockchain reste l’ordinateur quantique.

Deuxième précision, pour tout le monde. Même si le résultat tient, il ne dit pas que tous les problèmes NP se résolvent vite. La question P contre NP , la plus célèbre de l’informatique, reste ouverte. OpenAI l’écrit elle-même dans son billet. Selon elle, la réfutation « rouvre la question de savoir à quel point ces tâches pourraient devenir plus rapides ». Et trouver de tels algorithmes « demandera des recherches supplémentaires significatives ».

Le feuilleton a une suite. Le 26 octobre, Anthropic a mis en ligne un papier concurrent, « A 2^o(n) Time Algorithm for 3-SAT ». D’après le dépôt, un modèle Claude de recherche interne a trouvé l’algorithme. Le papier prévient toutefois que « le résultat est purement asymptotique et ne dit rien sur la résolution de formules en pratique ». Terence Tao l’avait d’ailleurs prédit dès septembre : « la simple rumeur que quelqu’un travaille sur un problème peut déclencher une quantité massive d’efforts assistés par l’IA ».