Merkle证明的实现

Question

目前，我正在实现锈蚀中的Merkle树。我面临的问题之一是产生证明的复杂性。意思是我给验证者的向量，以检查是否存在一个元素。很多人说我应该横越树来找到元素的路径(如果元素是数据集的一部分)，但是我不明白如果Merkle没有排序，它将如何工作。我是不是遗漏了什么？根据我的理解，最好的方法是找到叶子(如果它存在的话)，然后找到你爬上树的路。在这种情况下，复杂度将是O(N)来生成。

提前感谢！

Answer 1

根据我的理解，最好的方法是找到叶子(如果它存在的话)，然后找到你爬上树的路。在这种情况下，复杂度将是O(N)来生成。

这里有两个步骤，不清楚您认为哪些可能需要O(N)时间。

第一步是查找叶；是的，如果您采用单独检查每个元素的方法，如果存在O(N)元素，这显然需要花费O(N)时间。另一方面，这并不一定是唯一可行的算法。如果我们有我们的N元素，那么我们可以构建一个数据结构(例如，一个哈希表)来快速查找元素，如果认为需要更快的查找的话。

第二步是生成身份验证路径；是的，生成整个Merkle树(以及计算根)将花费O(N)时间，而且没有办法解决这个问题。另一方面，一旦我们构建了树，我们通常可以保存中间节点的值。在最直接的方法中，我们只需保存所有中间节点；这需要O(N)内存；另一方面，构造身份验证路径只需复制适当的节点值，这可以在O(\log N)时间内完成。