Delivery-date: Wed, 20 Mar 2024 13:53:08 -0700
Sender: bitcoindev@googlegroups.com
Date: Wed, 20 Mar 2024 13:42:33 -0700 (PDT)
From: Antoine Riard <antoine.riard@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <ee24a4e6-52fe-4e9a-93bb-f37a24f87a89n@googlegroups.com>
In-Reply-To: <573ba0d7-522c-424e-898f-caa780c6ecf0n@googlegroups.com>
References: <573ba0d7-522c-424e-898f-caa780c6ecf0n@googlegroups.com>
Subject: [bitcoindev] Re: 51% Attack via Difficulty Increase with a Small
 Quantum Miner
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_3960_2107380359.1710967353965"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_Part_3960_2107380359.1710967353965
Content-Type: multipart/alternative; 
	boundary="----=_Part_3961_1012099564.1710967353965"

------=_Part_3961_1012099564.1710967353965
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Or,

Thanks for the research.

> The complexity of the attack is ~1/r^2 epochs, where r is the fraction of=
=20
the block rewards that the quantum miner would have received if they mined=
=20
honestly. This attack (or variants thereof) provides essentially the same=
=20
benefits as classical 51% attacks, including double spending, and all the=
=20
revenue from the block rewards.=20

Quantum algorithm like Grover's algorithm are well-adapted to solve=20
problems with a hidden structure, e.g where the answer can be easily=20
verified.
This is the case any randomly yielded state from a qubit vector can be fast=
=20
verified as a PoW on a classical computer architecture.
However, I'm not sure Grover's algorithm works well for dynamic block=20
template construction and corresponding PoW calculations.
Any last-minute high-fee transaction might be selected in the block=20
template, invalidating all the oracle calls performed so far by the run of=
=20
the Grover's algorithm.
Classical computers do not have this issue that you cannot observe the=20
state until the computation ends, contrary to quantum computers.
Inability to adapt to a fast-dynamic fee market might render this 51%=20
attack unsustainable, in a post-subsidy world.

> *The attack isn't relevant for the forthcoming years, requiring an=20
extremely fast, noise-tolerant quantum computer.*

Information on what is the qubit format and associated solid-state=20
technology used for the estimation can be valuable. Especially to estimate=
=20
the real-world energy cost compared to hydro pure ASIC-based mining=20
infrastructure.

Best,
Antoine


Le lundi 18 mars 2024 =C3=A0 13:31:37 UTC, Or Sattath a =C3=A9crit :

> Hi,
> In a recent work <https://arxiv.org/abs/2403.08023> with Bolton Bailey=20
> (still not peer-reviewed) , we showed how a single quantum miner, with=20
> relatively little hashing power, can execute a 51% attack. *The attack=20
> isn't relevant for the forthcoming years, requiring an extremely fast,=20
> noise-tolerant quantum computer.*
> The attack is surprisingly simple. The attacker creates a private fork,=
=20
> increasing the difficulty by a factor c. Due to the properties of Grover'=
s=20
> algorithm, it is only \sqrt c harder for the quantum miner to mine at the=
=20
> new difficulty level, but these blocks count as $c$ times more for the Po=
W.=20
> Therefore, by mining even a single epoch for a large enough $c$, the=20
> quantum miner can generate more proof-of-work than the competing=20
> (classical) chain. The complexity of the attack is ~1/r^2 epochs, where r=
=20
> is the fraction of the block rewards that the quantum miner would have=20
> received if they mined honestly. This attack (or variants thereof) provid=
es=20
> essentially the same benefits as classical 51% attacks, including double=
=20
> spending, and all the revenue from the block rewards.=20
>
> This attack might be relevant when considering future protocol=20
> modifications.
>
> Or
>
>
>
>

--=20
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 e=
mail 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.

------=_Part_3961_1012099564.1710967353965
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Or,<div><br /></div><div>Thanks for the research.</div><div><br /></div>=
<div>&gt; The complexity of the attack is ~1/r^2 epochs, where r is the fra=
ction of the block rewards that the quantum miner would have received if th=
ey mined honestly. This attack (or variants thereof) provides essentially t=
he same benefits as classical 51% attacks, including double spending, and a=
ll the revenue from the block rewards.=C2=A0</div><div><br /></div><div>Qua=
ntum algorithm like Grover's algorithm are well-adapted to solve problems w=
ith a hidden structure, e.g where the answer can be easily verified.</div><=
div>This is the case any randomly yielded state from a qubit vector can be =
fast verified as a PoW on a classical computer architecture.</div><div>Howe=
ver, I'm not sure Grover's algorithm works well for dynamic block template =
construction and corresponding PoW calculations.</div><div>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.=
</div><div>Classical computers do not have this issue that you cannot obser=
ve the state until the computation ends, contrary to quantum computers.</di=
v><div>Inability to adapt to a fast-dynamic fee market might render this 51=
% attack unsustainable, in a post-subsidy world.</div><div><br /></div><div=
>&gt;=C2=A0<b>The attack isn't relevant for the=C2=A0<span style=3D"color: =
rgb(0, 0, 0); font-family: &quot;Lucida Grande&quot;, Helvetica, Arial, san=
s-serif; font-size: 13.608px;">forthcoming years, requiring an extremely fa=
st, noise-tolerant quantum computer.</span></b></div><div><br /></div><div>=
Information on what is the qubit format and associated solid-state technolo=
gy used for the estimation can be valuable. Especially to estimate the real=
-world energy cost compared to hydro pure ASIC-based mining infrastructure.=
</div><div><br /></div><div>Best,</div><div>Antoine</div><div><br /><br /><=
/div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">Le l=
undi 18 mars 2024 =C3=A0 13:31:37 UTC, Or Sattath a =C3=A9crit=C2=A0:<br/><=
/div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8ex; border=
-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">Hi,<div>In a recen=
t <a href=3D"https://arxiv.org/abs/2403.08023" target=3D"_blank" rel=3D"nof=
ollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Dfr&amp;q=3Dh=
ttps://arxiv.org/abs/2403.08023&amp;source=3Dgmail&amp;ust=3D17110519994560=
00&amp;usg=3DAOvVaw1wDp8NO0jfWAyhCG0Kt0bD">work</a>=C2=A0with=C2=A0Bolton B=
ailey (still not peer-reviewed)=C2=A0, we showed how a single quantum miner=
, with relatively little hashing power, can execute a 51% attack. <b>The at=
tack isn&#39;t relevant for the=C2=A0<span style=3D"color:rgb(0,0,0);font-f=
amily:&quot;Lucida Grande&quot;,Helvetica,Arial,sans-serif;font-size:13.608=
px">forthcoming years, requiring an extremely fast, noise-tolerant quantum =
computer.</span></b></div><div>The attack is surprisingly simple. The attac=
ker creates a private fork, increasing the difficulty by a factor c. Due to=
 the properties of Grover&#39;s algorithm, it is only \sqrt c harder for th=
e 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 fo=
r a large enough $c$, the quantum miner can generate more proof-of-work tha=
n the competing (classical) chain. The complexity of the attack is ~1/r^2 e=
pochs, where r is the fraction of the block rewards that the quantum miner =
would have received if they mined honestly. This attack (or variants thereo=
f) provides essentially the same benefits as classical 51% attacks, includi=
ng double spending, and all the revenue from the block rewards.=C2=A0</div>=
<div><br></div><div>This attack might be relevant when considering future p=
rotocol modifications.</div><div><br></div><div>Or</div><div><br></div><div=
><br></div><div><br></div></blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/bitcoindev/ee24a4e6-52fe-4e9a-93bb-f37a24f87a89n%40googlegroups.=
com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg=
id/bitcoindev/ee24a4e6-52fe-4e9a-93bb-f37a24f87a89n%40googlegroups.com</a>.=
<br />

------=_Part_3961_1012099564.1710967353965--

------=_Part_3960_2107380359.1710967353965--