Develop with pleasure!

福岡でCloudとかBlockchainとか。

UTXOのサイズ削減のアプローチTXO Commitments

BitcoinのUTXOのデータサイズは増加する一方で、フルノードを運用する際のボトルネックにもなっているが、そのUTXOの成長の問題を解決する方法としてBitcoinのコア開発者の1人であるPerter Toddが昨年 TXO Commitmentsという仕組みについてブログに投稿してた↓ので仕様部分だけまとめてみた。

Making UTXO Set Growth Irrelevant With Low-Latency Delayed TXO Commitments

現状の課題

現状Bitcoinにはブロックサイズの制限以外に、各種データのサイズを制限するようなコンセンサスルールは存在せず、UTXOのサイズも増えている。UTXOのセットを保持するのがフルノードの最小要件なので、UTXOのサイズが大きくなるほどフルノードの実行のハードルが上がる。

またUTXOのディスク上のサイズは圧縮しシリアライズされた状態であり、UTXOをモリ上に展開するとそのサイズは大幅に増える。複数の入力をマージして1つのUTXOを作るなどすればUTXOのサイズを減らせるが、現状そういったことをするインセンティブも無いので、サイズ削減も期待できない。それ以外に、小額過ぎて実際に使うことのないUTXOや秘密鍵の紛失により使用できないUTXO、コインの送付を目的としていないタイムスタンプサービスなどの使い方など、多くの要因によってUTXOサイズは増加している。特にタイムスタンプサービスなどはデータを記録するのが目的なので、通常のBitcoin送付の手数料よりもずっと高額な手数料を支払うことも許容される。

今のところUTXOの成長を防ぐための良いツールはなく、Segregated Witnessには、UTXOのサイズの削減する効果があるが、UTXOの成長を無視できるほどの効果は無い。

UTXOセットのサイズをハードリミットするというアイディアもあるが、これはBitcoinノードを効率的に動かすための最小要件であって、UTXOのスパム問題の根本解決にならない。

TXO Commitments

このUTXOのサイズの問題を解消しようと提案されているのがTXO Commitments。

(使用済み・未使用両方の出力を含む)全てのトランザクション出力の状態にコミットするマークルツリーを構築する仕組みで、出力の現在の状態をコンパクトに証明する方法を提供できる。これによりUTXOセットのアクセスの低い部分をアーカイブし、フルノードで関連データを破棄しても、それらの出力が実際に使用されていないことをノードに証明することで、アーカイブされた出力が使用する仕組みを提供する。

具体的には、TXO Commitmentsでは決定性のあるインデックス可能な挿入型マークルツリーの一種であるMerkle Mountain Range (MMR)を提案しており、ストレージ要件を最小限に抑え、新しいアイテムを安価にツリーに追加することができる。出力がTXO MMRに追加されると、その出力は決して削除されることはない。出力が使用された場合は、その場でステータスが更新される。MMRの特定のアイテムの状態と、MMRのアイテムの変更の有効性は両方ともツリーの先端までのマークルパスからなる { \displaystyle\log{2} n}サイズのプルーフで証明できる。

TXO commitment proofsは署名者の関与無しに生成及びトランザクションへの追加ができる。TXO commitment proofsは自体は署名される必要はなく、トランザクションハッシュの一部でもないので、TXO MMRのデータにアクセスできる人であれば誰でも、不足しているproofを再生成することができ、TXO commitmentsを使用するためにウォレットのソフトウェアに最小限の変更が必要となる。

TXO Commitmentsの実装

コミットメントフルノード実装では次のデータを格納する必要がある。

  1. UTXOセット
    未使用であることが明らかなtxoutsのキー:バリューのMap。既存のUTXOの実装と同様だが、古い出力のUTXOはこのセットから除外されるのが大きく違う。
  2. STXOセット
    直近のTXO commitmentの後に使用されたトランザクション出力のセット。ただしTXO commitmentより前に作成されたもの
  3. TXOジャーナル
    TXO MMRに使用済みとマークする必要がある出力。追加は低レイテンシーで、削除は高レイテンシーで行われる必要がある。
  4. TXO MMRリスト
    pruning可能な順序付けられたTXO MMRのリストで、主にペンディングされてるコミットメント。
Fast-Path: ブロック内で使用されているTxOutの検証

トランザクション出力がブロック内のトランザクションで使われた場合、以下の2ケースが考えられる。

  1. 最近作られた出力の場合
    最新のTXO commitmentの後に作られた出力なので、出力はUTXOセット内に存在する。そのためその出力を使用するトランザクションにはTXO commitment proofは不要。出力をUTXOセットから削除し、TXOジャーナルに追加する。
  2. アーカイブされた出力の場合
    最新のTXO commitmentより前に作られた出力なので、出力がUTXOセット内に存在するとは限らない。トランザクションはその出力が未使用であることを示す最新のTXO commitmentに対するTXO commitment proofを持つ。出力がSTXOに存在していないことを確認し、STXO内に無ければSTXOに追加する。出力と TXO commitment proofをTXOジャーナルに追加する。

どちらのケースでも、出力を使用済みとして記録する際は2つのキー・バリューの更新と1つのジャーナルの追加が必要。既存のUTXOセットは使用の都度1つのキー:バリューの更新が必要で、最悪ブロック内のトランザクション出力の使用が全てアーカイブされた出力であったとしてもブロックの検証レイテンシーは現状の2倍以内になると期待される。

Slow-Path:保留中のTXO Commitmentsの計算

優先順位の低いバックグラウンドタスクでTXOジャーナルをフラッシュし、TXO MMRに各ブロックが使用した出力を記録し、MMRデータをハッシュしTXO commitmentsダイジェストを取得する。さらにこのバックグラウンドタスクはTXO commitmentsに記録された出力をSTXOから削除し、不要になったTXO commitment を剪定する。

TXO commitmentの計算のスループットは既存のUTXOのみのスキームより悪くなる。

TXO MMRの詳細な実装

各TXO MMRの状態は、ほとんどの情報が共有されている前のものの修正で、多数の TXO commitmentsの状態を効率的に保存している。マークル化されたデータ構造では循環参照は不可能なので、ガベージコレクションは単純な参照カウンタで充分。不要になったデータはデータベースから削除することで剪定できる。

実際に構成も見たほうが理解しやすいと思うkので具体例で考えてみる。

2つのtxoutsを持つ以下のTXO MMRを考える。(これを状態#0と呼ぶ)

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

別のエントリーを追加すると状態#1になる↓

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

commitment #1で状態#0のデータがどのように再利用されたかに注目してほしい。状態#2を得るためさらに2つのエントリーを追加する。

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

このケースでは状態#1のデータは再利用されていない。

ここで状態#2が最新のブロックによってブロックチェーンにコミットされたとする。状態#2で作られた出力を使おうとする将来のトランザクションは、それが未使用であることを証明する責務がある。基本的には状態#2のMMRのデータを提供しなければならない。これによりTXO MMRに新しいtxoutを追加するために必要最低限のデータを残し、データを剪定することができる。

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

実装の詳細に応じて、ノード"2"と"e"に必要なデータはそのハッシュダイジェストだけである。

さらに3つのtxoutを追加すると状態#3になる。

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

ここで最近作られたtxout fが使用されたとする。MMRを更新するための全てのデータがあり、状態#4になる。ここでは2つの内部ノードと1つのリーフノードを変更する。

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

もしアーカイブされたtxoutが使われると、トランザクションは最近コミットされたTXO(このケースでは状態#2)にマークルパスを提供するよう要求する。txout bが使用された場合であれば、トランザクションは状態#2から以下のデータを提供する必要がある。

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

ローカルのTXO MMRをベースに上記データを復元すると↓

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

この時点でまだ状態#4は変更していない。txout bが使用されたことを示すようデータを更新し状態#5にする。

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

続いて、現在状態#3がチェーンにコミットされている状態で、状態#3で作られたtxoutを使用するトランザクションを作りたい場合、状態#3のデータからなるTXO proofを提供する必要がある。出力gとhのリーフノードとその内部ノードが状態#3の一部であるため、それらを剪定する↓

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

最後にa、c、gの3つのtxoutを使って、新しい3つのtxout i、j、kを作る。状態#3が最新のコミットされた状態だったので、aとgを使用するトランザクションはそこまでのマークルパスを提供する必要がある。これには状態#2のデータの一部が含まれる↓

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

unpruningすると、状態#5のデータは以下のようになる。

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

a、c、gの3つの出力を使用し、新しい出力i、j、kを追加した結果以下のの状態#6になる。

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

再度、状態#4の関連データを剪定することができる。さらにSTXOセットの実装方法によっては、この状態以降の使用済みtxtoutに関連するデータも剪定することができる(配下のノードが使用済みとなった内部ノードを含む)。

まとめ&所感

  • 様々な要因によってBitcoinのUTXOのサイズは増加する一方で、フルノードを運用する際のボトルネックにもなっている。
  • 現状の実装ではUTXOセット1つのみの構成で、そこに全UTXOのデータが保持されているけど、アクセス頻度の低いUTXOをアーカイブして、高速にアクセスする必要のあるUTXOのサイズを削減しようというアプローチ。
  • アーカイブされたUTXOは、それがまだ未使用である証拠=TXO commitment proofsを提供することでUTXOとしての正当性を評価して使えるようにする。
  • TXO commitment では、全てのトランザクション出力(未使用・使用済み両方含む)からなるマークルツリー = Merkle Mountain Range (MMR)を構成する。
  • MMRは決定性があるインデックス可能な挿入型のマークルツリー。
  • 未使用・使用済み両方含んでるからUTXOじゃなくTXO Commitmentsなんだろう。
  • トランザクションでは、そのトランザクションで使用しようとしているUTXOが未使用であることをTXO commitment proofsを添付することで証明する。
  • TXO commitment proofsの提供が必要になるのはアーカイブ済みのtxoutsを使用するトランザクションの場合のみ。
  • アーカイブ済みのtxoutを使用するトランザクションは、最新のTXO commitmentへのマークルパスを提供する。
  • UTXOの削減以外の用途でもMMR使ったコミットメントの仕組み利用できるんじゃないかなー。