Merkle樹(shù)是一類(lèi)基于哈希值的二叉樹(shù)或多叉樹(shù)，其葉子節(jié)點(diǎn)上的值通常為數(shù)據(jù)塊的哈希值，而非葉子節(jié)點(diǎn)上的值，是將該節(jié)點(diǎn)的所有子節(jié)點(diǎn)的組合結(jié)果的哈希值。Merkle樹(shù)是區(qū)塊鏈的重要數(shù)據(jù)結(jié)構(gòu)，其作用是快速歸納和校驗(yàn)區(qū)塊數(shù)據(jù)的存在性和完整性。在處理完整性驗(yàn)證的應(yīng)用場(chǎng)景中，特別是在分布式環(huán)境下進(jìn)行這樣的驗(yàn)證時(shí)， Merkle樹(shù)會(huì)大大減少數(shù)據(jù)的傳輸量以及計(jì)算的復(fù)雜度，在安全性上僅僅依賴(lài)于哈希函數(shù)的安全性。Merkle樹(shù)通常包含區(qū)塊體的底層（交易）數(shù)據(jù)庫(kù)，區(qū)塊頭的根哈希值（MerkleRoot）以及所有沿底層區(qū)塊數(shù)據(jù)到根哈希的分支，運(yùn)算過(guò)程一般是將區(qū)塊體的數(shù)據(jù)進(jìn)行分組哈希，并將生成的新哈希值插入 Merkle樹(shù)中，如此遞歸直到只剩最后一個(gè)根哈希值并記為區(qū)塊頭的 Merkle根。

（一）、Merkle樹(shù)特點(diǎn)

Merkle樹(shù)特點(diǎn)如下：

① Merkle樹(shù)是一種樹(shù)，大多數(shù)是二叉樹(shù)，也可以多叉樹(shù)，無(wú)論是幾叉樹(shù)，它都具有樹(shù)結(jié)構(gòu)的所有特點(diǎn)；

② Merkle樹(shù)的葉子節(jié)點(diǎn)的值是數(shù)據(jù)集合的單元數(shù)據(jù)或者單元數(shù)據(jù)哈希值；

③非葉子節(jié)點(diǎn)的值是根據(jù)它下面所有的葉子節(jié)點(diǎn)值然后按照哈希算法計(jì)算而得出的。

區(qū)塊鏈中的 Merkle樹(shù)用于存儲(chǔ)交易信息，每個(gè)交易兩兩配對(duì)，構(gòu)成 Merkle樹(shù)的葉子節(jié)點(diǎn)，進(jìn)而生成整個(gè)Merkle樹(shù)。Merkle樹(shù)有諸多優(yōu)點(diǎn)，首先是極大地提高了區(qū)塊鏈的運(yùn)行效率和可擴(kuò)展性，使得區(qū)塊頭只需包含根哈希值而不必封裝所有底層數(shù)據(jù)；其次是 Merkle樹(shù)可支持“簡(jiǎn)化支付驗(yàn)證”協(xié)議，即在不運(yùn)行完整區(qū)塊鏈網(wǎng)絡(luò)節(jié)點(diǎn)的情況下，也能夠?qū)Γń灰祝?shù)據(jù)進(jìn)行檢驗(yàn)，使得用戶(hù)可以通過(guò)從區(qū)塊頭得到的 Merkle樹(shù)根和別的用戶(hù)所提供的中間哈希值列表去驗(yàn)證某個(gè)交易是否包含在區(qū)塊中。利用一個(gè)節(jié)點(diǎn)出發(fā)到達(dá) Merkle樹(shù)的根所經(jīng)過(guò)的路徑上存儲(chǔ)的哈希值，可以構(gòu)造一個(gè) Merkle證明，驗(yàn)證范圍可以是單個(gè)哈希值這樣的少量數(shù)據(jù)，也可以是驗(yàn)證可能擴(kuò)至無(wú)限規(guī)模的大量數(shù)據(jù)。提供中間哈希值的用戶(hù)并不需要是可信的，因?yàn)閭卧靺^(qū)塊頭的代價(jià)很高，而中間哈希值如果偽造的話(huà)會(huì)導(dǎo)致驗(yàn)證失敗。

（二）、Merkle哈希樹(shù)

如圖所示為一個(gè) Merkle哈希樹(shù)，節(jié)點(diǎn)A的值必須通過(guò)節(jié)點(diǎn)C、D上的值計(jì)算而得到。葉子節(jié)點(diǎn)C、D分別存儲(chǔ)數(shù)據(jù)塊001和02的哈希值，而非葉子節(jié)點(diǎn)A存儲(chǔ)的是其子節(jié)點(diǎn)C、D的組合的哈希值，這類(lèi)非葉子節(jié)點(diǎn)的哈希值被稱(chēng)作路徑哈希值，而葉子節(jié)點(diǎn)的哈希值是實(shí)際數(shù)據(jù)的哈希值。

若C、D、E和F存儲(chǔ)了一組數(shù)據(jù)塊的哈希值，當(dāng)把這些數(shù)據(jù)從張三傳輸?shù)嚼钏暮鬄轵?yàn)證傳輸?shù)嚼钏牡臄?shù)據(jù)完整性，只需要驗(yàn)證張三和李四上所構(gòu)造的 Merkle樹(shù)的根節(jié)點(diǎn)值是否一致即可。如果一致，表示數(shù)據(jù)在傳輸過(guò)程中沒(méi)有發(fā)生改變。假如在傳輸過(guò)程中E對(duì)應(yīng)的數(shù)據(jù)被人篡改，通過(guò) Merkle樹(shù)很容易定位找到（因?yàn)榇藭r(shí)，根節(jié)點(diǎn)、B和E所對(duì)應(yīng)的哈希值都發(fā)生了變化），定位的時(shí)間復(fù)雜度為（log（n））。比特幣的輕量級(jí)節(jié)點(diǎn)所采用的SPV驗(yàn)證就是利用 Merkle樹(shù)這一優(yōu)點(diǎn)。

為驗(yàn)證數(shù)據(jù)塊003所對(duì)應(yīng)的交易包含在區(qū)塊中，除了 Merkle樹(shù)根外，用戶(hù)只需要節(jié)點(diǎn)A對(duì)應(yīng)的哈希值Hash（C，D）以及節(jié)點(diǎn)F所對(duì)應(yīng)的哈希值Hash（004）。除了數(shù)據(jù)塊003外，他并不需要其他數(shù)據(jù)塊所對(duì)應(yīng)的交易明細(xì)。通過(guò)3次哈希計(jì)算，用戶(hù)就能夠確認(rèn)數(shù)據(jù)塊003所對(duì)應(yīng)的交易是否包含在區(qū)塊中。實(shí)際上，若區(qū)塊包含圖中所對(duì)應(yīng)的 Merkle樹(shù)，且區(qū)塊所包含的4個(gè)交易的容量均達(dá)到最大值，下載整個(gè)區(qū)塊可能需要超過(guò)400000個(gè)字節(jié)，而下載兩個(gè)哈希值加上區(qū)塊頭部?jī)H需要120個(gè)字節(jié)，可以減少很大的傳輸量。

（三）、非對(duì)稱(chēng)加密

非對(duì)稱(chēng)加密是現(xiàn)代密碼學(xué)歷史上一項(xiàng)偉大的發(fā)明可以很好地解決對(duì)稱(chēng)加密中提前分發(fā)密鑰的問(wèn)題。顧名思義，非對(duì)稱(chēng)加密算法中，加密密鑰和解密密鑰是不同的，分別稱(chēng)為公鑰（public key和私鑰（private key）。私鑰一般需要通過(guò)隨機(jī)數(shù)算法生成，公鑰可以根據(jù)私鑰生成。公開(kāi)密鑰是對(duì)外公開(kāi)的，而私有密鑰是保密的，其他人不能通過(guò)公鑰推算出對(duì)應(yīng)的私鑰。每一個(gè)公開(kāi)密鑰都有其相對(duì)應(yīng)的私有密鑰，如果我們使用公開(kāi)密鑰對(duì)信息進(jìn)行了加密，那么則必須有對(duì)應(yīng)的私有密鑰才能對(duì)加密后的信息進(jìn)行解密；而如果是用私有密鑰加密信息，則只有對(duì)應(yīng)的公開(kāi)密鑰才可以進(jìn)行解密。在區(qū)塊鏈中，非對(duì)稱(chēng)加密主要用于信息加密、數(shù)字簽名等場(chǎng)景。

非對(duì)稱(chēng)加密算法的優(yōu)點(diǎn)是公、私鑰分開(kāi)，不安全通道也可使用。其缺點(diǎn)是處理速度（特別是生成密鑰和解密過(guò)程）往往比較慢，一般比稱(chēng)加解密算法慢2~3個(gè)數(shù)量級(jí)；同時(shí)加密強(qiáng)度也往往不如對(duì)稱(chēng)加密算法。非對(duì)稱(chēng)加密算法的安全性往往需要基于數(shù)學(xué)問(wèn)題來(lái)保障，目前主要有基于大數(shù)質(zhì)因子分解、離散對(duì)數(shù)、橢圓曲線等經(jīng)典數(shù)學(xué)難題進(jìn)行保護(hù)。代表算法包括：RSA， Diffie－Hellman－密鑰交換、 ElGamal、橢圓曲線（Elliptic Curve Crytosystems，ec）、sm2等系列算法。

①RA：經(jīng)典的公鑰算法，1978年由 Ron Rivest、 Adi Shamir、 Leonard Adleman共同提出，三人于2002年因此獲得圖靈獎(jiǎng)。算法利用了對(duì)大數(shù)進(jìn)行質(zhì)因子分解困難的特性，但目前還沒(méi)有數(shù)學(xué)證明兩者難度等價(jià)，或許存在未知算法在不進(jìn)行大數(shù)分解的前提下解密。

② Diffie－Hellman－密鑰交換：基于離散對(duì)數(shù)無(wú)法快速求解，可以在不安全的通道上，雙方協(xié)商一個(gè)公共密鑰。

③ EIGamal：由 Taher EIGamal設(shè)計(jì)，利用了模運(yùn)算下求離散對(duì)數(shù)困難的特性，被應(yīng)用在PGP等安全工具中。

④橢圓曲線（Elliptic Curve Cryptography，ECC）：現(xiàn)代備受關(guān)注的算法系列，基于對(duì)橢圓曲線上特定點(diǎn)進(jìn)行特殊乘法逆運(yùn)算難以計(jì)算的特性。最早在1985年 Neal由 Koblitz和 Victor Miller分別獨(dú)立提出。ECC系列算法一般被認(rèn)為具備較高的安全性，但加解密計(jì)算過(guò)程往往比較費(fèi)時(shí)。

⑤m2（ShangMi2）：國(guó)家商用密碼算法，由國(guó)家密碼管理局于2010年12月17日發(fā)布，同樣基于橢圓曲線算法，加密強(qiáng)度優(yōu)于RSA系列算法。

非對(duì)稱(chēng)加密算法一般適用于簽名場(chǎng)景或密鑰協(xié)商，但不適于大量數(shù)據(jù)的加解密。目前普遍認(rèn)為RSA類(lèi)算法可能在不遠(yuǎn)的將來(lái)被破解，一般推薦可采用安全強(qiáng)度更高的橢圓曲線系列算法。

（四）、時(shí)間戳

時(shí)間戳是指從格林尼治時(shí)間1970年01月01日00時(shí)00分00秒（北京時(shí)間1970年01月01日08時(shí)00分00秒）起至現(xiàn)在的總秒數(shù)，通常是一個(gè)字符序列，唯一地標(biāo)識(shí)某一刻的時(shí)間。在比特幣系統(tǒng)中，獲得記賬權(quán)的節(jié)點(diǎn)在鏈接區(qū)塊時(shí)需要在區(qū)塊頭中加蓋時(shí)間戳，用于記錄當(dāng)前區(qū)塊數(shù)據(jù)的寫(xiě)入時(shí)間。每一個(gè)隨后區(qū)塊中的時(shí)間戳都會(huì)對(duì)前一個(gè)時(shí)間戳增強(qiáng)工作量證明，形成一個(gè)時(shí)間遞增的鏈條。時(shí)間戳技術(shù)本身并沒(méi)有多復(fù)雜，但在區(qū)塊鏈技術(shù)中應(yīng)用時(shí)間戳卻是一個(gè)重大創(chuàng)新，時(shí)間戳為未來(lái)基于區(qū)塊鏈的互聯(lián)網(wǎng)和大數(shù)據(jù)增加了一一個(gè)時(shí)間維度，使得數(shù)據(jù)更容易追溯，重現(xiàn)歷史也成為可能。同時(shí)，時(shí)間戳可以作為存在性證明（ Proof of Existence）的重要參數(shù)，它能夠證實(shí)特定數(shù)據(jù)必然在某特定時(shí)刻是的確存在的，這保證了區(qū)塊鏈數(shù)據(jù)庫(kù)是不可篡改和不可偽造的，這也為區(qū)塊鏈技術(shù)應(yīng)用于公證、知識(shí)產(chǎn)權(quán)注冊(cè)等時(shí)間敏感領(lǐng)域提供了可能。