Develop with pleasure!

福岡でCloudとかBlockchainとか。

TaprootのアウトプットのスクリプトTapscriptに適用される新しいスクリプトルールを定義したBIP-342

TaprootのBIPドラフトについて書いた↓

techmedia-think.hatenablog.com

ので、続いてそのTaprootのアウトプットで使用されるスクリプト = Tapscriptに適用されるスクリプトの新しいルールの提案BIP-342↓について見てみる。

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

主な変更点は

  • OP_CHECKSIGOP_CHECKSIGVERIFYがECDSAの代わりにSchnorr署名の検証をするようになる。
  • OP_CHECKMULTISIGOP_CHECKMULTISIGVERIFYは無効化され、新しいopcode OP_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_IFOP_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の使用としてマークされている。

そのようなインプットの検証は、指定された順序で以下の手順を実行することと同等である必要がある。

  1. インプットがBIP 141もしくはBIP 341に対して無効な場合、失敗する。
  2. BIP 341で定義されているスクリプト(つまりオプションのannexを削除後の最後から2番めのwitnessスタック要素)は、tapscriptと呼ばれ、1つずつopcodeにデコードされる。
    1. opcode番号80, 98, 126-129, 131-134, 137-138, 141-142, 149-153, 187-254が検出された場合、検証は成功する(以下のルールはいずれも適用されない)。tapscriptの後のバイトがそれ以外でデコードに失敗したとしても、これは適用される。これらのopcodeはOP_SUCCESS80...OP_SUCCESS254に名前が変更され、まとめてOP_SUCCESSxと総称される。
    2. 任意のpush opcodeのデコードに失敗すると、tapscriptの終わりを超えて広がるため、失敗する。
  3. BIP 341で定義されている初期スタックが(つまり、オプションのannexおよび最後から2つのスタック要素を両方削除した後のwitnessスタックのサイズ)、リソース制限(スタックサイズ、スタック内の要素のサイズ、「リソース制限参照」)に違反する場合、失敗する。このチェックはOP_SUCCESSxを使ってバイパスできることに注意すること。
  4. tapscriptは、初期スタックをインプットとして次のセクションのルールに従って実行される。
    1. 何らかの理由で実行に失敗した場合、失敗する。
    2. 実行した結果、スタック上の要素が正確に1つで、それがCastToBool()でtrueとして評価される要素以外が発生した場合、失敗する。
  5. 失敗すること無くこのステップに到達すると、検証は成功となる。

スクリプトの実行

tapscriptの実行ルールは、BIP 65やBIP 112で定義されているOP_CHECKLOCKTIMEVERIFYOP_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参照)で動作するように変更され、新しいopcode OP_CHECKSIGADDが追加された。
    • opcode 186 (0xba)がOP_CHECKSIGADDという名前になる。

署名opcodeのルール

以下のルールがOP_CHECKSIGおよびOP_CHECKSIGVERIFYOP_CHECKSIGADDに適用される。

  • OP_CHECKSIGVERIFYおよびOP_CHECKSIGの場合、公開鍵(1番上の要素)と署名(上から2番めの要素)がスタックからポップされる。
    • スタックの要素が2要素未満の場合、スクリプトは失敗し直ちに終了しなければならない。
  • OP_CHECKSIGADDの場合、公開鍵(1番上の要素)とCScriptNum n(上から2番めの要素)および署名(上から3番めの要素)がスタックからポップされる。
    • スタックの要素が3要素未満の場合、スクリプトは失敗し直ちに終了しなければならない。
    • nが4バイトより大きい場合、スクリプトは失敗し直ちに終了しなければならない。
  • 公開鍵のサイズが0の場合、スクリプトは失敗し直ちに終了しなければならない。
  • 公開鍵のサイズが32バイトの場合、BIP 340の公開鍵とみなされる。
    • 署名が空のベクターでない場合、公開鍵に対して、検証される(以下のセクション参照)。検証に失敗するとスクリプトは失敗し直ちに終了しなければならない。
  • 公開鍵のサイズが0でも32バイトでもない場合、公開鍵は未知の公開鍵タイプであり、実際の署名検証は適用されない。署名opcodeのスクリプト実行中、署名検証が成功したとみなされることを除き、既知の公開鍵タイプと同じように動作する。
  • 公開鍵のタイプに関係なく、この手順の前にスクリプトが失敗し終了しなかった場合は:
    • 署名が空のベクターの場合
      • OP_CHECKSIGVERIFYの場合、スクリプトは失敗し直ちに終了しなければならない。
      • OP_CHECKSIGの場合、空のベクターがスタックにプッシュされ、次のopcodeへ実行が続く。
      • OP_CHECKSIGADDの場合、値nCScriptNumがスタックにプッシュされ、次のopcopdeへ実行が続く。
    • 署名が空のベクターでなく、sigopsバジェットにカウントされる
      • OP_CHECKSIGVERIFYの場合、スタックのこれ以上の変更なく実行は継続する。
      • OP_CHECKSIGの場合、1バイトの値0x01がスタック上にプッシュされる。
      • OP_CHECKSIGADDの場合、値n + 1CScriptNumがスタックにプッシュされる。

署名検証

公開鍵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と同じだ。

  1. 署名メッセージにはtapscript固有のデータkey_versionが含まれる。
  2. 署名メッセージは、scriptCodeではなくleaf versionとスクリプトを含むtapleaf_hashを介して実行されたスクリプトにコミットする。これはこのコミットメントがOP_CODESEPARATORの影響を受けないことを意味する。
  3. 署名メッセージには、最後に実行された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バイトの制限は残る。

論拠

  1. OP_SUCCESSxOP_SUCCESSxスクリプトシステムのアップグレードのための仕組み。ソフトフォークによって意味が定義される前にOP_SUCCESSxを使用することは安全ではなく、資金消失に繋がる。スクリプトOP_SUCCESSxを含めると無条件にコインが渡される。さまざまなエッジケースを指定する際の難しさを回避するため、スクリプト実行ルールに先行する。例えば、入力スタックが1000要素を超えるスクリプト内のOP_SUCCESSx、もしくは署名opcodeが多すぎた後のOP_SUCCESSxOP_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_SUCCESSxopcodeをプレフィックスとして使用してまったく新しいスクリプト言語を導入することができたりする。
  2. OP_CHECKMULTISIGとOP_CHECKMULTISIGVERIFYが無効になり、OP_SUCCESSxにならないのはなぜ?:これはTaprootで誤ってOP_CHECKMULTISIGを使い続けている人がすぐに問題に気付くようにするための予防策だ。また、コンテキスト依存になるスクリプトの逆アセンブラの複雑さを回避する。
  3. MINIMALIFをコンセンサスにするのはなぜ? こうすることで、スタックからブランチ情報を取得するmalleabilityの無いコードを書くのがかなり簡単になる。
  4. OP_CHECKSIGADD このopcodeはバッチ検証とは互換性のないOP_CHECKMULTISIGのようなopcodeが無くなるのをカバーするために追加されている。OP_CHECKSIGADDは機能的にはOP_ROT OP_SWAP OP_CHECKSIG OP_ADDと同等だが1バイトしか必要ない。OP_ADDCScriptNum関連の振る舞いはすべて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に対応する署名から空のベクトルのいずれか。NUMEQUALNUMEQUALVERIFYに置き換えることで、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閾値署名:マルチシグポリシーは検証可能な秘密分散法を使って閾値署名で実現することもできる。これにより単一の鍵の支払いと区別できない出力と入力が得られるが、送信先のアドレスを決める前に対話型プロトコル(および関連するバックアップ手順)が必要になる。
  6. 未知の公開鍵タイプにより、ソフトフォークを介して新しい署名検証ルールを追加できる。ソフトフォークはスクリプをパスするか失敗させすぐに終了させる実際の署名検証を追加できる。この方法で新しいSIGHASHモードを追加できる他、NOINPUTタグ付き公開鍵や署名検証のためにtaprootの内部キーに置き換え可能な効果鍵定数を追加できる。
  7. 署名メッセージがkey_versionにコミットするのはなぜ?これは未知の公開鍵タイプを定義する将来の拡張のためで、署名をある鍵タイプから別の鍵タイプに移動できないようにする。
  8. 署名メッセージに最後に実行されたOP_CODESEPARATORの位置が含まれるのはなぜ?これにより引き続き、OP_CODESEPARATORを使って、スクリプトの実行パスに署名できる。codeseparator_positionはハッシュへの最後の入力であるため、SHA256 midstateは単一のスクリプト内の複数のOP_CODESEPARATORに対して効率的にキャッシュ可能。対照的にBIP143のOP_CODESEPARATOR処理は最後に実行されたOP_CODESEPARATOR以降からのみ実行されたスクリプトにコミットするため、スクリプトの不必要な再ハッシュが必要になる。既知のOP_CODESEPARATORユースケースは、2つのコードブランチ間で最初のプッシュを共有することで2つめの公開鍵のプッシュを保存する場合、各ブランチを異なるtaprootリーフに移動することでより安価に表現出来る可能性が高いことに注意。
  9. スクリプトのサイズ制限が不要になったのはなぜ?scriptCodeがsighashに直接含まれないため、署名チェックに使われるCPU時間は実行されるスクリプトのサイズに比例しなくなる。
  10. opcode数の制限が不要になったのはなぜ?opcodeの制限は、実行中にデータ構造が無制限に大きくなるのを防ぐことができる範囲でのみ役立つ(メモリ使用量と、それらの構造のサイズに比例して大きくなる可能性があるため)。スタックとアルトスタックのサイズは既に独立して制限されている。ここで実装されているようにOP_IF、OP_NOTIF、OP_ELSE、およびOP_ENDIFに対してO(1)ロジックを使用することにより、他の唯一のインスタンスも回避できる。
  11. tapscriptのsigops制限:署名opcodeの制限は、過度に多くの署名操作のために検証が遅いスクリプトから保護するためのもの。tapscriptでは、署名opcodeの数はBIP 141または従来のsigop制限にカウントはされない。古いsigop制限により、ブロック構築におけるトランザクション選択は、weightに加えて2つめの制約であるため、不必要に難しくなる。代わりにtapscript署名opcodeの数は、witnessのweightによってのみ制限される。さらに、制限はブロックでっはなくトランザクションインプットに適用され、実際に実行された署名opcodeのみがカウントされる。tapscriptの実行により、50 witness weight毎に1つの署名opcodeと1つの無料の署名opcodeが許可される。
  12. sigops制限のパラメータ選択:通常のwitnessはそのweightが公開鍵と(SIGHASH_ALLの)署名のペアで構成されそれぞれ33 + 65 weightの単位であるため、制限の影響を受けない。これは署名のweightが65か66であるため、スクリプト内で公開鍵が再利用される場合にも当てはまる。ただし、この制限により追加のweightが必要になるため、署名(および公開鍵)が重複する異常なスクリプトの手数料は高くなる。sigop係数50あたりのweightはBIP141のブロック制限の比率(4 MB weightを80,000sigopsで割った値)に対応する。トランザクションインプットの非witness部分のweightに対応するため、制限によって許可される無料の署名opcodeが存在する。
  13. なぜ署名opcodeのみが場ジェッドにカウントされ、例えばハッシュopcodeなどの高価な操作はカウントされないのか?署名チェックopcode最大密度で構成されるスクリプトの検証のためのwitnessバイト辺りのCPUコストは、ハッシュopcodeやOP_ROLLを含む他のopcodeが詰め込まれたスクリプトのコストに非常に近いことが分かる。ただし、この構造は非常に柔軟で、CHECKSIGFROMSTACKなどの新しい署名opcodeを追加して、ソフトフォークを介して制限にカウントできる。将来、通常のスクリプトコストを変更する新しいopcodeが導入されたとしても、witnessに無意味なデータを詰め込む必要はない。代わりに、taproot annexを利用して、実際のwitnessのサイズを増やすこと無くwitnessにweightを追加できる。