梅克爾樹
梅克爾樹
默克爾樹（又叫哈希樹）是一種二叉樹，由一個根節(jié)點、一組中間節(jié)點和一組葉節(jié)點組成。最下面的葉節(jié)點包含存儲數(shù)據(jù)或其哈希值，每個中間節(jié)點是它的兩個孩子節(jié)點內(nèi)容的哈希值，根節(jié)點也是由它的兩個子節(jié)點內(nèi)容的哈希值組成。
進(jìn)一步的，默克爾樹可以推廣到多叉樹的情形。
默克爾樹的特點是，底層數(shù)據(jù)的任何變動，都會傳遞到其父親節(jié)點，一直到樹根。
默克爾樹的典型應(yīng)用場景包括：
- 快速比較大量數(shù)據(jù)：當(dāng)兩個默克爾樹根相同時，則意味著所代表的數(shù)據(jù)必然相同。
- 快速定位修改：例如上例中，如果 D1 中數(shù)據(jù)被修改，會影響到 N1，N4 和 Root。因此，沿著 Root --> N4 --> N1，可以快速定位到發(fā)生改變的 D1；
- 零知識證明：例如如何證明某個數(shù)據(jù)（D0……D3）中包括給定內(nèi)容 D0，很簡單，構(gòu)造一個默克爾樹，公布 N0，N1，N4，Root，D0 擁有者可以很容易檢測 D0 存在，但不知道其它內(nèi)容。
Neo中的梅克爾樹
我們看一下Neo的代碼，看看如此神奇的的數(shù)據(jù)結(jié)構(gòu)，到底怎么實現(xiàn)的。
代碼在/neo/Cryptography/MerkleTree.cs中
構(gòu)造函數(shù)
image.png
- 構(gòu)造函數(shù)的參數(shù)傳入了一個hash數(shù)組，這些數(shù)組，就是葉子節(jié)點。
- 調(diào)用的build函數(shù)，返回root，說明build函數(shù)是用來把數(shù)組變成一顆樹的函數(shù)。
- for循環(huán)計算樹的高度。
build樹
樹的節(jié)點
節(jié)點
- 每個節(jié)點都有一個hash值
- 有三個指針，父節(jié)點指針，左孩子指針，右孩子指針。
建立樹的算法
建立樹
對于圖中的標(biāo)記，解釋一下。
- 參數(shù)就是葉子節(jié)點。
- 計算父節(jié)點的數(shù)目，創(chuàng)建父節(jié)點數(shù)組，父節(jié)點的數(shù)目為
(leaves.Length + 1) / 2 - 通過一個循環(huán)，給父節(jié)點賦值。
- 如果葉子節(jié)點是奇數(shù)，則最后一個父節(jié)點的左右孩子是一樣的。
- 根據(jù)左右孩子的hash值，產(chǎn)生父節(jié)點。
- 當(dāng)前生成的parent，又變成leaves，遞歸調(diào)用build方法。
退出的時候，就是
leaves.Length == 1的時候，當(dāng)做root的返回。
Neo如何使用梅克爾樹
計算根節(jié)點
計算根節(jié)點
根節(jié)點會被包含在block中，block就是區(qū)塊鏈的塊，后面看到這塊代碼再仔細(xì)分析。
從樹變成數(shù)組
從樹變成數(shù)組
使用的地方
在
MerkleBlockPayload里面，保存的是這個數(shù)組，我想可能是這樣可以節(jié)省一點空間吧。后面繼續(xù)研究具體存在這里干嘛。
裁剪樹
裁剪樹
BitArray和BloomFilter相關(guān)，這里就是根據(jù)這個array來表示存在的節(jié)點，然后把梅克爾樹修剪一下，具體什么時候才會用到這個呢，后面跑起來再看看，現(xiàn)在還不知道。
總結(jié)
我們看到Neo實現(xiàn)的梅克爾樹還是很簡練的，而且有一些使用場景，需要進(jìn)一步研究。
