Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
BIP XX: Consensus-enforced transaction replacement signaled via nSequence

  BIP: XX
  Title: Consensus-enforced transaction replacement signalled via sequence numbers
  Author: Mark Friedenbach <mark@friedenbach.org>
  Status: Draft
  Type: Standards Track
  Created: 28-05-2015

Table of Contents

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.

Motivation

Bitcoin has sequence number fields for each coin a transaction is spending. 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, and 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 with respect to enforcing transaction replacement without assuming anything other than profit-maximizing behaviour 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 past of the block of the input it is spending. 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 is set.

This is proposed to be accomplished by replacing IsFinalTx(), an existing consensus code function that returns true if a transaction's lock-time constraints are satisfied and false otherwise, with LockTime(), a new function that returns a non-zero value if a transaction's lock-time or sequence number constraints are not satisfied and zero otherwise.

    int64_t LockTime(const CTransaction &tx, int flags, const CCoinsView* pCoinsView, int nBlockHeight, int64_t nBlockTime)
    {
        CCoins coins;
        uint32_t nLockTime;
    
        AssertLockHeld(cs_main);
    
        bool fEnforceBIPXX = flags & LOCKTIME_VERIFY_SEQUENCE;
        if (fEnforceBIPXX && !pCoinsView)
            pCoinsView = pcoinsTip;
    
        // 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).
        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)
                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 (!fEnforceBIPXX)
                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))
                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
                // 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);
        }
    
        // If sequence numbers are MAX_INT / zero relative lock-time, 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 (nBlockHeight == 0)
            nBlockHeight = chainActive.Height();
        if (nMinHeight >= nBlockHeight)
            return nMinHeight;
    
        if (nBlockTime == 0)
            nBlockTime = GetAdjustedTime();
        if (nMinTime >= nBlockTime)
            return nMinTime;
    
        return 0;
    }

Code conditional on the return value of IsFinalTx() has to be updated as well.

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 tx 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.

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.

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.

Implementation

A reference implementation is provided in the following git repository:

https://github.com/maaku/bitcoin/tree/sequencenumbers

Acknowledgements

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.

@btcdrak
Copy link

btcdrak commented Jun 22, 2015

This was given BIP68. Time for a pull request?

Loading

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment