問題タブ [merkle-tree]

簡単にするために、私の質問は、文字列 (約 200 文字) をできるだけ早くハッシュする方法です。セキュリティは重要ではありませんが、衝突は大きな問題です。

注: 簡単な調査の結果、MurmHash3が最良の選択であると思われます。私はそうでないと言っているどんなコメントにもオープンです。

まず、他にも同様の質問がたくさんあることは知っていますが、説得力のある答えはまだ見つかりませんでした。

オブジェクトのリストがあり、それぞれがデータベースに保存される約 3k の段落のリストを含んでいます。X 時間ごとに、これらの段落が再生成されます。変更された段落があるかどうかを確認し、変更されている場合は、それらの新しい段落のみをプッシュする必要があります。

違いを見つけるために私が見つけた最も簡単な方法 (ほとんどの場合コンテンツが同一であることを知っている) は、MerkleTreeを作成し、それを DB に保存し、段落自体を比較する代わりに、 MerkleTree を反復処理して違いを見つけることです。 .

これは、私の場合、DB にあるものと比較するために毎秒 1 万のハッシュを作成することを意味します。したがって、これらのハッシュを作成する非常に効率的な方法が必要です。セキュリティについては気にしません。衝突の数が非常に少ないままであることを確認するだけで済みます。

そのためにJavaで利用できる最良のアルゴリズムは何でしょうか?

私の場合、主なオブジェクトはセクションで構成され、言語で構成され、パラグラフで構成されています。比較戦略は次のとおりです。

1) オブジェクト ハッシュが同一の場合は停止し、そうでない場合は 2) に進みます。

2）すべてのセクションでループし、異なるハッシュを持つセクションのみを保持します

3) それらのセクションのすべての言語をループし、異なるハッシュを持つ言語のみを保持します

4) これらすべての言語のすべての段落をループし、ハッシュが異なる場合は、新しいコンテンツをプッシュします。

マークル ツリーがある場合、1 つのリーフ ノードへの変更を検証するために必要なハッシュの最小数はいくつですか?

最初は、トップ ハッシュ (マークル ツリー ルートまたはマークル ツリー ルートのハッシュ) のみが必要であるという私の理解は正しいですか? そして、葉が変更されたら、変更された葉ノードに降りながら、「訪問した」各行のハッシュを取得する必要がありますか?

たとえば、ルートに 10 個の子と 1 個の孫があり、それらが変更されている場合、その特定の孫を検証したい場合、新しいマークル ルート ハッシュ、10 個の子のハッシュ、およびそのハッシュを取得する必要があります。孫の親の子供。

変更のたびに、少なくとも最初の行からすべてのハッシュを取得する必要がありますか? (そうでなければ、マークル ルート ハッシュをどのように再構築して検証しますか?)

パーティションの数は、Cassandra クラスターの修復時間にどのように影響しますか?

パーティションの数が少ないほど、マークル ツリー アルゴリズムと修復手順の速度が速いというのは正しいですか?

より速く修復します -

よりも

カウント (id2, id1) > カウント (id1) の場合?

私はこの論文でマークルツリーの一貫性アルゴリズムを実装しようとしています:

https://books.google.de/books?id=CokSDQAAQBAJ&lpg=PA147&dq=merkle%20consistency%20proof&hl=de&pg=PA148#v=onepage&q&f=false

ただし、ConsProofSub 部分を実行すると常に無限ループに陥ってしまうため、整合性チェックに行き詰っています。

例：

新しい木には8、古い木には7葉があります。

前の関数をm = 7使用して、新しいツリーの葉を ベクトルEおよびtrueとして取得していbます。

この状況に到達するまで、関数は再帰的なコード フローを通過します。

E には2要素があるので、n = 2.

m = 1m < k、およびの再帰呼び出しでの以前の減算によるものb = falseです。

とが等しくないので、 m = n && b = falseif には該当しません。mn

kは、再び として計算されています。これは、天井がから2の結果を に修正しているためです。1/2log2(n)/21

このケースに陥り、m <= kもう一度、まったく同じパラメーターを使用して関数を再帰的に呼び出しています。今、私たちは無限ループに陥っています。

しかし、私は自分が間違っていることを理解できないようです。k計算の上限が問題な気がします。いくつかの反復の後kよりも常に高く見えるため、基本的にループから抜け出すことができなくなります。m

ここでの私の間違いに関するアドバイス/ヒントはありますか?

編集: 興味深いのは、n が奇数の場合にアルゴリズムが完全に機能するように見えるという事実です。偶数の場合にのみ失敗するようです。7 枚の葉の新しいツリーで試してみたところ、一貫性を証明するために必要な正しいノードが提供され、魅力的に機能します。

ただし、偶数で機能させるためにどのような変更を加える必要があるかはまだわかりません。

私はマークル ツリーが SPV やブロックチェーン テクノロジの他の多くのシナリオでどのように機能するかを理解しようとしていましたが、トランザクションの検証でマークル パスがどのように生成されるかという 1 つの質問について理解できませんでした。

下のグラフで、トランザクション2を検証したいとします。 3、01、4567のハッシュとルートが必要であることは理解していますが、そもそもこのメルケル パスがどのように生成されるのか疑問に思っています。

トランザクション2がサーバー/ノードに渡されると、サーバー/ノードは2を検証するためにどのパスを返すかをどのように知るのでしょうか? サーバーがこのパスを既に知っている場合、なぜサーバーはそれを検証せず、わざわざこのパスを返すのでしょうか?

ありがとう、

_{(ソース: codeproject.com )}