summaryrefslogtreecommitdiff
path: root/a9/047c89d90993a557e533aca92271f75e4c2362
blob: 82e09febd079d6a427c5d7b6ed7339b014ab88e0 (plain)
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
Return-Path: <theymos@mm.st>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id DC496910
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed,  5 Apr 2017 23:11:02 +0000 (UTC)
X-Greylist: delayed 00:05:39 by SQLgrey-1.7.6
Received: from out1-smtp.messagingengine.com (out1-smtp.messagingengine.com
	[66.111.4.25])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 0422A90
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed,  5 Apr 2017 23:10:58 +0000 (UTC)
Received: from compute4.internal (compute4.nyi.internal [10.202.2.44])
	by mailout.nyi.internal (Postfix) with ESMTP id 7B99820C97
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed,  5 Apr 2017 19:05:18 -0400 (EDT)
Received: from web5 ([10.202.2.215])
	by compute4.internal (MEProxy); Wed, 05 Apr 2017 19:05:18 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=mm.st; h=
	content-transfer-encoding:content-type:date:from:in-reply-to
	:message-id:mime-version:references:subject:to:x-me-sender
	:x-me-sender:x-sasl-enc; s=fm1; bh=7QgKMCtnEKO7LsUuZC5MweoCjSGQ8
	wB2G2IPrDLfZGw=; b=eozr9IQOb3PvP4MsjWZz764xn2R1esUdFlhWWgx0kExkq
	CSWLbajit/eAUeE0UldKUbnZaCsxFUuyMgDr77c6cENnLfJQZrdMwGYFVX9P7chk
	1prMs/Gx9LgNQNvabbaSSzy+lgj/S6ICjDf+iU+5zRcV+9iGUMmtrf+Q79pMbkE3
	Q/EafGcgVcYrUAsWpTXRgyMjCY/UoGI+BCWYMxvTrgudsPvZpUbb6XggZjgBvhKJ
	tLwOnSNTaKYfUEZPjj9imCT1p7v/2jSRR6+k1h/gWWBhhlk90UBO+ZH6vMisqAFG
	Bp0s8AWjsKfinHWiX9j3N2/S5E5yc93oaUe9AjHVw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=
	messagingengine.com; h=content-transfer-encoding:content-type
	:date:from:in-reply-to:message-id:mime-version:references
	:subject:to:x-me-sender:x-me-sender:x-sasl-enc; s=fm1; bh=7QgKMC
	tnEKO7LsUuZC5MweoCjSGQ8wB2G2IPrDLfZGw=; b=JvkjjSBwzq8hsgaDBkxR++
	9XM5J+sc8ry3/esdSbm/VxZhXR+vbBx9/DUQolhO2nqDtYHA7WjjqsBZF3uHo48a
	019JWLD0Nv0vM8V4Z42YQTu7dkuO6gCznrQSiyD8woX6UoJl4bsZPSgF4dBwbkvw
	mQy7ybRvg9JxSIh597XYo2Jnaetih1PPdyhhshGFcsFFo31kqSdTAFfGXzCR6CZJ
	wRqAvlQYFobrht22J6mUpoAAyliq0mg8kGvrwjB4tkil+hIqsU80/Uyras9ioeQz
	deOAUhZVvIQ+/vR5c3FpXu5DrD+UAhdhsv1gjQl9ON15V5hKnBW/MweCWZJ9OC9A
	==
X-ME-Sender: <xms:LnjlWCqHSPHf0oV5ST0NTDrIo5Nhkioa2oOrh6xxaDAW0NJgI1XQEQ>
Received: by mailuser.nyi.internal (Postfix, from userid 99)
	id 4FC2B9E21D; Wed,  5 Apr 2017 19:05:18 -0400 (EDT)
Message-Id: <1491433518.2765667.935644008.2B153D86@webmail.messagingengine.com>
From: theymos <theymos@mm.st>
To: bitcoin-dev@lists.linuxfoundation.org
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset="utf-8"
X-Mailer: MessagingEngine.com Webmail Interface - ajax-8e6aa83c
In-Reply-To: <CAAS2fgR84898xD0nyq7ykJnB7qkdoCJYnFg6z5WZEUu0+-=mMA@mail.gmail.com>
References: <CAAS2fgR84898xD0nyq7ykJnB7qkdoCJYnFg6z5WZEUu0+-=mMA@mail.gmail.com>
Date: Wed, 05 Apr 2017 18:05:18 -0500
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, LOTS_OF_MONEY,
	RCVD_IN_DNSWL_LOW, T_MONEY_PERCENT autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
X-Mailman-Approved-At: Wed, 05 Apr 2017 23:11:40 +0000
Subject: Re: [bitcoin-dev] BIP proposal: Inhibiting a covert attack 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: Wed, 05 Apr 2017 23:11:03 -0000

This seems to be a serious security problem.  Would it be possible to have
a flag-day softfork included in Bitcoin Core as soon as 0.14.1? I think that a trigger
3-6 months from release should be sufficient for enough of the economy to upgrade,
given the severity of the issue.

BIP 141 says that the the commitment is optional if there are no SegWit transactions in
the block,  so will today's SegWit-ready miners always produce it even when optional
according to BIP 141, as required by this softfork?

On Wed, Apr 5, 2017, at 04:37 PM, Gregory Maxwell via bitcoin-dev wrote:
> A month ago I was explaining the attack on Bitcoin's SHA2 hashcash which
> is exploited by ASICBOOST and the various steps which could be used to
> block it in the network if it became a problem.
> 
> While most discussion of ASICBOOST has focused on the overt method
> of implementing it, there also exists a covert method for using it.
> 
> As I explained one of the approaches to inhibit covert ASICBOOST I
> realized that my words were pretty much also describing the SegWit
> commitment structure.
> 
> The authors of the SegWit proposal made a specific effort to not be
> incompatible with any mining system and, in particular, changed the
> design at one point to accommodate mining chips with forced payout
> addresses.
> 
> Had there been awareness of exploitation of this attack an effort
> would have been made to avoid incompatibility-- simply to separate
> concerns.  But the best methods of implementing the covert attack
> are significantly incompatible with virtually any method of
> extending Bitcoin's transaction capabilities; with the notable
> exception of extension blocks (which have their own problems).
> 
> An incompatibility would go a long way to explain some of the
> more inexplicable behavior from some parties in the mining
> ecosystem so I began looking for supporting evidence.
> 
> Reverse engineering of a particular mining chip has demonstrated
> conclusively that ASICBOOST has been implemented
> in hardware.
> 
> On that basis, I offer the following BIP draft for discussion.
> This proposal does not prevent the attack in general, but only
> inhibits covert forms of it which are incompatible with
> improvements to the Bitcoin protocol.
> 
> I hope that even those of us who would strongly prefer that
> ASICBOOST be blocked completely can come together to support
> a protective measure that separates concerns by inhibiting
> the covert use of it that potentially blocks protocol improvements.
> 
> The specific activation height is something I currently don't have
> a strong opinion, so I've left it unspecified for the moment.
> 
> <pre>
>   BIP: TBD
>   Layer: Consensus
>   Title: Inhibiting a covert attack on the Bitcoin POW function
>   Author: Greg Maxwell <greg@xiph.org>
>   Status: Draft
>   Type: Standards Track
>   Created: 2016-04-05
>   License: PD
> </pre>
> 
> ==Abstract==
> 
> This proposal inhibits the covert exploitation of a known
> vulnerability 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
> attack which can allow an attacking 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 claim to hold a patent on this attack,
> which they have so far not licensed for free and open use by the public.
> They have 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 exploiting the underlying vulnerability: One
> obvious 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.
> 
> Exploitation of this vulnerability could result in payoff of as much as
> $100 million USD per year at the time this was written (Assuming at
> 50% hash-power miner was gaining a 30% power advantage and that mining
> was otherwise at profit equilibrium).  This could have a phenomenal
> centralizing effect by pushing mining out of profitability for all
> other participants, and the income from secretly using this
> optimization could be abused to significantly distort the Bitcoin
> ecosystem in order to preserve the advantage.
> 
> Reverse engineering of a mining ASIC from a major manufacture has
> revealed that it contains an undocumented, undisclosed ability
> to make use of this attack. (The parties claiming to hold a
> patent on this technique were completely unaware of this use.)
> 
> On the above basis the potential for covert exploitation of this
> vulnerability and the resulting inequality in the mining process
> and interference with useful improvements presents a clear and
> present danger to the Bitcoin system which requires a response.
> 
> ==Background==
> 
> The general idea of this attack 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 attack. 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 attack.
> 
> 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 attack.
> 
> 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 attack 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 attack ==
> 
> The non-covert form can be trivially blocked by requiring that
> the header version match the coinbase transaction version.
> 
> This proposal does not include this block because this method
> may become generally available without restriction in the future,
> does not generally interfere with improvements in the protocol,
> and because it is so easily detected that it could be blocked if
> it becomes an issue in the future.
> 
> ==Backward compatibility==
> 
> 
> ==Implementation==
> 
> 
> ==Acknowledgments==
> 
> 
> ==Copyright==
> 
> This document is placed in the public domain.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev