问题标签 [merkle-tree]

正如文章所建议的那样，我理解使用 Merkle 树来识别数据中的不一致背后的想法

• 关键概念：使用 Merkle 树检测数据中的不一致
• 默克尔树 | 辉煌的数学与科学维基

从本质上讲，我们使用递归算法从我们要验证的根向下遍历，并跟踪存储的哈希值与服务器不同的节点（具有可信哈希值），一直到不一致的叶子/数据块。

如果只有一个这样的块（叶子）被损坏，这意味着我们沿着一条路径向下到叶子，即 log(n) 查询。

但是，在多个不一致的数据块/叶子的情况下，我们最多需要 O(n) 个查询。在极端情况下，所有数据块都损坏了，我们的算法需要将每个节点发送到服务器（身份验证器）。在现实世界中，由于网络，这变得昂贵。

所以我的问题是，对基本的从根遍历算法有什么已知的改进吗？我能想到的一个可能的改进是查询中间节点的级别。例如，在下面的树中，我们向服务器发送第二层的两个节点（'64' 和 '192'），对于任何返回不一致的节点，我们递归地转到该子树的中间层 -类似于基于高度的二进制搜索。

这将我们的最佳情况时间从 O(1) 增加到 O(sqrt(n))，并且可能在一定程度上减少了我们最坏情况的时间（我还没有计算出多少）。

我想知道是否有比这更好的方法？我尝试在 Google Scholar 上搜索相关文章，但看起来大多数以算法为中心的论文都涉及 merkle-tree 遍历问题，这与上述问题不同。

提前致谢！

对于包含 128 个数据块的哈希树，您需要执行多少次哈希检查才能定位错误？假设错误只发生在一个块上。

我正在尝试使用 merkletreejs 库测试 merkle 证明，但我不知道为什么会这样

但这不是吗？

我正在阅读有关区块链 Merkle 树和级别 DB 的信息。我的查询与区块链中使用的树有关。与大多数区块链一样，level-DB 用于将数据存储在键值对结构中，甚至 level-DB 也使用合并日志树。那么为什么需要使用 Merkle 树，甚至级别 DB 也是使用树结构来存储数据。

使用本网站的插图： https ://transparency.dev/verifiable-data-structures/

在此图像中，树根是“E”。为了验证文档 2 的存在，审计路径需要哈希 A、哈希 D 和哈希 E。

但如果添加另一个文档：

现在什么是老树根（E）不再重要。组成“E”的组合是节点“C”和“D”的散列。但是对于树中的第四个文档，“C”和“D”永远不会被散列。

文档 2的新完整审计路径是哈希 A、哈希 G、哈希 H。

显然，始终可以计算 Merkle 树中任何节点的完整审计路径。但是随着树增长到数以百万计的条目，在某些时候，从旧的 Tree Root审计变得更加容易。

意思是，如果您已经通过第一个图像中的“E”验证了审计跟踪，那么在尝试验证第二个图像中的审计跟踪时，您现在有什么好处？如果树根恰好位于完美的二叉树中，那么它们是否仅对未来的审计有意义？

我在 Python 中的实现计算了大约 1500 个输入哈希的 merkle 根哈希：

由于 merkle 根计算了 1000 次，因此一次计算大约需要 5ms：

如何提高计算速度？这段代码可以优化吗？

到目前为止，我已经尝试在 Python 和 C++ 中展开递归函数。但是，性能并没有提高，大约花了 6 毫秒。

编辑

该文件可在此处获得： txids.txt

编辑 2

由于评论中的建议，我删除了unhexlify和的不必要步骤hexlify。在循环之前，列表准备一次。

现在执行时间约为 4 毫秒：

我正在尝试尽可能优化 merkle 根计算。到目前为止，我在 Python 中实现了它，这导致了这个问题以及用 C++ 重写它的建议。

但是，与 Python 实现（~4s）相比，性能更差：

完整的实现和输入文件可在此处获得：test.cpp和txids.txt。

我怎样才能提高性能？默认情况下是否启用编译器优化？是否有比openssl可用的更快的 sha256 库？

我正在运行一个 Web 服务器，我在其中接收 JSON 格式的数据并计划将其存储在 NoSQL 数据库中。这是一个例子：

我曾想过使用 Merkle 树来表示我的数据，因为 JSON 也是一种树状结构。

本质上，我想做的是将我的数据存储在（或作为）更安全的去中心化树状结构中。许多实体将有权从中创建、读取、更新或删除 (CRUD) 记录。理想情况下，这些 CRUD 操作需要从网络中的其他实体进行验证，这些实体也将持有数据库的副本。就像在区块链中一样。

我遇到了设计/概念问题，我试图了解如何将我的 JSON 转换为 Merkle 树结构。这是我的节点类：

我对此的概念/设计感兴趣，因为我无法弄清楚它是如何工作的。知道如何在 Merkle 树中保存/存储我的 data_example 对象吗？（可能吗？）

我刚刚开始阅读有关稀疏默克尔树的内容，并且遇到了一个函数（获取值），该函数用于查找指定键的值。我在互联网上找不到可以解释 get value 函数如何工作的解释。

我的理解是每个节点都是 256 位的，所以可以有 2^256 个叶子节点并且键被索引。所以我们从根开始，根据天气选择左节点或右节点，位为 0 或 1，但我无法理解 v = db.get(v)[32:] 语句。它如何引导我获得所提供密钥的价值？

来自https://github.com/fmerg/pymerkle

（我知道 0x00 和 0x01 只是“特定的字节值”，它们可以是任何东西）

为什么这行得通？

理论上，攻击者不能找到以 0x00 开头的伪造内容的叶子哈希吗？

预先添加父节点的哈希节点有什么好处？