paint-brush
默克尔树简介:它是什么以及它如何运作?经过@0xkishan
1,064 讀數
1,064 讀數

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

经过 Kishan Kumar5m2023/07/03
Read on Terminal Reader

太長; 讀書

Merkle Tree 是哈希值的二叉树,其中每个叶节点代表一条数据。它用于有效地验证大量数据的完整性。哈希函数就像指纹机。它接受任何输入并产生一个独特的输出,称为哈希,它比输入短得多。
featured image - 默克尔树简介:它是什么以及它如何运作?
Kishan Kumar HackerNoon profile picture
0-item
1-item
2-item

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


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


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


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


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


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


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


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


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

默克尔树插图,作者:Kishan Kumar

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


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


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


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

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

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


例如,假设您有交易。 TATBTC 。您可以计算它们的哈希值。 HAHBHC然后你可以复制 HC 得到 H C' 。之后;您可以配对并组合哈希值以获得H ABH 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 。请访问以表示您的支持。


也发布在这里。