Develop with pleasure!

福岡でCloudとかBlockchainとか。

MASTで選択されたスクリプトを実行するtail-callの仕組みを定義したBIP-117

MASTの機能を実現するのに新しくBIP-98とBIP-116とBIP-117の3種類のBIPが提案されている。

BIP-116はスクリプトの条件分岐をフラットにしてMASTのマークツリーを構成した結果、スクリプトで実際に使用する条件(サブスクリプト)がそのマークルツリー内に含まれていることを検証するための新しいopcodeMERKLEBRANCHVERIFYを定義した↓

techmedia-think.hatenablog.com

BIP-98はそのMASTのマークツリーを構成する際に使用する効率的なハッシュ関数やマークルパスを指定する際のエンコード方法を新たに定義した↓

techmedia-think.hatenablog.com

最後のBIP-117は、MERKLEBRANCHVERIFYでマークルツリーへの包含が確認できたあと、実際に使用する条件(サブスクリプト)をスクリプトとして実行するためのプロトコルを定義している↓

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

概要

BIP16 (Pay to Script Hash)とBIP141 (Segregated Witness)は、そこにロックされたコインを使用する際にwitnessのデータの一部としてそのスクリプトの内容を公開するようになっている。どちらの場合も1つのスクリプトだけがコミットされる。これはこのBIPの目標を達成するのには便利だが、コインを使用する際に必要かどうかに関係なく全ての内容を1つのスクリプト内に記載する必要がある。

このBIPはBIP116(MERKLEBRANCHVERIFY)と組み合わせて、実質無制限の条件を持つスクリプトにコミットしつつ、コインを使用する際にその条件のうちコインのアンロックに使用する条件のみを公表するようにする。これにより複雑な条件分岐を持つスクリプトを分岐のないフラットな実行パスに分解し、可能なパスのセット全体にコミットし、使用するパスのみを明らかにする一般化されたMASTの形式を実現する。

動機

BIP16 (Pay to Script Hash)とBIP141 (Segregated Witness)は、ポリシーの公開を使用時まで遅延させることができる。しかしこれらのアプローチは、特定のトランザクションのアウトプットに対してコミットできるのは1つのポリシーのみという点で制限されている。複数のポリシーにコミットすることはできず、使用時にどちらを公開するか選択することはできない。

BIP116(MERKLEBRANCHVERIFY)は複数のデータ要素にコミットし、使用時に必要な要素のみを明らかにすることを可能にする。MERKLEBRANCHVERIFY opcodeは予め選択されたデータのセットに対してのみコミットを提供でき、コード自体を実行することはできない。

このBIPでは、redeem scriptがスタックにポリシースクリプトを配置するために必要なあらゆるタイプの計算を実行できるようにすることで、これら従来の方法のアプローチを一般化する。ポリシースクリプトは、BIP16やBIP141でredeem scriptがwitnessスタックの上から実行されるのと同じように、データスタックの先頭から実行される。特に、scriptPubkeyやredeem scriptでMERKLEBRANCHVERIFYを使うとコイン使用の検証に必要な条件のみを含むポリシースクリプトを選択することができる。これは、事前計算の段階でシンタックスツリーを実行可能なパスに分割し、それらを列挙してポリシースクリプトのマークルツリーハッシュにする一般化されたMASTの形式だ。ポリシースクリプトを実行する前に、コインの使用時に提供されたポリシースクリプトがこのツリーの一部であることは証明される。

仕様

スクリプトの実行が終了した際に

  • 実行した状態がクリーンでない場合、つまり
    1. メインスタック上に複数の要素がある、もしくは
    2. メインスタックに1つの要素があり、アルトスタックが空でない
  • メインスタックの一番上の要素がboolで解釈した際にtrueと評価される、かつ
  • メインスタックの一番上の要素が1バイトでないか、0x51(OP_1)0x60(OP_16)の範囲外の場合

メインスタックの一番上の要素がポップされ、シリアライズされたスクリプトとして解釈され実行される。その際メインスタックとアルトスタックに残っている残りの要素はインプットとしてそのまま残る。

最後の1つを残して上記の条件を満たした場合以下のようになる。

  • 一番上の要素は、0x51OP_1つまりN=2)から0x60OP_16つまりN=17)の範囲のシングルバイトである。

そして、

  • メインスタック上の次のN-1の要素(メインスタック上の要素が全て使われていた場合はアルトスタック上で継続)は520バイトのプッシュで、
  • 続くメインスタック上のN番目の要素(もしくはアルトスタック上)は1〜520バイトのデータ

となる。続いてメインスタック上の一番上の要素がドロップされ、N=2(0x51)〜N=17(0x60)の追加要素がメインスタックからポップされ(メインスタックの要素を全て使い果たした場合はアルトスタックで継続)、逆順でシリアライズされたスクリプトを形成し、両方のスタックの要素をそのインプットとしてスクリプトを実行する。

サブスクリプト内のCHECKSIGCHECKMULTISIGはグローバルなMAX_BLOCK_SIGOPS_COST制限にカウントされず、サブスクリプトで実行される非プッシュopcodeの数はMAX_OPS_PER_SCRIPTで制限されない。上記の例外を除いて、実行状態はサブスクリプトに引き継がれ、サブスクリプトの終了(terminate)はスクリプト全体の実行の終了(terminate)になる。これはtail-callセマンティクスによる実行と呼ばれる。

このようなサブスクリプトのtail-callはスクリプトの実行コンテキスト毎に1つだけ許可され、かつsegwitのredeem script内からのみ許可される。その他のwitnessスタックの評価やscriptPubkeyやscriptSig、P2SHのredeem scriptの実行の際にtail-callセマンティクスが実行されることはない。

論拠

現状、スクリプトを実行した結果スタック上にシリアライズしたスクリプトが残っているとデータ的にはtrueであると評価されスクリプトの検証結果はtrueになる。そのためこのBIPはこのBitcoinのコンセンサスルールを変更するソフトフォークの提案である。サブスクリプトに実行終了の機会を与えるのは、検証ルールをさらに制約することに過ぎない。唯一falseと評価されるスクリプトは空のスクリプト、もしくはスタックに空/ゼロをプッシュするだけのスクリプトだ。これらのスクリプトにはいずれも現実的な効用はないので、ソフトフォークの互換性のためそれらを除外しても欠点はない。

より一般的なEVAL opcodeではなくtail-callの評価に限定することで、実装を大幅に簡略化する。tail-callセマンティクスとは実行結果が呼び出し元のスクリプトのコンテキストに戻らないこと意味し、このため状態を保存したり後で復元する必要もない。実装は本当にシンプルで、スタックからサブスクリプトを引っ張り出して、いくつかの状態変数をリセットし、スクリプトインタプリタの先頭にジャンプバックするだけである。

tail-callの再帰を1レイヤーのみ許可するという制限はあるが、マルチレイヤーにおけるtail-callの再帰をサポートする技術的課題は重要だ。スクリプトデータの使用状況を追跡するためには、トランザクションデータとwitnessサイズの2つファクターについて新しいメトリックを開発する必要がある。この新しいweightは、トランザクションを使って中継され、手数料計算のベースとして使用され、トランザクションの実行でインラインで検証され、違反するトランザクションを伝搬するDoS禁止ピアの方針を決定する。

ただこれらの問題を克服する場合、単一の再帰の制約を解除すること自体もソフトフォークが必要になる。tail-callの再帰を1レイヤーのみ許可することで、マルチポリシーコミットメント/一般化したMASTの主な利点を享受できるが、いつか必要な変更がリソースアカウンティングとP2Pトランザクションの配布に行われた場合の将来の一般化されたtail-call再帰への道は残る。

グローバルSIGOP制限やスクリプト単位のopcode制限はポリシースクリプトには適用されない。これはポリシースクリプトを動的に選択すると一般的に静的解析ツールでこれらの制限を検証することができなくなり、libsecp256k1やBitcoin Coreのパフォーマンスが向上したためこれらの制限は必要なくなった(また検証は一度だけ行えばいい)。検証コストはブロックサイズの制限内でエンコード可能な署名操作の数によって依然として制限されており、インプット単位のスクリプトサイズもまだ10,000バイト以下と制限されている。

これらのグローバルやスクリプト単位の制限を外すため、scriptPubKeyで直接tail-callの評価を実行することは許可されておらず、そういったスクリプトはUTXOからフェッチされ検証されるブロックのブロックサイズの制限にはカウントされない。同様にP2SHのredeem scriptのtail-callも、segwitで修正された二次的な脆弱性のためサポートされない。

汎用的なMAST

tail-callをBIP116 (MERKLEBRANCHVERIFY)と組み合わせると汎用的なMASTの機能を利用できるようになる。スクリプトの作成者はまず使用時に検証する完全なコントラクトの記述から始める。記述したコントラクトの条件分岐を条件の検証とブランチに置き換え、スクリプトを実行する際に通る可能性があるパスを列挙する。実行可能性のあるパスのリストはマークルツリーに入れられ、フラット化されたポリシースクリプトがこのツリーのリーフになる。最後に、資金を送金するredeem scriptは以下のようになる。

redeemScript: OVER HASH256 <root> 1 MERKLEBRANCHVERIFY 2DROP 2DROP
witness: <argN> ... <arg1> <policyScript> <proof>

policyScriptがフラット化されたポリシースクリプトで、proofシリアライズされたマークルブランチとパスでpolicyScriptがマークルツリーrootを構成するのに使われセットの一部であることを証明する。arg1argNpolicyScriptが必要とする引数。OVER HASH256はサブスクリプトをコピーし、MERKLEBRANCHVERIFYで必要なリーフのハッシュ値を準備するのにdouble-SHA256ハッシュを実行する。2DROP 2DROPMERKLEBRANCHVERIFYの検証を終えた際にその検証に必要だった引数をスタックから削除するのに使われる。

上の例は分かりやすくするために設計されているが、実際はsegwit v0スクリプト実行の際のCLEANSTACKルールに違反している。CLEANSTACKルールが新しいsegwitのアウトプットバージョンで削除もしくは変更されない限り、以下のようにアルトスタックを使用する形にスクリプトを変更する必要がある。

redeemScript: [TOALTSTACK]*N OVER HASH256 <root> 1 MERKLEBRANCHVERIFY 2DROP 2DROP
witness: <policyScript> <proof> <arg1> ... <argN>

[TOALTSTACK]*NTOALTSTACKopcodeがN回繰り返されたことを意味する。これはarg1argNをアルトスタックに逆順で移動させ、policyScriptが実行される時にarg1がアルトスタックの先頭に配置する。当然policyScriptもアルトスタックから引数をフェッチするよう変更する必要がある。

ポリシースクリプトのセットの中にさまざまなパラメータ数をとるスクリプトが含まれている場合、合理的な範囲内でサポートすることができる。以下のredeem scriptではポリシースクリプトとマークルプルーフに加え1〜3個のwitness引数を指定できる。

 witness: <policyScript> <proof> <arg1> ... <argN> // N は1〜3
redeemScript: DEPTH TOALTSTACK                    // witness要素の数をアウトスタックに保存
              TOALTSTACK                          // 最初の必須要素をアルトスタックに保存
              DEPTH 2 SUB                         // policyScriptとプルーフを無視して、オプションの数を計算
              DUP IF SWAP TOALTSTACK 1SUB ENDIF   // もし引数の要素が現れたら、オプションの2つ目の要素としてアウトスタックに保存
              IF TOALTSTACK ENDIF                 // もし引数の要素が現れたら、オプションの3つ目の要素としてアウトスタックに保存
              OVER HASH256 <root> 1 MERKLEBRANCHVERIFY 2DROP 2DROP
alt-stack: <N+2> <argN> ... <arg1>

witness要素の数がアルトスタックにプッシュされるため、アルトスタックが通常のスクリプトにアクセスできない場合でも、ポリシースクリプトは渡された引数の数を検証できる。上記のredeem scriptを使用する以下のポリシースクリプトは、アルトスタック上の2つのwitness 要素のみを受け入れ、witnessのmalleabilityを防ぐ。

policyScript: FROMALTSTACK ...check arg1... FROMALTSTACK ...check&consume arg2/arg1&2... FROMALTSTACK 4 EQUAL

数値4にはpolicyScriptproofが含まれていると予想される。

上記の例のような冗長性は、全てのポリシーサブスクリプトのパラメータとして同じ数のwitness要素を使用し、条件及びスタックサイズ数を削除することで回避することができる。将来のスクリプトのバージョンのアップグレードでは、witness/redeem scriptからメインスタックのポリシースクリプトに引数を直接渡せるようにCLEANSTACKルールの緩和も検討する必要がある。

BIP114との比較

BIP114 (Merkelized Abstract Syntax Tree)はBIP141のスクリプトのバージョニングを使って導入するMASTスキームについて定義している。BIP114と異なり、BIP116 (MERKLEBRANCHVERIFY)と共にこのBIPで提案するスキームは、MAST内のポリシースクリプトのメンバーシップを検証するのにスクリプト自体を使ってMAST構造を暗黙的に有効にする。これはMAST自体がプログラマブルであるため、コンセンサスコードの変更が大幅に少なくなるだけでなく、コンセンサスコードの変更を全く必要としない将来のスクリプトベースのイノベーションを可能にする可能性がある。

さらに、NOP拡張スペースを使用する全てのスクリプトMERKLEBRANCHVERIFYとtail-callセマンティクスを追加することで、BIP141のスクリプトバージョニングは不要となる。これによりこの機能をデプロイする際の、アドレスフォーマットをどうするかいった問題、スクリプトのバージョンアップの展開方法、別の機能がv1アップグレードを使用する際の合意、といったハードルは無くなる。

実装

コンセンサスコードの変更とテストを含むこのBIPの実装は以下のリポジトリで確認できる。

https://github.com/maaku/bitcoin/tree/tail-call-semantics

デプロイ

このBIPはBIP-8を使ってデプロイされ、tailcallという名前でbit 3を使用する。

Bitcoinのmainnetでは、BIP8のstartheightがM(未決定)で、timeoutはM+50,400ブロック後。

Bitcoinのtestnetでは、BIP8のstartheightがT(未決定)で、timeoutはT+50,400ブロック後。

CLEANSTACKは、この機能を使用するトランザクションが既にネットワークルールで非標準とみなされているため、例えばBIP68の時よりデプロイは容易になる。

互換性

v0 segwitのルールではスタックに何らかの要素を残すことは禁止されているので、互換性の理由からv0のパラメータはアルトスタックに渡す必要がある。

MASTを実現するMERKLEBRANCHVERIFYを定義したBIP-116

MAST(マークル化抽象構文木)を実現する新しいアプローチとしてMERKLEBRANCHVERIFY opcodeの導入を提案するBIP-116が公開された↓

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

MAST(Merkelized Abstract Syntax Tree)とは?

Bitcoinスクリプトでは IF/ELSEの分岐を使って以下のように複数のアンロック条件を定義することができる。

IF
  2 <アリスの公開鍵> <ボブの公開鍵> 2 CHECKMULTISIGVERIFY
ELSE
  HASH160 <H(x)> EQUAL <ボブの公開鍵> CHECKSIGVERIFY
ENDIF

このスクリプトにロックされたコインは、

  • アリスとボブが協力してマルチシグをアンロックする署名の作成が必要
  • ボブがハッシュのプリイメージを知っていればそのプリイメージとボブの署名が必要

のどちらかの条件を満たせばアンロックできる。つまりアンロックのパスは2つある。

こういったスクリプトはそのハッシュがP2SHの形式でscriptPubkeyに指定され、そのコインを使用する際のインプットのscriptSigに↑のスクリプトと↑のアンロック条件を満たす要素がセットされるようになる。

この一般的な手法には↓の2つの問題がある。

  1. scriptSigにプッシュできる要素数には制限があるので巨大なスクリプトは組み込めないし、スクリプトのアンロック条件が多くスクリプトが大きくなるほどトランザクションサイズも増えるので手数料も増える。
  2. 実際にコインを入手する際に使用するパスは1つだけなのに、使用しないパス(条件)も公開され誰もが参照可能な状態になってしまう(ケースによっては使用されない条件は秘匿したいということも考えられる)。

そこでスクリプトのパスについてマークルツリーを利用して↑の問題を解消しようというのがMASTを使ったアプローチになる。各アンロック条件のパスをそれぞリーフノードとしてマークルツリーを構成し、そのマークルートに資金をロックする。資金を使用する際は、実際にアンロックに使用する実行パスのスクリプトと、それ以外の条件のマークルブランチのハッシュと、使用する実行パスへのマークルパスをscriptSigのスタックに入れる。

こうすると実際にアンロックに使用するスクリプト部分のみが公開され、それ以外のスクリプトは秘匿されたまま、しかし与えられたマークルパスとハッシュから計算したマークルルートとロック時に使われたマークルルートを比較することで、スクリプト全体に対するコミットはされる。また全スクリプトを公開する必要がないことから、どんなに巨大なスクリプトでも構築することができ、scriptSig自体はコンパクトになることから手数料も大きくなることはない。

MASTの提案自体は、Johnson Lauが2016年4月にBIP-114として提案している↓

techmedia-think.hatenablog.com

BIP-114はSegwitによって導入されるwitness programに新バージョンを定義することで使用できるような提案になっており、segwitが導入されるのに時間がかかったこともありデプロイ計画はまだない。

今回のBIP-116は、BIP-114がwitness programの新しいバージョンでMASTをサポートするのに対し、まだ残りがある将来の拡張用のNOP opcodeを使って新しいopcode MERKLEBRANCHVERIFYを導入する仕様になっている。既存のスクリプト内で使用可能になるので非Segwitなトランザクションでも利用可能になる。個人的にはBIP-116の方がシンプルで既存のクライアントとも互換があるので、BIP-116によるMASTの導入に期待したい。

また、デプロイ方法にBIP-8を挙げてるのも興味深い。

techmedia-think.hatenablog.com

具体的なBIP-116の具体的な仕様については、BIPの内容を見てみよう↓

概要

Bitcoinコントラクトの一般的な手法では、アンロック条件を全て列挙し、これらの条件の検証を1つのスクリプトにプログラムする。ロックされているコインを償還する際は、例えばif/elseのような条件が構成された場合、使用する条件を明示的に選択し、選択した条件を満たす要素をwitnessスタックにプッシュする。

この手法には、検証に使われないパスも含め全てのプログラムのパスをscriptPubkeyもしくはredeem scriptを含めなければならないという大きな欠点がある。これはブロックチェーンのスペースを無駄に消費し、プッシュ制限のためスクリプトのサイズを制限することなる。また特定のユーザーに向けたコントラクトであるケースも多く、その内容が全て公開されてしまうためプライバシーやファンジビリティの影響もある。

このBIPでは、スクリプトの作成者が償還時にスクリプトの全体を明かすことなく、償還に使用するスクリプトの1要素もしくは複数の要素のみを明らかにすれば済むように、ソフトフォークでアップグレード可能な新しいopcode MERKLEBRANCHVERIFYを提案する。公開鍵や検証サブスクリプトなどの要素をこれらのポリシーでエンコードし、MERKLEBRANCHVERIFYopcodeを使えば既存のBitcoinスクリプトの制限を克服できる。

仕様

MERKLEBRANCHVERIFYは既存のOP_NOP4 opcodeを再定義して使用する。実行した際、以下の条件のいずれかに当てはまるとスクリプトインタプリタはエラーで終了する。

  1. スタックの要素が3つより少ない
  2. スタックの最初の要素が2バイトより大きい
  3. スタックの最初の要素は整数Nとして解釈され、Nが負の値であるか最小限のエンコードでない場合
  4. スタックの2つめの要素が32バイトでない場合
  5. スタックの3つめの要素がBIP-98で指定されているfloor(N/2) のVERIFYハッシュであるシリアライズされたマークルツリーのinclusion proofではない場合
  6. 残りのスタックの要素にはfloor(N/2)未満の追加要素が含まれており、これらをあわせてインプットスタック要素となる。

Nの下位ビットがクリアな場合N&1 == 0、各インプットスタック要素はdouble-SHA256でハッシュされている。それ以外の場合は、各要素は正確に32バイトの長さである必要がありシリアライズされたハッシュとして解釈される(これらはVERIFYハッシュ)。

スタックの3つめの要素のマークルツリーのinclusion proofのVERIFYハッシュを使ってスタックに示されている順に上から下に計算して算出したfast マークルルートが、スタックの2つめの要素と一致しない場合、スクリプトインタプリタはエラーで終了する。

上記以外の場合は、NOPが実行されたかのようにスクリプトの実行が継続される。

動機

BIP16 (Pay to Script Hash)やBIP141 (Segregated Witness)では両方ともredeem scriptをscriptPubKey外につまりUTXO外に保持することができようにしたが、コインを使用する際にそのコインの全使用条件(redeem script全て)を明らかにしなければならない。これには償還に必要な条件のパスやポリシーが含まれる。この不必要な情報がブロックチェーン上に存在することは非効率なだけでなく、使用されていないスクリプトポリシーが識別される可能性があるためプライバシーやファンジビリティにも影響する。マークルハッシュツリーを使ってポリシーオプションにコミットし、償還時に使用するポリシーのみを明らかにすることで、この情報漏洩は最小限に抑えられる。

マークルハッシュツリーを使ってポリシーにコミットすることで、今までは組み込みのスクリプトサイズや実行時の制限のため不可能だったより複雑なコントラクトの構築が可能になる。ポリシーに対するマークルコミットメントにより、サイズや実行時の制限は全ポリシーの合計ではなく使用するポリシーのみに制限される。

論拠

Satoshiがブロックヘッダのマークルルートの計算に使用したマークルルートの構成には下位プロトコルにmalleabilityを導入する要因となる重複エントリーの脆弱性があるため、MERKLEBRANCHVERIFY opcodeはBIP-98で定義されたfast マークルハッシュを使用する。マークルプルーフにおけるmalleabilityは、MERKLEBRANCHVERIFYを使用するプロトコル脆弱性をもたらす可能性がる。例えばコンパクトな2-of-Nのポリシーでは、MERKLEBRANCHVERIFYを使って同じツリーから2つの鍵が一度に抽出されたことを証明し、続いて同じエントリーが2回使用されなかったことを確認するためビット単位の等価性の証明をチェックする。脆弱なマークルツリーの実装では、バランスの取れていないマークルツリー内に特別なポジションがあり、1つのエントリーに対し複数のプルーフを構築できてしまう。

BIP141 (Segregated Witness)は、スクリプトバージョニングと呼ばれる強力なスクリプトアップグレードの仕組みサポートしており、以前であればハードフォークが必要だったアップグレードをソフトフォークで可能にした。スクリプトバージョニングをこの仕組みを導入すると、MERKLEBRANCHVERIFYはそのインプットを使用するように書くことができ、多くの予想されるユースケースに対して2バイトの節約が可能だ。しかし、スクリプトバージョニングではなく BIP65 (CHECKLOCKTIMEVERIFY)やBIP112 (CHECKSEQUENCEVERIFY)の導入の際に使われたより使い慣れたNOPを使った拡張ソフトフォークの仕組みが以下の2つの理由から採用された。

  1. インフラストラクチャの互換性
    NOP拡張のソフトフォークにすることで、カスタムスクリプトを使用できる既存のソフトウェアでMERKLEBRANCHVERIFYを利用できるようになり、結果BIP143の署名コードを必要とせずP2SHやP2SHでネストされたP2WSHアドレスが使える。これによりMERKLEBRANCHVERIFYスクリプトバージョニングやBIP-143の署名をライブラリやツールがサポートするのを待つことなく、必要なサービスですぐに使用することができる。
  2. スクリプトアップグレードプロトコルの決定の遅れ
    今後のスクリプトのアップグレードに関して、スクリプトバージョニングをどのように使用すべきか未解決の問題がある。将来の拡張用に確保されているスクリプトバージョンは16種類しかないため、希少なリソースとして扱う必要がある。さらに、スクリプト機能のバージョニングはおそらくwitnessに対して定義されるべきで、BIP141のスクリプトバージョニングはwitnessの構造を定義するのにのみ使用されるが、まだそのようなプロトコルは無い。NOP拡張スペースを使用することで(既に利用可能な拡張スペースを利用しているので)、スクリプトのアップグレード手続きが完了するまでMERKLEBRANCHVERIFYが停滞するのを防ぐことができる。

MERKLEBRANCHVERIFY opcodeではVERIFYハッシュを直接提示するか、リーフの値をdouble-SHA256して計算する。ほとんどの場合、後者のアプローチはリーフの値を前処理なくブランチの検証と他の目的の両方に使用できることが期待される。しかし既に計算済みのハッシュをインプットとすることで、チェーンされたMERKLEBRANCHVERIFYopcodeを使って520バイトのプッシュ制限を超えるほど大きなプルーフを持つツリーのブランチを検証することができる。定義されているように、リーフから15番めの内部ノードをルートとして証明し、そのノードのハッシュが実際のマークルツリーのルートハッシュの子であることを証明することで30ブランチパスを検証できる。(ハッシュ値をキーとするバイナリプレフィックスツリーのような)250ブランチパスの検証は、18の連鎖検証が必要だが現在のスクリプトの制限内に収まる。

アプリケーション

1-of-N(Nが巨大な場合)

スクリプトサイズによる線形スケーリングなく、巨大なセット内の任意の鍵でコインを使用するredeem scriptは以下のようになる。

redeemScript: <root> 2 MERKLEBRANCHVERIFY 2DROP DROP CHECKSIG
witness: <sig> <pubkey> <proof>

redeem scriptは標準のpay-to-pubkey-hashにとても似てるが、P2PKHにおいてpubkeyのハッシュがP2PKHのハッシュ(コミットメント)と同じであることを示す代わりに、pubkeyはredeem scriptでコミットされているマークルツリーに含まれる多くの公開鍵の1つであることを示している。最初のパラメータ2の下位ビットは((2>>1) == 1)でインプットが1つある(シリアライズされた公開鍵)ことを指し、そのVERIFYハッシュはdouble-SHA256を使ってMERKLEBRANCHVERIFYで計算する必要がある。

ハニーポット

Pieter Wuilleによって説明されているように*1、1-of-Nのスキームはハニーポットの構築に特に有用だ。サーバー自体の価値よりも大きな特典をつけるのが大事で、サーバーに侵入された場合ハッカーはそのサーバより価値のあるビットコインを入手する=サーバーへの侵入が明らかになる。しかしサーバの数が多い場合(1,000台とか)、各サーバ毎に別々の賞金を確保するととても高額になる。同じ賞金が複数のサーバで共有され、どのサーバが侵入されたか明らかになるのが望ましいだろう。

これには1000個の別々の鍵を生成し、これらの公開鍵のハッシュツリーを構築し、各鍵と関連するマークルパスをそれぞれのサーバに配置することで実現できる。ハニーポットが請求されたとき、前のコインのオーナーは資金の請求に使われた鍵とパスからどのサーバが侵入されたのか知ることができる。

実装

このBIPの実装はコンセンサスコードの更新とテストの両方を含み、以下のリポジトリで公開されている。

https://github.com/maaku/bitcoin/tree/merkle-branch-verify

デプロイ

このBIPはBIP-8を使ってデプロイされ、merklebranchverifyという名前でbit 2を使用する。

Bitcoinのmainnetでは、BIP8のstartheightがM(未決定)で、timeoutはM+50,400ブロック後。

Bitcoinのtestnetでは、BIP8のstartheightがT(未決定)で、timeoutはT+50,400ブロック後。

DISCOURAGE_UPGRADABLE_NOPSは、この機能を使用するトランザクションが既にネットワークルールで非標準とみなされているため、例えばBIP68の時よりデプロイは容易になる。

互換性

古いクライアントはOP_MERKLEBRANCHVERIFYをNOPとみなして無視する。プルーフは検証されないがトランザクションは承認される。

Merkle Treeの重複エントリー問題の解消とパフォーマンスを向上するFast Merkle Treeについて定義したBIP-98

Bitcoinのブロックヘッダにはブロックに入っているトランザクションのリストにコミットするため、各トランザクションのTXIDをリーフノードにしたマークルツリーを構築し、そのマークルルートの値が入れられるようになっている。ブロックにどれだけたくさんのトランザクションが含まれていても、それらから計算されるマークルルートは32バイトの固定値で、その固定値が全てのデータセットのコミットメントになる、とても空間効率の良いデータ構造で、ブロックヘッダのマークルルート以外にも様々な使い方が提案されている。

このマークルツリーの構造の改良について、Fast Merkle Treeという新しい提案(BIP-98)が公開され↓

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

↓のような特徴がある。

パフォーマンスの向上

リーフノードからマークルツリーを構築する際、親ノードの値は2つの子ノードの値を結合し、それをdouble-SHA256ハッシュした値になる。この提案では必ずしもここでdouble-SHA256である必要はなく、これをfast-SHA256という新しく定義する暗号学的ハッシュ関数に置き換えることでパフォーマンスを向上させる。ただこのハッシュ関数はインプットとして2つの32バイトのハッシュ値を持つデータに対してのみ有効なハッシュ関数となる。

脆弱性への対応

マークルツリーの構築アルゴリズムでは、マークルツリーのリーフ要素が奇数の場合、奇数の最後の要素を複製して偶数個にするが、ここに重複エントリーの問題がある。奇数個のリストのアイテムを持つマークルツリーと、奇数個の最後の要素と全く同じ要素を加えて偶数個にしたリストのマークルツリーは、リーフノードの要素数は異なるが、それら計算したマークルルートは同じ値になる。Fast Merkle Treeの場合、要素数が奇数個の場合にその要素をコピーして偶数個にすることをしないことで、この脆弱性を回避する。

データがマークルツリーに含まれていることを証明するInclusion Proofのエンコード方法

マークルツリーにあるデータが含まれていることを示すプルーフ提供の仕組みは、SPVノードなどが受け取るmerkleblockメッセージなどで利用されている。このメッセージには

  • トランザクション数(リーフノードの数)
  • 1つ以上のトランザクションのハッシュと内部ノードのハッシュ
  • マークルツリーの特定のノードに↑のハッシュを割り当てるために使うフラグリスト

が含まれており、これをベースにマークルツリーの部分的な復元や検証をしている。この内、フラグリストには1バイト中に8個のフラグビットがセットされ、そのフラグビットの0 or 1でマークツリー内のノードにハッシュを割り当てるかどうか判断している。

一方このFast Merkle Treeでは、ツリーの内部ノードの数を可変長整数でシリアライズし、その後に内部ノードが持つ2つの子ノードが{SKIP,VERIFY,DESCEND}のどの構成であるか示す3 bitのデータをルートノードから順番にバイト列にパックしシリアライズしたデータでツリー構造を表現するようになっている。

用途

↑のような特徴があるFast Merkle Treeだが、既存のブロックヘッダのマークルルートの計算方法をこれに変えようという提案ではなく(変更するとHFになる)、別で提案されているBIP-116のMERKLEBRANCHVERIFYの実装でこのアルゴリズムを使用するようだ。

詳細についてはBIPの内容を見てみる↓

概要

多くのアプリケーションでは、あるデータがデータセット内のデータであることを証明するのに、データセットの全データを明らかにする必要はない。インナー/内部ノードのラベルがその子ノードのハッシュから生成されるマークルハッシュツリーは、それを実現する暗号化ツールだ。Bitcoinではブロック内のトランザクションをブロックヘッダにコミットするのにマークルハッシュツリーを利用している。Satoshiによって作られたこの設計は、National Vulnerability DatabaseのCVE-2012-2459*1に記載されているように重複したエントリーに関連する深刻な欠陥に悩まされており、また不必要なダブルハッシュにより最適なパフォーマンスとは言えない。

このBIPでは、CVE-2012-2459の脆弱性がなく、最適化したSatoshiのマークルハッシュツリー構造の実装に比べてハッシュツリーの構築および検証時間が55%減少する、より効率的なマークルハッシュツリー構造について説明する。

動機

マークルハッシュツリーは、全ての非末端ノードはそのノードに接続されているノードの値もしくはラベルを結合した値のハッシュ値でラベルされる非循環有向グラフのデータ構造である。BitcoinはSatoshiが考案したユニークなマークルハッシュツリー構造を利用して、ブロック内のトランザクションのリストに対するブロックヘッダのコミットメントを計算している。新しいアプリケーションではこれと同じデータ構造を利用することで、実装の共有やメンテナンスコストの削減が見込まれるが、再利用には3つの欠陥がある。

最初に、Satoshiのマークルハッシュツリー構造は重複したエントリーについて深刻な欠陥があり、そのまま使用するとプロトコルにバグをまねく可能性がある。この欠陥の悪用からプロトコルと実装を保護することは可能だが、この脆弱性を回避する安全なプロトコルを設計するには洞察といくつかの注意が必要だ。新しいプロトコルの設計者はネイティブな実装による下流のバグの可能性を確実に減らすため、可能な限りSatoshiのマークルツリーハッシュ構造の使用を避けなければならない。

第二に、Satoshiのマークルツリーハッシュは不要な数の暗号学的ハッシュ関数の圧縮ラウンドを実行する必要があり、本来の用途として必要な数に比べて、簡単な実装では約3倍の計算時間と検証時間がかかり、目的に特化した実装でも2.32倍以上の計算量が必要になる*2後方互換性を必要としない新しい実装では、不必要な負荷を実行しないハッシュツリーの実装を検討する必要がある。

第三に、Satoshiのアルゴリズムは順序付きリストからツリーインデックスを構築することを前提としているため、ツリー内の全ての要素についてルートからリーフまで均一のパス長をもつバランスの取れたツリーをサポートするよう設計されている。一方、多くのアプリケーションでは不均衡なパス長を持つツリーを活かしている。特に短いパスが使用される可能性が高い場合により効果的だ。Satoshiのハッシュツリーのいくつかの要素を他の要素より短いパスにすることも可能だが、そのためのトリックはツリーのサイズに依存しあまり柔軟ではない。

これら3つの理由は、これらの問題を解決する新しいプロトコルで使用する標準的なマークルハッシュツリー構造を指定する際の正当性を提供する。このBIPではその構造について記述し、実装例を示す。

仕様

このBIPで定義されているマークルハッシュツリーは任意のバランスのバイナリツリーで、その末端のリーフノードはデータのdouble-SHA256ハッシュでラベル付けされ(そのフォーマットは本BIPの範囲外)、内部ノードはその子ノードのラベルのfast-SHA256 から生成された値でラベル付けされる。以下の図はアンバランスなハッシュツリーの例を示している。

https://camo.githubusercontent.com/63c0399d76e6a12ca382745ccceabca5cecdd2e2/68747470733a2f2f676973742e6769746875622e636f6d2f6d61616b752f34316230303534646530373331333231643233653964613930626134656530612f7261772f366536613432623465633930353230376561623162363934303162366363306666666134326232662f756e62616c616e6365642d686173682d747265652e706e67

AおよびBCはリーフラベルで、リーフに関連付けられたデータの32バイトのdouble-SHA256ハッシュである。NodeRootは内部ノードで、そのラベルはそれぞれの子ノードのラベルのfast-SHA256ハッシュである。NodeBCを連結したfast-SHA256ハッシュでラベル付けされる。RootANodeを連結したfast-SHA256ハッシュでラベル付けされ、このツリーのマークルルートである。子ノードが1つだけのノードは許可されない。

double-SHA256暗号学的ハッシュ関数は、任意の長さのデータをインプットとし、FIPS 180-4*3で指定されたSHA256ハッシュ関数を介してデータを実行し、length-extension attack(伸長攻撃)から保護するため同じハッシュを再度実行して32バイトのハッシュを生成する。

fast-SHA256暗号学的ハッシュ関数は2つのハッシュ値を取り、これらを連結して64バイトのバッファを生成し、 カスタム初期化ベクトル (IV)と、メッセージパディング無しでSHA256ハッシュ関数を1回実行する。結果は結合されたハッシュ値と内部ノードのラベルである32バイトのmidstate*4である。変更されたIVは、パス拡張攻撃に対する保護になる。fast-SHA256は2つの32バイトのハッシュに対してのみ有効な定義である。カスタムIVは、以下の16進エンコードされたバイト列について標準のSHA256を実行したmidstateを展開した後に生成される中間ハッシュ値である。

cbbb9d5dc1059ed8 e7730eaff25e24a3 f367f2fc266a0373 fe7a4d34486d08ae
d41670a136851f32 663914b66b4b3c23 1b9e3d7740a60887 63c11d86d446cb1c

このデータは9番目の素数である23の平方根の最初の512小数bitであり、結果得られるmidstateはfast-SHA256暗号学的ハッシュ関数のIVとして使われる。

static unsigned char _MidstateIV[32] =
        { 0x89, 0xcc, 0x59, 0xc6, 0xf7, 0xce, 0x43, 0xfc,
          0xf6, 0x12, 0x67, 0x0e, 0x78, 0xe9, 0x36, 0x2e,
          0x76, 0x8f, 0xd2, 0xc9, 0x18, 0xbd, 0x42, 0xed,
          0x0e, 0x0b, 0x9f, 0x79, 0xee, 0xf6, 0x8a, 0x24 };

fast-SHA256は2つの32バイトハッシュのインプットに対してのみ定義されているので、2つの特殊なケースがある。空のマークルツリーは許可されず、そういったツリーに対してはルートハッシュも定義されない。データが1つだけのマークルツリーの場合、そのルートハッシュはツリーの唯一のリーフノード自身の値と同じになる(パススルー操作でハッシュ計算が行われない)。

論拠

64バイトのデータをFIPS 180-4で指定されているSHA256でハッシュすると(メッセージパディングのため)2回の圧縮が実行され、double-SHA256を計算するのに3回の圧縮が実行される。このためfast-SHA256ハッシュ関数は、用途を特化したdouble-SHA256の実装より2.32倍高速に、通常のSHA256プリミティブを2回適用する実装より3倍高速に計算できる。同様にfast-SHA256のマークルルートの検証は、SatoshiがBitcoinで使用するdouble-SHA256より2倍以上高速に行える。さらにfast-SHA256の実装は一般的なSHA256の実装であり、パフォーマンスコストをかけずに汎用回路やコードへの再利用が可能だ。

fast-SHA256はインプットがハッシュ値で数値と長さが固定されているので、メッセージのパディングやダブルハッシュによる攻撃の影響を受けることはなく、安全に内部ノードのラベル付けを行うことができる。

fast-SHA256の初期化ベクトル(IV)はリーフハッシュや内部ノードのコミットメントが別のリーフハッシュと部分的に衝突するような上位レベルのプロトコルに対する攻撃を防ぐために変更されている。IVはカスタムIVをサポートしていない暗号ライブラリインタフェースとの互換性を保つため、カスタムIVやmidstateからのレジュームをサポートしていない場合、↑の2倍のパフォーマンスを犠牲にして標準のSHA256とmidstateの抽出を行い計算される。ハッシュされたデータは、ハッシュプリイメージが知られていないnothing-up-my-sleeve numberである。2〜19までの最初の8個の素数の先頭bitが既にSHA256自体の設定に使われている定数であるため、その次の9個めの素数23を選択した。次の素数を順番に使うことで一定の因子の再利用による弱点が導入される可能性を減らすことができる。

データ要素が1つしかないツリーのマークルルートハッシュは、何の変更もないリーフハッシュへの単純にパススルーで、スプリットプルーフの連鎖検証を可能にする。これは、Bitcoinスクリプトのプッシュ制限のような検証サイズに制限があるような検証環境において便利だ。連鎖検証により検証者は1つのプルーフを2つ以上に分割することができ、リーフは内部ノードの下に示され、内部ノードがルートの下に示される。データ要素が1つのみツリーにおいてパススルーハッシングでない場合だと、連鎖検証を使うのにチェーンのリンクの数と同じ最小パス数の要件が余計に必要になる。単一要素のパススルーハッシングは1つ以上の連鎖検証の代わりにゼロ長パスからなるNOPプルーフを使うことができ、それにより例えば固定された一連の4つの連鎖検証が長さ3以下のパスを検証できる。

Inclusion Proofs

マークルルートハッシュの使い方で重要なのは、オーダーlog(サイズ)のプルーフで、任意のデータが含まれていることをコンパクトに証明できることだ。このセクションでは、ある複数の要素がツリーに含まれていることを証明するプルーフの標準的なエンコード方法を定義する。

特定のルートを持つマークルツリーにあるハッシュのセットが含まれていることを証明するには次の4つの情報が必要になる。(この要素は既存のマークルツリーの場合と同じ)

  1. マークルツリーのルートハッシュ
  2. 検証されるハッシュ値。通常データ要素のdouble-SHA256で構成されるが、それか内部ノードのラベルかその両方。
  3. ルートから対象のハッシュがあるノードへのパス(シリアライズされたバイナリツリー構造として表現される)。
  4. それらのパスに含まれないブランチ(ノード)のハッシュ値

通常↑の最後の2つの要素(パスとパスを辿らないブランチのハッシュ)をまとめてプルーフと呼んでいる。

シリアライズする際は、まずプルーフ内の内部ノードの数Nを可変長整数(Varint)としてエンコードする。次にツリーの構造を、深さ優先で左から右、前順・先行順・前置順・行きがけ順で各内部ノードを走査する前提で、各ノードの構成をパックした3bit表現でエンコードする(ノード数Nに応じて(3*N + 7) / 8バイト消費する)。続いてスキップするハッシュの数(プルーフの中に含まれるハッシュ、プルーフで検証しないもの)は、可変長整数(Varint)でシリアライズされ、その後にプルーフで明かされるハッシュ自体が順番に続く。

以下の図のように8個の内部ノードの構成が可能だ。

https://github.com/maaku/bips/raw/b124dc51abad9b9533c9310dfbbc6ec17bbe3984/bip-0098/node-variants.png

この図では、DESCENDは"..."とラベル付けされた子グラフ要素で表されている別の内部ノードへの分岐リンクを意味する。SKIPはそのブランチに省略されたサブツリーのハッシュか要素のハッシュが含まれていることを意味し、このブランチのサブツリーのfast-SHA256ルートハッシュかデータ要素のdouble-SHA256ハッシュのどちらかがプルーフデータの中に含まれている。VERIFYはそのブランチにプルーフの検証に必要なwintessとして外部から提供されたハッシュが含まれていることを意味する。表形式にするとこれらのコード値は以下の通り。

コード Left Right
000 VERIFY SKIP
001 VERIFY VERIFY
010 VERIFY DESCEND
011 DESCEND SKIP
100 DESCEND VERIFY
101 DESCEND DESCEND
110 SKIP VERIFY
111 SKIP DESCEND

この3つのbitコードは3バイト毎に8つのコードが収まるようバイト列にパックされる。バイトを埋めていく順序は最上位bit0x80で始まり、最下位bit0x01で終わる。内部ノードの数が8の倍数でない限り、シリアライズした最終バイトは下位bitが余ることになり、この余りのbitには全てゼロがセットされなければならない。

ツリーのシリアライゼーションは自己分割であることに注意すること。ツリー構造を追跡することで、プルーフの校正者はパーサーがいつ最後の内部ノードに到達したかを知ることができる。プルーフ内にシリアライズされた内部ノードの数は、ツリー構造自体から推論されるノード数と等しくなければならない。同様に、SKIPハッシュの数はシリアライズされたツリー構造から推論することもでき、プルーフ内のハッシュの数と等しくなければならない。

(内部ノードが無い)シングルハッシュプルーフはN=0で、(内部ノードが無いので)ツリー構造もシリアライズされずSKIPハッシュの数は0または1のいずれか。

次のマークルツリー構造を考えてみよう。

https://github.com/maaku/bips/raw/b124dc51abad9b9533c9310dfbbc6ec17bbe3984/bip-0098/traversal-example.png

この構造では6個の内部ノードがある。深さ優先で左から右、前順・先行順・前置順・行きがけ順で探索するとA→B→→D→F→C→Eの順に回る。3つのSKIPハッシュがあり、0x00... → 0x66... → 0x22...の順に回る。残りの4つのハッシュは実行時に提供されプルーフにより検証される。

  Byte 1 Byte 2 Byte3
Bits 76543210 76543210 76543210
Nodes AAABBBDD DFFFCCCE EE------
Code 10111101 10000100 01000000

リアライゼーションは内部ノードの数の可変長整数(Varint)で始まるので↑だと0x06、次にツリーのシリアライゼーション自体(↑だと0xbd8440)が続く。次のSKIPハッシュの数も可変長整数としてエンコードされ↑だと0x03、その後に3つのハッシュが順番に続く。結果101バイトのプルーフBase64で以下のようにエンコードされた値となる。

Br2EQAMAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmREREREREREREREREREREREREREREREREREREREREREQ=

論拠

内部ノードの3 bitエンコードは、左右のブランチがそれぞれ{DESCEND, SKIP, VERIFY}のいずれかであるかを示す構成をエンコードすることができる。この他、除外された第9のパターンとして、左右のブランチが両方共SKIPであるパターンがある。

https://github.com/maaku/bips/raw/b124dc51abad9b9533c9310dfbbc6ec17bbe3984/bip-0098/skip-skip.png

このパターンは検証のため許可されていない(そのブランチ自体へのSKIPと同じことであるため)。この2つのSKIPブランチを持つノードを不許可にすることで、プルーフのmalleabitiyの原因を排除している。

プルーフを検証するために必要なハッシュ計算の回数は、ハッシュの数(SKIPとVERIFYを合わせた数)より1つ少なく、内部ノードの数Nと等しい。可変長整数エンコーディングにはシリアライズされた数値も辞書順にソートされたものも数値順にソートされるという性質がある。最初にシリアライズされるのは内部ノードの数であるため、プルーフを辞書順にソートすることはプルーフの検証に必要な作業量でプルーフをソートする効果がある。

プルーフの検証のためのインプットとして必要なハッシュの数は、N+1からSKIPハッシュの数を引いたもので、ツリー構造を解析することなく素早く計算することができる。

シリアライズされたツリー構造のコーディングルールとパッキングルールは辞書比較を有効にするため選択された。もし完全に拡張されたツリー(SKIPが無く全てVERIFYの)を左から右に深さ優先で要素のリストをエンコードするとみなした場合、欠損している値のハッシュをSKIPし、SKIP,SKIPノードを再帰的にプルーニングすることでリストのサブセットのプルーフ抽出することができる。結果得られるシリアライズされたツリー構造を辞書順に比較することは、派生したプルーフによって検証されたオリジナルのリストからインデックスのリストを比較するのと同じことである。

内部ノードの数とSKIPハッシュの数はツリー構造から抽出可能であるため、プルーフ内の可変長整数は両方とも冗長で省略可能だ。しかし、そうするとシリアライゼーションと検証の両方で、デシリアライズの際にメモリ上に明示的にツリーを構築・保持する必要があるか、比較的複雑なツリー解析コードの複製が必要になる。そのため(単一ハッシュのエッジケースの場合も同様)、冗長だが内部ノードの数とSKIPハッシュの数を明示的にシリアライゼーションし、プルーフが有効であるためにはその2つの値がツリー構造から推測される値と一致しなければならない。これによりデシリアライズが簡単になり、検証のタイミングまでツリーの構築を遅らせることができる。これには対数時間の検証アルゴリズムが有効になるという追加のメリットがある。

Fast Merkle Lists

多くのアプリケーションではマークルツリーを使用してリスト内の要素についてのインデックス化やコンパクトなメンバーシップ証明を提供する。この仕組はいろんな長さのリストのための標準的な平衡木構造を構築するアルゴリズムを指定する。このアルゴリズムには、重複エントリーに関連する脆弱性を構造的に防止するため、Satoshiのアルゴリズムとは微細だが重要な点で違いがある。

  1. まず任意のデータ文字列のリストがある。
  2. リストの各要素をそれぞれdouble-SHA256ハッシュした値に置き換える前処理を行う。
  3. リストが空の場合は、ゼロハッシュを返す。
  4. リストに2つ以上の要素がある場合は
    • リストの隣接するエントリーを結合し、fast-SHA256ハッシュに渡す。リストの要素が奇数の場合、最後の要素をそのまま残す(これにより脆弱性を修正する)。このステップでN個のリストの要素をceil(N/2) 個のエントリーに減らす。
  5. リストに残った最後のアイテムがマークルルートである。

このアルゴリズムBitcoinで使われているマークルリストと2つの点で異なる。1つめは、内部ノードのラベル付けにdouble-SHA256でなくfast-SHA256が使われる。2つめは、奇数長のリストの最終エントリーは重複してハッシュされない。これはCVE-2012-2459につながった間違いだ。

実装

このBIPのマークルブランチの抽出と高速なマークルブランチの検証は以下のGithubリポジトリで利用可能だ。

https://github.com/maaku/bitcoin/tree/fast-merkle-tree

このリポジトリにはこのBIPのアルゴリズムを使用してルート値の計算と任意ツリーのinclusion proofsの抽出および値のリストからツリーを構築するmerklebranch RPCと、2つ以上のマークルinclusion proofsを統合する(SKIPハッシュを別のproofから抽出したサブツリーに置き換える)ためのmergemerklebranch RPCが含まれる。

デプロイ

このBIPは、BIP-116(MERKLEBRANCHVERIFY)がソフトフォーク用のNOP拡張opcodeを使用してMerkle inclusion proof の検証をスクリプトに追加するために使用される。MERKLEBRANCHVERIFYのデプロイはこのBIPの内容を決定的にするだろう。BIP-116のデプロイ計画はそのBIPの本文に記載されている。

*1:bitcoind及びBitcoin-QTの0.6.2より前のバージョンにあったDoS攻撃脆弱性で、マークルツリーのリーフに重複したトランザクションを配置してブロックハッシュを衝突させ、同じハッシュを持つ正当なブロックを受け入れられないようにする。

*2:2017年9月にPieter Wuilleとの個人的なコミュニケーションの結果、ハッシュ関数の各ステージのインプットが固定長であるという知識を利用することで、Satoshiのマークルツリー構造ハッシュ集約関数について、Wuille氏は64バイトデータのdouble-SHA256ハッシュの計算にかかる時間を22.7%短縮することができた

*3:Federal Information Processing Standard(FIPS) PUB 180-4

*4:SHA256はデータを64バイト毎のチャンクに分割し処理を行う。チャンク毎に、データを分割→拡張→圧縮という工程を経るが、この時の圧縮してできたデータがmidstateで、次のチャンクで圧縮処理をする際に使用される。

SIGHASH_FORKIDとfork idを使ったリプレイプロテクションの仕組み

8/1にBitcoin Cashが分岐した際、BTCとの間のリプレイアタックに対する保護の仕組みを組み込む必要があり、この時SIGHASHを利用する仕組みが導入された。

spec/replay-protected-sighash.md at master · Bitcoin-UAHF/spec · GitHub

最近分岐したBitcoin Gold(BTG)も同じ仕組みを採用したようだ。

SIGHASH_FORKID

通常トランザクションに署名する際には、トランザクションのどのスコープまで署名するか決めるのにSIGHASH TYPEと呼ばれるものをセットするようになっている↓

techmedia-think.hatenablog.com

基本となるSIGHASH_ALLSIGHASH_NONESIGHASH_SINGLEの3つタイプにSIGHASH_ANYONECANPAYというフラグを組み合わせることで計6通りの署名スコープをセットできるようになっている。
(ほとんどのトランザクションSIGHASH_ALLを使っている。)

フォークを識別するため、SIGHASH_ANYONECANPAYのように追加されたフラグがSIGHASH_FORKIDで以下の値がフラグとして決められている。

SIGHASH_FORKID = 0x40

HF後、このフラグがセットされていないトランザクションはBCHやBTGのブロックチェーン上では無効なトランザクションと判断される。尚、BTCのチェーンでは、セットされているSIGHASH_TYPEからSIGHASH_ANYONECANPAYを除去した結果、その値がSIGHASH_ALL(0x01)SIGHASH_SINGLE(0x03)の間でなければ署名のエンコードチェックでエラーになる。つまり、 SIGHASH_FORKID(0x40)フラグがセットされていればエラーになる。

署名スコープがSIGHASH_ALLでBCHやBTGのトランザクションの署名を作る際、そのSIGHASH TYPEは

SIGHASH_ALL(0x01) | SIGHASH_FORKID0x40) = 0x41

になる。

実際にBitcoin Cashトランザクション

https://www.blocktrail.com/BCC/tx/50c22f9cb1fbeec34fb9a77fdd54bcfa65c6ae65deebc6e06655867d0d659b3d

のインプットのscriptSigを見てみると↓

304502210085b726543e566fe2921f801f548e18bfb67662de920f0264bee6086e610af553022011103703f8cbc19c33c213e546da169434f3334c20f456fdf36fd2ea33fe4e1b41 
033489bdf777f135fa9ab0f31bd795a60a56d7daddc0ae18c6c1ad4d8589d2c72e

1つめの要素が署名で2つめの要素が公開鍵。署名の最後にはSIGHASH TYPEをセットする決まりなので、上記から41 = SIGHASH_ALL | SIGHASH_FORKIDになっていることが分かる。

Bitcoin Goldのトランザクションも↓

https://btgexp.com/api/getrawtransaction?txid=6673dd19df842c2777201718d95edca600f72de6bf508727604ddb0834212323&decrypt=1

41 = [ALL|FORKID]が適用されていることが分かる。

fork id

BCHもBTGもどちらもSIGHASH_FORKIDフラグが付与されているのは分かったが、これだけだとBTC⇔BCH,BTGのリプレイ保護にはなるけどBCH⇔BTG間のリプレイ保護にはならない。そのため共通のSIGHASH_FORKIDフラグとは別に各チェーンを識別するためのfork idが存在する。各チェーンのfork idの値は以下の通り。

チェーン fork id
BCH 0
BTG 79(金の原子番号

このfork idは、署名対象のトランザクションのダイジェストデータであるSIGHASHを生成する際に加味される。BCHもBTGもトランザクションのダイジェストデータを生成する仕様は、BTCのsegwitで導入されたBIP-143のルールに従う↓(BCHはsegwit導入はしていないけどこの仕様だけは導入している)

techmedia-think.hatenablog.com

オリジナルのBIP-143と唯一違うのは、このSIGHASHを生成する際に使用するSIGHASH TYPEの最上位bitにfork idを含める点だ。BCHのfork idは0なので実質何もする必要はないが、BTGの場合は79なので↓のようにSIGHASH TYPEにfork idのビット和を適用する必要がある。

hash_type = hash_type | (79 << 8)

これにより、BTGのトランザクションをBCHのチェーンで署名検証すると、署名対象データであるSIGHASHを生成する際に使用する値(fork id)が違っているので署名検証に失敗し、リプレイ攻撃から保護できるという仕組みだ。

以上のSIGHASH_FORKIDfork idがリプレイプロテクションの仕組みなので、この仕組みを採用しているBTC派生チェーンで有効なトランザクションを作成する際は、

  1. トランザクション署名時のSIGHASH TYPEにSIGHASH_FORKIDフラグを適用
  2. SIGHASH生成時に使用するSIGHASH TYPEの最上位bitにfork_idを適用(BCHのみ省略可)

すれば、それぞれのチェーンで有効なトランザクションが生成できる。トランザクションについては他はBTCと変わらないみたいなので、各チェーンのコインを送金したい場合は↑のルールに則って署名すればいいだけ。

気になる点

  • この仕組みはSIGHASHを使った仕組みなので、当然ながらOP_CHECKSIGOP_CHECKMULTISIGを使用せず署名検証が必要のないスクリプトの場合、リプレイ保護は提供されない(まぁほとんどは署名検証をするスクリプトになっているということだろう)。
  • SIGHASH_FORKIDは署名の最後のSIGHASH TYPEを確認すれば簡単に分かるが、fork idはSIGHASH生成時の1要素なだけなので署名データから明示的に確認する方法はなく、そのチェーンで有効なfork idなのかは署名検証するまで分からない。
  • 署名検証のコストも考慮すると、ネットワークのservice bitsなんかで互いを識別して接続しないようにするとかした方が、各ノードが無駄なコストを負担しなくて済むように思うけどどうなんだろう?

Scriptless Scriptで実現するAtomic Swap

Atomic Swapといえば同じハッシュ関数とタイムロックの仕組みを持つブロックチェーンであれば、それぞれのチェーンの通貨をトラストレスに交換することができるプロトコルで、最近だとBitcoinやLitecoin、BitcoinとEthereumでAtomic Swapの事例が出てきている。

ハッシュのプリイメージとタイムロックの仕組みを使ったこのプロトコルの詳細は↓

techmedia-think.hatenablog.com

このプロトコルでは、各チェーンで以下のようなスクリプトにコインをロックしている。

IF
  2 <アリスの公開鍵> <ボブの公開鍵> 2 CHECKMULTISIGVERIFY
ELSE
  HASH160 <H(x)> EQUAL <ボブの公開鍵> CHECKSIGVERIFY
ENDIF

↑はBitconのスクリプト言語だが、Ethereumでは同様の機能を持つContractを実装することになる。

ハッシュのプリイメージとタイムロックを使うこのプロトコルには、2つのチェーンにおいて同じプリイメージ及びそのハッシュを使用しているのでチェーン間のトランザクションがリンクできるというプライバシーの課題がある。MASTが利用可能になれば取引の当事者が協調することでこの課題を解消する方法もあるが、こういったハッシュのプリイメージを使用するスクリプトを使わずに暗号技術を使ってAtomic Swapを実現するScriptless Scriptというアプローチがある。

スクリプト無しでどうやってAtomic Swapを行うかは、Scaling Bitcoin 2017でもScriptless Scriptsについて話をしたBlockstreamのAndrew Poelstraが、以下のドキュメントに書いている。

github.com

内容についてざっと見てみる。

Schnorr署名とAdaptor Signature

Scriptless Scriptを構成する要素がSchnorr署名とAdaptor Signatureになる。楕円曲線のジェネレータをGとし、Hをビット文字列の空間から(Gの位数を法とする整数である)スカラーグループにマッピングするハッシュ関数としたとき、公開鍵Pを有するメッセージmのSchnorr署名は以下の式を満たす(s, R)のペアになる。

sG = R + H(P || R || m)P

これに関連するAdaptor Signatureは以下の式を満たす(s', R, T)として定義される。

s'G = T + R + H(P || R || m)P

Schnorr署名(s, R)とAdaptor Signature(s', R, T)から(それぞれRが同じであることに注意)、Tの離散対数をs' - sで計算することができる。上記の式を減算すると(s' - s)G = Tになるため。

同様に、Adaptor Signature(s', R, T)T = tGとなるtが与えられると、s = s' - tでSchnorr署名(s, R)を計算することができる。

公開鍵Pを有するAdaptor Signature(s', R, T)が与えられると、同じP及びRを有するSchnorr署名の知識はTの離散対数の知識と等しいと結論付けることができる。

このAdaptor SignatureがAtomic Swapのハッシュのプリイメージの代わりに使われる。

Schnorr署名のマルチシグ

Schnorr署名には複数の署名を集約することができる特性がある。公開鍵PQを持つ2人の当事者が対話的にPQのマルチシグを作成することが可能だ。署名のコンポーネント(s, R)は、両当事者の提出した署名鍵の合計になる。まず最初に両当事者は署名で使用するRの値について同意し、続くステップで各当事者がそれぞれの署名鍵を提供しsを作る。

スクリプトレスなAtomic Swapのプロトコル

スクリプトレスなAtomic Swapは↑のSchnorr署名のマルチシグとAdopter Signatureを組み合わせたプロトコルになる。

アリスはAチェーンに、ボブはBチェーンにコインをそれぞれ持っており、それぞれのチェーンのコインをアトミックに交換したい場合、以下の手順でAtomic Swapを行う。

f:id:techmedia-think:20171111133601p:plain

  1. まずアリスとボブはそれぞれコインを持っているチェーンで、使用するには両者の署名が必要なマルチシグのアウトプットにコインを入れる。またこの時、最終的にコインを償還する際の署名に使用するRの値についてお互いに合意する。
  2. 続いてアリスはランダムな値tを生成し、T = tGを算出する。続いてマルチシグの署名値のsを作成するためのアリスの署名鍵を渡す代わりにAdaptor Signature(s', R, T)を生成して、ボブに送る。(T + R + H(P || R || m)PPの部分はマルチシグなので、おそらくアリスの公開鍵とボブの公開鍵を結合したものになる)
  3. ボブは受け取ったAdaptor Signatureを検証し問題なければ(各チェーンのAdaptor Signatureで同じTが使われている=離散対数が同じことをを確認する)、マルチシグの署名データsに必要な自分の署名鍵を明らかにする。
  4. アリスはボブから受け取った署名鍵と自分の署名鍵を組み合わせてsを導出し、マルチシグの署名(s, R)を完成させる。それをパブリッシュしてコインを入手する。
  5. ボブは手順2でアリスから受け取ったAdaptor Signatureと手順4でアリスが公開した署名からシークレットtを計算する(Schnorr署名とAdaptor SignatureからTの離散対数tを計算できる)。算出したtを使ってアリスの署名鍵を計算する。
  6. ボブは計算したアリスの署名鍵に自分の署名鍵を加えて署名を完成させ、その署名でコインを入手する。

※ 手順2でアリスからAdaptor Signatureが送られてこなかったり、2つのAdaptor SignatureのTが違っていたり、手順4でアリスがトランザクションをブロードキャストしない場合、予めlocktimeを設けていた払い戻し用のトランザクションをブロードキャストして自分のコインを取り戻す。

という手順でSchnorr署名のマルチシグとAdaptor Signatureを利用することで、スクリプトを書くことなくクロスチェーンのAtomic Swapを行うことができる。

この時ブロックチェーンに記載されるのはSchnorr署名のデータのみであるため、アリスとボブの間でAtomic Swapが行われたことを他のユーザーが検知することはできず、プライバシーに優れている。

↑のプロトコルはAtomic Swapを行う各チェーンで同じ楕円曲線を使用する前提になっているが、Scaling Bitcoin 2017でのAndrew Poelstraのセッションでは今後異なる楕円曲線間(Bitcoinのsecp256k1とMoneroのed25519など)のスワップのサポートを追加していくとのこと。

Andrew Poelstraの記事を読むことで、Scriptless Scriptの仕組みがふんわりと分かった気がする。Schnorr署名は単純に署名を集約してサイズ削減するだけでなく、こういった暗号学的なトリックに使うことができるのは面白い。バックボーンの原理についてはよく分かってないので勉強しないとなー。