區(qū)塊鏈經(jīng)歷了比特幣 1.0 時(shí)代，以太坊 2.0 時(shí)代，以及目前正在進(jìn)行的 3.0 時(shí)代，應(yīng)用領(lǐng)域正在蔓延到各行各業(yè)，主要底層技術(shù)包含：密碼學(xué)、共識(shí)算法、分布式存儲(chǔ)、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)知識(shí)。公開課回放視頻網(wǎng)址：http://www.mooc.ai/open/course/535?=aitechtalksunqichaosunqichao

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

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

分享提綱：

1. 介紹哈希算法的特點(diǎn)

2. 什么是默克爾樹

3. 默克爾書的特點(diǎn)

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

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

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

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

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

下面看哈希算法的幾個(gè)特點(diǎn)：

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

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

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

第四，沖突避免。比如說 666 和 667 經(jīng)過 MD5 后的值就一定不一樣，即不存在明文不一樣而哈希值一樣的情況。這個(gè)特點(diǎn)也是唯一性，后面的查找也要用到這個(gè)特點(diǎn)，因?yàn)橹挥泄Ｖ凳俏ㄒ坏?，我們才能用它去定位，否則就沒有意義。

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

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

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

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

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

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

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

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

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

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

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

我們接下來看一下它的特性（跟哈希算法的特性有很大關(guān)系，因?yàn)槟藸枠浠诠Ｋ惴ǎ?/p>

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

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

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

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

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

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

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

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

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

?

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

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

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

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

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

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