本章將介紹一些新的數(shù)據(jù)結(jié)構(gòu)。除非特別說明，本章提到的所有的類與函數(shù)均位于main.h或main.cpp。

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

CBlock

CBlock類表示一個區(qū)塊。

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

};

這里有幾點注意：

一個區(qū)塊包含若干筆交易，并存放于vector vtx。

一個區(qū)塊的哈希，由函數(shù)GetHash()生成，是通過計算區(qū)塊的塊頭（block-header）而不是整個區(qū)塊數(shù)據(jù)所得到。更具體講，哈希由成員變量nVersion到nNonce生成，而并不包括交易容器vtx。

成員變量uint256 hashMerkleRoot是塊頭的一部分。它由成員函數(shù)BuildMerkleTree()生成，該函數(shù)將所有交易vtx作為輸入參數(shù)，并最終生成一個256位哈希hashMerkleRoot。

uint256 hashPrevBlock是當(dāng)前區(qū)塊之前的區(qū)塊哈希，被包括在塊頭當(dāng)中。因此，一個區(qū)塊的哈希與它在區(qū)塊鏈當(dāng)中先前區(qū)塊的哈希有關(guān)。

CBlock::BuildMerkleTree()

BuildMerkleTree()建立一個梅克爾樹并返回樹根。該樹的每個節(jié)點，包括葉節(jié)點和中間節(jié)點，均為一個uint256哈希值。該樹被扁平化并放置在vector vMerkleTree中。為了扁平化梅克爾樹，該函數(shù)首先將第0層的葉節(jié)點放入vMerkleTree，接著將第1層的中間結(jié)點緊接著放在它們之后，向上重復(fù)該過程直到到達(dá)根結(jié)點。

位于第25行的變量j用于索引vMerkleTree的起始位置來放入樹每一層的第一個節(jié)點。變量nSize是每層的節(jié)點個數(shù)。從第0層開始，nSize=vtx.size()，并且j=0。

最外層的for循環(huán)訪問樹的每一層。每層節(jié)點個數(shù)是上一層的一半（nSize=(nSize+1)/2，第26行）。里面的for循環(huán)依次訪問某一層的每對節(jié)點，指針i每一步增量為2。節(jié)點對（i和i2）的哈希附加在容器vMerkleTree，其中i2=i+1。當(dāng)i到達(dá)最后一對節(jié)點，i=nSize-1當(dāng)nSize為奇數(shù)，或者i=nSize-2當(dāng)nSize為偶數(shù)。在前者情形，最后一個節(jié)點（i2=i=nSize-1）則與其自身的復(fù)制組成節(jié)點對。

CBlock::GetMerkleBranch()

該函數(shù)返回一個梅克爾樹分支。整個梅克爾樹已被扁平化至容器vMerkleTree。參數(shù)nIndex指向容器vMerkleTree[nIndex]的那個節(jié)點。它的取值從0到vtx.size()。因此，nIndex永遠(yuǎn)指向一個葉節(jié)點，為某筆交易的哈希。

返回的梅克爾樹分支包含了所有從vMerkleTre[nIndex]到樹根所伴隨的節(jié)點。回憶建立梅克爾樹的過程，每一層的節(jié)點兩兩相配，成為下一層的節(jié)點。在第0層，若nIndex為偶數(shù)，則與節(jié)點vMerkleTree[nIndex]伴隨的節(jié)點是vMerkleTree[nIndex+1]；若nIndex為奇數(shù)，則伴隨節(jié)點為vMerkleTree[nIndex-1]。為了簡化，我們把vMerkleTree[nIndex]稱作節(jié)點A0，其伴隨節(jié)點為B0。A0與B0相結(jié)合并生成另一個位于第1層節(jié)點A1。在第1層，A1的伴隨節(jié)點為B1，兩者配對并生成位于第2層的節(jié)點A2。重復(fù)該過程，直到到達(dá)梅克爾樹根。節(jié)點[A0, A1, A2, ...]形成一條從A0到根節(jié)點的路徑，它們的伴隨節(jié)點[B0, B1, ...]則構(gòu)成所返回的梅克爾分支。

為了找到伴隨節(jié)點，該函數(shù)遍歷樹的每一層（第4行）。在每一層，指針nIndex比它前一層的值減半。因此，nIndex永遠(yuǎn)指向路徑節(jié)點[A0, A1, A2, ...]。另一個指針i設(shè)為min(nIndex^1, nSize-1)，位于第46行?；蜻\(yùn)算符^1翻轉(zhuǎn)nIndex最后一位，而不修改其他位。這將保證i永遠(yuǎn)指向nIndex所指向節(jié)點的伴隨節(jié)點，例如節(jié)點[B0, B1, B2, ...]。

你可能會問，梅克爾樹的作用是什么。它可以快速地驗證一筆交易是否被包括在一個區(qū)塊當(dāng)中。下面我們將會介紹。

CBlock::CheckMerkleBranch()

這個函數(shù)接受它的第一個參數(shù)hash，用它檢查第二個參數(shù)vMerkleBranch，并返回一個生成的梅克爾樹根。如果所返回的樹根與hashMerkleRoot相同，則hash所指向交易的哈希被包括在該CBlock當(dāng)中。第三個參數(shù)nIndex是第一個參數(shù)在vMerkleTree當(dāng)中的位置；它與GetMerkleBranch()的唯一參數(shù)是相同的。

因此，若需要檢查一筆交易是否被包括在一個CBlock里，則僅需生成該筆交易的哈希并調(diào)用該函數(shù)，驗證返回值是否與hashMerkleroot相同。

CBlock::WriteToDisk()與CBlock::ReadFromDisk()

WriteToDisk將一個CBlock寫入磁盤。在第80行，它調(diào)用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()的第一個參數(shù)nFileRet用于存放返回值。分析AppendBlockFile()和OpenBlockFile()源碼顯示nFileRet是一系列數(shù)據(jù)文件，以“blk0001.data”，“blk0002.data”的形式命名。區(qū)塊被保存在這些文件中。它們被稱作區(qū)塊數(shù)據(jù)文件。

返回WriteToDisk()，第三個參數(shù)nBlockPosRet是當(dāng)前CBlock在區(qū)塊數(shù)據(jù)文件中存放的起始位置。在Block::WriteToDisk()的第89行，nBlockRet被賦給返回值ftell()，其為區(qū)塊數(shù)據(jù)文件的當(dāng)前指針位置。在其后面，當(dāng)前CBlock以序列化后的形式被存儲在區(qū)塊數(shù)據(jù)文件里（第92行）。

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

CBlockIndex與CDiskBlockIndex

在上面對CBlock::WriteToDisk()和CBlock::ReadFromDisk()的分析顯示區(qū)塊被保存在一系列區(qū)塊數(shù)據(jù)文件當(dāng)中。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還包括一份它所指向的區(qū)塊頭的副本（除了字段hashPrevBlock，可通過pprev->phashBlock訪問）。這樣可以使計算得到區(qū)塊哈希不需要從區(qū)塊數(shù)據(jù)文件中讀取整個區(qū)塊。

從注釋的1-6行，我們可以知道pprev指向其在區(qū)塊鏈中緊挨著的前一個區(qū)塊索引，pnext則指向區(qū)塊鏈中緊挨著的下一個區(qū)塊索引。

如果你仔細(xì)注意的話，你會發(fā)現(xiàn)我提到的是“區(qū)塊鏈中的區(qū)塊索引”而不是“區(qū)塊鏈中的區(qū)塊”。這里有點讓人頭暈，畢竟區(qū)塊鏈?zhǔn)怯蓞^(qū)塊而不是區(qū)塊索引構(gòu)成的，不是嗎？的確，區(qū)塊鏈由區(qū)塊所構(gòu)成，但你也可以換一種說法：區(qū)塊鏈由區(qū)塊索引構(gòu)成。這是一位區(qū)塊的完整數(shù)據(jù)被保存在磁盤上的區(qū)塊數(shù)據(jù)文件當(dāng)中，而一個區(qū)塊索引則通過區(qū)塊的成員變量nFile和nBlockPos引用這個區(qū)塊。指針pprev和pnext分別指向一個區(qū)塊的前一個和下一個區(qū)塊，以構(gòu)成整個區(qū)塊鏈。所以，區(qū)塊索引與區(qū)塊鏈同樣具有意義。

盡管被稱為區(qū)塊鏈，比特幣的區(qū)塊鏈其實并不是線性結(jié)構(gòu)，而是樹狀結(jié)構(gòu)。這棵樹的根節(jié)點是創(chuàng)世區(qū)塊，被硬編碼至源碼當(dāng)中。其他區(qū)塊則在創(chuàng)世區(qū)塊之上依次累積。在一個區(qū)塊上累積兩個或更多區(qū)塊是合法的。當(dāng)這種情況發(fā)生之后，區(qū)塊鏈將產(chǎn)生一個分叉。一個區(qū)塊鏈可能含有若干分叉，而分叉出來的分支則可能進(jìn)一步分叉。

由于分叉的存在，多個區(qū)塊索引的pprev字段可能指向同一個前任。這些區(qū)塊索引每一個都開始一個分支，而這些分支都基于同一個前任區(qū)塊。然而，前任區(qū)塊的pnext字段只能指向開始最長一條分支的繼任區(qū)塊。從樹根（創(chuàng)世區(qū)塊）到最長分支的最后一個區(qū)塊的路徑被稱為最長鏈，或最佳鏈，或這個區(qū)塊鏈的主鏈。

指針phashBlock指向該區(qū)塊的哈希，可以通過CBlockIndex內(nèi)嵌的區(qū)塊頭現(xiàn)場計算。

nHeight是該區(qū)塊在區(qū)塊鏈中的高度。區(qū)塊鏈由高度為0的區(qū)塊開始，即創(chuàng)世區(qū)塊。緊接著的區(qū)塊高度為1，以此類推。

CBlockIndex實例僅保存在內(nèi)存當(dāng)中。若要將區(qū)塊索引存入磁盤，衍生類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();

}

//......

};

該類擁有另外兩個成員變量：前任區(qū)塊索引和繼任區(qū)塊索引的哈希，hashPrev和hashNext。不要將它們與CBlockIndex中的pprev和pnext搞混，后者是指向區(qū)塊索引的指針，而前者則是區(qū)塊的哈希。

CBlockIndex和CDiskBlockIndex本身均不帶有哈希；它們永遠(yuǎn)用所指向區(qū)塊的哈希辨識自己。從CDiskBlockIndex的構(gòu)造器（第15行）可以總結(jié)出這點。在這個構(gòu)造器里，hashPrev被賦值為pprev->GetBlockHash()，其中pprev是一個CBlockIndex的指針。如果你檢查CBlockIndex的成員函數(shù)GetBlockHash，你可以看到它返回的是前任區(qū)塊的哈希。對于CDiskBlockIndex，它的成員函數(shù)GetBlockHash()同樣返回它所指向區(qū)塊的哈希。

CBlockIndex沒有序列化方法，而CDiskBlockIndex則通過宏IMPLEMENT_SERIALIZE實現(xiàn)序列化。這是因為后者需要保存在磁盤里，而前者只存在于內(nèi)存當(dāng)中。

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實例攜帶有這兩個字段使其能方便地被驗證是否屬于一個區(qū)塊。

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

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

[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分別是區(qū)塊數(shù)據(jù)文件的序號，區(qū)塊在區(qū)塊數(shù)據(jù)文件當(dāng)中的位置和交易在區(qū)塊數(shù)據(jù)中的位置。因此，CDiskTxPos包含了從區(qū)塊數(shù)據(jù)文件中找到某筆交易的全部信息。

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