diff options
Diffstat (limited to 'bip-0068.mediawiki')
| -rw-r--r-- | bip-0068.mediawiki | 246 |
1 files changed, 132 insertions, 114 deletions
diff --git a/bip-0068.mediawiki b/bip-0068.mediawiki index 8da92b8..55905af 100644 --- a/bip-0068.mediawiki +++ b/bip-0068.mediawiki @@ -1,7 +1,10 @@ <pre> BIP: 68 - Title: Consensus-enforced transaction replacement signalled via sequence numbers + Title: Relative lock-time using consensus-enforced sequence numbers Author: Mark Friedenbach <mark@friedenbach.org> + BtcDrak <btcdrak@gmail.com> + Nicolas Dorier <nicolas.dorier@gmail.com> + kinoshitajona <kinoshitajona@gmail.com> Status: Draft Type: Standards Track Created: 2015-05-28 @@ -9,17 +12,44 @@ ==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 introduces relative lock-time (RLT) 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. ==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 transactions have a sequence number field for each input. The original idea appears to have been that a transaction in the mempool would be replaced by using the same input with a higher sequence value. Although this was not properly implemented, it assumes miners would prefer higher sequence numbers even if the lower ones were more profitable to mine. However, a miner acting on profit motives alone would break that assumption completely. The change described by this BIP repurposes the sequence number for new use cases without breaking existing functionality. It also leaves room for future expansion and other use cases. + +The transaction nLockTime is used to prevent the mining of a transaction until a certain date. nSequence will be repurposed to prevent mining of a transaction until a certain age of the spent output in blocks or timespan. This, among other uses, allows bi-directional payment channels as used in [https://github.com/ElementsProject/lightning/raw/master/doc/deployable-lightning.pdf Hashed Timelock Contracts (HTLCs)] and [https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki#Bidirectional_Payment_Channels BIP112]. ==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. +This specification defines the meaning of sequence numbers for transactions with an nVersion greater than or equal to 2 for which the rest of this specification relies on. + +All references to median-time-past (MTP) are as defined by BIP113. + +If bit (1 << 31) of the sequence number is set, then no consensus meaning is applied to the sequence number and can be included in any block under all currently possible circumstances. + +If bit (1 << 31) of the sequence number is not set, then the sequence number is interpreted as an encoded relative lock-time. + +The sequence number encoding is interpreted as follows: + +Bit (1 << 22) determines if the relative lock-time is time-based or block based: If the bit is set, the relative lock-time specifies a timespan in units of 512 seconds granularity. The timespan starts from the median-time-past of the output’s previous block, and ends at the MTP of the previous block. If the bit is not set, the relative lock-time specifies a number of blocks. + +The flag (1<<22) is the highest order bit in a 3-byte signed integer for use in bitcoin scripts as a 3-byte PUSHDATA with OP_CHECKSEQUENCEVERIFY (BIP 112). + +This specification only interprets 16 bits of the sequence number as relative lock-time, so a mask of 0x0000ffff MUST be applied to the sequence field to extract the relative lock-time. The 16-bit specification allows for a year of relative lock-time and the remaining bits allow for future expansion. + +<img src=bip-0068/encoding.png></img> + +For time based relative lock-time, 512 second granularity was chosen because bitcoin blocks are generated every 600 seconds. So when using block-based or time-based, the same amount of time can be encoded with the available number of bits. Converting from a sequence number to seconds is performed by multiplying by 512 = 2^9, or equivalently shifting up by 9 bits. + +When the relative lock-time is time-based, it is interpreted as a minimum block-time constraint over the input's age. A relative time-based lock-time of zero indicates an input which can be included in any block. More generally, a relative time-based lock-time n can be included into any block produced 512 * n seconds after the mining date of the output it is spending, or any block thereafter. +The mining date of the output is equals to the median-time-past of the previous block which mined it. + +The block produced time is equal to the median-time-past of its previous block. -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: +When the relative lock-time is block-based, it is interpreted as a minimum block-height constraint over the input's age. A relative block-based lock-time of zero indicates an input which can be included in any block. More generally, a relative block lock-time n can be included n blocks after the mining date of the output it is spending, or any block thereafter. + +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,183 +57,171 @@ This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), LOCKTIME_VERIFY_SEQUENCE = (1 << 0), }; - const uint32_t SEQUENCE_THRESHOLD = (1 << 31); - - int64_t LockTime(const CTransaction &tx, - int flags, const CCoinsView* pCoinsView, - int nBlockHeight, int64_t nBlockTime) + /* Setting nSequence to this value for every input in a transaction + * disables nLockTime. */ + static const uint32_t SEQUENCE_FINAL = 0xffffffff; + + /* If this flag set, CTxIn::nSequence is NOT interpreted as a + * relative lock-time. Setting the most significant bit of a + * sequence number disabled relative lock-time. */ + static const uint32_t SEQUENCE_LOCKTIME_DISABLE_FLAG = (1 << 31); + + /* If CTxIn::nSequence encodes a relative lock-time and this flag + * is set, the relative lock-time has units of 512 seconds, + * otherwise it specifies blocks with a granularity of 1. */ + static const uint32_t SEQUENCE_LOCKTIME_TYPE_FLAG = (1 << 22); + + /* If CTxIn::nSequence encodes a relative lock-time, this mask is + * applied to extract that lock-time from the sequence field. */ + static const uint32_t SEQUENCE_LOCKTIME_MASK = 0x0000ffff; + + /* In order to use the same number of bits to encode roughly the + * same wall-clock duration, and because blocks are naturally + * limited to occur every 600s on average, the minimum granularity + * for time-based relative lock-time is fixed at 512 seconds. + * Converting from CTxIn::nSequence to seconds is performed by + * multiplying by 512 = 2^9, or equivalently shifting up by + * 9 bits. */ + static const int SEQUENCE_LOCKTIME_GRANULARITY = 9; + + int64_t LockTime(const CTransaction &tx, int flags, const std::vector<int>* prevHeights, const CBlockIndex& block) { - CCoins coins; - uint32_t nLockTime; - - bool fEnforceBIP68 = tx.nVersion >= 2 + assert(prevHeights == NULL || prevHeights->size() == tx.vin.size()); + int64_t nBlockTime = (flags & LOCKTIME_MEDIAN_TIME_PAST) + ? block.GetAncestor(std::max(block.nHeight-1, 0))->GetMedianTimePast() + : block.GetBlockTime(); + + bool fEnforceBIP68 = static_cast<uint32_t>(tx.nVersion) >= 2 && flags & LOCKTIME_VERIFY_SEQUENCE; - + // Will be set to the equivalent height- and time-based nLockTime // values that would be necessary to satisfy all relative lock- // 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) + for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) { + const CTxIn& txin = tx.vin[txinIndex]; + // Set a flag if we witness an input that isn't finalized. + if (txin.nSequence == CTxIn::SEQUENCE_FINAL) 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. + // unless we have been instructed to, and a view has been + // provided. if (!fEnforceBIP68) continue; - // Skip this input if it is not in the UTXO set. This should - // only ever happen in non-consensus code. - if (!pCoinsView->GetCoins(txin.prevout.hash, coins)) + // Sequence numbers with the most significant bit set are not + // treated as relative lock-times, nor are they given any + // consensus-enforced meaning at this point. + if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLE_FLAG) continue; - if (nLockTime < LOCKTIME_THRESHOLD) - // We subtract 1 from relative lock-times because of 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); - else + if (prevHeights == NULL) + continue; + + int nCoinHeight = (*prevHeights)[txinIndex]; + + if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) { + + int64_t nCoinTime = block.GetAncestor(std::max(nCoinHeight-1, 0))->GetMedianTimePast(); + // 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. - nMinTime = std::max(nMinTime, - pindexBestHeader->GetAncestor(coins.nHeight-1)->GetMedianTimePast() - - LOCKTIME_THRESHOLD + (int64_t)nLockTime); + nMinTime = std::max(nMinTime, nCoinTime + (int64_t)((txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) << CTxIn::SEQUENCE_LOCKTIME_GRANULARITY) - 1); + } else { + // 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, nCoinHeight + (int)(txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) - 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; - + if ((int64_t)tx.nLockTime < LOCKTIME_THRESHOLD) nMinHeight = std::max(nMinHeight, (int)tx.nLockTime); else nMinTime = std::max(nMinTime, (int64_t)tx.nLockTime); - if (nMinHeight >= nBlockHeight) + if (nMinHeight >= block.nHeight) return nMinHeight; + if (nMinTime >= nBlockTime) return nMinTime; return 0; - } - - int64_t CheckLockTime(const CTransaction &tx, int flags) - { - AssertLockHeld(cs_main); - - // By convention a negative value for flags indicates that the - // current network-enforced consensus rules should be used. - flags = std::max(flags, 0); - - // pcoinsTip contains the UTXO set for chainActive.Tip() - const CCoinsView *pCoinsView = pcoinsTip; - - // CheckLockTime() uses chainActive.Height()+1 to evaluate - // nLockTime because when LockTime() is called within - // CBlock::AcceptBlock(), the height of the block *being* - // evaluated is what is used. Thus if we want to know if a - // transaction can be part of the *next* block, we need to call - // LockTime() with one more than chainActive.Height(). - const int nBlockHeight = chainActive.Height() + 1; - - // Timestamps on the other hand don't get any special treatment, - // because we can't know what timestamp the next block will have, - // and there aren't timestamp applications where it matters. - const int64_t nBlockTime = GetAdjustedTime(); - - return LockTime(tx, flags, pCoinsView, nBlockHeight, nBlockTime); - } -</pre> + }</pre> Code conditional on the return value of IsFinalTx() / CheckLockTime() has to be updated as well, since the semantics of the return value has been inverted. -==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. - ==Example: Bidirectional payment channel== -A bidirectional payment channel can be established by two parties funding a single output in the following way: Alice funds a 1btc output which is the 2-of-2 multisig of Alice AND Bob, or Alice's key only after a sufficiently long timeout, e.g. 30 days or 4320 blocks. The channel-generating transaction is signed by Alice and broadcast to the network. +A bidirectional payment channel can be established by two parties funding a single output in the following way: Alice funds a 1 BTC output which is the 2-of-2 multisig of Alice AND Bob, or Alice's key only after a sufficiently long timeout, e.g. 30 days or 4320 blocks. The channel-generating transaction is signed by Alice and broadcast to the network. -Alice desires to send Bob a payment of 0.1btc. She does so by constructing a transaction spending the 1btc output and sending 0.1btc to Bob and 0.9btc back to herself. She provides her signature for the 2-of-2 multisig constraint, and sets a relative lock-time using the sequence number field such that the transaction will become valid 24-hours or 144 blocks before the refund timeout. Two more times Alice sends Bob a payment of 0.1btc, each time generating and signing her half of a transaction spending the 1btc output and sending 0.2btc, then 0.3btc to Bob with a relative lock-time of 29 days from creation of the channel. +Alice desires to send Bob a payment of 0.1 BTC. She does so by constructing a transaction spending the 1 BTC output and sending 0.1 BTC to Bob and 0.9 BTC back to herself. She provides her signature for the 2-of-2 multisig constraint, and sets a relative lock-time using the sequence number field such that the transaction will become valid 24-hours or 144 blocks before the refund timeout. Two more times Alice sends Bob a payment of 0.1 BTC, each time generating and signing her half of a transaction spending the 1btc output and sending 0.2 BTC, then 0.3 BTC to Bob with a relative lock-time of 29 days from creation of the channel. -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. +Bob now desires to send Alice a refund of 0.25 BTC. He does so by constructing a transaction spending the 1btc output and sending 0.95 BTC (= 0.7 BTC + 0.25 BTC) to Alice and 0.05 BTC to himself. Since Bob will still have in his logs the transaction giving him 0.7 BTC 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== -A reference implementation is provided in the following git repository: +A reference implementation is provided by the following pull request + +https://github.com/bitcoin/bitcoin/pull/6312 -https://github.com/maaku/bitcoin/tree/sequencenumbers +==Acknowledgments== -==Acknowledgements== +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. -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. +This BIP was edited by BtcDrak, Nicolas Dorier and kinoshitajona. ==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. +This BIP is to be deployed by either version-bits BIP9 or by isSuperMajority(). Exact details TDB. -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. +BIP68 MUST be deployed together with BIP113. It is also recommended to deploy BIP112 at the same time. ==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. +As can be seen from the specification section, a number of bits are undefined by this BIP to allow for other use cases by setting bit (1 << 31) as the remaining 31 bits have no meaning under this BIP. Additionally, bits (1 << 23) through (1 << 30) inclusive have no meaning at all when bit (1 << 31) is unset. -The most efficient way to calculate sequence number from relative lock-time is with bit-inversion: +Additionally, this BIP specifies only 16 bits to actually encode relative lock-time meaning a further 6 are unused (1 << 16 through 1 << 21 inclusive). This allows the possibility to increase granularity by soft-fork, or for increasing the maximum possible relative lock-time in the future. -<pre> - // 0 <= nHeight < 500,000,000 blocks - nSequence = ~(nHeight); - nHeight = ~(nSequence); - - // 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: +The most efficient way to calculate sequence number from relative lock-time is with bit masks and shifts: <pre> - nSequence = 0xffffffff - nHeight; - nHeight = 0xffffffff - nSequence; + // 0 <= nHeight < 65,535 blocks (1.25 years) + nSequence = nHeight; + nHeight = nSequence & 0x0000ffff; - nSequence = 0xffffffff - nTime + 1 - LOCKTIME_THRESHOLD; - nTime = 0xffffffff - nSequence + 1 - LOCKTIME_THRESHOLD; + // 0 <= nTime < 33,554,431 seconds (1.06 years) + nSequence = (1 << 22) | (nTime >> 9); + nTime = (nSequence & 0x0000ffff) << 9; </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 +BIP112: https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki + +BIP113: https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki -BIP 65: OP_CHECKLOCKTIMEVERIFY, https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki +Hashed Timelock Contrats (HTLCs): https://github.com/ElementsProject/lightning/raw/master/doc/deployable-lightning.pdf -BIP 66: Strict DER signatures, https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki |