簡(jiǎn)介
Merkle Tree杖玲，通常也被稱作Hash Tree顿仇，顧名思義，就是存儲(chǔ)hash值的一棵樹摆马。Merkle樹的葉子是數(shù)據(jù)塊(例如臼闻，文件或者文件的集合)的hash值。非葉節(jié)點(diǎn)是其對(duì)應(yīng)子節(jié)點(diǎn)串聯(lián)字符串的hash囤采。
默克爾樹
比特幣中對(duì)應(yīng)的默克爾樹
-
比特幣中區(qū)塊的定義結(jié)構(gòu)
CBlock
//
// Nodes collect new transactions into a block, hash them into a hash tree,
// and scan through nonce values to make the block's hash satisfy proof-of-work
// requirements. When they solve the proof-of-work, they broadcast the block
// to everyone and the block is added to the block chain. The first transaction
// in the block is a special one that creates a new coin owned by the creator
// of the block.
//
// Blocks are appended to blk0001.dat files on disk. Their location on disk
// is indexed by CBlockIndex objects in memory.
//
class CBlock
{
public:
// header
int nVersion;
uint256 hashPrevBlock;
uint256 hashMerkleRoot;
unsigned int nTime;
unsigned int nBits; // 記錄本區(qū)塊難度
unsigned int nNonce;
// network and disk
vector<CTransaction> vtx;
// memory only
mutable vector<uint256> vMerkleTree;
// 對(duì)應(yīng)的方法省略述呐，后面用到會(huì)單獨(dú)講解
};
- 構(gòu)建塊中交易對(duì)應(yīng)的默克爾樹
對(duì)應(yīng)的代碼如下：
uint256 CBlock::BuildMerkleTree() const
{
vMerkleTree.clear();
foreach(const CTransaction& tx, vtx)
vMerkleTree.push_back(tx.GetHash());
int j = 0;
for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
{
for (int i = 0; i < nSize; i += 2)
{
int i2 = min(i+1, nSize-1);
vMerkleTree.push_back(Hash(BEGIN(vMerkleTree[j+i]), END(vMerkleTree[j+i]),
BEGIN(vMerkleTree[j+i2]), END(vMerkleTree[j+i2])));
}
j += nSize;
}
return (vMerkleTree.empty() ? 0 : vMerkleTree.back());
}
舉一個(gè)例子，假設(shè)對(duì)應(yīng)的block中有A,B,C,D四個(gè)交易記錄（這些交易記錄保存在block中的vector<CTransaction> vtx）
假設(shè)塊中對(duì)應(yīng)的交易vtx中內(nèi)容有A,B,C,D四個(gè)交易記錄
則使用上述構(gòu)建默克爾樹的方法BuildMerkleTree蕉毯，則使得block中對(duì)應(yīng)的默克爾樹結(jié)構(gòu)體vector<uint256> vMerkleTree如下圖所示：
對(duì)上述交易構(gòu)建的默克爾樹結(jié)果
默克爾樹對(duì)應(yīng)的樹形圖
- 根據(jù)交易在塊中的索引查詢其對(duì)應(yīng)的默克爾樹分支
獲取對(duì)應(yīng)的默克爾樹的分支在CBlock中對(duì)應(yīng)的方法GetMerkleBranch代碼如下：
vector<uint256> CBolck::GetMerkleBranch(int nIndex) const
{
if (vMerkleTree.empty())
BuildMerkleTree();
vector<uint256> vMerkleBranch;
int j = 0;
for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
{
int i = min(nIndex^1, nSize-1);
vMerkleBranch.push_back(vMerkleTree[j+i]);
nIndex >>= 1;
j += nSize;
}
return vMerkleBranch;
}
交易索引0對(duì)應(yīng)的默克爾樹分支
紅色節(jié)點(diǎn)對(duì)應(yīng)的就是節(jié)點(diǎn)A的默克爾樹分支
- 驗(yàn)證對(duì)應(yīng)的交易是否在默克爾樹中
驗(yàn)證某個(gè)節(jié)點(diǎn)是否在默克爾樹中代虾，在CBlock中對(duì)應(yīng)的方法代碼如下：
static uint256 CBlock::CheckMerkleBranch(uint256 hash, const vector<uint256>& vMerkleBranch, int nIndex)
{
if (nIndex == -1)
return 0;
foreach(const uint256& otherside, vMerkleBranch)
{
if (nIndex & 1)
hash = Hash(BEGIN(otherside), END(otherside), BEGIN(hash), END(hash));
else
hash = Hash(BEGIN(hash), END(hash), BEGIN(otherside), END(otherside));
nIndex >>= 1;
}
return hash;
}
驗(yàn)證CheckMerkleBranch方法返回的結(jié)果是否和CBlock中對(duì)應(yīng)的默克爾樹中對(duì)應(yīng)根的值一樣进肯，即如下面代碼所示：
if (CBlock::CheckMerkleBranch(GetHash(), vMerkleBranch, nIndex) != pBlock->hashMerkleRoot)
return 0;
對(duì)應(yīng)上面的例子對(duì)應(yīng)的驗(yàn)證過程如下圖所示：
驗(yàn)證第一步是得到節(jié)點(diǎn)E
驗(yàn)證第二步是得到節(jié)點(diǎn)G
比特幣交易對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)
交易對(duì)應(yīng)的類圖
對(duì)應(yīng)的代碼如下：
//
// The basic transaction that is broadcasted on the network and contained in
// blocks. A transaction can contain multiple inputs and outputs.
//
class CTransaction
{
public:
int nVersion;
vector<CTxIn> vin;
vector<CTxOut> vout;
int nLockTime;
// 方法省略
};
//
// A transaction with a merkle branch linking it to the block chain
//
class CMerkleTx : public CTransaction
{
public:
uint256 hashBlock;
vector<uint256> vMerkleBranch;
int nIndex;
// memory only
mutable bool fMerkleVerified;
// 方法省略
}；
從類圖或代碼中可以看到CMerkleTx 中有一個(gè)屬性是vMerkleBranch棉磨，表示的是對(duì)應(yīng)的每一個(gè)默克爾交易都對(duì)應(yīng)一個(gè)默克爾樹分支江掩，因此對(duì)應(yīng)默克爾交易可以很快的驗(yàn)證這個(gè)交易是否在某個(gè)CBlock中。
