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
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
|
Return-Path: <sergio.d.lerner@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id E6EA0A6E
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 7 Apr 2017 20:53:02 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-qt0-f175.google.com (mail-qt0-f175.google.com
[209.85.216.175])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id AF5A513D
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 7 Apr 2017 20:52:58 +0000 (UTC)
Received: by mail-qt0-f175.google.com with SMTP id x35so70364926qtc.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 07 Apr 2017 13:52:58 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:from:date:message-id:subject:to;
bh=o1cSvcBAtdnKGtbq3FnXMs1/++E5DcZOJ8SLxM1+w5Q=;
b=OcJE0vMa7hi3cBHWI32Lxd6kPbMsqTj0aLX2/dDuyEUzhJHN4PdfoEHkZeK6qv4xUl
uTpk2ldX1NqyLrPEYt7O2K3AMpZ6z/3ihLBnxeRXSImdE4+DFRFXaZYEzNwuCIlwLqyM
aTMSu7w5QjZ6QOhy1KEkfZL9ZZhCzm/0g6QCi/cJJn8l0blUC+rHYlIZ0Q7SibX6NZse
vM6FX1FPS0/+WlkfCPFUTj+2qp8Lb51YUR1vFQktDRg7rx4Ot7lE6WMBY3eVKdrUrbCv
hSYq9+qdiDOFsU/QGwA96hzJBIDfX2MP+kto/TlRzdOE71VLsVmAD6AQE6D/KlZbOBSm
IqZA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
bh=o1cSvcBAtdnKGtbq3FnXMs1/++E5DcZOJ8SLxM1+w5Q=;
b=JmcNGqGiU3kw1CyJ/BxAOZwgRZFDo4uO9BsdzPRO3PBDF1U8VpQ7F89XpiVHyfLgih
XJB79wIojat3nxpeNQ4WdwvrDA6vmXUmzyVVFRyEyTH9O55mUJBo4BgSGSoLFgR6YSG3
d6tRdM5+a4Vboc4QsZnpR1wRKY3J4dYaAQDKozCiC5Ey0VG3DgeXzdVKQhqQzAXM3J2m
Cjj/ULmD8qXbpw/FhcZ6bWdusKRLuY6mLmPNeG6h8WXawAUKzO2oynUk3qR7xo5cqVxP
dNwfd7HOs/ygEZuoRSxF1utOpDjQytDj/HS31OzCjFDCS/25dD0G1F5tiH/Q3yMr/VE9
jH7A==
X-Gm-Message-State: AFeK/H1cFFn1wfee3O7eVSIUepZx1CWENbguH459x6bqSISrGDmz505nKlLr5AKrp37nXeOcLSbg/ssRa1lmmw==
X-Received: by 10.237.53.48 with SMTP id a45mr41156053qte.286.1491598377560;
Fri, 07 Apr 2017 13:52:57 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.12.170.220 with HTTP; Fri, 7 Apr 2017 13:52:17 -0700 (PDT)
From: Sergio Demian Lerner <sergio.d.lerner@gmail.com>
Date: Fri, 7 Apr 2017 17:52:17 -0300
Message-ID: <CAKzdR-rzb6oBq01DQM530pdgNUjzc79yjtYp_HAyF5GZpBPnFw@mail.gmail.com>
To: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=001a11c000ae7132d1054c99cffb
X-Spam-Status: No, score=-0.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,MPART_ALT_DIFF,
RCVD_IN_DNSWL_NONE,RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: [bitcoin-dev] BIP Proposal: Inhibiting a covert optimization on the
Bitcoin POW function
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 07 Apr 2017 20:53:03 -0000
--001a11c000ae7132d1054c99cffb
Content-Type: text/plain; charset=UTF-8
<pre>
BIP: TBD
Layer: Consensus
Title: Inhibiting a covert optimization on the Bitcoin POW function
Author: Sergio Demian Lerner <sergio.d.lerner@gmail.com>
Status: Draft
Type: Standards Track
Created: 2016-04-07
License: PD
</pre>
==Abstract==
This proposal inhibits the covert use of a known optimization in Bitcoin
Proof of Work function.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119.
==Motivation==
Due to a design oversight the Bitcoin proof of work function has a potential
optimization which can allow a rational miner to save up-to 30% of their
energy
costs (though closer to 20% is more likely due to implementation overheads).
Timo Hanke and Sergio Demian Lerner applied for a patent on this
optimization. The company "Sunrise Tech Group, Llc" has offered to license
it to any interested party in the past. Sunrise Tech Group has been
marketing their patent licenses under the trade-name ASICBOOST. The
document takes no position on the validity or enforceability of the patent.
There are two major ways of taking advantage of this optimization, as
described
by the patent:
One way which is highly detectable and is not in use on the network
today and a covert way which has significant interaction and potential
interference with the Bitcoin protocol. The covert mechanism is not
easily detected except through its interference with the protocol.
In particular, the protocol interactions of the covert method can block the
implementation of virtuous improvements such as segregated witness.
The use of this optimization could result in a big payoff, but the actual
sum depends on the degree of research, investment and effort put into
designing
the improved cores.
On the above basis the potential for covert use of this optimization
in the covert form and interference with useful improvements presents a
danger to the Bitcoin system.
==Background==
The general idea of this optimization is that SHA2-256 is a merkle damgard
hash
function which consumes 64 bytes of data at a time.
The Bitcoin mining process repeatedly hashes an 80-byte 'block header' while
incriminating a 32-bit nonce which is at the end of this header data. This
means that the processing of the header involves two runs of the compression
function run-- one that consumes the first 64 bytes of the header and a
second which processes the remaining 16 bytes and padding.
The initial 'message expansion' operations in each step of the SHA2-256
function operate exclusively on that step's 64-bytes of input with no
influence from prior data that entered the hash.
Because of this if a miner is able to prepare a block header with
multiple distinct first 64-byte chunks but identical 16-byte
second chunks they can reuse the computation of the initial
expansion for multiple trials. This reduces power consumption.
There are two broad ways of making use of this optimization. The obvious
way is to try candidates with different version numbers. Beyond
upsetting the soft-fork detection logic in Bitcoin nodes this has
little negative effect but it is highly conspicuous and easily
blocked.
The other method is based on the fact that the merkle root
committing to the transactions is contained in the first 64-bytes
except for the last 4 bytes of it. If the miner finds multiple
candidate root values which have the same final 32-bit then they
can use the optimization.
To find multiple roots with the same trailing 32-bits the miner can
use efficient collision finding mechanism which will find a match
with as little as 2^16 candidate roots expected, 2^24 operations to
find a 4-way hit, though low memory approaches require more
computation.
An obvious way to generate different candidates is to grind the
coinbase extra-nonce but for non-empty blocks each attempt will
require 13 or so additional sha2 runs which is very inefficient.
This inefficiency can be avoided by computing a sqrt number of
candidates of the left side of the hash tree (e.g. using extra
nonce grinding) then an additional sqrt number of candidates of
the right side of the tree using transaction permutation or
substitution of a small number of transactions. All combinations
of the left and right side are then combined with only a single
hashing operation virtually eliminating all tree related
overhead.
With this final optimization finding a 4-way collision with a
moderate amount of memory requires ~2^24 hashing operations
instead of the >2^28 operations that would be require for
extra-nonce grinding which would substantially erode the
benefit of the optimization.
It is this final optimization which this proposal blocks.
==New consensus rule==
Beginning block X and until block Y the coinbase transaction of
each block MUST either contain a BIP-141 segwit commitment or a
correct WTXID commitment with ID 0xaa21a9ef.
(See BIP-141 "Commitment structure" for details)
Existing segwit using miners are automatically compatible with
this proposal. Non-segwit miners can become compatible by simply
including an additional output matching a default commitment
value returned as part of getblocktemplate.
Miners SHOULD NOT automatically discontinue the commitment
at the expiration height.
==Discussion==
The commitment in the left side of the tree to all transactions
in the right side completely prevents the final sqrt speedup.
A stronger inhibition of the covert optimization in the form of
requiring the least significant bits of the block timestamp
to be equal to a hash of the first 64-bytes of the header. This
would increase the collision space from 32 to 40 or more bits.
The root value could be required to meet a specific hash prefix
requirement in order to increase the computational work required
to try candidate roots. These change would be more disruptive and
there is no reason to believe that it is currently necessary.
The proposed rule automatically sunsets. If it is no longer needed
due to the introduction of stronger rules or the acceptance of the
version-grinding form then there would be no reason to continue
with this requirement. If it is still useful at the expiration
time the rule can simply be extended with a new softfork that
sets longer date ranges.
This sun-setting avoids the accumulation of technical debt due
to retaining enforcement of this rule when it is no longer needed
without requiring a hard fork to remove it.
== Overt optimization ==
A BIP for avoiding erroneous warning messages when miners use the overt
version
of the optimization was proposed several years ago, in order to deter the
covert
use of the optimization. But that BIP was rejected.
However, in light of the current discoveries, that BIP could be
reconsidered.
The over optimization does not generally interfere with improvements in the
protocol.
==Backward compatibility==
==Implementation==
==Acknowledgments==
Greg Maxwell <greg@xiph.org> for the original report, which contained
several errors that were corrected in the present proposal.
==Copyright==
This document is placed in the public domain.
--001a11c000ae7132d1054c99cffb
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div><pre></div><div>=C2=A0 BIP: TBD</div><div>=C2=
=A0 Layer: Consensus</div><div>=C2=A0 Title: Inhibiting a covert optimizati=
on on the Bitcoin POW function</div><div>=C2=A0 Author: Sergio Demian Lerne=
r <<a href=3D"mailto:sergio.d.lerner@gmail.com">sergio.d.lerner@gmail.co=
m</a>></div><div>=C2=A0 Status: Draft</div><div>=C2=A0 Type: Standards T=
rack</div><div>=C2=A0 Created: 2016-04-07</div><div>=C2=A0 License: PD</div=
><div></pre></div><div><br></div><div>=3D=3DAbstract=3D=3D</div><div>=
<br></div><div>This proposal inhibits the covert use of a known optimizatio=
n in Bitcoin Proof of Work function.</div><div><br></div><div>The key words=
"MUST", "MUST NOT", "REQUIRED", "SHALL&=
quot;, "SHALL NOT",</div><div>"SHOULD", "SHOULD NO=
T", "RECOMMENDED", "MAY", and "OPTIONAL"=
in this document are to be interpreted as described in RFC 2119.</div><div=
><br></div><div>=3D=3DMotivation=3D=3D</div><div><br></div><div>Due to a de=
sign oversight the Bitcoin proof of work function has a potential</div><div=
>optimization which can allow a rational miner to save up-to 30% of their e=
nergy</div><div>costs (though closer to 20% is more likely due to implement=
ation overheads).</div><div><br></div><div>Timo Hanke and Sergio Demian Ler=
ner applied for a patent on this optimization. The company "Sunrise Te=
ch Group, Llc"=C2=A0has offered to license it to any interested party=
=C2=A0in the past. Sunrise Tech Group has been marketing their patent licen=
ses under the trade-name ASICBOOST.=C2=A0 The document takes no position on=
the validity or enforceability of the patent.</div><div><br></div><div>The=
re are two major ways of taking advantage of this optimization, as describe=
d=C2=A0</div><div>by the patent:=C2=A0</div><div>One way which is highly de=
tectable and is not in use on the network</div><div>today and a covert way =
which has significant interaction and potential</div><div>interference with=
the Bitcoin protocol.=C2=A0 The covert mechanism is not</div><div>easily d=
etected except through its interference with the protocol.</div><div><br></=
div><div>In particular, the protocol interactions of the covert method can =
block the</div><div>implementation of virtuous improvements such as segrega=
ted witness.</div><div><br></div><div>The use of this optimization could re=
sult in a big payoff, but the actual</div><div>sum depends on the degree of=
research, investment and effort put into designing</div><div>the improved =
cores. =C2=A0</div><div><br></div><div>On the above basis the potential for=
covert use of this optimization=C2=A0</div><div>in the covert form and int=
erference with useful improvements presents a=C2=A0</div><div>danger to the=
Bitcoin system.</div><div><br></div><div>=3D=3DBackground=3D=3D</div><div>=
<br></div><div>The general idea of this optimization is that SHA2-256 is a =
merkle damgard hash</div><div>function which consumes 64 bytes of data at a=
time.</div><div><br></div><div>The Bitcoin mining process repeatedly hashe=
s an 80-byte 'block header' while</div><div>incriminating a 32-bit =
nonce which is at the end of this header data. This</div><div>means that th=
e processing of the header involves two runs of the compression</div><div>f=
unction run-- one that consumes the first 64 bytes of the header and a</div=
><div>second which processes the remaining 16 bytes and padding.</div><div>=
<br></div><div>The initial 'message expansion' operations in each s=
tep of the SHA2-256</div><div>function operate exclusively on that step'=
;s 64-bytes of input with no</div><div>influence from prior data that enter=
ed the hash.</div><div><br></div><div>Because of this if a miner is able to=
prepare a block header with</div><div>multiple distinct first 64-byte chun=
ks but identical 16-byte</div><div>second chunks they can reuse the computa=
tion of the initial</div><div>expansion for multiple trials. This reduces p=
ower consumption.</div><div><br></div><div>There are two broad ways of maki=
ng use of this optimization. The obvious</div><div>way is to try candidates=
with different version numbers.=C2=A0 Beyond</div><div>upsetting the soft-=
fork detection logic in Bitcoin nodes this has</div><div>little negative ef=
fect but it is highly conspicuous and easily</div><div>blocked.</div><div><=
br></div><div>The other method is based on the fact that the merkle root</d=
iv><div>committing to the transactions is contained in the first 64-bytes</=
div><div>except for the last 4 bytes of it.=C2=A0 If the miner finds multip=
le</div><div>candidate root values which have the same final 32-bit then th=
ey</div><div>can use the optimization.</div><div><br></div><div>To find mul=
tiple roots with the same trailing 32-bits the miner can</div><div>use effi=
cient collision finding mechanism which will find a match</div><div>with as=
little as 2^16 candidate roots expected, 2^24 operations to</div><div>find=
a 4-way hit, though low memory approaches require more</div><div>computati=
on.</div><div><br></div><div>An obvious way to generate different candidate=
s is to grind the</div><div>coinbase extra-nonce but for non-empty blocks e=
ach attempt will</div><div>require 13 or so additional sha2 runs which is v=
ery inefficient.</div><div><br></div><div>This inefficiency can be avoided =
by computing a sqrt number of</div><div>candidates of the left side of the =
hash tree (e.g. using extra</div><div>nonce grinding) then an additional sq=
rt number of candidates of</div><div>the right =C2=A0side of the tree using=
transaction permutation or</div><div>substitution of a small number of tra=
nsactions.=C2=A0 All combinations</div><div>of the left and right side are =
then combined with only a single</div><div>hashing operation virtually elim=
inating all tree related</div><div>overhead.</div><div><br></div><div>With =
this final optimization finding a 4-way collision with a</div><div>moderate=
amount of memory requires ~2^24 hashing operations</div><div>instead of th=
e >2^28 operations that would be require for</div><div>extra-nonce =C2=
=A0grinding which would substantially erode the</div><div>benefit of the op=
timization.</div><div><br></div><div>It is this final optimization which th=
is proposal blocks.</div><div><br></div><div>=3D=3DNew consensus rule=3D=3D=
</div><div><br></div><div>Beginning block X and until block Y the coinbase =
transaction of</div><div>each block MUST either contain a BIP-141 segwit co=
mmitment or a</div><div>correct WTXID commitment with ID 0xaa21a9ef.</div><=
div><br></div><div>(See BIP-141 "Commitment structure" for detail=
s)</div><div><br></div><div>Existing segwit using miners are automatically =
compatible with</div><div>this proposal. Non-segwit miners can become compa=
tible by simply</div><div>including an additional output matching a default=
commitment</div><div>value returned as part of getblocktemplate.</div><div=
><br></div><div>Miners SHOULD NOT automatically discontinue the commitment<=
/div><div>at the expiration height.</div><div><br></div><div>=3D=3DDiscussi=
on=3D=3D</div><div><br></div><div>The commitment in the left side of the tr=
ee to all transactions</div><div>in the right side completely prevents the =
final sqrt speedup.</div><div><br></div><div>A stronger inhibition of the c=
overt optimization in the form of</div><div>requiring the least significant=
bits of the block timestamp</div><div>to be equal to a hash of the first 6=
4-bytes of the header. This</div><div>would increase the collision space fr=
om 32 to 40 or more bits.</div><div>The root value could be required to mee=
t a specific hash prefix</div><div>requirement in order to increase the com=
putational work required</div><div>to try candidate roots. These change wou=
ld be more disruptive and</div><div>there is no reason to believe that it i=
s currently necessary.</div><div><br></div><div>The proposed rule automatic=
ally sunsets. If it is no longer needed</div><div>due to the introduction o=
f stronger rules or the acceptance of the</div><div>version-grinding form t=
hen there would be no reason to continue</div><div>with this requirement.=
=C2=A0 If it is still useful at the expiration</div><div>time the rule can =
simply be extended with a new softfork that</div><div>sets longer date rang=
es.</div><div><br></div><div>This sun-setting avoids the accumulation of te=
chnical debt due</div><div>to retaining enforcement of this rule when it is=
no longer needed</div><div>without requiring a hard fork to remove it.</di=
v><div><br></div><div>=3D=3D Overt optimization =3D=3D</div><div><br></div>=
<div>A BIP for avoiding erroneous warning messages when miners use the over=
t version</div><div>of the optimization was proposed several years ago, in =
order to deter the covert</div><div>use of the optimization. But that BIP w=
as rejected.=C2=A0</div><div>However, in light of the current discoveries, =
that BIP could be reconsidered.</div><div><br></div><div>The over optimizat=
ion does not generally interfere with improvements in the protocol.</div><d=
iv><br></div><div>=3D=3DBackward compatibility=3D=3D</div><div><br></div><d=
iv><br></div><div>=3D=3DImplementation=3D=3D</div><div><br></div><div><br><=
/div><div>=3D=3DAcknowledgments=3D=3D</div><div><br></div><div>Greg Maxwell=
<<a href=3D"mailto:greg@xiph.org">greg@xiph.org</a>> for the origina=
l report, which contained several errors that were corrected in the present=
proposal.</div><div><br></div><div>=3D=3DCopyright=3D=3D</div><div><br></d=
iv><div>This document is placed in the public domain.</div></div>
--001a11c000ae7132d1054c99cffb--
|