※本記事は2020年3月25日に開催された「【暗号通貨読書会#36】Taproot（※オンライン開催）」の文字書き起こしです。
https://cryptocurrency.connpass.com/event/167570/
書き起こしもとの動画はこちらから視聴いただけます。書き起こしに伴い一部欠落または改変されている箇所がある場合がありますので、ご了承ください。
BIP３４１「taproot:SegWit version １ spending rules」（以下BIP３４１）というBIPと
BIP３４２「Validation of Taproot Scripts」（以下BIP３４２）が、BIP３４１の上位BIP３４１を使った
taproot用のスクリプト言語の説明です
今日のハイライト
Bitcoinに近々実装される予定の「Taproot」と呼ばれる技術について、
その使用である下記のBIP（Bitcoin Improvement Proposale）の解説を行います。
解説は基本的にBIPの内容を要約したものになっておりますので、適宜元のBIPをご参考ください。
・BIP３４１「Taproot:SegWit version １ spending rules」
・BIP３４２「Validation of Taproot Scripts」
日本語訳
本公演に先立ち、本日紹介するBIPの日本語訳を GitHub Gistにて公開しています。
復習等、ご利用ください。
・BIP３４１ http://gist.github.com/visvirial/2c729806bd4f95b91e7ef3c7adfbf31
・BIP３４２ http://gist.github.com/visvirial/95b1f05b37878a75d465924062caeabe
BIPの中身を見ると、前提となる知識が必要とされます。
暗号の知識が必要なのはもちろん、Bitcoin自体の仕様の知識の復習として
いくつか既存の技術について触れていきます。
Merklized Abstract Syntax Tree(マークル化抽象構文木;MAST）（以下MAST）
Taprootのコアのアイデアであり、スマートコントラクト(スクリプト)内に条件分岐がある場合どちらかしか実行出来ません。
そのため実行されなかった方の命令をブロックチェーンに書くのは無意味な為、
実行されない命令については命令文を記入せず、命令文のハッシュ値のみ公開しデータ容量を削減し、実行した命令文自体が公開されないことによりプライバシーの向上を目指したものがMASTです。
このMASTの記事を無料で公開しております。是非ご覧ください。https://blog.visvirial.com/articles/657
Schnorr（シュノア）署名
シュノアという男性が発明し、自身の名をつけた署名です。
ECDSAやDSAなどと同様の電子署名方式の一つです。
既存の電子署名と比べると、数学的にいい特徴を持っています。
・署名の集約が（簡単に）出来る ※１
〇複数の電子署名を組み合わせることでマルチシグが簡単に構成出来ます
・安全性が(DLP設定の下で)数学的に証明されている ※２
・大量の署名検証処理が高速になる(バッチ検証） ※３
詳しく知りたい方は拙著のブログ記事
「Schnorr署名－30年の時を超えて注目を集める電子署名」https://blog.visvirial.com/articles/721及び
BIP３４０「Schnorr Signatures for secp256k1」(拙作の日本語訳あり)https://gist.github.com/visvirial/1d36ab0902cfd6d427767e41a328a1fa
等をご覧ください
※１ 署名の集約自体はSchnorr署名だと準同型性を持つため、簡単に出来る。
（他のECDSAなどは準同型性を持たないため、集約できなくはないが作業量が増えてしまいます。）
※２ 離散対数問題と言われる難しい問題が解けなければ、Schnorr署名が解けない、
ハッキングできないということが数学的に証明されています。
※３ バッチ検証と呼ばれるBIP３４０でSchnorr署名に関するBIPが検証されています。
千個、一万個と一度に検証するときに一度に検証するよりも早くなるというアルゴリズムがあります。
Segwit（Segregated Witness、セグウィット)
旧来の方法ではScriptSignature内に公開鍵データと署名データを一緒くたに記述していましたが、
Segwitではこれを分離することで以下のような改善がなされています。
・トランザクション展性の問題の解決 ※４
・電子署名データを検証しなくてもよい場合のデータ転送量の削減
・ソフトウォークによる柔軟なアップグレートの仕組みの提供 ※５
ここではTaprootを英買いするために必要な情報のみ紹介しておりますので、詳細については
BIP１４１「Segregated Witness(Consensus Layer)」などを参照してください。
※４ トランザクション展性とは トランザクションの意味合いを変えずに
バイナリデータ(ハッシュ値)を変えてしまう攻撃があり、ライトニングネットワーク等がうまくいかない場合があります。
だが、Segwitを使うと電子署名データが分離されるためプロダクション展性が無くなります
※５ SegwitにはVer0～Ver16まであり、今現状のSegwitで使われている従来のものに対応していますが
今回紹介するtaprootはこのSegwitのバージョン1を使いアップグレードの仕組みを提供しています。
Segwit
ScriptPubKey（P2SHの場合はredeemScript）が「1バイトのプッシュ命令(0～16)」「2～40バイトのプッシュ命令」で構成されている出力はSegwit出力とみなします。
ここで一番のプッシュされた数字を「バージョン」、二番目を「Witness Program」といいます。※６
現在はバージョン番号としては0番のみが採択されており、Taprootでは未使用の1番のバージョンを利用します。
Segwitトランザクションの検証では、バージョン番号に基づき、Witness Program 及び従来のトランサクションデータとは別に保管されている Witness スタックと呼ばれるバイトレつの配列を組み合わせて検証を行います。※７
BIP３４１ taproot：Segwit Version １ Spending Rules
を使って解説していきます。
導入、設計、仕様、taproot出力を作制、使用、セキュリティ等のコンテンツがあります。
動機
taprootのメリットとしてプライバシー、効率性、Bitcoinのスクリプト言語の能力に対することを便利にできる。
セキュリティ上の新しい過程のデメリット無しに導入することを目的としている。
また、タブレットを使うとブロックチェーン上に公開されるトランザクションのスマートコントラクト
の一部情報のみ公開するので、プライバシーの向上につながる。
設計
Schnorr署名、MAST、新しいSighashモード、CHECKSIGFROMSTACKなど新しいOPコード、Taproot、Graftroot、G’root
及び入力をまたぐ電子署名の集約方式の提案されていました。
しかし、すべて集約するのは難しいので、有用かつ副作用が少ないもののみを集めた物です。
その中で今回のtaprootで採用されているものが
・Merkleブランチ(MAST）
・Taproot
採用することでPay-to-putkey及びPay-to-scripthushポリシーを一つにまとめることが出来、プライバシー向上につながります。
・Schnorr署名
鍵の集約ができるのでパーティが複数人いた場合、今までのECDSAの場合参加人数分の鍵が必要でしたが、
Schnorr署名の場合鍵を集約して一つの電子署名に集約できるため便利です。
また、Schnorr署名は閾値署名をサポートし、任意のM-of-Nポリシーに一般化することができます。
・バッチ検証
・ソフトウォークによる新しいスクリプト言語のバージョンを導入
・署名ハッシュアルゴリズムの変更
金額とScriptPubkeyに対して電子署名が除外、トレザーに対してインプット、アウトプットで出てしまう差異に今まで気づけなかったことを検証できます。
・公開鍵が直接ブロックチェーンに直接記録されるようになるため、サイズ効率が良くなります。
まとめると
Segwit Witnessバージョンとしてバージョン１が追加され、
Witnessプログラムは点Qの３２プログラムとして公開されている。
（Qとは？公開鍵P及びMASTのマークルルートMを結合したもののハッシュ値を取りベースポイントgにかけたものにより計算されます。）
仕様
タグ付ハッシュをTaprootでは基本的に使用します。
Taprootの出力はSegwitバージョン番号１かつ、Witnessプログラムが３２バイトになっているネイティブSegwit出力をTaprootとします。
実際に受け取ったトランザクションをどのように検証するのか
・スモールキューという変数をSchnorr署名に公開鍵に対応するWitnessプログラムとしてQを使用する
・この時点でWitnessスタックに要素がない場合失敗である。
・Witnessスタック要素を見てWitnessスタック要素が二つ以上存在し、Witnessスタックのトップアイテムが０ｘ５０である場合は、annex a と呼び、Witnessスタックから削除します。
・Witnessスタックに乗せている要素が一つの場合、鍵パスを用いた仕様とみなされます。
普通のシングル送金に対応しています。Schnorr署名であると解釈され、公開鍵Qに対して有効なSchnorr署名であるといけないという検証をしています。
・Witnessスタックに二個以上の要素が残っていた場合、スクリプトパスを用いた仕様に対応するとみなされます。その場合の検証はスタックの一番上から二番目のスタック要素Sはスクリプトとします。
・Witnessスタックの一番上はコントロールブロックCと呼ばれ３３＋３２Mバイトのサイズです。Mの値は０から１２８の間の整数値である必要があります。Mはマークルツリーの高さに相当するデータです。
・マークルツリーのK0版を元にマークルプルーフをデータを合体して、マークルルートを計算、まとめる。従来のBitcoinと違う所は、マークルツリーの順番を辞書順にソートする事です。
・t=hashtapweak（P ll Km）とし、境界チェックしコントロールブロックの0番目のバイトをチェックし(c〔0〕&1=1であればQ=point(q)をX座標とし楕円曲線状の点とします。
最後に、定義としてqをtaprootの出力鍵、ｐをtaprooの内部鍵と定義します。
署名検証ルール
署名メッセージ
・関数 SigMsg(hash_type,ext_flag)をメッセージとして使用されるバイト列とします。引数が二つあり、ハッシュタイプは従来から使われるSIGHASH(SIGHASH_ALL、SIGHASH_NONE,SIGHASH_SINGLE、SIGHASH_ANYONECAMPAY)を含みます。また、hash_typeのデフォルト値として0x00の場合SIGHASH_ALLと同様、トランザクション全体に署名します。
・ext_flagは0～127の間の整数であり、メッセージハッシュの最後に拡張データを追加するflagです。
このもとでメッセージを構成していきます(動画参照)
・コントロール
・hash_type(1) 1バイト入れる
・トランザクションデータ
・nVersion(4)
・nLockTime(4)
・hash_type&0x80がSIGHASH_ANYONECAMPAYと一致しなかった場合
・sha_prevouts(32)消費しようとしている出力のトランザクションハッシュ値、
・sha_amounts(32)すべての入力のnsequenceをシリアライズしたもの
この入力に関するデータ
・spend_type(1):(ext_flag*2)+annex_presendのデータで埋められる。
ここでannex_presentはannexが存在しなければ0、
存在すれば1(元のWitnessスタックが2個以上のwitness要素を持ち、
かつ最後の要素の初めのバイトが0x50の場合)
・ScriptPubkey(35)：この入力により消費される前の出力のScriptPubkeyを
CTｘOutの内部スクリプトと同様にシリアライズ。サイズは常に35バイト。
・hash_type&0x80がSIGHASH_ANYONECAMPAYと一致する場合：
・outpoint(36):この入力に対応するcOutPoint(32バイトのハッシュ値+バイト、リトルエンディアン）
・amount(8):この入力のnsequence
・hash_type&0x80が、SIGHASH_ANYONECAMPAYと一致しなかった場合：
・input_index(4):トランザクションの入力ベクトル内に位置する、この入力のインデックス。最初の入力のインデックスは0。新しく追加されたものです。
・annexが存在する場合(spend_typeの再開いびっとがセットされている場合)
・sha_annex(32):(compact_size(size of annex）ll annex）のSHA256ハッシュ。
ここでannexは必須のプレフィクス0x50を含む。新しく追加されたもの。
この出力に関するデータ
・hash_type&3がSIGHASH_SINGLEと一致する場合：
・sha_single_output(32):対応する出力のCTxOut フォーマットのSHA256ハッシュ。
SigMsg()の全サイズは最大で209バイトとなります。
まとめると、BIP143 sighashタイプのセマンティクスは、以下の点を除いて維持されます：
1.シリアライゼーションのやり方及び順番の変更
2．署名メッセージはScriptPubkeyに対してコミットされます
3．SIGHASH_ANYONECAMPAYフラグがセットされていない場合、メッセージはすべてのトランザクションの入力数量に対してコミットされます。
4．SIGHASH_NONEまたはSIGHASH_SINGLEがセットされている場合(または同時にSIGHASH_ANYONECANPAYがセットされていない場合)には、署名メッセージはすべての入力のnsequenceに対してコミットされます。
5．署名メッセージはTaproot専用のデータであるspend_type及びannex(存在すれば)に対するコミットメントを含みます。
Taproot鍵パス仕様の署名検証
公開鍵qに対し署名sigの検証は以下のように行います：
・sigが64バイトの場合、verifi(q,hashtapsighash(0x00 ll SigMsg(0x00)),sigの結果を返します。
ここでverifyはBIP340で定義されているものです。
・sigが65バイトの場合、sig〔64〕≠0x00およびverifi(q,hashtypesighash(0x00 ll SigMsg(sig〔64〕,0))，sig〔0:64〕)の結果を返します。
・以上が当てはまらない場合には失敗とします。
Taproot出力を構成・使用する
実際にTaprootの出力をどのように構成するのか、使用するのかというと、ウォレットソフトウェア等がトランザクションを作るときにソフトウェアが何をすればいいのか？
初期ステップとして内部鍵として何を使うのかを決めて残りのスクリプト構成の鍵を決めます。
・含めたいスクリプトを分解してマークルツリーを作ります。スクリプト内に条件分岐(op_if等）を含めるか、もしくはスクリプトを複数に分割し違うマークルイフにする方法があります。(後者のほうが利便性が高い)
・内部鍵として、全員の鍵を集約したものを内部鍵として選ぶ場合があるが、選べない場合、すべてのスクリプトを結合したものの中の鍵を集約したものを加えることで、「全員による合意」という枝を実効的に加えるのが良い。これが許容できない場合、離散対数が道の点の内部鍵を選びましょう。
・使用条件にスクリプトパスが必要でない場合は、使用できないスクリプトパスに対してコミットすることが必要です。具体的には、Q=P+int(hashTapTweak(bytes(P))Gとして計算することで実現できます。
・上記を用いてスクリプトを構成し、内部鍵を構成後にスクリプトを集めます。平衡木(バランスツリー)を作ることもできますが、スクリプトごとに実行確率がすべて同じではないため、実行確率の高いスクリプトは根に近いところに配置、逆に実行確率の低いスクリプトは根に遠い深いところに配置することによりデータサイズの削減等ができます。
図：サンプルツリー
この図の下部右側にあるDというスクリプトを使うためにどのようにデータを作ればいいか？コントロールブロックとしてどのユニ構成すればいいのかが記載されています。
この時に鍵パスを用いた仕様として記載されている内容を使用します。(動画参照1:07:00～頃)
セキュリティ
taprootでは、スクリプトを分割して実行された使用条件だけ公開することでプライバシーの改善しています。注意点として、スクリプトパスを用いて使用した場合はスクリプトパスが存在すること及び鍵パスが適用されなかったという情報が漏洩してしまいます。
また、プライバシー上の理由からTaprootの出力は鍵の再利用をしてはいけません。
実装
TODO
後方互換性
SegWit wittnessプログラムのアップグレードシステムを使ったソフトフォークの為、古いソフトであっても使用することができます。ただし、アップグレードをしないとバージョン1SegWit wittnessプログラムを検証することが出来ない為、アップグレードを強く推奨しています。
※６ Witness program というのは、ver.0のSegwitなどで電子署名データやスクリプトのハッシュ値を記録する所
※７ Segwitのトランザクションをどのように検証するかという話ですが、①ver.番号、②Witnessプログラム、
③スクリプトキーScriptPubkeyに入っているデータの外側にWitnessスタックというバイト列のアレイ
の3つを使い検証を行います。
BIP342 Taprootスクリプトについて
設計
Taprootに使われるスクリプト言語使用を定めたのがBIP342です。
今までのBitcoinで使われていたスタックマシンのスクリプト言語が踏襲されますが、一部の改善点を記載されています。
・OP_CHECKSIGおよびOP_CHECKSIGVERIFYはBIP340で定着されているようにSchnorr署名を検証できるようになります。また、BIP341の共通的なメッセージの計算方法に基づいた署名メッセージアルゴリズムを利用するように修正されます。
・OPコードセパレータについての取り扱いが簡略化されています。(OP_CHECKMULTおよびOP_CHECKMULTISGVERIFYの廃止)
・代わりに新しいOPコードとしてOP_CHECKSIGADDが導入され、バッチ検証ができる形で従来と同様なマルチしぐポリシーを作成することが出来るようになります。
・tapscriptは新しく、より簡単な署名OPコード制限として用いており、トランザクションの重量との複雑な相互作用があることを修正しています。
・OP_SUCCESS OPコードを使用するよりOP_NOPを用いるより、より柔軟にOPコード変更をすることが出来るようになります。
仕様
TapscriptとみなされるBIP342の条件として、
・トランザクションの入力がsegwitによる使用
・BIP341で定義されるようなtaprootによる使用
・BIP341で定義されるようなスクリプトパスによる使用
・葉のバージョンが0xc0であった場合、BIP342のTapscriptを使用
Tapscriptの検証として、
1.入力がBIP141またはBIP341に対して無効であれば、失敗とします。
2．BIP341で定義されているようなスクリプト(すなわち、任意の要素であるannexを取り除いた後に残るwittnessスタック要素の第二番目のもの)は、Tapscriptと呼ばれ、一つずつOPコードに出コードされます。
i.OPコードが80,98,126-129,131-138,141-142,149-153,187-254
いずれかに遭遇した場合、検証は成功とします。
ii.いずれかのプッシュOPコードがtapscriptの終端を超えてしまいデコードに失敗した場合には、失敗とします。
3.BIP341で定義されているような初期スタックがいずれかのリソース制限(スタックサイズおよびスタック内の要素のサイズ;以下の「リソース制限」を参照)に違反した場合、失敗とします。このチェックはOP_SUCCESSxを用いることで回避できます。
4.初期スタックを入力として以下のセクションにあるようなルールに基づいてtapscriptが実行されます。
i.何らかの理由によって実行が失敗した場合、失敗とします。
ii.実行の結果、CastToBool()によってtureと評価されるような要素がスタックにただ一つだけ残るよううな場合を除き、失敗とします。
5.失敗に遭遇せず、このステップに達した場合検証は成功とします。
スクリプトの実行
・無効化されたスクリプトOPコード
OP_CHECKMULTISIGおよびOP_CHECKMULTISGVERIFY
・コンセンサスで強制されるMINIMALIF
これにより、OP_IFおよびOP_NOTIF OPコードへの入力員数は厳密に0(からベクトル)または厳密に1(値1を持つ1バイトのベクトル)とならなければいけないことを意味します。
・OP_SUCCESx OPコード
・署名OPコード
OP_CHECKSIGおよびOP_CHECKMULTISGVERIFYはECDSAではなく、
Schnorr公開鍵および署名(BIP340参照)に対して動作するように修正され、
新しいOPコードとしてOP_CHECKSIGADDが追加されました。
・OPコード186(0xba)はOP_CHECKSIGADDと命名されます。
署名OPコードのルール
・与えられた公開鍵に対していくつ正しい電子署名が入っていたかカウントするこ。
・OP_CHECKSIG、OP_CHECKSIGVERIFYは従来通りです。
署名検証
公開鍵pに対して、署名sigを検証するためには:
・Tapscriptメッセージ拡張extを計算します。これは以下を結合したものによって構成されます。
・tapleaf_hash（32）
・key_version（1）
・codesep_pos（4）
・sigが64バイトの長さの場合、Verify(p,hashTopSighash(0x00 ll SigMsg0x00,1)llext),sig)を返却します。ここでverifyはBIP340で定義されているものです。
・sigが65バイトの長さの場合、sig〔64〕≠0x00 and verify(p,hashTopSighash(0x00 ll SigMsg(sig〔64〕,1 ll ext),sig〔0;64〕)を返却します。
・それ以外の場合には、失敗とします。
リソース制限
・スクリプトサイズ制限 10000バイトの最大スクリプトサイズは適応されません。
・非プッシュOPコード制限 スクリプト当たり201個の最大非プッシュOPコード制限は適応されません。代わりにsigops制限が導入されました。
・Sigops制限 署名系のopコードを実行した場合、バジェットが50ずつ減少し、これによりバジェットがゼロを下回った場合、スクリプトはすぐさま失敗します。
・スタック+オルトスタック要素制限
任意のOPコードを実行した後に残る、スタックおよびオルトスタックを合わせた1000要素の既存の制限は存続します。これは初期スタックのサイズに対しても適応されます。
・スタック要素サイズ制限 スタック要素当たり最大で520バイトの既存の制限は、初期スタックおよびプッシュOPコード双方に対して存続します。
以上