diff options
author | Matt Corallo <lf-lists@mattcorallo.com> | 2019-03-06 21:39:15 +0000 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2019-03-06 21:39:19 +0000 |
commit | 9e583a076275af1c3a3be8089c6bc9edb3c96a06 (patch) | |
tree | f5c05879524d6721f550af72f8d8962bbe3b3df2 | |
parent | 5d40c34014e041a6734e8b9a522c04b10c208716 (diff) | |
download | pi-bitcoindev-9e583a076275af1c3a3be8089c6bc9edb3c96a06.tar.gz pi-bitcoindev-9e583a076275af1c3a3be8089c6bc9edb3c96a06.zip |
[bitcoin-dev] BIP Proposal: The Great Consensus Cleanup
-rw-r--r-- | 3a/ef32e2cdb0b00893289d0a33cbeb79aef3e2f3 | 330 |
1 files changed, 330 insertions, 0 deletions
diff --git a/3a/ef32e2cdb0b00893289d0a33cbeb79aef3e2f3 b/3a/ef32e2cdb0b00893289d0a33cbeb79aef3e2f3 new file mode 100644 index 000000000..31d136b4f --- /dev/null +++ b/3a/ef32e2cdb0b00893289d0a33cbeb79aef3e2f3 @@ -0,0 +1,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. + |