diff options
Diffstat (limited to 'bip-0068.mediawiki')
| -rw-r--r-- | bip-0068.mediawiki | 83 |
1 files changed, 58 insertions, 25 deletions
diff --git a/bip-0068.mediawiki b/bip-0068.mediawiki index e336765..12b97c7 100644 --- a/bip-0068.mediawiki +++ b/bip-0068.mediawiki @@ -13,15 +13,15 @@ This BIP describes a modification to the consensus-enforced semantics of the seq ==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" 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. +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 an 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== 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. -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. +If the second most significant bit (1 << 30) is clear, the next 16 bits are interpreted as a minimum block-height constraint over the input's age. The remaining 14 bits have no consensus-enforced meaning. 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, but cannot be included in the same block as its parent. A sequence number of 2 << 14 can't be included until at least 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. +Alternatively, if the second most significant bit (1 << 30) is set, the next 25 bits are interpreted as a minimum block-time constraint over the input's age. The remaining 5 bits have no consensus-enforced meaning. 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: @@ -52,7 +52,7 @@ This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), { CCoins coins; - bool fEnforceBIP68 = tx.nVersion >= 2 + bool fEnforceBIP68 = static_cast<uint32_t>(tx.nVersion) >= 2 && flags & LOCKTIME_VERIFY_SEQUENCE; // Will be set to the equivalent height- and time-based nLockTime @@ -72,8 +72,9 @@ This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), fFinalized = false; // Do not enforce sequence numbers as a relative lock time - // unless we have been instructed to. - if (!fEnforceBIP68) + // unless we have been instructed to, and a view has been + // provided. + if (!(fEnforceBIP68 && pCoinsView)) continue; // Sequence numbers equal to or above the locktime threshold @@ -82,31 +83,62 @@ This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), 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 (txin.nSequence < CTxIn::SEQUENCE_UNITS_THRESHOLD) + // Fetch the UTXO corresponding to this input. + if (!pCoinsView->GetCoins(txin.prevout.hash, coins)) { + // It is fully expected that coinbases inputs are not + // found in the UTXO set. Proceed to the next intput... + if (txin.prevout.IsNull()) + continue; + // If a non-coinbase input cannot be found, we cannot + // be certain about whether lock-time constraints have + // been satisfied. Note that it should only ever be + // possible for this to happen with wallet transactions + // that have unknown inputs. + else + return std::numeric_limits<int64_t>::max(); + } + + // coins.nHeight is MEMPOOL_HEIGHT (an absurdly high value) + // if the parent transaction was from the mempool. We can't + // know what height it will have once confirmed, but we + // assume it makes it in the same block. + int nCoinHeight = std::min(coins.nHeight, nBlockHeight); + + 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)(txin.nSequence >> CTxIn::SEQUENCE_BLOCKS_OFFSET) - - 1); - else + nMinHeight = std::max(nMinHeight, nCoinHeight + (int)( + txin.nSequence >> CTxIn::SEQUENCE_BLOCKS_OFFSET) - 1); + } else { + // In two locations that follow we make reference to + // chainActive.Tip(). To prevent a race condition, we + // store a reference to the current tip. + // + // Note that it is not guaranteed that indexBestBlock will + // be consistent with the passed in view. The proper thing + // to do is to have the view return time information about + // UTXOs. + const CBlockIndex& indexBestBlock = *chainActive.Tip(); + + // The only time the negative branch of this conditional + // is executed is when the prior output was taken from the + // mempool, in which case we assume it makes it into the + // same block (see above). + int64_t nCoinTime = (nCoinHeight <= (indexBestBlock.nHeight+1)) + ? indexBestBlock.GetAncestor(nCoinHeight-1)->GetMedianTimePast() + : nBlockTime; + // 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. We subtract one for the same reason as // above. - nMinTime = std::max(nMinTime, - pindexBestHeader->GetAncestor(coins.nHeight-1)->GetMedianTimePast() - + (int64_t)((txin.nSequence ^ CTxIn::SEQUENCE_UNITS_THRESHOLD) >> CTxIn::SEQUENCE_SECONDS_OFFSET) - - 1); + nMinTime = std::max(nMinTime, nCoinTime + (int64_t)(( + txin.nSequence - CTxIn::SEQUENCE_UNITS_THRESHOLD) + >> CTxIn::SEQUENCE_SECONDS_OFFSET) - 1); + } } // If all sequence numbers are CTxIn::SEQUENCE_FINAL, the @@ -137,7 +169,8 @@ This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), flags = std::max(flags, 0); // pcoinsTip contains the UTXO set for chainActive.Tip() - const CCoinsView *pCoinsView = pcoinsTip; + CCoinsViewMemPool viewMemPool(pcoinsTip, mempool); + const CCoinsView *pCoinsView = &viewMemPool; // CheckLockTime() uses chainActive.Height()+1 to evaluate // nLockTime because when LockTime() is called within @@ -174,9 +207,9 @@ Alice and Bob continue to make payments to each other, decrementing the relative ==Implementation== -A reference implementation is provided in the following git repository: +A reference implementation is provided by the following pull request -https://github.com/maaku/bitcoin/tree/sequencenumbers +https://github.com/bitcoin/bitcoin/pull/6312 ==Acknowledgments== |