比特幣核心數據結構
- 2019 年 10 月 3 日
- 筆記
我們學習電腦時曾經有這麼一個定義：程式=數據結構+演算法，對於一個區塊鏈，我認為從技術方面看與程式的定義類似，核心一個是共識演算法，一個是核心數據結構，這兩點直接決定了這條區塊鏈工作運行原理。比特幣的共識演算法，在這一篇《哈希函數與比特幣共識演算法PoW》中已經講述了其原理，這一篇主要講述比特幣核心數據結構這一部分。主要包括如下內容：
- Blockchain（區塊鏈）
- Block（區塊）
- Block Header（區塊頭部）
- Merkle Tree（默克爾樹）
- Transaction（交易）
Blockchain
區塊鏈很難用一個什麼定義來描述，如果一定要描述的話，借用以太坊黃皮書中的解釋：區塊鏈就是一個具有共享狀態的密碼性安全交易的單機(cryptographically secure transactional singleton machine with shared-state)。這裡按數據結構的層面來描述區塊鏈，就是用哈希指針將一些列區塊串聯起來形成的一條數據鏈。在比特幣區塊鏈中，是有區塊這個概念的，現在部分區塊鏈中已經沒有區塊這個概念了，感興趣的可以關注一下DAG。
Block
上面講到區塊鏈是由一個個區塊構成的，哪區塊是怎麼定義的？由區塊頭部和交易兩部分構成：
- 區塊頭部: a data structure containing the block’s metadata
- 交易列表: an array (vector in rust) of transactions
C++版本實現定義：
class CBlock : public CBlockHeader { public: // network and disk std::vector<CTransactionRef> vtx; //...省略部分程式碼... }Rust版本實現定義，可以看到基本都是一樣的：
#[derive(Debug, PartialEq, Clone, Serializable, Deserializable)] pub struct Block { pub block_header: BlockHeader, // 區塊頭部 pub transactions: Vec<Transaction>, // 交易列表 }BlockHeader
區塊頭部定義如下：
c++版本實現定義：
/** 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. */ class CBlockHeader { public: // header int32_t nVersion; // 版本號，指定驗證規則(indicates which set of block validation rules to follow) uint256 hashPrevBlock; // 前一區塊哈希（實際計算時取得是前一區塊頭哈希）(a reference to the parent/previous block in the blockchain) uint256 hashMerkleRoot; // 默克爾根哈希(a hash (root hash) of the merkle tree data structure containing a block's transactions) uint32_t nTime; // 時戳(seconds from Unix Epoch) uint32_t nBits; // 區塊難度(aka the difficulty target for this block) uint32_t nNonce; // 工作量證明nonce(value used in proof-of-work) // ...部分程式碼省略... }Rust實現版本定義，可以看到基本都是一樣的：
#[derive(PartialEq, Clone, Serializable, Deserializable)] pub struct BlockHeader { pub version: u32, // 版本號，指定驗證規則 pub previous_header_hash: H256, // 前一區塊哈希 pub merkle_root_hash: H256, // 默克爾根哈希 pub time: u32, // 時戳 pub bits: Compact, // 區塊難度 pub nonce: u32, // 工作量證明nonce }Merkle Tree
上面區塊頭部的hashMerkleRoot欄位就是默克爾樹根哈希值，默克爾樹可以說是區塊中最重要的一個數據結構，不僅僅提供了整個區塊所有交易的完整性驗證，。
Rust版本Merkle tree程式碼實現如下：
/// Calculates the root of the merkle tree /// https://en.bitcoin.it/wiki/Protocol_documentation#Merkle_Trees pub fn merkle_root<T: AsRef<H256> + Sync>(hashes: &[T]) -> H256{ // 遞歸結束條件 if hashes.len() == 1 { return hashes[0].as_ref().clone(); } // 哈希成對，為下一步計算做準備 let mut row = Vec::with_capacity(hashes.len() / 2); let mut i = 0; while i + 1 < hashes.len() { row.push((&hashes[i], &hashes[i + 1])); i += 2 } // duplicate the last element if len is not even if hashes.len() % 2 == 1 { let last = &hashes[hashes.len() - 1]; row.push((last, last)); //如果元素是奇數個數，將最後一個元素複製一份，自己與自己配對 } // 一層一層的遞歸計算，一直到只有最後一個根哈希值 let res: Vec<_>; // Only compute in parallel if there is enough work to benefit it if row.len() > 250 { res = row.par_iter().map(|x| merkle_node_hash(&x.0, &x.1)).collect(); } else { res = row.iter().map(|x| merkle_node_hash(&x.0, &x.1)).collect(); } merkle_root(&res) // 這裡不用擔心遞歸的深度，其一，比特幣區塊大小有限，限制了交易數量；其二，是因為Merkle tree是類似二叉樹的結構，遞歸計算次數為log(n)，即使n非常大，遞歸次數也很小。 } /// Calculate merkle tree node hash pub fn merkle_node_hash<T>(left: T, right: T) -> H256 where T: AsRef<H256> { dhash256(&*concat(left, right)) //雙SHA-256哈希運算 } #[inline] fn concat<T>(a: T, b: T) -> H512 where T: AsRef<H256> { //將2個哈希值並在一起 let mut result = H512::default(); result[0..32].copy_from_slice(&**a.as_ref()); result[32..64].copy_from_slice(&**b.as_ref()); result }Transaction
Rust實現版本定義如下：
pub struct Transaction { pub version: i32, //協議版本，明確這筆交易參照的規則協議 pub inputs: Vec<TransactionInput>, //輸入列表 pub outputs: Vec<TransactionOutput>, //輸出列表 pub lock_time: u32, //鎖定時間 }可以看到，交易中最重要的是輸入列表和輸出列表，說明這次比特幣轉賬時比特幣的來源和轉賬去向。
Rust版本實現輸入列表定義：
pub struct TransactionInput { pub previous_output: OutPoint, //上一筆交易輸出 pub script_sig: Bytes, //解鎖腳本 pub sequence: u32, //序列號 pub script_witness: Vec<Bytes>, //見證腳本 } /** An outpoint - a combination of a transaction hash and an index n into its vout */ pub struct OutPoint { pub hash: H256, //交易ID pub index: u32, //輸出索引，表明是交易中的第幾個輸出 }上面這個OutPoint定義如何沒有理解的話，可參考下圖進行理解：
Rust版本實現輸出列表定義：
pub struct TransactionOutput { pub value: u64, //輸出金額 pub script_pubkey: Bytes, //鎖定腳本，對於一個比特幣交易來說，交易本身是不用關心輸出的地址，交易只需要關心鎖定腳本，當使用的時候能使用正確的解鎖腳本即可動用比特幣。 }更多請參考我的另一篇博文比特幣交易。
