1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
|
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--
|
