0
區塊鏈經歷了比特幣 1.0 時代，以太坊 2.0 時代，以及目前正在進行的 3.0 時代，應用領域正在蔓延到各行各業，主要底層技術包含：密碼學、共識算法、分布式存儲、P2P 網絡系統。
雖然比特幣至今還是有很大爭議，但是從純技術角度去看，比特幣是目前來說最成功的區塊鏈應用，而其中最核心的就是它的底層交易系統，把支撐比特幣的底層交易系統原理弄清楚，是成為區塊鏈開發者最重要的一環。
近日，在雷鋒網 AI 研習社公開課上，法國蒙彼利埃大學孫啟超與大家分享了支撐區塊鏈中的底層查詢系統相關知識。公開課回放視頻網址：http://www.mooc.ai/open/course/535?=aitechtalksunqichaosunqichao
孫啟超：法國蒙彼利埃大學 MBA 在讀，CSDN 百萬博客專家，2015 年之前參與 360 技術團隊的研究工作。目前負責公司公鏈項目的架構。
分享主題：支撐區塊鏈中的底層查詢系統
分享提綱：
1. 介紹哈希算法的特點
2. 什么是默克爾樹
3. 默克爾書的特點
4. 區塊鏈的查詢系統原理
雷鋒網 AI 研習社將其分享內容整理如下：
我們本次分享的主題是：支撐區塊鏈中的底層查詢系統。
首先講一下基礎知識。實際上，目前互聯網傳輸，包括區塊鏈的數據傳輸，底層都依賴于密碼學的發展，哈希（Hash）算法則是現在最重要的密碼學之一。它的主要作用是將任意長度的二進制明文映射為較短的、長度固定的二進制串的算法。比如不管傳過來是多長的二進制明文，經過 MD5 運算后都會變成 64 位的二進制編碼。比如「維多利亞的秘密」、「程序員的秘密」等明文，經過 MD5 后，都得到 64 位的十六進制的編碼，但通過二者的對比可以看到，雖然二者明文中「的密碼」有一定相似性，但是 MD5 后，二者的編碼完全沒有一點相似性。
如果從空間上分析，哈希算法就是從一個非常大的取值空間映射到一個非常小的取值空間。我們再看前面這句明文經 MD5 運算后得到的一長串編碼，我們幾乎推不出來「維多利亞的秘密」，這說明了哈希函數轉換后不可逆，意思是不可能通過逆操作以及哈希值還原出原始的值。
下面看哈希算法的幾個特點：
第一，正向快速。給定明文和哈希算法，在有限時間和有限資源內能快速計算得到哈希值。
第二，逆向困難。給定哈希值，在有限時間內很難逆推出明文，只能將所有可能性進行窮舉，而并不能破解算法。
第三，輸入敏感。原始輸入信息發生任何變化，新的 Hash 值都會出現天翻地覆的變化。就比如剛剛提到的「維多利亞的秘密」、「程序員的秘密」，明文有些相似性，但是 MD5 后的編碼沒有任何相似的地方。
第四，沖突避免。比如說 666 和 667 經過 MD5 后的值就一定不一樣，即不存在明文不一樣而哈希值一樣的情況。這個特點也是唯一性，后面的查找也要用到這個特點，因為只有哈希值是唯一的，我們才能用它去定位，否則就沒有意義。
常見的哈希算法包括 MD5 和 SHA 系列，目前 MD5 和 SHA1 已經被破解，在比特幣中，如果使用 MD5 去生成數學難題，幾乎就沒有什么難度了——一般推薦至少使用 SHA2-256 算法，該算法要比 MD5 高很多個數量級別。
接下來我們講它區塊鏈中的運用，首先講一下區塊鏈的概念，因為我們主要講底層技術。區塊鏈可以簡單理解成數據的存儲空間，一個區塊就是一個存儲空間，可以存圖片、文字、視頻等。而多個存儲空間連在一起，就是一個區塊鏈。如果是公鏈，則只有一條鏈。
鏈通過我們剛剛講到的哈希值來連接。一個區塊鏈有兩個哈希值，一個是本身存儲的數據轉換成的二進制編碼，用這些編碼進行哈希運算，得到一個哈希值；另一個代表上一個區塊的哈希值，上一個區塊鏈自身也有一個哈希值，會傳到該區塊中。而該區塊的哈希值也會傳達到它的下一個區塊中——大家可以將這個過程想象成一個鐵環再套下一個鐵環。不過，該區塊的一個鐵環是由上一個區塊牽引著的，而它本身的另一個鐵環則牽引著下一個區塊的鐵環。
對數據結構的理解有一個鏈表，其實跟區塊鏈很相似。假如有一個區塊的哈希值在所有區塊中都找不到，就說明這個區塊鏈是假的，或者說不被大家所認可。因此在區塊鏈中，首先要去查區塊鏈交易的內容，比如說記賬，存一個圖片進去，那這個圖片是否被認可呢？——如果哈希值在公鏈上找不到的話，就是不被認可的區塊鏈。
介紹一下默克爾樹這個概念。區塊鏈的很多名詞其實都翻譯得非常好，基本上通過名詞就能知道要表達什么意思。這里的「樹」由一個根節點，一組中間節點和一組葉子節點組成。根節點表示是最終的那個節點，且只有一個。葉子節點可以有很多，但是不能再擴散也就是沒有子節點了。如圖：
它的運轉過程是：
第一步把最底層的 Data0...Data3 這四條數據，每一條都單獨進行哈希值，得出 4 個 64 位的哈希值作為葉子節點。
第二步把相鄰的兩個葉子節點的哈希值拿出來兩兩結合，再進行哈希，如 B0+B1 兩個 64 位的值，哈希后得出一個 64 位的 B4。
第三步遞歸執行這樣的哈希操作，直到最終 Hash 出一個根節點，就結束了。
這就是默克爾樹的運行原理，在圖中展現是：B0+B1 哈希得出 B4，B2+B3 哈希得出 B5，B4+B5 哈希得出 Root 根節點。如果節點為奇數也沒關系，只要在后面再加一條鏈，能通過默克爾路徑出來就可以了。比如說這里得到 B4+B5 的哈希值，再與該哈希值合并就可以的，最后遞歸出來的只有一個。
由于每個節點上的內容都是哈希值，默克爾樹所以也叫「哈希樹」。
我們接下來看一下它的特性（跟哈希算法的特性有很大關系，因為默克爾樹基于哈希算法）：
第一特性：任意一個葉子節點的細微變動，都會導致 Root 節點發生翻天覆地的變化。我們回去看上圖，假如 B1 了，那 B4 就一定會變，自然而然地，最后的 Root 節點也會變。這一特性可以用來判斷兩個加密后的數據是否完全一樣。
第二特性：快速定位修改，如果 Data1 中數據被修改，會影響到 B1，B4 和 Root，當發現根節點 Root 的哈希值發生變化，可以沿著 Root - > B4 - > B1 最多通過 O(logn) 時間即可快速定位到實際發生改變的數據塊 Data1，而不需要比對 B5 那邊的哈希值。
第三特性：零知識證明，它指的是證明者能夠在不向驗證者提供任何有用的信息的情況下，使驗證者相信某個論斷是正確的。有的公司就專門利用了這一個特性做了一個叫做數字認證的項目，它是指在不向任何人提供信息的情況下，我們就能證明擁有這項權利。當我們只愿意給出 Data0...Data3 這四條數據中的 Data0 時，怎么證明我們擁有 Data0...Data3 這些數據呢？步驟如下：
第一，創建一棵如圖所示的默克爾樹，然后對外公布 B1，B5，Root；
第二，這時 Data0 的擁有者通過哈希生成 B0，然后根據公布的 B1 生成 B4，再根據公布的 B5 生成 Root，如果最后生成的 Root 哈希值能和公布的 Root 一樣，則可以證明擁有這些數據，而且不需要公布 Data1，Data2，Data3 這些真實數據。
今天的重點就是講區域鏈的查詢系統。首先介紹「默克爾路徑」這個概念，上圖中 Root - > B4 - > B1 就是一條路徑，表示從根節點到葉子節點所經過的節點組成的路徑。
在比特幣中，默克爾樹被用作歸納一個區塊中的所有交易，同時生成整個交易集合的數字簽名，且提供了一種校驗區塊是否存在某交易的高效途徑，就是默克爾路徑。一條條路徑就相當于一筆筆交易。之前我們所說的交易慢，實際上是因為出區塊的時間慢，1MB 存不了多少數據，隨著人數越來越多，排隊就要很長時間了。
而生成默克爾樹，需要遞歸地對各個子節點進行哈希運算，將新生成的哈希節點插入到默克爾樹中，直到只剩一個哈希節點，該節點就是默克爾樹的根節點。
這就是整個查詢的原理，時間復雜度為 logN，依據的是默克爾路徑。我們可以通過下圖直觀地看到怎樣高效地查找交易：
?
路徑其實也是一個大小，路徑數代表哈希值的數量，路徑數是 4 表示這條路徑存了 4 個哈希值，每個哈希值是 32 Byte。而區塊大小 = 交易數 * 250 Byte；路徑大小 = 路徑數 * 32 Byte。因此，好的算法對高效查找交易非常重要。
最后講一下區塊鏈中最簡單的確認支付的形式——簡單支付驗證（SPV）。
比特幣和以太坊都通過默克爾樹來進行查詢、確認。有了默克爾樹，一個節點能夠僅下載區塊頭 80 字節，包含上一區塊頭的哈希值、時間戳、挖礦難度值、工作量證明隨機數以及該區塊交易的默克爾樹的根哈希值。
從 2008 年誕生起，區塊鏈交易加起來有 160 多個 G 的內存。使用簡單支付驗證（SPV），我們只需要通過從一個滿節點回溯一條小的默克爾路徑就能認證一筆交易的存在，而不需要下載整個區塊、存儲上百 G 的內容。
以上就是本期嘉賓的全部分享內容。更多公開課視頻請到雷鋒網(公眾號：雷鋒網) AI 研習社社區觀看。關注微信公眾號：AI 研習社（okweiwu），可獲取最新公開課直播時間預告。
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
