比特币探究之MerkleTree

在比特币区块里，所有交易都按照Merkle Tree的格式组织起来，再跟区块头里的hashMerkleTreeRoot对应起来，就可以保证本区块交易信息的不可篡改。关于Merkle Tree的解释和具体算法，可以参见Merkle Tree学习这篇文章，讲得很好，这里不重复了，仅贴张图示意一下：

MerkleTree结构图
比特币源码当中，关于Merkle Tree的实现，是在src/consensus/merkle.cpp里。Merkle树的建立，是通过IncrementExtraNonce函数（在miner.cpp）被调用：

pblock->hashMerkleRoot = BlockMerkleRoot(*pblock);

下面是BlockMerkleRoot的实现：

//mutated用于报告是否有重复交易，其默认值是nullptr
uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
{
    std::vector<uint256> leaves;
    leaves.resize(block.vtx.size());
    //用交易哈希值去填充叶子
    for (size_t s = 0; s < block.vtx.size(); s++) {
        leaves[s] = block.vtx[s]->GetHash();
    }
    return ComputeMerkleRoot(std::move(leaves), mutated);
}

ComputeMerkleRoot用于计算树根的哈希：

uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
    bool mutation = false;
    //从叶子向根逐层循环计算
    while (hashes.size() > 1) {
        if (mutated) {
            for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
                //发现相邻的重复交易
                if (hashes[pos] == hashes[pos + 1]) mutation = true;
            }
        }
        //叶子总数是单数，就把最后一个哈希复制一次
        if (hashes.size() & 1) {
            hashes.push_back(hashes.back());
        }
        //每算完一层，节点数减一半
        SHA256D64(hashes[0].begin(), hashes[0].begin(), hashes.size() / 2);
        hashes.resize(hashes.size() / 2);
    }
    if (mutated) *mutated = mutation;
    if (hashes.size() == 0) return uint256();
    //返回最终的根节点
    return hashes[0];
}

这里的SHA256D64函数定义在sha256.cpp里：

void SHA256D64(unsigned char* out, const unsigned char* in, size_t blocks)
{
    //... 去除了部分无用代码
    while (blocks) {
        TransformD64(out, in);
        out += 32;
        in += 64;
        --blocks;
    }
}

对照上面的调用，可以看到out和in指向同一块地址，这个实际上不影响，TransformD64函数是在全部读取完毕，完成加密计算之后再写入的。这个加密算法的源码很长，网上标准教程也多，这里就不贴了。

---

欢迎转载，请注明出处。