OpenAI claims a cryptography breakthrough. Does that threaten Bitcoin?

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.

Explore the Bitcoin task

Search for a valid block-header hash. A theoretical SAT bound does not establish a measured mining advantage.

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

1. OpenAI announcement
2. Manuscript, introductory pages 1–8
3. Official Lean scope
4. Independent examination letter
5. Bitcoin BIP340
6. Bitcoin mining rules
7. Bitcoin transaction signatures

Supporting facts

• 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]

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.

Ryan Williams, posting as @rrwilliams, said he, Russell Impagliazzo and Mohan Paturi had been asked to organize an open, independent examination, without NDAs or compensation.

In a separate post, @rrwilliams said he had asked OpenAI to check whether existing cryptosystems were compromised and relayed that they were apparently safe. That is his second-hand account of a check requested from OpenAI, not an independent cryptographic audit.

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.