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

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