問題タブ [hashtree]

特定のトランザクションが与えられた場合に、ハッシュ ツリー構造を適切にナビゲートする方法を見つけようとしています。私はすでにその質問に対する答えを持っていますが、彼らがどのようにしてそれに到達したのか完全にはわかりません.

これはハッシュツリー構造へのリンクです

質問:アイテム {1,3,4,5,8} を含むトランザクションが与えられた場合、トランザクションの候補を見つけるときにどのハッシュ ツリー リーフ ノードにアクセスしますか?

答え: L1、L3、L5、L9、L11

これはアプリオリの一種であることは理解しているので、最初に考えたプロセスは、最初のノード レベル {1, 4, 7}、{2, 5, 8}、および {3, 6, 9} を調べ、もしあればこれらの 3 つの候補項目セットのうち、トランザクションに少なくとも 1 つの番号が含まれている場合は、次のノード レベルに進みます。ここでは、トランザクションに少なくとも 2 つの番号が含まれているかどうかを確認しますが、まったく機能しません。トランザクションを使用してこのタイプのハッシュ ツリーをナビゲートする方法を説明できる人がいれば、非常に役に立ちます。

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

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 枚の葉の新しいツリーで試してみたところ、一貫性を証明するために必要な正しいノードが提供され、魅力的に機能します。

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