默克尔树简介：它是什么以及它如何运作？

Merkle Tree 是哈希值的二叉树，其中每个叶节点代表一条数据或一条数据的哈希。它用于有效地验证大量数据的完整性。它由 Ralph Merkle 于 1979 年发明，广泛应用于比特币和以太坊等加密货币。

哈希函数就像指纹机。它接受任何输入，例如文件、文本或数字，并生成一个唯一的输出，称为哈希，它比输入短得多。哈希就像输入的指纹。很难找到具有相同哈希值的两个不同输入。并且不可能从哈希中获取原始输入。

例如，如果您有一个名为“ kishan.jpg ”且大小为 1 MB 的文件，则可以使用哈希函数来获取长度仅为64 个字符的哈希值，例如0A6DF48A27EF7DB48B213DF3DBA84FAD1BB4FD9B47568DA1F570C067D9A4867F 。

即使更改文件中的一个像素，哈希值也会完全不同，例如C69E60E932F3D0C6C2363B68301E202551C09123A71F639E6AB3BC8F847BE4AF 。

所以你可以使用哈希来验证文件是否与之前相同。

但是如果你有很多文件怎么办？单独计算和存储每个文件的哈希值会很乏味。这就是默克尔树派上用场的地方。

Merkle 树就像哈希的家谱。您首先将每个文件的哈希值作为树的叶子。然后将哈希值配对并组合它们以获得新的哈希值。重复此过程，直到到达树的顶部，此时只剩下一个哈希值。这个哈希值称为默克尔根。

Merkle 根就像树中所有文件的指纹。如果任何文件发生变化，其哈希值也会发生变化，其上方的所有哈希值也会发生变化，直到 Merkle 根发生变化。所以你可以使用 Merkle root 来验证所有文件是否与之前相同。

但是如何验证特定文件呢？您无需下载并检查树中的所有文件。您只需要下载并检查从文件到 Merkle 根的路径上的一些哈希值。这条路径称为Merkle 证明。

例如，假设您要验证文件“cat.jpg”是否正确。您只需要下载其哈希值HA 0a6df4 、其同级的哈希值HB (ea12e7) 、其父级同级的哈希值H CD (b582ae)以及 Merkle 根H ABCD (7bd24f) 。

然后，您可以通过组合HA和HB来计算H AB并通过组合 H AB 和 H CD 来计算H ABCD 。如果 H ABCD 与 Merkle 根匹配，则可以确定“ cat.jpg ”是正确的。

您可以使用相同的类比，通过验证 Merkle 根（而不是 cat.jpg 或 dogs.txt）来验证块中存在的交易是否受到调节。这将是叶节点上的一堆事务。

请注意：在上面的示例中，我已将哈希值截断为 6 个字符，以使图表看起来更清晰。

如果我只有三个叶节点怎么办？我将如何创建默克尔树？

这种情况可以通过复制一个节点来快速解决，从而使节点总数达到四个。

例如，假设您有交易。 TA 、 TB和TC 。您可以计算它们的哈希值。 HA 、 HB和HC 。然后你可以复制 HC 得到 H C' 。之后;您可以配对并组合哈希值以获得H AB 、 H CC'和H ABCC' 。 Merkle 根是H ABCC' 。

总而言之，默克尔树有利于区块链和其他分布式系统，在这些系统中，许多计算机必须共享和验证大量数据。通过使用 Merkle 树，它们可以节省带宽、存储和计算时间。

下面是一个快速的 Java 示例，展示了如何创建自己的 Merkle 树：

 import java.nio.charset.StandardCharsets; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; class MerkleTree{ static class Node { String content; public Node(String content) { this.content = content; } public String getHash() throws NoSuchAlgorithmException { MessageDigest md = MessageDigest.getInstance("SHA-256"); byte[] hash = md.digest(content.getBytes(StandardCharsets.UTF_8)); StringBuilder buffer = new StringBuilder(); for (byte b : hash) { buffer.append(String.format("%02x", b)); } return buffer.toString(); } } public static void main(String[] args) throws NoSuchAlgorithmException{ Node cat = new Node("I am a cat, this is a cat file called cat.jpg"); Node dog = new Node("I am a dog, this is a dog file called dog.txt"); // we have two leaf nodes, in order to create a merkle root, // we simple need to get their individual hashes // and then combine those hashes and hash them again String HA = cat.getHash(); String HB = dog.getHash(); Node merkleRoot = new Node(HA + HB); String HAB = merkleRoot.getHash(); System.out.println("Merkle Root: " + merkleRoot.getHash()); // let's say we altered the cat file cat = new Node("I am a cat, this is a cat file called dog.jpg"); // notice we have changed the cat.jpg to dog.jpg String HA_MODIFIED = cat.getHash(); Node modifiedMerkleRoot = new Node(HA_MODIFIED + HB); String HAB_MODIFIED = modifiedMerkleRoot.getHash(); System.out.println("Merkle Root: " + HAB_MODIFIED); } }

输出：

 Merkle Root: d1da3503d679f032134b4330768d31e67813fcfe2824fceed93f8185a405bdf9 Merkle Root: 1a898c7fee0e46647e55d5f9874f090e5ed76726acf39308527a0bba22a34b3e

我感谢您花时间阅读我的文章。请在Hackernoon上关注我来支持我，这样每当我发布文章时您都会收到通知。

多谢。

深入了解有关去中心化系统、技术和人工智能趋势的富有洞察力的文章： https://www.0xkishan.com 。请访问以表示您的支持。

也发布在这里。