區(qū)塊鏈學(xué)習(xí)三——比特幣的數(shù)據(jù)結(jié)構(gòu)

文章內(nèi)容來(lái)源于北京大學(xué)肖臻老師《區(qū)塊鏈技術(shù)與應(yīng)用》公開課

一、哈希指針（hash pointers）

普通的指針存儲(chǔ)的是結(jié)構(gòu)體在內(nèi)存中的起始地址
哈希指針除了存儲(chǔ)起始地址還存儲(chǔ)該結(jié)構(gòu)體的哈希值
根據(jù)哈希值可以檢測(cè)出該結(jié)構(gòu)體是否被篡改。

二、區(qū)塊鏈

由一個(gè)一個(gè)區(qū)塊組成的鏈表
Q：區(qū)塊鏈?zhǔn)褂玫逆湵砼c普通鏈表的區(qū)別
A：區(qū)塊鏈?zhǔn)褂玫逆湵硎褂霉Ｖ羔槾媪似胀ǖ闹羔?br>

系統(tǒng)中產(chǎn)生的第一個(gè)區(qū)塊：創(chuàng)世紀(jì)區(qū)塊 genesis block
系統(tǒng)中最近產(chǎn)生的區(qū)塊：most recent
每個(gè)區(qū)塊都有一個(gè)哈希指針
取哈希值是將整個(gè)區(qū)塊的內(nèi)容合在一起取得哈希（包括哈希指針）
只需記住最后一個(gè)哈希值即可檢測(cè)前面得區(qū)塊是否被篡改（多米諾骨牌、牽一發(fā)而動(dòng)全身）
因此節(jié)點(diǎn)只需保存最近的節(jié)點(diǎn)，需要前面得區(qū)塊可以問(wèn)別人要，通過(guò)計(jì)算哈希值即可檢測(cè)前面的區(qū)塊是否是正確的。

三、Merkle tree

根節(jié)點(diǎn)也可取哈希值叫做根哈希
知道根哈?？梢詸z測(cè)出整棵樹節(jié)點(diǎn)是否被篡改（效率更高）每個(gè)節(jié)點(diǎn)的改變會(huì)導(dǎo)致根節(jié)點(diǎn)發(fā)生改變
最下面的子節(jié)點(diǎn)相當(dāng)于是交易

這個(gè)數(shù)跟二叉樹很像
最上面深顏色的方塊代表區(qū)塊，tx即最下面的一行代表交易，H()哈希值
每個(gè)區(qū)塊都包含塊頭block header （有根哈希值、塊頭沒(méi)有具體的交易數(shù)據(jù)的）和塊身block body（塊身含有交易數(shù)據(jù)）
區(qū)塊包含的所有交易組成的merkle tree的根哈希值存在區(qū)塊的塊頭

1.Merkle tree的作用：Merkle Proof

全節(jié)點(diǎn)：保存整個(gè)區(qū)塊鏈的內(nèi)容，有塊頭block header 和塊身block body（塊身含有交易數(shù)據(jù)）
輕節(jié)點(diǎn)：只保存塊頭block header
Q（Merkle Proof）：如何向輕節(jié)點(diǎn)證明交易已經(jīng)寫入?yún)^(qū)塊鏈中 （輕節(jié)點(diǎn)沒(méi)有保存交易列表，只有根哈希值block header）上圖黃色的方塊包含在Merkle tree。
A：輕節(jié)點(diǎn)向全節(jié)點(diǎn)發(fā)出請(qǐng)求。全節(jié)點(diǎn)把圖中紅色的H() 哈希值發(fā)給輕節(jié)點(diǎn)。輕節(jié)點(diǎn)在本地計(jì)算標(biāo)綠的哈希值 H()，由綠色的哈希值和紅色的哈希值可以計(jì)算出上一層節(jié)點(diǎn)的綠色的哈希值；再由剛才計(jì)算出綠色的哈希值與該層紅色的哈希值；計(jì)算出再上一層的綠色哈希值，再由綠色的哈希值與紅色的哈希值即可計(jì)算出根節(jié)點(diǎn)的哈希值，與輕節(jié)點(diǎn)的哈希值比較即可得到是否包含交易信息。
只驗(yàn)證交易數(shù)據(jù)所在的到根節(jié)點(diǎn)的一條分支即可，根哈希值不變，即交易都不會(huì)被篡改。人為制造哈希碰撞可以篡改 難度太大了collision resistence

Merkle Proof（Proof of membership、Proof of inclusion）:向輕節(jié)點(diǎn)證明交易已經(jīng)寫入?yún)^(qū)塊鏈中。有n條交易的話時(shí)間復(fù)雜度為log(n)

2.Proof of non-membership

Q：如何證明Proof of non-membership
A：直接將一棵樹發(fā)給輕節(jié)點(diǎn)，把整個(gè)交易都發(fā)給輕節(jié)點(diǎn)。時(shí)間復(fù)雜度為O(n)
優(yōu)化：把交易的哈希值按照順序進(jìn)行排序，其他步驟跟merkle proof 過(guò)程類似。時(shí)間復(fù)雜度為log(n)。代價(jià)是要先排序。sorted merkle tree。
比特幣中不要求排序 不要求Proof of non-membership

四、總結(jié)

區(qū)塊鏈與Merkle tree都需要使用哈希指針來(lái)構(gòu)造。沒(méi)有環(huán)的鏈表可以使用哈希指針，有環(huán)的不可使用哈希指針。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-476435.html

到了這里，關(guān)于區(qū)塊鏈學(xué)習(xí)三——比特幣的數(shù)據(jù)結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！