BIP 342 — Taproot スクリプトの検証 - ビットコイン・インスティテュート

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 使用として識別される。

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

インプットが BIP141 または BIP341 により無効である場合は失敗。
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 の末尾を越えて拡張するために復号に失敗する場合は失敗。
BIP341 で定義される 初期スタック (すなわち、任意の annex とその後の末尾 2 個のスタック要素を取り除いたウィットネススタック) が何らかのリソース制限 (スタックサイズ、およびスタック内要素のサイズ。下記「リソース制限」を参照) に違反する場合は失敗。この検査は OP_SUCCESSx により回避できることに注意。
tapscript は、次節のルールに従い、初期スタックを入力として実行される。
1. 何らかの理由で実行が失敗した場合は失敗。
2. 実行の結果、CastToBool() で真と評価される要素がスタックにちょうど 1 個だけ残る、という状態以外になった場合は失敗。
失敗に遭遇せずこの手順に到達した場合、検証は成功する。

スクリプト実行

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, hash_TapSighash(0x00 || SigMsg(0x00, 1) || ext), sig) を返す。ここで Verify は BIP340 で定義される。
sig が 65 バイト長であれば、sig[64] ≠ 0x00 かつ Verify(p, hash_TapSighash(0x00 || SigMsg(sig[64], 1) || ext), sig[0:64]) を返す。
それ以外は失敗。

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

署名メッセージには tapscript 固有のデータ key_version が含まれる。なぜ署名メッセージは key_version にコミットするのか？これは、未知の公開鍵型を定義する将来の拡張のためであり、署名がある鍵型から別の鍵型へ移せないことを保証する。
署名メッセージは、葉バージョンとスクリプトを含む tapleaf_hash を通じて、実行されたスクリプトにコミットする (scriptCode の代わり)。これは、このコミットメントが OP_CODESEPARATOR の影響を受けないことを含意する。
署名メッセージには、最後に実行された OP_CODESEPARATOR のオペコード位置が含まれる。なぜ署名メッセージは最後に実行された OP_CODESEPARATOR の位置を含むのか？これにより、スクリプトの実行された経路に署名するために OP_CODESEPARATOR を引き続き使用できる。codeseparator_position はハッシュへの最後の入力であるため、単一のスクリプト内の複数の OP_CODESEPARATOR について SHA256 の midstate を効率的にキャッシュできる。対照的に、BIP143 における OP_CODESEPARATOR の扱いは、最後に実行された OP_CODESEPARATOR 以降のみ実行されたスクリプトにコミットするというものであり、不要なスクリプトの再ハッシュを要する。なお、既知の OP_CODESEPARATOR の用途である、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)の参加者を含め、貴重なフィードバックとレビューを提供してくれたすべての方々に感謝する。

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

序論

概要

著作権

動機

設計

仕様

スクリプト実行

署名オペコードのルール

共通署名メッセージ拡張

署名検証

リソース制限

根拠

展開

実例

謝辞

原典の外部ソース

他の外部ソース

序論

概要

著作権

動機

設計

仕様

スクリプト実行

署名オペコードのルール

共通署名メッセージ拡張

署名検証

リソース制限

根拠

展開

実例

謝辞

関連エントリー

原典の外部ソース

他の外部ソース