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
このドキュメントでは BIP341 のもとでの初期スクリプトシステムのセマンティクスを定義します。
このドキュメントは 3 条項 BSD ライセンスでライセンスされます。
BIP341 ではスクリプトの構造についてだけの改善提案がなされており、スクリプト言語自体に含まれる特定の OP コードのセマンティクスについてはその目的とは相容れません。 別々の任意の改善によってそれらを取り扱うこともできますが、BIP341 自体で同時に扱わない限りその影響は保証されません。
特に、その目的はスクリプトシステムを使ったコインの使用時に Schnorr 署名、バッチ検証、および署名ハッシュに関する改善を利用可能とすることです。
これらの目的を達するため、署名に関する OP コードである OP_CHECKSIG および OP_CHECKSIGVERIFY は BIP340 で定義されているように 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 による使用となります。
- 入力が BIP141 または BIP341 に対して無効であれば、失敗とします。
- BIP341 で定義されているようなスクリプト (すなわち、任意の要素である annex を取り除いた後に残る witness スタック要素の第二番目のもの) は tapscript と呼ばれ、一つずつ OP コードにデコードされます。
- OP コードが 80, 98, 126-129, 131-134, 137-138, 141-142, 149-153, 187-254 のいずれかに遭遇した場合、検証は成功とします (以下の検証ルールは適用されません)。これはその後の tapscript のバイト列が正常にデコードされないような場合でも成り立ちます。これらの OP コードは
OP_SUCCESS80, ...,OP_SUCCESS254にリネームされ、総称してOP_SUCCESSxと呼ばれます[1]。 - いずれかのプッシュ OP コードが tapscript の終端を超えてしまいデコードに失敗した場合には、失敗とします。
- OP コードが 80, 98, 126-129, 131-134, 137-138, 141-142, 149-153, 187-254 のいずれかに遭遇した場合、検証は成功とします (以下の検証ルールは適用されません)。これはその後の tapscript のバイト列が正常にデコードされないような場合でも成り立ちます。これらの OP コードは
- BIP341 で定義されているような (すなわち、任意の要素である annex およびそれに続く上二つのスタック要素を削除した後の witness スタック) 初期スタックがいずれかのリソース制限 (スタックサイズおよびスタック内の要素のサイズ; 以下の「リソース制限」を参照してください) に違反した場合には、失敗とします。このチェックは
OP_SUCCESSxを用いることで回避できることに注意してください。 - 初期スタックを入力として下記のセクションにあるようなルールにもとづいて tapscript が実行されます。
- なんらかの理由によって実行が失敗した場合には、失敗とします。
- 実行の結果、
CastToBool()によって true と評価されるような要素がスタックにただひとつだけ残るような場合を除き、失敗とします。
- 失敗に遭遇せずにこのステップに達した場合、検証は成功とします。
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_NOTIFOP コードへの入力引数は厳密に 0 (空ベクトル) または厳密に 1 (値 1 を持つ 1 バイトのベクトル) とならなければいけないことを意味します[3]。 - OP_SUCCESSx OP コード 上述の通り、いくつかの OP コードは
OP_SUCCESSxにリネームされ、スクリプトを無条件で有効となるようにしました。 - 署名 OP コード
OP_CHECKSIGおよびOP_CHECKSIGVERIFYは ECDSA ではなく Schnorr 公開鍵および署名 (BIP340 を参照してください) に対して動作するように修正され、新しい OP コードとしてOP_CHECKSIGADDが追加されました。
以下のルールは OP_CHECKSIG、OP_CHECKSIGVERIFY および OP_CHECKSIGADD に対して適用されます。
OP_CHECKSIGVERIFYおよびOP_CHECKSIGについては、公開鍵 (最上位要素) および署名 (上から二番目の要素) がスタックからポップされます。- スタックにある要素が 2 未満の場合、スクリプトは失敗しなければならず (MUST)、すぐさま終了します。
OP_CHECKSIGADDについては、公開鍵 (最上位要素)、CScriptNumn(上から二番目の要素)、および署名 (上から三番目の要素) がスタックからポップされます。- スタックにある要素が 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) を返却します。ここで Verify は BIP340 で定義されているものです。
- sig が 65 バイトの長さの場合、sig[64] ≠ 0x00 and Verify(p, hashTapSighash(0x00 || SigMsg(sig[64], 1) || ext), sig[0:64]) を返却します。
- それ以外の場合には、失敗とします。
- 署名メッセージは tapscript 由来のデータである key_version を含みます。[7]
- 署名メッセージは、scriptCode ではなく葉のバージョンおよびスクリプトを含む tapleaf_hash を通じて、実行されたスクリプトに対してコミットします。
- 署名メッセージは最後に実行された
OP_CODESEPARATORの OP コードの位置を含みます。[8]
いくつかの OP コードのセマンティクスを変更したのに加えて、リソース制限についてもいくつかの変更が加えられています:
- スクリプトサイズ制限 10000 バイトの最大スクリプトサイズは適用されません。これらのサイズはブロックの重量制限によって暗に制限されます。[9]
- 非プッシュ OP コード制限 スクリプトあたりの 201 個の最大非プッシュ OP コード制限は適用されません。[10]
- Sigops 制限 Tapscript 内の sigops はブロック全体の制限である 80000 (重み付けあり) に対してカウントされません。その代わり、スクリプトあたりの sigops バジェットが存在します。バジェットは 50 + トランザクションの入力の witness 全体をシリアライズしたバイト数 (
CCompactSizeプレフィクスを含みます) です。空でない署名に対して署名 OP コード (OP_CHECKSIG、OP_CHECKSIGVERIFY、またはOP_CHECKSIGADD) を実行すると、バジェットが 50 ずつ減少します。これによってバジェットがゼロを下回った場合、スクリプトはすぐさま失敗します。未知の公開鍵タイプおよび空でない署名に対する署名 OP コードについても勘定されます。[11][12][13]
- Sigops 制限 Tapscript 内の sigops はブロック全体の制限である 80000 (重み付けあり) に対してカウントされません。その代わり、スクリプトあたりの sigops バジェットが存在します。バジェットは 50 + トランザクションの入力の witness 全体をシリアライズしたバイト数 (
- スタック + オルトスタック要素数制限 任意の OP コードを実行した後に残る、スタックおよびオルトスタックを合わせた 1000 要素の既存の制限は存続します。これは初期スタックのサイズに対しても適用されます。
- スタック要素サイズ制限 スタック要素あたり最大で 520 バイトの既存の制限は、初期スタックおよびプッシュ OP コード双方に対して存続します。
- ^
OP_SUCCESSxOP_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_SUCCESSxOP コードでプレフィクスすることで完全に新しいスクリプト言語を導入することもできます。
- ソフトフォークによって
- ^
OP_CHECKMULTISIGおよびOP_CHECKMULTISIGVERIFYが無効化され、しかも OP_SUCCESSx とはされていないのはなぜですか？ これは tapscript においてもOP_CHECKMULTISIGを間違えて使い続けてしまう人たちが問題にすぐさま気づくことで注意喚起を行うためです。またスクリプトの逆アセンブラに対して文脈に依存した処理を行う複雑性を回避するためでもあります。 - ^ MINIMALIF をコンセンサスルールとしたのはなぜですか？ スタックからブランチの情報を取得するスクリプトが展性を持たないようなものを書くのを非常に簡単にするためです。
- ^
OP_CHECKSIGADDこの OP コードはバッチ検証と互換性のないOP_CHECKMULTISIG系の OP コードがなくなったことを補完するものです。OP_CHECKSIGADDは機能的にはOP_ROT OP_SWAP OP_CHECKSIG OP_ADDと同一ですが、1 バイトのみで構成されます。すべてのCScriptNumに関連したOP_ADDの振る舞いについてはOP_CHECKSIGADDに対しても適用されます。 - ^
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_iはpubkey_iに対応する署名もしくは空のベクトルになります。これと似たCHECKMULTISIGVERIFYスクリプトは、NUMEQUALをNUMEQUALVERIFYに置き換えることで 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-n、n ≥ 6 に対して 2-of-n、n ≥ 9 に対して 3-of-n, ...) についてのみコスト効果が高い方法となります。なお、ここでの署名は利用されたブランチにコミットされますので、署名者はどの他の署名者が参加しているのかについて知るか、それぞれの木の葉に対して署名を作成する必要があります。 - すべての組み合わせに対して集約した公開鍵を使う方法 すべての葉が k 個の公開鍵によって構成される木を構成するのではなく、MuSig を利用してすべての葉が k 個の鍵を集約した一つの鍵で構成される木を構成する方法もあります。このアプローチはより効率的ですが、(ひとつの) 署名を作成するのに協調して 3 ラウンドの対話的な署名プロトコルを実行する必要があります。
- ネイティブ Schnorr 閾値署名 検証可能な秘密分散法を利用することで、閾値署名を用いたマルチシグポリシーを実現することもできます。これによって出力および入力は単一鍵による支払いと区別できないものになりますが、送金先アドレスを決定する前に対話的なプロトコル (およびそれに関連したバックアップ手続き) が必要となるという代償を支払う必要があります。
- 一つの
- ^ 未知の公開鍵タイプにより、ソフトフォークによって新しい署名検証ルールを追加することができます。ソフトフォークでは合格、またはスクリプトが失敗しすぐさま終了するといったいずれかの実際の署名検証が追加されるでしょう。こうすることで、新しい
SIGHASHモードが追加できたり、NOINPUT でタグ付けされた公開鍵や、署名検証のための taproot 内部鍵で置換できる公開鍵定数などを追加することができます。 - ^ 署名メッセージが key_version に対してコミットされるのはなぜですか？ これは未知の公開鍵タイプを定義する将来の拡張において、署名が一つの鍵タイプから別の鍵タイプへと移動できないことを保証します。
- ^ 署名メッセージが最後に実行された
OP_CODESEPARATORの OP コードの位置を含むのはなぜですか？ スクリプトの実行されたパスに対して署名するためにOP_CODESEPARATORが継続的に使用できるようになるからです。なぜならcodeseparator_positionはハッシュへの最後の入力であり、SHA256 の midstate は一つのスクリプトの中の複数のOP_CODESEPARATORに対して効率的にキャッシュできるからです。一方で、BIP143 でのOP_CODESEPARATORの利用の仕方だと、最後に実行されたOP_CODESEPARATOR以降に実行されたスクリプトにのみコミットしますので、スクリプトの不必要な再ハッシュが必要となります。一つのOP_CODESEPARATORの既知のユースケースとして、二つのコードブランチの間で最初の公開鍵を共有することで二番目の公開鍵のプッシュを節約するといったものは、それぞれのブランチを分離された taproot 葉に移動することで、より安く表現できる可能性が高いことに注意してください。 - ^ スクリプトサイズの制限がもはや必要ないのはなぜですか？ 署名ハッシュに
scriptCodeは直接的に含まれないため (事前計算可能な tapleaf ハッシュを通して間接的にのみ含まれます)、署名検証に費やされる CPU 時間は実行されるスクリプトのサイズにもはや比例しないためです。 - ^ OP コードの数に対する制限がもはや必要ないのはなぜですか？ OP コード制限は、実行時にデータ構造が無限に膨らんでしまうのを防ぐのに限られた効果しかありません (これはメモリの利用の仕方および、このような構造のサイズに対して比例して時間が増えることによります)。スタックおよびオルトスタックのサイズは既に非依存的に制限されています。こちらで提案されているものや、こちらで実装されているように、
OP_IF、OP_NOTIF、OP_ELSE、およびOP_ENDIFを用いた O(1) のロジックを使うことで、どちらか一方のみしか防ぐことができません。 - ^ Tapscript の sigop 制限 署名 OP コード制限は、過剰に多数の署名命令があるために検証が遅くなるようなスクリプトから守るために存在します。Tapscript においては、BIP141 や旧来の sigop 制限に対して署名 OP コードの数はカウントされません。従来の sigop 制限は、重量に追加して二番目の拘束条件となってしまうため、ブロック生成時のトランザクション選択を不必要に難しくしてしまいます。一方で、tapscript の署名 OP コードの数は witness の重量によって制限されます。さらに、制限はブロックではなくトランザクションの入力に対してのみ適用され、実際に実行された署名 OP コードのみカウントされます。Tapscript の実行においては、50 witness 重量単位に対して一つの署名 OP コードおよび、一回の自由な署名 OP コードを許可します。
- ^ Sigop 制限のパラメータ選択 通常の witness は、その重量は公開鍵および、それぞれ 33 + 65 の重量単位 (1 重量単位を持つ
CCompactSizeタグを含みます) をもつ (SIGHASH_ALLの) 署名ペアで構成される重量を持ちますので、この制限に影響を受けません。署名自体の重量は 65 ないし 66 の重量単位を持ちますので、公開鍵が再利用された場合にもこれは成り立ちます。重量あたりの 50 という sigop 係数は、BIP141 のブロック制限の率に対応しています: 4 メガ重量単位を 80,000 sigop で割ったものです。制限によって許可された「自由な」署名 OP コードはトランザクションの入力の非 witness 領域の重量に対応したものです。 - ^ 署名 OP コードのみがバジェットに対してカウントされ、例えばハッシュ OP コードやその他の高価な命令がカウントされないのはなぜですか？ スクリプトの検証の際に witness バイトあたりの CPU コストは、署名検証 OP コード (50 WU/sigop の制限が使われる) が最大の密度で含まれているスクリプトを検証する際のものは、既にハッシュ OP コード (520 バイトのスタック要素制限が使われる) や
OP_ROLL(1000 スタック要素制限が使われる) を含む他の OP コードで詰められたスクリプトのものに非常に近くなっています。つまり、この構成は非常に柔軟で、CHECKSIGFROMSTACKなどの新しい署名 OP コードを追加し、ソフトフォークによって制限に対してカウントすることができます。将来的に、通常のスクリプトコストを変更するような新しい OP コードが導入された場合においても、意味のないデータを witness に詰め込む必要はありません。その代わり、taproot annex を用いることで、実際の witness サイズを増やすことなく witness に対して重量を追加することができます。
このドキュメントは多数の議論の結果およびいくつかの人たちによる貢献を含みます。著者は有益なフィードバックおよびレビューをいただいたすべての人たちに感謝いたします。これには構造的レビューに参加いただいた方を含みます。