研发人员一定要心中有“树”

• 2019 年 12 月 31 日
• 筆記

【这是一猿小讲的第 79 篇原创分享】

作为高鸡攻城狮一定要心中有树，因为这个的确能提升底层认知。

希望每人都能够做到心中有树，面对面试高频问题，方能有的放矢。

01. 区块链中的树

体会一下：区块链上交易的篡改，会给区块带来什么影响？

如图是区块链中的一个区块，里面存放了一批已经完成的交易信息，为了方便处理，区块的交易信息组织成 Merkle 树的形式，区块的块头存储了前一区块的哈希值。

假设叶子节点上的交易 3 发生篡改，那么交易 3 对应的哈希值就会变动，变动就会逐级向上传递，直到相应的父节点，最终导致区块的的根哈希发生变化，进而会导致整个区块的哈希发生变化。

一句话：交易的篡改，导致整个区块的哈希变化。

由于交易 3 的篡改，导致交易 3 对应的整个区块的哈希发生变动，进而会引起下一个区块上记录的上一个区块的哈希就对不上了，那么是不是要考虑篡改后面的区块呀？但是区块后面的后面的区块也要篡改，子子孙孙无穷匮也。

一句话：交易的篡改，牵一发要动全身，需要篡改整个链条才可以生效，难度可想而知（区块链不可篡改的特性）。

感受一下：如何验证区块上的交易是否存在？

假如需要验证区块上是否真实存在交易 3，该怎么去验证？其实我们只需要“哈希 2”和“哈希 01”就可以证明啦，验证步骤如下。

Step 1：获取交易 3 的哈希值，哈希 3 = Hash(交易 3)； Step 2：通过哈希 2 和哈希 3，得到父节点的哈希值：哈希 23 = Hash(哈希 2 + 哈希 3)； Step 3：通过哈希 01 和哈希 23 的哈希值，得到根节点的哈希值：Root = Hash(哈希 01 + 哈希 23)； Step 4：将上一步得到的根哈希值 Root 与区块头中默克尔根哈希值对比，如果相同，则证明该区块中存在交易 3，否则说明不存在。

一句话：通过引入默克尔树，比特币采用少量计算及比较，就可以完成交易的验证。

思考一下：如何回收磁盘空间？

随着时间的推移，链越来越长，区块链的数据也逐日增长，数据量级越来越大，对存储肯定要求也越来越高。其实一旦最新交易已经被足够多的区块覆盖，这之前的支付交易就可以被丢弃，以便节省磁盘空间。

如上图所示，交易被哈希进默克尔树，只有根节点被纳入到区块的哈希值。那么老的区块可通过剪除树枝的方式被压缩，树枝内部的哈希不需要被保存，进而可以节省磁盘空间而又不破坏区块的哈希值（堪称设计完美）。

其实比特币的以上种种设计，背后都离不开默克尔树，那默克尔树到底是什么呢？

02. 掌握默克尔树

学习任何一门技术，都不要忘记谷哥和度娘，在谷歌输入“Merkle Tree”搜之，映入眼帘的就是维基百科的解释。

哈希树（hash tree；Merkle tree），在密码学及计算机科学中是一种树形数据结构，每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签 。哈希树能够高效、安全地验证大型数据结构的内容，是哈希链的推广形式。 哈希树的概念由瑞夫·墨克于 1979 年申请专利，故亦称墨克树（Merkle tree）。

通过搜索我们明白两点。

1. 原来 Merkle Tree 也叫做 Hash Tree（哈希树），因为 Merkle Tree 每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签 ，所以又叫做哈希树； 2. Merkle Tree 在维基百科被翻译为墨克树，而在中本聪的论文中又被翻译成了默克尔树。其实到这一步，名字叫什么已经无所啦。

通过这个图我们明白两点。

1. 哈希树的顶部为顶部哈希（top hash），亦称根哈希（root hash）或主哈希（master hash）； 2. Hash 0-0 和 Hash 0-1 分别是数据块 L1 和 L2 的哈希值，Hash 0 是将 Hash 0-0 和 Hash 0-1 连接后所取得的哈希值。

主要应用场景。

1. Merkle 树典型的应用场景是点对点网络下载。 先从朋友或者网站分享等方式获取可信的 Merkle 树的顶部哈希；拿到顶部哈希后，就可以通过 P2P 网络中的非受信来源下载整棵 Merkle 树；下载得到 Merkle 树后，就可以根据可信的顶部哈希对其进行校验，验证数据是否完整、是否遭受破坏； 2. Merkle 树可以被用来快速比较大量的数据，因为当两个 Merkle 树根相同时，则意味着所代表的数据必然相同； 3. 开篇中谈到的区块链场景。

03. 闲言碎语

默克尔树就分享到这儿，希望大家对默克尔树有个初步认识吧。

文中图片，大都来自于比特币的创始人中本聪的论文，中本聪的论文建议有时间读一读，毕竟是颠覆之作。

区块链 2.0 的代表技术以太坊 Ethereum（不是比特币的一个克隆，而是完完全全独立的一种设计和实现）建议有时间也了解了解。

比特币：https://github.com/bitcoin 中本聪论文： https://bitcoin.org/files/bitcoin-paper/bitcoin_zh_cn.pdf 以太坊：https://github.com/ethereum 以太坊白皮书： https://github.com/ethereum/wiki/wiki/White-Paper

今天的分享原计划是从 Java 源码用到的树–> MySQL 底层用到的树 –> 区块链中的树，这样一条线来分享我心中的树，但是年底啦，总结、规划等事情太多了，时间不够用啊，希望后面陆陆续续给大家补上