研發人員一定要心中有「樹」

• 2019 年 12 月 31 日
• 筆記

【這是一猿小講的第 79 篇原創分享】

作為高雞攻城獅一定要心中有樹，因為這個的確能提升底層認知。

希望每人都能夠做到心中有樹，面對面試高頻問題，方能有的放矢。

01. 區塊鏈中的樹

體會一下：區塊鏈上交易的篡改，會給區塊帶來什麼影響？

如圖是區塊鏈中的一個區塊，裡面存放了一批已經完成的交易資訊，為了方便處理，區塊的交易資訊組織成 Merkle 樹的形式，區塊的塊頭存儲了前一區塊的哈希值。

假設葉子節點上的交易 3 發生篡改，那麼交易 3 對應的哈希值就會變動，變動就會逐級向上傳遞，直到相應的父節點，最終導致區塊的的根哈希發生變化，進而會導致整個區塊的哈希發生變化。

一句話：交易的篡改，導致整個區塊的哈希變化。

由於交易 3 的篡改，導致交易 3 對應的整個區塊的哈希發生變動，進而會引起下一個區塊上記錄的上一個區塊的哈希就對不上了，那麼是不是要考慮篡改後面的區塊呀？但是區塊後面的後面的區塊也要篡改，子子孫孫無窮匱也。

一句話：交易的篡改，牽一髮要動全身，需要篡改整個鏈條才可以生效，難度可想而知（區塊鏈不可篡改的特性）。

感受一下：如何驗證區塊上的交易是否存在？

假如需要驗證區塊上是否真實存在交易 3，該怎麼去驗證？其實我們只需要「哈希 2」和「哈希 01」就可以證明啦，驗證步驟如下。

Step 1：獲取交易 3 的哈希值，哈希 3 = Hash(交易 3)； Step 2：通過哈希 2 和哈希 3，得到父節點的哈希值：哈希 23 = Hash(哈希 2 + 哈希 3)； Step 3：通過哈希 01 和哈希 23 的哈希值，得到根節點的哈希值：Root = Hash(哈希 01 + 哈希 23)； Step 4：將上一步得到的根哈希值 Root 與區塊頭中默克爾根哈希值對比，如果相同，則證明該區塊中存在交易 3，否則說明不存在。

一句話：通過引入默克爾樹，比特幣採用少量計算及比較，就可以完成交易的驗證。

思考一下：如何回收磁碟空間？

隨著時間的推移，鏈越來越長，區塊鏈的數據也逐日增長，數據量級越來越大，對存儲肯定要求也越來越高。其實一旦最新交易已經被足夠多的區塊覆蓋，這之前的支付交易就可以被丟棄，以便節省磁碟空間。

如上圖所示，交易被哈希進默克爾樹，只有根節點被納入到區塊的哈希值。那麼老的區塊可通過剪除樹枝的方式被壓縮，樹枝內部的哈希不需要被保存，進而可以節省磁碟空間而又不破壞區塊的哈希值（堪稱設計完美）。

其實比特幣的以上種種設計，背後都離不開默克爾樹，那默克爾樹到底是什麼呢？

02. 掌握默克爾樹

學習任何一門技術，都不要忘記谷哥和度娘，在Google輸入「Merkle Tree」搜之，映入眼帘的就是維基百科的解釋。

哈希樹（hash tree；Merkle tree），在密碼學及電腦科學中是一種樹形數據結構，每個葉節點均以數據塊的哈希作為標籤，而除了葉節點以外的節點則以其子節點標籤的加密哈希作為標籤 。哈希樹能夠高效、安全地驗證大型數據結構的內容，是哈希鏈的推廣形式。 哈希樹的概念由瑞夫·墨克於 1979 年申請專利，故亦稱墨克樹（Merkle tree）。

通過搜索我們明白兩點。

1. 原來 Merkle Tree 也叫做 Hash Tree（哈希樹），因為 Merkle Tree 每個葉節點均以數據塊的哈希作為標籤，而除了葉節點以外的節點則以其子節點標籤的加密哈希作為標籤 ，所以又叫做哈希樹； 2. Merkle Tree 在維基百科被翻譯為墨克樹，而在中本聰的論文中又被翻譯成了默克爾樹。其實到這一步，名字叫什麼已經無所啦。

通過這個圖我們明白兩點。

1. 哈希樹的頂部為頂部哈希（top hash），亦稱根哈希（root hash）或主哈希（master hash）； 2. Hash 0-0 和 Hash 0-1 分別是數據塊 L1 和 L2 的哈希值，Hash 0 是將 Hash 0-0 和 Hash 0-1 連接後所取得的哈希值。

主要應用場景。

1. Merkle 樹典型的應用場景是點對點網路下載。 先從朋友或者網站分享等方式獲取可信的 Merkle 樹的頂部哈希；拿到頂部哈希後，就可以通過 P2P 網路中的非受信來源下載整棵 Merkle 樹；下載得到 Merkle 樹後，就可以根據可信的頂部哈希對其進行校驗，驗證數據是否完整、是否遭受破壞； 2. Merkle 樹可以被用來快速比較大量的數據，因為當兩個 Merkle 樹根相同時，則意味著所代表的數據必然相同； 3. 開篇中談到的區塊鏈場景。

03. 閑言碎語

默克爾樹就分享到這兒，希望大家對默克爾樹有個初步認識吧。

文中圖片，大都來自於比特幣的創始人中本聰的論文，中本聰的論文建議有時間讀一讀，畢竟是顛覆之作。

區塊鏈 2.0 的代表技術以太坊 Ethereum（不是比特幣的一個克隆，而是完完全全獨立的一種設計和實現）建議有時間也了解了解。

比特幣：https://github.com/bitcoin 中本聰論文： https://bitcoin.org/files/bitcoin-paper/bitcoin_zh_cn.pdf 以太坊：https://github.com/ethereum 以太坊白皮書： https://github.com/ethereum/wiki/wiki/White-Paper

今天的分享原計劃是從 Java 源碼用到的樹–> MySQL 底層用到的樹 –> 區塊鏈中的樹，這樣一條線來分享我心中的樹，但是年底啦，總結、規劃等事情太多了，時間不夠用啊，希望後面陸陸續續給大家補上