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
|
Return-Path: <lf-lists@mattcorallo.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 1E3EB66BC
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 6 Mar 2019 21:39:19 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mail.bluematt.me (mail.bluematt.me [192.241.179.72])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id ACDD3180
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 6 Mar 2019 21:39:17 +0000 (UTC)
Received: from [10.233.42.100] (gw.vpn.bluematt.me [144.217.106.88])
by mail.bluematt.me (Postfix) with ESMTPSA id 4380B12035A;
Wed, 6 Mar 2019 21:39:16 +0000 (UTC)
From: Matt Corallo <lf-lists@mattcorallo.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <bf96c2fb-2e2e-a47f-e59f-87e56d83eca3@mattcorallo.com>
Date: Wed, 6 Mar 2019 21:39:15 +0000
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
Thunderbird/60.5.0
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 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: Thu, 07 Mar 2019 10:14:22 +0000
Cc: Luke Dashjr <luke_bipeditor@dashjr.org>
Subject: [bitcoin-dev] BIP Proposal: The Great Consensus Cleanup
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, 06 Mar 2019 21:39:19 -0000
The following is a proposed BIP to soft-fork out some oddities in the
current Bitcoin consensus rules, resolving several vulnerabilities, in
addition to fixing the timewarp vulnerability. I'd like to ask the BIP
editor to assign a BIP number.
The latest version of the BIP can be found at
https://github.com/TheBlueMatt/bips/blob/cleanup-softfork/bip-XXXX.mediawiki
(a text copy is included below).
Some things that may be worth discussing:
* Note that the activation times in this BIP may result in the
activation of the new soft-fork rules on the same block as the scheduled
block-subsidy halving. Sadly, avoiding this either requires a
significantly compressed BIP activation time (which may result in the
rules not activating for benign reasons) or beginning the activation
process significantly into the future.
* The BIP proposes allowing timestamps on the difficulty-adjustment
block to go backwards by 600 seconds which has the nice property of
making the difficulty-adjustment algorithm target almost exactly one
block per 600 seconds in the worst-case (where miners are attempting to
exploit the timewarp attack), while avoiding any potential hardware
bricking (assuming upgrades on the part of mining pools). Alternatively,
some have proposed allowing the time to go backwards 7200 seconds, which
introduces some small level of inflation in the case of a miner attack
(though much less than we've had historically simply due to the rapidly
growing hashrate) but avoids any requirements for upgrades as the
existing 7200-second-in-the-future check implies miners will only ever
build on blocks for which they can set the next timestamp to their
current time.
* The 4th change (making non-standard signature hash types invalid)
may be worth discussing. In order to limit the number of potential
signature hashes which could be used per-input (allowing us to cache
them to avoid re-calculation), we can disable non-standard sighash
types. Alternatively, however, most of the same effect could be achieved
by caching the just-before-the-last-byte sighash midstate and hashing
only the last byte when a checking signatures. Still, them having been
non-standard for many years makes me doubt there is much risk involved
in disabling them, and I don't see much potential use-case for keeping
them around so I'd like to just remove them.
As for why the timewarp vulnerability should (IMO rather obviously) be
fixed, it seems rather clear that the only potential use for exploiting
it would be either to inflate the currency supply maliciously by miners
or to fork in what amounts to extension blocks. As for why extension
blocks are almost certainly not the right approach to such changes, its
likely worth reading this old post:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-January/013510.html
<pre>
BIP: XXXX
Layer: Consensus (soft fork)
Title: The Great Consensus Cleanup
Author: Matt Corallo
Status: Draft
Type: Standards Track
Created: 2019-01-28
License: PD
</pre>
==Abstract==
This BIP defines a set of consensus changes which reduce the complexity
of Bitcoin implementations and improve worst-case validation times,
fixing a number of long-standing vulnerabilities.
==Motivation==
BIP 143 significantly improved certain aspects of Bitcoin's consensus
rules, key to this being changes to the format of the data which is
hashed and signed in CHECKSIG operations during script execution.
However, several improvements were left for later forks to avoid
bloating the original activation with unrelated changes. This BIP seeks
to make some of these changes as well as a few other simplifications.
Specifically, this BIP proposes the following changes:
* Worst-case validation time for non-BIP 143 transactions has long been
considered a significant vulnerability. To address this, both
OP_CODESEPARATOR in non-BIP 143 scripts and FindAndDelete fail script
validation, among other cleanups. This drastically reduces worst-case
validation time for non-BIP 143 transactions by enabling Signature Hash
caching on a per-input basis. While validation time of large, simple
non-BIP 143 transactions can still be excessively high on their own,
removing these multipliers goes a long way towards resolving the issue.
* By further restricting nTime fields on difficulty adjustment blocks,
we propose fixing the long-standing "timewarp" inflation vulnerability
in Bitcoin's difficulty adjustment without risking existing mining
hardware becoming unusable. This limits the worst-case difficulty
adjustment target in case of attack from the current exponential growth,
to once every roughly 600 seconds. Note that no change in default
behavior is proposed, keeping the existing target of one block every
~600.6 seconds[1] in the common case (ie we limit the attack scenario to
about a 0.1% inflation rate, much smaller than the historical inflation
rate due to rapid hashrate growth).
* Several vulnerabilities where Bitcoin clients needed to check for
specific cases of malleation in the merkle tree construction are
resolved by making certain transaction sizes invalid.
==Specification==
Upon activation, the following rules will be enforced on all new blocks:
* scriptSigs which contain non-push opcodes fail the script validation.
Push opcodes are OP_0 - OP_1NEGATE and OP_1 - OP_16. Note that this
implies any opcodes in scriptSigs greater than 0x60 will fail script
validation, in addition to OP_RESERVED (0x50, which already fails script
execution in executed branches, though all branches are now guaranteed
to execute).
* OP_CODESEPARATOR in non-BIP 143 scripts fails the script validation.
This includes OP_CODESEPARATORs in unexecuted branches of if statements,
similar to other disabled opcodes, but unlike OP_RETURN.
* When validating signatures in non-BIP 143 scripts, if the scriptPubKey
being executed contains, pushed as a single element using minimal
PUSHDATA, a signature stack element being validated, the script fails
validation. For the avoidance of doubt, any FindAndDelete matches result
in script execution failure.
* If the sighash type byte (ie last byte in a signature being evaluated
during the execution of OP_CHECKSIG[VERIFY] or OP_CHECKMULTISIG[VERIFY])
is anything other than 1, 2, 3, 0x81, 0x82, or 0x83, the script
execution fails. This does not apply to 0-length signature stack elements.
* Transactions smaller than 65 bytes when serialized without witness
data are invalid.
* The nTime field of each block whose height, mod 2016, is 0 must be
greater than or equal to the nTime field of the immediately prior block
minus 600. For the avoidance of doubt, such blocks must still comply
with existing Median-Time-Past nTime restrictions.
==Deployment==
This BIP will be deployed by "version bits" BIP9 with the name
"cleanups" and using bit (0-indexed) 3.
For Bitcoin mainnet, the BIP9 starttime will be midnight August 1st,
2019 UTC (Epoch timestamp 1564617600) and BIP9 timeout will be midnight
August 1st, 2020 UTC (Epoch timestamp 1596240000).
For Bitcoin testnet, the BIP9 starttime will be midnight June 1st, 2019
UTC (Epoch timestamp 1559347200) and BIP9 timeout will be midnight June
1st, 2020 UTC (Epoch timestamp 1590969600).
==Discussion==
* There are very few known uses for OP_CODESEPARATOR and none for
FindAndDelete. None of these uses enable new functionality, and any
efficiency gains are better made by switching to BIP 141. Further, there
is no known use of either on the chain today, and both have been
non-standard in Bitcoin Core since version 0.16.1, making them much more
difficult to have mined. Both changes, together, allow for signature
hash caching within each input script in a non-BIP 143 transaction
today. Note that due to their non-standardness, miners using Bitcoin
Core version 0.16.1 or later will not mine blocks which violate these
rules today.
* Reducing valid scriptSigs to the minimal set of operations which can
generate any stack state removes the requirement that scriptCodes need
to be generated for scriptSig execution, reducing the possible set of
scriptCodes which must be cached per input by 2x. Because any stack
state can be created using only push opcodes, this does not reduce
spendability except for pessimal scriptPubKeys which require a
significant number of identical stack elements (ie created using
OP_DUP). Note that such transactions have been non-standard in Bitcoin
Core since before git history (SVN 197) and thus miners running Bitcoin
Core will not mine such transactions today.
* Further, disabling non-canonical sighash types allows caching of the
sighash themselves instead of midstates (as the sighash type byte is
included in the sighash itself). Avoiding applying this rule to 0-length
signatures avoids breaking deliberate OP_CHECKSIG failures while still
avoiding having to ever calculate such sighashes. Such sighashes have
been non-standard and thus miners using Bitcoin Core version 0.8 or
higher will not mine blocks containing such transactions today.
<br/>
* While there are no known attempts to exploit the "timewarp"
vulnerability on Bitcoin's mainnet today, and the authors do not believe
it is likely to occur in the immediate future, removing the possibility
has long been on various wishlists and greatly simplifies potential
attack analysis.
** Sadly, some deployed mining hardware relies on the ability to roll
nTime forward by up to 600 seconds[3]. Thus, only requiring that the
nTime field move forward during difficulty adjustment would allow a
malicious miner to prevent some competitors from mining the next block
by setting their timestamp to two hours in the future. Thus, we allow
nTime to go backwards by 600 seconds, ensuring that even a block with a
timestamp two hours in the future allows for 600 seconds of nTime
rolling on the next block.
** Note that miners today only enforce increasing timestamps against the
median-timestamp-of-last-11-blocks, so miners who do not upgrade may
mine a block which violates this rule at the beginning of a difficulty
window if the last block in a difficulty window has a timestamp in the
future. Thus, it is strongly recommended that SPV clients enforce the
new nTime rules to avoid following any potential forks which occur.
<br/>
* The issues involved in having leaf nodes in the transaction merkle
tree which can be confused for inner nodes are well documented.
[4][5][6] While there are workarounds for the pitfalls, there are many
SPV-proof-validators which do not implement them. Further, the limited
use-cases for very small transactions does not suffice as reason to
force the added complexity onto clients. Note that any transactions
smaller than 83 bytes have been considered non-standard since Bitcoin
Core version 0.17.0, so miners will not mine blocks which validate this
rule by default.
<br/>
* There are several early-stage proposals which may affect the execution
of scripts, including proposals such as Schnorr signatures, Taproot,
Graftroot, and MAST. These proposals are not expected to have any
interaction with the changes in this BIP, as they are likely to only
apply to SegWit scripts, which are not covered by any of the new rules
except for the sighash type byte rule. Thus, the sighash type byte rule
defined above only applies to *current* signature-checking opcodes, as
any new signature-checking is likely to be implemented via the
introduction of new opcodes.
<br/>
* In spite of some suggestion that other activation methods be used, BIP
9 is proposed as ensuring miners have upgraded to enforce new rules is
an important part of minimizing disruption. While previous BIP 9
soft-forks have resulted in political contention, this
comparatively-unimportant soft-fork provides a good opportunity to
attempt to return to utilizing BIP 9 to ensure miner upgrade prior to
activation, which the authors believe is a critical goal. However, if
there is broad agreement to activate these rules when the BIP 9 expiry
time is reached, and miners have not yet signaled sufficient level of
readiness, a later flag-day activation may be merited. For this reason,
implementations may wish to provide a compatibility option which allows
flag-day enforcement of these rules without an update.
==Reference Implementation==
[https://github.com/bitcoin/bitcoin/pull/15482 Bitcoin Core Pull #15482]
==References==
[1] The difficulty adjustment algorithm in Bitcoin multiplies the
previous difficulty by (2016 / time taken to mine the last 2015 blocks).
Intuitively[2], this implies the actual Inter-Block-Time (IBT) target is
2016/2015*600, or about 600.3 seconds. However, the expected value of
the inverse of an Erlang distribution (which the above is effectively
sampling from) is actually 1/(N-1), not 1/N. Thus, the above expression
actually targets an IBT of 2016/2014*600, or about 600.6 seconds, ie
E(2016*600/X) = 1 where X~ErlangDistribution(k=2015, λ=1/IBT) when IBT
is 2016/2014*600. This is equivalent to 600*E(2016*600/X) where
X~ErlangDistribution(k=2015, λ=1/600). In the case of a miner
deliberately reducing timestamps by 600 seconds on the
difficulty-retargeting block, we are effectively changing the difficulty
multiplier to (2016 / (time taken to mine the last 2016 blocks + 600)),
or 600*E(2016*600/(X + 600)) where X~Erlang Distribution(k=2016,
λ=1/600), which is effectively targeting an inter-block time of
~599.9999 seconds.
[2] See [https://twitter.com/pwuille/status/1098288749098795008] for
most peoples' intuition. For more info see Pieter's writeup at
[https://gist.github.com/sipa/1a70884abe6d0a7cddc340c99f741a41]
[3] While no official stratum specification exists, the btc.com pool
server (one of the most popular pool servers today) rejects shares with
timestamps more than 600 seconds in the future at
[https://github.com/btccom/btcpool/blob/e7c536834fd6785af7d7d68ff29111ed81209cdf/src/bitcoin/StratumServerBitcoin.cc#L384].
While there are few resources describing hardware operation today,
timestamp rolling can be observed on the chain (in some rare cases) as
block timestamps go backwards when a miner rolled one block nTime
forward and the next does not, but only incredibly rarely more than 600
seconds.
[4]
[https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016091.html]
[5]
[https://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180609/9f4f5b1f/attachment-0001.pdf]
[6]
[https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-February/016697.html]
==Acknowledgments==
Thanks (in alphabetical order) to Suhas Daftuar, James Hilliard, Johnson
Lau, Steve Lee, Greg Maxwell, John Newberry, and Pieter Wuille for their
helpful feedback at various stages as well as the entire Bitcoin
Protocol Development Community.
|