LOCUS CHAIN 技術シリーズ 5：検証可能なプルーニング 第2章

原文标题：《LOCUS CHAIN TECH SERIES 5: Verifiable Pruning Chapter 2.》

作者：LOCUS CHAIN FOUNDATION

编译：ChainCatcher

階層的歪んだマークルツリー：検証可能な剪定のデータ構造
従来の歪んだマークルツリー

階層的歪んだマークルツリー（H-SMT）は、Locus Chainの検証可能な剪定をサポートする中心的なデータ構造です。H-SMTは歪んだマークルツリーに基づいており、これはマークルツリーの変種です。

マークルツリーは、各葉ノードが暗号ハッシュ値のラベルを持ち、各非葉ノードがその子ラベルから伝達される暗号ハッシュ値のラベルを持つ木構造のデータ構造です。ブロックチェーンでは、マークルツリーはリスト内のデータの存在を証明するために広く使用されています。

歪んだマークルツリー（SMT）は、各非葉ノードが葉ノードと非葉ノードを持つマークルツリーの一形態です。歪んだマークルツリーは、マークルツリーに基づく連結リストです。新しい根ノードを以前のSMTの上に追加することで、データをSMT連結リストに追加します。以前の根は新しい根ノードの子ノードとなり、新しいデータブロックも子ノードとして追加されます。SMT内のデータブロックの数は、SMTの高さから1を引いたものです。SMT内のノードは、その子ノードのハッシュ値を確認することで検証され、そのノード以前のすべてのノードのハッシュ値を効果的に計算します。

階層的SMT：SMTに基づいて構築された有向非循環グラフ

SMTはシンプルなデータ構造です。SMTの検証コストはデータの長さまたはO(N)に比例します。階層的SMTは、補助的な検証リンク（「ジャンプリンク」）を追加することで性能をO(log N)に向上させ、ジャンプノードの指数的距離を持ちます。

SMTは二分マークルツリーです。マークルツリーの各ノードのラベルは、その子ノードのラベルから伝達されるハッシュ値です。SMTでは、あるノードの最初の子は新しいデータブロックTnのハッシュ値を持ち、2番目の子は前の根ノードRn-1のラベルを持ちます。

H-SMTノードにはさらに1つの子ノードがあります。3番目の子ノードは、過去の点におけるマークルツリーのノードへのリンクを指します。この3番目の子を「ジャンプリンク」と呼びます。

ジャンプ距離

ジャンプリンクは、過去のノードのマークルルートハッシュ値を指します。技術的には、過去の任意のノードを使用できます。Locus Chainでは、ジャンプリンクノードの相対位置（または「ジャンプ距離」）は、事前定義された「ジャンプ基数」値とグラフの高さに基づいて決定されます。

特に、ジャンプ距離はジャンプ基準距離の倍数です。最小ジャンプ距離はbase、最大距離はbase^baseです。

ジャンプリンクの追加

既存のSMTにbase=3のジャンプリンクを追加してH-SMTを構築する例を挙げましょう。

ジャンプ距離は、ノードから基数へのオフセットに基づいて計算されます。オフセットは、ノードの高さnを基数で割った余りです。

offset = n mod 基数

したがって、ジャンプ距離はbaseオフセットのべき乗です。もしoffset=0であれば、距離は基から基のべき乗です。

Locus BFTコンセンサスアルゴリズムは、offset=1のノードにジャンプリンクを追加する例です。ノード4のラベルは、3つの子T4、R3、R1から伝達されます。

次に、offset=2のノードにジャンプリンクを配置します。offset=2のノードのジャンプ距離は3²=9です。実際、リンク距離が長くなると、ジャンプリンクを省略する方が効率的かもしれません。図4では、offset=2のジャンプリンクは、高さが(offset+baseoffset*k)のノードにのみ配置され、直線的な連結リストを形成します。

このプロセスをオフセットが底に達するまで繰り返します。図5はbase=3のジャンプリンクの最終結果です。

新しいデータブロックの追加

同じアルゴリズムが、新しいブロックTnを既存のSMTに追加するために適用されます。高さを使用してオフセットとジャンプ距離を計算し、次にh(Tn)、Rn-1、およびRn-jump_distanceに基づいて新しい根H-SMTノードのハッシュラベルを計算します。

ブロックの検証

検証者がH-SMTリスト内のノードのハッシュ値Ryを持っていると仮定し、検証者は前のブロックTx、またはブロックh(Tx)のハッシュがH-SMTに含まれているかを検証したいと考えています。これは、RyからRxへのパスを見つける問題であり、RxはTxの直接の親ノードです。検証者は以下の手順に従ってRyからRxへのパスを見つけることができます。

1) Ryから始めて、近くのノード{Ry-1, Ry-2, …, Ry-base}をチェックして、ノードRi (i>=x)への最長のジャンプリンクを見つけます。

2) iを記録し、Riを使用して手順1を繰り返し、iがxに達するまで続けます。

3) 手順1と2で見つけたすべてのノードのハッシュ値のチェーンを計算します。最終値がRyと一致すれば、TxはTyの先行ブロックです。

図6は、ノードR59から先行ブロックT8を見つける例です。隣接する先行リンクはR59→R58→R57に使用されます。R57からR30まで、距離27のジャンプリンクを経由します。距離9のジャンプリンクはR29からR11まで使用されます。最後にR11からR8までを通過します。

この例で通過したリンク数は9です。SMTでは、59--8=51回の通過が必要です。

現実世界の実装

前の例では基数3を使用しましたが、より大きな基数が実際の使用に適しています。Locus Chainでは一般的にbase値は10であり、base=10のジャンプ距離の範囲は10〜10¹⁰です。例えば、距離1999の2つのノードの最適なリンク通過数は28で、(11000 + 9100 + 9*10 + 9)から伝達されます。

偽造リンクの検出

悪意のある行為者は、不正なジャンプリンクを使用してH-SMTノードのハッシュ値を偽造する可能性があります。H-SMTでは、ノードへの複数のパスを交差検証することで、このような偽造ノード値を識別できます。

H-SMTは有向非循環グラフであり、2つのノード間の距離が基数を超える場合、常に2つ以上のパスが存在します。ノード間の各パスは1つのマークルツリーであり、各マークルツリーが計算するハッシュ値は一致しなければなりません。もし偽造されたノードが不正なハッシュ値を参照している場合、パス間のハッシュ値は一致しません。

この特性により、ランダムな遠距離の先行ブロックへの2つの異なるパスを選択し、パスのハッシュ値を比較することでノードを検証できます。

要約

長いチェーンデータの検証は、ブロックチェーンにおける計算集約的なコストです。一部のブロックチェーンシステムは、帳簿データの完全性を検証するために数時間の準備時間を必要とします。Locus Chainは階層的歪んだマークルツリーを通じてこの問題を解決しており、これはデータチェーンの検証コストをチェーンの長さの対数スケールに減少させる革新的なデータ構造です。