スパースマークルツリーの多値証明とは何ですか
編集者注: この記事は以下からのものです。イーサリアム愛好家 (ID: ethfans)編集者注: この記事は以下からのものです。
イーサリアム愛好家 (ID: ethfans)
、著者：Jim McDonald、翻訳および校正：Pei Qi & A Jian、Odaily の許可を得て転載。
最初のレベルのタイトル
ポピュラーサイエンス | メルケル首相の切り捨てとは何ですか
スパース マークル マルチプルーフ (Sparse Merkle multiproofs) は、マークル ツリー トランケーション (マークル ポラード) の代替手段であり、マークル ツリー上の複数の値の存在を証明するためのスペースを提供でき、節約の証拠となります。マークル証明とマークル木切り捨てとは何かについては、前の記事で説明しました。この記事を読む前に、これらの概念を読んで理解しておくことをお勧めします。次に、本文では下図のマークル ツリーを使用して、多値の証明を説明します。
画像の説明
スパース多値証明は、Vitalik Buterin によって最初に提案されました。
多値証明
画像の説明
-図2、3、4：それぞれバナナ、ピーチ、キンカンに対応するメルケルの証明-
上の図からわかるように、3 つの証明には中間分岐 (つまり、緑色でマークされた部分) の合計 9 つのハッシュ値が含まれています。各証明には 3 つのハッシュ値があります。これら 3 つの証明を次の図に示す構造に組み合わせると、多値の証明になります。
画像の説明
-図5：バナナ、ピーチ、キンカンに対応するマークル多値証明-
スパース多値証明
マークル ツリーの多値証明によりストレージ スペースがいくらか節約されますが、データの一部は他の方法で取得できるため、これらのデータを削除するとストレージ スペースをさらに節約できます。 (翻訳者注: 他の手段で取得できるデータは、必要なときに取得できる限り、校正刷りに保存する必要はありません)
画像の説明
-図6：マークルツリーの多値証明で削除できるハッシュ値（黄色のマークを参照）-
これらのハッシュ値を削除すると、次の図に示すように、マークル ツリー内のスパースな複数値の証明を取得できます。
画像の説明
-図 7: スパースマークルツリーの多値証明-
スパースマークルの多値証明により、含める必要のあるハッシュの数が 9 から 3 に減ります。スパース多値証明は、同じ証明に対して 6 つのハッシュを必要とするマークル切り捨て証明よりも効率的です。
検証者がスパース多値証明を取得した後、それらの値がマークル ツリーの一部であることを検証するには、次の手順を実行する必要があります (マークル ツリーでは、左から右、上からの順に)底）：
(翻訳者注: 「値をハッシュする」とは、値をハッシュ関数の入力として使用し、出力のランダムな文字列を取得することを意味します)
バナナをハッシュして bc4f...8d3f を取得する
ハッシュピーチで59a0…421dを獲得
ハッシュキンカンで2aab…6f791を入手
bc4f...8d3f と 59a0...421d をハッシュして 9c15...5dec を取得します
2aab…6f79 と 45cf…14d9 をハッシュして a6e4…87df を取得します
d596…66ef と 9c15…5dec をハッシュして c0b7…da30 を取得します
e336…ed14 と a6e4…87df をハッシュして 6ff9…8e3d を取得します
c0b7...da30 と 6ff9...8e3d をハッシュして d576...ffd9 を取得します
この時点で、最終的なハッシュ値とマークルツリーのルートハッシュ値を比較することができ、両者が一致していれば、すべての値がマークルツリーにあると判断されます。
次の図は、マークル ツリー内の値と証明の数が変化したときに、マークル ツリーの切り詰められたマークル ツリーとマークル ツリー内のスパース多値証明がマークル証明を保存するときに節約できる記憶域の量を比較しています。
多値証明の節約は、マークル ツリー内の証明された値の位置と、削除できる中間ブランチ ハッシュの数に依存するため、おおよその値であることに注意してください。
スパース多値証明とマークル切り捨ての比較
上の表からわかるように、スパース多値証明はマークル ツリー トランケーションよりも多くのストレージ スペースを節約します。では、なぜマークル ツリー トランケーションを使用するのでしょうか?スパース多値証明には、切り捨てられたマークル木と比較していくつかの異なる特性があるため、主な点は次のとおりです。
多値証明方式では、すべての値の証明がまとめて生成・検証されますが、切り捨て方式では、各値の証明が個別に生成・検証されます。および関連する証明が必要です。多値証明の場合、検証対象の複数の値と、複数の値の対応する証明を取り出す必要があります)
スパースな多値証明では、証明の生成と検証により多くのメモリと CPU サイクルが必要になります
疎な多値証明は、並行して生成および検証することが困難です
スパース多値プルーフのサイズは可変ですが、マークル ツリーの切り捨てのプルーフ サイズは、マークル ツリーとプルーフの総数を考慮すると固定です。
https://github.com/場合によっては、情報の送信に使用されるエンコード システムが異なるため、スパースな多値証明にはマークル ツリーの切り捨てよりも多くのスペースが必要になる可能性があるため、使用する前にテストすることをお勧めします。
