[科普中国]-梅克尔树

梅克尔树（Merkle trees）是区块链的基本组成部分。虽说从理论上来讲，没有梅克尔树的区块链当然也是可能的，只需创建直接包含每一笔交易的巨大区块头（block header）就可以实现，但这样做无疑会带来可扩展性方面的挑战，从长远发展来看，可能最后将只有那些最强大的计算机，才可以运行这些无需受信的区块链。 正是因为有了梅克尔树，以太坊节点才可以建立运行在所有的计算机、笔记本、智能手机，甚至是那些由Slock.it生产的物联网设备之上。1

相关概念区块链区块链是随着比特币等数字加密货币的日益普及而逐渐兴起的一种全新的去中心化基础架构与分布式计算范式， 目前已经引起政府部门、金融机构、科技企业和资本市场的高度重视与广泛关注。 区块链技术具有去中心化、时序数据、集体维护、可编程和安全可信等特点, 特别适合构建可编程的货币系统、金融系统乃至宏观社会系统.。2

哈希（散列）哈希（hash），一般翻译做“散列”，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

梅克尔树梅克尔树是区块链的重要数据结构， 其作用是快速归纳和校验区块数据的存在性和完整性。一般意义上来讲，它是哈希大量聚集数据“块”的一种方式，它依赖于将这些数据“块”分裂成较小单位的数据块，每一个bucket块仅包含几个数据“块”，然后取每个bucket单位数据块再次进行哈希，重复同样的过程，直至剩余的哈希总数仅变为1。

构成原理梅森树通常包含区块体的底层 (交易) 数据库， 区块头的根哈希值 (即Merkle根) 以及所有沿底层区块数据到根哈希的分支。梅森树运算过程一般是将区块体的数据进行分组哈希， 并将生成的新哈希值插入到梅森树中，如此递归直到只剩最后一个根哈希值并记为区块头的 Merkle根。 最常见的梅森树是比特币采用的二叉梅森树,，其每个哈希节点总是包含两个相邻的数据块或其哈希值3。其特点如下：

梅克尔树是一种树，大多数是二叉树，也可以多叉树，无论是几叉树，它都具有树结构的所有特点；

Merkle Tree的叶子节点的value是数据集合的单元数据或者单元数据HASH。

非叶子节点的value是根据它下面所有的叶子节点值，然后按照Hash算法计算而得出的。

优点梅克尔树有诸多优点，首先是极大地提高了区块链的运行效率和可扩展性，使得区块头只需包含根哈希值而不必封装所有底层数据,，这使得哈希运算可以高效地运行在智能手机甚至物联网设备上；其次是梅克尔树可支持 “简化支付验证” 协议, 即在不运行完整区块链网络节点的情况下，也能够对（交易）数据进行检验。4

种类即根哈希（root hash）梅克尔树最为常见和最简单的形式，是二进制梅克尔树（ binary Mekle tree），其中一bucket单位的数据块总是包含了两个相邻的块或哈希。哈希算法允许了一个整齐的机制，我们称之为梅克尔证明（Merkle proofs）。一个梅克尔证明包含了一个数据块，这颗梅克尔树的根哈希，以及包含了所有沿数据块到根路径哈希的“分支”。

帕特里夏树（Patricia Trees）以太坊所使用的梅克尔树，我们称之为“梅克尔.帕特里夏树”（Merkle Patricia tree）。其工作原理，最为简单的解释是，一个以编码形式存储到记录树的“路径”的值。每个节点会有16个子（children），所以路径是由十六进制编码来确定的：例如，狗（dog）的键的编码为6 4 6 15 6 7，所以你会从这个根开始，下降到第六个子，然后到第四个，并依次类推，直到你达到终点。

应用数字签名最初Merkle Tree目的是高效的处理Lamport one-time signatures。 每一个Lamport key只能被用来签名一个消息，但是与Merkle tree结合可以来签名多条Merkle。这种方法成为了一种高效的数字签名框架，即Merkle Signature Scheme。

P2P网络在P2P网络中，Merkle Tree用来确保从其他节点接受的数据块没有损坏且没有被替换，甚至检查其他节点不会欺骗或者发布虚假的块。5

Trusted Computing可信计算是可信计算组为分布式计算环境中参与节点的计算平台提供端点可信性而提出的。可信计算技术在计算平台的硬件层引入可信平台模块(Trusted Platform，TPM)，实际上为计算平台提供了基于硬件的可信根(Root of trust，RoT)。从可信根出发，使用信任链传递机制，可信计算技术可对本地平台的硬件及软件实施逐层的完整性度量，并将度量结果可靠地保存再TPM的平台配置寄存器(Platform configuration register，PCR)中，此后远程计算平台可通过远程验证机制(Remote Attestation)比对本地PCR中度量结果，从而验证本地计算平台的可信性。可信计算技术让分布式应用的参与节点摆脱了对中心服务器的依赖，而直接通过用户机器上的TPM芯片来建立信任，使得创建扩展性更好、可靠性更高、可用性更强的安全分布式应用成为可能。可信计算技术的核心机制是远程验证(remote attestation),分布式应用的参与结点正是通过远程验证机制来建立互信,从而保障应用的安全。6

IPFSIPFS(InterPlanetary File System)是很多NB的互联网技术的综合体，如DHT( Distributed HashTable，分布式哈希表)，Git版本控制系统，Bittorrent等。它创建了一个P2P的集群，这个集群允许IPFS对象的交换。全部的IPFS对象形成了一个被称作Merkle DAG的加密认证数据结构。

比特币梅克尔树最早的应用是比特币，它是由中本聪在2009年描述并创建的。Bitcoin的Blockchain利用Merkle proofs来存储每个区块的交易。

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学