我正在尝试实现一个默克尔树一致性证明，但我无法理解算法。

Question

我正在尝试使用这篇论文实现默克尔树一致性算法：

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，并且b = true。

该函数通过递归代码流程，直到我们到达这种情况：

E现在有2个元素，因此n = 2。

m = 1，由于递归调用m<k的先前减法以及b = false。

如果m和n不相等，则不会陷入m = n && b = false的情况。

k现在被计算为2，因为向上取整将结果从log2(n)/2的1/2修正为1。

我们进入了m <= k的情况，并且再次使用完全相同的参数递归调用函数。现在我们陷入了一个无限循环。

然而，我似乎无法找出我的错误所在。我觉得k计算中的向上取整是问题所在。这基本上使得无法跳出循环，因为在一些迭代后，k似乎总是比m高。

对于我的错误有什么建议/提示吗？

编辑：有趣的是，当n是奇数时，该算法似乎完美地工作。它只似乎在偶数情况下失败。我刚刚尝试了一个新的有7个叶子的树，它像魔术一样运行，提供了证明一致性所需的正确节点。

然而，我仍然无法弄清楚必须进行哪些更改才能使其与偶数配合使用。

- Sossenbinder

Answer 1

这本书似乎有误。需要单独处理m = n且b = true的情况。可以在RFC 6962中找到更详细的算法描述。

以下是修正方法：

- Anton

---

这是完美的解决方案。请注意，我还对您的答案进行了编辑，因为我发现书中算法中还有其他错误。 - Sossenbinder

@Sossenbinder 在你的编辑中写道： “我想补充一下，书中显示的 k 的计算不正确。如果使用此公式，并且我们遇到 n = 9 的情况，则 k 将为 4 而不是 8。” 我不认为这是真的。 n = 9 ⇒ log(n/2) = log(4.5) ≈ 2.17 ⇒ ⌈log(n/2)⌉ = 3 ⇒ 2^⌈log(n/2)⌉ = 8。⌈x⌉ 是 上取整函数 的符号。 - Anton

确实，我在计算中肯定做错了什么。我使用了向上取整函数，但可能是括号的位置或其他地方出了问题。 - Sossenbinder