witプロトコルを利用したBeam Sync

こないだGethに導入された新しい同期方法Snap Syncについて書いたけど↓

techmedia-think.hatenablog.com

今回は、Beam Syncという同期方法↓

https://github.com/ethereum/stateless-ethereum-specs/blob/master/beam-sync-phase0.md

を調べてみる。

Beam Syncの同期方法

Beam SyncもSnap Syncと同様、スタンドアロンの同期プロトコルではなく、既存のethプロトコルと一緒に動作する同期方法になる。

現在Gethのデフォルトの同期方法であるFast Syncは、現在のブロックのステートをピアからダウンロードすることで、同期速度を向上させるアプローチを採っている。ただ、それでも同期には結構時間がかかり、ノードとして機能できるまで待つ必要がある。

これに対し、Beam Syncは、最新のブロックを選択し、そのブロックを実行しながらそのブロックで必要とされるステートをピアからオンデマンドに取得することで、クライアントが初期起動後すぐに利用可能にできるようにしようというアプローチを採っている。

基本的な処理のフローは：

1. 先頭ブロックを選択すると、そのブロックの全トランザクションを実行する。
2. EVM実行中に、必要なステート（アカウントの残高やストレージのデータ、コントラクトのバイトコードなど）を保持していない場合、EVMを一時停止する。
   1. 不足しているステートのトライノードをリモートピアに要求する。
   2. ステートがダウンロードできたら、EVMの実行を再開する。
3. EVMの実行がすべて終わると、次のブロックを処理する。

もちろん、ブロックで必要とされるステートだけを常にオンデマンドで取得していたのでは、完全なステートツリーを構築することはできないので、バックグラウンドで不足しているステートをピアから随時ダウンロードする。この２つの処理を並行して実行することで、クライアントを素早く利用可能にしようというアプローチだ。完全にステートツリーが同期されると、その後は他の同期モードと同様Full syncに移行する。

Ethereumの研究用クライアントの１つであるTrinityがこのBeam Syncを実装しており、こないだ、新規クライアントを起動後80秒で先頭のブロックの検証を終えたという内容が投稿されていた↓

snakecharmers.ethereum.org

ステート入手の課題

一見すると、シンプルなソリューションに見えるけど、オンデマンドでデータを入手する際のパフォーマンスが重要なポイントになる。

初回起動時には、ステートを１つも持っていないので、その状態でブロックを処理すると、EVM実行中にすぐにアカウントの残高など必要なステートを要求することになる。ただ、そのステートをリモートピアに要求するにしても、アカウントのキーを指定したらそのステートを返ってくるような単純な処理ではない。ethプロトコルで定義されているGetNodeDataメッセージは、Merkle Patricia Trieのツリー上のノードのハッシュを指定してそのトライノードのデータを要求するメッセージで、アカウントであればツリーのリーフノードにその残高等のデータが保持されている。

つまり、アカウントのステートを取得しようとすると、そのツリーのルートノードからリーフノードまでのすべてのトライノードのハッシュの情報が必要になり、これを取得するためにルートノードから順番に子ノードのハッシュを知るためにGetNodeDataを実行していく必要がある。現在のmainnetではアカウントのステートが保持されているのはルートから大体7階層めくらいとされているので、その分のGetNodeData/NodeDataのやりとりが必要になる。

ピボット

オンデマンドでステートを要求しながらブロックの全トランザクションを実行していくと、リモートピアとのRTTなども影響し、ブロックタイムが15秒なので、処理が完了するまでに次のブロックが到着するということが容易に想像できる。また、クライアントによって異なるがGethだと直近128ブロックのステートをインメモリで保持しているが、それを超えたブロックの処理を続けるようなケースになるとリモートピアからステートが取得できなくなり処理がスタックしてしまう。

そのため、チェーンの先頭から離されると、そのブロックの実行を中止し、再度先頭のブロックを選択し、そのブロックの実行するようピボットする必要がある。このピボットを繰り返しながら、ローカルのステートを満たしていくことで、ピボットの機会は減っていく。

Beam Syncを使った実験で、起動後22時間経過しても、１つの新しいブロックを処理するのに中央値で約300の新しいトライノードを必要とする模様。

witプロトコルによる高速化

↑のステート入手を高速化するため（最終的にはステートレスクライアントを支援するため）にdevp2p上に設計されたのがwitプロトコル↓

https://github.com/ethereum/devp2p/blob/master/caps/wit.md

現状このプロトコルのバージョンは0で、以下のP2Pメッセージが定義されている。

• GetBlockWitnessHashes(0x01)：
  指定されたブロックで使用されるトライノードハッシュのリストを要求するメッセージ。
• BlockWitnessHashes(0x02)：
  指定されたブロックの実行および検証中に読み取られたトライノードのリストを返すメッセージ。

witというのはwitnessから来ており、ステートレスクライアントで必要となるステートをwitnessとして提供するのが目的だと思われるが、↑のメッセージからもわかるように現時点ではwitnessは提供されず、そのメタデータ（ハッシュ）のみを提供するプロトコル仕様になっている。

Beam Syncではこのwitプロトコルを使うことで、ブロック内のトランザクションを実行する際に必要となるトライノードのハッシュを事前にリストで取得できるようになる。この結果、Beam Syncのオンデマンドのステート取得の際に余分なGetNodeData/NodeDataのやりとりをしなくて済むことになり、同期速度を向上させることができる。↑のTrinityの80秒で利用可能にしたというのも、このwitプロトコルを使った結果。

もちろん、この高速化のためには、リモートピアがwitプロトコルに対応している必要がある。ただ、witに限らず、Beam Syncのノードは直近のブロックの実行に必要なステートを保持しているノードでもあるので、Beam Syncノードは互いにデータを提供でき、ネットワークに多くのBeam Syncノードが参加しても、ステートの要求はそれらの間で分散して共有される可能性がある。

というのがBeam Syncの仕組み。フェーズ0〜フェーズ2までの段階があり、witを使った高速化がフェーズ１。フェーズ２はブロックヘッダーにwitness proofを追加するコンセンサスの変更が必要なので、まだ先っぽい。

ステートレスクライアントのためのVerkle Trie

Ethereumのスケーラビリティを考えた際にネックになるのが巨大なステートストレージ。利用者は１回だけ手数料を積んだトランザクションを発行するだけだけど、ネットワークに参加するフルノードは以降ずっとそのデータを維持しなければならず、ステートの成長とともに維持コストも膨れ上がりネックになる。

この問題へのアプローチの１つとして、ステートレスクライアントというアイディアがある。全ステートに対する暗号学的なコミットメントが、Ethereumのブロックヘッダーにステートルートという形で記録されている。ブロックの提供者に各トランザクションがアクセスするステート自体とそれが有効なステートであることの証明をセットで提供してもらうことで、ノードがそのストレージにステートを保持しなくて済むようにしようというもの。

Merkle Patricia Trieの包含証明

あるステートが有効かどうかはMerkle Patricia Trieのアイテムの包含証明を提供することで検証可能だ。web3-ethでもこのプルーフを取得するための関数getProofが提供されている。

Bitcoinのような二分木であれば、各ノードは2つの子ノードしか持たないため、ルートから対象のリーフノードまでのパス上にある兄弟ノードの数分の各ノードのハッシュ値がプルーフになる（）。

一方、Merkle Patricia Trieのような16-ary(hex-ary)ツリーは、16個の子ノードを持つ。つまり各ノードが最大16個の子ノードのハッシュ値を持っている。そのため、単一のアイテムの包含証明には、ツリーのルートからそのアイテムがあるリーフノードまでのツリーの経路上のノードデータがプルーフとして必要になる。厳密にいうと、ルートノードは既知であるから必要なく、それ以外の経路上のノードデータの内、関係する子ノード以外の兄弟ノードのハッシュ値になるので15個のハッシュ。これらがあれば、リーフノードのデータから各ノードのハッシュを計算し、上位ノードの兄弟ノードのハッシュ値（プルーフ）を計算しながらツリーをたどり、ルートノードの子ノードのハッシュ値と合致すれば、アイテムがツリーに包含されていることを検証できる。ちなみに↑のgetproof関数は、兄弟分とかは関係なく経路上のノードの全データを返してるっぽい。

ステートレスクライアントのようなアプローチをする場合、現状のMerkle Patricia Trieだと上記のように１つのプルーフあたりのデータが必要になり、これがネックになる。

Verkle Trie

↑の課題を解消するために提案されているのがVerkle Trieという木構造とKZGコミットメントのアキュムレーター構造を組み合わせたもの↓

https://notes.ethereum.org/_N1mutVERDKtqGIEYc-Flw

Verkleという名前はVectorとMerkleから取った模様。Verkle Trieでは、プルーフの生成に多項式コミットメントスキームの一種であるKZGコミットメントを使用している↓

techmedia-think.hatenablog.com

一般的に、マークルツリーはn個の要素に対するベクトルコミットメントとして機能するが、多項式コミットメントも、n次の多項式にコミットするように構成すれば、n個の要素に対するベクトルコミットメントとして機能する。

そしてこの多項式コミットメントスキームの利点は、ベクトル内のアイテムの包含証明が、アイテムの数に依存せず、一定サイズになるという点（アキュムレーターのように機能する）。これによりステートレスクライアント導入にあたって、ステートの存在証明のサイズを小さな一定サイズにすることができる。

Verkle Trieのアイディアは、16個の子ノードを保持するMerkle Patricia Trieの内部ノードをKZGコミットメントに置き換えたKZGコミットメントのツリーを構成しようというもの。

中間ノードのKZGコミットメント

システムパラメータとして16個の楕円曲線上の点が与えられるので（Gはそのベースポイント）、それと16個の子ノードの各データ（おそらくハッシュ値）をを使って、

を計算すれば、これがその中間ノードのKZGコミットメントになる。

見ての通り、このコミットメントは楕円曲線の1要素なので、サイズは使用する楕円曲線に依存するがBLS12-381とかだと48バイトくらいのはずで（KZGコミットメントにはペアリングが可能な曲線が必要）、既存の32バイトのハッシュ値×16個よりもとても小さくなる。

また、KZGコミットメントへの置き換えにより、包含証明に必要なプルーフのデータがからまで削減できる。

Verkle Trieの包含証明

Vercle Trie内にアイテムが存在するかは、以下のデータを使って検証される。

• 実際のリーフノードのデータ
• データが保持されているノードまでのすべての中間ノードのKZGコミットメント
• 単一のプルーフ（KZGコミットメントに対してプルーフをどう検証するかは前回のブログ記事参照↑）

これらのデータを使って

1. リーフノードのデータが、親ノードのKZGコミットメントに含まれているか。
2. 1の親ノードのデータがさらにその親のKZGコミットメントに含まれているか。
3. これをルートまで繰り返す。

ここまでだと、中間ノードの数分のコミットメントとプルーフが必要に思えるが、Multi-proofsという仕組みを利用すると小さな単一のプルーフ（200バイト以下）でこれらの証明が可能になるみたい↓

https://notes.ethereum.org/nrQqhVpQRi6acQckwm1Ryg

この辺り、また詳しく追っていきたい。

Trusted Setup

ただ、KZGコミットメントは、↑のブログ記事に書いたようにTrusted Setupを必要とする。↑のような16-aryツリーを構成する場合は、16個のシークレットパラメータ（）を予め、誰もその値を知りえないようMPCなどで計算する必要がある。

Merkle Patricia Trieの課題から二分木に移行しようという議論もあったけど、Verkle Trieは、16-aryツリーのままアイテムの包含証明のサイズを削減できる新しいアプローチになる。

Geth v1.10.0で導入された新しい同期方法Snap sync

ノードが新しくブロックチェーンネットワークに参加した際、最初にチェーンの初期同期を開始するが、ブロックチェーンの成長と伴にこの初期同期のスピードというのがネックになる。先日リリースされたGeth v1.10.0では、Ethereumのブロックチェーンを同期する際の新しい同期方法がリリースされていたので見てみる↓

blog.ethereum.org

これまでの同期方法

Gethでは、これまでFull syncとFast syncと呼ばれる２つの同期方法がサポートされてきた。

Full sync

Full syncは初期からある同期方法で、Ethereumの各ブロックに含まれているトランザクションをすべて実行し、ローカルのステートツリーを更新する方法。最新のブロックまでステートツリーを更新し続けることで、ブロックチェーンを同期するシンプルな方法。

Ethereumのフルノードは、各アカウントが保持するetherの量や、コントラクトのコード、コントラクトが保持するストレージデータをすべて保持する必要があり、トランザクションを実行すると該当するこれらのステートデータが更新される。ただ、これらのデータをそのままブロックチェーンに記録することは（サイズ的に）できないので、そのステートへのコミットメントをブロックヘッダーに記録している。各データをリーフノードとし、全データで構成される巨大なマークルツリーのルートハッシュがこのコミットメントで、ブロックヘッダーにステートルートとしてセットされる。

ただ、Ethereumのブロックチェーンの累計トランザクション数は10億を超えている。そのため、初回起動したばかりのノードがジェネシスブロックからすべてのトランザクションを実行するというのは、ハードルの高い作業になった。結果、ノードのCPUリソースとディスクIOに負荷がかかり、性能の良いマシンで同期に1週間から10日かかるとされている。

Fast sync

チェーンの成長に伴いFull syncの同期時間が問題になったこともあり、Gethはv1.6からFast Syncという新しい同期方法を導入した（現在デフォルトの同期方法）。

Fast syncは、チェーンの先頭に近いピボットブロック*1を選択し、そのブロック時点のステートツリーをリモートピアから直接ダウンロードすることで、ローカルのステートツリーを構築するというアプローチを採った同期方法。ピボットブロック以降のブロックについてはFull syncと同様トランザクションを実行することでステートツリーを更新していく。

ダウンロードの仕組みを理解するには、Merkle Patricia Trieの構造を理解しておくのが良い↓

techmedia-think.hatenablog.com

ノードはブロックヘッダーの同期が終わると、ピボットブロックを選択する。そのブロックヘッダーから、そのブロック時点のステートツリーのルートハッシュが何かは知っている。なので、

1. まずそのルートハッシュを指定してGetNodeDataメッセージをリモートピアに送信して、ステートルートのノードデータを要求する。
2. リモートピアはNodeDataメッセージでルートノードのデータを返してくる。このノードはブランチノードで、さらに最大16個の子ノードをを持っている。
3. ノードは続いて2の子ノードを取得するのにGetNodeDataをリモートピアに送信する。

これを繰り返してツリーの探索を進め、ステートツリーのデータをすべてダウンロードすることで、ステートツリーを同期する。

この方法では、ジェネシスブロックからトランザクションをすべて実行する必要がなくなり、Full syncに比べて速くチェーンの同期が可能になった。しかし、これもステートの成長に伴い別のボトルネックが発生するようになる。

Fast syncのボトルネック

ステートの成長に伴い、GetNodeData/NodeDataを使ったステートをダウンロード処理自体がボトルネックになるようになってきた。Fasy syncでは↑のようにルートノードを起点にステートツリー内のすべてのノードをダウンロードすることになる。問題は現在のEthereumのステートツリーには約6億7500万個を超えるノードが存在するということだ。この結果、以下のボトルネックが報告されている。

• リモートピアにノードデータを要求するが、1リクエストあたり最大384個のノード要求をバッチ化できるが、それでもすべてのノードを要求するのにノードとリモートピア間で、最低でも175万回の通信の往復が発生する。10個のリモートピアと並列で実行したとしても、ネットワークのRTTを50msとすると、その合計は150分。
• GetNodeData要求を受けたピアは、対象のノード情報を提供する必要があるが、その際ディスクアクセスが発生する*2。データ自体はGethの場合LevelDBに保存されているが、検索のキーはノードのハッシュ値になるので、基本的にランダムリードになる。結果ディスクリードは、1リクエスト384ノードの要求に対して、約2700回弱になり、SATA SSDで100,000IOPS出ると仮定しても、10個のピアで並列してすべてのノードを取得するのに108分のリード時間が発生。
• ノードはすべてのノードを取得するためにGetNodeDataでメッセージでそのすべてのハッシュ値をアップロードしていることになる。ハッシュ値１つあたり32バイトなので、アップロードするハッシュ値の合計は、6億7500万×32バイト＝約21GB。ダウンロードするノードデータの合計は、その2倍ちょっと。アップロードの速度を51Mbps、ダウンロードの速度を97Mbpsとすると、アップロードで56分、ダウンロードで63分それぞれかかる。

Full syncではCPUとディスクIOがボトルネックになっていたが、Fast syncではネットワークの帯域幅やレイテンシー、ディスクIOがボトルネックになっている。まぁそこにボトルネックが発生するほど、ステートが膨らんだ＝利用されているということ。

Snap sync

↑のFast syncのボトルネックを軽減する新しい同期方法がステートのスナップショットを利用したSnap syncになる。これはSnap protocolとして定義されている。

Fast syncでステートツリーをルートノードを起点のツリーのノードをすべてダウンロードしているため、中間ノード（ブランチノードやエクステンションノード）もすべてダウンロードする必要があり、膨大な数のノードをダウンロードしなければならないが、Snap syncは、この中間ノードをダウンロードすることなくステートツリーを構築できるようにしようというものだ。

具体的には、各ノードはMerkle Patricia Trieとは別に、ブロックチェーンの特定のブロックにおけるViewとなるスナップショットを作成する。このスナップショットは、すべてのアカウントとそのストレージスロットのフラットなKey-Valueストアになる。このデータストアから、アカウントやストレージのデータを連続したデータチャンクとして入手できるようにすることで、そのステートデータからMerkle Patricia Trieを復元する。こうすることで、リモートピアからツリーの中間ノードをダウンロードすることなくそれらをローカルで計算することができ、最終的にルートノードまで計算される。余計な中間ノードをダウンロードしなくて済むので、その分のコストが不要になる。またこれらのデータを提供するピアにとっても、スナップショットからデータをリードする際にO(1)のダイレクトアクセスができるようになる。その結果、Fast syncと比べたSnap syncのコストは↓のように変化するとのこと。

ただ、Snap syncを利用するには前提としてリモートピアが、予めスナップショットを作成しておく必要がある。ただ、スナップショットはステートの参照にも利用可能で、eth_callの呼び出しは桁違いに高速になる。同期以外にも、そういうユースケースが求められるケースではスナップショットの恩恵が受けられそう。

当然ながら、次々と新しいブロックが来るのでスナップショットも随時更新していく必要がある。ただ、Ethereumにはファイナリティは無く再編成が発生する可能性があるので、ブロックが到着したら順次ステートを単純に上書きしていくということはできない。そこでGethのスナップショットは永続化レイヤーとインメモリの差分レイヤーで構成されている。基本的にステートの更新は永続化レイヤーに直接行わず、差分レイヤーに対して行う。十分な差分レイヤーが積み重なると、下のレイヤーから順に永続化レイヤーに書き込まれるという仕組み。なお、シャットダウン時にはメモリ上の差分レイヤーもジャーナルに保存されれ、起動時にそこからロードバックされる。と書くのは簡単だけど、実際の実装はもっと考慮すべきことが多く、結構ヘビーそう。

また、当然ながら同期中にもリモートピアのスナップショットは随時更新されることになるため、同期中に不整合なデータを受け取る可能性があるが、不整合は後で、Fast syncスタイルの同期方法を利用して修復する模様。

snap syncのトレードオフ

スナップショット作成するとハッピーになれそうな感じがする、ここにもトレードオフはある。

• スナップショットの作成に伴い、
  • 最初だけだが、1日〜1週間かかる。
  • Merkle Patricia Trieのデータの冗長コピーになるので、現状追加で20〜25GBのディスクスペースが必要になる。
• 再編成が発生した場合のリスクを吸収するのに、インメモリの差分レイヤーがあるが、永続化レイヤーに適用した変更を覆すチェーンの再編成が発生した場合、スナップショットを新規に作成しなおさなければならない。

というのが、Synap syncの仕組み。

フルノードが減少？

Ethereumのフルノードといえば、一時期Bitcoinより多かったが、最近みるとどうもフルノードの数が減少している。現在は6,500〜7,000台。

チェーンの成長と伴にEthereumのフルノードの運用コストも大きくなってるので、単純に運用者が減ってるのか？ただ、ノードが減少すると、↑のような同期をする際も既存のノードが負荷が上がるので、ノードの運用コストは重要なファクターになる。

*1:たしか先頭から64ブロック前のブロック

*2:これはLevelDBがもともとディスクバックアップされたオンメモリデータベースとしての使用が意図されたもので、データの大部分がメモリ上に収まればパフォーマンスが良いが、データがメモリに乗らないようになるとディスクアクセスが増え当然ボトルネックになる。

Merkle Patricia Trieの構造とボトルネック

Ethereumのステートを管理する上で重要な構成要素の１つがMerkle Patricia Trie。ビットコイナーならマークルツリーはお馴染みだが、Merkle Patricia Trieはマークルツリーとはだいぶ勝手が違うデータ構造なので、どんな仕組みで構築されて、特定のアイテムがそれに含まれていることをどう探索、検証しているのか、またそのボトルネックについてまとめておく。

ステートの種類

Ethereumのブロックヘッダーには、以下の３つのステートツリーのルートハッシュが記録されてる。

• ステートルート：
  俗にワールドステートと呼ばれる、各アカウントのステートで構成されるツリーのルートハッシュ。
• トランザクションルート：
  ブロックに含まれるトランザクションで構成されるツリーのルートハッシュ。
• レシートルート：
  トランザクションレシートで構成されるツリーのルートハッシュ。

ステートルートのリーフノードのデータには、ストレージルートが含まれている。つまり各アカウントはそれぞれストレージのステートツリーを持っており、そのルートハッシュが↑のステートツリーのリーフのデータとして記録されている。

結果、Ethereumのフルノードは４つのMerkle Patricia Trieを管理している。各Merkle Patricia Trieのkey-value値は以下のとおり：

Trie	key	value
ステートツリー	アドレスのKeccak-256ハッシュ	残高、nonce、ストレージルート、コードハッシュで構成されるステート
トランザクションツリー	トランザクションのブロック内のインデックス	トランザクションデータ
レシートツリー	トランザクションのブロック内のインデックス	レシートデータ
ストレージツリー	各コントラクトの変数のハッシュ値*1	ストレージの値

Merkle Patricia Trieの構成要素

マークルツリーは、リーフノードと、２つの子ノードのハッシュ値を連結して自身のハッシュ値を計算する内部ノードの2種類のノードのみでシンプルだが、Merkle Patricia Trieには、以下の4種類のノードが存在し、それぞれ保持するデータが異なる。またアイテムはkey-valueのマッピングで構成される。

• ブランクノード：
  空のTrieで、ツリーの初期状態。
• ブランチノード：
  ツリーの内部ノード兼リーフノード的な位置づけのノードで、17個のリストを持つ。16個のアイテムは子ノードの32バイトのハッシュ値を保持している（つまりブランチノードは最大16個の子ノードを持つ）。17個めの最後のアイテムは、keyの最後がこのブランチノードで終わる場合のvalue値が入る。
• リーフノード：
  ツリーの末端のノードで、パス（ニブル）とvalue値を持つ。このvalueは実際に保存するステートの値。
• エクテンションノード：
  ツリーの内部ノードで、パス（ニブル）とvalue値を持つ。リーフノードと似ているけど、valueはステートの値ではなく、他のノードのハッシュ値になっている。LevelDBに対して、このハッシュ値でルックアップすると、子ノードの情報を入手できる。

アイテムをツリー内のどこに配置するかは、アイテムのkey-valueのkeyによって決まる。つまりkeyはツリー内のアイテムが存在するノードのパスであると言える。そして、リーフノードとエクステンションノード内のパスは、そのパスのデータの一部で、ニブルの配列。

アイテムの登録に伴い、これらのノードがどう解釈され、どうアイテムが探索、追加されるのか？具体的にみていこう。

アイテムの探索

ツリー内のあるアイテムを探索する場合、アイテムのkeyを指定してルートノードから探索する。

まず、自明なことだけど、ツリー内のアイテム数が１でそのアイテムしかない場合、ルートノードはリーフノードでそのアイテム自身だ。

それ以外に、ツリーに複数のアイテムが登録されている場合、ルートノードは、ブランチノードかエクステンションノードのいずれかになる。この場合、まずkeyをニブルに変換する。変換した値を3, 0, 4, 2, 5, 8としよう（Ethereumの場合、keyはKeccak-256ハッシュなので、実際は64個）。

• ブランチノードの場合：
  ニブルの最初の要素が3なので、ブランチノードの0〜15個の16個のリストの4つめのアイテムを取得する。これは子ノードのハッシュ値なので、LevelDBにこのハッシュ値の子ノードを問い合わせる。この時、keyのニブル3は消化したので、その子ノードの探索は0, 4, 2, 5, 8のニブルで継続する。
  
• エクテンションノードの場合：
  エクステンションノードのニブルと、keyのニブルの合致する部分をチェックし、エクステンションノードのvalue値を取得する。これは子ノードのハッシュ値なので、LevelDBにこのハッシュ値の子ノードを問い合わせる。この時、エクステンションノードのニブルが3, 0, 4だった場合、それらは消化したので、子ノードの探索は残りのニブル2, 5, 8で行う。

↑の探索を行うと次のノードは、ブランチノードか、エクステンションノードか、リーフノードのいずれかになる。リーフノードの場合、そのキーの値はそのノードから取得できる。ブランチノードかエクステンションノードの場合は、↑と同じ処理を続けて、最終的にリーフノードまで探索を続ける。

内部ノードの種類がブランチノードだけでなくエクステンションノードが存在する理由は、リーフノードの探索をショートカットするためだ。ブランチノードだけだと、keyが32バイトなので、ブランチノードはそのニブルを１つずつしか合致できないので、どのアイテムも64階層めにリーフノードが存在することになり、探索コストが大きくなってしまう。そこで、keyが共通の値をもつ部分をエクステンションノードやリーフノードのニブルとして保持することで、探索するノード数を減らしている。

アイテムの登録

マークルツリーの場合、登録するアイテムのハッシュをリーフノードとして、そこを起点に親（内部）ノードを計算し、最終的にルートノードのルートハッシュを計算するが、Merkle Patricia Trieの場合、ルートノード（最初はブランクノード）を起点にアイテムを登録してツリーを成長させていく。この時、↑の探索特性をサポートするため、探索した先のノードに応じて、以下のルールでツリーを構成していく。

• ノードがブランクノードだったら、リーフノードに置き換える。
• ノードがリーフノードだったら、それをエクステンションノードに変換し、その新しいブランチとしてリーフノードを追加する。
• エクステンションノードで停止したら、それよりパスが短い別のエクステンションノードに変換し、新しくブランチノードを作成しそれをエクステンションノードの子ノードとする。

ニブルのプレフィックス

↑では省略していたけど、リーフノードやエクステンションノードのパスであるニブルをエンコードする際は、ニブルの特性により先頭にプレフィックスがつくようになっている。それぞれ4bitのニブルはエンコードされる際はバイトになる。しかし、ニブルの個数は奇数になる場合もあり、その場合、バイトにするのに4bit分不足してしまう。例えばニブルが1だった場合、01とエンコードされてしまうと、ニブル0, 1と同値になり区別できなくなる。この問題を回避するためにニブルには、プレフィックスが付与される。

プレフィックスのルールは、

hex文字	ニブルの数	ノードタイプ
0	偶数	エクステンション
1	奇数	エクステンション
2	偶数	リーフ
3	奇数	リーフ

ニブルの数が偶数か奇数かに関係なくプレフィックスは付与され、1つ付与するだけだと逆に偶数のニブルが奇数になるので、偶数の場合は後ろに0がパディングされる。つまり、個数が偶数のニブルのプレフィックスは00か20。

なお、偶奇だけでなく、そのノードがエクステンションノードなのかリーフノードなのか（末端なのかどうか）を判断するためのフラグも加味されている。

データの保護

子ノードを持つ、ブランチノードとエクステンションノードはそれらの子ノードのハッシュ値を持っており、各ノードのハッシュ値はそのノードが保持するデータ（ブランチノードは最大16個の子ノードのハッシュ値とvalue値、エクステンションノードはニブルと単一の子ノードのハッシュ値、リーフノードはニブルとvalue値）のハッシュ値であるため、データが更新されるとそのハッシュ値が変わる。このあたりはマークルツリーと同様のツリー型のハッシュチェーンでデータを保護している。

Merkle Patricia Trieのボトルネック

Merkle Patricia Trieでステートを管理することで、ステートが更新された際その時点のステートにコミットするのに、全てのステートのハッシュを再計算する必要がなく、ツリー内の変更のあったノードのハッシュ値を再計算するだけで済むという恩恵を受けられる。これはステート更新時の計算コストを下げるというメリットがある反面、ステートの読み取りコストが増加する。単なるKVSであればあるキーに対応する値はO(1)でダイレクトにアクセスできるが、Merkle Patricia Trieでは目的のステートが保持されているノードを探索するコストが増える。

現状のmainnetで各アカウントのステートツリーがどのくらいの深さかは正確には分からないけど、2020年7月の記事では、2019年自体で深さ7が飽和していており、少なくとも7〜8の内部ノードにアクセスしているだろうと記載されている。つまりその回数分、LevelDBへのクエリが発行されていることになる。またLevelDB自体、データを階層化して管理する（最大7階層）という特性上、これによりディスクへのランダムアクセスがさらに増える。このあたりがEthereumのスケーリングにあたってディスクIOがボトルネックになっている要因。

これらを解消するため、マークルツリーのような二分木に移行しようという議論もされており、その仕組みについてはまた別の記事で。

*1:例えば、0番目の変数のkeyは、sha3(0000000000000000000000000000000000000000000000000000000000000000)

PSBT Version 2を定義したBIP-370

PSBTは、マルチパーティでBitcoinのトランザクションを構築したり、トランザクションの署名にハードウェアウォレットと連携したりする際に、共通のデータフォーマットを定義した仕様で、2017年に定義され、これまでいくつか修正が加えられてきた↓

techmedia-think.hatenablog.com

そして、先日PSBTのVersion 2がBIP-370として定義された↓

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

BIP-174のPSBTは、グローバルタイプで未署名のトランザクションを定義（PSBT_GLOBAL_UNSIGNED_TX）していたので、後からそのトランザクションにインプットやアウトプットを追加することができなかった。この問題に対応するため、BIP-370で新しいPSBT Version 2を定義し、PSBT_GLOBAL_UNSIGNED_TXを廃止し、各インプットとアウトプットの情報をマップ形式で保持するようPSBTのフォーマットを変更している。この変更のため、BIP-174とBIP-370は互換性はないが、BIP-370→BIP-174への変換は可能になっている。

もともとBIP-174はPSBT Version 0で本来ならVersion 1になるべきが、どうもBIP-174をVersion 1と呼び、BIP-370がVersion 2と呼称されてることから、混乱を避けるためVersion 2にしたらしい。まぁこういう仕様はバージョン１から定義した方がいいね。

以下、BIP-370の意訳↓

イントロダクション

概要

このドキュメントはBIP 174で定義されているPartially Signed Bitcoin Transactionフォーマットの２つめのバージョンを提案するもので、PSBTの作成後にインプットやアウトプットの追加を可能にする。

Copyright

このBIPは2-clause BSD licenseが適用される。

動機

BIP 174で定義されているPartially Signed Bitcoin Transaction Version 0では、新しいインプットとアウトプットをトランザクションに追加することができない。固定のGlobal Unsigned Transactionは変更できないので、これによりインプットやアウトプットが追加できなくなっている。PSBT Version 2は、この問題を修正することを目的としている。

さらに良い副作用として、あるインプットやアウトプットのすべての情報が、<input-map>および<output-map>で提供されるようになる。Version 0では、インプットやアウトプットのすべての情報を取得するのに、<input-map>/<output-map>とGlobal Unsigned Transactionの２つの異なる場所から探す必要があった。PSBT Version 2では関連数すべての情報が１つの場所に移動している。

仕様

PSBT Version 2（PSBTv2）は、新しいフィールドとフィールドの包含/除外要件のみを定義する。

PSBT_GLOBAL_UNSIGNED_TXはPSBTv2では除外されなければならない。PSBTv2には、PSBT_GLOBAL_VERSIONが含まれ バージョン番号は2*1をセットする必要がある。

PSBT Version 2の新しいグローバルタイプは以下の通り：

名称	キータイプ	キーデータ	キーデータの定義	値データ	値データの定義	含める必要のあるバージョン	除外する必要のあるバージョン	含めることができるバージョン
トランザクションバージョン	PSBT_GLOBAL_TX_VERSION = 0x02	None	キーデータ無し	32-bit uint	作成されるトランザクションのバージョン番号を表す32bitのリトルエンディアンの符号付き整数。PSBT_GLOBAL_VERSIONフィールドで指定されるPSBTバージョン番号と異なることに注意すること。	2	0	2
フォールバックロックタイム	PSBT_GLOBAL_FALLBACK_LOCKTIME = 0x03	None	キーデータ無し	32-bit uint	インプットがlocktimeを指定しない場合に使用するトランザクションのlocktimeを表す32bitのリトルエンディアンの符号なし整数		0	2
インプットの数	PSBT_GLOBAL_INPUT_COUNT = 0x04	None	キーデータ無し	compact size uint	このPSBTのインプットの数を表すCompact sizeの符号なし整数	2	0	2
アウトプットの数	PSBT_GLOBAL_OUTPUT_COUNT = 0x05	None	キーデータ無し	compact size uint	このPSBTのアウトプットの数を表すCompact sizeの符号なし整数	2	0	2
トランザクションの変更可能フラグ	PSBT_GLOBAL_TX_MODIFIABLE = 0x06	None	キーデータ無し	8-bit uint	さまざまなトランザクションの変更フラグ用のビットフィールドとして使用する8bitのリトルエンディアンの符号なし整数。bit 0はInputs Modifiableフラグで、インプットが変更可能かどうかを示す。bit 1は、Outputs Modifiableフラグで、アウトプットが変更可能化どうかを示す。bit 2は、Has SIGHASH_SINGLEフラグで、トランザクションがSIGHASH_SINGLE署名を持ち、インプットとアウトプットのペアを保持する必要があるかどうかを示す。bit 2は基本的に、Constructorがインプットをチェックして、インプットを追加するかどうか、追加する方法を決定する必要があることを示す。		0	2

PSBT Version 2の新しいインプット毎のタイプは以下の通り：

名称	キータイプ	キーデータ	キーデータの定義	値データ	値データの定義	含める必要のあるバージョン	除外する必要のあるバージョン	含めることができるバージョン
前のTXID	PSBT_IN_PREVIOUS_TXID = 0x0e	Nonee	キーデータ無し	txid	前のトランザクションの32バイトのtixdで、そのPSBT_IN_OUTPUT_INDEXのアウトプットが使用される。	2	0	2
使用するアウトプットインデックス	PSBT_IN_OUTPUT_INDEX = 0x0f	None	キーデータ無し	32-bit uint	PSBT_IN_PREVIOUS_TXIDのtxidを持つトランザクションの使用するアウトプットのインデックスを表す32bitのリトルエンディアン整数。	2	0	2
シーケンス番号	PSBT_IN_SEQUENCE = 0x10	None	キーデータ無し	32-bit uint	このインプットのシーケンス番号である32bitの符号なしリトルエンディアン整数。省略された場合、シーケンス番号は最終シーケンス番号（0xffffffff）とみなされる。		0	2
時間ベースのLocktime	PSBT_IN_REQUIRED_TIME_LOCKTIME = 0x11	None	キーデータ無し	32bit uint	このトランザクションのlocktimeとして設定する必要がある最小のUnixタイムスタンプを表す500000000以上の32bit符号なしリトルエンディアン整数。		0	2
高さベースのLocktime	PSBT_IN_REQUIRED_HEIGHT_LOCKTIME = 0x12	None	キーデータ無し	32-bit uint	このトランザクションのlocktimeとして設定する必要がる最小のブロック高を表す、500000000未満の32bit符号なしリトルエンディアン整数。		0	2

PSBT Version 2の新しいアウトプット毎のタイプは以下の通り：

名称	キータイプ	キーデータ	キーデータの定義	値データ	値データの定義	含める必要のあるバージョン	除外する必要のあるバージョン	含めることができるバージョン
アウトプットの量	PSBT_OUT_AMOUNT = 0x03	None	キーデータ無し	64-bit int	satoshi単位のアウトプットの量を表す64bitの符号付きリトルエンディアン整数。	2	0	2
アウトプットスクリプト	PSBT_OUT_SCRIPT = 0x03	None	キーデータ無し	Script	scriptPubKeyとして知られるアウトプットのScript。PSBTv0では省略され、PSBTv2では提供されなければならない。

Locktimeの決定

トランザクションのnLockTimeフィールドは、PSBT_GLOBAL_PREFERRED_LOCKTIMEおよび各インプットのPSBT_IN_REQUIRED_TIME_LOCKTIME、PSBT_IN_REQUIRED_HEIGHT_LOCKTIMEをチェックすることで決定される。どのインプットにもPSBT_IN_REQUIRED_TIME_LOCKTIME、PSBT_IN_REQUIRED_HEIGHT_LOCKTIMEが内場合は、PSBT_GLOBAL_PREFERRED_LOCKTIMEを使用しなければならない。PSBT_GLOBAL_PREFERRED_LOCKTIMEが提供されない場合、0とみなされる。

１つ以上のインプットがPSBT_IN_REQUIRED_TIME_LOCKTIMEもしくはPSBT_IN_REQUIRED_HEIGHT_LOCKTIMEを持つ場合、選択されたフィールドはすべてのインプットでサポートされるフィールドである。これは、これらのフィールドのいずれかでlocktimeを指定するすべてのインプットをチェックし、それらのすべてのインプットに存在するフィールドを選択することで決定できる。locktimeを指定しないインプットは、両方を指定するインプットと同様に、両方のタイプのlocktimeを取れる。選択されるlocktimeは、選択されたloctimeタイプの最大値になる。

一意な識別

PSBTv2は、PSBTに記載されている情報を元に未署名のトランザクションを構築し、そのトランザクションのトランザクションIDを計算することで一意に識別することができる。PSBT_IN_SEQUENCEはUpdaterやCombinerによって変更される可能性があるため、この未署名のトランザクションのシーケンス番号は（finalでもなくPSBT_IN_SEQUENCEのシーケンスでもなく）0に設定する必要がある。この未署名のトランザクションのlocktimeは前述のように計算されなければならない。

ロール

PSBTv2は新しいロールを導入し、既存のロールを一部変更する。

Creator

PSBTv2では、Creatorは0個のインプットと0個のアウトプットを持つPSBTを初期化する。PSBTのバージョン番号は2が設定される。トランザクションのバージョン番号は少なくとも2を設定する必要がある*2。Creatorはまた、PSBT_GLOBAL_PREFERRED_LOCKTIMEを設定する必要がある。CreatorがConstructorではなく、PSBTを他のユーザーに渡してインプットやアウトプットを追加する場合は、PSBT_GLOBAL_TX_MODIFIABLEフィールドが存在し、Inputs ModifiableおよびOutputs Modifiableフラグが適切に設定されている必要がある。CreatorがConstructorで、他のエンティティによってインプットとアウトプットが追加されない場合、PSBT_GLOBAL_TX_MODIFIABLEは省略可能。

Constructor

Constructorは、PSBTv2にのみ登場する。CreatorがPSBTを初期化すると、Constructorはインプットとアウトプットを追加する。これらを追加する前に、ConstructorはPSBT_GLOBAL_TX_MODIFIABLEフィールドをチェックする必要がある。nputs Modifiableフラグがtrueの場合のみインプットを追加でき、Outputs Modifiableフラグがtrueの場合のみアウトプットを追加できる。

インプットとアウトプットを追加したら、PSBTのPSBT_GLOBAL_INPUT_COUNTとPSBT_GLOBAL_OUTPUT_COUNTがそれぞれインプットの数とアウトプットの数になるようインクリメントしなければならない。インプットを追加する際は、PSBT_IN_PREVIOUS_TXIDとPSBT_IN_OUTPUT_INDEXを設定しなくてはならない。アウトプットを追加する際は、PSBT_OUT_VALUEとPSBT_OUT_OUTPUT_SCRIPTを設定しなくてはならない。もしインプットがタイムロックを必要とする場合は、Constructorsはtimelockフィールドを設定しなければならない。インプットが時間ベースのタイムロックを持つ場合は、PSBT_IN_REQUIRED_TIME_TIMELOCKを、ブロック高ベースのタイムロックを持つ場合はPSBT_IN_REQUIRED_HEIGHT_TIMELOCKを設定しなければならない。インプットが両方のタイプのタイムロックを持つ場合、両方設定しなければならない。場合によっては、両方のタイプを許可するインプットがあるが、１つのタイプのタイムロックのみをサポートする特定の分岐が選択されるため、使用されるタイムロックのタイプは１つのみになる。

追加するインプットで必要案タイムロックが指定されている場合、Constructorは既存のすべてのインプットをチェックし、タイムロックのタイプに互換性があることを確認する必要がある。さらに、このチェック中に、インプットに署名があることが分かった場合、新しく追加されたインプットによってトランザクションのlocktimeが変更されないようにする必要がある。新しく追加されたインプットに互換性のないタイムロックがある場合、追加してはならない。既存の署名がある場合、トランザクションのlocktimeを変更するような追加をしてはならない。

Has SIGHASH_SINGLEフラグがtrueの場合、Constructorはすべてのインプットチェックし、SIGHASH_SINGLEを使用した署名を持っているインプットを探す。インプットと対応するアウトプットの前に、同じ数のインプットとアウトプットを加える必要がある。

Constructorは、PSBT_GLOBAL_TX_MODIFIABLEのbool値をfalseにするか、フィールドを完全に削除して、トランザクションにインプットとアウトプットを追加できないよう宣言することを選択できる。

単一のエンティティがCreatorとConstructorの両方になる可能性がある。

Updater

PSBTv2では、Updaterはシーケンス番号を設定できる。

Signer

PSBTv2sでは、Signerはインプットに署名後、PSBT_GLOBAL_TX_MODIFIABLEフィールドを更新し、PSBT状態を正確に反映させる必要がある。SignerがSIGHASH_ANYONECANPAYを使用しない署名を追加した場合、Input Modifiableフラグをfalseに設定しなければならない。SignerがSIGHASH_NONEを使用しない署名を追加した場合、Outputs Modifiableをfalseに設定しなければならない。Signerが、SIGHASH_SINGLEを使用する署名を追加した場合、Has SIGHASH_SINGLEフラグをtrueに設定しなければならない。

Transaction Extractor

PSBTv2sでは、トランザクションはPSBTv2の各フィールドを使って構築される。このトランザクションのlocktimeは、Locktimeの決定セクションで指定された方法で決定される。Extractorは、すべての入力が完了した場合、完全に有効なネットワークシリアライゼーションされたトランザクションを生成する必要がある。

後方互換性

PSBTv2は、BIP 174で定義されているPSBTv0と同じgemeric形式を共有している。PSBTv0用のパーサーは新しいフィールドをサポートするための変更のみでPSBTv2をデシリアライズすることができるはずである。

ただし、PSBT_GLOBAL_VERSIONを使用しているため、PSBTv2はPSBTv0とは互換性がなく、その逆も同様。この非互換性は、PSBT_GLOBAL_UNSIGNED_TXを削除するために意図的なものだ。しかし、PSBTv2のフィールドから未署名のトランザクションを作成することで、PSBTv2をPSBTv0に変換することは可能。

Test Vector

TBD

参照実装

BSBTフォーマットの参照実装は、https://github.com/achow101/bitcoin/tree/psbt2から入手可能。

*1:バージョン番号1はどうなったの？PSBT Version 0が俗にバージョン１と呼ばれているため、Version 1はスキップしている。本来このBIPはVersion 1の予定だったが、設計中に俗にVersion 2と呼ばれていたため、混乱がないようにバージョン番号を2に変更することにした。

*2:トランザクションのバージョン番号はなぜ2以上なのか？トランザクションのバージョン番号はOP_CHECKSEQUENCEVERIFYのような機能のバリデーションルールの一部である。後方互換性があり、これらの機能を無効にする方法は他にもあるため（シーケンス番号など）、トランザクションのバージョン番号をネゴシエートするよりも、トランザクションがこれらの機能をサポートできるようにする方が簡単。