區(qū)塊鏈經(jīng)歷了比特幣 1.0 時代，以太坊 2.0 時代，以及目前正在進(jìn)行的 3.0 時代，應(yīng)用領(lǐng)域正在蔓延到各行各業(yè)，主要底層技術(shù)包含：密碼學(xué)、共識算法、分布式存儲、P2P 網(wǎng)絡(luò)系統(tǒng)。

雖然比特幣至今還是有很大爭議，但是從純技術(shù)角度去看，比特幣是目前來說最成功的區(qū)塊鏈應(yīng)用，而其中最核心的就是它的底層交易系統(tǒng)，把支撐比特幣的底層交易系統(tǒng)原理弄清楚，是成為區(qū)塊鏈開發(fā)者最重要的一環(huán)。

近日，在雷鋒網(wǎng) AI 研習(xí)社公開課上，法國蒙彼利埃大學(xué)孫啟超與大家分享了支撐區(qū)塊鏈中的底層查詢系統(tǒng)相關(guān)知識。公開課回放視頻網(wǎng)址：http://www.mooc.ai/open/course/535?=aitechtalksunqichaosunqichao

孫啟超：法國蒙彼利埃大學(xué) MBA 在讀，CSDN 百萬博客專家，2015 年之前參與 360 技術(shù)團(tuán)隊的研究工作。目前負(fù)責(zé)公司公鏈項目的架構(gòu)。

分享主題：支撐區(qū)塊鏈中的底層查詢系統(tǒng)

分享提綱：

1. 介紹哈希算法的特點

2. 什么是默克爾樹

3. 默克爾書的特點

4. 區(qū)塊鏈的查詢系統(tǒng)原理

雷鋒網(wǎng) AI 研習(xí)社將其分享內(nèi)容整理如下：

我們本次分享的主題是：支撐區(qū)塊鏈中的底層查詢系統(tǒng)。

首先講一下基礎(chǔ)知識。實際上，目前互聯(lián)網(wǎng)傳輸，包括區(qū)塊鏈的數(shù)據(jù)傳輸，底層都依賴于密碼學(xué)的發(fā)展，哈希（Hash）算法則是現(xiàn)在最重要的密碼學(xué)之一。它的主要作用是將任意長度的二進(jìn)制明文映射為較短的、長度固定的二進(jìn)制串的算法。比如不管傳過來是多長的二進(jìn)制明文，經(jīng)過 MD5 運算后都會變成 64 位的二進(jìn)制編碼。比如「維多利亞的秘密」、「程序員的秘密」等明文，經(jīng)過 MD5 后，都得到 64 位的十六進(jìn)制的編碼，但通過二者的對比可以看到，雖然二者明文中「的密碼」有一定相似性，但是 MD5 后，二者的編碼完全沒有一點相似性。

如果從空間上分析，哈希算法就是從一個非常大的取值空間映射到一個非常小的取值空間。我們再看前面這句明文經(jīng) MD5 運算后得到的一長串編碼，我們幾乎推不出來「維多利亞的秘密」，這說明了哈希函數(shù)轉(zhuǎn)換后不可逆，意思是不可能通過逆操作以及哈希值還原出原始的值。

下面看哈希算法的幾個特點：

第一，正向快速。給定明文和哈希算法，在有限時間和有限資源內(nèi)能快速計算得到哈希值。

第二，逆向困難。給定哈希值，在有限時間內(nèi)很難逆推出明文，只能將所有可能性進(jìn)行窮舉，而并不能破解算法。

第三，輸入敏感。原始輸入信息發(fā)生任何變化，新的 Hash 值都會出現(xiàn)天翻地覆的變化。就比如剛剛提到的「維多利亞的秘密」、「程序員的秘密」，明文有些相似性，但是 MD5 后的編碼沒有任何相似的地方。

第四，沖突避免。比如說 666 和 667 經(jīng)過 MD5 后的值就一定不一樣，即不存在明文不一樣而哈希值一樣的情況。這個特點也是唯一性，后面的查找也要用到這個特點，因為只有哈希值是唯一的，我們才能用它去定位，否則就沒有意義。

常見的哈希算法包括 MD5 和 SHA 系列，目前 MD5 和 SHA1 已經(jīng)被破解，在比特幣中，如果使用 MD5 去生成數(shù)學(xué)難題，幾乎就沒有什么難度了——一般推薦至少使用 SHA2-256 算法，該算法要比 MD5 高很多個數(shù)量級別。

接下來我們講它區(qū)塊鏈中的運用，首先講一下區(qū)塊鏈的概念，因為我們主要講底層技術(shù)。區(qū)塊鏈可以簡單理解成數(shù)據(jù)的存儲空間，一個區(qū)塊就是一個存儲空間，可以存圖片、文字、視頻等。而多個存儲空間連在一起，就是一個區(qū)塊鏈。如果是公鏈，則只有一條鏈。

鏈通過我們剛剛講到的哈希值來連接。一個區(qū)塊鏈有兩個哈希值，一個是本身存儲的數(shù)據(jù)轉(zhuǎn)換成的二進(jìn)制編碼，用這些編碼進(jìn)行哈希運算，得到一個哈希值；另一個代表上一個區(qū)塊的哈希值，上一個區(qū)塊鏈自身也有一個哈希值，會傳到該區(qū)塊中。而該區(qū)塊的哈希值也會傳達(dá)到它的下一個區(qū)塊中——大家可以將這個過程想象成一個鐵環(huán)再套下一個鐵環(huán)。不過，該區(qū)塊的一個鐵環(huán)是由上一個區(qū)塊牽引著的，而它本身的另一個鐵環(huán)則牽引著下一個區(qū)塊的鐵環(huán)。

對數(shù)據(jù)結(jié)構(gòu)的理解有一個鏈表，其實跟區(qū)塊鏈很相似。假如有一個區(qū)塊的哈希值在所有區(qū)塊中都找不到，就說明這個區(qū)塊鏈?zhǔn)羌俚?，或者說不被大家所認(rèn)可。因此在區(qū)塊鏈中，首先要去查區(qū)塊鏈交易的內(nèi)容，比如說記賬，存一個圖片進(jìn)去，那這個圖片是否被認(rèn)可呢？——如果哈希值在公鏈上找不到的話，就是不被認(rèn)可的區(qū)塊鏈。

介紹一下默克爾樹這個概念。區(qū)塊鏈的很多名詞其實都翻譯得非常好，基本上通過名詞就能知道要表達(dá)什么意思。這里的「樹」由一個根節(jié)點，一組中間節(jié)點和一組葉子節(jié)點組成。根節(jié)點表示是最終的那個節(jié)點，且只有一個。葉子節(jié)點可以有很多，但是不能再擴(kuò)散也就是沒有子節(jié)點了。如圖：

它的運轉(zhuǎn)過程是：

第一步把最底層的 Data0...Data3 這四條數(shù)據(jù)，每一條都單獨進(jìn)行哈希值，得出 4 個 64 位的哈希值作為葉子節(jié)點。

第二步把相鄰的兩個葉子節(jié)點的哈希值拿出來兩兩結(jié)合，再進(jìn)行哈希，如 B0+B1 兩個 64 位的值，哈希后得出一個 64 位的 B4。

第三步遞歸執(zhí)行這樣的哈希操作，直到最終 Hash 出一個根節(jié)點，就結(jié)束了。

這就是默克爾樹的運行原理，在圖中展現(xiàn)是：B0+B1 哈希得出 B4，B2+B3 哈希得出 B5，B4+B5 哈希得出 Root 根節(jié)點。如果節(jié)點為奇數(shù)也沒關(guān)系，只要在后面再加一條鏈，能通過默克爾路徑出來就可以了。比如說這里得到 B4+B5 的哈希值，再與該哈希值合并就可以的，最后遞歸出來的只有一個。

由于每個節(jié)點上的內(nèi)容都是哈希值，默克爾樹所以也叫「哈希樹」。

我們接下來看一下它的特性（跟哈希算法的特性有很大關(guān)系，因為默克爾樹基于哈希算法）：

第一特性：任意一個葉子節(jié)點的細(xì)微變動，都會導(dǎo)致 Root 節(jié)點發(fā)生翻天覆地的變化。我們回去看上圖，假如 B1 了，那 B4 就一定會變，自然而然地，最后的 Root 節(jié)點也會變。這一特性可以用來判斷兩個加密后的數(shù)據(jù)是否完全一樣。

第二特性：快速定位修改，如果 Data1 中數(shù)據(jù)被修改，會影響到 B1，B4 和 Root，當(dāng)發(fā)現(xiàn)根節(jié)點 Root 的哈希值發(fā)生變化，可以沿著 Root - > B4 - > B1 最多通過 O(logn) 時間即可快速定位到實際發(fā)生改變的數(shù)據(jù)塊 Data1，而不需要比對 B5 那邊的哈希值。

第三特性：零知識證明，它指的是證明者能夠在不向驗證者提供任何有用的信息的情況下，使驗證者相信某個論斷是正確的。有的公司就專門利用了這一個特性做了一個叫做數(shù)字認(rèn)證的項目，它是指在不向任何人提供信息的情況下，我們就能證明擁有這項權(quán)利。當(dāng)我們只愿意給出 Data0...Data3 這四條數(shù)據(jù)中的 Data0 時，怎么證明我們擁有 Data0...Data3 這些數(shù)據(jù)呢？步驟如下：

第一，創(chuàng)建一棵如圖所示的默克爾樹，然后對外公布 B1，B5，Root；

第二，這時 Data0 的擁有者通過哈希生成 B0，然后根據(jù)公布的 B1 生成 B4，再根據(jù)公布的 B5 生成 Root，如果最后生成的 Root 哈希值能和公布的 Root 一樣，則可以證明擁有這些數(shù)據(jù)，而且不需要公布 Data1，Data2，Data3 這些真實數(shù)據(jù)。

今天的重點就是講區(qū)域鏈的查詢系統(tǒng)。首先介紹「默克爾路徑」這個概念，上圖中 Root - > B4 - > B1 就是一條路徑，表示從根節(jié)點到葉子節(jié)點所經(jīng)過的節(jié)點組成的路徑。

在比特幣中，默克爾樹被用作歸納一個區(qū)塊中的所有交易，同時生成整個交易集合的數(shù)字簽名，且提供了一種校驗區(qū)塊是否存在某交易的高效途徑，就是默克爾路徑。一條條路徑就相當(dāng)于一筆筆交易。之前我們所說的交易慢，實際上是因為出區(qū)塊的時間慢，1MB 存不了多少數(shù)據(jù)，隨著人數(shù)越來越多，排隊就要很長時間了。

而生成默克爾樹，需要遞歸地對各個子節(jié)點進(jìn)行哈希運算，將新生成的哈希節(jié)點插入到默克爾樹中，直到只剩一個哈希節(jié)點，該節(jié)點就是默克爾樹的根節(jié)點。

這就是整個查詢的原理，時間復(fù)雜度為 logN，依據(jù)的是默克爾路徑。我們可以通過下圖直觀地看到怎樣高效地查找交易：

?

路徑其實也是一個大小，路徑數(shù)代表哈希值的數(shù)量，路徑數(shù)是 4 表示這條路徑存了 4 個哈希值，每個哈希值是 32 Byte。而區(qū)塊大小 = 交易數(shù) * 250 Byte；路徑大小 = 路徑數(shù) * 32 Byte。因此，好的算法對高效查找交易非常重要。

最后講一下區(qū)塊鏈中最簡單的確認(rèn)支付的形式——簡單支付驗證（SPV）。

比特幣和以太坊都通過默克爾樹來進(jìn)行查詢、確認(rèn)。有了默克爾樹，一個節(jié)點能夠僅下載區(qū)塊頭 80 字節(jié)，包含上一區(qū)塊頭的哈希值、時間戳、挖礦難度值、工作量證明隨機(jī)數(shù)以及該區(qū)塊交易的默克爾樹的根哈希值。

從 2008 年誕生起，區(qū)塊鏈交易加起來有 160 多個 G 的內(nèi)存。使用簡單支付驗證（SPV），我們只需要通過從一個滿節(jié)點回溯一條小的默克爾路徑就能認(rèn)證一筆交易的存在，而不需要下載整個區(qū)塊、存儲上百 G 的內(nèi)容。

以上就是本期嘉賓的全部分享內(nèi)容。更多公開課視頻請到雷鋒網(wǎng)(公眾號：雷鋒網(wǎng)) AI 研習(xí)社社區(qū)觀看。關(guān)注微信公眾號：AI 研習(xí)社（okweiwu），可獲取最新公開課直播時間預(yù)告。

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。