上海企業(yè)建設(shè)網(wǎng)站成人職業(yè)技術(shù)培訓(xùn)學(xué)校
文章目錄
- 比特幣中的數(shù)據(jù)結(jié)構(gòu)
- 1. 區(qū)塊鏈(block chain)
- 2. 默克爾樹(Merkle tree)
- 3.哈希指針的問題
比特幣中的數(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 bodyMerkle 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)依賴的問題。