转自：丛末?AI科技评论?
孙启超：法国蒙彼利埃大学 MBA 在读，CSDN 百万博客专家，2015 年之前参与 360 技术团队的研究工作。目前负责公司公链项目的架构。
分享主题：支撑区块链中的底层查询系统
分享提纲：
1. 介绍哈希算法的特点
2. 什么是默克尔树
3. 默克尔书的特点
4. 区块链的查询系统原理
雷锋网 AI 研习社将其分享内容整理如下：
我们本次分享的主题是：支撑区块链中的底层查询系统。
首先讲一下基础知识。实际上，目前互联网传输，包括区块链的数据传输，底层都依赖于密码学的发展，哈希（Hash）算法则是现在最重要的密码学之一。它的主要作用是将任意长度的二进制明文映射为较短的、长度固定的二进制串的算法。比如不管传过来是多长的二进制明文，经过 MD5 运算后都会变成 64 位的二进制编码。比如「维多利亚的秘密」、「程序员的秘密」等明文，经过 MD5 后，都得到 64 位的十六进制的编码，但通过二者的对比可以看到，虽然二者明文中「的密码」有一定相似性，但是 MD5 后，二者的编码完全没有一点相似性。
如果从空间上分析，哈希算法就是从一个非常大的取值空间映射到一个非常小的取值空间。我们再看前面这句明文经 MD5 运算后得到的一长串编码，我们几乎推不出来「维多利亚的秘密」，这说明了哈希函数转换后不可逆，意思是不可能通过逆操作以及哈希值还原出原始的值。
下面看哈希算法的几个特点：
第一，正向快速。给定明文和哈希算法，在有限时间和有限资源内能快速计算得到哈希值。
第二，逆向困难。给定哈希值，在有限时间内很难逆推出明文，只能将所有可能性进行穷举，而并不能破解算法。
第三，输入敏感。原始输入信息发生任何变化，新的 Hash 值都会出现天翻地覆的变化。就比如刚刚提到的「维多利亚的秘密」、「程序员的秘密」，明文有些相似性，但是 MD5 后的编码没有任何相似的地方。
第四，冲突避免。比如说 666 和 667 经过 MD5 后的值就一定不一样，即不存在明文不一样而哈希值一样的情况。这个特点也是唯一性，后面的查找也要用到这个特点，因为只有哈希值是唯一的，我们才能用它去定位，否则就没有意义。
常见的哈希算法包括 MD5 和 SHA 系列，目前 MD5 和 SHA1 已经被破解，在比特币中，如果使用 MD5 去生成数学难题，几乎就没有什么难度了——一般推荐至少使用 SHA2-256 算法，该算法要比 MD5 高很多个数量级别。
接下来我们讲它区块链中的运用，首先讲一下区块链的概念，因为我们主要讲底层技术。区块链可以简单理解成数据的存储空间，一个区块就是一个存储空间，可以存图片、文字、视频等。而多个存储空间连在一起，就是一个区块链。如果是公链，则只有一条链。
链通过我们刚刚讲到的哈希值来连接。一个区块链有两个哈希值，一个是本身存储的数据转换成的二进制编码，用这些编码进行哈希运算，得到一个哈希值；另一个代表上一个区块的哈希值，上一个区块链自身也有一个哈希值，会传到该区块中。而该区块的哈希值也会传达到它的下一个区块中——大家可以将这个过程想象成一个铁环再套下一个铁环。不过，该区块的一个铁环是由上一个区块牵引着的，而它本身的另一个铁环则牵引着下一个区块的铁环。
对数据结构的理解有一个链表，其实跟区块链很相似。假如有一个区块的哈希值在所有区块中都找不到，就说明这个区块链是假的，或者说不被大家所认可。因此在区块链中，首先要去查区块链交易的内容，比如说记账，存一个图片进去，那这个图片是否被认可呢？——如果哈希值在公链上找不到的话，就是不被认可的区块链。
介绍一下默克尔树这个概念。区块链的很多名词其实都翻译得非常好，基本上通过名词就能知道要表达什么意思。这里的「树」由一个根节点，一组中间节点和一组叶子节点组成。根节点表示是最终的那个节点，且只有一个。叶子节点可以有很多，但是不能再扩散也就是没有子节点了。如图：
它的运转过程是：
第一步把最底层的 Data0...Data3 这四条数据，每一条都单独进行哈希值，得出 4 个 64 位的哈希值作为叶子节点。
第二步把相邻的两个叶子节点的哈希值拿出来两两结合，再进行哈希，如 B0+B1 两个 64 位的值，哈希后得出一个 64 位的 B4。
第三步递归执行这样的哈希操作，直到最终 Hash 出一个根节点，就结束了。
这就是默克尔树的运行原理，在图中展现是：B0+B1 哈希得出 B4，B2+B3 哈希得出 B5，B4+B5 哈希得出 Root 根节点。如果节点为奇数也没关系，只要在后面再加一条链，能通过默克尔路径出来就可以了。比如说这里得到 B4+B5 的哈希值，再与该哈希值合并就可以的，最后递归出来的只有一个。
由于每个节点上的内容都是哈希值，默克尔树所以也叫「哈希树」。
我们接下来看一下它的特性（跟哈希算法的特性有很大关系，因为默克尔树基于哈希算法）：
第一特性：任意一个叶子节点的细微变动，都会导致 Root 节点发生翻天覆地的变化。我们回去看上图，假如 B1 了，那 B4 就一定会变，自然而然地，最后的 Root 节点也会变。这一特性可以用来判断两个加密后的数据是否完全一样。
第二特性：快速定位修改，如果 Data1 中数据被修改，会影响到 B1，B4 和 Root，当发现根节点 Root 的哈希值发生变化，可以沿着 Root - > B4 - > B1 最多通过 O(logn) 时间即可快速定位到实际发生改变的数据块 Data1，而不需要比对 B5 那边的哈希值。
第三特性：零知识证明，它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。有的公司就专门利用了这一个特性做了一个叫做数字认证的项目，它是指在不向任何人提供信息的情况下，我们就能证明拥有这项权利。当我们只愿意给出 Data0...Data3 这四条数据中的 Data0 时，怎么证明我们拥有 Data0...Data3 这些数据呢？步骤如下：
第一，创建一棵如图所示的默克尔树，然后对外公布 B1，B5，Root；
第二，这时 Data0 的拥有者通过哈希生成 B0，然后根据公布的 B1 生成 B4，再根据公布的 B5 生成 Root，如果最后生成的 Root 哈希值能和公布的 Root 一样，则可以证明拥有这些数据，而且不需要公布 Data1，Data2，Data3 这些真实数据。
今天的重点就是讲区域链的查询系统。首先介绍「默克尔路径」这个概念，上图中 Root - > B4 - > B1 就是一条路径，表示从根节点到叶子节点所经过的节点组成的路径。
在比特币中，默克尔树被用作归纳一个区块中的所有交易，同时生成整个交易集合的数字签名，且提供了一种校验区块是否存在某交易的高效途径，就是默克尔路径。一条条路径就相当于一笔笔交易。之前我们所说的交易慢，实际上是因为出区块的时间慢，1MB 存不了多少数据，随着人数越来越多，排队就要很长时间了。
而生成默克尔树，需要递归地对各个子节点进行哈希运算，将新生成的哈希节点插入到默克尔树中，直到只剩一个哈希节点，该节点就是默克尔树的根节点。
这就是整个查询的原理，时间复杂度为 logN，依据的是默克尔路径。我们可以通过下图直观地看到怎样高效地查找交易：
?
路径其实也是一个大小，路径数代表哈希值的数量，路径数是 4 表示这条路径存了 4 个哈希值，每个哈希值是 32 Byte。而区块大小=交易数 * 250 Byte；路径大小=路径数 * 32 Byte。因此，好的算法对高效查找交易非常重要。
最后讲一下区块链中最简单的确认支付的形式——简单支付验证（SPV）。
比特币和以太坊都通过默克尔树来进行查询、确认。有了默克尔树，一个节点能够仅下载区块头 80 字节，包含上一区块头的哈希值、时间戳、挖矿难度值、工作量证明随机数以及该区块交易的默克尔树的根哈希值。
从 2008 年诞生起，区块链交易加起来有 160 多个 G 的内存。使用简单支付验证（SPV），我们只需要通过从一个满节点回溯一条小的默克尔路径就能认证一笔交易的存在，而不需要下载整个区块、存储上百 G 的内容。
注册有任何问题请添加 微信：MVIP619 拉你进入群
打开微信扫一扫
添加客服
进入交流群
发表评论