Develop with pleasure!

福岡でCloudとかBlockchainとか。

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

BIP Bitcoin MAST

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

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

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

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

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

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

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

そこでスクリプトのパスについてマークルツリーを利用して↑の問題を解消しようというのが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のコントラクトの一般的な手法では、アンロック条件を全て列挙し、これらの条件の検証を１つのスクリプトにプログラムする。ロックされているコインを償還する際は、例えばif/elseのような条件が構成された場合、使用する条件を明示的に選択し、選択した条件を満たす要素をwitnessスタックにプッシュする。

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

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

仕様

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

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

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

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

上記以外の場合は、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を使って同じツリーから２つの鍵が一度に抽出されたことを証明し、続いて同じエントリーが２回使用されなかったことを確認するためビット単位の等価性の証明をチェックする。脆弱なマークルツリーの実装では、バランスの取れていないマークルツリー内に特別なポジションがあり、１つのエントリーに対し複数のプルーフを構築できてしまう。

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

  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でコミットされているマークルツリーに含まれる多くの公開鍵の１つであることを示している。最初のパラメータ2の下位ビットは((2>>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とみなして無視する。プルーフは検証されないがトランザクションは承認される。

*1:https://blockstream.com/2015/08/24/treesignatures.html