技术派：区块链和你“最熟悉的陌生人”——Git

提到“以Merkle树为底层数据结构的分布式系统”，你会想到谁？ 除了区块链，其实还有一个你最熟悉的陌生人——Git。

区块链的“简化”版本

在许多方面，Git 就像一个简化的区块链。

Git 的开发始于 2005 年，当时 Linux 内核开发团队正为之前使用的专有代码管理系统 BitKeeper 而苦恼。 Linus Torvalds 希望能得到一个分布式系统，有类似 BitKeeper 的体验，但是到处找不到，所以他选择了自己开发。

Git项目开发效率惊人——Linus 4月3日开工，4月6日向社区发布，7日实现自托管，18日合并第一批分支，并能够上传Linux内核代码在 29 日以每秒 6.7 次的速度运行。 树被修补了。 6月，在Git的控制下，发布了2.6.12内核。

如果用三句话来解释Git的运行原理，那就是：

生成修改后的文件

生成当前目录树文件​​并关联当前状态文件

生成commit文件，关联当前目录树文件​​，记下父commit

它的用法可以简单描述为：本地提交，多次积累后推送到远程。 这次提交会和之前的提交关联起来，是不是类似于区块链？ 版本控制最重要的是可追溯性。 如果提交错误，可以回滚到历史版本——可追溯性也是区块链的一个重要特性。

区块链是分布式的，Git自然也是分布式的，只是Git依赖文件系统。 以GitHub上的操作为例，代码或文档一旦提交，操作将无法撤销。 如果程序员克隆repo，只要不删除，就会永久保存在自己的电脑上，除非文件系统崩溃； 如果程序员fork repo区块链是比特币最底层的技术吗，只要账号不被删除，repo会永久保存在账号下。

此外，repo 被 fork 和 clone 的次数越多，被销毁的概率就越低； 而且，即使repo在最近一次操作中清除了所有代码，仍然可以通过git log恢复。

区块链的另一个特点是不可篡改，即只能插入。 吉特呢？ 可以修改 GitHub 托管的 repo 中的内容，但不能修改提交历史。 每个提交都有一个唯一的标志，这个提交将有父提交信息。 Git 生成的日志也可以与区块链数据库进行对比。

而且，谁又能说“不可修改”或者有共识算法就是区块链的充分条件呢？

如果我们将视角转向底层，我们可以发现两者更多的相似之处。

通用底层数据结构——默克尔树

区块链和Git内部的数据结构都是用树型数据对象来表示——即默克尔树（Merkle Tree）作为底层数据结构。

Merkle树的现代数据结构是由计算机科学家Ralph Merkle（他也是公钥加密算法的共同设计者）在1979年提出的（作为对比，Knuth的TAOCP三卷本第一版写于1973年），并以他的名字命名。

这种数据结构的特点是：

大部分是二叉树，也可以是多叉树。 不管有多少叉树，它们都具有树结构的所有特征。

叶子节点值是数据集的单位数据或单位数据Hash

一个非叶子节点的值是根据它下面的所有叶子节点的值计算出来的，然后根据Hash算法计算出来的

近年来，除了比特币、以太坊、IPFS之外，大量计算机工程的突破都得益于这种用于完整性验证的数据结构，例如文件系统ZFS、Btrfs、另一个分布式版本控制系统Mercurial、NoSQL数据库Apache Cassandra ,Riak,Dynamo等BT下载也是通过Merkle树进行完整性校验。

要实现完整性验证，最简单的方法就是对整个数据文件进行Hash运算，将得到的Hash值发布到网上，下载数据，重新计算Hash值。 如果运算结果相等，则表示没有损坏。

如果是从稳定的服务器下载的，可以使用单个Hash进行验证。 但是，在点对点网络中传输数据时，会同时从多台机器上下载，线路充满了不稳定性。 这时候就需要更巧妙的做法了。

实际上，一个相对较大的文件被切割成小块。 如果在传输过程中有一小块数据损坏，只需重新下载该数据块即可。 当然，这需要每个数据块都有自己的Hash值。

以我们熟悉的BT下载为例，在下载真实数据之前，会先下载一个Hash列表。 这时候，一个问题就出现了——这么多的Hash，如何保证它们都是正确的呢？

答案是需要一个“root Hash”。 把每个小块的Hash值放在一起，然后对整个长串进行Hash运算，最后的结果就是Hash链表的根Hash。 因此，如果我们能够保证从一个绝对可信的网站，或者从我们的朋友那里得到一个正确的根Hash，我们就可以用它来验证Hash列表中的每一个Hash是正确的，那么我们就可以保证每一个数据的正确性块下载。

这种想法很好，但是在实际应用中区块链是比特币最底层的技术吗，还是有不足之处，这也是发行Merkle树的原因。

在底层，和Hash列表一样，将数据分成小块，有对应的Hash及其对应关系。 但是往上走，并不是直接计算根Hash，而是将相邻的两个Hash组合成一个字符串，然后计算这个字符串的Hash，这样每两个Hash结婚生子，就产生​​一个“子Hash” .

如果底层的哈希总数是奇数，那么末尾一定只有一个哈希。 此时直接对其进行哈希运算，因此也可以得到其子哈希。 所以往上推，还是老样子，可以得到更小数的新一层Hash，最终必然形成一棵倒树。 在树根的这个位置，这一代只剩下一个根哈希，称为默克尔根。

与Hash List相比，Merkle Tree的一个明显优势是可以单独取出一个分支（作为一棵小树）来验证部分数据。 这在很多使用场合带来了Hash List无法比拟的方便和高效。 .

- 【结束】 -