Develop with pleasure!

福岡でCloudとかBlockchainとか。

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

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

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

Merkle Patricia Trieの包含証明

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

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

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

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

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コミットメントに置き換えたKGZコミットメントのツリーを構成しようというもの。

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

システムパラメータとして16個の {s_0G, s_iG, ..., s_{15}G}楕円曲線上の点が与えられるので(Gはそのベースポイント)、それと16個の子ノードの各データ(おそらくハッシュ値)を {p_0, p_1, ..., p_{15}}を使って、

 {\displaystyle commitment = \sum_i^{15}p_i s_iG}

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

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

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

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個のシークレットパラメータ( {s_0, s_i, ..., s_{15}})を予め、誰もその値を知りえないよう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と呼ばれる2つの同期方法がサポートされてきた。

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でメッセージでそのすべてのハッシュ値をアップロードしていることになる。ハッシュ値1つあたり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のコストは↓のように変化するとのこと。

https://user-images.githubusercontent.com/129561/109820169-6ee0af00-7c3d-11eb-9721-d8484eee4709.png

ただ、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台。

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

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

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

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

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

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

ステートの種類

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

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

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

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

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

Merkle Patricia Trieの構成要素

マークルツリーは、リーフノードと、2つの子ノードのハッシュ値を連結して自身のハッシュ値を計算する内部ノードの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を指定してルートノードから探索する。

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

それ以外に、ツリーに複数のアイテムが登録されている場合、ルートノードは、ブランチノードかエクステンションノードのいずれかになる。この場合、まず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バイトなので、ブランチノードはそのニブルを1つずつしか合致できないので、どのアイテムも64階層めにリーフノードが存在することになり、探索コストが大きくなってしまう。そこで、keyが共通の値をもつ部分をエクステンションノードやリーフノードのニブルとして保持することで、探索するノード数を減らしている。

アイテムの登録

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

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

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

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

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

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

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

データの保護

子ノードを持つ、ブランチノードとエクステンションノードはそれらの子ノードのハッシュ値を持っており、各ノードのハッシュ値はそのノードが保持するデータ(ブランチノードは最大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にしたらしい。まぁこういう仕様はバージョン1から定義した方がいいね。

以下、BIP-370の意訳↓

イントロダクション

概要

このドキュメントはBIP 174で定義されているPartially Signed Bitcoin Transactionフォーマットの2つめのバージョンを提案するもので、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の2つの異なる場所から探す必要があった。PSBT Version 2では関連数すべての情報が1つの場所に移動している。

仕様

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_LOCKTIMEPSBT_IN_REQUIRED_HEIGHT_LOCKTIMEをチェックすることで決定される。どのインプットにもPSBT_IN_REQUIRED_TIME_LOCKTIMEPSBT_IN_REQUIRED_HEIGHT_LOCKTIMEが内場合は、PSBT_GLOBAL_PREFERRED_LOCKTIMEを使用しなければならない。PSBT_GLOBAL_PREFERRED_LOCKTIMEが提供されない場合、0とみなされる。

1つ以上のインプットが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を設定する必要がある*2Creatorはまた、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_COUNTPSBT_GLOBAL_OUTPUT_COUNTがそれぞれインプットの数とアウトプットの数になるようインクリメントしなければならない。インプットを追加する際は、PSBT_IN_PREVIOUS_TXIDPSBT_IN_OUTPUT_INDEXを設定しなくてはならない。アウトプットを追加する際は、PSBT_OUT_VALUEPSBT_OUT_OUTPUT_SCRIPTを設定しなくてはならない。もしインプットがタイムロックを必要とする場合は、Constructorsはtimelockフィールドを設定しなければならない。インプットが時間ベースのタイムロックを持つ場合は、PSBT_IN_REQUIRED_TIME_TIMELOCKを、ブロック高ベースのタイムロックを持つ場合はPSBT_IN_REQUIRED_HEIGHT_TIMELOCKを設定しなければならない。インプットが両方のタイプのタイムロックを持つ場合、両方設定しなければならない。場合によっては、両方のタイプを許可するインプットがあるが、1つのタイプのタイムロックのみをサポートする特定の分岐が選択されるため、使用されるタイムロックのタイプは1つのみになる。

追加するインプットで必要案タイムロックが指定されている場合、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が俗にバージョン1と呼ばれているため、Version 1はスキップしている。本来このBIPはVersion 1の予定だったが、設計中に俗にVersion 2と呼ばれていたため、混乱がないようにバージョン番号を2に変更することにした。

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

多項式コミットメントスキーム Kate(KZG) commitment

コミットメントスキーム自体は、いろんなスキームがあり、さまざまなところで使われている(Confidential Transactionなどで登場するPedersen Commitmentや、ゼロ知識で範囲証明を提供するBulletproofsなど)。身近なところだと、ブロックチェーンでよく使用されるデータ構造の一種であるマークルツリーを使ったコミットメントなんかも。

例えば高さ4のマークルツリーには24個の要素を持つが、これは各要素のリストをベクトルとし、マークルルートをそのベクトルとベクトルコミットメントとして扱うことができる。このコミットメントにある要素が含まれているかどうかは、4個のハッシュ(マークルプルーフ)を使って証明することができる。

Kate(KZG) commitmentは、KateおよびZaverucha、Goldbergによって発表された多項式コミットメントスキームで(↑のマークルツリーを使ったコミットメントはベクトルコミットメント)、最近、Ethereumで現状のマークルツリーベースのステートプルーフを、よりコンパクトにするために多項式コミットメントの導入が検討されてることもあって注目されてる。今回はこのKate commitmentの仕組みについて見ていく。

多項式の性質

次数nの多項式は、 {p(x) = \sum_{i=0}^{n} p_{i} x^{i}}と表現できる。この多項式にコミットするのが多項式コミットメント。多項式コミットメントの説明に入る前に、多項式の性質について。

  • 多項式p(x)において、p(z) = 0になるようなzを多項式の根と呼ぶ。
  • そして、p(x)を因数分解してp(x) = q(x)(x - z)となるようなq(x)が成立すると仮定し、そのq(x)の根が同じzである場合、zはp(x) = q'(x)(x - z)kとなる重複度kを持つ。
  • 多項式p(x)を二項一次多項式(x - z)で割った余りはp(z)となるという多項式の剰余の定理から、p(a) = yとなる場合、p(x) = q(x)(x - a) + p(a)が成立する。
  • 多項式a(x)を多項式b(x)で除算すると、商q(x)と剰余r(x)は、a(x) = q(x)b(x) + r(x)と定義することができる。
  • n次の多項式は、多項式の代入値と結果のペア(x, y)がn + 1個あれば、ラグランジュ補完公式を使って多項式を復元することができる(シャミアの秘密分散などで使われてる)。

マークルツリーを使った多項式コミットメント

ちなみに、マークルツリーを使って多項式コミットメントを作るとどうなるか?ベクトルコミットメントの場合は、ベクトルの要素をリーフノードとして配置してマークルツリーを構成したけど、多項式コミットメントの場合は、n次の多項式であればリーフノードにn + 1個の各係数を配置すれば多項式にコミットしたことになる。

ただ、問題として証明者が多項式p(x)にコミットしていることを証明するためには、検証者に全ての係数を公開する必要がある。コミットメントのサイズ自体はマークルルートなので一定サイズだが、それを証明するプルーフのサイズは多項式の次数に比例する。

Kate commitment

Kate commitmentは、ペアリングが可能な楕円曲線を利用するコミットメントスキームで、多項式p(x)にコミットし、y = p(a)となるyとそれがコミットとした多項式にaを代入して得られた値であることを証明するプルーフを用いて多項式をデコミットする。特徴としては、コミットメントは1つの楕円曲線グループの要素で、プルーフ多項式の次数に関係なく1つの楕円曲線グループの要素となり、プルーフが一定サイズになる。

ペアリングが可能な楕円曲線

Kate commitmentは、ペアリングが可能な楕円曲線を必要とする。位数pの2つの楕円曲線 {\mathbb G_1, \mathbb G_2}とし、 {e: \mathbb G_1 ✕ \mathbb G_2 → \mathbb G_t}とする。そして、GとHをそれぞれ {\mathbb G_1, \mathbb G_2}のジェネレーターとする。

ペアリングが可能ため、任意の {P \in \mathbb G_1, Q \in \mathbb G_2}について、 {\displaystyle e(aP, bQ) = e(P, Q)^{ab}}となる双線形性を持つ。

Trusted Setup

n次の多項式をコミットする場合、n + 1個*1のランダムシークレット(sとする)が必要になる。このランダムシークレットの値は誰にも知られない必要があるため、通常このTrusted SetupはMPCなどを用いて実行する必要がある。

ランダムシークレットsを使って、n + 1個の {(s^{i}G, s^{i}H) (i = 0, ..., n)}を計算する。

コミットメントの作成

n次の多項式 {p(x) = \sum_{i=0}^{n} p_{i} x^{i}}のコミットメントはTrusted Setupで生成した各要素を使って、

 {\displaystyle C = \sum_{i=0}^{n} p_i s^{i}G}

を計算することで得られる。これは、Trusted Setupで生成した楕円曲線上の点を各次数にマッピングし、各次数の点に多項式の係数( {p_i})を乗算(つまり楕円曲線スカラー倍算)し、それらを合算(楕円曲線の点と点の加算)したものである。つまりコミットメントCも楕円曲線上の点で、サイズは固定だ。

任意の値での多項式の評価

コミットされた多項式p(x)について、x = a(y = p(a))で評価する場合、以下の多項式を計算する↓

 {\displaystyle q(x) = \frac{p(x) - y}{x - a}}

続いて、この多項式q(x)について、

 {\displaystyle \pi = \sum_{i=0}^{n}q_i s^{i}G}

を計算する。 {q_i}多項式q(x)の各係数で、 {s^{i}G}はTrusted Setupで生成した要素。

コミットメントのデコミット

コミットした多項式p(x)について、証明者は、検証者に値y = p(a)と、↑の {\pi}を提供することで、任意の値(x = a)でこのコミットメントを解くことができる。検証者は以下のペアリングの等価性を利用してこの関係を検証する。

 {\displaystyle e(\pi, (s - a)H) = e(C - yG, H)}

これらは、ペアリングの双線形性から、

 {\displaystyle e(G, H)^{q(s) (s - a)} = e(G, H)^{p(s) - y}}

と変形でき、つまり、

 {\displaystyle q(s) (s - a) = p(s) - y}

の検証をしていることになる。

↑の多項式の剰余の定理を変形すると {\displaystyle q(x) = \frac{p(x) - y}{x - a}}であることから、これが成立すれば、yがp(a)の値であることが分かる。

そしてシークレット値sは実際にそのまま扱うこと無く、(s - a)H = sH - aHの値として現れるだけで、あくまでTrusted Setupの出力値を使っての検証であって、sの値を検証者が知ることはない。

と、Kate commitmentを使用すると、多項式を満たすある値の正しさを↑のように一定サイズのプルーフ(↑の {\pi})で証明することが可能になる。

Ethereumでの検討

Kate commitmentは多項式コミットメントスキームだけど、Ethereumではこれをベクトルコミットメントとして利用しようとしている。長さnのベクトルにコミットするには、n-1次の多項式にコミットするよう構成することでベクトルコミットメントにすることができる。

現状のツリーベースのコミットをKate commitmentに置き換えることで、ベクトル内の要素の証明をベクトルの長さに依存しない一定サイズのプルーフで証明できるようにするというのが目的っぽい。このコミットメントスキームを組み込もうとしてるのがVerkle triesの提案みたい。

参考

*1:n + 1個とするケースとn個のケースがあるけど、これは多項式が定数項を含むか含まないかの違いだと思われる。