私はこの論文でマークルツリーの一貫性アルゴリズムを実装しようとしています:
ただし、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 枚の葉の新しいツリーで試してみたところ、一貫性を証明するために必要な正しいノードが提供され、魅力的に機能します。
ただし、偶数で機能させるためにどのような変更を加える必要があるかはまだわかりません。