Rewrite BIP to reflect current state of pull request #6312, including the removal of bit inversion and the allocation of future soft-fork bits.

1 files changed, 71 insertions, 59 deletions

diff --git a/bip-0068.mediawiki b/bip-0068.mediawiki
index 8da92b8..e336765 100644
--- a/bip-0068.mediawiki
+++ b/bip-0068.mediawiki
@@ -1,6 +1,6 @@
 <pre>
   BIP: 68
-  Title: Consensus-enforced transaction replacement signalled via sequence numbers
+  Title: Consensus-enforced transaction replacement signaled via sequence numbers (relative lock-time)
   Author: Mark Friedenbach <mark@friedenbach.org>
   Status: Draft
   Type: Standards Track
@@ -9,17 +9,21 @@
 
 ==Abstract==
 
-This BIP describes a modification to the consensus-enforced semantics of the sequence number field to enable a signed transaction input to remain invalid for a defined period of time after confirmation of its corresponding output, for the purpose of supporting consensus-enforced transaction replacement features.
+This BIP describes a modification to the consensus-enforced semantics of the sequence number field to enable a signed transaction input to remain invalid for a defined period of time after confirmation of its corresponding outpoint, for the purpose of supporting consensus-enforced transaction replacement features.
 
 ==Motivation==
 
-Bitcoin has sequence number fields for each input of a transaction. The original idea appears to have been that the highest sequence number should dominate and miners should prefer it over lower sequence numbers. This was never really implemented, and the half-implemented code seemed to be making this assumption that miners would honestly prefer the higher sequence numbers, even if the lower ones were much much more profitable. That turns out to be a dangerous assumption, and so most technical people have assumed that kind of sequence number mediated replacement was useless because there was no way to enforce "honest" behaviour, as even a few rational (profit maximizing) miners would break that completely. The change described by this BIP provides the missing piece that makes sequence numbers do something significant with respect to enforcing transaction replacement without assuming anything other than profit-maximizing behaviour on the part of miners.
+Bitcoin has sequence number fields for each input of a transaction. The original idea appears to have been that the highest sequence number should dominate and miners should prefer it over lower sequence numbers. This was never really implemented, and the half-implemented code seemed to be making this assumption that miners would honestly prefer the higher sequence numbers, even if the lower ones were much much more profitable. That turns out to be a dangerous assumption, and so most technical people have assumed that kind of sequence number mediated replacement was useless because there was no way to enforce "honest" behavior, as even a few rational (profit maximizing) miners would break that completely. The change described by this BIP provides the missing piece that makes sequence numbers do something significant with respect to enforcing transaction replacement without assuming anything other than profit-maximizing behavior on the part of miners.
 
 ==Specification==
 
-The maximum sequence number can be included in any block, like normal. For transactions with an nVersion of 2 or greater, a sequence number of one less than the maximum can only be included in the next block after the input it is spending, rather than it being possible to be included in the same block. A sequence number one less than that can only be included two blocks later, and so on. Alternatively, a sequence number LOCKTIME_THRESHOLD (500,000,000) less than the maximum (0xffffffff - 500,000,000 = 0xe2329aff) can only be included in a block with an nTime timestamp at least one second greater than the median time stamp of the 11 blocks prior to the block containing the coin being spent. A sequence number one less than that can only be included two seconds later, and so on. This behaviour is only enforced if the most significant bit of the sequence number field is set.
+For transactions with an nVersion of 2 or greater, if the most significant bit (1 << 31) of a sequence number is clear, the remaining 31 bits are interpreted as an encoded relative lock-time. A sequence number with the most significant bit set is given no consensus meaning and can be included in any block, like normal, under all circumstances.
 
-This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), existing consensus code functions that return true if a transaction's lock-time constraints are satisfied and false otherwise, with LockTime() and CheckLockTime(), new functions that return a non-zero value if a transaction's lock-time or sequence number constraints are not satisfied and zero otherwise:
+If the second most significant bit (1 << 30) is clear, the remaining bits reduced by 2^14 are interpreted as a minimum block-heigh constraint over the input's age. A sequence number of zero indicates a relative lock-time of zero blocks (bits 31 and 30 clear) and can be included in any block. A sequence number of 1 << 14 can be included in the next block after the input it is spending, or any block thereafter, rather than it being possible to be included in the same block. A sequence number of 2 << 14 can't be included until two blocks later, and so on.
+
+Alternatively, if the second most significant bit (1 << 30) is set, the remaining bits reduced by 2^5 are interpreted as a minimum block-time constraint over the input's age. A sequence number with just that second most significant bit set (0x40000000) is interpreted as a relative lock-time of 0, measured in seconds, and can be included in the same block as the output being spent. Advancing that sequence number by 2^5 (0x40000020) constrains the transaction to be included in blocks with an nTime timestamp at least one second greater than the median time stamp of the 11 blocks prior to the block containing the coin being spent. Advancing the sequence number by an additional 2^5 (0x40000040) constrains the spend to be two seconds later, and so on.
+
+This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), existing consensus and non-consensus code functions that return true if a transaction's lock-time constraints are satisfied and false otherwise, with LockTime() and CheckLockTime(), new functions that return a non-zero value if a transaction's lock-time or sequence number constraints are not satisfied and zero otherwise:
 
 <pre>
     enum {
@@ -27,14 +31,26 @@ This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(),
         LOCKTIME_VERIFY_SEQUENCE = (1 << 0),
     };
     
-    const uint32_t SEQUENCE_THRESHOLD = (1 << 31);
+    /* Setting nSequence to this value for every input in a transaction
+     * disables nLockTime. */
+    const uint32_t CTxIn::SEQUENCE_FINAL = 0xffffffff;
+    /* Threshold for CTxIn::nSequence: below this value it is interpreted
+     * as arelative lock-time, otherwise ignored. */
+    const uint32_t CTxIn::SEQUENCE_LOCKTIME_THRESHOLD = (1 << 31);
+     /* Threshold for CTxIn::nSequence when interpreted as a relative
+      * lock-time: below this value it has units of blocks, otherwise
+      * seconds. */
+    const uint32_t CTxIn::SEQUENCE_UNITS_THRESHOLD = (1 << 30);
+    /* Number of reserved low-order bits (depending on units used) which
+     * are shifted out prior to relative lock-time constraint checking. */
+    const int CTxIn::SEQUENCE_BLOCKS_OFFSET = 14;
+    const int CTxIn::SEQUENCE_SECONDS_OFFSET = 5;
     
     int64_t LockTime(const CTransaction &tx,
                      int flags, const CCoinsView* pCoinsView,
                      int nBlockHeight, int64_t nBlockTime)
     {
         CCoins coins;
-        uint32_t nLockTime;
     
         bool fEnforceBIP68 = tx.nVersion >= 2
                           && flags & LOCKTIME_VERIFY_SEQUENCE;
@@ -44,56 +60,58 @@ This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(),
         // time constraints given our view of block chain history.
         int nMinHeight = 0;
         int64_t nMinTime = 0;
-        // Will remain equal to true if all inputs are finalized (MAX_INT).
+        // Will remain equal to true if all inputs are finalized
+        // (CTxIn::SEQUENCE_FINAL).
         bool fFinalized = true;
     
         BOOST_FOREACH(const CTxIn& txin, tx.vin) {
-            // The relative lock-time is the inverted sequence number so
-            // as to preserve the semantics MAX_INT means an input is
-            // finalized (0 relative lock-time).
-            nLockTime = ~txin.nSequence;
-    
-            // ~MAX_INT is zero/false, meaning the input is final.
-            if (!nLockTime)
+            // Set a flag if we witness an input that isn't finalized.
+            if (CTxIn::SEQUENCE_FINAL == txin.nSequence)
                 continue;
             else
                 fFinalized = false;
     
-            // Sequence numbers equal to or above the SEQUENCE_THRESHOLD
-            // are not treated as relative lock-times, nor are they given
-            // any consensus-enforced meaning at this point.
-            if (nLockTime >= SEQUENCE_THRESHOLD)
-                continue;
-    
             // Do not enforce sequence numbers as a relative lock time
             // unless we have been instructed to.
             if (!fEnforceBIP68)
                 continue;
     
-            // Skip this input if it is not in the UTXO set. This should
-            // only ever happen in non-consensus code.
+            // Sequence numbers equal to or above the locktime threshold
+            // are not treated as relative lock-times, nor are they given
+            // any consensus-enforced meaning at this point.
+            if (txin.nSequence >= CTxIn::SEQUENCE_LOCKTIME_THRESHOLD)
+                continue;
+    
+            // Skip this input if it is not in the UTXO set. Aside from
+            // the coinbase input, this should only ever happen in non-
+            // consensus code.
             if (!pCoinsView->GetCoins(txin.prevout.hash, coins))
                 continue;
     
-            if (nLockTime < LOCKTIME_THRESHOLD)
-                // We subtract 1 from relative lock-times because of lock
+            if (txin.nSequence < CTxIn::SEQUENCE_UNITS_THRESHOLD)
+                // We subtract 1 from relative lock-times because a lock-
                 // time of 0 has the semantics of "same block," so a lock-
                 // time of 1 should mean "next block," but nLockTime has
                 // the semantics of "last invalid block height."
-                nMinHeight = std::max(nMinHeight, coins.nHeight + (int)nLockTime - 1);
+                nMinHeight = std::max(nMinHeight,
+                      coins.nHeight
+                    + (int)(txin.nSequence >> CTxIn::SEQUENCE_BLOCKS_OFFSET)
+                    - 1);
             else
                 // Time-based relative lock-times are measured from the
                 // smallest allowed timestamp of the block containing the
                 // txout being spent, which is the median time past of the
-                // block prior.
+                // block prior. We subtract one for the same reason as
+                // above.
                 nMinTime = std::max(nMinTime,
                       pindexBestHeader->GetAncestor(coins.nHeight-1)->GetMedianTimePast()
-                    - LOCKTIME_THRESHOLD + (int64_t)nLockTime);
+                    + (int64_t)((txin.nSequence ^ CTxIn::SEQUENCE_UNITS_THRESHOLD) >> CTxIn::SEQUENCE_SECONDS_OFFSET)
+                    - 1);
         }
     
-        // If sequence numbers are MAX_INT / zero relative lock-time, the
-        // transaction is considered final and nLockTime constraints are
-        // not enforced.
+        // If all sequence numbers are CTxIn::SEQUENCE_FINAL, the
+        // transaction is considered final and nLockTime constraints
+        // are not enforced.
         if (fFinalized)
             return 0;
     
@@ -142,7 +160,7 @@ Code conditional on the return value of IsFinalTx() / CheckLockTime() has to be
 
 ==Rationale==
 
-Counting down from the maximum makes sense, since nothing can be higher than the maximum and no transaction can be in a block before its parent transactions. This means that a higher sequence number can always be included earlier than a lower one (even if the time the original coins being spent was unknown when the transaction was authored). Because of this, even rational miners should go along with the scheme: Take the higher sequence number and collect the fees, or skip over it in the hopes that no one else takes a higher number before the next available lower number becomes spendable. And, of course, users are not constrained to make their sequence numbers go down only one at a time. So it's "take the most updated version, now, or gamble that no one in the next dozen blocks takes the most updated and that you manage to include the next to most when it finally becomes mineable." This is similar to how lock-time works. In fact, this scheme is precisely a per-input relative lock-time.
+Using sequence numbers for locking inputs makes sense, since no transaction can be in a block before its parent transactions. This means that a lower sequence number can always be included earlier than a higher one (even if the time the original coins being spent was unknown when the transaction was authored). Because of this, even rational miners should go along with the scheme: Take the lowest sequence number and collect the fees, or skip over it in the hopes that no one else takes a lower number before the next available higher number becomes spendable. And, of course, users are not constrained to make their sequence numbers go up only one at a time. So it's "take the most updated version, now, or gamble that no one in the next dozen blocks takes the most updated and that you manage to include the next to most when it finally becomes mineable." This is similar to how lock-time works. In fact, this scheme is precisely a per-input relative lock-time.
 
 ==Example: Bidirectional payment channel==
 
@@ -152,7 +170,7 @@ Alice desires to send Bob a payment of 0.1btc. She does so by constructing a tra
 
 Bob now desires to send Alice a refund of 0.25btc. He does so by constructing a transaction spending the 1btc output and sending 0.95btc (= 0.7btc + 0.25btc) to Alice and 0.05btc to himself. Since Bob will still have in his logs the transaction giving him 0.7btc 29 days after the creation of the channel, Alice demands that this new transaction have a relative lock-time of 28 days so she has a full day to broadcast it before the next transaction matures.
 
-Alice and Bob continue to make payments to each other, decrementing the relative lock-time by one day each time the channel switches direction, until the present time is reached or either party desires to close out the channel. A close-out is performed by setting the relative lock-time to zero (nSequence = MAX_INT) and both parties signing.
+Alice and Bob continue to make payments to each other, decrementing the relative lock-time by one day each time the channel switches direction, until the present time is reached or either party desires to close out the channel. A close-out is performed by finalizing the input (nSequence = MAX_INT) and both parties signing.
 
 ==Implementation==
 
@@ -160,50 +178,44 @@ A reference implementation is provided in the following git repository:
 
 https://github.com/maaku/bitcoin/tree/sequencenumbers
 
-==Acknowledgements==
+==Acknowledgments==
 
-Credit goes to Gregory Maxwell for providing a succinct and clear description of the behaviour of this change, which became the basis of this BIP text.
+Credit goes to Gregory Maxwell for providing a succinct and clear description of the behavior of this change, which became the basis of this BIP text.
 
 ==Deployment==
 
-We reuse the double-threshold switchover mechanism from BIPs 34 and 66, with the same thresholds, but for nVersion = 4. The new rules are in effect for every block (at height H) with nVersion = 4 and at least 750 out of 1000 blocks preceding it (with heights H-1000..H-1) also have nVersion = 4. Furthermore, when 950 out of the 1000 blocks preceding a block do have nVersion = 4, nVersion = 3 blocks become invalid, and all further blocks enforce the new rules.
+We reuse the double-threshold switch over mechanism from BIPs 34 and 66, with the same thresholds, but for nVersion = 4. The new rules are in effect for every block (at height H) with nVersion = 4 and at least 750 out of 1000 blocks preceding it (with heights H-1000..H-1) also have nVersion = 4. Furthermore, when 950 out of the 1000 blocks preceding a block do have nVersion = 4, nVersion = 3 blocks become invalid, and all further blocks enforce the new rules.
 
-It is recommended that this soft-fork deployment trigger include other related proposals for improving Bitcoin's lock-time capabilities, such as [https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP 65]: OP_CHECKLOCKTIMEVERIFY.
+It is recommended that this soft-fork deployment trigger include other related proposals for improving Bitcoin's lock-time capabilities, including [https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP 65]: OP_CHECKLOCKTIMEVERIFY, [https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki BIP 112]: CHECKSEQUENCEVERIFY, and [https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki BIP 113] Median time-past as endpoint for lock-time calculations.
 
 ==Compatibility==
 
-The only use of sequence numbers by the Bitcoin Core reference client software is to disable checking the nLockTime constraints in a transaction. The semantics of that application are preserved by this BIP without requiring any special-case handling.
+The only use of sequence numbers by the Bitcoin Core reference client software is to disable checking the nLockTime constraints in a transaction. The semantics of that application are preserved by this BIP.
 
-There may be other uses for the sequence number field that are not commonplace or yet to be discoverd. To allow for other uses of the sequence number field, it is only interpreted as a relative lock-time as described in this BIP if the most significant bit is set. This allows up to 31 bits of the sequence number field to be used for other purposes in applicaitons which don't simultaneously need a per-input relative lock-time.
+There may be other uses for the sequence number field that are not commonplace or yet to be discovered. To allow for other uses of the sequence number field, it is only interpreted as a relative lock-time as described in this BIP if the most significant bit is clear. This allows up to 31 bits of the sequence number field to be used for other purposes in applications which don't simultaneously need a per-input relative lock-time. In addition, the unused low-order bits of the relative lock-time encoding are available for use by future soft-fork extensions.
 
-The most efficient way to calculate sequence number from relative lock-time is with bit-inversion:
+The most efficient way to calculate sequence number from relative lock-time is with bit masks and shifts:
 
 <pre>
-    // 0 <= nHeight < 500,000,000 blocks
-    nSequence = ~(nHeight);
-    nHeight = ~(nSequence);
+    // 0 <= nHeight < 65,535 blocks (1.25 years)
+    nSequence = nHeight << 14;
+    nHeight = nSequence >> 14;
     
-    // 1 <= nTime < 1,647,483,648 seconds (52.2 years)
-    nSequence = ~(nTime - 1 + LOCKTIME_THRESHOLD);
-    nTime = ~(nSequence) - LOCKTIME_THRESHOLD + 1;
-</pre>
-
-In languages which do not support bit inversion, the calculation can be accomplished with integer arithmetic instead:
-
-<pre>
-    nSequence = 0xffffffff - nHeight;
-    nHeight = 0xffffffff - nSequence;
-    
-    nSequence = 0xffffffff - nTime + 1 - LOCKTIME_THRESHOLD;
-    nTime = 0xffffffff - nSequence + 1 - LOCKTIME_THRESHOLD;
+    // 0 <= nTime < 33,554,431 seconds (1.06 years)
+    nSequence = 1<<30 | (nTime << 5);
+    nTime = (nSequence ^ 1<<30) >> 5;
 </pre>
 
 ==References==
 
 Bitcoin mailing list discussion: https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg07864.html
 
-BIP 34: Block v2, Height in Coinbase, https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki
+[https://github.com/bitcoin/bips/blob/master/bip-0034.mediawiki BIP 34]: Block v2, Height in Coinbase
+
+[https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP 65]: OP_CHECKLOCKTIMEVERIFY
+
+[https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki BIP 66]: Strict DER signatures
 
-BIP 65: OP_CHECKLOCKTIMEVERIFY, https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki
+[https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki BIP 112]: CHECKSEQUENCEVERIFY
 
-BIP 66: Strict DER signatures, https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki
+[https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki BIP 113]: Median time-past as endpoint for lock-time calculations