第三章

本章将介绍一些新的数据结构。除非特别说明，本章提到的所有的类与函数均位于main.h或main.cpp。

每个节点均保存有一个区块链副本。区块链由相互连接的区块（CBlock实例）所构成。每个区块包含多笔交易（CTransaction实例）。为了存储、搜索、读取在内存与磁盘中的区块和交易信息，比特币引入了一些访问类。它们包括：CBlockIndex和CDiskBlockIndex用于索引区块，CDiskTxPos和CTxIndex用于索引交易。

CBlock

CBlock类表示一个区块。

class CBlock{public: // header int nVersion; uint256 hashPrevBlock; uint256 hashMerkleRoot; unsigned int nTime; unsigned int nBits; unsigned int nNonce; // network and disk vector vtx; // memory only mutable vector vMerkleTree; CBlock() { SetNull(); } IMPLEMENT_SERIALIZE ( READWRITE(this->nVersion); nVersion = this->nVersion; READWRITE(hashPrevBlock); READWRITE(hashMerkleRoot); READWRITE(nTime); READWRITE(nBits); READWRITE(nNonce); // ConnectBlock depends on vtx being last so it can calculate offset if (!(nType & (SER_GETHASH|SER_BLOCKHEADERONLY))) READWRITE(vtx); else if (fRead) const_cast(this)->vtx.clear(); ) void SetNull() { nVersion = 1; hashPrevBlock = 0; hashMerkleRoot = 0; nTime = 0; nBits = 0; nNonce = 0; vtx.clear(); vMerkleTree.clear(); 蓑衣网小编2022 } bool IsNull() const { return (nBits == 0); } uint256 GetHash() const { return Hash(BEGIN(nVersion), END(nNonce)); } uint256 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()); } vector GetMerkleBranch(int nIndex) const { if (vMerkleTree.empty()) BuildMerkleTree(); vector vMerkleBranch; int j = 0; for (int nSize = vtx.size(); nSize >蓑衣网小编2022 1; nSize = (nSize + 1) / 2) { int i = min(nIndex^1, nSize-1); vMerkleBranch.push_back(vMerkleTree[j+i]); nIndex >>= 1; j += nSize; } return vMerkleBranch; } static uint256 CheckMerkleBranch(uint256 hash, const vector& 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 蓑衣网小编2022 >>= 1; } return hash; } bool WriteToDisk(bool fWriteTransactions, unsigned int& nFileRet, unsigned int& nBlockPosRet) { // Open history file to append CAutoFile fileout = AppendBlockFile(nFileRet); if (!fileout) return error("CBlock::WriteToDisk() : AppendBlockFile failed"); if (!fWriteTransactions) fileout.nType |= SER_BLOCKHEADERONLY; // Write index header unsigned int nSize = fileout.GetSerializeSize(*this); fileout << FLATDATA(pchMessageStart) << nSize; // Write block nBlockPosRet = ftell(fileout); if (nBlockPosRet == -1) return error("CBlock::WriteToDisk() : ftell failed"); fileout <> *this; // Check the header if (CBigNum().SetCompact(nBits) > bnProofOfWorkLimit) return error("CBlock::ReadFromDisk() : nBits errors in block header"); if (GetHash() > CBigNum().SetCompact(nBits).getuint256()) return error("CBlock::ReadFromDisk() : GetHash() errors in block header"); return true; } void print() const { printf("CBlock(hash=%s, ver=%d, hashPrevBlock=%s, hashMerkleRoot=%s, nTime=%u, nBits=%08x, nNonce=%u, vtx=%d)\n", GetHash().ToString().substr(0,14).c_str(), nVersion, hashPrevBlock.ToString().substr(0,14).c_str(), hashMerkleRoot.ToString().substr(0,6).c_str(), nTime, nBits, nNonce, vtx.size()); for (int i = 0; i < vtx.size(); i++) { printf(" "); vtx[i].print(); } printf(" vMerkleTree: "); for (int i = 0; i < vMerkleTree.size(); i++) printf("%s ", vMerkleTree[i].ToString().substr(0,6).c_str()); printf("\n"); } int64 GetBlockValue(int64 nFees) const; bool DisconnectBlock(CTxDB& txdb, CBlockIndex* pindex); bool ConnectBlock(CTxDB& txdb, CBlockIndex* pindex); bool ReadFromDisk(const CBlockIndex* blockindex, bool fReadTransactions); bool AddToBlockIndex(unsigned int nFile, unsigned int nBlockPos); bool CheckBlock() const; bool AcceptBlock();};

这里有几点注意：

一个区块包含若干笔交易，并存放于vector vtx。一个区块的哈希，由函数GetHash()生成，是通过计算区块的块头（block-header）而不是整个区块数据所得到。更具体讲，哈希由成员变量nVersion到nNonce生成，而并不包括交易容器vtx。成员变量uint256 hashMerkleRoot是块头的一部分。它由成员函数BuildMerkleTree()生成，该函数将所有交易vtx作为输入参数，并最终生成一个256位哈希hashMerkleRoot。uint256 hashPrevBlock是当前区块之前的区块哈希，被包括在块头当中。因此，一个区块的哈希与它在区块链当中先前区块的哈希有关。

CBlock::BuildMerkleTree()

BuildMerkleTree()建立一个梅克尔树并返回树根。该树的每个节点，包括叶节点和中间节点，均为一个uint256哈希值。该树被扁平化并放置在vector vMerkleTree中。为了扁平化梅克尔树，该函数首先将第0层的叶节点放入vMerkleTree，接着将第1层的中间结点紧接着放在它们之后，向上重复该过程直到到达根结点。

位于第25行的变量j用于索引vMerkleTree的起始位置来放入树每一层的第一个节点。变量nSize是每层的节点个数。从第0层开始，nSize=vtx.size()，并且j=0。

最外层的for循环访问树的每一层。每层节点个数是上一层的一半（nSize=(nSize+1)/2，第26行）。里面的for循环依次访问某一层的每对节点，指针i每一步增量为2。节点对（i和i2）的哈希附加在容器vMerkleTree，其中i2=i+1。当i到达最后一对节点，i=nSize-1当nSize为奇数，或者i=nSize-2当nSize为偶数。在前者情形，最后一个节点（i2=i=nSize-1）则与其自身的复制组成节点对。

CBlock::GetMerkleBranch()

该函数返回一个梅克尔树分支。整个梅克尔树已被扁平化至容器vMerkleTree。参数nIndex指向容器vMerkleTree[nIndex]的那个节点。它的取值从0到vtx.size()。因此，nIndex永远指向一个叶节点，为某笔交易的哈希。

返回的梅克尔树分支包含了所有从vMerkleTre[nIndex]到树根所伴随的节点。回忆建立梅克尔树的过程，每一层的节点两两相配，成为下一层的节点。在第0层，若nIndex为偶数，则与节点vMerkleTree[nIndex]伴随的节点是vMerkleTree[nIndex+1]；若nIndex为奇数，则伴随节点为vMerkleTree[nIndex-1]。为了简化，我们把vMerkleTree[nIndex]称作节点A0，其伴随节点为B0。A0与B0相结合并生成另一个位于第1层节点A1。在第1层，A1的伴随节点为B1，两者配对并生成位于第2层的节点A2。重复该过程，直到到达梅克尔树根。节点[A0, A1, A2, ...]形成一条从A0到根节点的路径，它们的伴随节点[B0, B1, ...]则构成所返回的梅克尔分支。

为了找到伴随节点，该函数遍历树的每一层（第4行）。在每一层，指针nIndex比它前一层的值减半。因此，nIndex永远指向路径节点[A0, A1, A2, ...]。另一个指针i设为min(nIndex^1, nSize-1)，位于第46行。或运算符^1翻转nIndex最后一位，而不修改其他位。这将保证i永远指向nIndex所指向节点的伴随节点，例如节点[B0, B1, B2, ...]。

你可能会问，梅克尔树的作用是什么。它可以快速地验证一笔交易是否被包括在一个区块当中。下面我们将会介绍。

CBlock::CheckMerkleBranch()

这个函数接受它的第一个参数hash，用它检查第二个参数vMerkleBranch，并返回一个生成的梅克尔树根。如果所返回的树根与hashMerkleRoot相同，则hash所指向交易的哈希被包括在该CBlock当中。第三个参数nIndex是第一个参数在vMerkleTree当中的位置；它与GetMerkleBranch()的唯一参数是相同的。

因此，若需要检查一笔交易是否被包括在一个CBlock里，则仅需生成该笔交易的哈希并调用该函数，验证返回值是否与hashMerkleroot相同。

CBlock::WriteToDisk()与CBlock::ReadFromDisk()

WriteToDisk将一个CBlock写入磁盘。在第80行，它调用AppendBlockFile()。

FILE* OpenBlockFile(unsigned int nFile, unsigned int nBlockPos, const char* pszMode){ if (nFile == -1) return NULL; FILE* file = fopen(strprintf("%s\\blk%04d.dat", GetAppDir().c_str(), nFile).c_str(), pszMode); if (!file) return NULL; if (nBlockPos != 0 && !strchr(pszMode, 'a') && !strchr(pszMode, 'w')) { if (fseek(file, nBlockPos, SEEK_SET) != 0) { fclose(file); return NULL; } } return file;}static unsigned int nCurrentBlockFile = 1;FILE* AppendBlockFile(unsigned int& nFileRet){ nFileRet = 0; loop { FILE* file = OpenBlockFile(nCurrentBlockFile, 0, "ab"); if (!file) return NULL; if (fseek(file, 0, SEEK_END) != 0) return NULL; // FAT32 filesize max 4GB, fseek and ftell max 2GB, so we must stay under 2GB if (ftell(file) < 0x7F000000 - MAX_SIZE) { nFileRet = nCurrentBlockFile; return file; } fclose(file); nCurrentBlockFile++; }}

AppendBlockFile()的第一个参数nFileRet用于存放返回值。分析AppendBlockFile()和OpenBlockFile()源码显示nFileRet是一系列数据文件，以“blk0001.data”，“blk0002.data”的形式命名。区块被保存在这些文件中。它们被称作区块数据文件。

返回WriteToDisk()，第三个参数nBlockPosRet是当前CBlock在区块数据文件中存放的起始位置。在Block::WriteToDisk()的第89行，nBlockRet被赋给返回值ftell()，其为区块数据文件的当前指针位置。在其后面，当前CBlock以序列化后的形式被存储在区块数据文件里（第92行）。

ReadFromDisk()可以很直观地被理解。

CBlockIndex与CDiskBlockIndex

在上面对CBlock::WriteToDisk()和CBlock::ReadFromDisk()的分析显示区块被保存在一系列区块数据文件当中。CBlockIndex将这些信息全部封装在一个单独类CBlockIndex。//// The block chain is a tree shaped structure starting with the// genesis block at the root, with each block potentially having multiple// candidates to be the next block. pprev and pnext link a path through the// main/longest chain. A blockindex may have multiple pprev pointing back// to it, but pnext will only point forward to the longest branch, or will// be null if the block is not part of the longest chain.//class CBlockIndex{public: const uint256* phashBlock; CBlockIndex* pprev; CBlockIndex* pnext; unsigned int nFile; unsigned int nBlockPos; int nHeight; // block header int nVersion; uint256 hashMerkleRoot; unsigned int nTime; unsigned int nBits; unsigned int nNonce;//...... uint256 GetBlockHash() const { return *phashBlock; }//......};

除了nFile和nBlockPos，CBlockIndex还包括一份它所指向的区块头的副本（除了字段hashPrevBlock，可通过pprev->phashBlock访问）。这样可以使计算得到区块哈希不需要从区块数据文件中读取整个区块。

从注释的1-6行，我们可以知道pprev指向其在区块链中紧挨着的前一个区块索引，pnext则指向区块链中紧挨着的下一个区块索引。

如果你仔细注意的话，你会发现我提到的是“区块链中的区块索引”而不是“区块链中的区块”。这里有点让人头晕，毕竟区块链是由区块而不是区块索引构成的，不是吗？的确，区块链由区块所构成，但你也可以换一种说法：区块链由区块索引构成。这是一位区块的完整数据被保存在磁盘上的区块数据文件当中，而一个区块索引则通过区块的成员变量nFile和nBlockPos引用这个区块。指针pprev和pnext分别指向一个区块的前一个和下一个区块，以构成整个区块链。所以，区块索引与区块链同样具有意义。

尽管被称为区块链，比特币的区块链其实并不是线性结构，而是树状结构。这棵树的根节点是创世区块，被硬编码至源码当中。其他区块则在创世区块之上依次累积。在一个区块上累积两个或更多区块是合法的。当这种情况发生之后，区块链将产生一个分叉。一个区块链可能含有若干分叉，而分叉出来的分支则可能进一步分叉。

由于分叉的存在，多个区块索引的pprev字段可能指向同一个前任。这些区块索引每一个都开始一个分支，而这些分支都基于同一个前任区块。然而，前任区块的pnext字段只能指向开始最长一条分支的继任区块。从树根（创世区块）到最长分支的最后一个区块的路径被称为最长链，或最佳链，或这个区块链的主链。

指针phashBlock指向该区块的哈希，可以通过CBlockIndex内嵌的区块头现场计算。

nHeight是该区块在区块链中的高度。区块链由高度为0的区块开始，即创世区块。紧接着的区块高度为1，以此类推。

CBlockIndex实例仅保存在内存当中。若要将区块索引存入磁盘，衍生类CDiskBlockIndex在这里定义。

class CDiskBlockIndex : public CBlockIndex{public: uint256 hashPrev; uint256 hashNext; CDiskBlockIndex() { hashPrev = 0; hashNext = 0; } explicit CDiskBlockIndex(CBlockIndex* pindex) : CBlockIndex(*pindex) { hashPrev = (pprev ? pprev->GetBlockHash() : 0); hashNext = (pnext ? pnext->GetBlockHash() : 0); } IMPLEMENT_SERIALIZE ( if (!(nType & SER_GETHASH)) READWRITE(nVersion); READWRITE(hashNext); READWRITE(nFile); READWRITE(nBlockPos); READWRITE(nHeight); // block header READWRITE(this->nVersion); READWRITE(hashPrev); READWRITE(hashMerkleRoot); READWRITE(nTime); READWRITE(nBits); READWRITE(nNonce); ) uint256 GetBlockHash() const { CBlock block; block.nVersion = nVersion; block.hashPrevBlock = hashPrev; block.hashMerkleRoot = hashMerkleRoot; block.nTime = nTime; block.nBits = nBits; block.nNonce = nNonce; return block.GetHash(); }//......};

该类拥有另外两个成员变量：前任区块索引和继任区块索引的哈希，hashPrev和hashNext。不要将它们与CBlockIndex中的pprev和pnext搞混，后者是指向区块索引的指针，而前者则是区块的哈希。

CBlockIndex和CDiskBlockIndex本身均不带有哈希；它们永远用所指向区块的哈希辨识自己。从CDiskBlockIndex的构造器（第15行）可以总结出这点。在这个构造器里，hashPrev被赋值为pprev->GetBlockHash()，其中pprev是一个CBlockIndex的指针。如果你检查CBlockIndex的成员函数GetBlockHash，你可以看到它返回的是前任区块的哈希。对于CDiskBlockIndex，它的成员函数GetBlockHash()同样返回它所指向区块的哈希。

CBlockIndex没有序列化方法，而CDiskBlockIndex则通过宏IMPLEMENT_SERIALIZE实现序列化。这是因为后者需要保存在磁盘里，而前者只存在于内存当中。

CMerkleTx与CWallet

在了解梅克尔树和CBlock之后，我们一起检查另外两个由CTransaction衍生的重要的类：CMerkleTx与CWallet。

class CMerkleTx : public CTransaction{public: uint256 hashBlock; vector vMerkleBranch; int nIndex; // memory only mutable bool fMerkleVerified; CMerkleTx() { Init(); } CMerkleTx(const CTransaction& txIn) : CTransaction(txIn) { Init(); } void Init() { hashBlock = 0; nIndex = -1; fMerkleVerified = false; } int64 GetCredit() const { // Must wait until coinbase is safely deep enough in the chain before valuing it if (IsCoinBase() && GetBlocksToMaturity() > 0) return 0; return CTransaction::GetCredit(); } IMPLEMENT_SERIALIZE ( nSerSize += SerReadWrite(s, *(CTransaction*)this, nType, nVersion, ser_action); nVersion = this->nVersion; READWRITE(hashBlock); READWRITE(vMerkleBranch); READWRITE(nIndex); ) int SetMerkleBranch(const CBlock* pblock=NULL); int GetDepthInMainChain() const; bool IsInMainChain() const { return GetDepthInMainChain() > 0; } int GetBlocksToMaturity() const; bool AcceptTransaction(CTxDB& txdb, bool fCheckInputs=true); bool AcceptTransaction() { CTxDB txdb("r"); return AcceptTransaction(txdb); }};

CTransaction的实例被收集并生成一个CBlock。对于指定的CTransaction实例，它的梅克尔分支，和它在CBlock的vector vtx字段中的位置，可以用于查找该实例是否被包含在这个CBlock里面。这便是为什么CMerkleTx包含另外两个字段：一个梅克尔分支vMerkleBranch，和一个位置索引nIndex。一个CMerkleTx实例携带有这两个字段使其能方便地被验证是否属于一个区块。

uint256 hashBlock是该交易所在CBlock的哈希。

CWalletTx进一步延伸CMerkleTx，包括了关于“只有（该笔交易的）拥有者关心”的信息。这些成员字段将被提及，当我们在代码当中遇到它们的时候。

class CWalletTx : public CMerkleTx{public: vector vtxPrev; map mapValue; vector vOrderForm; unsigned int fTimeReceivedIsTxTime; unsigned int nTimeReceived; // time received by this node char fFromMe; char fSpent; //// probably need to sign the order info so know it came from payer // memory only mutable unsigned int nTimeDisplayed;//......};

CDiskTxPos与CTxIndex

这两个类用来索引交易。

class CDiskTxPos{public: unsigned int nFile; unsigned int nBlockPos; unsigned int nTxPos;//......}class CTxIndex{public: CDiskTxPos pos; vector vSpent;}

CDiskTxPos中的nFile，nBlockPos和nTxPos分别是区块数据文件的序号，区块在区块数据文件当中的位置和交易在区块数据中的位置。因此，CDiskTxPos包含了从区块数据文件中找到某笔交易的全部信息。

一个CTxIndex是一个数据库记录“包含有一笔交易和花费这笔交易输出的交易在磁盘的位置”。一笔交易可以很容易地找到它的来源交易（参见第一章），但反过来不行。vector vSpent包含所有由CDiskTxPos pos指向的某笔交易作为来源交易的交易的位置，例如所有花费CDiskTxPos pos指向的交易的交易。