比特币探究之MerkleTree
2018-07-22 本文已影响36人
魏兆华
在比特币区块里,所有交易都按照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函数是在全部读取完毕,完成加密计算之后再写入的。这个加密算法的源码很长,网上标准教程也多,这里就不贴了。
欢迎转载,请注明出处。