本章將介紹一些新的數據結構。除非特別說明，本章提到的所有的類與函數均位于main.h或main.cpp。

每個節點均保存有一個區塊鏈副本。區塊鏈由相互連接的區塊（CBlock實例）所構成。每個區塊包含多筆交易（CTransaction實力）。為了存儲、搜索、讀取在內存與磁盤中的區塊和交易信息，比特幣引入了一些訪問類。它們包括：CBlockIndex和CDiskBlockIndex用于索引區塊，CDiskTxPos和CTxIndex用于索引交易。

CBlock

CBlock類表示一個區塊。

[cpp]view plaincopy

classCBlock

{

public:

//header

intnVersion;

uint256hashPrevBlock;

uint256hashMerkleRoot;

unsignedintnTime;

unsignedintnBits;

unsignedintnNonce;

//networkanddisk

vectorvtx;

//memoryonly

mutablevectorvMerkleTree;

CBlock()

{

SetNull();

}

IMPLEMENT_SERIALIZE

(

READWRITE(this->nVersion);

nVersion=this->nVersion;

READWRITE(hashPrevBlock);

READWRITE(hashMerkleRoot);

READWRITE(nTime);

READWRITE(nBits);

READWRITE(nNonce);

//ConnectBlockdependsonvtxbeinglastsoitcancalculateoffset

if(!(nType&(SER_GETHASH|SER_BLOCKHEADERONLY)))

READWRITE(vtx);

elseif(fRead)

const_cast(this)->vtx.clear();

)

voidSetNull()

{

nVersion=1;

hashPrevBlock=0;

hashMerkleRoot=0;

nTime=0;

nBits=0;

nNonce=0;

vtx.clear();

vMerkleTree.clear();

}

boolIsNull()const

{

return(nBits==0);

}

uint256GetHash()const

{

returnHash(BEGIN(nVersion),END(nNonce));

}

uint256BuildMerkleTree()const

{

vMerkleTree.clear();

foreach(constCTransaction&tx,vtx)

vMerkleTree.push_back(tx.GetHash());

intj=0;

for(intnSize=vtx.size();nSize>1;nSize=(nSize+1)/2)

{

for(inti=0;i

{

inti2=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());

}

vectorGetMerkleBranch(intnIndex)const

{

if(vMerkleTree.empty())

BuildMerkleTree();

vectorvMerkleBranch;

intj=0;

for(intnSize=vtx.size();nSize>1;nSize=(nSize+1)/2)

{

inti=min(nIndex^1,nSize-1);

vMerkleBranch.push_back(vMerkleTree[j+i]);

nIndex>>=1;

j+=nSize;

}

returnvMerkleBranch;

}

staticuint256CheckMerkleBranch(uint256hash,constvector&vMerkleBranch,intnIndex)

{

if(nIndex==-1)

return0;

foreach(constuint256&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;

}

returnhash;

}

boolWriteToDisk(boolfWriteTransactions,unsignedint&nFileRet,unsignedint&nBlockPosRet)

{

//Openhistoryfiletoappend

CAutoFilefileout=AppendBlockFile(nFileRet);

if(!fileout)

returnerror("CBlock::WriteToDisk():AppendBlockFilefailed");

if(!fWriteTransactions)

fileout.nType|=SER_BLOCKHEADERONLY;

//Writeindexheader

unsignedintnSize=fileout.GetSerializeSize(*this);

fileout<

//Writeblock

nBlockPosRet=ftell(fileout);

if(nBlockPosRet==-1)

returnerror("CBlock::WriteToDisk():ftellfailed");

fileout<

returntrue;

}

boolReadFromDisk(unsignedintnFile,unsignedintnBlockPos,boolfReadTransactions)

{

SetNull();

//Openhistoryfiletoread

CAutoFilefilein=OpenBlockFile(nFile,nBlockPos,"rb");

if(!filein)

returnerror("CBlock::ReadFromDisk():OpenBlockFilefailed");

if(!fReadTransactions)

filein.nType|=SER_BLOCKHEADERONLY;

//Readblock

filein>>*this;

//Checktheheader

if(CBigNum().SetCompact(nBits)>bnProofOfWorkLimit)

returnerror("CBlock::ReadFromDisk():nBitserrorsinblockheader");

if(GetHash()>CBigNum().SetCompact(nBits).getuint256())

returnerror("CBlock::ReadFromDisk():GetHash()errorsinblockheader");

returntrue;

}

voidprint()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(inti=0;i

{

printf("");

vtx[i].print();

}

printf("vMerkleTree:");

for(inti=0;i

printf("%s",vMerkleTree[i].ToString().substr(0,6).c_str());

printf("\n");

}

int64GetBlockValue(int64nFees)const;

boolDisconnectBlock(CTxDB&txdb,CBlockIndex*pindex);

boolConnectBlock(CTxDB&txdb,CBlockIndex*pindex);

boolReadFromDisk(constCBlockIndex*blockindex,boolfReadTransactions);

boolAddToBlockIndex(unsignedintnFile,unsignedintnBlockPos);

boolCheckBlock()const;

boolAcceptBlock();

};

這里有幾點注意：

一個區塊包含若干筆交易，并存放于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()。

[cpp]view plaincopy

FILE*OpenBlockFile(unsignedintnFile,unsignedintnBlockPos,constchar*pszMode)

{

if(nFile==-1)

returnNULL;

FILE*file=fopen(strprintf("%s\\blk%04d.dat",GetAppDir().c_str(),nFile).c_str(),pszMode);

if(!file)

returnNULL;

if(nBlockPos!=0&&!strchr(pszMode,'a')&&!strchr(pszMode,'w'))

{

if(fseek(file,nBlockPos,SEEK_SET)!=0)

{

fclose(file);

returnNULL;

}

}

returnfile;

}

staticunsignedintnCurrentBlockFile=1;

FILE*AppendBlockFile(unsignedint&nFileRet)

{

nFileRet=0;

loop

{

FILE*file=OpenBlockFile(nCurrentBlockFile,0,"ab");

if(!file)

returnNULL;

if(fseek(file,0,SEEK_END)!=0)

returnNULL;

//FAT32filesizemax4GB,fseekandftellmax2GB,sowemuststayunder2GB

if(ftell(file)

{

nFileRet=nCurrentBlockFile;

returnfile;

}

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。

[cpp]view plaincopy

//

//Theblockchainisatreeshapedstructurestartingwiththe

//genesisblockattheroot,witheachblockpotentiallyhavingmultiple

//candidatestobethenextblock.pprevandpnextlinkapaththroughthe

//main/longestchain.Ablockindexmayhavemultiplepprevpointingback

//toit,butpnextwillonlypointforwardtothelongestbranch,orwill

//benulliftheblockisnotpartofthelongestchain.

//

classCBlockIndex

{

public:

constuint256*phashBlock;

CBlockIndex*pprev;

CBlockIndex*pnext;

unsignedintnFile;

unsignedintnBlockPos;

intnHeight;

//blockheader

intnVersion;

uint256hashMerkleRoot;

unsignedintnTime;

unsignedintnBits;

unsignedintnNonce;

//......

uint256GetBlockHash()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在這里定義。

[cpp]view plaincopy

classCDiskBlockIndex:publicCBlockIndex

{

public:

uint256hashPrev;

uint256hashNext;

CDiskBlockIndex()

{

hashPrev=0;

hashNext=0;

}

explicitCDiskBlockIndex(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);

//blockheader

READWRITE(this->nVersion);

READWRITE(hashPrev);

READWRITE(hashMerkleRoot);

READWRITE(nTime);

READWRITE(nBits);

READWRITE(nNonce);

)

uint256GetBlockHash()const

{

CBlockblock;

block.nVersion=nVersion;

block.hashPrevBlock=hashPrev;

block.hashMerkleRoot=hashMerkleRoot;

block.nTime=nTime;

block.nBits=nBits;

block.nNonce=nNonce;

returnblock.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。

[cpp]view plaincopy

classCMerkleTx:publicCTransaction

{

public:

uint256hashBlock;

vectorvMerkleBranch;

intnIndex;

//memoryonly

mutableboolfMerkleVerified;

CMerkleTx()

{

Init();

}

CMerkleTx(constCTransaction&txIn):CTransaction(txIn)

{

Init();

}

voidInit()

{

hashBlock=0;

nIndex=-1;

fMerkleVerified=false;

}

int64GetCredit()const

{

//Mustwaituntilcoinbaseissafelydeepenoughinthechainbeforevaluingit

if(IsCoinBase()&&GetBlocksToMaturity()>0)

return0;

returnCTransaction::GetCredit();

}

IMPLEMENT_SERIALIZE

(

nSerSize+=SerReadWrite(s,*(CTransaction*)this,nType,nVersion,ser_action);

nVersion=this->nVersion;

READWRITE(hashBlock);

READWRITE(vMerkleBranch);

READWRITE(nIndex);

)

intSetMerkleBranch(constCBlock*pblock=NULL);

intGetDepthInMainChain()const;

boolIsInMainChain()const{returnGetDepthInMainChain()>0;}

intGetBlocksToMaturity()const;

boolAcceptTransaction(CTxDB&txdb,boolfCheckInputs=true);

boolAcceptTransaction(){CTxDBtxdb("r");returnAcceptTransaction(txdb);}

};

CTransaction的實例被收集并生成一個CBlock。對于指定的CTransaction實例，它的梅克爾分支，和它在CBlock的vector vtx字段中的位置，可以用于查找該實例是否被包含在這個CBlock里面。這便是為什么CMerkleTx包含另外兩個字段：一個梅克爾分支vMerkleBranch，和一個位置索引nIndex。一個CMerkleTx實例攜帶有這兩個字段使其能方便地被驗證是否屬于一個區塊。

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

CWalletTx進一步延伸CMerkleTx，包括了關于“只有（該筆交易的）擁有者關心”的信息。這些成員字段將被提及，當我們在代碼當中遇到它們的時候。

[cpp]view plaincopy

classCWalletTx:publicCMerkleTx

{

public:

vectorvtxPrev;

mapmapValue;

vector

unsignedintfTimeReceivedIsTxTime;

unsignedintnTimeReceived;//timereceivedbythisnode

charfFromMe;

charfSpent;

////probablyneedtosigntheorderinfosoknowitcamefrompayer

//memoryonly

mutableunsignedintnTimeDisplayed;

//......

};

CDiskTxPos與CTxIndex

這兩個類用來索引交易。

[cpp]view plaincopy

classCDiskTxPos

{

public:

unsignedintnFile;

unsignedintnBlockPos;

unsignedintnTxPos;

//......

}

classCTxIndex

{

public:

CDiskTxPospos;

vectorvSpent;

}

CDiskTxPos中的nFile，nBlockPos和nTxPos分別是區塊數據文件的序號，區塊在區塊數據文件當中的位置和交易在區塊數據中的位置。因此，CDiskTxPos包含了從區塊數據文件中找到某筆交易的全部信息。

一個CTxIndex是一個數據庫記錄“包含有一筆交易和花費這筆交易輸出的交易在磁盤的位置”。一筆交易可以很容易地找到它的來源交易（參見第一章），但反過來不行。vector vSpent包含所有由CDiskTxPos pos指向的某筆交易作為來源交易的交易的位置，例如所有花費CDiskTxPos pos指向的交易的交易。