区块链与你“最熟悉的陌生人”

“简化版”的区块链

从许多角度看，Git 都像简化版的区块链。

Git 的开发始于 2005年。彼时，Linux 内核开发团队正被之前使用的专有代码管理系统 BitKeeper 所困扰，Linus Torvalds 希望获得一种体验近似BitKeeper 的分布式系统，遍寻不得，便选择了自行开发。

Git 项目开发效率惊人——Linus 4 月 3 日开工，6 日向社区宣布，7 日实现 self-hosting，18 日第一批分枝合并，29 日就能以每秒 6.7 次的速度向 Linux 内核代码树打补丁。6 月，在 Git 的控制下，便发布了 2.6.12 版内核。

如果用三句话阐述Git的运行原理，那就是：

生成修改过的文件生成当前目录 tree 文件，关联当前状态文件生成commit文件，关联到当前目录tree文件，并记下父 commit

其使用方式可简单描述为：本地提交，累积几次后 push 到 remote。本次提交会关联上一次提交，跟区块链是不是类似？版本控制最重要的是可追溯，如果某次错误提交，还可以回退到历史版本——可追溯也是区块链的重要特性。

区块链是分布式的，Git 天然就是分布式，不过 Git 依赖文件系统。以 GitHub 上的操作为例，代码或者文档一旦提交，操作将无法撤销。如果程序员clone repo，只要不删除，将永久存储在自身电脑，除非文件系统崩溃；如果某程序员 fork 该 repo，只要账户不被删除，这个 repo 将永久保留在账户之下。

另外，某个repo fork、clone次数越多，被摧毁的概率也就越低；再者，某个repo即使最近一次操作清空了所有代码，还可以通过git log恢复。

区块链的另一个特性是不可篡改，也就是只能 Insert。Git 呢？GitHub 托管的 repo 里的内容本身是可以修改的，然而这个 commit 历史却是无法修改的。每一次 commit 都有唯一标志，本次 commit 会有 parent commit 的信息。Git 产生的 log 也可以通区块链数据库类比。

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

如果将视角转向底层，我们能发现两者更多相似。

共同的底层数据结构——默克尔树

区块链与 Git 内部数据结构都以树形数据对象表示——即以默克尔树（Merkle Tree）作为底层数据结构。

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

这种数据结构的特点是：

大多数为二叉树，也可以多叉树，无论是几叉树，它都具有树结构的所有特点叶子节点value是数据集合的单元数据或者单元数据Hash非叶子节点的value是根据它下面所有的叶子节点值，然后按照Hash算法计算而得出 近年来，除了 Bitcoin、Ethereum、IPFS，一大批计算机工程突破，都得益于这种数据结构进行完整性校验，例如文件系统 ZFS、Btrfs，另一种分布式版本控制系统 Mercurial，NoSQL 数据库 Apache Cassandra、Riak、Dynamo 等。BT 下载，也是通过默克尔树进行完整性校验。

要实现完整性校验，最简单的方法是对整个数据文件做 Hash 运算，把得到的 Hash 值公布在网上，下载数据后，再次运算 Hash 值，如果运算结果相等，就表示没有任何的损坏。

假如从稳定的服务器上下载，那么采用单个 Hash 来进行校验的形式是可以接受的。但在点对点网络中作数据传输时，会从同时从多个机器上下载，且线路充斥着不稳定，这时需要有更加巧妙的做法。

实际中，都是把比较大的一个文件，切成小块。如果有一个小块数据在传输过程中损坏，只要重新下载这一个数据块就行。当然这就要求每个数据块都拥有自己的 Hash 值。

以我们熟悉的 BT 下载为例，下载真正的数据之前，会先下载一个 Hash 列表的。这时有一个问题出现——那么多的 Hash，怎么保证它们本身都是正确地呢？

答案是需要一个 “根 Hash”。把每个小块的 Hash 值拼到一起，然后对整个这个长长的字符串再做一次 Hash 运算，最终的结果就是 Hash 列表的根 Hash。于是，如果我们能够保证从一个绝对可信的网站，或者从我们的朋友手里拿到一个正确的根 Hash，就可以用它来校验 Hash 列表中的每一个 Hash 都是正确的，进而可以保证下载的每一个数据块的正确性了。

这种设想挺好，但实际应用中，还有不足，这就是为什么要发默克尔树。

在最底层，与 Hash 列表一样，数据被分成小块，有相应的 Hash 和其对应。但是往上走，并不是直接去运算根 Hash，而是把相邻的两个 Hash 合并成一个字符串，然后运算这个字符串的 Hash，这样每两个 Hash 就结婚生子，得到了一个 “子 Hash”。

如果最底层的 Hash 总数是单数，那到最后必然出现一个单身 Hash，这种情况就直接对它进行 Hash 运算，所以也能得到它的子 Hash。于是往上推，依然是一样的方式，可以得到数目更少的新一级 Hash，最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根 Hash 了，称为默克尔根。

相对于 Hash List，Merkle Tree 的明显的一个好处是可以单独拿出一个分支来（作为一个小树）对部分数据进行校验，这个很多使用场合就带来了 Hash 列表所不能比拟的方便和高效。