比特幣中的數(shù)據(jù)結(jié)構(gòu)

1. 區(qū)塊鏈（block chain）

哈希指針：

（1）保存數(shù)值的位置
（2）保存數(shù)值的哈希值

區(qū)塊鏈：一個(gè)使用哈希指針的鏈表

genesis block：創(chuàng)世塊（最開始創(chuàng)建的塊）
most recent block：最近創(chuàng)建的塊
tamper-evident log：篡改證明記錄

每一個(gè)當(dāng)前區(qū)塊都保存了上一個(gè)區(qū)塊所有內(nèi)容的哈希值與位置，形成了一個(gè)哈希指針，保存在當(dāng)前區(qū)塊中，所有區(qū)塊利用哈希指針形成了區(qū)塊鏈。最后一個(gè)區(qū)塊的哈希指針保存在系統(tǒng)內(nèi)部。

當(dāng)區(qū)塊鏈中某一個(gè)區(qū)塊（圖中紅色區(qū)塊）的內(nèi)容遭到篡改，那么這個(gè)區(qū)塊后面的所有區(qū)塊（圖中紅色區(qū)塊右邊的區(qū)塊）中的哈希指針都要修改。因此只需要通過對(duì)比最后一個(gè)區(qū)塊的哈希值是否被修改就能夠察覺整個(gè)區(qū)塊鏈上的區(qū)塊是否遭到了篡改。

有了這個(gè)性質(zhì)，比特幣上的某些節(jié)點(diǎn)無需保存所有的區(qū)塊，有的可能只保存了離自己最近的幾千個(gè)區(qū)塊。如果要用到更靠前的區(qū)塊，那么可以向其他人詢問，但如何保證詢問到的區(qū)塊是可靠的呢？只需要對(duì)比保存的區(qū)塊的最前面一個(gè)區(qū)塊內(nèi)保存的的哈希值與別人給的區(qū)塊的哈希值是否一致即可。

2. 默克爾樹（Merkle tree）

默克爾樹：一個(gè)使用哈希指針的二叉樹。樹中包含數(shù)據(jù)塊（交易記錄）和哈希指針。

區(qū)塊的結(jié)構(gòu)：

（1）block header：保存了root hash
（2）block body：保存交易記錄數(shù)據(jù)信息

Merkle tree的用途：向輕節(jié)點(diǎn)證明某個(gè)記錄被寫入到了區(qū)塊鏈。proof of membership或proof of inclusion

比特幣中有兩種節(jié)點(diǎn)（區(qū)塊）：
輕節(jié)點(diǎn)：只保存block header
全節(jié)點(diǎn)：既有block header，又有block body

Merkle proof：

圖中圈起來的節(jié)點(diǎn)就是輕節(jié)點(diǎn)。
a. 首先需要向某個(gè)全節(jié)點(diǎn)請(qǐng)求一個(gè)Merkle proof路徑，并請(qǐng)求路徑上需要的哈希值（圖中紅色H）
b. 然后計(jì)算需要證明的記錄的哈希值，然后通過給定的路徑一步一步計(jì)算哈希值，直到計(jì)算到根哈希值（root hash）
c. 因?yàn)檩p節(jié)點(diǎn)中是保存了block header的，而block header中保存的是root hash，因此只需要對(duì)比計(jì)算出來的root hash是否與保存的root hash一致即可。

Merkle tree的第二個(gè)用途：proof of non-membership，證明某個(gè)交易不在某個(gè)輕節(jié)點(diǎn)中。

使用sorted Merkle tree：對(duì)交易記錄tx的哈希值進(jìn)行排序，如果計(jì)算出待證明tx的哈希值不在這些值里面，而在某兩個(gè)tx哈希值之間，那么按照Merkle proof的路徑計(jì)算這兩個(gè)tx的哈希值，一直算到root hash，看是否被篡改，如果沒有被篡改，則證明待證明tx不在該輕節(jié)點(diǎn)中。

比特幣中沒有用到sorted Merkle tree，這是因?yàn)楸忍貛胖胁恍枰猵roof of non-membership。

3.哈希指針的問題

只要是該數(shù)據(jù)結(jié)構(gòu)不存在環(huán)，那么就可以使用哈希指針，如果存在環(huán)，就會(huì)存在循環(huán)依賴的問題。