ビットコイン・インスティテュート
ビットコイン・インスティテュート
English

BIP 68 — コンセンサスに​より​強制される​シーケンス番号を​用いた​相対ロックタイム

BIP（ビットコイン改善提案） GitHub · 対象日 · 登録日 · 更新日
人物： マーク・フリーデンバッハ ,  BtcDrak ,  ニコラ・ドリエ ,  kinoshitajona
ソフトフォークコンセンサスタイムロックライトニングネットワーク
マーク・フリーデンバッハ（Mark Friedenbach） 2015年5月28日 
BIP: 68
  Layer: Consensus (soft fork)
  Title: Relative lock-time using consensus-enforced sequence numbers
  Authors: Mark Friedenbach <mark@friedenbach.org>
           BtcDrak <btcdrak@gmail.com>
           Nicolas Dorier <nicolas.dorier@gmail.com>
           kinoshitajona <kinoshitajona@gmail.com>
  Status: Deployed
  Type: Specification
  Assigned: 2015-05-28

概要

本 BIP は、シーケンス番号フィールドに対して相対ロックタイム（RLT）というコンセンサスで強制される意味論を導入する。これにより、署名済みトランザクション入力を、対応するアウトポイントが承認されてから一定期間、無効な状態のままにしておくことができる。

動機

ビットコインのトランザクションには、各入力にシーケンス番号フィールドがある。当初のアイデアは、同じ入力をより高いシーケンス値で使い直すことで、メンプール内のトランザクションを置換できるようにする、というものだったようだ。これは正しく実装されなかったが、たとえ低いシーケンス番号のほうが採掘の収益性が高くても、マイナーは高いシーケンス番号を優先するという前提に立っている。しかし、利益動機のみで行動するマイナーは、この前提を完全に崩してしまう。本 BIP が述べる変更は、既存の機能を壊すことなく、シーケンス番号を新しい用途に転用する。また、将来の拡張や他の用途のための余地も残している。

トランザクションの nLockTime は、特定の日付まではトランザクションが採掘されないようにするために使われる。nSequence は、使用済み出力がブロック数または期間で表される一定の経過期間に達するまでトランザクションが採掘されないようにするために転用される。これは、他の用途に加えて、Hashed Timelock Contracts (HTLCs) (https://github.com/ElementsProject/lightning/raw/master/doc/miscellaneous/deployable-lightning.pdf)や BIP112 で用いられるような双方向ペイメントチャンネルを可能にする。

仕様

本仕様は、nVersion が 2 以上であるトランザクションについて、シーケンス番号の意味を定義する。本仕様の残りの部分はこの定義に依拠する。

median-time-past（MTP）への言及はすべて、BIP113 の定義に従う。

シーケンス番号のビット (1 << 31) が立っている場合、そのシーケンス番号にコンセンサス上の意味は適用されず、現在可能などのような状況の下でも任意のブロックに含めることができる。

シーケンス番号のビット (1 << 31) が立っていない場合、そのシーケンス番号は符号化された相対ロックタイムとして解釈される。

シーケンス番号の符号化は、以下のように解釈される。

ビット (1 << 22) は、相対ロックタイムが時間ベースかブロックベースかを決定する。このビットが立っていれば、相対ロックタイムは 512 秒粒度の単位で期間を表す。この期間は出力の直前ブロックの median-time-past から始まり、直前ブロックの MTP で終わる。このビットが立っていなければ、相対ロックタイムはブロック数を表す。

フラグ (1<<22) は、OP_CHECKSEQUENCEVERIFY（BIP 112）と共にビットコインスクリプトで 3 バイトの PUSHDATA として用いる 3 バイト符号付き整数における最上位ビットである。

本仕様はシーケンス番号のうち 16 ビットのみを相対ロックタイムとして解釈するため、相対ロックタイムを取り出すにはシーケンスフィールドに 0x0000ffff のマスクを適用しなければ（MUST）ならない。この 16 ビットの仕様により最大 1 年分の相対ロックタイムを表現でき、残りのビットは将来の拡張に充てられる。

相対ロックタイムのためのシーケンス番号ビットフィールド符号化

時間ベースの相対ロックタイムについては、ビットコインのブロックが 600 秒ごとに生成されることから、512 秒粒度が選ばれた。これにより、ブロックベースと時間ベースのどちらを使う場合でも、利用可能なビット数で同じだけの時間を符号化できる。シーケンス番号から秒数への変換は、512 = 2^9 を掛ける、つまり 9 ビット上位へシフトすることで行われる。

相対ロックタイムが時間ベースである場合、それは入力の経過時間に対する最小のブロック時刻制約として解釈される。値が 0 の相対時間ベースロックタイムは、どのブロックにも含められる入力を示す。より一般には、値が n の相対時間ベースロックタイムを持つ入力は、それが使用する出力の採掘日時から 512 × n 秒後、またはそれ以降に生成された任意のブロックに含めることができる。 出力の採掘日時は、その出力を採掘したブロックの直前ブロックの median-time-past に等しい。

ブロックの生成時刻は、その直前ブロックの median-time-past に等しい。

相対ロックタイムがブロックベースである場合、それは入力の経過時間に対する最小のブロック高制約として解釈される。値が 0 の相対ブロックベースロックタイムは、どのブロックにも含められる入力を示す。より一般には、値が n の相対ブロックロックタイムを持つ入力は、それが使用する出力の採掘日時から n ブロック後、またはそれ以降に含めることができる。

新しいルールは、コインベーストランザクションの入力の nSequence フィールドには適用されない。

実装

リファレンス実装は、以下のプルリクエストで提供されている。

https://github.com/bitcoin/bitcoin/pull/7184

enum {
    /* Interpret sequence numbers as relative lock-time constraints. */
    LOCKTIME_VERIFY_SEQUENCE = (1 << 0),
};

/* Setting nSequence to this value for every input in a transaction
 * disables nLockTime. */
static const uint32_t SEQUENCE_FINAL = 0xffffffff;

/* Below flags apply in the context of BIP 68*/
/* If this flag set, CTxIn::nSequence is NOT interpreted as a
 * 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;

/**
 * Calculates the block height and previous block's median time past at
 * which the transaction will be considered final in the context of BIP 68.
 * Also removes from the vector of input heights any entries which did not
 * correspond to sequence locked inputs as they do not affect the calculation.
 */
static std::pair<int, int64_t> CalculateSequenceLocks(const CTransaction &tx, int flags, std::vector<int>* prevHeights, const CBlockIndex& block)
{
    assert(prevHeights->size() == tx.vin.size());

    // 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.
    // The semantics of nLockTime are the last invalid height/time, so
    // use -1 to have the effect of any height or time being valid.
    int nMinHeight = -1;
    int64_t nMinTime = -1;

    // tx.nVersion is signed integer so requires cast to unsigned otherwise
    // we would be doing a signed comparison and half the range of nVersion
    // wouldn't support BIP 68.
    bool fEnforceBIP68 = static_cast<uint32_t>(tx.nVersion) >= 2
                      && flags & LOCKTIME_VERIFY_SEQUENCE;

    // Do not enforce sequence numbers as a relative lock time
    // unless we have been instructed to
    if (!fEnforceBIP68) {
        return std::make_pair(nMinHeight, nMinTime);
    }

    for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) {
        const CTxIn& txin = tx.vin[txinIndex];

        // 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) {
            // The height of this input is not relevant for sequence locks
            (*prevHeights)[txinIndex] = 0;
            continue;
        }

        int nCoinHeight = (*prevHeights)[txinIndex];

        if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) {
            int64_t nCoinTime = block.GetAncestor(std::max(nCoinHeight-1, 0))->GetMedianTimePast();
            // NOTE: Subtract 1 to maintain nLockTime semantics
            // BIP 68 relative lock times have the semantics of calculating
            // the first block or time at which the transaction would be
            // valid. When calculating the effective block time or height
            // for the entire transaction, we switch to using the
            // semantics of nLockTime which is the last invalid block
            // time or height.  Thus we subtract 1 from the calculated
            // time or height.

            // 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, nCoinTime + (int64_t)((txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) << CTxIn::SEQUENCE_LOCKTIME_GRANULARITY) - 1);
        } else {
            nMinHeight = std::max(nMinHeight, nCoinHeight + (int)(txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) - 1);
        }
    }

    return std::make_pair(nMinHeight, nMinTime);
}

static bool EvaluateSequenceLocks(const CBlockIndex& block, std::pair<int, int64_t> lockPair)
{
    assert(block.pprev);
    int64_t nBlockTime = block.pprev->GetMedianTimePast();
    if (lockPair.first >= block.nHeight || lockPair.second >= nBlockTime)
        return false;

    return true;
}

bool SequenceLocks(const CTransaction &tx, int flags, std::vector<int>* prevHeights, const CBlockIndex& block)
{
    return EvaluateSequenceLocks(block, CalculateSequenceLocks(tx, flags, prevHeights, block));
}

bool CheckSequenceLocks(const CTransaction &tx, int flags)
{
    AssertLockHeld(cs_main);
    AssertLockHeld(mempool.cs);

    CBlockIndex* tip = chainActive.Tip();
    CBlockIndex index;
    index.pprev = tip;
    // CheckSequenceLocks() uses chainActive.Height()+1 to evaluate
    // height based locks because when SequenceLocks() is called within
    // ConnectBlock(), 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 use one more than chainActive.Height()
    index.nHeight = tip->nHeight + 1;

    // pcoinsTip contains the UTXO set for chainActive.Tip()
    CCoinsViewMemPool viewMemPool(pcoinsTip, mempool);
    std::vector<int> prevheights;
    prevheights.resize(tx.vin.size());
    for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) {
        const CTxIn& txin = tx.vin[txinIndex];
        CCoins coins;
        if (!viewMemPool.GetCoins(txin.prevout.hash, coins)) {
            return error("%s: Missing input", __func__);
        }
        if (coins.nHeight == MEMPOOL_HEIGHT) {
            // Assume all mempool transactions are confirmed in the next block
            prevheights[txinIndex] = tip->nHeight + 1;
        } else {
            prevheights[txinIndex] = coins.nHeight;
        }
    }

    std::pair<int, int64_t> lockPair = CalculateSequenceLocks(tx, flags, &prevheights, index);
    return EvaluateSequenceLocks(index, lockPair);
}

謝辞

この変更の挙動について簡潔かつ明快な説明を提供し、それが本 BIP の文章の土台となったグレゴリー・マックスウェルに謝意を表する。

本 BIP は BtcDrak、ニコラ・ドリエ、kinoshitajona によって編集された。

展開

本 BIP は、ビット 0 を用いた「versionbits」BIP9 によって展開される。

ビットコインのメインネットでは、BIP9 の**開始時刻（starttime）は 2016 年 5 月 1 日 UTC 午前 0 時（Unix タイムスタンプ 1462060800）、BIP9 のタイムアウト（timeout）**は 2017 年 5 月 1 日 UTC 午前 0 時（Unix タイムスタンプ 1493596800）となる。

ビットコインのテストネットでは、BIP9 の**開始時刻（starttime）は 2016 年 3 月 1 日 UTC 午前 0 時（Unix タイムスタンプ 1456790400）、BIP9 のタイムアウト（timeout）**は 2017 年 5 月 1 日 UTC 午前 0 時（Unix タイムスタンプ 1493596800）となる。

本 BIP は、同じ展開機構を用いて BIP112・BIP113 と同時に展開されなければならない。

互換性

Bitcoin Core のリファレンスクライアントソフトウェアがシーケンス番号を用いる唯一の場面は、トランザクション内の nLockTime 制約のチェックを無効化する場合である。本 BIP はこのアプリケーションの意味論を保持する。

仕様の節から分かるとおり、本 BIP はビット (1 << 31) を立てることで他の用途に使えるよう多くのビットを未定義のままにしている。残る 31 ビットは本 BIP の下では意味を持たない。加えて、ビット (1 << 31) が立っていない場合、ビット (1 << 23) から (1 << 30) までも一切意味を持たない。

さらに、本 BIP は実際には 16 ビットのみを相対ロックタイムの符号化に用いるため、残り 6 ビット（(1 << 16) から (1 << 21) まで）は未使用である。これにより、将来ソフトフォークで粒度を上げたり、相対ロックタイムの最大値を増やしたりできる余地が残る。

相対ロックタイムからシーケンス番号を計算する最も効率的な方法は、ビットマスクとシフト演算を用いることである。

    // 0 <= nHeight <= 65,535 blocks (1.25 years)
    nSequence = nHeight;
    nHeight = nSequence & 0x0000ffff;

    // 0 <= nTime < 33,554,431 seconds (1.06 years)
    nSequence = (1 << 22) | (nTime >> 9);
    nTime = (nSequence & 0x0000ffff) << 9;

参考文献

ビットコインメーリングリストでの議論: https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg07864.html

BIP9: https://github.com/bitcoin/bips/blob/master/bip-0009.mediawiki

BIP112: https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki

BIP113: https://github.com/bitcoin/bips/blob/master/bip-0113.mediawiki

Hashed Timelock Contracts (HTLCs): https://github.com/ElementsProject/lightning/raw/master/doc/miscellaneous/deployable-lightning.pdf

関連エントリー

原典の外部ソース

https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki