Merklix ツリーを使用して UTXO セットをチェックポイントする

前回の投稿では、順序付けられていない集合やグラフを記述する暗号化方法として Merklix ツリーを紹介しました。これにより、要素が o(ln(n)) データ構造に含まれているかどうかを証明し、その完全な内容を知らなくても、これらの証明を使用して構造を変更することが可能になります。

ここでは、ビットコインなどのブロックチェーン技術で UTXO セットを処理するためにこれをどのように使用できるかを説明します。

Merklixは存在を証明するか

UTXO の部分に入る前に、Merklix ツリーを使用してセット内の要素の有無を証明する方法を示しましょう。

この例では、Item1 がコレクション内にあることを証明しようとしています。これを説明するには、Item1 またはそのハッシュ 6eec を使用します。図では、Item1 を表示したくないか、単に証明を簡潔にしたいため、これらが赤で強調表示されています。

次に、ツリー内でルートにつながるパスを提供します。このパスは図の中で黄色で強調表示されています。証明を検証するには、6eec を 3738 でハッシュして bf1b を取得し、これを d9fe でハッシュしてツリーのルートである 2812 を取得します。要素が実際にツリー内にあることが証明されました。

ここで、Item5 がツリー内に存在しないことを証明したいとします。ハッシュは cd5a で、c=1100 です。

黄色の要素からも同じ証明が得られます。 bf1b と d9fe を一緒にハッシュすることで、これらが両方ともツリーの一部であり、兄弟であることを確認できます。 bf1b は 0 から始まるすべての要素を子として受け取り、d9fe は 111 から始まる要素を受け取ります。したがって、Item5 はこれらのサブツリーのいずれにも属すことはできません。ただし、ツリー内にある場合は、これら 2 つのノードの間にあります。これら 2 つのノードは同じレベルにあるため、それらの間には何もないことがわかっており、Item5 はセット内にないと結論付けることができます。

Merklix証明を使用してツリーを更新する

ツリー内のパスは証明によって提供されるため、証明を使用してツリー自体を変更することもできます。繰り返しますが、この作業では、ツリーのルートより先の事前の知識は必要ありません。これで、Item5 がツリー内にないことが証明されましたが、おそらくそれを追加したいのでしょうか?

ツリー内の新しいノードは赤で表示されます。図の黄色の部分は証明のブロックを表しています。ご覧のとおり、Item5 が挿入されると、証明内のハッシュのみを使用してツリーのルートを計算できます。

Item1 がコレクション内にあるという証明もあるので、これを削除しましょう。

もう一度言いますが、削除結果を計算するために必要な一意のハッシュは、証明に含まれているか、Item5 が挿入されたときに計算されている必要があります。

このことから、次のように結論付けることができます。k << n の場合、n 要素の Merklix ツリー内の k の変更のセットを O(k * ln(n)) で維持でき、k が大きくなるにつれて O(k) に近づく傾向があります。バリエーション セットは図に赤で表示されます。

Merklixツリーを使用してUTXOセットに関する証明を生成する

UTXO セットは、txid をキーとして使用し、未使用の出力のシリアル化を値として使用することで、Merklix ツリーで表現できます。わかりやすくするために、上の図ではハッシュ値をキーとして使用していますが、必ずしもそうする必要はありません。未使用の出力がどのようにシリアル化されるかについては詳しく説明しません。しかし、概念を理解するにはこれで十分です。

ネットワーク経由でトランザクションを送信するときに、UTXO セット内の入力の証明を送信することもできます。これにより、トランザクションとアテステーションを受け入れるノードは、特にセットが大きくディスク上に保存する必要がある場合に、時間のかかるプロセスになる可能性がある UTXO セットのクエリを回避できます。

さらに、これによりノードは UTXO セットの一部を削減できるようになります。存在証明を使用して、UTXO セットを更新し、プルーニングされた部分を含めることができます。トランザクションに証明がない場合、プルーニングされた UTXO セットのその部分を持たない別のノードから証明を要求できます。証明によって入力が UTXO セット内にあることが示された場合、他の当事者に対して検証することができ、これが有効であれば、トランザクションを他のノードに転送できます。証明が存在しないことを示す場合、トランザクションは無効として拒否されます。

一般的に、ネットワーク上のノードは互いに信頼すべきではないと考えられています。証明できない場合は問題にはなりません。ノードは嘘をつくことはできません。さらに悪いことに、ノードが応答を拒否する可能性があり、その場合、要求は別のノードに転送される可能性があります。

したがって、実際に UTXO セットを照会する必要があるノードはごくわずかであり、その作業は多くのノードに分散できます。これは、ビットコイン ブロックチェーンにおける水平スケーリングの最初の例となります。この対策により、各シャードを処理するノードのサブセットのみを持つことにより、UTXO セットを非常に大きなサイズにまで拡大することができます。サブセット内のノードは、要求されたシャードの独自のサブセットを担当します。

たとえば、約 5000 個のノードがある場合、シャードあたり約 78 個のノードで UTXO を 64 通りに分割できます。

これらのノードの半分が信頼できず、リクエストに応答しないと仮定しても、シャードあたり 39 個のノードが残ります。

これにより、各ノードのストレージ要件が 64 削減され、UTXO チェックのワークロードが 2500 削減されます。絶対数で言えば、1.5Gb の UTXO セットにはノードあたり約 24Mb のメモリが必要であり、ネットワークが現在のワークロードを処理するためにブロックでチェックする必要があるのは UTXO のごく一部だけです。

ノードが、高速のお金をメモリ内に保持し、ディスクにコミットして、非同期的にメモリから節約するなどのインテリジェントな戦略を採用すると、ネットワーク全体で UTXO 要求の非常に高いスループットを実現でき、重大な問題を引き起こすことなく UTXO セットを桁違いに増やすことができます。

ブロック内のUTXOセットのチェックポイント

ノードはブロックチェーンの履歴全体をたどることで UTXO セットを再構築できますが、これは新しいノードの自己起動時間が o(n*t) であることを意味します。ここで、n はトランザクション量、t は時間です。これは時間が経つにつれて悪化するばかりです。ノードがルートハッシュの UTXO セットを取得できる場合、ノードはすぐに有効になります。

これは、ソフトフォークとしてコインベーストランザクションに配置することで実行できますが、ハードフォークとしてブロックヘッダーに配置する方が適切です。このようにして、ノードは接続されている限りネットワーク上で検証を開始し、既知の有効なブロックを逆検証してネットワーク プロセスとして転送することができます。