问题标签 [merkle-tree]

为了简单起见，我的问题是：如何尽快散列一个字符串（大约 200 个字符）。安全性并不重要，但碰撞很重要。

注意：经过快速调查，似乎MurmurHash3可能是最佳选择。我愿意接受任何评论，否则'

首先，我知道还有很多其他类似的问题，但我还没有找到令人信服的答案。

我有一个对象列表，每个对象都包含一个保存到数据库的大约 3k 段落的列表。每隔 X 小时，这些段落就会重新生成，我需要查找是否有任何段落发生了变化，如果是，则只推送那些新段落。

我发现找到差异的最快方法（知道大部分时间内容是相同的）是创建一个MerkleTree，将其保存到数据库，然后遍历 MerkleTree 以找到差异，而不是比较段落本身.

就我而言，这意味着我将每秒创建一万个哈希值来与数据库中的哈希值进行比较。因此，我需要一种非常有效的方法来创建这些哈希。我不关心安全性，我只需要确保碰撞次数保持非常非常低。

Java中最好的算法是什么？

在我的例子中，主要对象由 Sections 组成，Sections 由 Languages 组成，Languages 由 Paragraph 组成。比较策略是：

1）如果对象哈希相同，则停止，否则转到2）

2）在所有Section上循环，只保留具有不同哈希的Section

3）循环这些部分的所有语言，只保留具有不同哈希的语言

4）循环所有这些语言的所有段落，如果哈希不同，则推送新内容。

当您拥有一棵 Merkle 树时，验证对一个叶节点的更改所需的最小哈希数是多少？

我的理解是否正确，首先，只需要顶部哈希（Merkle 树根或 Merkle 树根的哈希）？然后一旦修改了叶子，您需要在下降到被修改的叶子节点时获取“访问”的每一行的哈希值？

因此，如果一个根有，比如说，十个孩子和一个孙子被修改，我想验证那个特定的孙子，我需要获得新的默克尔根哈希，十个孩子的哈希和孙子的父母的孩子。

因此，在每次修改时，您总是需要至少获取第一行的所有哈希值？（否则你如何重建和验证默克尔根哈希？）

分区数量如何影响 Cassandra 集群中的修复时间？

分区数量越少，默克尔树算法和修复过程的速度越快，这是否正确？

将更快地修复 -

比

如果 count(id2, id1) > count (id1) ？

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

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 = 1, 由于之前在递归调用中的减法m < k, 以及b = false.

我们不属于m = n && b = falseif、asm和n不相等。

k现在再次计算为 ，2因为上限正在校正1/2从log2(n)/2到的结果1。

我们陷入了这种m <= k情况，再一次，我们用完全相同的参数递归地调用函数。现在我们处于无限循环中。

但是，我似乎无法弄清楚我做错了什么。我觉得k计算中的上限是问题所在。它基本上使它不可能跳出循环，因为k似乎总是比m经过一些迭代后要高。

对我的错误有任何建议/提示吗？

编辑：有趣的是，当 n 为奇数时，该算法似乎可以完美运行。它似乎只对偶数失败。我刚刚用一棵 7 片叶子的新树进行了尝试，它就像一个魅力，提供了证明一致性所需的正确节点。

但是，我仍然无法弄清楚必须进行哪些更改才能使其适用于偶数。

我正在阅读有关 Cassandra 修复的文档，它说

比较从 Merkle 树的顶部节点开始。如果没有检测到差异，则该过程进行到左子节点并比较，然后是右子节点。

但是，Merkle 树的非叶子节点表示：

树中较高的每个父节点都是其各自子节点的散列。因为 Merkle 树中较高的节点代表树下的数据，Casandra 可以独立检查每个分支，而不需要协调节点下载整个数据集。

据此，以及我发现的其他数据结构文章，它们都表明只有在两棵 Merkle 树的根不同时才进行比根更深的比较。我不确定文档是否正确描述了我可能理解错误，或者它实际上有错误？

我试图了解比特币块解决尝试是如何工作的。

我看到一个 nonce 是一个 32 位数字，所以要尝试大约 40 亿个值。另外，我看到了一个著名的矿池，手头有 500 Ph/s 的功率。我发现有一个特定的块在 40 分钟内解决了。

因此，即在该池上计算 (40 x 3600) x (500 x 10^15) = 7.2 x 10^22 哈希，以解决一个块。

这意味着在这 40 分钟内，随机数已经“循环”了 167630 亿次。

所以我想知道在每个 nonce 周期之后又做了 167630 亿件事情是什么？（“1 个随机数周期”从 0 变为 4294967295）？

我看到我们可以按一定比例更改时间戳，以及默克尔根哈希。

默克尔哈希和时间戳的计算和使用不是比随机数更严格吗？

那167630亿只是时间戳和默克尔的变化？我们可以根据需要重新生成尽可能多的独特默克尔哈希和更改时间戳吗？

你能给我举个例子吗？对不起，如果我的观点有点偏见，我从这个开始。

当 Cassandra 进行数据完整性检查时，它会进行验证压缩，但这究竟意味着什么？我的理解是，它会创建一个将临时存储的 SSTable（直到修复完成），然后从该单个创建的 SSTable 生成 Merkle 树。如果任何 Merkle 树的叶子未能通过验证，则用于创建该叶子的分区（来自在验证压缩期间创建的 SSTable）将被流式传输到另一个节点。然而，一位朋友告诉我，Merkle 树是从每个（以前存在的）SSTable 生成的。

那么，生成了多少个 Merkle 树，一个或与 SSTables 一样多？

我有一个带有私有数据的 JSON 对象。它具有以下（复杂！）结构：

我想创建一个哈希树，允许其他人验证我发送给他们的数据片段——例如，通过在公共区块链上声明根。

例如，我希望能够只分享我的年龄，并让接收者能够计算散列并检查它是否正确。稍后，我可能想向其他用户透露我的第一个孩子名叫“Alice”，她最喜欢的颜色是“粉红色”。

我的理解是默克尔树是二元的——每个节点只有两个叶子。是否有一种固定的模式或方法可以始终如一地将上述复杂结构“扁平化”为默克尔树？

或者，是否有另一种类型的哈希树结构天生就可以为数据提供这种复杂性？

例如：

似乎无论树是如何构造的，重要的是原始数据的结构以某种方式被保留并且可以由验证器仔细检查。

• 例如，阻止我提供孩子的年龄而不是我自己的年龄。
• 在二叉默克尔树的情况下：考虑到叶索引可能代表完全不同的数据，具体取决于它们拥有的孩子的数量。

解决这个问题的最佳方法是什么？我正在使用 Node.JS 和整洁的Merkle Tools 包，但我不确定 merkle 树是否适合这项工作。如果我遗漏了任何重要的内容，或者您​​有任何澄清问题，我会尽力改进问题。

非常感谢。

使用 Merkle 根哈希和 Merkle 路径，可以验证给定对象（即交易）是否存在于 Merkle 树中。但是是否有可能告诉树中没有其他对象的重复。

例如，如果我有一个交易列表的 Merkle 根和一个交易的 Merkle 路径。然后，我可以验证我的交易是否存在于 Merkle 树中，但我是否也可以告诉只有一个这样的交易，而不是两个？

我试图了解 Merkle 树在 SPV 和区块链技术中的许多其他场景中是如何工作的，但我无法理解这个问题：在验证交易时如何生成 Merkle 路径。

在下图中，假设我想验证事务2 ，我知道需要3、01、4567和根的哈希值，但是，我想知道这个默克尔路径首先是如何生成的。

当事务2被提供给服务器/节点时，服务器/节点如何知道返回哪个路径来验证2？如果服务器已经知道这条路径，为什么服务器不验证它，为什么还要返回这条路径？

谢谢，

_{（来源：codeproject.com）}