BIP 341 — Taproot: SegWit バージョン 1 の支払いルール

BIP: 341
  Layer: Consensus (soft fork)
  Title: Taproot: SegWit version 1 spending rules
  Authors: 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-0341
  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
              2019-10-09: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-October/017378.html [bitcoin-dev] Taproot updates
  Requires: 340

序論

概要

本文書は、Taproot・シュノア署名・マークルブランチに基づく支払いルールを備えた、新たな SegWit バージョン 1 のアウトプット型を提案する。

著作権

本文書は 3 条項 BSD ライセンスの下に提供される。

動機

本提案は、新たなセキュリティ仮定を追加することなく、ビットコインのスクリプティング能力のプライバシー・効率性・柔軟性を改善することを目指す新たなセキュリティ仮定を追加しないとは何を意味するか？ 署名の偽造不可能性は、盗難を防ぐために必要な要件である。少なくともスクリプト実行自体をデジタル署名方式として扱う場合、離散対数問題が困難であるとの前提の下で、偽造不可能性はランダムオラクルモデルにおいて証明可能 (https://github.com/apoelstra/taproot)である。現行スクリプトシステムにおける ECDSA の偽造不可能性に対する証明 (https://nbn-resolving.de/urn:nbn:de:hbz:294-60803)は、その上にさらに非標準的な仮定を必要とする。スクリプトに対するセキュリティが正確に何を意味するかをモデル化することは一般に困難である。ウォレットソフトウェアが用いる方針やプロトコルに依存するためである。。具体的には、トランザクションのアウトプットの使用条件に関する情報が、生成時または使用時にチェーン上にどの程度開示されるかを最小化し、複数のアップグレード機構を追加すると同時に、軽微ながら長年存在する問題をいくつか修正することを狙う。

設計

ビットコインのスクリプティング能力を改善する関連アイデアは、これまでにいくつも提案されてきた。シュノア署名 (BIP340 (https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki))、マークルブランチ (“MAST”、BIP114 (https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki)、BIP117 (https://github.com/bitcoin/bips/blob/master/bip-0117.mediawiki))、新しいシグハッシュモード (BIP118 (https://github.com/bitcoin/bips/blob/master/bip-0118.mediawiki))、CHECKSIGFROMSTACK のような新オペコード、Taproot (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html)、Graftroot (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015700.html)、G’root (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016249.html)、そしてクロスインプット集約 (https://bitcointalk.org/index.php?topic=1377298.0)である。

これらすべてのアイデアを単一の提案にまとめることは、変更範囲が広大となりレビューが困難であり、過程で得られたはずの新たな知見を取りこぼす可能性も高い。さらに、すべてが同程度に成熟しているわけでもない。たとえばクロスインプット集約は、アップグレード機構と複雑に相互作用 (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015838.html)し、その解決策はいまだ流動的 (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-October/016461.html)である。一方で、これらをすべて独立したアップグレードに分割すれば、得られる効率性とプライバシーの利得は減じ、ウォレット事業者やサービス提供者も多数の段階的更新に応じる意欲を失いかねない。したがって、機能性とスコープの肥大化との間でトレードオフに直面する。本設計では、Taproot とマークルブランチがもたらす構造的なスクリプト改善、ならびにそれらを実用的かつ効率的にするために必要な変更に焦点を絞ることで均衡を取る。シグハッシュやオペコードのような項目については、既知の問題への修正は含めるが、副作用なしに独立して追加できる新機能は除外する。

その結果、以下の技術の組合せを採用する。

• マークルブランチ によって、スクリプトの実行されうるあらゆる経路ではなく、実際に実行された部分のみをブロックチェーンに開示すればよくなる。これを実装する既知の様々な機構のうち、マークルツリーをスクリプト構造の一部に直接組み込む方式が空間効率を最大化するため、本提案ではその方式を採用する。
• その上に Taproot を重ねることで、伝統的に分離されていた pay-to-pubkey と pay-to-scripthash の方針を統合でき、すべてのアウトプットを鍵またはスクリプト (任意) のいずれかで使用可能とし、かつ相互に区別不能とすることができる。鍵による支払い経路 (キーパス使用) が使用される限り、スクリプトパスも許可されていたかどうかは開示されず、結果として支払い時の空間節約とスクリプティングプライバシーの増大が得られる。
• Taproot の利点は、ほとんどのアプリケーションにおいて、関係する全当事者の合意によって使用できるアウトプットが用いられる、という前提の下で顕在化する。ここで シュノア 署名が登場する。シュノア署名は鍵集約 (https://eprint.iacr.org/2018/068)を可能にするためである。すなわち、複数の参加者の公開鍵から 1 個の公開鍵を構築でき、その公開鍵に対して署名するには全参加者の協力を要する。このような多者公開鍵および多者署名は、単独当事者の同等物と区別不能である。これにより Taproot 下のほとんどのアプリケーションは、効率的かつプライベートなキーパス使用を用いることができる。これはより複雑な準備プロトコルを代償として、任意の M-of-N 方針に一般化できる。シュノア署名は閾値署名にも対応するためである。
• さらにシュノア署名は バッチ検証 も可能にし、複数の署名を独立に検証するよりも効率的にまとめて検証できるため、本設計のあらゆる部分がこれと互換であるよう注意を払う。
• 上記の変更の結果として未使用ビットが生じる箇所は、将来の拡張 のための機構として予約する。結果として、マークルツリー内のすべてのスクリプトには対応するバージョンが付与され、BIP 341 と互換性を保ちつつ、新たなスクリプトバージョンをソフトフォークで導入できる。加えて、将来のソフトフォークはウィットネス内の現在未使用の annex を活用できる ([[bip-0341.mediawiki#rationale|根拠]] を参照)。
• 署名ハッシュアルゴリズム の中核的な意味は変更しないが、本提案にはいくつかの改善が含まれる。新しい署名ハッシュアルゴリズムは、署名メッセージに金額と scriptPubKey を含めることでオフライン署名デバイスの検証能力の不備を解消し、不要なハッシュ計算を回避し、タグ付きハッシュ を使用し、既定のシグハッシュバイトを定義する。
• 公開鍵を直接アウトプットに含める。これは、公開鍵またはスクリプトのハッシュをアウトプットに格納する典型的な従来構成と対照的である。送信側にとっての費用は同等であり、キーパス使用が選択される場合は全体としてより空間効率が高い。なぜ公開鍵を直接アウトプットに含めるのか？ 典型的な従来構成ではスクリプトや公開鍵のハッシュをアウトプットに格納するが、常に公開鍵が関与する場合にはこれは無駄が多い。バッチ検証を保証するためには公開鍵をすべての検証者が知る必要があり、ハッシュのみをアウトプットとして開示すると、ウィットネスに追加で 32 バイトを乗せることになる。さらに、アウトプットに対して 128 ビットの衝突安全性 (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012198.html)を維持するには、いずれにせよ 256 ビットのハッシュが必要となり、これは公開鍵を直接開示するのと同等のサイズ (したがって送信側にとっての費用も同等) である。公開鍵ハッシュの使用が ECDLP の崩壊や量子コンピューターに対する保護になるとしばしば言われるが、この保護はせいぜい非常に弱い。トランザクションは承認中は保護されず、また通貨供給量の非常に大きな部分 (https://web.archive.org/web/20220531184542/https://twitter.com/pwuille/status/1108085284862713856)はそもそもそのような保護下にない。こうしたシステムへの実質的な耐性は、異なる暗号学的仮定に依拠することで導入可能であるが、本提案は安全性モデルを変えない改善に焦点を当てる。

非形式的に述べると、結果として得られる設計は次のとおりである。新しいウィットネスバージョン (バージョン 1) が追加され、そのプログラムは点 Q の 32 バイト符号化からなる。Q は、公開鍵 P と、葉がバージョン番号とスクリプトからなるマークルツリーのルート m について、P + hash(P||m)G として計算される。これらのアウトプットは、Q に対する署名を提供することで直接使用できるか、または P・スクリプトと葉バージョン・スクリプトを充足するインプット・Q がその葉にコミットしていることを証明するマークルパス、を開示することで間接的に使用できる。本構成中のすべてのハッシュ (P から Q を計算するためのハッシュ・マークルツリーの内部節のハッシュ・使用される署名ハッシュ) はドメイン分離を保証するためタグ付けされている。

仕様

本節では Taproot のコンセンサスルールを規定する。妥当性は除外によって定義される。すなわち、失敗を示す条件が存在しなければ、ブロックまたはトランザクションは妥当である。

以下の記法は [[bip-0340.mediawiki#design|BIP340]] のそれに従う。これには SHA256(SHA256(tag) || SHA256(tag) || x) を表す hash_tag(x) 記法が含まれる。著者らの知る限り、ビットコインにおける既存の SHA256 の用法で、2 つの単独 SHA256 出力で始まるメッセージを与えるものは存在せず、hash_tag と他のハッシュとの衝突は極めて起こりにくい。

スクリプト検証ルール

Taproot のアウトプットは、バージョン番号 1 と 32 バイトのウィットネスプログラムを持つネイティブ SegWit アウトプット (BIP141 (https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki) を参照) である。 以下のルールは、そのようなアウトプットが使用される場合にのみ適用される。それ以外のアウトプット、たとえば長さが 32 バイト以外のバージョン 1 アウトプットや、P2SH ラップされたバージョン 1 アウトプットなぜ P2SH ラップは対応されないのか？ P2SH ラップされたアウトプットは 160 ビットのハッシュ使用のため、80 ビットの衝突安全性しか得られない。これは低いと考えられ、単一当事者を超えるデータ (公開鍵、ハッシュなど) をアウトプットに含める場合は常にセキュリティ上のリスクとなる。 は、従来どおり制約を受けない。

• q を、ウィットネスプログラム (scriptPubKey における第 2 のプッシュ) を保持する 32 バイト配列とし、これは [[bip-0340.mediawiki#design|BIP340]] に従って公開鍵を表す。
• ウィットネススタックの要素数が 0 の場合は失敗。
• ウィットネス要素が 2 個以上あり、かつ末尾要素の先頭バイトが 0x50なぜ annex の先頭バイトは 0x50 なのか？ 0x50 は、有効な P2WPKH や P2WSH の使用と混同されえない値として選ばれている。コントロールブロックの先頭バイトの最下位ビットは公開鍵の Y 座標のパリティを示すために使われるため、各葉バージョンには偶数のバイト値と直後の奇数のバイト値の双方が必要であり、いずれも P2WPKH や P2WSH の使用ではまだ使われていない値である必要がある。annex を示すには 0x50 のような「ペアになっていない」利用可能なバイトのみが必要となる。この選択により、将来のスクリプトバージョンに対する選択肢が最大化される。 である場合、この末尾要素を annex aannex の用途は何か？ annex は将来の拡張のために予約された領域である。たとえば、使用されるアウトプットの scriptPubKey を知ることなく認識可能な形で、計算量の大きい新オペコードの検証費用を示すなどの用途が想定される。本フィールドの意味が別のソフトフォークで定義されるまで、ユーザーはトランザクションに annex を含めるべきではない (SHOULD NOT)、含めると 資金の恒久的な喪失 につながる可能性がある。 と呼び、ウィットネススタックから取り除く。annex (またはその不在) は常に署名により保護され、トランザクションの重みに寄与するが、Taproot 検証の他の部分では無視される。
• ウィットネススタックに残る要素が厳密に 1 個である場合、キーパス使用となる。
  • 残った単一のウィットネススタック要素は署名と解釈され、公開鍵 q に対して妥当でなければならない (次節を参照、また次小節を参照)。
• ウィットネススタックに残る要素が 2 個以上である場合、スクリプトパス使用となる。
  • スタックの末尾から 2 番目の要素を s と呼び、これがスクリプトである。
  • 末尾のスタック要素はコントロールブロック c と呼ばれ、その長さは 33 + 32m でなければならない。ここで m は 0 から 128 の間の整数 (両端含む) であるなぜマークルパス長は 128 に制限されるのか？ 空間効率の最適なマークルツリーは、葉に置かれたスクリプトの確率に基づき、ハフマンアルゴリズムにより構築できる。このアルゴリズムは長さがおおよそ log₂(1/probability) に等しい枝を構築するが、長さ 128 を超える枝を持つには実行確率が 2¹²⁸ 分の 1 未満のスクリプトが必要となる。これは本提案の安全境界でもあるため、真にこれほど低い確率しか持たないスクリプトはおそらく完全に削除してよい。。長さがこの形でない場合は失敗。
  • p = c[1:33] とし、P = lift_x(int(p)) とする。ここで lift_x および [:] は [[bip-0340.mediawiki#design|BIP340]] のとおり定義される。この点が曲線上にない場合は失敗。
  • v = c[0] & 0xfe とし、これを 葉バージョン (leaf version) と呼ぶ葉バージョンにはどのような制約があるか？ まず、c[0] & 0xfe は常に偶数となるため葉バージョンは奇数になりえず、また 0x50 にもなりえない (annex と曖昧になるため)。さらに、使用されるアウトプットへのアクセスなしにスクリプト使用を識別できることを必要とする一部の静的解析に対応するため、有効な P2WPKH 公開鍵または有効な P2WSH スクリプトの妥当な先頭バイトと衝突するような葉バージョンの使用を避けることが推奨される (すなわち、v と v | 1 の双方が未定義・無効・無効化されたオペコードか、または先頭オペコードとして妥当でないオペコードであること)。この規則に適合する値は、0xc0 から 0xfe の間の 32 個の偶数値、ならびに 0x66、0x7e、0x80、0x84、0x96、0x98、0xba、0xbc、0xbe である。なおこの制約は、ウィットネスバージョンを知るには使用されるアウトプットへのアクセスが必要となるため、葉バージョンは異なるウィットネスバージョン間で共有されるべきであることを含意する。。
  • k₀ = hash_TapLeaf(v || compact_size(size of s) || s) とする。これを tapleaf ハッシュ とも呼ぶ。
  • j を [0,1,…,m-1] で動かして:
    • e_j = c[33+32j:65+32j] とする。
    • k_j+1 を、k_j < e_j’ (辞書式順序) であるか否かに応じて定めるなぜマークルツリー内でハッシュ前に子要素をソートするのか？ こうすることで、開示されるマークルブランチにおいてハッシュとともに左右方向を開示する必要がなくなる。これが可能なのは、本提案がツリー内の特定のスクリプトの位置を実際には問題とせず、それらが確かにコミットされていることのみを問題とするためである。。
      • k_j < e_j の場合: k_j+1 = hash_TapBranch(k_j || e_j)なぜマークルツリーの内部節点でより効率的なハッシュ構成を用いないのか？ 採用した構成では SHA256 圧縮関数の呼び出しが 2 回必要となり、そのうち 1 回は理論上回避できる (BIP98 (https://github.com/bitcoin/bips/blob/master/bip-0098.mediawiki) を参照)。しかし、実装の単純さと解析容易性の双方の観点から、標準的な暗号原始関数を用いて実装できる構成にとどめる方が望ましいと思われる。必要であれば、2 回目の圧縮関数の大部分は 64 バイト入力向けの専用化 (https://github.com/bitcoin/bitcoin/pull/13191)により最適化可能である。。
      • k_j ≥ e_j の場合: k_j+1 = hash_TapBranch(e_j || k_j)。
  • t = hash_TapTweak(p || k_m) とする。
  • t ≥ 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 (secp256k1 の位数) の場合は失敗。
  • Q = P + int(t)G とする。
  • q ≠ x(Q) または c[0] & 1 ≠ y(Q) mod 2 の場合は失敗なぜスクリプトパス使用で 1 ビットを開示し、それが Q の Y 座標のパリティに一致することを検査する必要があるのか？ Y 座標のパリティは、X 座標 q を一意の点に持ち上げる (lift する) ために必要である。これは上記で説明された Taproot コミットメントの検証には厳密には必要ないが、バッチ検証を可能にするためには必要である。代替案として Q に偶数 Y 座標を強制することも考えられるが、その場合 Q がその性質を満たすまで内部公開鍵 (またはメッセージ) を変えて再試行することになる。コントロールブロックのビットは別の用途には使われないため、パリティビットを追加することに弊害はない。。
  • 適用されるスクリプトルールスクリプトパス使用において適用されるスクリプトルールは何か？ BIP342 (https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki) が葉バージョン 0xc0 に適用される妥当性ルールを規定するが、将来の提案で他の葉バージョン向けのルールを導入できる。 に従い、スクリプト s・コントロールブロック c・annex a (存在する場合) を除いたウィットネススタック要素を初期スタックとして、スクリプトを実行する。これは将来の葉バージョン (非 0xC0) においては実行が成功しなければならないことを含意するなぜ将来の葉バージョンの検証で成功させる必要があるのか これは将来の葉バージョンをソフトフォークとして導入可能にするために必要である。。

q は Taproot 出力鍵 (taproot output key) と呼ばれ、p は Taproot 内部鍵 (taproot internal key) と呼ばれる。

署名検証ルール

まず再利用可能な共通署名メッセージ計算関数を定義し、続いてキーパス使用において用いられる実際の署名検証を定義する。

共通署名メッセージ

関数 SigMsg(hash_type, ext_flag) は、署名されるメッセージの共通部分をバイト配列として計算する。これは、使用するトランザクションおよびそれが使用するアウトプットの暗黙の関数でもあるが、記法を単純に保つためそれらは引数として明記しない。

パラメーター hash_type は 8 ビットの符号なし値である。レガシースクリプトシステムからの SIGHASH 符号化、すなわち SIGHASH_ALL、SIGHASH_NONE、SIGHASH_SINGLE、SIGHASH_ANYONECANPAY を再利用する。新しい hashtype として SIGHASH_DEFAULT (値 0x00) を定義する。これは SIGHASH_ALL と同様にトランザクション全体に対する署名を意味する。以下の制約が適用され、違反すると検証失敗となる。

• 未定義の hash_type の使用 (0x00、0x01、0x02、0x03、0x81、0x82、0x83 以外なぜ未知の hash_type 値を拒否するのか？ こうすることで、適切なキャッシュを備えた実装が実行しなければならない最悪ケースの署名ハッシュ計算量について見積もりやすくなる。)。
• 「対応するアウトプット」 (検証対象のインプットと同じインデックスを持つアウトプット) を持たない状態での SIGHASH_SINGLE の使用。

パラメーター ext_flag は 0〜127 の範囲の整数であり、SigMsg() の出力に拡張が付加されることをメッセージ内で示すために用いられるどの拡張が ext_flag 機構を利用するのか？ [[bip-0342.mediawiki#common-signature-message-extension|BIP342]] は同じ共通署名メッセージアルゴリズムを再利用するが、末尾に BIP342 固有のデータを追加し、それを ext_flag = 1 で示す。。

パラメーターが受け入れ可能な値を取る場合、メッセージは以下のデータをこの順序で連結したものとなる (各項目のバイトサイズを括弧内に示す)。2 バイト・4 バイト・8 バイトの数値はリトルエンディアンで符号化される。

• 制御:
  • hash_type (1)。
• トランザクションデータ:
  • nVersion (4): トランザクションの nVersion。
  • nLockTime (4): トランザクションの nLockTime。
  • hash_type & 0x80 が SIGHASH_ANYONECANPAY と等しくない場合:
    • sha_prevouts (32): 全インプットの outpoint をシリアライズしたものの SHA256。
    • sha_amounts (32): 全インプットの金額をシリアライズしたものの SHA256。
    • sha_scriptpubkeys (32): 使用される全アウトプットの scriptPubKey を CTxOut 内のスクリプトとしてシリアライズしたものの SHA256。
    • sha_sequences (32): 全インプットの nSequence をシリアライズしたものの SHA256。
  • hash_type & 3 が SIGHASH_NONE または SIGHASH_SINGLE と等しくない場合:
    • sha_outputs (32): 全アウトプットを CTxOut 形式でシリアライズしたものの SHA256。
• 本インプットに関するデータ:
  • spend_type (1): (ext_flag * 2) + annex_present に等しい。ここで annex_present は annex が存在しない場合は 0、存在する場合 (元のウィットネススタックが 2 個以上のウィットネス要素を持ち、末尾要素の先頭バイトが 0x50) は 1。
  • hash_type & 0x80 が SIGHASH_ANYONECANPAY と等しい場合:
    • outpoint (36): 本インプットの COutPoint (32 バイトのハッシュ + 4 バイトのリトルエンディアン)。
    • amount (8): 本インプットが使用する直前のアウトプットの値。
    • scriptPubKey (35): 本インプットが使用する直前のアウトプットの scriptPubKey を CTxOut 内のスクリプトとしてシリアライズしたもの。サイズは常に 35 バイト。
    • nSequence (4): 本インプットの nSequence。
  • hash_type & 0x80 が SIGHASH_ANYONECANPAY と等しくない場合:
    • input_index (4): トランザクションのインプットベクトルにおける本インプットのインデックス。先頭インプットのインデックスは 0。
  • annex が存在する場合 (spend_type の最下位ビットがセットされている場合):
    • sha_annex (32): (compact_size(size of annex) || annex) の SHA256。ここで annex は必須の 0x50 接頭辞を含む。
• 本アウトプットに関するデータ:
  • hash_type & 3 が SIGHASH_SINGLE と等しい場合:
    • sha_single_output (32): 対応するアウトプットを CTxOut 形式でシリアライズしたものの SHA256。

SigMsg() の総長は最大 206 バイトである何が SigMsg() の出力長か？ SigMsg() の総長は次の式で計算できる: 174 - is_anyonecanpay * 49 - is_none * 32 + has_annex * 32。。なおこの長さには、sha_prevouts のような部分ハッシュのサイズは含まれない。これらは同一トランザクションの複数の署名にまたがってキャッシュできる。

要約すると、BIP143 (https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki) のシグハッシュ型の意味は、以下を除き変更されない。

1. シリアライズの方式と順序が変更された。なぜ署名メッセージにおけるシリアライズが変更されたのか？ 署名メッセージに入るハッシュおよびメッセージ自体は、二重 SHA256 ではなく単一の SHA256 呼び出しで計算されるようになった。署名メッセージには秘密データが含まれないため、SHA256 に対する長さ拡張攻撃は懸念にならず、SHA256 の二重化による安全性上の改善は期待できない。したがって SHA256 の二重化は資源の浪費である。メッセージ計算は今や論理的な順序に従う。すなわち、トランザクションレベルのデータが先、続いてインプットデータとアウトプットデータである。これにより、SHA256 の midstate を用いて、異なるインプット間でメッセージのトランザクション部分を効率的にキャッシュできる。加えて、メッセージ計算時には部分ハッシュをスキップできる (たとえば SIGHASH_ANYONECANPAY がセットされている場合は sha_prevouts を、BIP143 のように 0 にセットしてからハッシュするのではなく、計算自体を省略する)。それでもなお、可変長データの前にデータ長を (hash_type と spend_type に暗黙に含めて) コミットすることにより、衝突は不可能とされる。
2. 署名メッセージは使用されるアウトプットの scriptPubKey にコミットし、SIGHASH_ANYONECANPAY フラグがセットされていない場合、メッセージはトランザクションが使用する 全 アウトプットの scriptPubKey にコミットする。なぜ署名メッセージは scriptPubKey にコミットするのか？ これは、実際に実行されるスクリプト (BIP143 の scriptCode) が正しい場合でも、使用対象のアウトプットについてオフライン署名デバイスを欺くことを防ぐ。これは、ハードウェアウォレットに対して (未使用の) 実行経路が存在したことを簡潔に証明できることを意味する。さらに、使用される全 scriptPubKey にコミットすることで、オフライン署名デバイスが自ウォレットに属する部分集合を判定する助けとなる。これは自動コインジョイン (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-April/017801.html)において有用である。
3. SIGHASH_ANYONECANPAY フラグがセットされていない場合、メッセージはトランザクションの 全 インプットの金額にコミットする。なぜ署名メッセージはトランザクションの全インプットの金額にコミットするのか？ これは、トランザクションの手数料についてオフライン署名デバイスを欺く可能性を排除する。
4. SIGHASH_NONE または SIGHASH_SINGLE がセットされている場合 (ただし SIGHASH_ANYONECANPAY も同時にセットされていない場合)、署名メッセージは全インプットの nSequence にコミットする。なぜ SIGHASH_SINGLE または SIGHASH_NONE がセットされている場合、署名メッセージは全インプットの nSequence にコミットするのか？ これらをセットすると、メッセージはすでに全トランザクションインプットの prevouts 部分にコミットすることになるため、nSequence を別扱いする意義はない。さらにこの変更により、nSequence は「SIGHASH_SINGLE と SIGHASH_NONE は署名メッセージをトランザクションのアウトプットに関してのみ変更し、インプットに関しては変更しない」という見方と整合する。
5. 署名メッセージには Taproot 固有のデータ spend_type および annex (存在する場合) へのコミットメントが含まれる。

Taproot キーパス使用の署名検証

Taproot 署名は、BIP340 (https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki) で定義される 64 バイトのシュノア署名に、ビットコインの慣例に従いシグハッシュバイトを付加したものである。このシグハッシュバイトは省略可能である。省略された場合、結果として得られる署名は 64 バイトであり、SIGHASH_DEFAULT モードが暗黙に指定されたものとする。

公開鍵 q で署名 sig を検証するには:

• sig が 64 バイト長であれば、Verify(q, hash_TapSighash(0x00 || SigMsg(0x00, 0)), sig) を返すなぜ hash_TapSighash への入力に 0x00 が前置されるのか？ この接頭辞はシグハッシュエポックと呼ばれ、ハッシュ計算の方式を侵襲的に変更する将来の署名アルゴリズムにおいて、hash_TapSighash タグ付きハッシュを再利用できるようにする (これは漸進的な拡張に用いられる ext_flag 機構とは対照的である)。代替案として異なるタグを用いる方法もあるが、増え続けるタグ数を支えることは望ましくないかもしれない。。ここで Verify は [[bip-0340.mediawiki#design|BIP340]] で定義される。
• sig が 65 バイト長であれば、sig[64] ≠ 0x00なぜ 65 バイト署名において hash_type を 0x00 にできないのか？ これを許すと、64 バイト署名を (マイナーを含む第三者によって) 65 バイト署名に展性 (malleate) 可能となり、結果として wtxid が変わり、また作成者の意図と異なる手数料率になる。 かつ Verify(q, hash_TapSighash(0x00 || SigMsg(sig[64], 0)), sig[0:64]) を返す。
• それ以外は失敗なぜ 2 通りの署名長を許すのか？ 最も一般的な hash_type を暗黙化することで、しばしば 1 バイトを節約できる。。

Taproot アウトプットの構築と使用

本節では、Taproot アウトプットの構築方法と使用方法を述べる。本節は受信および支払いの実装を選択するウォレットソフトウェアにのみ影響し、いかなる意味でもコンセンサスに関わるものではない。

概念的には、すべての Taproot アウトプットは、単一の公開鍵条件 (内部鍵) と、ツリー状に組織化されたスクリプトに符号化された 0 個以上の一般条件、の組合せに対応する。 これらの条件のいずれかを満たせばアウトプットを使用できる。

初期手順 最初の手順は、内部鍵と残りのスクリプトの構成方針を定めることである。具体的内容はおそらくアプリケーションに依存するが、一般的な指針を以下に挙げる。

• 条件付き (OP_IF など) を含むスクリプトを採用するか、それを複数のスクリプトに分割するか (各スクリプトが元スクリプトの 1 通りの実行経路に対応する) を選ぶ場合、一般には後者が望ましい。
• 単一条件で複数の鍵による署名を必要とする場合、MuSig のような鍵集約技術を用いて 1 個の鍵に統合できる。詳細は本文書の範囲外であるが、署名手続が複雑化しうる点に留意されたい。
• 使用条件のうち 1 つ以上が単一の鍵のみで構成される (集約後の) 場合、最も可能性の高い条件を内部鍵とすべきである。そのような条件が存在しない場合、すべてのスクリプトに参加する全鍵を集約したものを 1 つ追加することを検討する価値がある。これは事実上「全員合意」の枝を追加することに相当する。それが受け入れがたい場合は、内部鍵として「Nothing Up My Sleeve」 (NUMS) 点、すなわち離散対数が未知の点を選ぶ。そのような点の一例は、secp256k1 (https://www.secg.org/sec2-v2.pdf) のベース点 G の標準非圧縮符号化のハッシュを X 座標として取ることで構築 (https://github.com/ElementsProject/secp256k1-zkp/blob/11af7015de624b010424273be3d91f117f172c82/src/modules/rangeproof/main_impl.h#L16)される H = lift_x(0x50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) である。キーパス使用が不可能であるという情報が漏れることを避けるため、0…n-1 の範囲から一様乱数で新鮮な整数 r を取り、H + rG を内部鍵として使うことが推奨される。検証者に r を開示することで、当該内部鍵が G に関して既知の離散対数を持たないことを証明でき、検証者は内部鍵がどう構築されたかを再構成できる。
• 使用条件がスクリプトパスを必要としない場合でも、出力鍵はスクリプトパスを持たないのではなく、使用不能なスクリプトパスにコミットすべきである。これは出力鍵の点を Q = P + int(hash_TapTweak(bytes(P)))G として計算することで達成できる。スクリプトパスがない場合でも、なぜ出力鍵は常に Taproot コミットメントを持つべきか？ Taproot 出力鍵が鍵の集約である場合、悪意ある当事者が他の当事者に気付かれずにスクリプトパスを追加できる可能性がある。 これにより多者方針を回避してコインを盗むことが可能になる。 MuSig 鍵集約はすでに内部鍵をランダム化させるため、この問題を持たない。

攻撃は次のように働く。アリスとマロリーが、スクリプトパスなしの Taproot 出力鍵に自分たちの鍵を集約しようとしているとする。 鍵打ち消しおよび関連する攻撃を防ぐため、彼らは MuSig ではなく MSDL-pop (https://eprint.iacr.org/2018/483.pdf) を用いるとする。 MSDL-pop プロトコルでは、全当事者に対応する秘密鍵の所有証明を提示することが要求され、集約鍵は個々の鍵の単純な和となる。 マロリーはアリスの鍵 A を受け取った後、M = M₀ + int(t)G を生成する。ここで M₀ はマロリー本来の鍵であり、t は内部鍵 P = A + M₀ とマロリーの鍵のみを含むスクリプトでのスクリプトパス使用を可能にする。 マロリーは M の所有証明をアリスに送り、両当事者は出力鍵 Q = A + M = P + int(t)G を計算する。 アリスはスクリプトパスに気付くことができず、マロリーは出力鍵 Q を持つ任意のコインを一方的に使用できる。

• 残りのスクリプトは二分木の葉に組織化すべきである。各スクリプトが対応する条件の確率が等しい場合、これは均衡木でよい。各条件の確率が既知である場合は、木をハフマン木として構築することを検討する。

出力スクリプトの計算 使用条件が内部鍵 internal_pubkey と、葉が (leaf_version, script) 組である二分木とに分解されたら、以下の Python3 アルゴリズムを用いて出力スクリプトを計算できる。これらのアルゴリズムは [[bip-0340/reference.py|BIP340 参照コード]] の補助関数 (整数変換・点の乗算・タグ付きハッシュ) を利用する。

まず、32 バイトの BIP340 (https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki) 公開鍵配列に対して taproot_tweak_pubkey を定義する。 本関数は、ツイークされた公開鍵の Y 座標を示すビットと、公開鍵のバイト配列を返す。 パリティビットはスクリプトパスでアウトプットを使用する際に必要となる。 キーパスでの使用を可能にするため、ツイークされた公開鍵に対応する秘密鍵を計算する taproot_tweak_seckey を定義する。 任意のバイト列 h について、taproot_tweak_pubkey(pubkey_gen(seckey), h)[1] == pubkey_gen(taproot_tweak_seckey(seckey, h)) が成り立つ。

なお、ツイークは 32 バイトの公開鍵に対して適用されるため、taproot_tweak_seckey はツイーク適用前に秘密鍵を否定 (negate) する必要があるかもしれない。

def taproot_tweak_pubkey(pubkey, h):
    t = int_from_bytes(tagged_hash("TapTweak", pubkey + h))
    if t >= SECP256K1_ORDER:
        raise ValueError
    P = lift_x(int_from_bytes(pubkey))
    if P is None:
        raise ValueError
    Q = point_add(P, point_mul(G, t))
    return 0 if has_even_y(Q) else 1, bytes_from_int(x(Q))

def taproot_tweak_seckey(seckey0, h):
    seckey0 = int_from_bytes(seckey0)
    P = point_mul(G, seckey0)
    seckey = seckey0 if has_even_y(P) else SECP256K1_ORDER - seckey0
    t = int_from_bytes(tagged_hash("TapTweak", bytes_from_int(x(P)) + h))
    if t >= SECP256K1_ORDER:
        raise ValueError
    return bytes_from_int((seckey + t) % SECP256K1_ORDER)

以下の関数 taproot_output_script は scriptPubKey (BIP141 (https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki) を参照) を含むバイト配列を返す。 ser_script は、入力に CompactSize 符号化長を前置する関数を指す。

def taproot_tree_helper(script_tree):
    if isinstance(script_tree, tuple):
        leaf_version, script = script_tree
        h = tagged_hash("TapLeaf", bytes([leaf_version]) + ser_script(script))
        return ([((leaf_version, script), bytes())], h)
    left, left_h = taproot_tree_helper(script_tree[0])
    right, right_h = taproot_tree_helper(script_tree[1])
    ret = [(l, c + right_h) for l, c in left] + [(l, c + left_h) for l, c in right]
    if right_h < left_h:
        left_h, right_h = right_h, left_h
    return (ret, tagged_hash("TapBranch", left_h + right_h))

def taproot_output_script(internal_pubkey, script_tree):
    """Given a internal public key and a tree of scripts, compute the output script.
    script_tree is either:
     - a (leaf_version, script) tuple (leaf_version is 0xc0 for [BIP342](https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki) scripts)
     - a list of two elements, each with the same structure as script_tree itself
     - None
    """
    if script_tree is None:
        h = bytes()
    else:
        _, h = taproot_tree_helper(script_tree)
    _, output_pubkey = taproot_tweak_pubkey(internal_pubkey, h)
    return bytes([0x51, 0x20]) + output_pubkey

このアウトプットをスクリプト D で使用する場合、コントロールブロックには以下のデータがこの順序で含まれる。

 <control byte with leaf version and parity bit> <internal key p> <C> <E> <AB>

そのとき TapTweak は [[bip-0341.mediawiki#script-validation-rules|上記]] で説明されたとおり、次のように計算される。

D = tagged_hash("TapLeaf", bytes([leaf_version]) + ser_script(script))
CD = tagged_hash("TapBranch", C + D)
CDE = tagged_hash("TapBranch", E + CD)
ABCDE = tagged_hash("TapBranch", AB + CDE)
TapTweak = tagged_hash("TapTweak", p + ABCDE)

キーパスを用いた使用 Taproot のアウトプットは、internal_pubkey に対応する秘密鍵で使用できる。そのためには、ウィットネススタックを単一の要素 — 上記で定義した署名ハッシュに対する BIP340 (https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki) 署名で、秘密鍵を上記スニペットと同じ h でツイークしたもの — から成るようにする。以下のコードを参照。

def taproot_sign_key(script_tree, internal_seckey, hash_type, bip340_aux_rand):
    if script_tree is None:
        h = bytes()
    else:
        _, h = taproot_tree_helper(script_tree)
    output_seckey = taproot_tweak_seckey(internal_seckey, h)
    sig = schnorr_sign(sighash(hash_type), output_seckey, bip340_aux_rand)
    if hash_type != 0:
        sig += bytes([hash_type])
    return [sig]

本関数は必要なウィットネススタックと、上記で定義した署名ハッシュを計算する sighash 関数を返す (単純化のため、上記のスニペットはトランザクション・インプット位置などの情報を sighash 計算コードに渡す部分を省略している)。

スクリプトのいずれかを用いた使用 Taproot のアウトプットは、その構築時に用いられた任意のスクリプトを充足することで使用できる。そのためには、スクリプトのインプットに加えて、スクリプト本体とコントロールブロックを含むウィットネススタックが必要となる。以下のコードを参照。

def taproot_sign_script(internal_pubkey, script_tree, script_num, inputs):
    info, h = taproot_tree_helper(script_tree)
    (leaf_version, script), path = info[script_num]
    output_pubkey_y_parity, _ = taproot_tweak_pubkey(internal_pubkey, h)
    pubkey_data = bytes([output_pubkey_y_parity + leaf_version]) + internal_pubkey
    return inputs + [script, pubkey_data + path]

セキュリティ

Taproot はビットコインのプライバシーを改善する。アウトプットを使用するためのすべての可能な条件を開示する代わりに、満たされた使用条件のみを公表すればよいためである。 理想的には、アウトプットはキーパスで使用される。これによりコインの使用条件を観察者が学習することを防げる。 キーパス使用は、単一署名または多者署名ウォレットからの「通常の」支払いであることもあれば、隠れた多者契約の協調的な決済であることもある。

スクリプトパス使用は、スクリプトパスが存在し、かつキーパスが適用不能であったこと — たとえば関係当事者が合意に達しなかったこと — を漏らす。 さらに、マークルルートにおけるスクリプトの深さは、木の最小深さを含む情報を漏らし、それはアウトプットを生成した特定のウォレットソフトウェアを示唆し、クラスタリングの助けとなりうる。 したがって、葉に対する確率分布から定まる最適な木から意図的に逸脱することで、スクリプト使用のプライバシーを向上できる。

他の既存のアウトプット型と同様、プライバシー上の理由から Taproot のアウトプットでも鍵を再利用してはならない。 これはアウトプットを使用する際に用いた特定の葉だけでなく、当該アウトプットがコミットしているすべての葉に当てはまる。 葉を再利用すると、別のアウトプットを使用する際にマークル証明の中で同じマークルブランチが再利用されることが起こりうる。 鮮度のある鍵を用いれば、Taproot のアウトプット構築において葉の位置をランダム化する特別な措置は不要となる。Taproot で用いる枝ソート式マークルツリー構成により、すでにランダム化されているためである。 これは葉の深さを通じた情報漏えいを回避するものではないため、本性質は均衡 (部分) 木にのみ当てはまる。 加えて、すべての葉は他のあらゆる葉と互いに異なる鍵の集合を持つべきである。 理由は、葉のエントロピーを増し、観察者が総当たり探索により未開示のスクリプトを学習することを防ぐためである。

テストベクトル

ウォレット動作 (scriptPubKey の計算、キーパス使用、コントロールブロック構築) のテストベクトルは [[bip-0341/wallet-test-vectors.json|こちら]] にある。 これは 2 組のベクトルから構成される。

• 第 1 の「scriptPubKey」テストは、内部公開鍵とスクリプトツリーが与えられたときの scriptPubKey と (メインネットの) BIP350 アドレスの計算を扱う。スクリプトツリーは、スクリプトなしを表す null、葉ノードを表す JSON オブジェクト、または内部ノードを表す 2 要素配列として符号化される。スクリプトパス使用に必要なコントロールブロックも、各スクリプト葉について提供される。
• 第 2 の「keyPathSpending」テストはテストケースの列からなる。各ケースは未署名トランザクションとそれが使用する UTXO を提供する。各 BIP341 インプットについて、内部秘密鍵と、それを導出したマークルルート、ならびに当該インプットを使用する期待されるウィットネスが与えられる。すべての署名は、全ビット 0 (0x0000…0000) の BIP340 補助乱数配列を用いて生成される。
• いずれの場合も、16 進値はバイト配列を表し、数値ではない。特にこれは、提供されるハッシュ値が、先頭のバイトに対応する 16 進桁が先に並ぶことを意味する。これは、16 進文字列が数値を表し結果として逆順となる、txid やブロックハッシュの慣例とは異なる。

Bitcoin Core 単体テスト枠組み (https://github.com/bitcoin/bitcoin/blob/3820090bd619ac85ab35eff376c03136fe4a9f04/src/test/script_tests.cpp#L1718)で用いられる検証テストベクトルはこちら (https://github.com/bitcoin-core/qa-assets/blob/main/unit_test_data/script_assets_test.json?raw=true)にある。

根拠

case DEFINED:
    if (GetMedianTimePast(block.parent) >= starttime) {
        return STARTED;
    }
    return DEFINED;

case STARTED:
    int count = 0;
    walk = block;
    for (i = 0; i < 2016; i++) {
        walk = walk.parent;
        if ((walk.nVersion & 0xE0000000) == 0x20000000 && ((walk.nVersion >> bit) & 1) == 1) {
            count++;
        }
    }
    if (count >= threshold) {
        return LOCKED_IN;
    } else if (GetMedianTimePast(block.parent) >= timeout) {
        return FAILED;
    }
    return STARTED;

case LOCKED_IN:
    if (block.nHeight < min_activation_height) {
        return LOCKED_IN;
    }
    return ACTIVE;