From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 1E3EB66BC for ; 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 ; 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 To: Bitcoin Protocol Discussion Message-ID: 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 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 
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
==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.
* 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.
* 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.
* 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.
* 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.