OpenAI claims a cryptography breakthrough. Does that threaten Bitcoin?
ETH here means Exponential Time Hypothesis, and a theoretical SAT speed-up alone does not establish a practical cryptographic attack. Read the full story on CryptoSlateUnderstand the crypto stories that matter and what to watch next. Get The Catalyst in your inbox
OpenAI says its AI system has refuted the Exponential Time Hypothesis, a longstanding assumption about how difficult certain logic problems are to solve. The Oct. 26 announcement has researchers organizing an independent examination. The disclosed result does not establish a practical attack on Bitcoin.
ETH here means Exponential Time Hypothesis, rather than Ether. The subject is 3-SAT, a puzzle in which a computer must find true-or-false settings that satisfy a collection of logical rules. The hypothesis says solving these problems requires exponential time in the number of variables in the worst case.
OpenAI says the result was verified in Lean, a proof assistant, although its scope note describes a weaker time bound than the manuscript's sharpest claim. The researchers organizing the community's examination have expressly declined to certify it. Their letter says, “Our involvement should not be taken as certification of the claim.”
The manuscript, dated Oct. 17 and revised Oct. 25, claims a deterministic algorithm that exactly counts the satisfying assignments of fixed-width Boolean formulas in subexponential time and polynomial space. In plain English, its running time grows more slowly than an exponential bound as the problem gets larger. That is a different promise from making the problem easy on today's computers.
The disclosed bound does not establish a polynomial-time algorithm or settle P=NP, the question of whether every decision problem whose proposed solutions can be verified in polynomial time can also be solved in polynomial time.
CryptoSlate's examination of the paper is limited to its introductory pages 1–8, rather than a review of the full proof.
Related ReadingFor Bitcoin, mining and spending authorization are separate tasks. Miners search for a block-header hash below a target. Signatures establish authorization to spend. Bitcoin's signature systems include ECDSA and Schnorr over the secp256k1 elliptic curve, as described in BIP340.