Bitcoinの取引の可撓性（transaction malleability）について

概要

• 取引の署名を有効なままに保ちつつ取引の要約値（hash value）を変更することができる。
  • 元の取引がブロックに格納される前に、変更した取引を先にブロックに格納できるかもしれないということ（あるいは、ブロック鎖（blockchain）の再構築（reorg/reorganization）によって元の取引が無効となり、変更した取引が有効となるかもしれないということ）。
  • 出金口座（source account）を変更できる訳ではないので、二重使用（double spending）ではない。
  • 要約値を変更できるだけなら特に問題はないのでは？
    • そうでもない。
• 取引入力は使用する取引出力を当該取引出力が含まれている取引の要約値と取引の中で当該取引出力が含まれている位置（index）によって参照する。
  • 使用している取引出力を含む取引の要約値が変化すると取引入力の参照が無効となり、結果として取引自体が無効となる可能性がある。

署名の可撓性（signature malleability）

署名の表現形式による可撓性

• 一般的に、データの表現形式には様々なものがある。
  • 取引の署名の表現方法にも様々なものが考えられる。
• Bitcoinでは、取引の署名はASN.1（abstract syntax notation one）の標準符号化規則であるDER（distinguished encoding rules）で表現されることになっている。
  • しかしながら、Bitcoinが利用しているOpenSSLはこの表現形式を厳格には適用しない（多少署名の表現形式がこの表現形式と合致していなくても有効な表現形式の署名（署名自体が有効なものであるかはまた別の話である）として受け入れてしまう）し、Bitcoinの参照実装（reference implementation）自体も署名の表現形式がこの表現形式と厳密に合致しているか確認はしていなかった。
    • 署名の表現形式というBitcoinの合意形成に係る取引の検証規則の1つに関してOpenSSLという外部的な作製物に依存していた。
      • 一般的に、合意形成に係る部分が外部的な作製物に依存しているのは非常に良くない状態である。何故なら、合意形成規則自体が外部に依存しているということであるし、外部的な作製物の仕様変更や瑕疵の混入などによって合意形成規則自体が変化する可能性があるからである。
  • 余談だが、Bitcoinが楕円曲線DSA（ECDSA）のパラメータとして採用しているsecp256k1の場合、署名は32バイトの2つ組(r, s)で表されるので単純にそれぞれの要素をそのまま結合した64バイトの値r||sで表現すれば何の問題もないのだが（DER形式で表現すると無駄にバイトが必要になってしまう）。
• すなわち、ある署名に対して、Bitcoinで有効なものとして受け入れられ得る署名の表現方法は複数存在した。
• すなわち、署名の表現方法が異なる複数の取引の表現が存在し得た。
• その一方で、取引の要約値を計算する際には取引に含まれる全ての情報が計算対象となる。
  • 複数の取引の表現が存在すると、それぞれの取引の表現の要約値はほぼ確実にそれぞれ異なる。したがって、同一の取引であるにも拘らず、要約値が異なる可能性がある（ほぼ確実に異なる）。
• そのため、取引の署名の表現方法を変更することによって取引の署名を有効なままに保ちつつ取引の要約値を変更することができた。
  • 可撓性。
    • BIP66によって修正提案され、参照実装のバージョン0.8.0で中継採掘方針（relay/mining policy）として修正され、バージョン0.10.0で合意形成規則（consensus rule）として修正された。以上は過去の話。

用語

中継採掘方針と合意形成規則
参照実装がBitcoinネットワークの他のノードから受信した取引を別の他のノードに転送したり、採掘を行うブロックの中に含めたりするかどうかの基準が中継採掘方針である。中継採掘方針の基準を充足しない取引であっても、取引自体は有効である可能性はあるし、参照実装以外の実装が転送を行ったり、採掘を行ったりする可能性はある。他方で、取引自体が有効であるかどうかの基準が合意形成規則である。（適切な合意が形成されていれば）無効な取引が含まれているブロックは無効となるし、無効なブロックがブロック鎖に含められることはない。

署名自体の性質による可撓性

• ECDSAにおいて、有効な署名(r, s)は(r, -s (mod N))と変形しても有効である。
• そのため、取引の署名をこのように変形することによって取引の署名を有効なままに保ちつつ取引の要約値を変更することができる。
  • 可撓性。

BIP66

• DER形式ではない署名を無効とするように取引の検証規則を変更する。
  • 署名はDERの符号化規則を厳密に充足していなければならない（DERの規則を充足していない署名は、たとえ署名として認識できるものであっても無効である）。
• スクリプトのOP_CHECKSIG、OP_CHECKSIGVERIFY、OP_CHECKMULTISIG、OP_CHECKMULTISIGVERIFY命令に渡される全ての署名はDERの符号化規則を厳密に充足していなければならない。
• スクリプトの実行の際には、これらの4つの命令の何れかに署名が渡された後に、それぞれの命令の実行過程の一部として、署名がDERの符号化規則を厳密に充足しているかの確認を実行し、充足していない場合には直ちにスクリプト全体の実行を中断し、スクリプトをfalseに評価する。充足している場合にはそのまま命令の実行を続行する。
• 実際の実装はinterpreter.cppのIsValidSignatureEncoding関数。
  • ただし、この関数に渡されるバイト配列には末尾に署名としては余分な1バイトの情報（署名要約値フラグ（sighash flag）：取引のどの部分が署名対象となっているかを表す）が付加されている。

/**
 * A canonical signature exists of: <30> <total len> <02> <len R> <R> <02> <len S> <S> <hashtype>
 * Where R and S are not negative (their first byte has its highest bit not set), and not
 * excessively padded (do not start with a 0 byte, unless an otherwise negative number follows,
 * in which case a single 0 byte is necessary and even required).
 * 
 * See https://bitcointalk.org/index.php?topic=8392.msg127623#msg127623
 *
 * This function is consensus-critical since BIP66.
 */
bool static IsValidSignatureEncoding(const std::vector<unsigned char> &sig) {
    // Format: 0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] [sighash]
    // * total-length: 1-byte length descriptor of everything that follows,
    //   excluding the sighash byte.
    // * R-length: 1-byte length descriptor of the R value that follows.
    // * R: arbitrary-length big-endian encoded R value. It must use the shortest
    //   possible encoding for a positive integers (which means no null bytes at
    //   the start, except a single one when the next byte has its highest bit set).
    // * S-length: 1-byte length descriptor of the S value that follows.
    // * S: arbitrary-length big-endian encoded S value. The same rules apply.
    // * sighash: 1-byte value indicating what data is hashed (not part of the DER
    //   signature)

    // Minimum and maximum size constraints.
    if (sig.size() < 9) return false;
    if (sig.size() > 73) return false;

    // A signature is of type 0x30 (compound).
    if (sig[0] != 0x30) return false;

    // Make sure the length covers the entire signature.
    if (sig[1] != sig.size() - 3) return false;

    // Extract the length of the R element.
    unsigned int lenR = sig[3];

    // Make sure the length of the S element is still inside the signature.
    if (5 + lenR >= sig.size()) return false;

    // Extract the length of the S element.
    unsigned int lenS = sig[5 + lenR];

    // Verify that the length of the signature matches the sum of the length
    // of the elements.
    if ((size_t)(lenR + lenS + 7) != sig.size()) return false;
 
    // Check whether the R element is an integer.
    if (sig[2] != 0x02) return false;

    // Zero-length integers are not allowed for R.
    if (lenR == 0) return false;

    // Negative numbers are not allowed for R.
    if (sig[4] & 0x80) return false;

    // Null bytes at the start of R are not allowed, unless R would
    // otherwise be interpreted as a negative number.
    if (lenR > 1 && (sig[4] == 0x00) && !(sig[5] & 0x80)) return false;

    // Check whether the S element is an integer.
    if (sig[lenR + 4] != 0x02) return false;

    // Zero-length integers are not allowed for S.
    if (lenS == 0) return false;

    // Negative numbers are not allowed for S.
    if (sig[lenR + 6] & 0x80) return false;

    // Null bytes at the start of S are not allowed, unless S would otherwise be
    // interpreted as a negative number.
    if (lenS > 1 && (sig[lenR + 6] == 0x00) && !(sig[lenR + 7] & 0x80)) return false;

    return true;
}

署名スクリプトの可撓性（scriptsig malleability）

• 取引に署名する際には取引に含まれる全ての情報が署名対象となる訳ではない（取引に含まれる全ての情報から署名要約値（sighash）を計算する訳ではない）。
  • 少なくとも署名そのものを署名対象にすることは不可能である。
  • 実際は、署名要約値フラグによって取引のどの部分が署名対象となるかが決まる。
• そのため、取引に含まれる署名対象でない情報を変更しても、取引の署名は有効なままである。
• その一方で、取引の要約値を計算する際には取引に含まれる全ての情報が計算対象となる。
• そのため、取引に含まれる署名対象でない情報のみを変更することによって取引の署名を有効なままに保ちつつ取引の要約値を変更することができる。
  • 可撓性。

取引に含まれる署名対象でない情報

• 具体的には、署名スクリプト（scriptsig/signature script）の中身。
  • 対処が必要なもの
    • 署名スクリプトの署名や公開鍵そのものを、別の値から署名や公開鍵を生成するスクリプトに置き換えることができるかもしれない（たとえば、3という値は1+2から得られる）。
      • 署名スクリプトにおいてはスタックへのデータの積み込みしかできないようにする（四則演算など、幾つかの値から別の新しい値を生成することのできる命令は使用禁止とする）。
    • Bitcoinではスタックにデータを積み込む方法が、許容されるデータの大きさ別に複数存在するが、大は小を兼ねる（小さいデータをスタックに積み込む方法が複数存在する）。
      • ある大きさのデータは唯1つの方法でしかスタックに積み込めないようにする。
    • 整数として解釈されるデータの冒頭に余分な1バイト以上の0を付加することができる（整数として解釈されるデータの冒頭に1バイト以上の0を付加しても同一のデータとして扱われる）。
      • 余分な0は付加できないようにする。
    • スクリプトの冒頭に余分な1つ以上のデータを付加することができる（スクリプトの冒頭に1つ以上のデータを付加してもスタックに積み込まれるだけでスクリプトの実行結果には影響を及ぼさない）。
      • スクリプトの実行の最後にはスタックには唯1つだけデータが積み込まれていなければならないものとする。
    • スクリプトに、スタックに適当なデータを積み込んだ後スタックからそのデータを取り出す余分な部分を付加することで同一の結果を返す異なるスクリプトを作成することができる。たとえば、署名スクリプトの最後でスタックにデータを積み込み、公開鍵スクリプト（script/pubkey script）の最初でスタックからデータを取り出すことで同一の結果を返す異なるスクリプトを作成することができる。
      • OP_CHECKMULTISIGとOP_CHECKMULTISIGVERIFYによってスタックから取り出される不必要な余分なデータは空のバイト配列でなければならないものとする。
      • これ以外については対処は不必要（これ以外で取引を撓めることができるのは支払人のみであるため。支払人が随意的に取引を撓めることができるのは何も問題がない）。
  • 対処が不必要なもの（上記の理由と同じ）
    • 署名要約値フラグによっては取引の中で署名されない部分ができる。署名されていない部分は誰でも自由に変更できる。
    • 秘密鍵を知っている者は別の新しい有効な署名を生成できる。

BIP62

• BIP66を含む？
  • BIP66はBIP62から派生したもの。
• 署名(r, s)のsの値の制限
  • 有効な署名(r, s)に対するもう1つの有効な署名(r, -s (mod N))を（Bitcoinの取引の検証規則としては）無効化。
• DER符号化規則
  • BIP66
• データ積み込み命令の使用制限
  • 空のバイト配列を積み込む場合にはOP_0を使用しなければならない。
  • 長さ1のバイト配列で値が1～16のものを積み込む場合にはそれぞれOP_1～OP_16を使用しなければならない。
  • 長さ1のバイト配列で値が129のものを積み込む場合にはOP_1NEGATEを使用しなければならない。
  • 上記以外の長さ1のバイト配列か長さ2～75までの任意のバイト配列を積み込む場合には標準データ積み込み（normal data push）を使用しなければならない。
  • 長さ76～255までの任意のバイト配列を積み込む場合にはOP_PUSHDATA1を使用しなければならない。
  • 長さ256～520までの任意のバイト配列を積み込む場合にはOP_PUSHDATA2を使用しなければならない。
  • 長さ521以上の任意のバイト配列を積み込むことはできない。
    • OP_PUSHDATA4は使用できない。