Skip to content

Instantly share code, notes, and snippets.

@visvirial
Last active September 17, 2020 15:46
Show Gist options
  • Save visvirial/2c729806bd4f95b91e7ef3c78adfbf31 to your computer and use it in GitHub Desktop.
Save visvirial/2c729806bd4f95b91e7ef3c78adfbf31 to your computer and use it in GitHub Desktop.
BIP 341「Taproot: SegWit version 1 spending rules」日本語版

翻訳者注:この日本語訳は、2020年2月21日時点で https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki に公開されているものを底本としています。最新の情報については原文をご参照ください。

  BIP: 341
  Layer: Consensus (soft fork)
  Title: Taproot: SegWit version 1 spending rules
  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-0341
  Status: Draft
  Type: Standards Track
  Created: 2020-01-19
  License: BSD-3-Clause
  Requires: 340
  Post-History: 2019-05-06: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016914.html [bitcoin-dev] Taproot proposal

Table of Contents

導入

アブストラクト

このドキュメントでは、Taproot に基づいた未使用コインの使用ルール、Schnorr(シュノア)署名、および Merkle ブランチを含めた、新しい SegWit バージョン 1 出力タイプを提案します。

著作権

このドキュメントは、3条項 BSD ライセンスでライセンスされます。

動機

この提案は、プライバシー、効率性、および Bitcoin のスクリプト言語の能力に対する柔軟性を、新しいセキュリティ上の仮定を導入せずに改善することを目的としています[1]。特に、この文書ではトランザクションが作成された時点、もしくは未使用コインを使用する時点において、ブロックチェーン上にトランザクションの出力の使用条件に関する情報が最小化されること、およびいくつかの軽微であるが長らく放置されていた問題を修正しつつ、いくつかのアップグレードの仕組みを追加することを目指しています。

設計

Bitcoin のスクリプト言語の能力を改善する関連するアイディアのいくつかは、既に提案がなされています: Schnorr 署名 (BIP340)、Merkle ブランチ ("MAST", BIP114, BIP117)、新しい sighash モード (BIP118)、CHECKSIGFROMSTACK などの新しい OP コード, TaprootGraftrootG'root、および 入力をまたぐ電子署名の集約方式

これらすべてのアイディアを合体させ一つの提案とするのは、変更点が膨大となり、レビューが難しくなり、また実装途中で見つかる可能性のある新しい発見を取り込み損なう可能性があります。例えば入力をまたがる集約方式は、アップグレードメカニズムと複雑に相互作用し、またこれらに対するソリューションは未だ流動的です。一方で、これらの改善手法をすべてバラバラに依存関係のないアップグレードとすることは、効率性、および本来あるはずだったプライバシーの向上を低下させます。またウォレットもしくはサービス提供者は多数の逐次的な更新に対して対応することに難色を示すでしょう。したがって、機能性とスコープクリープの間のトレードオフに直面することでしょう。本ドキュメントの設計では、Taproot および Merkle ブランチの提供する構造的なスクリプト言語の改善および、これらを有用かつ効率的にするために必要な変更にのみ注力することで、妥協点に至っています。Sighash や OP コードのようなものについては、既知の問題への修正のみを含めることにし、欠点なく独立に追加することのできる新機能については省いています。

その結果、以下のような技術の組み合わせを選択しました:

  • Merkle ブランチを採用することで、スクリプトが実行されるすべての可能性について列挙するのではなく、実際に実行された一部のスクリプトのみをブロックチェーンに公開することができます。こうした機能を実装するためのメカニズムはいくつか知られていますが、Merkle 木を採用すると直接的にサイズを削減できるため、このアプローチが選択されました。
  • Taproot を採用することで、伝統的に分離されていた pay-to-pubkey および pay-to-scripthash ポリシーを一つにまとめることができ、すべての出力コインを鍵、もしくはスクリプト(任意)によって使用でき、かつそれらを区別できないようにすることができます。コインを使用する際に鍵ベースの使用パスが選択される限りにおいて、スクリプトパスが利用可能かどうかが公開されず、コインの使用時にサイズ削減やスクリプトのプライバシーを向上させることができます。
  • Taproot の優位性は、ほとんどのアプリケーションではすべての参加者による同意のもとで出力が使用されるという仮定のもとで明らかになります。これが Schnorr 署名が登場する理由であり、鍵の集約ができるという特徴に基づきます: 公開鍵を複数の参加者の公開鍵から構築することができ、この場合すべての参加者が協調して署名を行わなければなりません。このような複数人による公開鍵および署名は、一人のみの場合に作られるデータと区別することができません。これはほとんどの Taproot アプリケーションは、効率的でプライバシーの高い鍵ベースのコイン使用パスを利用できることを意味しています。より複雑な初期セットアッププロトコルが代償とはなりますが、Schnorr 署名は閾値署名をサポートしますので、これは任意の M-of-N ポリシーに一般化することができます。
  • Schnorr 署名はバッチ検証を行うこともできますので、複数の署名をひとまとめに検証を行うことで電子署名を一つずつ検証するのに比べてより効率的に処理を行うことができます。この文書では設計上任意の場所でこのバッチ検証に互換性のある形にしました。
  • 上記の変更によって使用されないビットが発生しますが、これらは将来的な拡張のメカニズムのために予約されております。これにより、Merkle 木に含まれる任意のスクリプトに対してバージョン情報が付加されますので、BIP 341 と互換性のある形でソフトフォークによって新しいスクリプト言語のバージョンを導入することができます。また、将来のソフトフォークでは、witness 内に含まれている現在は未使用の annex を利用することができます (BIP341 を参照してください)。
  • 署名ハッシュアルゴリズムのコアセマンティクスは変更されていませんが、この提案ではいくつかの改善点が含まれています。新しい署名ハッシュアルゴリズムでは署名メッセージの中に金額と scriptPubKey が含まれていますので、オフラインの署名デバイスでの検証能力に対する修正が行われています。不必要なハッシュ化処理の除外、タグ付けされたハッシュの利用、およびデフォルトの sighash バイトが定義されています。
  • 典型的な以前の方法では、公開鍵もしくはスクリプトのハッシュ値が利用されるのと対照に、公開鍵は出力に直接記述されます。これによって、送金者にとっては同じコストですが、鍵ベースのコイン使用パスが選択された場合には全体的によりサイズ効率がよくなります。[2]
端的に言うと、最終的な設計は以下のようなものです: 新しい witness バージョンが追加され (バージョン1)、witness プログラムは点 Q の32バイトエンコーディングで構成されます。Q は公開鍵 P および、バージョン番号とスクリプトにより構成される葉を持つ Merkle 木のルート m に対して P + hash(P||m)G により計算されます。こうした出力は Q に対する署名を作成することで直接的に使用することができますし、P、スクリプト、葉のスクリプトのバージョン、スクリプトを満足する入力、Q がその葉に対してコミットされていることを証明する Merkle パスを公開することで間接的に使用することもできます。この構成で用いるハッシュ値(P から Q を計算するためのハッシュ値、Merkle 木の内部ノードで用いられるハッシュ値、および署名ハッシュに用いられるハッシュ値)はすべて領域が分離されることを保証するためにタグ付けされています。

仕様

このセクションでは Taproot のコンセンサスルールを定義します。有効性は排他的に定義されます: すなわちブロックまたはトランザクションは、これらを失敗とみなす条件が存在しない限り有効となります。

以下で記法はBIP340のものに準拠します。これには SHA256(SHA256(tag) || SHA256(tag) || x) を意味する hashtag(x) 記法を含みます。著者の知る限りにおいて、二つの単一な SHA256 の出力で始まるようなメッセージは、Bitcoin で利用されている SHA256 の既存の利用方法には存在しません。これによって、hashtag に対して他のハッシュ値と衝突が発生する可能性は極限まで排除されます。

スクリプト検証ルール

Taproot 出力はバージョン番号 1 かつ witness プログラムが 32 バイトのネイティブ SegWit 出力 (BIP141 を参照してください) です。 以下のルールはそのような出力が使用されようとしたときにのみ適用されます。その他の出力、例えば 32 バイトではないサイズを持つバージョン 1 の出力や、P2SH にラッピングされたバージョン 1 の出力[3]については、従来どおり感知しないものとします。

  • qBIP340 に従う公開鍵に対応する witness プログラム (scriptPubKey における二番目のプッシュ命令) を含む 32 バイトのバイト列とします。
  • Witness スタックに要素がない場合には失敗とします。
  • Witness 要素が少なくとも二つ以上存在し、かつ最後の要素の最初のバイトが 0x50[4] である場合、この最後の要素は annex a[5] と呼ぶことにし、witness スタックからは削除します。Annex (またはそれの欠落) は常に sighash の入力に含まれ、トランザクションの重量に影響します。しかしながら Taproot の検証処理においては、これは無視されます。
  • Witness スタックにちょうど一個の要素が残っっていた場合には、鍵パスを用いた使用とみなされます:
    • この単一の witness スタック要素は署名であると解釈され、公開鍵 q (次のサブセクションを参照してください) に対して有効なものでなければなりません (次のサブセクションを参照してください)。
  • 少なくとも二つの witness 要素が残っていた場合には、スクリプトパスを用いた使用とみなされます:
    • 最後から二番目のスタック要素 s はスクリプトと呼ばれます。
    • 最後のスタック要素はコントロールブロック c と呼ばれ、33 + 32m バイトのサイズを持つ必要があります。ここで m の値は 0 から 128[6] の間の整数値である必要があります。もしもそのような長さを持たない場合には、失敗とします。
    • p = c[1:33] および P = point(p) とします。ここで point および [:]BIP340 で定義されているものと同様とします。この点 P が曲線上に乗っていない場合には失敗とします。
    • v = c[0] & 0xfe とし、これを葉のバージョン[7]と呼びます。
    • k0 = hashTapLeaf(v || compact_size(size of s) || s) とし、これを tapleaf ハッシュ と呼びます。
    • For j in [0,1,...,m-1]:
      • ej = c[33+32j:65+32j] とします。
      • kj+1kj < ej (辞書順)[8] を満たすかどうかによって以下のうように定義します:
        • kj < ej の場合: kj+1 = hashTapBranch(kj || ej)[9] とします。
        • kj ≥ ej の場合: kj+1 = hashTapBranch(ej || kj) とします。
    • t = hashTapTweak(p || km) とします。
    • t ≥ 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 (secp256k1 の位数) の場合、失敗とします。
    • (c[0] & 1) = 1 であれば Q = point(q) とし、そうでない場合には -point(q) とします[10]。この点が曲線に乗らない場合には失敗とします。
    • Q ≠ P + int(t)G の場合、失敗とします。
    • スクリプト s、コントロールブロック c および annex a (存在すれば) を除いた witness スタック要素を初期スタックとして、適当なスクリプトルール[11]を用いてスクリプトを実行します。
qTaproot 出力鍵pTaproot 内部鍵 といいます。

署名検証ルール

まずはじめに再利用可能な共通の署名メッセージ計算関数を定義したあと、鍵パスの使用の際に用いられる実際の署名検証ルールを定義します。

共通の署名メッセージ

関数 SigMsg(hash_type, ext_flag) はメッセージとして署名されるバイト列を計算します。これは暗に使用するトランザクションおよび使用しようとしている出力に依存しますが、ここでは記法の簡略化のために明示しません。

パラメータ hash_type は 8 ビットの符号なし整数です。従来のスクリプトシステムで用いられている SIGHASH エンコーディングは踏襲されます。これには SIGHASH_ALLSIGHASH_NONESIGHASH_SINGLE、および SIGHASH_ANYONECANPAY を含みます。また hash_type のデフォルト値として 0x00 を追加します。これは SIGHASH_ALL と同様にトランザクション全体に署名をします。以下のような制限も追加で導入され、これらに合致しない場合には検証失敗となります:

  • 未定義の hash_type (0x00, 0x01, 0x02, 0x03, 0x81, 0x82, or 0x83[12] でないもの) を用いた場合。
  • SIGHASH_SINGLE を「対応する出力」(検証しようとしている入力と同じインデックスを持つ出力)なしに用いた場合。
パラメータ ext_flag は 0〜127 の間の整数であり、メッセージの最後に拡張が追加されていることを示すために用いられます[13]

パラメータが許可された値であれば、以下のようなデータを順番に(それぞれのバイトサイズは括弧内で示しています)結合したものとしてメッセージは構成されます。2、4、および 8 バイトの数値データはリトルエンディアンでエンコードされます。

  • コントロール:
    • hash_type (1).
  • トランザクションデータ:
    • nVersion (4): トランザクションの nVersion
    • nLockTime (4): トランザクションの nLockTime
    • hash_type & 0x80SIGHASH_ANYONECANPAY と一致しなかった場合:
      • sha_prevouts (32): すべての入力の消費しようとしている出力元をシリアライズしたものの SHA256 ハッシュ。
      • sha_amounts (32): すべての入力の数量をシリアライズしたものの SHA256 ハッシュ。
      • sha_sequences (32): すべての入力の nSequence をシリアライズしたものの SHA256 ハッシュ。
    • hash_type & 3SIGHASH_NONE または SIGHASH_SINGLE と一致しなかった場合:
      • sha_outputs (32): すべての出力を CTxOut フォーマットでシリアライズしたものの SHA256 ハッシュ。
  • この入力に関するデータ:
    • spend_type (1): (ext_flag * 2) + annex_present の値。ここで annex_present は annex が存在しなければ 0 であり、存在すれば 1 (元の witness スタックが二個以上の witness 要素をもち、かつ最後の要素の最初のバイトが 0x50 のとき)。
    • scriptPubKey (35): この入力により消費される、前の出力の scriptPubKeyCTxOut の内部のスクリプトと同様にシリアライズしたもの。サイズは常に 35 バイト。
    • hash_type & 0x80SIGHASH_ANYONECANPAY と一致する場合:
      • outpoint (36): この入力に対応する COutPoint (32 バイトのハッシュ値 + 4 バイト、リトルエンディアン)。
      • amount (8): この入力によって消費される、前の出力の数量。
      • nSequence (4): この入力の nSequence
    • hash_type & 0x80SIGHASH_ANYONECANPAY と一致しなかった場合:
      • input_index (4): トランザクションの入力ベクトル内に位置する、この入力のインデックス。最初の入力のインデックスは 0。
    • Annex が存在する場合 (spend_type の最下位ビットがセットされている場合):
      • sha_annex (32): (compact_size(size of annex) || annex) の SHA256 ハッシュ。ここで annex は必須のプレフィクス 0x50 を含む。
  • この出力に関するデータ:
    • hash_type & 3SIGHASH_SINGLE と一致する場合:
      • sha_single_output (32): 対応する出力の CTxOut フォーマットの SHA256 ハッシュ。
SigMsg() の全サイズは最大で 209 バイトになります[14]。同一のトランザクション内に含まれる署名の間でキャッシュを行うことが出来る sha_prevouts などのサブハッシュのサイズは含まれないことに注意してください。

まとめると、BIP143 sighash タイプのセマンティクスは、以下の点を除いて維持されます:

  1. シリアライゼーションのやり方および順番が変更されています。[15]
  2. 署名メッセージは scriptPubKey[16] に対してコミットされます。
  3. SIGHASH_ANYONECANPAY フラグがセットされていない場合、メッセージはすべてのトランザクションの入力の数量に対してコミットされます。[17]
  4. SIGHASH_NONE または SIGHASH_SINGLE がセットされている場合 (また同時に SIGHASH_ANYONECANPAY がセットされていない場合) には、署名メッセージはすべての入力の nSequence に対してコミットされます。[18]
  5. 署名メッセージは Taproot 専用のデータである spend_type および annex (存在すれば) に対するコミットメントを含みます。

Taproot 鍵パス使用の署名検証

公開鍵 q に対し署名 sig の検証は以下のように行います:

  • sig が 64 バイトの場合には Verify(q, hashTapSigHash(0x00 || SigMsg(0x00, 0)), sig)[19] の結果を返します。ここで VerifyBIP340 で定義されているものです。
  • sig が 65 バイトの場合には、sig[64] ≠ 0x00[20] および Verify(q, hashTapSighash(0x00 || SigMsg(sig[64], 0)), sig[0:64]) の結果を返します。
  • 以上が当てはまらない場合には、失敗とします[21]

Taproot 出力を構築・使用する

このセクションでは Taproot 出力をどのように構築し、使用するのかを議論します。これは Taproot 出力の受け取りおよび送金を実装するように選択したウォレットソフトウェアにのみ影響があり、どのような場合でもコンセンサス・クリティカルではありません。

概念的には、すべての Taproot 出力は単一公開鍵の条件 (内部鍵) およびゼロ以上の Merkle 木上にエンコードされたスクリプトによる一般的な条件を組み合わせたものになります。 以下のいずれかの条件をみたす場合、出力を使用することができます。

初期ステップ 最初のステップは、内部鍵が何かを決定し、残りのスクリプトの組成がどうあるべきかを決定することです。詳細についてはアプリケーションに依存すると思われますが、以下にいくつかの一般的なガイドラインを示します:

  • スクリプト内に条件分岐 (OP_IF など) を含めるか、またはスクリプトを複数に分割 (元のスクリプトのそれぞれの実行パスに相当します) するのかを決める際には、一般的には後者を選択するとよいでしょう。
  • 一つの条件に対して複数の鍵による署名を要求する場合には、MuSig のような鍵集約のテクニックを利用して一つの鍵に集約するのがよいでしょう。詳細についてはこのドキュメントのスコープを外れてしまいますが、これによって署名手続きは複雑になってしまうことに注意してください。
  • (集約後の) 一つの鍵に対して一つ以上の使用条件がある場合、内部鍵を作るのがよいでしょう。そのような条件が存在しない場合、すべてのスクリプトを結合したものの中の鍵を集約したものを加えることで、「全員による合意」という枝を実効的に加えるのがよいでしょう。これが許容できない場合、離散対数が未知の点の内部鍵を選びましょう。そのような点の一つの例として、secp256k1 ベースポイント G の標準的な未圧縮エンコーディングの X 座標のハッシュから構成される H = point(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) があります。鍵パス使用が不可能であるという情報が漏洩するのを防ぐためには、0...n-1 の間の整数 r を一様ランダムに選択し、H + rG を内部鍵としましょう。r を検証者に渡すことで内部鍵が G に対する既知の離散対数を持たないことを証明することができます。これによって検証者はどのように内部鍵が作られたのかを再構築することができます。
  • 使用条件にスクリプトパスが必要ではない場合には、出力鍵はスクリプトの存在しないパスではなく、使用できないスクリプトへのパスに対してコミットしなければいけません。これは出力鍵の点を Q = P + int(hashTapTweak(bytes(P)))G として計算することで実現できます。[22]
  • 残りのスクリプトは二分木の葉に編成する必要があります。それぞれのスクリプトに対応する条件がほぼ同じ確率を持つ場合には、平衡木を作ることもできます。それぞれの条件の確率が既知であった場合には、Huffman 木を用いて木を構成することを検討してください。
出力スクリプトの計算 使用条件が複数の内部鍵 internal_pubkey に分割され、タプル (leaf_version, script) を葉に持つ二分木に変換すれば、出力スクリプトは下記の Python3 アルゴリズムで計算を行うことができます。これらのアルゴリズムは整数変換、点の乗算、およびタグ付きハッシュ値の計算について bip-0340/referency.py BIP340 のリファレンスコードからの補助関数を利用しています。

まずはじめに、32 バイトの BIP340 公開鍵列として taproot_tweak_pubkey を定義します。 Tweak された公開鍵のバイト列に加えて、公開鍵が tweak された点であるか、それともそれを符号反転したものなのかを表すブール値を返却します。 これはスクリプトパスを用いた出力の使用に必要なものです。 鍵パスを用いた使用ができるようにするため、tweak された公開鍵に対応する秘密鍵を計算できるよう taproot_tweak_seckey を定義します。 任意のバイト列 h に対して、taproot_tweak_pubkey(pubkey_gen(seckey), h)[0] == pubkey_gen(taproot_tweak_seckey(seckey, h)) が成り立ちます。

def taproot_tweak_pubkey(pubkey, h):
    t = int_from_bytes(tagged_hash("TapTweak", pubkey + h))
    if t >= SECP256K1_ORDER:
        raise ValueError
    Q = point_add(point(pubkey), point_mul(G, t))
    is_negated = not has_square_y(Q)
    return bytes_from_int(x(Q)), is_negated

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

以下の関数 taproot_output_script は scriptPubKey を含むバイト列を返却します (BIP141 をご覧ください)。 ser_script は CCompactSize でエンコードされた長さを含む入力でプレフィクスされたものを表します。

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):
    """与えられた内部公開鍵及びスクリプトの木から、出力スクリプトを計算する。
    ここで script_tree は以下のいずれかである:
     - タプル (leaf_version, script) ([[bip-0342.mediawiki|BIP342]] のスクリプトに関しては leaf_version は 0xc0)
     - script_tree 自体と同じ構造を持つ二つの要素のリスト
     - 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

この図は内部鍵 <i>P</i> から tweak を得る際のハッシュ構造を示す、5 個のスクリプト葉から構成される Merkle 木です。<i>A</i>, <i>B</i>, <i>C</i> および <i>E</i> は <i>TapLeaf</i> ハッシュであり、同様に <i>D</i> および <i>AB</i> は <i>TapBranch</i> ハッシュです。<i>CDE</i> が計算される際には、<i>CD</i> よりも <i>E</i> の方が小さいため、<i>E</i> がはじめにハッシュされることに注意してください。
この図は内部鍵 P から tweak を得る際のハッシュ構造を示す、5 個のスクリプト葉から構成される Merkle 木です。A, B, C および ETapLeaf ハッシュであり、同様に D および ABTapBranch ハッシュです。CDE が計算される際には、CD よりも E の方が小さいため、E がはじめにハッシュされることに注意してください。

スクリプト D を用いてこの出力を使用するためには、コントロールブロックは以下のデータをこの順番で含める必要があります:

     <葉のバージョンを含むコントロールバイトおよび、符号ビット> <内部鍵 p> <C> <E> <AB>

TapTweak は上記で説明されるのと同様に計算されます:

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)

鍵パスを用いた使用 internal_pubkey に対応した秘密鍵を用いて Taproot の出力は消費されます。そのためには、witness スタックは一つの要素で構成されなければいけません: 上のスニペットにあるのと同様な h を用いて tweak した秘密鍵を用いた、上述の署名ハッシュに対する BIP340 で定義される署名です。以下のコードを参照してください:

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

この関数は必要な witness スタックおよび上記で定義された署名ハッシュを計算する sighash 関数を返却します (簡単のため、上のスニペットはトランザクション、入力の位置などの情報を sighash のコードへ渡すことを省略しています)。

スクリプトを用いた使用 Taproot の出力は、構成時に利用されたスクリプトのいずれか一つをみたすことで使用することができます。そのためにはスクリプトの入力およびスクリプト自体、およびコントロールブロックを含む witness スタックが必要です。以下のコードを参照してください:

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]
    _, is_negated = taproot_tweak_pubkey(internal_pubkey, h)
    output_pubkey_tag = 0 if is_negated else 1
    pubkey_data = bytes([output_pubkey_tag + leaf_version]) + internal_pubkey
    return inputs + [script, pubkey_data + path]

セキュリティ

Taproot では、出力を使用するすべての取りうる条件を明かすことなく、みたされた一つの使用条件のみを公開することができますので、Bitcoin のプライバシーを改善します。 理想的には、出力が鍵パスを用いて使用されることによって、観察者がコインの使用条件を知ってしまうことを防ぐことができます。 鍵パスを用いた使用は、「通常の」支払い、すなわちシングルシグまたはマルチシグウォレット、または秘匿された複数参加者によるコントラクトの協調的なセットルメントを表すでしょう。

スクリプトパスを用いた使用は、スクリプトパスが存在することおよび鍵パスが適用されなかったという情報を漏洩させます。これは例えば複数の参加者が共通の合意に至ることができなかったことなどを表します。 さらに Merkle ルートの中にあるスクリプトの深さは木の最小の深さを含む情報を漏洩させ、これによって出力を作った特定のウォレットソフトウェアが示唆され、クラスタリングを行うことを助けます。 したがって葉の間の確率分布から決定される最適な木構造から敢えて外れさせることで、スクリプトを用いた使用のプライバシーを向上させることができます。

既に存在する他の出力タイプと同様に、プライバシー上の理由から Taproot の出力は鍵を再利用してはいけません。 これは実際に使用された出力が含まれる特定の葉にのみ適用されるものではなく、出力にコミットされるすべての葉に対してあてはまります。 葉が再利用された場合、異なる出力を使用したとしても、Merkle プルーフの中で同じ Merkle 枝が再利用される可能性があります。 Taproot において用いられている Merkle 木を構成する際の枝のソーティングによって葉の場所は既にランダム化されておりますので、新鮮な鍵を利用することは、Taproot の出力を構成する際に葉の場所をランダム化するための特別な手段を取る必要がなくなることを示唆します。 これは葉の深さの情報を漏洩させることを防ぐわけではなく、(サブ)平衡木に対してのみ当てはまります。 さらにすべての葉は他のすべての葉と違った鍵セットを持たなければなりません。 その理由は葉のエントロピーを増やし、観察者から公開されていないスクリプトのブルートフォース探索を防がなければならないからです。

テストベクトル

生成トランザクションおよび使用トランザクションのペアの例 (有効/無効)。

それぞれの sighash モードに対する sighash のプレイメージの例。

論拠

  1. ^ セキュリティ上の仮定を導入しないとはどういう意味ですか? 署名が偽造できないことは盗難を防ぐためには必要要件です。少なくともスクリプト言語の実行をデジタル署名スキームのみに絞った場合、偽造不可能性はランダムオラクルモデルにおいて離散対数問題が困難であることを仮定すれば証明可能です。現状のスクリプト言語システム上での ECDSA の偽造不可能性の証明には離散対数問題が難しいという仮定の他に、一般的ではない仮定が必要となります。ウォレットソフトウェアで利用されているポリシーおよびプロトコルに依存するため、スクリプト言語のセキュリティと言った場合に何を意味するのかを正確にモデリングすることは一般的には困難であることに注意してください。
  2. ^ なぜ公開鍵を出力に直接含めるのですか? 典型的な以前の方法では、公開鍵もしくはスクリプトのハッシュ値が出力に含まれますが、これは公開鍵が必ず伴う場合、より無駄があります。バッチ検証性を保証するためには、すべての検証者が公開鍵を知る必要があり、出力にハッシュ値のみを公開する場合には witness に追加の32バイトを追加しなければいけないことを意味します。そのうえ、出力に対して128ビットの衝突耐性を維持するためには、256ビットのハッシュ値が必要ですので、公開鍵を直接公開するのに比べてサイズ(そして送金者のコスト)的には同等のものとなります。しばしば ECDLP の破綻や量子コンピュータに対する防御策として公開鍵のハッシュ化が利用されていると言われていますが、この防御策は控えめに言っても非常に脆弱です: トランザクションはブロック取り込み待ちの間は防御されませんし、そもそも通貨供給量のうち大半がこのような防御策のもとにありません。異なる暗号学的仮定に依存したものを導入することで、こうしたシステムに対する実効的な耐性を得られはずですが、この提案ではセキュリティモデルを変えないような改善点にのみ注力しています。
  3. ^ なぜ P2SH にラッピングされたものはサポートされないのですか? P2SH にラッピングされた出力は 160 ビットのハッシュ関数を用いているため、たったの 80 ビットの衝突安全性しか提供されません。このビット数は低いと考えられますので、一人よりも多い参加者 (公開鍵、ハッシュ値、……) からのデータが出力に含まれる場合にはセキュリティ上のリスクになるでしょう。
  4. ^ なぜ annex の最初のバイトは 0x50 なのですか? 0x50 は有効な P2WPKH または P2WSH を使用するものと混同しないように選択されました。コントロールブロックの最初のバイトの最下位ビットは公開鍵の Y 座標の平方剰余性を示すために用いられているため、それぞれの葉のバージョンは偶数のバイト値を持つ必要があり、これはすなわち P2WPKH および P2WSH を使用するものについては偶数のバイト値を持つことを意味するからです。Annex を示すためには、0x50 のような「ペアリングされていない」利用可能なバイトが必要です。この選択により将来のスクリプトバージョンに対して有効な選択肢が最大化されます。
  5. ^ Annex にはどのような目的があるのですか? Annex は将来的な拡張に対する予約されたデータ領域であり、例えば計算量的に高価な検証コストを持つ新しい OP コードを、使用される出力の scriptPubKey を知ることなく認識するために用いることができます。他のソフトフォークでこのフィールドの意味が定義されるまで、ユーザはトランザクション内に annex を含めるべきではありません (SHOULD NOT)。さもなければ、永久に資産が失われてしまう可能性があります。
  6. ^ なぜ Merkle パスの長さは 128 に制限されるのですか? サイズに対して効率的に最適化された Merkle 木は、Huffman アルゴリズムを用いた葉のスクリプトの利用確率に基づいて構成することができます。このアルゴリズムでは、長さがおおよそ log2(1/probability) に等しい枝が構成されます。したがって 128 を超える長さを持つ枝は 2-128 以下の実行確率を持つスクリプトとなります。これはここでのセキュリティ限界であり、そのような低い確率を真に持つスクリプトは完全に削除される必要があるでしょう。
  7. ^ 葉のバージョンに対する制限は何ですか? まずはじめに、c[0] & 0xfe は常に偶数となるため、葉のバージョンは奇数にはできません。また annex と混同されるおそれがあるため、0x50 にすることはできません。また、使用されようとしている出力へアクセスすることなく使用しようとしているスクリプトが同定できることに依存している静的な解析のいくつかの形式をサポートするためには、有効な P2WPKH の公開鍵または有効な P2WSH スクリプト (すなわち、v および v | 1 は未定義か、無効もしくは無効化された OP コード、または最初の OP コードとして有効ではないもの) の有効な最初のバイトと衝突するような葉のバージョンは使わないようにすることが推奨されます。このようなルールに適合するような値は 0xc0 から 0xfe の間の 32 個の偶数値、および 0x66, 0x7e, 0x80, 0x84, 0x96, 0x98, 0xba, 0xbc, 0xbe です。Witness のバージョンを知るためには使用されようとしている出力へのアクセスが必要なため、この制限は異なる witness バージョンの間で葉のバージョンは共有されなければならいことに注意してください。
  8. ^ Merkle 木上でハッシュ化する前になぜ子要素をソートするのですか? こうすることによって、公開した Merkle 枝のハッシュ値について、左右の向きを明示する必要がなくなるためです。これができるのは木の中の特定のスクリプトの位置を気にする必要がないことに依拠します。スクリプトが実際に Merkle 木にコミットされていることだけを示せばよいためです。
  9. ^ Merkle 木内部のノードに対して、より効率的なハッシュ関数を利用しないのはなぜですか? 本文書で選択されている構成では二回の SHA256 圧縮関数の計算が必要となりますが、理論的には一回のみで可能 (BIP98 を参照してください) です。しかしながら標準的な暗号プリミティブを用いて実装できる構成にとどめておく方が、実装の容易さや解析のしやすさ双方にとって良いでしょう。必要であれば、64 ビットの入力値に対してはこちらの特殊化技法を用いて二回目の圧縮関数の大部分を最適化によって落とすことができます。
  10. ^ なぜスクリプトパスの使用で出力の公開鍵によって示されている点を符号反転するかどうかを表すビットを公開する必要があるのですか? point 関数 (BIP340 で定義されているもの) では常に平方剰余な Y 座標をもつ点を作り出します。しかしながら Q は内部の公開鍵 P に対して Taproot tweak を足し合わせることで作られますので、Q がそのような Y 座標を持つことを簡単に保証することはできません。したがって必要であれば符号反転を行うことで、Taproot tweak を検証する前に元の点を復元する必要があります。バッチ検証の妨げとなりますので、Y 座標を無視することはできません。複数の内部鍵を用いて、このような条件を満たす Q が出てくるまで試すこともできますが、Y 座標のこういった情報については未使用のビットをひとつ消費するだけですので、適当でも必要でもないでしょう。
  11. ^ スクリプトパスの使用における、適当なスクリプトルールとはなんですか? BIP342 で葉のバージョンが 0xc0 の場合に適用される検証ルールを定義しています。これ以外の葉のバージョンに対するルールについては、将来的に別の提案として導入されるでしょう。
  12. ^ なぜ未知の hash_type を拒否するのですか? これは、適切なキャッシュ処理を行っている実装において、署名ハッシュを行う最悪の場合の個数を推察することが容易となるからです。
  13. ^ ext_flag のメカニズムはどのような拡張で用いられていますか? BIP342 では共通の同様な署名メッセージアルゴリズムを再利用していますが、最後に BIP342 特有のデータを追加しており、これは ext_flag = 1 を用いて示されます。
  14. ^ SigMsg() の出力サイズとはなんですか? SigMsg() の全サイズは次の公式を用いて求めることができます: 177 - is_anyonecanpay * 52 - is_none * 32 + has_annex * 32
  15. ^ 署名メッセージのシリアライゼーション方法が変更されているのはなぜですか? 署名メッセージの中に入るハッシュ値およびメッセージ自体はダブル SHA256 ではなく一回の SHA256 によって計算されます。SHA256 を二回行うことによって守ることができるのは length-extension 攻撃に対してのみであり、秘密データのない署名メッセージに対しては意味がない攻撃ですので、SHA256 を二回行うことによるセキュリティ上の期待される改善はありません。したがってダブル SHA256 はリソースの無駄遣いでしかありません。メッセージの構築方式は、トランザクションレベルのデータが最初、次に入力、出力、といった具合に論理的な順番に従うようになります。これによって SHA256 の midstate を用いることでメッセージのトランザクションパートを異なる入力に対して効率的にキャッシュできるようになります。さらに、メッセージ (例えば SIGHASH_ANYONECANPAY がセットされた場合の `sha_prevouts`) を計算する際にサブハッシュをゼロにセットして BIP143 のようにこれらをハッシュする際に、サブハッシュをスキップすることができます。しかしながら、可変の長さデータの前にデータの長さ (hash_type および spend_type に暗に含まれています) をコミットすることで衝突が不可能なようになっています。
  16. ^ 署名メッセージを scriptPubKey に対してコミットするのはなぜですか? 実際に実行されたスクリプト (BIP143 の scriptCode) が正しい場合においても、使用しようとしている出力に関してオフラインの署名デバイスを騙すことができないようになります。これによってハードウェアウォレットに対してどのような (未使用の) 実行パスが存在するのかをコンパクトに証明することができるようになります。
  17. ^ 署名メッセージがすべてのトランザクションの入力に対してコミットされているのはなぜですか? トランザクションの手数料に関して、オフラインの署名デバイスを騙す可能性を削減することができるからです。
  18. ^ SIGHASH_NONE または SIGHASH_SINGLE がセットされている場合に署名メッセージがすべての入力の nSequence に対してコミットされるのはなぜですか? これらのフラグがセットされている場合には、メッセージはすべてのトランザクションの入力に対する prevouts に対してコミットするため、nSequence を特別扱いすることは有用ではありません。さらに、この変更により nSequenceSIGHASH_SINGLE および SIGHASH_NONE がトランザクションの入力ではなく出力に対して署名メッセージを変更するという見方と一貫性を持ちます。
  19. ^ hashTapSigHash に対する入力に対して 0x00 をプレフィクスするのはなぜですか? このプレフィクスは sighash epoch と呼ばれ、将来の署名アルゴリズムで hashTapSigHash によるタグ付けされたハッシュを再利用してハッシュの実行の仕方を侵略的に変更することができます (ext_flag のメカニズムを用いた逐次的な拡張とは対称的です)。代わりに異なるタグを利用するということもできますが、タグの数を増やすことをサポートするのは得策ではありません。
  20. ^ 65 バイトの署名に対して、hash_type0x00 ではない値を取ることができるのはなぜですか? (採掘者を含む第三者により) 64 バイトの署名を 65 バイトの署名にすることで、異なる `wtxid` および作成者が意図した手数料率とは異なるトランザクションを作ることができるためです。
  21. ^ 二つの署名長を許可するのはなぜですか? 最も共通的に使われている hash_type を暗に指定することができるようにすることで、1 バイト節約できるためです。
  22. ^ スクリプトパスが存在しないにもかかわらず、出力鍵が必ず Taproot コミットメントを持つ必要があるのはなぜですか? Taproot の出力鍵が複数の鍵を集約したものであった場合には、攻撃者が他の参加者に知られることなくスクリプトパスを追加できる可能性があります。 これにより複数人が必要というポリシーをバイパスし、コインを盗むことができてしまいます。 MuSig による鍵集約では、内部鍵がランダム化されますのでこの問題はありません。 攻撃は以下のように行われます: Alice および Mallory がそれぞれの鍵を集約し、スクリプトパスのない一つの Taproot 出力鍵にしようとしていると仮定します。 鍵キャンセルおよびそれに関連する攻撃を防ぐために、MuSig のかわりに MSDL-pop を使うとします。 MSDL-pop プロトコルは、すべての参加者の対応する秘密鍵に対して所有の証明を提供することを要求します。集約鍵はそれぞれの鍵を合算したものになります。 Mallory が Alice の鍵 A を受け取ったあと、Mallory は M = M0 + int(t)G を生成します。ここで M0 は Mallory の元の鍵であり、t によって内部鍵 P + A + M0 を用いて使用可能なスクリプトパスが利用できてしまい、Mallory の鍵だけを含むスクリプトを作ることができてしまいます。 Mallory は M に対する所有の証明を Alice に対して送信し、両者は出力鍵 Q = A + M = P + int(t)G を計算します。 Alice はスクリプトパスに気づくことはできませんが、Mallory は一方的に出力鍵 Q を持つ任意のコインを使用することができてしまいます。

実装

TODO

後方互換性

これはソフトフォークですので、古いソフトウェアは変更なしに動作し続けることができます。 しかしながら、アップグレードされていないノードは、すべてのバージョン 1 SegWit witness プログラムを anyone-can-spend スクリプトとして解釈します。 新しいプログラムを完全に検証するために、アップグレードを行うことを強くおすすめします。

アップグレードされていないウォレットは、アップグレードされていないウォレットおよびアップグレードされたウォレットの双方から、バージョン 0 の SegWit プログラム、例えば伝統的な pay-to-pubkey-hash を用いて送受金できます。 実装には依存しますがアップグレードされていないウォレットであっても、BIP173 Bech 32 アドレスに対する送金をサポートしていれば、バージョン 1 の SegWit プログラムに対して送金することができます。

謝辞

この文書はスクリプトおよび署名の改善まわりに対するたくさんの方の議論による結果であり、Greg Maxwell らによる直接的な貢献の賜物です。さらにこれは、既出の改善提案である Greg Maxwell による Taproot、Russel O'Connor, Johnson Lau および Mark Friedenbach らによる Merkle 枝の構成に依拠しています。

Arik Sosman による Merkle ノードの子をハッシュする前にソートすることで木の中の位置を伝送する必要をなくす改善提案や、構造的レビューに参加していただいた方を含む、その他数々の有用なフィードバックおよびレビューをいただいた方々に感謝いたします。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment