Merkle Tree是区块链技术领域最普遍应用的数据结构之一。这是因为Merkle Tree数据结构可以带来两大好处：
1）对数量与尺寸可变的交易列表进行有规律的哈希压缩得到固定长度的根哈希值并存入区块头部，使得区块头部可被独立传输、处理；
2）仅仅提供少量数据，Merkle Tree及其变种Sparse Merkle Tree即可用于证明某一笔交易是否存于某一区块中。
这两点特性为SPV轻量客户端、Plasma、BTC-Relay等技术方案提供了最基本的支撑。因为在这些方案设计中，智能合约程序和轻量客户端无法实现独立的、完整的全节点功能，必须依赖于用户或外部系统提供的证明数据，才能正确执行判断逻辑。
图1， 来自《Plasma Cash: Towards more efficient Plasma constructions》
Merkle Tree以二叉树的形式组织交易及哈希值，如图1所示，最底层的交易是倒挂树结构的叶子节点，最顶层是根哈希值，中间层的节点属于过度哈希值。树的层级数与交易数量呈Log2(N)的对数关系。比如有1024笔交易，则有10个中间过度层级。
以BTC-Relay为例，这是一种非常典型的链中链设计方案。可以将部署在以太坊平台上的BTC-Relay合约看成是一个特殊的BTC客户端，由于Ethereum系统的封闭性，这个客户端显然无法主动接收到BTC网络中产生的区块广播，只能依靠多个Relayer向合约输入BTC区块头部数据，以被动接收的方式维护简化后的BTC账本数据，形成一个位于Ethereum系统中的Bitcoin系统（BlockChain in BlockChain，链中链）。因为Ethereum系统上的存储是昂贵的，所以合约内部只包含尺寸很小的区块头部数据，而不包含大容量的具体交易数据，
如图1左侧所示，若Alice需证明自己的一笔交易A属于某一区块，那么只需给出TxA、TxA位于区块中的序号、H(B)、H( H(C) + H(D) )这4个数据即可证明这笔交易是真实存在于该区块中的。因为利用这些数据作为参数，程序可自动计算出H(A)、H( H(A) + H(B) )，并验证H( H( H(A) + H(B) ) + H( H(C) + H(D) ) )是否匹配该区块头中包含的根哈希值。
Sparse Merkle Tree（简记为SMT）是普通Merkle Tree的一个变种。SMT是针对不可置换通证Non Fungible Token（简记为NFT）的交易而设计的。由于每一枚NFT都是不可切分的、不可置换的，只能做完整转移。因此一个系统中若设计拥有总量为M个NFT，则可以按照1～M的顺序进行排列，形成SMT的1～M叶子节点槽位。若在某一区块中不包含编号为K的NFT交易，则用空数据填入SMT对应的K叶子节点槽位。如图1右侧所示，证明编号为C的NFT没有出现在某一区块中，则只需给出空数据、空数据的序号、H(D)、H( H(A) + H(空) )即可，这就证明了「该交易不存在于该区块」。因为从逻辑上看，「不存在」是「存在」的一种特殊形式，「不存在」可以被认为是「存在空」，所以证明了「空」存在于C槽位，也就证明了与C相关的交易是不存在的。
网友评论