summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMatt Corallo <lf-lists@mattcorallo.com>2019-03-06 21:39:15 +0000
committerbitcoindev <bitcoindev@gnusha.org>2019-03-06 21:39:19 +0000
commit9e583a076275af1c3a3be8089c6bc9edb3c96a06 (patch)
treef5c05879524d6721f550af72f8d8962bbe3b3df2
parent5d40c34014e041a6734e8b9a522c04b10c208716 (diff)
downloadpi-bitcoindev-9e583a076275af1c3a3be8089c6bc9edb3c96a06.tar.gz
pi-bitcoindev-9e583a076275af1c3a3be8089c6bc9edb3c96a06.zip
[bitcoin-dev] BIP Proposal: The Great Consensus Cleanup
-rw-r--r--3a/ef32e2cdb0b00893289d0a33cbeb79aef3e2f3330
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.
+