読者です 読者をやめる 読者になる 読者になる

Develop with pleasure!

福岡でCloudとかBlockchainとか。

Segregated Witnessの仕様(BIP-141)

Bitcoinのスケーラビリティの問題への対応の1つとして、トランザクションの情報から署名(Witness)を分離(Segregate)する”Segregated Witness”という提案がされており、この導入によりトランザクション容量の削減が期待されている。
実際に”Segregated Witness”が有効になったテスト環境「SegNet」も2015年12月にデプロイされている。

BIPの中でSegregated Witness関連のBIPが以下の5つ。

Segregated Witnessの仕様がどのようなものか、BIP-141を見てみる。

摘要

このBIPでは、トランザクションのマークルツリーとは別にブロックにコミットされる"witness"という新しい構造について定義する。この構造にはトランザクションの有効性を確認するためのデータが含まれているが、トランザクションの作用を決めるのには必要無い。具体的にはスクリプトと署名がこの新しい構造に移される。

このBIPのソフトフォークによる互換性を保つため、witnessはコインベーストランザクションを経由してブロックの既存のマークルルートにネストされているツリーにコミットされる。将来のハードフォークでは独自のブランチにこのツリーを配置することができるようになる。

動機

トランザクションがどのように作用するかは全て、既存の出力の消費(UTXOの消費)と新しい出力(UTXO)の作成によって決められる。その他のトランザクションデータ(特に署名)はブロックチェーンの状態の検証のためのみに必要で、トランザクションの作用には一切関係が無い。

トランザクションのマークルツリーにコミットされたトランザクションの構造からこのデータを除去することにより、↓のような問題が解決される。

  1. 意図しないトランザクションのmalleability*1を不可能にする
    署名データがトランザクションハッシュの一部ではなくなったので、どのようにトランザクションが署名されたかはトランザクションの識別とは関係なくなる。トランザクションのmalleabilityの解決策として、これは正規の署名アプローチ(BIP-62)より優れている。
  2. 署名データの送信がオプションになる
    署名データはピアが(存在ではなく)トランザクションの検証を行う場合のみ必要。これによりSPV証明のサイズを削減し、同じ帯域幅で多くのトランザクション情報がダウンロード可能になり潜在的SPVクライアントのプライバシーを向上させる。
  3. トランザクションデータの一部を現在のプロトコルが知らない構造に移すことで、いくつかの制約がソフトフォークで無視されるようになる。
    例えば
    • ブロックサイズを計算する際に、witnessのサイズを無視できるようになり、効果的にある程度ブロックサイズを増やすことができる。(署名データが不要になった分、多くのトランザクションをブロックに入れられる)
    • 最大データプッシュサイズ(512バイト)やsigops制限といったハードコードされた定数は除去もしくは再評価される。
    • 新しいスクリプトシステムは、既存のスクリプトセマンティックからなんら制限を受けること無く導入できる。例えば、署名検証のための新しいトランザクションダイジェストアルゴリズムが新しくBIP-143で定義されている。

仕様

トランザクションID

新しいデータ構造witnessが定義され、各トランザクションは2つのIDも持つ。

既存のtxidの定義は変更されず、従来のシリアライズ形式のダブルSHA-256ハッシュのまま。

[nVersion][txins][txouts][nLockTime]

新たにwtxidが定義され、witnessデータを持つ新しいシリアライズ形式のダブルSHA-256ハッシュ。

[nVersion][marker][flag][txins][txouts][witness][nLockTime]

nVersiontxinstxoutsnLockTimeのフォーマットは従来と同じもの。

markerは必ず0x00

flagは必ず0以外の1バイトで、現在は0x01を使わないといけない。

witnessトランザクション内の全witnessデータをシリアライズしたもの。各txinはwitnessフィールドと関連付けられる。witnessフィールドはtxinのスタックアイテムの数を示すためvar_intから始まる。各アイテムはその長さを示すためvar_intで始まりスタックアイテムが続く。witnessデータはスクリプトではない。

後述するnon-witness programでは、txinは0x00で表される空のwitnessフィールドに関連付けられる必要がある。全てのtxinがnon-witness programの場合、トランザクションのwtxidはtxidと同じ値になる。

コミットメント構造

wtxidへのコミットメントを必要とする新しいブロックルールが追加された。コインベーストランザクションのwtxidは、0x0000....0000な値になる。

witnessのルートハッシュは、ブロックヘッダのhashMerkleRootと似ていて、マークルツリーのリーフのようにwtxidを全て使って計算される。

コミットメントはコインベーストランザクションのscriptPubKeyに記録される。0x6a24aa21a9edの最初の6バイトを持つ少なくとも38バイトのデータになる。

   1-byte - OP_RETURN (0x6a)
   1-byte - 以下の36バイトをプッシュ (0x24)
   4-byte - コミットメントヘッダ (0xaa21a9ed)
  32-byte - コミットメントハッシュ: Double-SHA256(witness root hash|witness reserved value)
  
  39th byte onwards: ノーコンセンサスを意味するオプションデータ

そしてコインベースの入力のwitnessは、`witness reserved value`である単一の32バイト配列で構成する必要がある。

パターンにマッチするscriptPubKeyが複数ある場合は、一番高い出力インデックスを持つものがコミットメントであると想定される。

Witness program

1バイトのプッシュ命令コードに続く2〜40バイトのデータプッシュからなるscriptPubKey(もしくはP2SHのredeemScript)は、新しい特別な意味を持つ。最初のプッシュ値は"version byte"を呼ばれ、それに続いてプッシュされるbyte vectorを"witness program"と呼ぶ。

witnessの検証ロジックが起動されるのは2つのケースがある。各ケースはscriptSigの形態と同様にwitnessのversion byteとprogramの位置を決める。

  1. version byteをプッシュし、 witness programをプッシュしたscriptPubKeyによるトリガー。scriptSigは空でないといけない。
  2. scriptPubKeyがP2SHスクリプトでscriptSigにBIP-16のredeemScriptがプッシュされた際の、 version byteをプッシュし、 witness programをプッシュしたscriptPubKeyによるトリガー。scriptSigは必ずBIP-16のredeemScriptのプッシュでなくてはならない。

version byteが0でwitness programが20バイトの場合

  • pay-to-witness-public-key-hash(P2WPKH)programと判断される。
  • witnessはそれぞれ520バイト以下の2つのアイテムから構成される。最初の1つが署名で、2つめが公開鍵。
  • 公開鍵のHASH160は20バイトのwitness programと一致する必要がある。
  • 通常のスクリプト評価の後に、公開鍵に対してCHECKSIGオペレーションで署名を検証する。検証の結果、スタック上で単一のTRUEになる必要がある。

version byteが0でwitness programが32バイトの場合

  • pay-to-witness-script-hash (P2WSH) programと判断される。
  • witnessはスクリプトに供給するため入力スタックで構成する必要がありシリアライズしたスクリプト"witnessScript"が続く。
  • 10,000バイト以下のwitnessScriptは最初のwitnessスタックからポップされ、witnessScriptのSHA-256は32バイトのwitness programと一致する。
  • witnessScriptはデシリアライズされ、残りのwitnessスタックの通常のスクリプト評価が終わった後に実行される。(スタックの各アイテムは512バイト以下)
  • スクリプトはfailになってはならず、結果はスタック上で単一のTRUEになる必要がある。

version byteが0でwitness programが20バイトでも32バイトでも無い場合、そのスクリプトはfailになる必要がある。

version byteが1〜16の場合、witness programやwitnessのさらなる解釈は発生せず、witnessに関するサイズ制限も無い。この1〜16は将来の拡張のために予約されている。

その他のコンセンサスの限界値

ブロックサイズ

ブロックは現在、最大サイズが1MBに制限されているが、この制限を以下のように変更する。

ベースサイズ✕3+トータルサイズを新しくblock weightとして定義する。*3

ベースサイズはwitness関連のデータを除外したオリジナルのトランザクションシリアライズしたバイト単位のブロックサイズ。

トータルサイズはBIP-144*4に定義されているシリアライズフォーマットでトランザクションシリアライズしたバイト単位のブロックサイズで、ベースデータとwitnessデータを含む。

新しいルールでは、block weightの合計が 4,000,000以下とされる。

Sigops

ブロックあたりのSigopsは現在20,000までに制限されているが、この制限を以下のように変更する。

現在のpubkey script, signature script, P2SH check script内のSigopsは前の値の4倍でカウントされる。Sigops制限も同様に4倍の80,000以下となる。

さらに、witness program内のopcodeは以前と同様にカウントされる。witness programではCHECKSIGは1 sigopとしてカウントされ、CHECKMULTISIGは引数に応じて1 〜 20 sigopsとしてカウントされる。このルールはネイティブ witness programとP2SH witness programの両方に適用される。

追加定義

以下の定義はコンセンサスの限界値には関係ないが、↑のコンセンサスの説明に出てくる内容を言語として定義したもの。

Transaction size calculations

Base transaction size * 3 + Total transaction sizeの値としてTransaction weightを定義。

Transaction weight / 4 した値をVirtual transaction sizeとして定義。(小数点以下は四捨五入)

Base transaction sizeはwitness関連のデータを除いてトランザクションシリアライズしたデータのバイト数。

Total transaction sizeは、witnessデータを含むBIP-144で定義されたフォーマットでトランザクションシリアライズしたデータのバイト数。

P2WPKH

次の例は、バージョン0のpay-to-witness-public-key-hash (P2WPKH)

    witness:      <signature> <pubkey>
    scriptSig:    (empty)
    scriptPubKey: 0 <20-byte-hash>
                  (0x0014{20-byte-hash})

scriptPubKeyの先頭の’0’は続くプッシュデータがバージョン0のwitness programであることを示す。witness programの長さから(20バイトのハッシュなので)P2WPKHタイプであることが分かる。
witnessは2つのアイテムから構成される必要があり、witnessの公開鍵のHASH160はwitness programと一致する必要がある。

署名は次のように検証される。

    <signature> <pubkey> CHECKSIG

従来のP2PKHの出力と比べると、P2WPKHはscriptPubKeyが3バイト少なく、署名と公開鍵をscriptSigからwitnessに移動する。

BIP-16のP2SHでネストされたP2WPKH

以下の例は同じP2WPKHだけど、BIP-16のP2SHでネストされている。

    witness:      <signature> <pubkey>
    scriptSig:    <0 <20-byte-key-hash>>
                  (0x160014{20-byte-key-hash})
    scriptPubKey: HASH160 <20-byte-script-hash> EQUAL
                  (0xA914{20-byte-script-hash}87)

scriptSig内のアイテムはHASH160でハッシュ化され、scriptPubKey内の20-byte-script-hashと比較され、以下のように解釈される

0 <20-byte-key-hash>

続いて前のサンプルと同様に公開鍵と署名の検証が行われる。

前の(P2WPKHの)例と比べると、scriptPubKeyが1バイト大きくscriptSigは23バイト大きくなる。ネストされたwitness programはあまり効率的ではないが、そのアドレスはBitcoin Core 0.6.0以降のとの完全な下位互換がある。

P2WSH

次の例は、1-of-2のマルチシグのバージョン0のpay-to-witness-script-hash (P2WSH)

    witness:      0 <signature1> <1 <pubkey1> <pubkey2> 2 CHECKMULTISIG>
    scriptSig:    (empty)
    scriptPubKey: 0 <32-byte-hash>
                  (0x0020{32-byte-hash})

scriptPubKeyの’0’は続くプッシュデータがバージョン0のwitness programであることを示す。witness programの長さから(32バイトのハッシュなので)P2WSHであることを示している。witnessの最後のアイテム("witnessScript")がポップされ、SHA256でハッシュされ、scriptPubKey内の32バイトのハッシュと比較され、デシリアライズされる。

    1 <pubkey1> <pubkey2> 2 CHECKMULTISIG

スクリプトがwitnessに続く残りのデータで実行される。

    0 <signature1> 1 <pubkey1> <pubkey2> 2 CHECKMULTISIG

P2WSHのスクリプトサイズは最大10,000バイトまで。

P2SHの23バイトとは対照的に、このscriptPubKeyは34バイトを占有する。サイズの増加は衝突攻撃に対する安全性の向上になる。2^80のハッシュ計算はもはや実現不可能ではない。(2015年末には、Bitcoinが作られて以降、2^84のハッシュがマイニングで計算されている)使用(消費)するスクリプトは、P2SHの出力のものと同じだが、witnessに移動される。

BIP-16のP2SHでネストされたP2WSH

次の例は、上の例と同じ1-of-2のマルチシグのP2WSHだけど、P2SHの出力でネストされている。

    witness:      0 <signature1> <1 <pubkey1> <pubkey2> 2 CHECKMULTISIG>
    scriptSig:    <0 <32-byte-hash>>
                  (0x0020{32-byte-hash})
    scriptPubKey: HASH160 <20-byte-hash> EQUAL
                  (0xA914{20-byte-hash}87)

scriptSig内のアイテムはHASH160でハッシュ化され、scriptPubKey内の20バイトのハッシュと比較され以下のように解釈される。

    0 <32-byte-hash>

前P2WSHの例と同様に、P2WSHのwitnessScriptが実行される。

前の例と比較すると、witnessは同じだが、scriptPubKeyは11バイト小さくなっている(その分、衝突攻撃への耐性は減少するけど)。しかしscriptSigで35バイト必要になる。

拡張可能なコミットメント構造

コインベーストランザクションの新しいコミットメントは`witness root hash`と`witness reserved value`のハッシュである。`witness reserved value`には現在コンセンサスの意味は無いが、将来のソフトフォークのための新しいコミットメント値を許可する。例えば将来コンセンサスクリティカルなコミットメントが必要となった際にコインベースにおけるコミットメントは以下のようになる。

  Double-SHA256(Witness root hash|Hash(new commitment|witness reserved value))

後方互換姓のため、Hash(new commitment|witness reserved value) の部分はコインベースのwitnessに記録され、`witness reserved value`は将来のソフトフォークで指定された異なる場所に記録されるだろう。任意の数の新しいコミットメントが同様の方法で追加できる。

マージマイニングのようにBitcoinにコンセンサスクリティカルでない任意のコミットメントは、Bitcoinのコンセンサスプロトコルをアップグレードする能力を保持するために`witness reserved value`を使ってはいけない。

コミットメントに続くオプションのデータ空間は将来のソフトフォークのメタデータのための余地を残しており、他の目的のために使ってはいけない。

トラストフリーな未確認トランザクション依存チェーン

Segregated witnessはmalleabilityの問題を根本的に解決し、トラストフリーな方法で未確認トランザクションを使ったチェーンの構築を可能にする。

アリスとボブの2人がいて、2-of-2のマルチシグ出力にある量のBitcoinを送付するのに合意したとする(このトランザクションを"funding transaction"とする)。"funding transaction"に署名することなく指定した時間まで承認されないようロックした別のトランザクションを作成し、2-of-2のマルチシグ出力を第三者のアカウントに送付する(このトランザクションを"spending transaction"とする)。アリスとボブは"spending transaction"に署名をしてその署名を交換する。受け取った署名を検査したら"funding transaction"に署名してブロックチェーンにコミットする。すると指定したロックタイムが過ぎたら"funding transaction"が確認され、元の契約に応じて資金が開放される。これより、両当事者の相互合意のみで、指定したロックタイムより短いロックタイムを持つ別の"spending transaction"によって、ロックタイム前の元の契約を取り消すことができる柔軟性を持つ。

このような仕組みは、malleabilityへの対応としてのBIP-62では不可能である(2人が最初に"funding transaction"への署名をしないと"spending transaction"が作成できないので)。アリスがボブより前に"funding transaction"の署名を明らかにしても、ボブは"spending transaction"へ署名しないことで無期限に資金をロックすることができる。

未確認トランザクションを使ったチェーンは、duplex micropayment channelやLightning Networkのような、より洗練された支払いネットワークの構成要素で、Bitcoinシステムのスケーラビリティ及び効率を大幅に改善する可能性を持っている。

将来の拡張

SPVノードのためのコンパクトな不正の証明

Bitcoinは今現在2つのセキュリティモデルを持っている。ユーザは、システム内の全てのルールで全てのブロックを検証するフルノードを使うか、一部のトランザクションの発行証明としてブロックヘッダを検証するSPVクライアントを使うかのどちらかである。Bitcoinのホワイトペーパーでは、SPVノードが無効なブロックを検出した際にフルノードからのアラートを受け入れ、検証のために対象のブロックとトランザクションをダウンロードするよう促している。しかし、このアプローチはDoS攻撃になる可能性もあり、アラームは不正の証拠がまだ無い場合はコンパクトでなくてはならない。

現在のBitcoinプロトコルでは、以下の少数を除いて、ほぼ全てのルールについてコンパクトな不正の証明を生成することができる。

  1. コインベーストランザクションの出力内にあまりにも多くのBitcoinを導入したマイナーの証明は、ブロック全体と全てのトランザクションの入力無しにはできない。
  2. 任意のブロック特定の制約違反(サイズやsigopの制限など)の証明はブロック全体無しにはできない。
  3. 存在しない入力の証明は、ブロックチェーン内の全てのトランザクションID無しにはできない。

余分なwitnessデータをコミットでき、それによりSPVノードが素早く検証できるよう無効ブロックの短い証明を与える。

  1. トランザクション手数料用のツリーの合計をコミットでき、それによりマイナーが過大な手数料をコインベースに追加しない短い証明の構築を可能にする。(ブロックサイズやsigopsカウント制限と同様に)
  2. トランザクションの入力に使用した出力のバックリンクを提供できる。これらのバックリンクは、ブロックハッシュとシンクライアントで出力の存在を簡単に検索・検証できるオフセットで構成される。

これらのコミットメントは、ソフトフォークを介して拡張可能なコミットメント構造に含めることができ、そのような新しいルールを認識できないノードに対しては透過的に振る舞う。

新しいスクリプトシステム

witness programの前にversion byteがプッシュされ、未知のバージョンのプログラムは常にanyone-can-spendスクリプトとして考えられるので、ソフトフォークした新しいスクリプトシステムを導入することができる。構造体としてのwitnessは、既存のスクリプトのセマンティクスや制約の制限を受けない(520バイトのプッシュ制限など)ため、任意の大きなスクリプトや署名を可能にする。

新しいスクリプトシステムの例としては、マルチシグトランザクションのサイズを劇的に削減するシュノール署名や、量子コンピュータが実現しても安全性を保てるランポート署名や、極端な複雑条件付きスクリプトの非常にコンパクトなwitnessを実現するMerklized抽象構文木などが挙げられる。

witness programの32バイトの制限は、将来強いハッシュ関数が必要とされた際に、ソフトフォークにより簡単に拡張できる。version byteもソフトフォークで拡張可能。

入力ごとのロックタイムと相対的なロックタイム

現在のところ、トランザクション内にはnLockTimeフィールドは1つしかなく、全ての入力が同じ値を共有する必要がある。BIP-68ではnSequenceフィールドを使って入力ごとの相対的なロックタイムの設定が可能だが、ロックタイム期間の制限はある。

ソフトフォークにより、入力ごとにロックタイムと相対的なロックタイムをサポートするため別々のwitness構造を導入することができ、新しいスクリプトシステムで署名と新しいデータの操作が可能になる(BIP-65BIP-112のような)。

後方互換

ソフトフォークのように、古いソフトウェアは変更することなく動作し続ける。アップグレードされていないノードは、witness data は参照も検証もされず、witness programはanyone-can-spend スクリプトとして判定されるだろう。ウォレットはそれらanyone-can-spendの取り扱いには充分慎重になる必要がある。アップグレードされていないノードについては、新しい機能を活用するためアップグレードすることを強く推奨する。

アップグレードされていないウォレットでできること
  • アップグレードされているウォレットとされていないウォレットからのBitcoinの受け取り
  • 従来のP2PKHアドレスを使用したアップグレードされているウォレット、されていないウォレットへのBitcoinの送付(segregated witnessの恩恵は無し)
  • アップグレードされたウォレットへのP2SHアドレスによるBitcoinの送付
  • アップグレードされたウォレットへのBIP70の支払プロトコルを介したネイティブwitness programを使ったBitcoinの送付
アップグレードされていないウォレットでできないこと

デプロイメント

このBIPの内容は"segwit"という名称でBIP-9のversion bitsを利用してデプロイされる。

mainnetについてはまだ未定。

testnetについては、BIP-9のstarttimeが2016/05/01からで、タイムアウトが1年後。(2016/09/07時点でactivateになってる)

所感

  • スケーラビリティの改善以外にも、署名データがトランザクションハッシュの一部でなくなることで、トランザクションのmalleabilityへの対応となる。
  • Segwitのトランザクションはtxid以外にwtxidを持つ。
  • 署名がトランザクションから分離される副次的な効果として、Lightning Networkみたいに未確認のトランザクションをインプットとしたトランザクションの作成ができるのはおもしろい。むしろサイズ削減よりこっちの方が機能としては魅力的。
  • 結構ソフトフォークによる拡張ポイントが多い。
  • 入力毎にロックタイムが設定できるようになると、ロックタイムを過ぎてない入力と過ぎた入力と、それを参照するトランザクションの出力はどういう振る舞いになるんだろう?

*1:トランザクションの入力と出力は変更せずにトランザクションハッシュを変更しトランザクションの二重払いを行う攻撃

*2:unconfrimedなUXTOを入力に使ってコインをやりとりする

*3:1MBとのベースデータと3MBのwitnessデータのような2つの制約ではなく、こうした1つの複合制約にしたのは、2つの制約を使用するとマイニングと手数料の算定が不可能と思われるため。2つの制約を与えられるとマイナーはその制約下で報酬を最大化するために複雑な非線形を解く必要があり、ウォレットにとってもいくら払えばマイナーに自分のトランザクションをブロックに入れてもらえるか判断できなくなる。また別の問題も引き起こす。一連のトランザクションデータがベースデータのリミット1MBに達すると、3MB分までwitnessへデータを最低手数料で追加することができる。余分なwitnessスペースのコストは限りなく0になってしまう。

*4:segwitの構造コミットする際のブロックとトランザクションシリアライズフォーマットを定義したBIP