The game-theory problems of PQ sunsetting modes
Antoine Riard
Hi list,
In this post, I'm extending on the game-theory problems
underscored for my answer to [ ] to other post-quantum
sunsetting scenarios previously mentioned on this list.
Firstly, let's remember the "tripwire" idea [0]. With the
"tripwire", if I understand it correctly we introduce a
consensus level proof of quantum computers e.g with a NUMS
puzzle.
This NUMS is committed in a honeypot UTXO let's say with
some non-null bitcoin reward to unlock it. When the NUMS
point is solved by a QC entity, it automatically triggers
a "freeze" of all the "legacy" coins starting at some block
height-defined window in the future.
While it appears feasible engineering-wise, the problem
is more on the game-theory plane of analysis. As it was
previously noted by another commentator than me [1], why
an economically-rational CRQC entity would go to trigger
such an evident "honeypot" UTXO depriving it from further
(covert) extractions of the legacy coins to a safe wallet
owned by this entity.
A more sophisticated scenario, that I was laying out more
recently, a 51% majority coalition of miners could coordinate
with a CRQC entity to censor the transaction inclusion of any
PQ proof, even an inclusion attempt of a PQ proof generated by
an honest PQ entity [2].
Exposing again the economic analysis, a year of mining income
is evaluated at around $20B. The number of legacy P2Pk coins
is evaluated to be around 1.7 M of coins or as of today $107B.
If we go to account the numbers of "coin loss", the estimated
number can be more around 3-4 M, so let's say $215B worth of
target coins (a coin lost to you is not a coin lost to a CRQC
entity...).
That's something like ~10 years of potential income, that an
economically rational miner might not refuse if a miner has
a credible odd of capturing a share of this magic income to
the prorata of their hashrate capabilities [3].
If we assume a PQ coin extraction game with 2 CQRC entities
availing roughly the same capabilities, they might compete for
the majority hashrate of the miners, those miners solely driven
by economic incentives. The focal point of equilibrium between
the two strategies is likely going to be the marginal energy cost
to run a CQRC, assuming that in a fee race a CQRC entity can
offer to the majority of miners to burn more of a coin value
as reorg fee.
Secondly, for the second approach of sunsetting, the one very roughly
described in BIP361 and based on pure "flag-day" activation, the
security analysis can extend to this approach too. Even assuming
a week-long period for a BIP9-like activation mechanism, a coalition
of miners might stil go to reorg in depth the chain before the
activation of said soft-fork.
Such an approach is only theoretically increasing the coordination cost
(and one would observe the asymmetry of information is selecting a time
horizon period, as a CRQC might appear at any time during this period).
One can observe that the 2 sunsetting approach, be it "tripwire" or
"flag-day" approaches are introducing a "choke point" to the chain finality,
as in the lack of it a CQRC entity might covertly exfiltrate "legacy" coins,
with no knowledge of the miners, or even without coordination with them.
After the "choke point", a CQRC entity might alter its strategy of going
overt and start to offer fee bounties to reorg the chain as it's advantage
to the majority of miners (to not loss an exploitation advantage to another
CQRC entity).
Finally, in this analysis we're only underscoring the risk of "legacy"
coins, i.e coins that would have not upgraded to a PQ safe format, after
some time horizon. However, in the Bitcoin blockchain world, time is
relative, or rather only thermodynamically convergent. If a CQRC entity
is able to build a coalition with a 51% majority of miners, the "upgraded
PQ safe" coins might be also at risk [4]. Indeed, such malicious coalition
could just roll-back the chain state back to the migration height of
said coin, solve the DL for this coin and unroll back forward the chain.
I do not believe that the old chain history would be safe from deep
reorgs attacks by CQRC capable entities, as soft-fork deployments are
"height-based" burnt and not "hash-based" burnt (BIP90). Checkpoints
have been removed from the latest bitcoind versions. Maybe user-activated
checkpoints or other similar mechanisms might be a more robust defense
against CQRC entities attacking the chain finality.
Current bitcoin mining process and the chain finality is assumed to be
reasonably secure under the Gambler's Ruin Problem and some other assumptions
(e.g a reliable network to relay the blocks). It might be considered that
the introduction of CQRC computers might not be only a risk for the "legacy"
coins, though far more concerning for the chain finality itself.
Independently of being philosophically "pro" or "contra" in freezing
legacy coins, I do believe the irruption of one or more CQRC entities
and the potential of disruptions on the Bitcoin network stability is
a subject deserving a bit more research and more work from the development
community [5].
Cheers,
Antoine
OTS hash: 496d9c26c6f3d805dae88f487600f46990572fc84c4ca907fb85b5441c235cf3
[0] https://groups.google.com/g/bitcoindev/c/8O857bRSVV8/m/8nr6I5NIAwAJ
[1] https://groups.google.com/g/bitcoindev/c/8O857bRSVV8/m/7uu4dZNgAwAJ
[2] One might consider the following realistic scenario, it
might that even if a CRQC become relevant, at first it will
be only operated by big companies let's say in the US or China
and they will prefer to keep the existence of such capabilities
hidden for a while for non-economical reasons.
Suddenly, one of the actor starts to use those post-quantum
capabilities and the social equilibrium does not hold anymore
with impactful second-order implications for the Bitcoin ecosystem.
[3] On the low time incentive miner hypothesis, one can empirically
observe (as of June '26) than it has limits given how fast are ready
mainstream mining companies to reallocate their data centers and
sources of energies to more generic high-performance computations
rather than SHA256 hashing.
[4] For the degree of scientificity of "game-theory" in itself, I can
only forward the reader to the "Formulation of the Economic Problem"
chapter in the "Theory of Games and Economic Behavior" book from Von
Neumann & Morgenstern, 1944
[5] As quantum raises a number of skeptical eyebrows in the community,
the first elaboration of quantum physics have been as old as the 30's,
and so far no one has got a Nobel Prize, or any other major scientific
prize to prove the physical impossibility of a large-scale quantum computer
conduition
If a CQRC entity is able to build a coalition with a 51% majority of miners, the "upgradedPQ safe" coins might be also at risk [4]. Indeed, such malicious coalitioncould just roll-back the chain state back to the migration height ofsaid coin, solve the DL for this coin and unroll back forward the chain.I do not believe that the old chain history would be safe from deepreorgs attacks by CQRC capable entities, as soft-fork deployments are"height-based" burnt and not "hash-based" burnt (BIP90). Checkpointshave been removed from the latest bitcoind versions. Maybe user-activatedcheckpoints or other similar mechanisms might be a more robust defenseagainst CQRC entities attacking the chain finality.
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CALZpt%2BFOUJF3E7YDk5xh-Cv9kxduGiuOPVK5x171%3D25C3ryJPQ%40mail.gmail.com.
Antoine Riard
> Solid analysis Antoine. However things play out here, activating a PQ sunset fork of any kind while in the company of a CRQC is apparently quite hard to do right without setting the incentives up such that they sabotage the whole effort.
that activating a PQ sunset fork of any kind might be very hard
in the presence of one or more company with a CQRC, at the very
least there is a lot of uncertainty due to the incentives.
You're correct that the problem appears as soon as you have a
company with one CRQC, where it can just go really deep in the
history of the chain. As soon as you start to have two CRQC,
there is an advantage to burn more EC coins in fees, to reorg to
your advantage, so we're back with some notion of chain finality.
See more comments on rough ideas to alleviate the issue.
> Very neat observation. For such a rollback to occur, the miners would have to cooperatively elect to stop mining the more mature ("authentic") chain, where users have already migrated/forked, and instead start mining on an old block (the "revisionist" chain). Any resources they spend on this mining will have no payoff until the cumulative proof-of-work of the revisionist chain surpasses that of the authentic chain. Until then, honest validator nodes will simply sit idle.
you can play even more sneaky chain games on what you're mentioning
about ressources. Let's say you're gaining "coins" on the "authentic"
chain, and after the 100 blocks maturity rule, you immediately short
them on the market to reinvest your proceedings in the energy cost of
the "revisionist" chain (or do a mining halt, as not mining might give
an advantage to the "revisionist" chain).
You're a miner, if the "authentic" chain wins, that's fine you're
already re-sell the matured coin. If the "revisionist" chain wins,
you got new fresh coinbase on the "revisionist" chain i.e a double-spend,
plus any CQRC "bounty" coming from the exploited coins.
I think there is some "mining silent reorg" advantage here.
> Due to the vast incentive towards colluding with the CRQC, maybe this would be feasible for some large miners?
>
> This would essentially be a massive double-spend attack as well, since miners who successfully roll back the blockchain in this way would be reorging their own mining earnings out of existence, some of which they presumably sold (on the authentic chain) to pay for electricity. This might make the exchanges they sold the coins to extremely unhappy: The miners are effectively retconning their own deposits.
Yes, miners would start to be unable to settle "fresh" coins, but also "old"
coins (both EC and PQ), as they are at risk of being roll back (at least for
the ones who are weeks recent).
> For this to happen, miners must be able to withstand significant capex (on mining a revisionist chain), while being blackballed by exchanges, and possibly also devaluing the very coins they were bribed with by the CRQC. And even then, it's not clear how - assuming they were able to pull the attack off and remain solvent - the miners would actually use the ill-gotten coins, and whether they'd have any value on the other side of a successful deep reorg attack.
the exploited coins, if they can get liquidity for them on the exchanges. On the
other hand, as long as they're economically solvent, they can keep the EC-exploited
coins, until some far future, when the market price them at an interesting price
enough, and slowly and covertly sell them out of their balance sheet by then.
> Still, for shallow reorgs (a few blocks) this seems like a worthwhile concern that seriously hampers any tripwire attempts. The best case is if we can deploy the EC disabling fork before such tempting incentives enter the field of play.
of course sounds it will be always at risk of being keep out of the chain by miners.
Even the "we move fast and try to disable EC", assuming it's philosophically acceptable
by the community, and I'm among the one disagreeing to do so, as I pointed out in my
previous post, the stack of "lost" EC coins might be worth 10 years of bitcoins, that's
a lot of reorg budget.
So in the hypothesis, you have a "sunset" activation, then 3 months after a CRQC
getting out of the box, there is a lot of incentives uncertainty. Even worst, there
is even a "Lorentz effect", where the public and well-known "sunset" activation,
incentives "advanced adversaries" to reveal the CRQC they were keeping sleeping
in the backyard, as they know after the activation the cost structure is altered.
I'm thinking there are other solutions that we have not explored yet such as
PQ-blessed periodic checkpoints. E.g, let's say that every month, by consensus
rule, there is a checkpoint published that needs to be finalized e.g being
signed by more than % of PQ-safe pubkeys (e.g %1 of the overall coins).
As those pubkeys are PQ-safe, they cannot be forged by a CRQC, and a mining
coalition would not be able to go deeper than this checkpoint height, capping
up the maximum of EC-unsafe coins that could be used as reorg budget. Of course,
that would ask for a number of stakeholders in the ecosystem to have online keys
for the "checkpoint" finalization, though that % can be kept low [0] [1].
It's just a "rough idea", as somehow it's re-introducing a form of checkpoint
(which is meehhhh...but not worse than the sun setting ideas imho). I think there
are more imaginative ideas that we can come up on the design table to alleviate
the risk of a CQRC acting in coordination with a mining coalition.
Notwithstanding the ultimate direction taken, the first primitive that
would need it to give us more design flexibility would be the PQ-safe signing
algorithm, be it Falcon, SkiSign or whatever.
Best,
Antoine
OTS hash: bdb435e6c81eb762bb6a12a03e2c23a83396a3481b8894af79732c2e2b569682
[0] This also let the door open for a EC coins owner, of which the pubkey
has not been revealed e.g P2TR to exfiltrate their old coins towards
safer one.
[1] The checkpoint would have to be carefully designed to avoid being tampered
by a miner, e.g a PQ-signed checkpoint would gain a proof-of-work bonus discount ?
I'm already far in the territory of heretical consensus design ideas...
conduition
It will run for 9-12 days according to my calculations.
The CCP publicly stated that they must destroy Bitcoin in order to survive as a country, on the evening news.
Drain the side chain of their coins ...
The next target would likely not be Bitcoin or any side chains of Bitcoin, but Ethereum.
The first cryptographically relevant quantum computers are likely to be slow, especially if they are neutral atom, trapped ion or some of the NV Diamond variants depending on the speed of the computation and stability of the qubits. Realizing the quantum attacks are going to be a surprise, my game theory approach is different. Quantum Physicists will not suddenly decide to become hackers and start attacking banking networks while living in the USA, EU or China. Chinese strategy as I see it will be covered separately, below.Quantum Physics will not offer new near term gains in mining, as Pierre-Luc explained. Attacks against Bitcoin are broken into short and long windows of opportunity. Since the first quantum computer to break Bitcoin will likely be a long window, slow attack neutral atom I will give some more general information. It will run for 9-12 days according to my calculations. With tricks, they currently have a run window that permits an attack. With qubit reuse the attack is a function of time, not the size of the machine assuming it has more than 2000 qubits of operational space. The attacks can be squeezed in under 900 qubits, but the runtime grows to match. The optimal strategy would be full width for a single key break, then switching to running multiple keys concurrently on one machine as soon as funds are available for more qubits. Attack round 2 would likely break 4-100 keys at a time, operating against a single equation like secp256k1, secp256r1, ed25519, x25519, etc. Switching equations is just a change to the python in linux. Adding more physical qubits allows attacking more keys in parallel for the same steps and time (but a little extra bookkeeping). Attacking RSA2048 keys will be 1-3 years after the first secp256k1 break unless it is PSI Quantum in late 2027 and they hit their milestone target.The long window attack will eventually be surpassed by the short window attack, coming from photonics or superconductors. There are some obscure (not mainstream) fast operations possible on trapped ion and NV Diamond quantum computers. When the short window CRQC comes into play, the runtime will be in minutes but still parallel execution for a small qubit cost and no time cost. 10 private keys in 10-70 minutes would be the target. This is scheduled for 2028 by PSI Quantum, but I hope that they are simply "under retainer" by the NSA and not able to publicly demonstrate their capabilities. PSI Q has already demonstrated qubit reuse, they have already mass produced hundreds of thousands of qubits in horizontally scaling systems. If they start off cracking a single private key, they can switch to breaking 2, then 4 just by continuing mass production and installation.A strategic CRQC operator would select their first target as one with low reputation and questionable security. Drain the side chain of their coins and don't touch Satoshi's Shield or any tripwire transactions. To further increase deniability, the stalwart quantum physicists may decide to launder the gains in the same way that people from North Korea or Iran does. A few hundred million dollars is a likely early target.The next target would likely not be Bitcoin or any side chains of Bitcoin, but Ethereum. The public keys are 100% exposed in DeFi. Physicists have urged upgrading prior to 2024 and the upgrades will likely arrive too little, too late. Pocket another $100 billion, ideally with continued plausible deniability.At this point the quantum attacker could spend 5-15% of the gains and simply purchase the ASIC manufacturer outright. This would allow them to again operate with plausible deniability. Get hired by the company after the purchase. Work on something fun. Now that the quantum achievement has been completed. The purchase of 1-2 ASIC manufacturers would allow them to simply own the hash rate, with any generational improvement. They could choose to sell machines after they have been eclipsed by newer hash rates.China has a different goal. The CCP publicly stated that they must destroy Bitcoin in order to survive as a country, on the evening news. Currently 1/3 of China's GDP is leaving the country each year and Bitcoin is the most efficient method to do so. Tron and Tether are face value, but Bitcoin is easy to send money overseas. Use Yuan to buy mining equipment, sell Bitcoin for EU or USD. This is done at a profit, while art sales and Tether are done at a significant or small loss respectively. China's Middle Class faces export controls on sending money overseas, international banking is extremely limited and total control is the CCP bare minimum standard.Against this backdrop, China has thrown millions of dollars at dozens of companies to create a huge number of quantum computers racing to be the first to break Bitcoin. Bitcoin is the stated goal. Destroying Bitcoin as a store of value is the government strategy. Rapid sales of any known public keys will commence ASAP, and CRCQ will be mass produced. So their likely runtime would be targeting Satoshi's Shield, getting 50 BTC per break. If they can catch exchange funds "proof of reserves" then they will topple most of the economic value. 6.9 million BTC to target. They might trigger a tripwire, the goal is to dump the market and the exchanges.I suspect the CCP will target Ethereum in order to cause critical damage to the US economy, especially as stablecoins and CBDC have jumped in. Bitcoin sales would allow them to pay down a small portion of their debt. Ethereum sales would allow China to supersede the USA as the dominant economy. As I have said publicly, the strategy is much different depending on the threat actor who gets the first and who gets the fast CRQC.The game theory for each threat actor is different:
US Individual: plausible deniability, stealth, money laundering.
US Company: salvage laws, plausible deniability, can not have govt funding and target US companies like Blackrock, (micro)Strategy, Coinbase, etc.EU Company: ideologically driven, might break a few accounts for retirement but not touch most public keys.China: must crash all crypto to survive. If they can destroy Bitcoin, mining and pay down debt, great. If they can use this to 'break the hegemonic order' they will definitely do so.I would be happy to discuss here or on Signal.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CALZpt%2BEjD5h9387diQvwtUY9nV-GFgN-Ukp9tY%3DuqBofb-w7Tg%40mail.gmail.com.