From mboxrd@z Thu Jan 1 00:00:00 1970
Delivery-date: Wed, 20 Mar 2024 13:53:08 -0700
Received: from mail-yb1-f188.google.com ([209.85.219.188])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBC3PT7FYWAMRBLMZ5WXQMGQEANWIEHI@googlegroups.com>)
id 1rn2vs-0003o0-B5
for bitcoindev@gnusha.org; Wed, 20 Mar 2024 13:53:08 -0700
Received: by mail-yb1-f188.google.com with SMTP id 3f1490d57ef6-dc693399655sf414557276.1
for <bitcoindev@gnusha.org>; Wed, 20 Mar 2024 13:53:08 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1710967982; x=1711572782; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:references:in-reply-to:message-id:to:from:date:sender:from
:to:cc:subject:date:message-id:reply-to;
bh=V2KqAfLyzStKA9lgG+00KyimMMkXvcr+XYuryjRKZEo=;
b=prmjwwbdEn0cin3I1jxy1WH3t9o5dPuV9Hhg6k9AREZ1S+b93Y8rz9wK7qKIuE7ikf
ujKHRCSxNwq5fANChG5x0NjwaPoy7rDmIaywhJnAwN4YiVk0nO4of1ar4ER12K5g8aLl
NqQAlmogwBu7XMC1X0pLwhyanZOuw8ANSmypF4WcgvkAQMUcxL0nHUDKxaF2JAgfy48K
BVXSrOlfxgE53mYxp7co+wWxSFStBKfstCE4ssGw+9eW/Pf8cryryJJ8G12LI7mYnhaI
BTg+3KoIbgBlDeJAwNwVNvG0HSykTwxhlNWiWApbLrtHVDyvs7wovGil0Dju1lZfiBQC
Xofw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1710967982; x=1711572782; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:references:in-reply-to:message-id:to:from:date:from:to:cc
:subject:date:message-id:reply-to;
bh=V2KqAfLyzStKA9lgG+00KyimMMkXvcr+XYuryjRKZEo=;
b=aLabVQkbdm67p6ekTAjgyIZjmGZNvH6RQ0s6zHu36YtioZHNBNF6PdcoNr64mEKr0w
egqt9BZvB4uD4c9O3D+ZgDFXbFS+iE79jKhY9tiKskSUxb6y6AtlQuhkyMjnSaN2xOtR
c+Wh6523hKddSpPZgctrfbyi4kBNFgtd59wjwA/Mokvr1BiqhXMClKo4n25uzmAaTmk+
5jL7b/2IdibV+Dh9jIXHBe3zfuQLelaTMsN1CvE/6jB1+QZ3Q5fYBDV5HUh8Q5eI9ciQ
OaBEPma9w7FaBmGxrpcUdKEz43pBY8DQW9B7rx0RGZULTFYZA5Gk6Lgc8OjnW2KypZlC
O5Zg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1710967982; x=1711572782;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:references:in-reply-to:message-id:to:from:date:x-beenthere
:x-gm-message-state:sender:from:to:cc:subject:date:message-id
:reply-to;
bh=V2KqAfLyzStKA9lgG+00KyimMMkXvcr+XYuryjRKZEo=;
b=DuEIyg9G7bGg5gwGKOG0krX07xxRQ67OEU6dChp5RNAk5KV9LoaY+uv3FMXEvHDeZI
l4EJE7wRQ4AfgXpM5838uZR0NMKx3K8IuW4PKWvZvhrUE9myNl7UOVcywEP7O4870syX
qlTdneQxishhrxammQzi/zomME4n01C6Dys3kwExLR6WSM9K05tBqDpzupzynrEXic+i
iwNw3rFmOZkfca5H0OrhAdjuFacV1cE/EplVDmi19ZG1VpxlZydeZ4Pt9627gE+p5hoI
lhrT1dx93C7LiXjggvoivjVouG1l1znjqgAUPmGyB9S93c/1m5Lex/A6aNfEPvmcC3rl
zN4w==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCUknS7oUPedwps/lKFcphy2g6xe0eAmcn4sNpEz+BSVbHeoNsl0J3Ny/m97QIc1GDkHwLegoJkyNB2bNIUrZH/h/K4bt3s=
X-Gm-Message-State: AOJu0Yw39YRH/O6XsswH8g6DYxGYs8xnJtC+z40aZeEWGEgI5lBEQTd4
TSfujaKKVsuc/sYmH26ASFxlZ7MMX1D6YqUciXzOALTB3P4B6SBt
X-Google-Smtp-Source: AGHT+IGfipP+BbJCbQN50SURtohj+uqSqs6TNFBkwxskdJ7I1Dlv6PsRxFI01zIsvtFTUR9HCvzaTw==
X-Received: by 2002:a5b:51:0:b0:dcc:4cdc:e98e with SMTP id e17-20020a5b0051000000b00dcc4cdce98emr3019545ybp.5.1710967981971;
Wed, 20 Mar 2024 13:53:01 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a25:e0d2:0:b0:dcc:4b24:c0da with SMTP id x201-20020a25e0d2000000b00dcc4b24c0dals502748ybg.2.-pod-prod-02-us;
Wed, 20 Mar 2024 13:53:01 -0700 (PDT)
X-Received: by 2002:a0d:ea0f:0:b0:60c:ca9c:7d10 with SMTP id t15-20020a0dea0f000000b0060cca9c7d10mr3488314ywe.2.1710967980990;
Wed, 20 Mar 2024 13:53:00 -0700 (PDT)
Received: by 2002:a05:690c:ed0:b0:610:e5cb:e605 with SMTP id 00721157ae682-610f20c60b3ms7b3;
Wed, 20 Mar 2024 13:42:35 -0700 (PDT)
X-Received: by 2002:a81:fe0e:0:b0:610:c400:9e8a with SMTP id j14-20020a81fe0e000000b00610c4009e8amr1696359ywn.2.1710967354378;
Wed, 20 Mar 2024 13:42:34 -0700 (PDT)
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"
X-Original-Sender: antoine.riard@gmail.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
<https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.5 (/)
------=_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>> 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=
>>=C2=A0<b>The attack isn't relevant for the=C2=A0<span style=3D"color: =
rgb(0, 0, 0); font-family: "Lucida Grande", 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&q=3Dh=
ttps://arxiv.org/abs/2403.08023&source=3Dgmail&ust=3D17110519994560=
00&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't relevant for the=C2=A0<span style=3D"color:rgb(0,0,0);font-f=
amily:"Lucida Grande",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'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" 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--