* [bitcoindev] 51% Attack via Difficulty Increase with a Small Quantum Miner
@ 2024-03-18 13:19 Or Sattath
2024-03-20 20:42 ` [bitcoindev] " Antoine Riard
0 siblings, 1 reply; 2+ messages in thread
From: Or Sattath @ 2024-03-18 13:19 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 1591 bytes --]
Hi,
In a recent work <https://arxiv.org/abs/2403.08023> with Bolton Bailey
(still not peer-reviewed) , we showed how a single quantum miner, with
relatively little hashing power, can execute a 51% attack. *The attack
isn't relevant for the forthcoming years, requiring an extremely fast,
noise-tolerant quantum computer.*
The attack is surprisingly simple. The attacker creates a private fork,
increasing the difficulty by a factor c. Due to the properties of Grover's
algorithm, it is only \sqrt c harder for the quantum miner to mine at the
new difficulty level, but these blocks count as $c$ times more for the PoW.
Therefore, by mining even a single epoch for a large enough $c$, the
quantum miner can generate more proof-of-work than the competing
(classical) chain. The complexity of the attack is ~1/r^2 epochs, where r
is the fraction of the block rewards that the quantum miner would have
received if they mined honestly. This attack (or variants thereof) provides
essentially the same benefits as classical 51% attacks, including double
spending, and all the revenue from the block rewards.
This attack might be relevant when considering future protocol
modifications.
Or
--
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+unsubscribe@googlegroups•com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/573ba0d7-522c-424e-898f-caa780c6ecf0n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 2115 bytes --]
^ permalink raw reply [flat|nested] 2+ messages in thread
* [bitcoindev] Re: 51% Attack via Difficulty Increase with a Small Quantum Miner
2024-03-18 13:19 [bitcoindev] 51% Attack via Difficulty Increase with a Small Quantum Miner Or Sattath
@ 2024-03-20 20:42 ` Antoine Riard
0 siblings, 0 replies; 2+ messages in thread
From: Antoine Riard @ 2024-03-20 20:42 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 3345 bytes --]
Hi Or,
Thanks for the research.
> The complexity of the attack is ~1/r^2 epochs, where r is the fraction of
the block rewards that the quantum miner would have received if they mined
honestly. This attack (or variants thereof) provides essentially the same
benefits as classical 51% attacks, including double spending, and all the
revenue from the block rewards.
Quantum algorithm like Grover's algorithm are well-adapted to solve
problems with a hidden structure, e.g where the answer can be easily
verified.
This is the case any randomly yielded state from a qubit vector can be fast
verified as a PoW on a classical computer architecture.
However, I'm not sure Grover's algorithm works well for dynamic block
template construction and corresponding PoW calculations.
Any last-minute high-fee transaction might be selected in the block
template, invalidating all the oracle calls performed so far by the run of
the Grover's algorithm.
Classical computers do not have this issue that you cannot observe the
state until the computation ends, contrary to quantum computers.
Inability to adapt to a fast-dynamic fee market might render this 51%
attack unsustainable, in a post-subsidy world.
> *The attack isn't relevant for the forthcoming years, requiring an
extremely fast, noise-tolerant quantum computer.*
Information on what is the qubit format and associated solid-state
technology used for the estimation can be valuable. Especially to estimate
the real-world energy cost compared to hydro pure ASIC-based mining
infrastructure.
Best,
Antoine
Le lundi 18 mars 2024 à 13:31:37 UTC, Or Sattath a écrit :
> Hi,
> In a recent work <https://arxiv.org/abs/2403.08023> with Bolton Bailey
> (still not peer-reviewed) , we showed how a single quantum miner, with
> relatively little hashing power, can execute a 51% attack. *The attack
> isn't relevant for the forthcoming years, requiring an extremely fast,
> noise-tolerant quantum computer.*
> The attack is surprisingly simple. The attacker creates a private fork,
> increasing the difficulty by a factor c. Due to the properties of Grover's
> algorithm, it is only \sqrt c harder for the quantum miner to mine at the
> new difficulty level, but these blocks count as $c$ times more for the PoW.
> Therefore, by mining even a single epoch for a large enough $c$, the
> quantum miner can generate more proof-of-work than the competing
> (classical) chain. The complexity of the attack is ~1/r^2 epochs, where r
> is the fraction of the block rewards that the quantum miner would have
> received if they mined honestly. This attack (or variants thereof) provides
> essentially the same benefits as classical 51% attacks, including double
> spending, and all the revenue from the block rewards.
>
> This attack might be relevant when considering future protocol
> modifications.
>
> Or
>
>
>
>
--
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+unsubscribe@googlegroups•com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/ee24a4e6-52fe-4e9a-93bb-f37a24f87a89n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 4522 bytes --]
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2024-03-20 20:53 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-03-18 13:19 [bitcoindev] 51% Attack via Difficulty Increase with a Small Quantum Miner Or Sattath
2024-03-20 20:42 ` [bitcoindev] " Antoine Riard
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox