第七节 Merkle树
区块链中的每个区块都包含了产生于该区块的所有交易,且以Merkle树表示。
Merkle树是一种哈希二叉树,它是一种用作快速归纳和校验大规模数据完整性的数据结构。这种二叉树包含加密哈希值。术语“树”在计算机学科中常被用来描述一种具有分支的数据结构,但是树常常被倒置显示,“根”在图的上部,同时“叶子”在图的下部,你会在后续内容中看到相应的例子。
在比特币网络中,Merkle树被用来归纳一个区块中的所有交易,同时生成整个交易集合的数字指纹,提供一种校验区块是否存在某交易的高效途径。生成一棵完整的Merkle树需要递归地对哈希节点对进行哈希,并将新生成的哈希节点插入Merkle树中,直到只剩一个哈希节点,该节点就是Merkle树的根。在比特币的Merkle树中两次使用到了SHA256算法,因此其加密哈希算法也被称为double-SHA256。
当n个数据元素经过加密后被插入Merkle树时,你最多计算次就能检查出某任意数据元素是否在该树中,这使得该数据结构非常高效。
Merkle树是自下向上构建的。在图2.4中,我们从A、B、C、D四个构成Merkle树树叶的交易开始。起始时所有的交易都还未存储在Merkle树中,而是先将数据哈希化,然后将哈希值存储至相应的叶子节点。这些叶子节点分别是HA、HB、HC和HD:
H~A~ = SHA256(SHA256(交易A))
通过串联相邻叶子节点的哈希值然后哈希之,这对叶子节点随后被归纳为父节点。例如,为了创建父节点HAB,子节点A和子节点B的两个32字节的哈希值将被串联成64字节的字符串。随后将字符串进行两次哈希来产生父节点的哈希值:
H~AB~=SHA256(SHA256(H~A~ + H~B~))
继续类似的操作直到只剩下顶部的一个节点,即Merkle根。产生的32字节哈希值存储在区块头,同时归纳了四个交易的所有数据。如图2.4所示。
图2.4
因为Merkle树是二叉树,所以它需要偶数个叶子节点。如果仅有奇数个交易需要归纳,那最后的交易就会被复制一份以构成偶数个叶子节点,这种偶数个叶子节点的树也被称为平衡树。如图2.5所示,C节点被复制了一份。
图2.5
由四个交易构造Merkle树的方法同样适用于从任意交易数量构造Merkle树。在比特币中,在单个区块中有成百上千的交易是非常普遍的,这些交易都会采用同样的方法归纳起来,产生一个仅仅32字节的数据作为Merkle根。在图2.6中,你会看见一个由16个交易形成的树。需要注意的是,尽管图中的根看起来比所有叶子节点都大,但实际上它们的大小都是32字节。无论区块中只有一个交易或者有10万个交易,Merkle根总会把所有交易都归纳为32字节。
图2.6
为了证明区块中存在某个特定的交易,一个节点只需要计算l个32字节的哈希值,形成一条从特定交易到树根的认证路径或者Merkle路径即可。随着交易数量的急剧增加,这样的计算量就显得异常重要,因为相对于交易数量的增长,以基底为2的交易数量的对数的增长会缓慢许多。这使得比特币节点能够高效地产生一条10或者12个哈希值(320~384字节)的路径,来证明在一个巨量字节大小的区块中上千笔交易中的某笔交易的存在。
在图2.7中,一个节点能够通过生成一条仅有4个32字节哈希值长度(总128字节)的Merkle路径,来证明区块中存在一笔交易K。该路径有4个哈希值(在图2.7中由深黑色标注)HL、HIJ、HMNOP和HABCDEFGH。由这4个哈希值产生的认证路径,再通过计算另外4对哈希值HKL、HIJKL、HIJKLMNOP和Merkle树根(在图2.7中由虚线标注),任何节点都能证明HK(在图2.7中由浅黑色标注)包含在Merkle根中。
图2.7
例1中的代码借用libbitcoin库中的一些辅助程序,演示了从叶子节点哈希至根创建整个Merkle树的过程。
例1 构造Merkle树。
#include <bitcoin/bitcoin.hpp> bc::hash_digest create_merkle(bc::hash_digest_list& merkle) { // Stop if hash list is empty. if (merkle.empty()) return bc::null_hash; else if (merkle.size() == 1) return merkle[0]; // While there is more than 1 hash in the list, keep looping… while (merkle.size() > 1) { // If number of hashes is odd, duplicate last hash in the list. if (merkle.size() % 2 ! = 0) merkle.push_back(merkle.back()); // List size is now even. assert(merkle.size() % 2 == 0); // New hash list. bc::hash_digest_list new_merkle; // Loop through hashes 2 at a time. for (auto it = merkle.begin(); it ! = merkle.end(); it += 2) { // Join both current hashes together (concatenate). bc::data_chunk concat_data(bc::hash_size * 2); auto concat = bc::make_serializer(concat_data.begin()); concat.write_hash(*it); concat.write_hash(*(it + 1)); assert(concat.iterator() == concat_data.end());
//Hash both of the hashes. bc::hash_digest new_root=bc::bitcoin_hash(concat_data); //Add this to the new list. new_merkle.push_back(new_root); } //This is the new list. merkle=new_merkle; //DEBUG output------------------------------------- std::cout<<"Current merkle hash list:"<<std::endl; for(const auto&hash: merkle) std::cout<<""<<bc::encode_hex(hash)<<std::endl; std::cout<<std::endl; //-------------------------------------------------- } //Finally we end up with a single item. return merkle[0]; } int main() { //Replace these hashes with ones from a block to reproduce the same merkle root. bc::hash_digest_list tx_hashes{ { bc::decode_hash("00000000000000000000000000000000000000000000000000 00000000000000"), bc::decode_hash("0000000000000000000000000000000000000000000000 000000000000000011"), bc::decode_hash("0000000000000000000000000000000000000000000000 000000000000000022"), }
}; const bc::hash_digest merkle_root = create_merkle(tx_hashes); std::cout << "Result: " << bc::encode_hex(merkle_root) << std::endl; return 0; }
例2展示了编译以及运行上述代码后的结果。
例2 编译以及运行构造Merkle树代码。
$ # Compile the merkle.cpp code $ g++ -o merkle merkle.cpp $(pkg-config --cflags --libs libbitcoin) $ # Run the merkle executable $ ./merkle Current merkle hash list: 32650049a0418e4380db0af81788635d8b65424d397170b8499cdc28c4d27006 30861db96905c8dc8b99398ca1cd5bd5b84ac3264a4e1b3e65afa1bcee7540c4 Current merkle hash list: d47780c084bad3830bcdaf6eace035e4c6cbf646d103795d22104fb105014ba3 Result: d47780c084bad3830bcdaf6eace035e4c6cbf646d103795d22104fb105014ba3
Merkle树的高效率随着交易规模的增加而变得异常明显。表2.3展示了为了证明区块中存在某交易而所需转化为Merkle路径的数据量。
表2.3 Merkle树的效率
依表2.3可得,当区块大小由16笔交易(4KB)急剧增加至65535笔交易(16MB)时,为证明交易存在的Merkle路径长度增长极其缓慢,仅仅从128字节增加到了512字节。有了Merkle树,一个节点能够仅下载区块头(80字节/区块),然后通过从一个满节点回溯一条小的Merkle路径就能认证一笔交易的存在,而不需要存储或者传输大量区块链中大多数内容,这些内容可能有几个GB的大小。这种不需要维护一条完整的区块链的节点,又被称作简单支付验证(SPV)节点,它不需要下载整个区块而是通过Merkle路径去验证交易的存在。