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.
Related Asset Bitcoin #1 BTC · $80,622.22 24-hour change: up 1.04% Loading price history… 24H Up 1.04% 7D Down 2.76% 30D Down 4.77%
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.”
Related Company OpenAI AI research and deployment company
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.
Related Asset Ethereum ETH · $2,341.56 24-hour change: up 1.76%
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.
A SAT claim. A missing bridge to a Bitcoin attack.
OpenAI's claimed ETH refutation concerns formula solving. Mining and spending pose different concrete tasks.
From a SAT claim to a practical Bitcoin attackTHE CLAIMFaster SAT countingOpenAI says; independent review openSATformulas
- apply？THE MISSING BRIDGEConcrete attackEncoding + real costs
MiningHash targetSpendingSignaturesDashed connectors mark an unestablished practical consequence, not an attack path.hashkey
The missing bridge, mobileTHE CLAIMFaster SAT countingOpenAI says; review remains openSATformulas
- apply？THE MISSING BRIDGEConcrete attackEncoding + real costs
MiningSpendingHash targetSignaturesDashed: practical consequence unestablishedhashkey
Explore the Bitcoin taskExplore the Bitcoin taskMiningSpending
Search for a valid block-header hash. A theoretical SAT bound does not establish a measured mining advantage.
mining taskMINING: FIND A VALID HASHBlock headerCandidate input
- hashBelowtarget？
- Valid blockSubject to other rules
- A SAT bound supplies no measured mining advantage.Difficulty retargeting is separate from spending authorization.if yes
mining task mobileMININGBlock headerCandidate input
- hashBelowtarget？
- Valid blockSubject to other rulesNo measured mining advantageRetargeting concerns block production.It does not protect signature keys.if yes
Signatures authorize spending. The SAT claim does not demonstrate recovery of a secp256k1 private key.
spending taskSPENDING: PROVE AUTHORIZATIONPrivate keySigning secret
- signValidsignature？
- Authorized spendSubject to script rules
- ECDSA and Schnorr use the secp256k1 curve.The SAT claim does not demonstrate private-key recovery.if yes
spending task mobileSPENDINGPrivate keySigning secret
- signValidsignature？
- Authorized spendSubject to script rulesNo demonstrated key recoveryECDSA / Schnorr on secp256k1.A separate concrete attack is needed.if yes
A subexponential SAT bound does not by itself demonstrate a practical Bitcoin attack.
The ETH refutation is OpenAI's claim pending independent scrutiny. Paper evidence is limited to introductory pages 1–8. No attack times, encoding sizes, benchmarks or independent cryptographic audit are established.
Sources and evidence
Sources
- OpenAI announcement
- Manuscript, introductory pages 1–8
- Official Lean scope
- Independent examination letter
- Bitcoin BIP340
- Bitcoin mining rules
- Bitcoin transaction signatures
- OpenAI said on Oct. 26 that its system had produced a refutation of the Exponential Time Hypothesis and that the result was subsequently verified in Lean; independent community examination remains open. [1] [4]
- The manuscript claims a deterministic algorithm for exactly counting satisfying assignments of fixed-width Boolean formulas in subexponential time and polynomial space. [2] [3]
- The disclosed subexponential SAT bound does not establish a polynomial-time algorithm or settle P=NP. [2] [3]
- OpenAI's formalization note documents a weaker logarithmic time bound for Lean than the sharper bound in the Oct. 25 manuscript. [3]
- The community letter signed by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams says their involvement should not be treated as certification and calls for careful independent scrutiny. [4]
- Bitcoin uses ECDSA and Schnorr signatures over secp256k1; BIP340 states Schnorr security assumptions involving discrete logarithms and hashes, and notes stronger assumptions for ECDSA security proofs. [5] [7]
- Bitcoin mining searches for a block-header hash below a target, while transaction signatures authorize spending; those are distinct cryptographic tasks. [6] [7] [5]
- The disclosed theoretical SAT speed-up does not by itself demonstrate a practical Bitcoin attack; applying it would require a concrete encoding and a cost comparison for the relevant cryptographic task. [2] [3] [5] [6]
- Bitcoin's difficulty is recalculated every 2,016 blocks, but this mechanism is separate from signature authorization. [6] [7]
- OpenAI says turning the theoretical advances into practical improvements requires significant further research. [1]
Supporting facts
Method
Qualitative mechanism diagram using the retained OpenAI claim, documented Lean scope, independent examination letter and Bitcoin protocol documentation. Geometry is schematic, not a performance scale. Native panels compare mining and spending tasks.
Scope
The ETH refutation is OpenAI's claim pending independent scrutiny. Paper evidence is limited to introductory pages 1–8. No attack times, encoding sizes, benchmarks or independent cryptographic audit are established.
Infographic by CryptoSlate
Bitcoin has two different security questions
For 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.
The security assumptions described there concern elliptic-curve discrete logarithms and hash functions. The key-recovery question is whether an attacker can derive a private key from its public counterpart. Refuting an assumption about worst-case SAT solving does not, by itself, show how to defeat those concrete mechanisms. A practical attack would still need a suitable encoding, an implementation and a cost comparison for the task being attacked.
The variable count in a SAT formula is also not interchangeable with the bit length of a cryptographic key or hash. The Lean scope measures its bound using the encoded formula's variables and input length. Substituting a familiar crypto bit count into that bound would skip the work needed to represent the actual problem.
Bitcoin's difficulty adjustment recalculates its mining target every 2,016 blocks. That concerns block production, not signature authorization. It would not make a private mining advantage irrelevant.
The distinction follows a debate CryptoSlate covered on Oct. 7, when Justin Drake urged preparations for “bunker mode” after an earlier OpenAI mathematics release. That warning concerned a possible future attack; the earlier announcement had not demonstrated a practical ECDSA or RSA break. The Oct. 26 ETH claim concerns a different result.
OpenAI itself says practical improvements require significant further research. Asked about benefits developers might feel, @rrwilliams said he did not know, allowing both for progress within 12 months and for no such development. The organizers intend to share findings as the examination progresses.