Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
BIP342「Validation of Taproot Scripts」の日本語版

  BIP: 342
  Layer: Consensus (soft fork)
  Title: Validation of Taproot Scripts
  Author: Pieter Wuille <pieter.wuille@gmail.com>
          Jonas Nick <jonasd.nick@gmail.com>
          Anthony Towns <aj@erisian.com.au>
  Comments-Summary: No comments yet.
  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0342
  Status: Draft
  Type: Standards Track
  Created: 2020-01-19
  License: BSD-3-Clause
  Requires: 340, 341
  Post-History: 2019-05-06: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016914.html [bitcoin-dev] Taproot proposal

Table of Contents

導入

アブストラクト

このドキュメントでは BIP341 のもとでの初期スクリプトシステムのセマンティクスを定義します。

著作権

このドキュメントは 3 条項 BSD ライセンスでライセンスされます。

動機

BIP341 ではスクリプトの構造についてだけの改善提案がなされており、スクリプト言語自体に含まれる特定の OP コードのセマンティクスについてはその目的とは相容れません。 別々の任意の改善によってそれらを取り扱うこともできますが、BIP341 自体で同時に扱わない限りその影響は保証されません。

特に、その目的はスクリプトシステムを使ったコインの使用時に Schnorr 署名バッチ検証、および署名ハッシュに関する改善を利用可能とすることです。

設計

これらの目的を達するため、署名に関する OP コードである OP_CHECKSIG および OP_CHECKSIGVERIFYBIP340 で定義されているように Schnorr 署名を検証できるように、また BIP341 の共通的なメッセージの計算方法に基づいた署名メッセージアルゴリズムを利用するように修正されます。 Tapscript 署名メッセージは、OP_CODESEPARATOR の取り扱いについても簡略化し、これをより効果的なものとします。

非効率的な OP_CHECKMULTISIG および OP_CHECKMULTISIGVERIFY といった OP コードについては無効化されます。 一方で、新しい OP コードである OP_CHECKSIGADD が導入され、バッチ検証ができる形で従来と同様なマルチシグポリシーを作成することができるようになります。 Tapscript は新しく、より簡単な署名 OP コード制限を用いており、トランザクションの重量との複雑な相互作用があることを修正しています。 さらに MINIMALIF を必須とすることで起こりうる展性ベクトルを削減しています。

Tapscript は、例えば新しい hash_types や署名アルゴリズムを追加することにより、未知の鍵タイプを定義することでソフトフォークによってアップグレードすることができます。 さらに tapscript の新しい OP_SUCCESS OP コードにより OP_NOP を用いるよりも、よりきれいに新しい OP コードを導入することができます。

仕様

以下のルールは以下の条件がすべて true となるようなトランザクションの入力を検証する際にのみ適用されます:

  • トランザクションの入力が SegWit による使用 であった場合 (すなわち、scriptPubKey が BIP141 で定義されているような witness プログラムを含む場合)。
  • BIP341 で定義されるような taproot による使用であった場合 (すなわち、witness バージョンが 1、witness プログラムが 32 バイト、かつ P2SH にラッピングされたものでない場合)。
  • BIP341 で定義されるような スクリプトパスによる使用であった場合 (すなわち、任意の要素である annex を witness スタックから取り除いた後に、二個以上のスタック要素が残っている場合)。
  • 葉のバージョンが 0xc0 であった場合 (すなわち、任意の要素である annex を取り除いた後に残る witness 要素の最後のものの最初のバイトが が 0xc0 または 0xc1 であった場合)、これは tapscript による使用となります。
そのような入力の検証は、以下のステップを指定された順番で実行したものと等価にならないといけません。
  1. 入力が BIP141 または BIP341 に対して無効であれば、失敗とします。
  2. BIP341 で定義されているようなスクリプト (すなわち、任意の要素である annex を取り除いた後に残る witness スタック要素の第二番目のもの) は tapscript と呼ばれ、一つずつ OP コードにデコードされます。
    1. OP コードが 80, 98, 126-129, 131-134, 137-138, 141-142, 149-153, 187-254 のいずれかに遭遇した場合、検証は成功とします (以下の検証ルールは適用されません)。これはその後の tapscript のバイト列が正常にデコードされないような場合でも成り立ちます。これらの OP コードは OP_SUCCESS80, ..., OP_SUCCESS254 にリネームされ、総称して OP_SUCCESSx と呼ばれます[1]
    2. いずれかのプッシュ OP コードが tapscript の終端を超えてしまいデコードに失敗した場合には、失敗とします。
  3. BIP341 で定義されているような (すなわち、任意の要素である annex およびそれに続く上二つのスタック要素を削除した後の witness スタック) 初期スタックがいずれかのリソース制限 (スタックサイズおよびスタック内の要素のサイズ; 以下の「リソース制限」を参照してください) に違反した場合には、失敗とします。このチェックは OP_SUCCESSx を用いることで回避できることに注意してください。
  4. 初期スタックを入力として下記のセクションにあるようなルールにもとづいて tapscript が実行されます。
    1. なんらかの理由によって実行が失敗した場合には、失敗とします。
    2. 実行の結果、CastToBool() によって true と評価されるような要素がスタックにただひとつだけ残るような場合を除き、失敗とします。
  5. 失敗に遭遇せずにこのステップに達した場合、検証は成功とします。

スクリプトの実行

Tapscript の実行ルールは BIP65 および BIP112 で定義されている OP_CHECKLOCKTIMEVERIFY および OP_CHECKSEQUENCEVERIFY OP コードを含む、BIP141 に従う P2WSH のものにもとづきますが、以下のような変更点が加えられています:

  • 無効化されたスクリプト OP コード 以下のスクリプト OP コードは tapscript では無効化されています: OP_CHECKMULTISIG および OP_CHECKMULTISIGVERIFY[2]。無効化された OP コードは実行されるとスクリプトをすぐさま失敗させ終了させることで OP_RETURN と同様に振る舞います。またスクリプト内で実行されなかったブランチに含まれていた場合には無視されます。
  • コンセンサスで強制される MINIMALIF P2WSH でのみ標準的なルールである MINIMALIF ルールについて、tapscript ではコンセンサスで強制されます。これによって OP_IF および OP_NOTIF OP コードへの入力引数は厳密に 0 (空ベクトル) または厳密に 1 (値 1 を持つ 1 バイトのベクトル) とならなければいけないことを意味します[3]
  • OP_SUCCESSx OP コード 上述の通り、いくつかの OP コードは OP_SUCCESSx にリネームされ、スクリプトを無条件で有効となるようにしました。
  • 署名 OP コード OP_CHECKSIG および OP_CHECKSIGVERIFY は ECDSA ではなく Schnorr 公開鍵および署名 (BIP340 を参照してください) に対して動作するように修正され、新しい OP コードとして OP_CHECKSIGADD が追加されました。
    • OP コード 186 (0xba) は OP_CHECKSIGADD と命名されます。[4][5]

署名 OP コードのルール

以下のルールは OP_CHECKSIGOP_CHECKSIGVERIFY および OP_CHECKSIGADD に対して適用されます。

  • OP_CHECKSIGVERIFY および OP_CHECKSIG については、公開鍵 (最上位要素) および署名 (上から二番目の要素) がスタックからポップされます。
    • スタックにある要素が 2 未満の場合、スクリプトは失敗しなければならず (MUST)、すぐさま終了します。
  • OP_CHECKSIGADD については、公開鍵 (最上位要素)、CScriptNum n (上から二番目の要素)、および署名 (上から三番目の要素) がスタックからポップされます。
    • スタックにある要素が 3 未満の場合、スクリプトは失敗しなければならず (MUST)、すぐさま終了します。
    • n が 4 バイトよりも大きい場合、スクリプトは失敗しなければならず (MUST)、すぐさま終了します。
  • 公開鍵のサイズがゼロの場合、スクリプトは失敗しなければならず (MUST)、すぐさま終了します。
  • 公開鍵のサイズが 32 バイトの場合、BIP340 で説明される公開鍵であると解釈されます:
    • 署名が空のベクトルでない場合、署名は公開鍵に対して妥当性の検証 (次のサブセクションを参照してください) が行われます。検証が失敗した場合、このケースではすぐさまスクリプトの実行は失敗として終了します。
  • 公開鍵のサイズがゼロでも 32 バイトでもない場合、公開鍵は未知の公開鍵タイプ[6]であり、実際に署名検証は行われません。署名 OP コードのスクリプトの実行中には、署名検証が成功とみなされることを除き、既知の公開鍵タイプと厳密に同じ動きをします。
  • スクリプトが失敗せず、このステップの前に停止しなかった場合、公開鍵のタイプによらず:
    • 署名が空のベクトルであった場合:
      • OP_CHECKSIGVERIFY の場合、スクリプトは失敗しなければならず (MUST)、すぐさま終了します。
      • OP_CHECKSIG の場合、空のベクトルがスタックにプッシュされ、次の OP コードに実行は移されます。
      • OP_CHECKSIGADD の場合、値 n を持った CScriptNum がスタックへプッシュされ、次の OP コードに実行は移されます。
    • 署名が空のベクトルではない場合、OP コードは sigops バジェットにカウントされます (下を参照してください)。
      • OP_CHECKSIGVERIFY の場合、スタックに何の変更も行うことなく実行は続行されます。
      • OP_CHECKSIG の場合、1 バイトの値 0x01 がスタックにプッシュされます。
      • OP_CHECKSIGADD の場合、n + 1 の値を持つ CScriptNum がスタックにプッシュされます。

署名検証

公開鍵 p に対して、署名 sig を検証するためには:

  • Tapscript メッセージ拡張 ext を計算します。これは以下を結合したものによって構成されます:
    • tapleaf_hash (32): BIP341 で定義されている tapleaf ハッシュ。
    • key_version (1): Tapscript 署名 OP コード実行での公開鍵の現在のバージョンを表す定数値 0x00
    • codesep_pos (4): 現在実行されている署名 OP コードの直前の、最後に実行された OP_CODESEPARATOR の OP コードの位置をリトルエンディアンで表したもの (または、実行されたものがなければ 0xffffffff)。スクリプトの最初の OP コードは位置 0 をもちます。マルチバイトのプッシュ OP コードは、プッシュされるデータのサイズにかかわらずひとつの OP コードとしてカウントされます。
  • sig が 64 バイトの長さの場合、Verify(p, hashTapSigHash(0x00 || SigMsg(0x00, 1) || ext), sig) を返却します。ここで VerifyBIP340 で定義されているものです。
  • sig が 65 バイトの長さの場合、sig[64] ≠ 0x00 and Verify(p, hashTapSighash(0x00 || SigMsg(sig[64], 1) || ext), sig[0:64]) を返却します。
  • それ以外の場合には、失敗とします。
まとめると、以下の点を除いて署名検証のセマンティクスは BIP340 のものと同一です:
  1. 署名メッセージは tapscript 由来のデータである key_version を含みます。[7]
  2. 署名メッセージは、scriptCode ではなく葉のバージョンおよびスクリプトを含む tapleaf_hash を通じて、実行されたスクリプトに対してコミットします。
  3. 署名メッセージは最後に実行された OP_CODESEPARATOR の OP コードの位置を含みます。[8]

リソース制限

いくつかの OP コードのセマンティクスを変更したのに加えて、リソース制限についてもいくつかの変更が加えられています:

  • スクリプトサイズ制限 10000 バイトの最大スクリプトサイズは適用されません。これらのサイズはブロックの重量制限によって暗に制限されます。[9]
  • 非プッシュ OP コード制限 スクリプトあたりの 201 個の最大非プッシュ OP コード制限は適用されません。[10]
    • Sigops 制限 Tapscript 内の sigops はブロック全体の制限である 80000 (重み付けあり) に対してカウントされません。その代わり、スクリプトあたりの sigops バジェットが存在します。バジェットは 50 + トランザクションの入力の witness 全体をシリアライズしたバイト数 (CCompactSize プレフィクスを含みます) です。空でない署名に対して署名 OP コード (OP_CHECKSIGOP_CHECKSIGVERIFY、または OP_CHECKSIGADD) を実行すると、バジェットが 50 ずつ減少します。これによってバジェットがゼロを下回った場合、スクリプトはすぐさま失敗します。未知の公開鍵タイプおよび空でない署名に対する署名 OP コードについても勘定されます。[11][12][13]
  • スタック + オルトスタック要素数制限 任意の OP コードを実行した後に残る、スタックおよびオルトスタックを合わせた 1000 要素の既存の制限は存続します。これは初期スタックのサイズに対しても適用されます。
  • スタック要素サイズ制限 スタック要素あたり最大で 520 バイトの既存の制限は、初期スタックおよびプッシュ OP コード双方に対して存続します。

論拠

  1. ^ OP_SUCCESSx OP_SUCCESSx はスクリプトシステムをアップグレードするためのメカニズムです。ソフトフォークによって OP_SUCCESSx の意味が定義される前にこれを用いることは安全ではなく、資産の喪失に繋がります。スクリプト内に OP_SUCCESSx を含めることは無条件にスクリプトの検証をスキップします。様々なエッジケースに対する困難を避けるために、これは任意のスクリプトの実行ルールに優先されます。例えば: スクリプトに OP_SUCCESSx が含まれており、入力スタックが 1000 を超える要素を持つ場合、過剰な署名 OP コードの後に OP_SUCCESSx がある場合、または OP_ENDIF がないような条件分岐のあるスクリプトなどです。スクリプトのどこかに単に OP_SUCCESSx が存在することは、そのようなすべての場合にスクリプトが成功することを保証します。OP_SUCCESSx はビットコインの非常に初期のバージョン (v0.1〜v0.3.5) での OP_RETURN に似ています。オリジナルの OP_RETURN ではスクリプトの実行をすぐさま停止し、停止した時点でのスタックのトップ要素に基づいて成功または失敗を返却します。これはオリジナルのビットコインプロトコルの重大な構造上の欠陥であり、scriptSig 内に OP_RETURN を仕込むことで無条件で第三者がコインを盗むことができていました。OP_SUCCESSx はスクリプトの一部であり (すなわち taproot 出力によってコミットされているため)、コインの持ち主の同意があることを意味しており、検証プロセスにおいて第三者が OP_SUCCESSx を検証プロセスにおいて挿入することはできませんので、この提案ではこれは問題になりません。OP_SUCCESSx はたくさんのアップグレードの可能性で利用することができます:
    • ソフトフォークによって OP_SUCCESSx は関数的な OP コードにすることも可能です。スタックに対して読み込み専用のアクセスしかできない OP_NOPx 派生系の OP コードとは違い、OP_SUCCESSx はスタックへの書き込みも行うことができます。OP_SUCCESSx を含むスクリプトへの任意の変更は、これを有効なスクリプトから無効なスクリプトに変更することのみができ、これは常にソフトフォークによって達成可能です。
    • OP_SUCCESSx は初期スタックおよびプッシュ OP コードのサイズチェックに優先されますので、520 バイトを超えるスタック要素を必要とする OP_SUCCESSx 派生の OP コードは、ソフトフォークによって制限を上昇させることができます。
    • OP_SUCCESSx は既存の OP コードと協調動作することで、動作を再定義することもできるでしょう。例えば OP_SUCCESSx 派生の OP コードが 64 ビットの整数値に対してはたらく場合、同じスクリプトの既存の算術 OP コードに対して同じように動作するようにすることもできるでしょう。
    • OP_SUCCESSx は潜在的にパースできないスクリプトであっても許可するということから、マルチバイトの OP コードを導入することもできますし、特定の OP_SUCCESSx OP コードでプレフィクスすることで完全に新しいスクリプト言語を導入することもできます。
  2. ^ OP_CHECKMULTISIG および OP_CHECKMULTISIGVERIFY が無効化され、しかも OP_SUCCESSx とはされていないのはなぜですか? これは tapscript においても OP_CHECKMULTISIG を間違えて使い続けてしまう人たちが問題にすぐさま気づくことで注意喚起を行うためです。またスクリプトの逆アセンブラに対して文脈に依存した処理を行う複雑性を回避するためでもあります。
  3. ^ MINIMALIF をコンセンサスルールとしたのはなぜですか? スタックからブランチの情報を取得するスクリプトが展性を持たないようなものを書くのを非常に簡単にするためです。
  4. ^ OP_CHECKSIGADD この OP コードはバッチ検証と互換性のない OP_CHECKMULTISIG 系の OP コードがなくなったことを補完するものです。OP_CHECKSIGADD は機能的には OP_ROT OP_SWAP OP_CHECKSIG OP_ADD と同一ですが、1 バイトのみで構成されます。すべての CScriptNum に関連した OP_ADD の振る舞いについては OP_CHECKSIGADD に対しても適用されます。
  5. ^ CHECKMULTISIG への代替 Taproot および tapscript を用いた k-of-n 閾値ポリシーを実装する方法はいくつかあります:
    • 一つの OP_CHECKSIGADD に基づいたスクリプトを用いる方法 Witness が 0 <signature_1> ... <signature_m> の場合の CHECKMULTISIG スクリプト m <pubkey_1> ... <pubkey_n> n CHECKMULTISIG は witness を <w_n> ... <w_1> とする <pubkey_1> CHECKSIG <pubkey_2> CHECKSIGADD ... <pubkey_n> CHECKSIGADD m NUMEQUAL というスクリプトで代替可能です。すべての witness 要素 w_ipubkey_i に対応する署名もしくは空のベクトルになります。これと似た CHECKMULTISIGVERIFY スクリプトは、NUMEQUALNUMEQUALVERIFY に置き換えることで BIP342 に翻訳することができます。このアプローチは既存の OP_CHECKMULTISIG ベースのスクリプトと非常に似た特徴を持ちます。
    • すべての組み合わせに対して k-of-k スクリプトを用いる方法 スクリプトをそれぞれが <pubkey_1> CHECKSIGVERIFY ... <pubkey_(n-1)> CHECKSIGVERIFY <pubkey_n> CHECKSIG を用いた k-of-k のポリシーを実装したいくつかの Merkle 木の葉に分割することで、k-of-n ポリシーを実装することができます。これは一つ前のアプローチと比べて、参加している公開鍵のみを公開するため、プライバシーの理由から好ましい方法ではありますが、k の値が小さい場合 (任意の n について 1-of-nn ≥ 6 に対して 2-of-nn ≥ 9 に対して 3-of-n, ...) についてのみコスト効果が高い方法となります。なお、ここでの署名は利用されたブランチにコミットされますので、署名者はどの他の署名者が参加しているのかについて知るか、それぞれの木の葉に対して署名を作成する必要があります。
    • すべての組み合わせに対して集約した公開鍵を使う方法 すべての葉が k 個の公開鍵によって構成される木を構成するのではなく、MuSig を利用してすべての葉が k 個の鍵を集約した一つの鍵で構成される木を構成する方法もあります。このアプローチはより効率的ですが、(ひとつの) 署名を作成するのに協調して 3 ラウンドの対話的な署名プロトコルを実行する必要があります。
    • ネイティブ Schnorr 閾値署名 検証可能な秘密分散法を利用することで、閾値署名を用いたマルチシグポリシーを実現することもできます。これによって出力および入力は単一鍵による支払いと区別できないものになりますが、送金先アドレスを決定する前に対話的なプロトコル (およびそれに関連したバックアップ手続き) が必要となるという代償を支払う必要があります。
  6. ^ 未知の公開鍵タイプにより、ソフトフォークによって新しい署名検証ルールを追加することができます。ソフトフォークでは合格、またはスクリプトが失敗しすぐさま終了するといったいずれかの実際の署名検証が追加されるでしょう。こうすることで、新しい SIGHASH モードが追加できたり、NOINPUT でタグ付けされた公開鍵や、署名検証のための taproot 内部鍵で置換できる公開鍵定数などを追加することができます。
  7. ^ 署名メッセージが key_version に対してコミットされるのはなぜですか? これは未知の公開鍵タイプを定義する将来の拡張において、署名が一つの鍵タイプから別の鍵タイプへと移動できないことを保証します。
  8. ^ 署名メッセージが最後に実行された OP_CODESEPARATOR の OP コードの位置を含むのはなぜですか? スクリプトの実行されたパスに対して署名するために OP_CODESEPARATOR が継続的に使用できるようになるからです。なぜなら codeseparator_position はハッシュへの最後の入力であり、SHA256 の midstate は一つのスクリプトの中の複数の OP_CODESEPARATOR に対して効率的にキャッシュできるからです。一方で、BIP143 での OP_CODESEPARATOR の利用の仕方だと、最後に実行された OP_CODESEPARATOR 以降に実行されたスクリプトにのみコミットしますので、スクリプトの不必要な再ハッシュが必要となります。一つの OP_CODESEPARATOR の既知のユースケースとして、二つのコードブランチの間で最初の公開鍵を共有することで二番目の公開鍵のプッシュを節約するといったものは、それぞれのブランチを分離された taproot 葉に移動することで、より安く表現できる可能性が高いことに注意してください。
  9. ^ スクリプトサイズの制限がもはや必要ないのはなぜですか? 署名ハッシュに scriptCode は直接的に含まれないため (事前計算可能な tapleaf ハッシュを通して間接的にのみ含まれます)、署名検証に費やされる CPU 時間は実行されるスクリプトのサイズにもはや比例しないためです。
  10. ^ OP コードの数に対する制限がもはや必要ないのはなぜですか? OP コード制限は、実行時にデータ構造が無限に膨らんでしまうのを防ぐのに限られた効果しかありません (これはメモリの利用の仕方および、このような構造のサイズに対して比例して時間が増えることによります)。スタックおよびオルトスタックのサイズは既に非依存的に制限されています。こちらで提案されているものや、こちらで実装されているように、OP_IFOP_NOTIFOP_ELSE、および OP_ENDIF を用いた O(1) のロジックを使うことで、どちらか一方のみしか防ぐことができません。
  11. ^ Tapscript の sigop 制限 署名 OP コード制限は、過剰に多数の署名命令があるために検証が遅くなるようなスクリプトから守るために存在します。Tapscript においては、BIP141 や旧来の sigop 制限に対して署名 OP コードの数はカウントされません。従来の sigop 制限は、重量に追加して二番目の拘束条件となってしまうため、ブロック生成時のトランザクション選択を不必要に難しくしてしまいます。一方で、tapscript の署名 OP コードの数は witness の重量によって制限されます。さらに、制限はブロックではなくトランザクションの入力に対してのみ適用され、実際に実行された署名 OP コードのみカウントされます。Tapscript の実行においては、50 witness 重量単位に対して一つの署名 OP コードおよび、一回の自由な署名 OP コードを許可します。
  12. ^ Sigop 制限のパラメータ選択 通常の witness は、その重量は公開鍵および、それぞれ 33 + 65 の重量単位 (1 重量単位を持つ CCompactSize タグを含みます) をもつ (SIGHASH_ALL の) 署名ペアで構成される重量を持ちますので、この制限に影響を受けません。署名自体の重量は 65 ないし 66 の重量単位を持ちますので、公開鍵が再利用された場合にもこれは成り立ちます。重量あたりの 50 という sigop 係数は、BIP141 のブロック制限の率に対応しています: 4 メガ重量単位を 80,000 sigop で割ったものです。制限によって許可された「自由な」署名 OP コードはトランザクションの入力の非 witness 領域の重量に対応したものです。
  13. ^ 署名 OP コードのみがバジェットに対してカウントされ、例えばハッシュ OP コードやその他の高価な命令がカウントされないのはなぜですか? スクリプトの検証の際に witness バイトあたりの CPU コストは、署名検証 OP コード (50 WU/sigop の制限が使われる) が最大の密度で含まれているスクリプトを検証する際のものは、既にハッシュ OP コード (520 バイトのスタック要素制限が使われる) や OP_ROLL (1000 スタック要素制限が使われる) を含む他の OP コードで詰められたスクリプトのものに非常に近くなっています。つまり、この構成は非常に柔軟で、CHECKSIGFROMSTACK などの新しい署名 OP コードを追加し、ソフトフォークによって制限に対してカウントすることができます。将来的に、通常のスクリプトコストを変更するような新しい OP コードが導入された場合においても、意味のないデータを witness に詰め込む必要はありません。その代わり、taproot annex を用いることで、実際の witness サイズを増やすことなく witness に対して重量を追加することができます。

謝辞

このドキュメントは多数の議論の結果およびいくつかの人たちによる貢献を含みます。著者は有益なフィードバックおよびレビューをいただいたすべての人たちに感謝いたします。これには構造的レビューに参加いただいた方を含みます。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment