《區(qū)塊鏈技術(shù)及應(yīng)用》區(qū)塊鏈數(shù)據(jù)存儲(chǔ)

區(qū)塊鏈數(shù)據(jù)存儲(chǔ)目錄/CONTENTS4.1哈希指針與區(qū)塊鏈4.2梅克爾數(shù)簡(jiǎn)介4.3區(qū)塊鏈存儲(chǔ)案例分析4.4編程案例本章小結(jié)思考題4.1哈希指針與區(qū)塊鏈4.1.1哈希指針哈希指針（HashPointer）是一個(gè)指向數(shù)據(jù)存儲(chǔ)位置和數(shù)據(jù)的哈希值的指針，即指向某個(gè)區(qū)塊的地址，只不過這個(gè)地址進(jìn)行了哈希轉(zhuǎn)換，用哈希值來表示。通過哈希指針，我們可以快速定位到某個(gè)區(qū)塊，且能按一定的順序進(jìn)行排列。哈希指針可以保證交易的不可篡改性，一旦區(qū)塊形成后，如果有人想要篡改某個(gè)區(qū)塊中的信息，那么后面一個(gè)區(qū)塊的哈希值匹配就會(huì)出現(xiàn)錯(cuò)誤。哈希指針的存在，使得任何篡改行為牽一發(fā)而動(dòng)全身，讓作惡者無法篡改區(qū)塊中的信息，從而保證數(shù)據(jù)的完整性。DataPointertoDataHashofDataHashPointer4.1.2區(qū)塊鏈如下圖所示，我們通過哈希指針構(gòu)建了一個(gè)區(qū)塊鏈。在普通鏈表中，每個(gè)區(qū)塊既有數(shù)據(jù)，也有指向上一個(gè)區(qū)塊的指針，而在區(qū)塊鏈中，上一個(gè)區(qū)塊的指針被替換成哈希指針。因此，每個(gè)區(qū)塊不僅能告訴我們上一個(gè)區(qū)塊的值在哪里，還包含了該值的摘要（原文經(jīng)過哈希函數(shù)形成），從而能夠驗(yàn)證這個(gè)值是否被改變。區(qū)塊鏈的一個(gè)應(yīng)用就是“防止篡改日志”，這意味著我們要構(gòu)建一個(gè)存儲(chǔ)大量數(shù)據(jù)的日志數(shù)據(jù)結(jié)構(gòu)，以便能夠?qū)?shù)據(jù)附加到日志末尾。只要有人篡改日志前面的數(shù)據(jù)，我們就可以監(jiān)測(cè)到。4.2.梅克爾樹簡(jiǎn)介4.2.1二叉樹二叉樹就是每個(gè)節(jié)點(diǎn)至多有兩棵子樹的樹。并且，二叉樹有左右之分，即其次序不能任意顛倒。二叉樹在數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)上有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種，而常用的存儲(chǔ)結(jié)構(gòu)是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，包括區(qū)塊鏈中使用的也是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。下圖所示的二叉鏈表存儲(chǔ)結(jié)構(gòu)中，二叉樹中的每一個(gè)節(jié)點(diǎn)用鏈表的一個(gè)鏈節(jié)點(diǎn)來存儲(chǔ)。二叉鏈表每個(gè)節(jié)點(diǎn)一般包括數(shù)據(jù)域和左右指針，這與梅克爾樹的結(jié)構(gòu)完全一樣。4.2.2梅克爾樹梅克爾樹（MerkleTree）又叫作哈希樹，是另一個(gè)我們可以用哈希指針建立的二叉樹樹型數(shù)據(jù)結(jié)構(gòu)，以其發(fā)明者梅克爾的名字命名。梅克爾樹是一種典型的二叉樹結(jié)構(gòu)，由一個(gè)根節(jié)點(diǎn)、一組中間節(jié)點(diǎn)和一組葉子節(jié)點(diǎn)組成。每個(gè)葉子節(jié)點(diǎn)包含一個(gè)存有數(shù)據(jù)的區(qū)塊，然后把所有葉子節(jié)點(diǎn)兩兩分組，每一組建立一個(gè)有兩個(gè)哈希指針的數(shù)據(jù)結(jié)構(gòu)，每個(gè)指針指向一個(gè)葉子節(jié)點(diǎn)，也就形成了一個(gè)父節(jié)點(diǎn)，依此類推，直到得到一個(gè)單一的節(jié)點(diǎn)，也就是根節(jié)點(diǎn)。4.2.2梅克爾樹梅克爾樹的典型應(yīng)用場(chǎng)景：1．比對(duì)或驗(yàn)證處理：特別是在分布式環(huán)境下進(jìn)行比對(duì)或驗(yàn)證時(shí)，梅克爾樹會(huì)大大減少數(shù)據(jù)的傳輸量以及計(jì)算的復(fù)雜度。2.快速定位修改：如下圖所示，如果N0對(duì)應(yīng)的數(shù)據(jù)被修改，會(huì)直接影響到N1、N4和N6。3.確保不可偽造和無重復(fù)交易：在比特幣的設(shè)計(jì)中，梅克爾樹存在于每個(gè)區(qū)塊中，它被應(yīng)用于交易的存儲(chǔ)上。每筆交易都會(huì)生成一個(gè)哈希值，然后不同的哈希值向上繼續(xù)做哈希運(yùn)算，最終生成唯一的根，并把這個(gè)梅克爾樹根作為數(shù)據(jù)區(qū)塊的區(qū)塊頭。4.3區(qū)塊鏈存儲(chǔ)案例分析4.3.1100%準(zhǔn)備金證明最簡(jiǎn)單的證明方法就是公布所有用戶數(shù)據(jù)。該方法很直接，但易偽造。如果想要保證邏輯完備性，需要證明以下兩點(diǎn)。（1）沒有偽造，包括沒有偽造用戶和沒有偽造用戶余額。（2）沒有遺漏，包括沒有直接遺漏用戶和間接遺漏用戶。要完成100%準(zhǔn)備金的證明，可以用到梅克爾樹。這個(gè)證明的主要過程是構(gòu)建梅克爾樹，當(dāng)構(gòu)建完該樹且根節(jié)點(diǎn)的余額與公布的儲(chǔ)蓄余額相同時(shí)，即可100%儲(chǔ)備。100%準(zhǔn)備金證明沒有偽造沒有偽造用戶沒有偽造用戶余額沒有遺漏沒有直接遺漏用戶沒有間接遺漏用戶4.3.2分布式存儲(chǔ)分布式存儲(chǔ)系統(tǒng)是大量普通計(jì)算機(jī)或服務(wù)器通過Internet互聯(lián)，對(duì)外作為一個(gè)整體提供存儲(chǔ)服務(wù)的系統(tǒng)。它的特點(diǎn)是可擴(kuò)展、成本低、性能高、易用。分布式存儲(chǔ)涉及的設(shè)計(jì)主要來自兩個(gè)領(lǐng)域：分布式系統(tǒng)和數(shù)據(jù)庫。分布式存儲(chǔ)系統(tǒng)分為以下4類。分布式存儲(chǔ)系統(tǒng)分布式文件系統(tǒng)分布式鍵值系統(tǒng)分布式表系統(tǒng)分布式數(shù)據(jù)庫系統(tǒng)1．分布式文件系統(tǒng)：以對(duì)象的形式組織，對(duì)象之間不存在關(guān)聯(lián)，這種數(shù)據(jù)一般稱為二進(jìn)制大對(duì)象數(shù)據(jù)。2．分布式鍵值系統(tǒng)：分布式鍵值系統(tǒng)用于存儲(chǔ)關(guān)系簡(jiǎn)單的半結(jié)構(gòu)化數(shù)據(jù)。3．分布式表系統(tǒng)：用于存儲(chǔ)具有更復(fù)雜關(guān)系的半結(jié)構(gòu)化數(shù)據(jù)。4．分布式數(shù)據(jù)庫系統(tǒng)：具有靈活的體系結(jié)構(gòu)，系統(tǒng)經(jīng)濟(jì)，可靠性高，可用性好，在一定條件下響應(yīng)速度快，可擴(kuò)展性好，易于集成現(xiàn)有系統(tǒng)，也易于擴(kuò)充。4.4編程案例4.4.1實(shí)現(xiàn)哈希列表哈希函數(shù)經(jīng)常被用于數(shù)據(jù)完整性校驗(yàn)，最簡(jiǎn)單的方法是對(duì)整個(gè)數(shù)據(jù)做哈希運(yùn)算，得到固定長(zhǎng)度的哈希值，然后把得到的哈希值公布在網(wǎng)上。這樣用戶下載數(shù)據(jù)之后，對(duì)數(shù)據(jù)再次進(jìn)行哈希運(yùn)算，將運(yùn)算結(jié)果和網(wǎng)上公布的哈希值進(jìn)行比較，如果兩個(gè)哈希值相等，說明下載的數(shù)據(jù)沒有被損壞。實(shí)際操作中，點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)在傳輸數(shù)據(jù)的時(shí)候其實(shí)都是把比較大的一個(gè)文件切成小的數(shù)據(jù)塊。在下載文件之前，通常需要先下載一個(gè)種子文件，這個(gè)種子文件里包含著每個(gè)塊的索引信息和哈希驗(yàn)證碼，因此也被稱為索引文件。根哈希確定這個(gè)哈希列表本身是否正確。使用哈希列表進(jìn)行數(shù)據(jù)完整性校驗(yàn)的原理如下圖所示。4.4.2實(shí)現(xiàn)梅克爾樹梅克爾樹也可以實(shí)現(xiàn)數(shù)據(jù)的完整性校驗(yàn)。相對(duì)于哈希列表，梅克爾樹一個(gè)明顯的優(yōu)點(diǎn)是可以單獨(dú)拿出一個(gè)分支（作為一個(gè)小樹）來對(duì)部分?jǐn)?shù)據(jù)進(jìn)行校驗(yàn)，這為很多使用場(chǎng)合帶來了哈希列表所不能比擬的方便和高效。如下圖所示，使用梅克爾樹對(duì)數(shù)據(jù)進(jìn)行高效檢驗(yàn)，假設(shè)8號(hào)文件在下載過程中出現(xiàn)了錯(cuò)誤，如果采用哈希列表，那么必須要對(duì)比16個(gè)分片文件的哈希值，才能確定究竟是哪個(gè)分片文件出現(xiàn)了錯(cuò)誤，而使用梅克爾樹，需要檢驗(yàn)的哈希值只有8個(gè)。4.4.2實(shí)現(xiàn)梅克爾樹下面以9個(gè)分片文件為例，介紹如何生成一棵梅克爾樹。（1）假如最底層有9個(gè)數(shù)據(jù)塊。（2）第五層：對(duì)9個(gè)數(shù)據(jù)塊進(jìn)行哈希運(yùn)算，Node0i=hash(Data0i)，i=1,2,…,9。（3）第四層：相鄰兩個(gè)哈希塊串聯(lián)，然后進(jìn)行哈希運(yùn)算，Node1i=hash(Node0j+Node0(j+1))，i=1,2,3,4，j=1,2,…,8；對(duì)于j=9，Node15=hash(Node09)。（4）第三層：重復(fù)步驟（3）。（5）第二層：重復(fù)步驟（3）。（6）第一層：重復(fù)步驟（3），生成梅克爾樹根。本章小結(jié)本章基于區(qū)塊鏈