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

BIP 342 — Taprootスクリプトの​検証

BIP（ビットコイン改善提案） GitHub · 対象日 · 登録日 · 更新日
人物： ピーター・ウィーユ ,  ジョナス・ニック ,  アンソニー・タウンズ
Taprootシュノアソフトフォークスマートコントラクト暗号学スクリプト言語
ピーター・ウィーユ（Pieter Wuille） 2020年1月19日 
BIP: 342
  Layer: Consensus (soft fork)
  Title: Validation of Taproot Scripts
  Authors: Pieter Wuille <pieter.wuille@gmail.com>
           Jonas Nick <jonasd.nick@gmail.com>
           Anthony Towns <aj@erisian.com.au>
  Status: Deployed
  Type: Specification
  Assigned: 2020-01-19
  License: BSD-3-Clause
  Discussion: 2019-05-06: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016914.html [bitcoin-dev] Taproot proposal
  Requires: 340, 341

序論

概要

本文書は、BIP341の下での初期スクリプティングシステムの意味論を規定する。

著作権

本文書は3条項BSDライセンスの下に提供される。

動機

BIP341はスクリプト構造のみの改善を提案するが、その目標のいくつかは、スクリプティング言語自体の一部オペコードの意味論と両立しない。 これらを別個の任意の改善として扱うことも可能ではあるが、BIP341自体と同時に対処しない限り、その効果は保証されない。

具体的には、スクリプトシステムを通じた使用でも、シュノア署名・バッチ検証・署名ハッシュの改善を使えるようにすることが目標である。

設計

これらの目標を達成するため、署名オペコードOP_CHECKSIGとOP_CHECKSIGVERIFYは、BIP340で規定されるシュノア署名を検証するよう変更され、BIP341の共通メッセージ計算に基づく署名メッセージアルゴリズムを用いるよう変更される。tapscriptの署名メッセージはまたOP_CODESEPARATORの処理を単純化し、より効率的にする。

非効率なOP_CHECKMULTISIGとOP_CHECKMULTISIGVERIFYオペコードは無効化される。 代わりに、同じマルチシグ方針をバッチ検証可能な形で作成できるよう、新オペコードOP_CHECKSIGADDが導入される。Tapscriptは、署名オペコードに新しい単純な制限を設け、トランザクション重みとの込み入った相互作用を解消する。 さらに、MINIMALIFを要求することで潜在的な展性ベクトルが排除される。

Tapscriptは、未知の鍵型を定義することでソフトフォークによりアップグレード可能である。たとえば新しいhash_typesや署名アルゴリズムを追加できる。 加えて、新しいtapscriptのOP_SUCCESSオペコードにより、OP_NOPを介するよりも明快に新オペコードを導入できる。

仕様

以下のルールは、以下の条件がすべて真であるトランザクションインプットを検証する場合にのみ適用される。

  • 当該トランザクションインプットが セグリゲーテッドウィットネス使用であること (すなわち、scriptPubKeyがBIP141で定義されるウィットネスプログラムを含む)。
  • BIP341で定義されるtaproot使用であること (すなわち、ウィットネスバージョンが1であり、ウィットネスプログラムが32バイトであり、P2SHラップされていない)。
  • BIP341で定義される スクリプトパス使用であること (すなわち、任意のannexをウィットネススタックから取り除いた後、2個以上のスタック要素が残る)。
  • 葉バージョンが0xc0であること (すなわち、任意のannexを取り除いた後の末尾ウィットネス要素の先頭バイトが0xc0または0xc1である)。これによりtapscript使用として識別される。

そのようなインプットの検証は、以下の手順を指定された順序で実行することと等価でなければならない。

  1. インプットがBIP141またはBIP341により無効である場合は失敗。
  2. BIP341で定義されるスクリプト (すなわち、任意のannexを取り除いた後の末尾から2番目のウィットネススタック要素) をtapscriptと呼び、これをオペコードに1つずつ復号する。
    1. 番号80、98、126-129、131-134、137-138、141-142、149-153、187-254のいずれかのオペコードに遭遇した場合、検証は成功する (以下のルールはいずれも適用されない)。これは、それ以降のバイトがtapscriptとして復号に失敗する場合でも真である。これらのオペコードはOP_SUCCESS80、…、OP_SUCCESS254と改称され、まとめてOP_SUCCESSxと呼ばれるOP_SUCCESSx OP_SUCCESSxはスクリプトシステムをアップグレードするための機構である。ソフトフォークによりその意味が定義される前にOP_SUCCESSxを使用することは安全ではなく、資金の喪失につながる。スクリプト中にOP_SUCCESSxが含まれることで、そのスクリプトは無条件に通過する。これはあらゆるスクリプト実行ルールに先立って適用され、たとえば入力スタックが1000要素を超えるスクリプト中のOP_SUCCESSx、署名オペコードが多すぎる後のOP_SUCCESSx、OP_ENDIFを欠く条件分岐を持つスクリプトなど、様々な特殊なケースをそれぞれ規定する難しさを、これで避けている。OP_SUCCESSxがスクリプト中のどこかに存在するだけで、こうしたすべてのケースで通過が保証される。OP_SUCCESSxは、初期のビットコインバージョン (v0.1からv0.3.5まで) におけるOP_RETURNに類似する。オリジナルのOP_RETURNはスクリプト実行を即座に終了させ、終了時点のスタック先頭要素に基づいて通過または失敗を返した。これはオリジナルのビットコインプロトコルにおける主要な設計上の欠陥の一つであった。scriptSigにOP_RETURNを置くだけで、第三者が無条件に資金を盗めたためである。本提案ではこれは懸念にならない。第三者が検証プロセスにOP_SUCCESSxを注入することは不可能だからである。OP_SUCCESSxはスクリプトの一部であり (したがってtaprootアウトプットによりコミットされ)、コイン所有者の同意を含意する。OP_SUCCESSxは様々なアップグレードの可能性に用いることができる。
      • OP_SUCCESSxは、ソフトフォークにより機能的なオペコードに転換できる。スタックへの読み取り専用アクセスのみを持つOP_NOPx由来のオペコードとは異なり、OP_SUCCESSxはスタックへの書き込みも行いうる。OP_SUCCESSxを含むスクリプトへのいかなるルール変更も、妥当なスクリプトを無効なスクリプトに変えることしかできず、これは常にソフトフォークで達成可能である。
      • OP_SUCCESSxは初期スタックとプッシュオペコードのサイズ検査に先立つため、520バイトを超えるスタック要素を要求するOP_SUCCESSx由来のオペコードは、ソフトフォークによりこの上限を引き上げられる。
      • OP_SUCCESSxは既存のオペコードの挙動を再定義し、新オペコードと連携させることもできる。たとえばOP_SUCCESSx由来のオペコードが64ビット整数を扱う場合、同じスクリプト内の既存の算術オペコードにも同様の扱いを許してよい。
      • OP_SUCCESSxは解析不能なスクリプトすら通過させるため、複数バイトのオペコードや、特定のOP_SUCCESSxオペコードを前置した完全に新しいスクリプト言語すら導入するために用いることができる。。
    2. プッシュオペコードがtapscriptの末尾を越えて拡張するために復号に失敗する場合は失敗。
  3. BIP341で定義される 初期スタック (すなわち、任意のannexとその後の末尾2個のスタック要素を取り除いたウィットネススタック) が何らかのリソース制限 (スタックサイズ、およびスタック内要素のサイズ。下記「リソース制限」を参照) に違反する場合は失敗。この検査はOP_SUCCESSxにより回避できることに注意。
  4. tapscriptは、次節のルールに従い、初期スタックを入力として実行される。
    1. 何らかの理由で実行が失敗した場合は失敗。
    2. 実行の結果、スタックに残る要素が、CastToBool() で真と評価される要素ちょうど1個でなければ失敗。
  5. 失敗に遭遇せずこの手順に到達した場合、検証は成功する。

スクリプト実行

tapscriptの実行ルールは、BIP65とBIP112で定義されるOP_CHECKLOCKTIMEVERIFYとOP_CHECKSEQUENCEVERIFYオペコードを含め、BIP141によるP2WSHのそれに基づくが、以下の変更を伴う。

  • 無効化されたスクリプトオペコード以下のスクリプトオペコードはtapscriptにおいて無効化される: OP_CHECKMULTISIGとOP_CHECKMULTISIGVERIFYなぜOP_CHECKMULTISIGとOP_CHECKMULTISIGVERIFYはOP_SUCCESSxにされず無効化されるのか？ これは、誤ってTapscript内でOP_CHECKMULTISIGを使い続けてしまう人々が問題に即座に気付けるようにするための予防措置である。またスクリプト逆アセンブラが文脈依存になる必要をなくす効果もある。。無効化されたオペコードは、実行時に即座に失敗しスクリプトを終了させる点でOP_RETURNと同様に振る舞い、スクリプトの未実行分岐内に見つかった場合は無視される。
  • コンセンサスにより強制されるMINIMALIF MINIMALIFルールは、P2WSHでは標準性ルールにすぎないが、tapscriptではコンセンサスにより強制される。これは、OP_IFとOP_NOTIFオペコードへの入力引数が、正確に0 (空ベクトル) または正確に1 (値1の1バイトベクトル) のいずれかでなければならないことを意味するなぜMINIMALIFをコンセンサスにするのか？ これにより、スタックから分岐情報を取得する非展性スクリプトの記述が格段に容易になる。。
  • OP_SUCCESSxオペコード上記のとおり、一部のオペコードはOP_SUCCESSxに改称され、スクリプトを無条件に妥当とする。
  • 署名オペコード。OP_CHECKSIGとOP_CHECKSIGVERIFYは、ECDSAの代わりにシュノア公開鍵と署名 (BIP340を参照) を扱うよう変更され、新オペコードOP_CHECKSIGADDが追加される。
    • オペコード186 (0xba) はOP_CHECKSIGADDと命名される。OP_CHECKSIGADD本オペコードは、バッチ検証と両立しないOP_CHECKMULTISIG系オペコードの喪失を補うために追加される。OP_CHECKSIGADDは機能的にOP_ROT OP_SWAP OP_CHECKSIG OP_ADDと等価であるが、1バイトしか要しない。OP_ADDのCScriptNum関連の挙動はすべてOP_CHECKSIGADDにも適用される。CHECKMULTISIGの代替案TaprootとTapscriptを用いて閾値k-of-n方針を実装する方法は複数存在する。
      • 単一のOP_CHECKSIGADDベースのスクリプトを用いる方法CHECKMULTISIGスクリプトm <pubkey_1> ... <pubkey_n> n CHECKMULTISIG (ウィットネス0 <signature_1> ... <signature_m>) は、スクリプト <pubkey_1> CHECKSIG <pubkey_2> CHECKSIGADD ... <pubkey_n> CHECKSIGADD m NUMEQUAL (ウィットネス <w_n> ... <w_1>) として書き換えられる。各ウィットネス要素w_iはpubkey_iに対応する署名か空ベクトルのいずれかである。同様のCHECKMULTISIGVERIFYスクリプトは、NUMEQUALをNUMEQUALVERIFYに置き換えることでBIP342に翻訳できる。この方式は、既存のOP_CHECKMULTISIGベースのスクリプトと非常によく似た特性を持つ。
      • 組合せごとにk-of-kスクリプトを用いる方法k-of-n方針は、マークルツリーの複数の葉にスクリプトを分割し、各葉が <pubkey_1> CHECKSIGVERIFY ... <pubkey_(n-1)> CHECKSIGVERIFY <pubkey_n> CHECKSIGを用いてk-of-k方針を実装することで実現できる。これは参加する公開鍵だけを開示するため、プライバシーの面では前述の方式より望ましい場合があるが、費用の面で上回るのはkの値が小さい場合だけである (任意のnに対する1-of-n、n ≥ 6に対する2-of-n、n ≥ 9に対する3-of-nなど)。さらに、ここでの署名は使用される分岐にコミットするため、署名者は、ほかのどの署名者が参加するかを前もって知っておくか、ツリーの葉ごとに署名を作るかの、どちらかをしなければならない。
      • 組合せごとに集約公開鍵を用いる方法各葉がk個の公開鍵からなる木を構築する代わりに、MuSig (https://eprint.iacr.org/2018/068)を用いて各葉がそれらk個の鍵の単一の 集約を含む木を構築することもできる。この方式ははるかに効率的であるが、単一の署名を共同で生成するために3ラウンドの対話的署名プロトコルを要する。
      • ネイティブなシュノア閾値署名マルチシグ方針は、検証可能な秘密分散を用いた閾値署名 (http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps)によっても実現できる。これは単一鍵支払いと区別不能なアウトプットとインプットをもたらすが、送金先のアドレスを決定する前に対話的プロトコル (および付随するバックアップ手続き) を要する代償を伴う。

署名オペコードのルール

以下のルールはOP_CHECKSIG、OP_CHECKSIGVERIFY、OP_CHECKSIGADDに適用される。

  • OP_CHECKSIGVERIFYとOP_CHECKSIGについては、公開鍵 (先頭要素) と署名 (先頭から2番目の要素) がスタックからポップされる。
    • スタックの要素数が2未満の場合、スクリプトは即座に失敗して終了しなければならない (MUST)。
  • OP_CHECKSIGADDについては、公開鍵 (先頭要素)、CScriptNum n (先頭から2番目の要素)、署名 (先頭から3番目の要素) がスタックからポップされる。
    • スタックの要素数が3未満の場合、スクリプトは即座に失敗して終了しなければならない (MUST)。
    • nが4バイトを超える場合、スクリプトは即座に失敗して終了しなければならない (MUST)。
  • 公開鍵のサイズがゼロの場合、スクリプトは即座に失敗して終了しなければならない (MUST)。
  • 公開鍵のサイズが32バイトの場合、BIP340に述べる公開鍵とみなされる。
    • 署名が空ベクトルでない場合、その署名は当該公開鍵に対して検証される (次小節を参照)。この場合の検証失敗は、スクリプト実行を即座に失敗として終了させる。
  • 公開鍵のサイズがゼロでも32バイトでもない場合、当該公開鍵は 未知の公開鍵型である未知の公開鍵型により、ソフトフォークを通じて新しい署名検証ルールを追加できる。ソフトフォークで実際の署名検証を加えることもでき、その検証は、通るか、スクリプトを失敗させて即座に終了させるかのどちらかになる。これにより、新しいSIGHASHモードや、NOINPUTタグ付き公開鍵 (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-December/016549.html)、そして署名検証のときにtaproot内部鍵に置き換わる公開鍵の定数を追加できる。とされ、実際の署名検証は適用されない。署名オペコードの実行中、それらは署名検証が成功したものとみなされる点を除き、既知の公開鍵型とまったく同様に振る舞う。
  • スクリプトがこの手順より前に失敗して終了していない場合、公開鍵型によらず:
    • 署名が空ベクトルである場合:
      • OP_CHECKSIGVERIFYについては、スクリプトは即座に失敗して終了しなければならない (MUST)。
      • OP_CHECKSIGについては、空ベクトルがスタックにプッシュされ、次のオペコードで実行が継続する。
      • OP_CHECKSIGADDについては、値nのCScriptNumがスタックにプッシュされ、次のオペコードで実行が継続する。
    • 署名が空ベクトルでない場合、当該オペコードはsigops予算に計上される (後述)。
      • OP_CHECKSIGVERIFYについては、スタックへのそれ以上の変更なしに実行が継続する。
      • OP_CHECKSIGについては、1バイトの値0x01がスタックにプッシュされる。
      • OP_CHECKSIGADDについては、値n + 1のCScriptNumがスタックにプッシュされる。

共通署名メッセージ拡張

BIP341共通署名メッセージへのtapscriptメッセージ拡張extを、ext_flag = 1により示されるものとして定義する。

  • tapleaf_hash (32): BIP341で定義されるtapleafハッシュ
  • key_version (1): tapscript署名オペコード実行における公開鍵の現行バージョンを表す定数値0x00。
  • codesep_pos (4): 現在実行中の署名オペコードより前に最後に実行されたOP_CODESEPARATORのオペコード位置。値はリトルエンディアン (実行されていない場合は0xffffffff)。スクリプト内の先頭オペコードの位置は0。複数バイトのプッシュオペコードは、プッシュされるデータのサイズによらず1個のオペコードとして数えられる。パースされたが未実行の分岐内のオペコードもこの値に計上される。

署名検証

公開鍵pで署名sigを検証するには:

  • 上記のtapscriptメッセージ拡張extを計算する。
  • sigが64バイト長であれば、Verify(p, hashTapSighash(0x00 || SigMsg(0x00, 1) || ext), sig) を返す。ここでVerifyはBIP340で定義される。
  • sigが65バイト長であれば、sig[64] ≠ 0x00かつVerify(p, hashTapSighash(0x00 || SigMsg(sig[64], 1) || ext), sig[0:64]) を返す。
  • それ以外は失敗。

要約すると、署名検証の意味論は以下を除きBIP340と同一である。

  1. 署名メッセージにはtapscript固有のデータkey_versionが含まれる。なぜ署名メッセージはkey_versionにコミットするのか？ これは、未知の公開鍵型を定義する将来の拡張のためであり、署名がある鍵型から別の鍵型へ移せないことを保証する。
  2. 署名メッセージは、葉バージョンとスクリプトを含むtapleaf_hashを通じて、実行されたスクリプトにコミットする (scriptCodeの代わり)。これは、このコミットメントがOP_CODESEPARATORの影響を受けないことを含意する。
  3. 署名メッセージには、最後に実行されたOP_CODESEPARATORのオペコード位置が含まれる。なぜ署名メッセージは最後に実行されたOP_CODESEPARATORの位置を含むのか？ これにより、スクリプトの実行された経路に署名するためにOP_CODESEPARATORを引き続き使用できる。codeseparator_positionはハッシュへの最後の入力であるため、単一のスクリプト内の複数のOP_CODESEPARATORについてSHA256のmidstateを効率的にキャッシュできる。対照的に、BIP143におけるOP_CODESEPARATORの扱いは、実行されたスクリプトのうち、最後に実行されたOP_CODESEPARATORより後の部分だけにコミットするというものであり、不要なスクリプトの再ハッシュを要する。なお、既知のOP_CODESEPARATORの用途である、1つ目の公開鍵のプッシュを2つのコード分岐で共有し、スクリプト中の2つ目の公開鍵のプッシュを省くという使い方は、各分岐を別個のtaproot葉に移すことでおそらくより安価に表現できる点に留意されたい。

リソース制限

多数のオペコードの意味論の変更に加え、リソース制限にもいくつかの変更がある。

  • スクリプトサイズ制限10000バイトという最大スクリプトサイズは適用されない。そのサイズはブロック重み制限によって暗黙に制約されるのみである。なぜスクリプトサイズの制限がもはや不要なのか？ 署名ハッシュにはscriptCodeが直接含まれなくなった (事前計算可能なtapleafハッシュを介して間接的にのみ含まれる) ため、署名検査に費やされるCPU時間は、実行されるスクリプトのサイズにもはや比例しない。
  • 非プッシュオペコード制限スクリプトあたり201という最大非プッシュオペコード制限は適用されない。なぜオペコード数の制限がもはや不要なのか？ オペコード制限は、実行中にデータ構造が無制限に増大すること (メモリー使用量、およびそれらの構造のサイズに比例して増大しうる時間の両方の理由から) を防ぐ限りにおいて役立つ。スタックとオルトスタックのサイズはすでに独立に制限されている。OP_IF、OP_NOTIF、OP_ELSE、OP_ENDIFに対してここ (https://bitslog.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/)で提案されここ (https://github.com/bitcoin/bitcoin/pull/16902)で実装されたとおりO(1) のロジックを用いれば、無制限に増えうるものとして唯一残っていた場合も、同じように避けられる。
  • sigops制限tapscript内のsigopsは、80000 (加重) というブロック全体の制限には計上されない。代わりに、スクリプトごとのsigops予算が存在する。予算は50に、当該トランザクションインプットのウィットネスの (CompactSize接頭辞を含む) シリアライズされたバイトサイズを加えたものに等しい。非空の署名を伴う署名オペコード (OP_CHECKSIG、OP_CHECKSIGVERIFY、OP_CHECKSIGADD) の実行は予算を50減らす。これにより予算が0未満になった場合、スクリプトは即座に失敗する。未知の公開鍵型かつ非空の署名を伴う署名オペコードも計上される。tapscriptのsigop制限署名オペコード制限は、署名操作が過剰に多いために検証が遅いスクリプトから保護する。tapscriptでは、署名オペコードの数はBIP141または既存のsigop制限には計上されない。旧来のsigop制限は、重みに加えた第2の制約となるため、ブロック構築におけるトランザクション選択を不必要に困難にしていた。代わりに、tapscriptの署名オペコード数はウィットネス重みにより制限される。加えて、この制限はブロックではなくトランザクションインプットに適用され、実際に実行された署名オペコードのみが計上される。Tapscriptの実行では、ウィットネス重み50単位あたり1個の署名オペコードに加え、1個の無料の署名オペコードが許される。sigop制限のパラメーター選択通常のウィットネスは、その重みが各33 + 65重み単位 (1重み単位のCompactSizeタグを含む) の公開鍵と (SIGHASH_ALL) 署名の組から構成されるため、本制限の影響を受けない。これはスクリプト内で公開鍵が再利用される場合も同様である。署名単体の重みだけで65または66重み単位となるためである。しかし本制限は、追加の重みを要求することで、重複する署名 (および公開鍵) を持つ異常なスクリプトの手数料を増加させる。sigopあたりの重み係数50は、BIP141のブロック制限の比率 (400万重み単位を80,000 sigopで割った値) に対応する。本制限が許す「無料」の署名オペコードは、トランザクションインプットの非ウィットネス部分の重みを考慮するために存在する。なぜハッシュオペコード等の他の高コストな操作ではなく、署名オペコードのみが予算に計上されるのか？ 署名検査オペコードを最大密度で含むスクリプト (50 WU/sigopの制限を考慮) の検証にかかるウィットネスバイトあたりのCPUコストは、ハッシュオペコード (520バイトのスタック要素制限を考慮) やOP_ROLL (1000個のスタック要素制限を考慮) を含む他のオペコードで構成されたスクリプトのそれに、すでに非常に近いことが分かっている。とはいえ、この構成は非常に柔軟であり、ソフトフォークを通じてCHECKSIGFROMSTACKのような新しい署名オペコードを追加し、予算に計上させることができる。将来、通常のスクリプトコストを変える新オペコードが導入されたとしても、ウィットネスを無意味なデータで埋める必要はない。代わりに、taprootのannexを用いて、実際のウィットネスサイズを増やすことなくウィットネスに重みを追加できる。。
  • スタック + オルトスタック要素数制限実行されたオペコードごとに、スタックとオルトスタックを合わせて1000要素という既存の制限が引き続き適用される。これは初期スタックのサイズにも適用されるよう拡張される。
  • スタック要素サイズ制限スタック要素あたり最大520バイトという既存の制限が、初期スタックとプッシュオペコードの両方において引き続き適用される。

根拠

展開

本提案はTaproot (BIP341) と同一の形で展開される。

実例

Taproot (BIP341) のテストベクトルには、Tapscriptの実行例も含まれる。

謝辞

本文書は多数の議論の結果であり、多くの人々による貢献を含む。著者らは、構造化レビュー (https://github.com/ajtowns/taproot-review)の参加者を含め、貴重なフィードバックとレビューを提供してくれたすべての方々に感謝する。

関連エントリー

原典の外部ソース

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

他の外部ソース