TaprootのBIPドラフトについて書いた↓
techmedia-think.hatenablog.com
ので、続いてそのTaprootのアウトプットで使用されるスクリプト = Tapscriptに適用されるスクリプトの新しいルールの提案BIP-342↓について見てみる。
https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki
主な変更点は
OP_CHECKSIG
、OP_CHECKSIGVERIFY
がECDSAの代わりにSchnorr署名の検証をするようになる。OP_CHECKMULTISIG
、OP_CHECKMULTISIGVERIFY
は無効化され、新しいopcodeOP_CHECKSIGADD
を使ったマルチシグポリシーを追加。- 現在未使用のopcode(80, 98, 126-129, 131-134, 137-138, 141-142, 149-153, 187-254)に
OP_SUCCESS80
...OP_SUCCESS254
を割り当て、OP_SUCCESS
系のopcodeを追加する。OP_SUCCESS
が実行されるとスクリプトはその時点で成功する。これは将来のソフトフォークで新しいopcodeを割り当てるのに使われる。従来OP_NOP
系のopcodeが拡張用に用意されてたけど、これだとスタックから要素をプッシュができないなどの制約があるので、より柔軟にopcodeを割り当て可能なOP_SUCCESS
を利用可能にすると。 - 署名の際に用いるメッセージであるトランザクションダイジェストの計算方法の変更
- 署名opcodeの制限がsigopから、トランザクションインプット単位のwitnessのweightベースの制限に変更。
- MINIMALIFルールがコンセンサスとして適用。MINIMALIFルールというのは、
OP_IF
やOP_NOTIF
がスタック要素からTrue/Falseを判定するが、その際のmalleabilityを排除するため、その要素は空ベクターか0x01
のどちらかでなければならないというルール。
以下、BIPドラフトの内容(追記:2020.03.19時点の内容で以下更新)。
イントロダクション
概要
BIP-341の下での最初のスクリプトシステムのセマンティクスを規定している。
動機
BIP-341はスクリプトの構造のみを改善することを提案しているが、その目標のいくつかはスクリプト言語自体の中の特定のopcodeのセマンティクスと両立しない。これらを別々の改善で扱うことは可能だが、BIP-341自体と同時に対応されない限り、それらの影響は保証されない。
具体的には、目標はSchnorr署名、バッチ検証、およびsignature hashの改善を、スクリプトシステムを使用するコインの使用にも利用できるようにすることだ。
設計
これらの目標を達成するために、署名opcode、OP_CHECKSIG
およびOP_CHECKSIGVERIFY
は、BIP340で指定されたSchnorr署名を検証し、BIP-341の共通メッセージ計算に基づく署名メッセージアルゴリズムを使用する。tapscriptの署名メッセージは、OP_CODESEPARATOR
の処理を単純化し、より効率的にする。
非効率な、OP_CHECKMULTISIG
およびOP_CHECKMULTISIGVERIFY
opcodeは無効になる。代わりに新しいopcode OP_CHECKSIGADD
が導入され、バッチ検証可能な方法で同じマルチシグポリシーを作成できるようになる。Tapscriptは、トランザクション weightを使用した複雑なやりとりを修正するための新しいよりシンプルな署名opcodeの制限を使用する。さらに潜在的なmalleability ベクトルはMINIMALIF
を必要とすることで排除する。
Tapscriptは、例えば新しいhash_types
や署名アルゴリズムを追加するために、未知のキータイプを定義することでソフトフォークを介してアップグレードできる。さらに新しいTapscript OP_SUCCESS
opcodeを使用すると、OP_NOP
を使用するよりもクリーンに新しいopcodeを導入できる。
仕様
以下のルールは、以下のすべての条件があてはまるトランザクションインプットを検証する場合にのみ適用される。
- 使用するアウトプットはsegregated witnessのアウトプットである(すなわち、scriptPubKeyはBIP 141で定義されているようなwitness programを含む)。
- そのアウトプットはBIP-341で定義されているtaprootアウトプットである(つまり、witness version 1で、witness programは32バイト。ただしP2SHでラップされていないこと)。
- BIP-341で定義されたスクリプトパスを使用している(つまり、witnessスタックからオプションのannexを削除後、2つ以上のスタック要素が残ること)。
- リーフバージョンは
0xc0
(オプションのannexを削除後、最後のwitness要素の先頭バイトが0xc0
もしくは0xc1
である)、つまりTapscriptの使用としてマークされている。
そのようなインプットの検証は、指定された順序で以下の手順を実行することと同等である必要がある。
- インプットがBIP 141もしくはBIP 341に対して無効な場合、失敗する。
- BIP 341で定義されているスクリプト(つまりオプションのannexを削除後の最後から2番めのwitnessスタック要素)は、tapscriptと呼ばれ、1つずつopcodeにデコードされる。
- opcode番号80, 98, 126-129, 131-134, 137-138, 141-142, 149-153, 187-254が検出された場合、検証は成功する(以下のルールはいずれも適用されない)。tapscriptの後のバイトがそれ以外でデコードに失敗したとしても、これは適用される。これらのopcodeは
OP_SUCCESS80
...OP_SUCCESS254
に名前が変更され、まとめてOP_SUCCESSx
と総称される。 - 任意のpush opcodeのデコードに失敗すると、tapscriptの終わりを超えて広がるため、失敗する。
- opcode番号80, 98, 126-129, 131-134, 137-138, 141-142, 149-153, 187-254が検出された場合、検証は成功する(以下のルールはいずれも適用されない)。tapscriptの後のバイトがそれ以外でデコードに失敗したとしても、これは適用される。これらのopcodeは
- BIP 341で定義されている初期スタックが(つまり、オプションのannexおよび最後から2つのスタック要素を両方削除した後のwitnessスタックのサイズ)、リソース制限(スタックサイズ、スタック内の要素のサイズ、「リソース制限参照」)に違反する場合、失敗する。このチェックは
OP_SUCCESSx
を使ってバイパスできることに注意すること。 - tapscriptは、初期スタックをインプットとして次のセクションのルールに従って実行される。
- 何らかの理由で実行に失敗した場合、失敗する。
- 実行した結果、スタック上の要素が正確に1つで、それが
CastToBool()
でtrueとして評価される要素以外が発生した場合、失敗する。
- 失敗すること無くこのステップに到達すると、検証は成功となる。
スクリプトの実行
tapscriptの実行ルールは、BIP 65やBIP 112で定義されているOP_CHECKLOCKTIMEVERIFY
やOP_CHECKSEQUENCEVERIFY
opcodeを含めBIP 141に準拠したP2WSHルールがベースになっているが、以下の点が変更されている。
- 無効化されたスクリプトopcode 次のscript opcodeはtapscriptでは無効になっている:
OP_CHECKMULTISIG
およびOP_CHECKMULTISIGVERIFY
。無効化されたopcodeは、実行されるとすぐに終了し、未実行ブランチで見つかっても無視するという点でOP_RETURN
と同じように動作する。 - コンセンサスによるMINIMALIFの強制 MINIMALIFルールは、P2WSHの標準ルールに過ぎないが、tapscriptではコンセンサスとして適用される。つまり、
OP_IF
およびOP_NOTIF
opcodeへの入力引数は、厳密に0(空のベクター)または1(値1の1バイトのベクター)でなければならないことを意味する。 - OP_SUCCESSx opcode 上記のようにいくつかのopcodeが
OP_SUCCESSx
という名前に変更され、無条件にスクリプトを有効とするようになる。 - 署名opcode
OP_CHECKSIG
およびOP_CHECKSIGVERIFY
は、ECDSAに代わってSchnorrの公開鍵および署名(bip-schnorr参照)で動作するように変更され、新しいopcodeOP_CHECKSIGADD
が追加された。- opcode 186 (
0xba
)がOP_CHECKSIGADD
という名前になる。
- opcode 186 (
署名opcodeのルール
以下のルールがOP_CHECKSIG
およびOP_CHECKSIGVERIFY
、OP_CHECKSIGADD
に適用される。
OP_CHECKSIGVERIFY
およびOP_CHECKSIG
の場合、公開鍵(1番上の要素)と署名(上から2番めの要素)がスタックからポップされる。- スタックの要素が2要素未満の場合、スクリプトは失敗し直ちに終了しなければならない。
OP_CHECKSIGADD
の場合、公開鍵(1番上の要素)とCScriptNum
n
(上から2番めの要素)および署名(上から3番めの要素)がスタックからポップされる。- 公開鍵のサイズが0の場合、スクリプトは失敗し直ちに終了しなければならない。
- 公開鍵のサイズが32バイトの場合、BIP 340の公開鍵とみなされる。
- 公開鍵のサイズが0でも32バイトでもない場合、公開鍵は未知の公開鍵タイプであり、実際の署名検証は適用されない。署名opcodeのスクリプト実行中、署名検証が成功したとみなされることを除き、既知の公開鍵タイプと同じように動作する。
- 公開鍵のタイプに関係なく、この手順の前にスクリプトが失敗し終了しなかった場合は:
署名検証
公開鍵pで署名sigを検証するには、
- 次のデータの連結で構成されるtapscriptメッセージ拡張extを計算する。
- tapleaf_hash(32):BIP 341で定義されているtapleaf hash
- key_version(1):tapscript内の署名opcode実行における公開鍵の現在のバージョンを表す定数値0x00。
- codesep_pos(4):現在実行中の署名opcodeの前に最後に実行された
OP_CODESEPARATOR
の位置でリトルエンディアンで表現(OP_CODESEPARATOR
が実行されていない場合は0xffffffff
)。スクリプト内の最初のopcodeの位置は0。マルチバイトのpush opcodeはプッシュされるデータのサイズに関係なく1 opcodeとしてカウントされる。
- sigの長さが64バイトの場合、
Verify(p, hashTapSigHash(0x00 || SigMsg(0x00, 1) || ext), sig)
の結果を返す。このVerifyはBIP 340に定義されている。 - sigの長さが65バイトの場合、sig[64] ≠ 0x00で、
Verify(p, hashTapSighash(0x00 || SigMsg(sig[64], 1) || ext), sig[0:64])
の結果を変えす。 - それ以外の場合、失敗。
要約すると署名検証のセマンティクスは以下の除いてBIP 340と同じだ。
- 署名メッセージにはtapscript固有のデータ
key_version
が含まれる。 - 署名メッセージは、scriptCodeではなくleaf versionとスクリプトを含むtapleaf_hashを介して実行されたスクリプトにコミットする。これはこのコミットメントが
OP_CODESEPARATOR
の影響を受けないことを意味する。 - 署名メッセージには、最後に実行された
OP_CODESEPARATOR
のopcode位置が含まれる。
リソース制限
多数のopcodeのセマンティクスを変更することに加えて、リソース制限にもいくつかの変更がある。
- スクリプトサイズの制限:最大スクリプトサイズ10000バイトは適用されない。サイズはブロックのweight制限によってのみ暗黙的に制限される。
- 非プッシュopcodeの制限:スクリプトあたり201の非プッシュopcodeの最大数制限は適用されない。
- Sigops制限:tapscript内のsigopsはブロック全体の制限である80000にはカウントされない。代わりに、スクリプト毎のsigopsバジェットがある。バジェットは
50 + (CCompactSizeプレフィックスを含む)トランザクションインプットwitnessの合計シリアライズサイズ
。空でない署名を使って署名opcode(OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKSIGADD)を実行するとバジェットが50減る。バジェットが0未満になるとスクリイプとはすぐに失敗する。未知の公開鍵タイプと空で無い署名を持つ署名opcodeもカウントされる。 - スタックとアルトスタックのカウント制限:全てのopcode実行後のスタックとアルトスタックの要素の最大数が1000の既存の制限は残り、初期スタックのサイズにも適用されるよう拡張される。
- スタック要素サイズの制限:初期スタックとプッシュopcodeの両方で、スタック要素あたり最大520バイトの制限は残る。
論拠
- OP_SUCCESSx:
OP_SUCCESSx
はスクリプトシステムのアップグレードのための仕組み。ソフトフォークによって意味が定義される前にOP_SUCCESSx
を使用することは安全ではなく、資金消失に繋がる。スクリプトにOP_SUCCESSx
を含めると無条件にコインが渡される。さまざまなエッジケースを指定する際の難しさを回避するため、スクリプト実行ルールに先行する。例えば、入力スタックが1000要素を超えるスクリプト内のOP_SUCCESSx
、もしくは署名opcodeが多すぎた後のOP_SUCCESSx
、OP_ENDIF
が内条件付きスクリプトなど。スクリプト内のどこかにOP_SUCCESSx
が存在するだけで、このようなケースのパスが保証される。OP_SUCCESSx
は初期のBitcoin(v0.1からv0.3.5まで)のOP_RETURNに似ている。元々のOP_RETURNはスクリプトの実行を即座に終了し、終了した時点で一番上のスタック要素に基づいて成功、失敗を返す。これは、scriptSigにOP_RETURNを配置することで無条件に第三者が窃盗できてしまうので、元々のBitcoinプロトコルの主な設計上の欠陥の1つだった。OP_SUCCESSx
はスクリプトの一部であり(したがって、taprootアウトプットによってコミットされる)コインの所有者の同意を意味し、第三者が検証プロセスにOP_SUCCESSx
を挿入することはできないため、これは本提案では懸念事項にならない。OP_SUCCESSx
はさまざまなアップグレードの可能性に使用できる。OP_SUCCESSx
は、ソフトフォークを介して機能的なopcodeに変換できる。スタックへのread-onlyアクセスのみを持つOP_NOP系のopcodeとは異なり、OP_SUCCESSx
はスタックに書き込むこともできる。OP_SUCCESSx
を含むスクリプトに対するルール変更は、有効なスクリプトのみを無効なスクリプトに変えることができ、これはソフトフォークで常に達成可能だ。OP_SUCCESSx
は初期スタックやプッシュopcodeのサイズチェックに先行するため、520バイトを超えるスタック要素を必要とするOP_SUCCESSx
から派生したopcodeは、ソフトフォークの制限を引き上げる可能性がある。OP_SUCCESSx
は、既存のopcodeの動作を再定義し、新しいopcodeと連携できるようにすることもできる。例えば、OP_SUCCESSx
から派生したopcodeが64bit整数と機能する場合、同じスクリプト内の算術opcodeでも同じことが可能になる。OP_SUCCESSx
により解析不能なスクリプトが渡される可能性があるため、マルチバイトopcodeを導入したり、特定のOP_SUCCESSx
opcodeをプレフィックスとして使用してまったく新しいスクリプト言語を導入することができたりする。
- OP_CHECKMULTISIGとOP_CHECKMULTISIGVERIFYが無効になり、OP_SUCCESSxにならないのはなぜ?:これはTaprootで誤って
OP_CHECKMULTISIG
を使い続けている人がすぐに問題に気付くようにするための予防策だ。また、コンテキスト依存になるスクリプトの逆アセンブラの複雑さを回避する。 - MINIMALIFをコンセンサスにするのはなぜ? こうすることで、スタックからブランチ情報を取得するmalleabilityの無いコードを書くのがかなり簡単になる。
- OP_CHECKSIGADD このopcodeはバッチ検証とは互換性のない
OP_CHECKMULTISIG
のようなopcodeが無くなるのをカバーするために追加されている。OP_CHECKSIGADD
は機能的にはOP_ROT OP_SWAP OP_CHECKSIG OP_ADD
と同等だが1バイトしか必要ない。OP_ADD
のCScriptNum
関連の振る舞いはすべて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
に対応する署名から空のベクトルのいずれか。NUMEQUAL
をNUMEQUALVERIFY
に置き換えることで、CHECKMULTISIGVERIFY
スクリプトと同様に変換できる。このアプローチには、既存のOP_CHECKMULTISIG
ベーススクリプトと非常によく似た特性がある。 - 全ての組み合わせのk-of-kスクリプトを使用する:k-of-nポリシーは、スクリプトをマークルツリーのいくつかのリーフに分割し、それぞれが
<pubkey_1> CHECKSIGVERIFY ... <pubkey_(n-1)> CHECKSIGVERIFY <pubkey_n> CHECKSIG
を使ってk-of-kポリシーを実装することで実装できる。これは参加する公開鍵のみが公開されるため、以前のアプローチよりもプライバシー上の理由で望ましい場合がある。またkが小さい値の方が費用対効果が高い。さらにここでの署名は、ブランチにコミットする。つまり署名者は他の署名者が参加することを認識するか、ツリーのリーフ毎に署名を作成する必要がある。 - 全ての組み合わせに集約公開鍵を使用する:全てのリーフがk個の公開鍵で構成されるツリーを作成する代わりに、MuSigを使って各リーフはk個の鍵の単一の集約鍵を含むツリーを構築できる。このアプローチははるかに効率的だが、(単一の)署名を共同で生成するため3ラウンドの対話型署名プロトコルを必要とする。
- ネイティブのSchnorr閾値署名:マルチシグポリシーは検証可能な秘密分散法を使って閾値署名で実現することもできる。これにより単一の鍵の支払いと区別できない出力と入力が得られるが、送信先のアドレスを決める前に対話型プロトコル(および関連するバックアップ手順)が必要になる。
- 単一の
- 未知の公開鍵タイプにより、ソフトフォークを介して新しい署名検証ルールを追加できる。ソフトフォークはスクリプをパスするか失敗させすぐに終了させる実際の署名検証を追加できる。この方法で新しいSIGHASHモードを追加できる他、NOINPUTタグ付き公開鍵や署名検証のためにtaprootの内部キーに置き換え可能な効果鍵定数を追加できる。
- 署名メッセージがkey_versionにコミットするのはなぜ?これは未知の公開鍵タイプを定義する将来の拡張のためで、署名をある鍵タイプから別の鍵タイプに移動できないようにする。
- 署名メッセージに最後に実行されたOP_CODESEPARATORの位置が含まれるのはなぜ?これにより引き続き、
OP_CODESEPARATOR
を使って、スクリプトの実行パスに署名できる。codeseparator_positionはハッシュへの最後の入力であるため、SHA256 midstateは単一のスクリプト内の複数のOP_CODESEPARATOR
に対して効率的にキャッシュ可能。対照的にBIP143のOP_CODESEPARATOR処理は最後に実行されたOP_CODESEPARATOR以降からのみ実行されたスクリプトにコミットするため、スクリプトの不必要な再ハッシュが必要になる。既知のOP_CODESEPARATOR
のユースケースは、2つのコードブランチ間で最初のプッシュを共有することで2つめの公開鍵のプッシュを保存する場合、各ブランチを異なるtaprootリーフに移動することでより安価に表現出来る可能性が高いことに注意。 - スクリプトのサイズ制限が不要になったのはなぜ?scriptCodeがsighashに直接含まれないため、署名チェックに使われるCPU時間は実行されるスクリプトのサイズに比例しなくなる。
- opcode数の制限が不要になったのはなぜ?opcodeの制限は、実行中にデータ構造が無制限に大きくなるのを防ぐことができる範囲でのみ役立つ(メモリ使用量と、それらの構造のサイズに比例して大きくなる可能性があるため)。スタックとアルトスタックのサイズは既に独立して制限されている。ここで実装されているようにOP_IF、OP_NOTIF、OP_ELSE、およびOP_ENDIFに対してO(1)ロジックを使用することにより、他の唯一のインスタンスも回避できる。
- tapscriptのsigops制限:署名opcodeの制限は、過度に多くの署名操作のために検証が遅いスクリプトから保護するためのもの。tapscriptでは、署名opcodeの数はBIP 141または従来のsigop制限にカウントはされない。古いsigop制限により、ブロック構築におけるトランザクション選択は、weightに加えて2つめの制約であるため、不必要に難しくなる。代わりにtapscript署名opcodeの数は、witnessのweightによってのみ制限される。さらに、制限はブロックでっはなくトランザクションインプットに適用され、実際に実行された署名opcodeのみがカウントされる。tapscriptの実行により、50 witness weight毎に1つの署名opcodeと1つの無料の署名opcodeが許可される。
- sigops制限のパラメータ選択:通常のwitnessはそのweightが公開鍵と(SIGHASH_ALLの)署名のペアで構成されそれぞれ33 + 65 weightの単位であるため、制限の影響を受けない。これは署名のweightが65か66であるため、スクリプト内で公開鍵が再利用される場合にも当てはまる。ただし、この制限により追加のweightが必要になるため、署名(および公開鍵)が重複する異常なスクリプトの手数料は高くなる。sigop係数50あたりのweightはBIP141のブロック制限の比率(4 MB weightを80,000sigopsで割った値)に対応する。トランザクションインプットの非witness部分のweightに対応するため、制限によって許可される無料の署名opcodeが存在する。
- なぜ署名opcodeのみが場ジェッドにカウントされ、例えばハッシュopcodeなどの高価な操作はカウントされないのか?署名チェックopcode最大密度で構成されるスクリプトの検証のためのwitnessバイト辺りのCPUコストは、ハッシュopcodeやOP_ROLLを含む他のopcodeが詰め込まれたスクリプトのコストに非常に近いことが分かる。ただし、この構造は非常に柔軟で、
CHECKSIGFROMSTACK
などの新しい署名opcodeを追加して、ソフトフォークを介して制限にカウントできる。将来、通常のスクリプトコストを変更する新しいopcodeが導入されたとしても、witnessに無意味なデータを詰め込む必要はない。代わりに、taproot annexを利用して、実際のwitnessのサイズを増やすこと無くwitnessにweightを追加できる。