Develop with pleasure!

福岡でCloudとかBlockchainとか。

MASTで選択されたスクリプトを実行するtail-callの仕組みを定義したBIP-117

BIP Bitcoin MAST

MASTの機能を実現するのに新しくBIP-98とBIP-116とBIP-117の3種類のBIPが提案されている。

BIP-116はスクリプトの条件分岐をフラットにしてMASTのマークツリーを構成した結果、スクリプトで実際に使用する条件（サブスクリプト）がそのマークルツリー内に含まれていることを検証するための新しいopcodeMERKLEBRANCHVERIFYを定義した↓

techmedia-think.hatenablog.com

BIP-98はそのMASTのマークツリーを構成する際に使用する効率的なハッシュ関数やマークルパスを指定する際のエンコード方法を新たに定義した↓

techmedia-think.hatenablog.com

最後のBIP-117は、MERKLEBRANCHVERIFYでマークルツリーへの包含が確認できたあと、実際に使用する条件（サブスクリプト）をスクリプトとして実行するためのプロトコルを定義している↓

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

概要

BIP16 (Pay to Script Hash)とBIP141 (Segregated Witness)は、そこにロックされたコインを使用する際にwitnessのデータの一部としてそのスクリプトの内容を公開するようになっている。どちらの場合も１つのスクリプトだけがコミットされる。これはこのBIPの目標を達成するのには便利だが、コインを使用する際に必要かどうかに関係なく全ての内容を１つのスクリプト内に記載する必要がある。

このBIPはBIP116(MERKLEBRANCHVERIFY)と組み合わせて、実質無制限の条件を持つスクリプトにコミットしつつ、コインを使用する際にその条件のうちコインのアンロックに使用する条件のみを公表するようにする。これにより複雑な条件分岐を持つスクリプトを分岐のないフラットな実行パスに分解し、可能なパスのセット全体にコミットし、使用するパスのみを明らかにする一般化されたMASTの形式を実現する。

動機

BIP16 (Pay to Script Hash)とBIP141 (Segregated Witness)は、ポリシーの公開を使用時まで遅延させることができる。しかしこれらのアプローチは、特定のトランザクションのアウトプットに対してコミットできるのは１つのポリシーのみという点で制限されている。複数のポリシーにコミットすることはできず、使用時にどちらを公開するか選択することはできない。

BIP116(MERKLEBRANCHVERIFY)は複数のデータ要素にコミットし、使用時に必要な要素のみを明らかにすることを可能にする。MERKLEBRANCHVERIFY opcodeは予め選択されたデータのセットに対してのみコミットを提供でき、コード自体を実行することはできない。

このBIPでは、redeem scriptがスタックにポリシースクリプトを配置するために必要なあらゆるタイプの計算を実行できるようにすることで、これら従来の方法のアプローチを一般化する。ポリシースクリプトは、BIP16やBIP141でredeem scriptがwitnessスタックの上から実行されるのと同じように、データスタックの先頭から実行される。特に、scriptPubkeyやredeem scriptでMERKLEBRANCHVERIFYを使うとコイン使用の検証に必要な条件のみを含むポリシースクリプトを選択することができる。これは、事前計算の段階でシンタックスツリーを実行可能なパスに分割し、それらを列挙してポリシースクリプトのマークルツリーハッシュにする一般化されたMASTの形式だ。ポリシースクリプトを実行する前に、コインの使用時に提供されたポリシースクリプトがこのツリーの一部であることは証明される。

仕様

スクリプトの実行が終了した際に

  • 実行した状態がクリーンでない場合、つまり
    1. メインスタック上に複数の要素がある、もしくは
    2. メインスタックに１つの要素があり、アルトスタックが空でない
  • メインスタックの一番上の要素がboolで解釈した際にtrueと評価される、かつ
  • メインスタックの一番上の要素が1バイトでないか、0x51(OP_1)〜0x60(OP_16)の範囲外の場合

メインスタックの一番上の要素がポップされ、シリアライズされたスクリプトとして解釈され実行される。その際メインスタックとアルトスタックに残っている残りの要素はインプットとしてそのまま残る。

最後の１つを残して上記の条件を満たした場合以下のようになる。

  • 一番上の要素は、0x51（OP_1つまりN=2）から0x60（OP_16つまりN=17）の範囲のシングルバイトである。

そして、

  • メインスタック上の次のN-1の要素（メインスタック上の要素が全て使われていた場合はアルトスタック上で継続）は520バイトのプッシュで、
  • 続くメインスタック上のN番目の要素（もしくはアルトスタック上）は1〜520バイトのデータ

となる。続いてメインスタック上の一番上の要素がドロップされ、N=2(0x51)〜N=17(0x60)の追加要素がメインスタックからポップされ（メインスタックの要素を全て使い果たした場合はアルトスタックで継続）、逆順でシリアライズされたスクリプトを形成し、両方のスタックの要素をそのインプットとしてスクリプトを実行する。

サブスクリプト内のCHECKSIGやCHECKMULTISIGはグローバルなMAX_BLOCK_SIGOPS_COST制限にカウントされず、サブスクリプトで実行される非プッシュopcodeの数はMAX_OPS_PER_SCRIPTで制限されない。上記の例外を除いて、実行状態はサブスクリプトに引き継がれ、サブスクリプトの終了(terminate)はスクリプト全体の実行の終了(terminate)になる。これはtail-callセマンティクスによる実行と呼ばれる。

このようなサブスクリプトのtail-callはスクリプトの実行コンテキスト毎に１つだけ許可され、かつsegwitのredeem script内からのみ許可される。その他のwitnessスタックの評価やscriptPubkeyやscriptSig、P2SHのredeem scriptの実行の際にtail-callセマンティクスが実行されることはない。

論拠

現状、スクリプトを実行した結果スタック上にシリアライズしたスクリプトが残っているとデータ的にはtrueであると評価されスクリプトの検証結果はtrueになる。そのためこのBIPはこのBitcoinのコンセンサスルールを変更するソフトフォークの提案である。サブスクリプトに実行終了の機会を与えるのは、検証ルールをさらに制約することに過ぎない。唯一falseと評価されるスクリプトは空のスクリプト、もしくはスタックに空/ゼロをプッシュするだけのスクリプトだ。これらのスクリプトにはいずれも現実的な効用はないので、ソフトフォークの互換性のためそれらを除外しても欠点はない。

より一般的なEVAL opcodeではなくtail-callの評価に限定することで、実装を大幅に簡略化する。tail-callセマンティクスとは実行結果が呼び出し元のスクリプトのコンテキストに戻らないこと意味し、このため状態を保存したり後で復元する必要もない。実装は本当にシンプルで、スタックからサブスクリプトを引っ張り出して、いくつかの状態変数をリセットし、スクリプトインタプリタの先頭にジャンプバックするだけである。

tail-callの再帰を1レイヤーのみ許可するという制限はあるが、マルチレイヤーにおけるtail-callの再帰をサポートする技術的課題は重要だ。スクリプトデータの使用状況を追跡するためには、トランザクションデータとwitnessサイズの2つファクターについて新しいメトリックを開発する必要がある。この新しいweightは、トランザクションを使って中継され、手数料計算のベースとして使用され、トランザクションの実行でインラインで検証され、違反するトランザクションを伝搬するDoS禁止ピアの方針を決定する。

ただこれらの問題を克服する場合、単一の再帰の制約を解除すること自体もソフトフォークが必要になる。tail-callの再帰を１レイヤーのみ許可することで、マルチポリシーコミットメント/一般化したMASTの主な利点を享受できるが、いつか必要な変更がリソースアカウンティングとP2Pのトランザクションの配布に行われた場合の将来の一般化されたtail-call再帰への道は残る。

グローバルSIGOP制限やスクリプト単位のopcode制限はポリシースクリプトには適用されない。これはポリシースクリプトを動的に選択すると一般的に静的解析ツールでこれらの制限を検証することができなくなり、libsecp256k1やBitcoin Coreのパフォーマンスが向上したためこれらの制限は必要なくなった（また検証は一度だけ行えばいい）。検証コストはブロックサイズの制限内でエンコード可能な署名操作の数によって依然として制限されており、インプット単位のスクリプトサイズもまだ10,000バイト以下と制限されている。

これらのグローバルやスクリプト単位の制限を外すため、scriptPubKeyで直接tail-callの評価を実行することは許可されておらず、そういったスクリプトはUTXOからフェッチされ検証されるブロックのブロックサイズの制限にはカウントされない。同様にP2SHのredeem scriptのtail-callも、segwitで修正された二次的な脆弱性のためサポートされない。

汎用的なMAST

tail-callをBIP116 (MERKLEBRANCHVERIFY)と組み合わせると汎用的なMASTの機能を利用できるようになる。スクリプトの作成者はまず使用時に検証する完全なコントラクトの記述から始める。記述したコントラクトの条件分岐を条件の検証とブランチに置き換え、スクリプトを実行する際に通る可能性があるパスを列挙する。実行可能性のあるパスのリストはマークルツリーに入れられ、フラット化されたポリシースクリプトがこのツリーのリーフになる。最後に、資金を送金するredeem scriptは以下のようになる。

redeemScript: <root> 2 MERKLEBRANCHVERIFY 2DROP DROP
witness: <argN> ... <arg1> <policyScript> <proof>

policyScriptがフラット化されたポリシースクリプトで、proofはシリアライズされたマークルブランチとパスでpolicyScriptがマークルツリーrootを構成するのに使われセットの一部であることを証明する。arg1〜argNはpolicyScriptが必要とする引数。2は１つのリーフ（1 << 1）が続き、リーフの値が事前にハッシュされていないことを示す。2DROP DROPはMERKLEBRANCHVERIFYの検証を終えた際にその検証に必要だった引数をスタックから削除するのに使われる。

上の例は分かりやすくするために設計されているが、実際はsegwit v0スクリプト実行の際のCLEANSTACKルールに違反している。CLEANSTACKルールが新しいsegwitのアウトプットバージョンで削除もしくは変更されない限り、以下のようにアルトスタックを使用する形にスクリプトを変更する必要がある。

redeemScript: [TOALTSTACK]*N <root> 2 MERKLEBRANCHVERIFY 2DROP DROP
witness: <policyScript> <proof> <arg1> ... <argN>

[TOALTSTACK]*NはTOALTSTACKopcodeがN回繰り返されたことを意味する。これはarg1〜argNをアルトスタックに逆順で移動させ、policyScriptが実行される時にarg1がアルトスタックの先頭に配置する。当然policyScriptもアルトスタックから引数をフェッチするよう変更する必要がある。

ポリシースクリプトのセットの中にさまざまなパラメータ数をとるスクリプトが含まれている場合、合理的な範囲内でサポートすることができる。以下のredeem scriptではポリシースクリプトとマークルプルーフに加え1〜3個のwitness引数を指定できる。

 witness: <policyScript> <proof> <arg1> ... <argN> // N は1〜3
redeemScript: DEPTH TOALTSTACK                    // witness要素の数をアウトスタックに保存
              TOALTSTACK                          // 最初の必須要素をアルトスタックに保存
              DEPTH 2 SUB                         // policyScriptとプルーフを無視して、オプションの数を計算
              DUP IF SWAP TOALTSTACK 1SUB ENDIF   // もし引数の要素が現れたら、オプションの2つ目の要素としてアウトスタックに保存
              IF TOALTSTACK ENDIF                 // もし引数の要素が現れたら、オプションの3つ目の要素としてアウトスタックに保存
              <root> 2 MERKLEBRANCHVERIFY 2DROP DROP
alt-stack: <N+2> <argN> ... <arg1>

witness要素の数がアルトスタックにプッシュされるため、アルトスタックが通常のスクリプトにアクセスできない場合でも、ポリシースクリプトは渡された引数の数を検証できる。上記のredeem scriptを使用する以下のポリシースクリプトは、アルトスタック上の2つのwitness 要素のみを受け入れ、witnessのmalleabilityを防ぐ。

policyScript: FROMALTSTACK ...check arg1... FROMALTSTACK ...check&consume arg2/arg1&2... FROMALTSTACK 4 EQUAL

数値4にはpolicyScriptとproofが含まれていると予想される。

上記の例のような冗長性は、全てのポリシーサブスクリプトのパラメータとして同じ数のwitness要素を使用し、条件及びスタックサイズ数を削除することで回避することができる。将来のスクリプトのバージョンのアップグレードでは、witness/redeem scriptからメインスタックのポリシースクリプトに引数を直接渡せるようにCLEANSTACKルールの緩和も検討する必要がある。

BIP114との比較

BIP114 (Merkelized Abstract Syntax Tree)はBIP141のスクリプトのバージョニングを使って導入するMASTスキームについて定義している。BIP114と異なり、BIP116 (MERKLEBRANCHVERIFY)と共にこのBIPで提案するスキームは、MAST内のポリシースクリプトのメンバーシップを検証するのにスクリプト自体を使ってMAST構造を暗黙的に有効にする。これはMAST自体がプログラマブルであるため、コンセンサスコードの変更が大幅に少なくなるだけでなく、コンセンサスコードの変更を全く必要としない将来のスクリプトベースのイノベーションを可能にする可能性がある。

さらに、NOP拡張スペースを使用する全てのスクリプトにMERKLEBRANCHVERIFYとtail-callセマンティクスを追加することで、BIP141のスクリプトバージョニングは不要となる。これによりこの機能をデプロイする際の、アドレスフォーマットをどうするかいった問題、スクリプトのバージョンアップの展開方法、別の機能がv1アップグレードを使用する際の合意、といったハードルは無くなる。

実装

コンセンサスコードの変更とテストを含むこのBIPの実装は以下のリポジトリで確認できる。

https://github.com/maaku/bitcoin/tree/tail-call-semantics

デプロイ

このBIPはBIP-8を使ってデプロイされ、tailcallという名前でbit 3を使用する。

Bitcoinのmainnetでは、BIP8のstartheightがM（未決定）で、timeoutはM+50,400ブロック後。

Bitcoinのtestnetでは、BIP8のstartheightがT（未決定）で、timeoutはT+50,400ブロック後。

CLEANSTACKは、この機能を使用するトランザクションが既にネットワークルールで非標準とみなされているため、例えばBIP68の時よりデプロイは容易になる。

互換性

v0 segwitのルールではスタックに何らかの要素を残すことは禁止されているので、互換性の理由からv0のパラメータはアルトスタックに渡す必要がある。