你可以在 Github 上擷取最新的源代碼（C#）
目錄
- 簡介
- 本文中的術語
- Merkle Tree被應用在哪裡?
- 數字貨币
- 全球供應鍊
- 保健行業
- 資本市場
- Git 和 Mercurial
- 為什麼使用Merkle Tree?
- 一緻性檢驗
- 資料校驗
- 資料同步
- 證明的重要性
- Merkle Tree實踐
- 資料校驗（審計證明）是如何實作的?
- 一緻性檢驗（一緻性證明）是如何實作的?
- 一緻性證明示範
- 重建舊的根哈希
- 一緻性證明的注意事項
- 一緻性證明的正常算法
- 示例
- 改變葉節點數
- 審計證明測試
- 一緻性證明測試
- 內建Merkle Tree
- MerkleHash 類
- MerkleNode 類
- MerkleTree 類
- 屬性和字段
- Contract 方法
- 構造器
- 追加葉節點
- 在現有的樹上添加樹
- 根據樹的葉節點構造樹
- AuditProof（審計證明）
- ConsistencyProof（一緻性證明）
- VerifyAudit（審計證明校驗）
- 将審計證明作為哈希對進行校驗
- VerifyConsistency（一緻性證明校驗）
- FindLeaf（在葉節點清單中尋找某一個葉節點）
- 根據自定義的節點要求來建立MerkleNode
- 其他
- MerkleProofHash 類
- 單元測試
- 一緻性證明的單元測試
- 單調哈希和區塊鍊
- 結論
- 參考文獻
在1979年，Ralph Merkle取得了哈希樹即現在廣為人知的MerkleTree的專利權（改專利在2002年過期）。其概括的描述為：“該發明包含了一種提供資訊驗證的數字簽名的方法，該方法利用單向的認證樹對密碼數字進行校驗。”
可能你更喜歡維基百科中的定義：“在密碼學和計算機科學當中，哈希樹或Merkle tree是一種特殊的樹結構，其每個非葉節點通過其子節點的标記或者值（子節點為葉節點）的哈希值來進行标注。哈希樹為大型的資料結構提供了高效安全的驗證手段。哈希樹也可以了解為哈希清單和哈希連結清單的泛化産物”
除了對外部資料的引用外，我盡量保持了本文中術語的一緻性。
記錄(Record)——一個用于描述對應Merkle tree中葉節點哈希後對應的資料包。當你閱讀Merkle tree相關的内容的時候，根據上下文的不同，它也可能被稱為“交易”或“憑證”。
區塊(Block)——從比特币中引用的概念，我将用“區塊”指代永久存儲在Merkle tree葉節點中的記錄集。引用來源：“交易資料被永久存儲在稱為區塊的檔案當中”。它可以被了解為城市檔案或者股票交易賬本中獨立的幾頁。換言之：“記錄被永久存儲在稱為區塊的檔案當中。”
Log——Merkle tree的别稱，log是從哈希的記錄中構造得到的哈希樹。除了用來表示哈希樹之外，log還有一個特殊的屬性：新的記錄總會被作為新的葉節點追加在樹最後的葉節點上。除此之外，對于交易系統來說（比如說貨币），一旦某個記錄被“logged”，它就不能再被更改了——相反地，對交易的更改将在log為表示為新的記錄條目，為交易提供完整的審計線索。與之相反的，在分布式存儲中（像NoSQL資料庫）可以更改記錄，同時會觸發樹中收到影響的記錄的哈希值的更新。在這種場景下，Merkle tree可以快速高效地識别已經更改的記錄以便同步分布式系統中的節點。
Merkle Tree被應用在哪裡？
Merkle tree（以及其變體）被應用于比特币，以太坊，Apache Cassandra以及其他用于提供以下服務的系統當中：
- 一緻性驗證
- 資料同步（這一部分在本文中不做講述，因為資料同步本身的内容就可以再寫一篇文章）
這些術語都是什麼意思呢？我後面會一一講解。
利用了Merkle tree的區塊鍊技術，現今受歡迎的程度不亞于比特币。需要跟蹤資料并且保證資料一緻性的企業也開始看到區塊鍊技術對這一過程的幫助。
拿執行個體來說，IBM和Maersk正在合作使用區塊鍊來管理全球的供應鍊：
“科技巨頭IBM和領先的運輸物流公司Maersk宣布了一個潛在的開創性合作——使用區塊鍊技術來數字化全球範圍的交易資訊和貨運管理商、海運承運商、參與供應鍊的港口和海關部門組成的托運網絡。
據IBM和Maersk所說，如果這項技術被廣泛應用，可以改變全球的跨境供應鍊并為行業節省數十億美元。”
“驅動Google健康技術的AI子公司DeepMind Health計劃使用基于比特币的新技術來賦予醫院、國民保健系統（NHS）以至患者實時監控個人身體情況的能力。它也被稱為可驗證的資料審計，這項計劃将會将患者的行為以加密可驗證的方式記錄下來據此建立每個人的特殊的數字記錄 ‘賬本’ ”。這意味着對資料的任何修改、通路行為都将是可見的。
雖然比特币技術最初就被當做一個可以被自由擷取的，實用的技術來替代傳統分布式共享網絡中各方資産記錄和交易資訊的儲存和記錄手段，但是2015年許多金融科技初創公司都将重點放在了隻有通過預先授權的參與者才能通路的私有區塊鍊開發上。GreySpark認為這與金融初創公司關鍵的商業訴求——為銀行和其他買方公司設計、提供一個廣泛、通用的區塊鍊解決方案實作交易前到交易後整個生命周期中分布式賬本技術的正常運轉。
顯然（盡管我沒有找到關于此事的權威論據）Git 和 Mercurial 使用了特殊處理過的Merkle trees來進行版本管理。
為什麼使用Merkle Tree？
使用像Merkle tree一樣的哈希樹
- 顯著減少了要達到證明資料完整性的置信度所需的資料量。
- 顯著減少了維護一緻性、資料校驗以及資料同步所需的網絡I/O資料包大小。
- 将資料校驗和資料本身分離——Merkle tree可以存在本地，也可以存放與受信任的權威機構上，也可以存在分布式系統上（你隻需要維護屬于你的樹即可。）将“我可以證明這個資料是合法的”和資料本身解耦意味着你可以為Merkle Tree和資料存儲提供适當的分離（包括備援）持久性。
是以本節标題問題的答案可以分為以下三點：
- Merkle tree提供了一種證明資料完整性/有效性的手段。
- Merkle tree可以利用很少的記憶體/磁盤空間實作簡單高效的計算。
- Merkle tree的論證和管理隻需要很少量的網絡傳輸流量。
也被稱為“一緻性證明”，你可以用它驗證兩份日志的版本是否一緻：
- 最新的版本包含了之前所有版本的資訊。
- 日志中的記錄順序是一緻的。
- 所有新的記錄都是跟在舊版本記錄的後面的。
如果你證明了日志的一緻性，那麼意味着：
- 日志中沒有憑證記錄被復原或者插入。
- 日志中沒有憑證被修改。
- 日志并沒有經過分支（breached）或者被fork
一緻性驗證是保證你的日志沒有損壞的關鍵手段。“監督員和審計員經常使用一緻性驗證來确認日志行為是否正常”
也被稱為“審計證明”，這是因為它可以讓你知道某一條具體的記錄是否存在于日志當中。與一緻性驗證一樣，維護日志的伺服器需要提供給用戶端特定的記錄存在于日志當中的證據。任何人都可以用一份日志來請求Merkle審計證明，校驗某條憑證記錄确實存在于日志當中，審計者會将這些類型的請求發送至日志以便它們檢驗TLS用戶端的證書。如果Merkle審計證明不能生成與Merkle Tree哈希值比對的根哈希值，則表示證書沒有在日志當中。（根節點包含什麼、審計證明是如何工作的這些内容會在稍後提到。）
向用戶端發送證明還有另外一個原因：它證明了伺服器本身并沒有創造正确的答案，它隻是為你和用戶端提供相關的證明，而僞造一個證明在計算上是不可能的。
Merkle tree在分布式資料存儲中的資料同步中發揮着重要的作用，這是因為它允許分布式系統中的每個節點可以迅速高效地識别已經更改的記錄而無需将發送所有的資料來進行比對。一旦樹中有特定的葉節點的變更被識别，我們隻需要将與該特定葉節點相關的資料上傳至網絡即可。注意Merkle tree并沒有直接提供解決沖突和将多個寫入者同步到相同記錄的機制。我們後面将示範這是如何實作的。
正如我開頭所說，因為資料同步本身的内容就很多，是以你必須要等下一篇文章。基本的資料同步（葉節點的更改）是很簡單的，但是動态環境下（存在葉節點的新增和删除）的資料同步就要複雜得多了，這是一個非平凡的問題。從技術上來講，你可能不希望為此使用Merkle tree，因為這裡資料的審計證明和一緻性證明通常是無用的，但我認為在分布式資料同步的場景下這仍然是值得的，因為有可能過程中有葉節點在沒有被徹底删除時就被标記為被删除。是以，Merkle tree的垃圾回收是資料同步中的一個問題，至少從我看這個問題的角度是這樣的。
一緻性證明和審計證明的重要性在于用戶端可以自己進行驗證。這意味着當用戶端請求伺服器來驗證一緻性或者某個訂單是否存在時，伺服器并不是簡單地回複答案“是”或“不是”，即使在“是”的情況下也會向你發送用戶端可以驗證的相關的證明。這些證明是基于伺服器對目前Merkle Tree的已有認知，而這是不能被某些希望用戶端相信它們的資料是有效的惡意使用者複制重複的。
在分布式系統中，每個節點都維護着它自己資料所在的Merkle tree，在同步的過程中，任何已經修改的節點都隐性地向其他的節點證明了自身的有效性。這也保證了任何節點不可能跳到網絡的層級上說“我有了一個新的記錄”或者“我有一個記錄來替換另一個的記錄”，因為每個節點缺乏必要的資訊來向其他節點證明自身。
Merkle一般來說就是一個二叉樹，它的每個葉節點的值為與它包含的記錄的哈希值。其他的内部節點的值為和它相連的兩個子節點中哈希值合并後再次哈希的結果。将子節點的哈希值合并後再次哈希建立節點的過程将不斷重複直至抵達頂部的根節點，也稱為“根哈希”。
上面的圖示模拟了子節點哈希值的級聯，我們在下面的文章中也将沿用這個模拟方式。
資料校驗（審計證明）是如何實作的？
如下圖所示，你是圖表中記錄“2”的擁有者。你也擁有來自權威機構提供的根哈希值，在我們的圖示中就是“01234567”。你詢問伺服器來證明你的記錄“2”确實在樹當中。伺服器傳回給你的将是下面黃色标記的哈希值“3”，“01”，“4567”。
利用這些傳回的資料（包含這些資料疊加所需的左右位置資訊），可以進行如下證明過程：
- 2 + 3 得到 23
- 01 + 23 得到 0123
- 0123 + 4567 得到 01234567
由于你已經擁有來自權威機構得到的根哈希值“01234567”，計算結果與其一直證明了記錄“2”确實存在于樹當中。此外，你擷取的證明來自的系統也證明了它的“權威性”，因為你可以用你的記錄“2”和它提供的哈希值重建出根哈希值“01234567”。任何假冒的驗證系統都不能為你提供以上的中間哈希值，因為你隻是向伺服器索要證明，并沒有提供給伺服器你的根哈希值——它不知道你的哈希值，隻有你自己知道你的哈希值。
為了完成以上校驗，需要提供給你的樹的資訊是很少的。相應的，要完成這個證明所需的資料包也非常小，這使得完成計算所需的資訊在網絡中的發送更為高效。
一緻性檢驗（一緻性證明）是如何實作的？
适用于樹的一緻性驗證隻限于新增節點，就像日志記錄一樣。它通常不會被用在葉節點需要更新的系統當中，因為這需要同步舊的根哈希值。新增的一緻性檢驗是可行的，下面我們将看到這個過程可能并不是我們想象的那樣。RFC 6962中的Section2.1.4提供了一些很好的框圖來說明一緻性證明是如何實作的，但是初看可能會比較費解，是以我在這裡盡力解釋地更清楚一些。使用他們的例子（但是還是用我上面的框圖以及其中的哈希值來示範），我們從包含三個記錄的樹開始：
最初的三個記錄“012”被建立：
第四個記錄“3”被添加之後，這個樹變成了：
兩個新的的記錄“45”被添加：
最後添加記錄“6”：
每次我們附加的子樹（記錄集）：
012
3
45
6
我們有：
- 所有的子樹附加在原始的樹上之後得到的新的根哈希
- 在附加子樹之前每個樹的原始哈希值
我們現在想要驗證盡管子樹附加在原始的樹上後整個樹的根哈希已經改變，但是之前的子樹的根哈希仍然可以被重建。這驗證了可信的權威伺服器上和用戶端所在的機器上記錄的順序以及與記錄相關的哈希值并沒有被改動。
每個子樹附加在主樹（master tree）上的時候，一緻性證明為新樹重建了哈希值（上面的最後一張圖）：
- 第一個樹的根哈希值為“012”。
- 當第二個子樹附加之後，根哈希值變為了“0123”。
- 當第三個子樹附加之後，根哈希值變為了”012345“
- 當最後一個子樹附加之後，根哈希值變為了”0123456“
第一顆樹的一緻性檢驗
我們怎樣檢驗第一個子樹呢？它的三個葉節點是否還在新的樹當中呢？
如上圖所示，我們需要節點"01"和"2"來重建第一棵樹的根哈希值"012"
第二棵樹的一緻性檢驗
當我們在第一棵樹上附加隻有一個葉節點"3"的第二棵樹之後，生成的樹具有四個葉節點，其根哈希值變為了"0123"。
第二棵樹的一緻性證明就是"0123"這個節點。
第三棵樹的一緻性證明
第三棵樹添加了兩個葉節點”45“，根哈希值變為了”012345“，我們獲得的一緻性證明如下圖所示：
另一種情況下的一緻性證明
假設我們依次單獨添加了葉節點”4“，"5"，"6"。當我們添加葉節點"4"的時候，我們會得到樹此時的根哈希值"01234"。在"4"，“5”，“6”被添加後我們的樹共有7個葉節點，要重建根哈希值“01234”需要的節點如下圖黃色标注所示：
以上執行個體中一緻性驗證的最後一個情況
這個情況與上述不同的地方在于需要三個節點的哈希值來重建原始的根哈希值。給定的樹一共有8個葉節點，當第七個葉節點“6”被添加後，此時的根哈希值為“0123456”。要重建它需要圖示中的黃色節點：
重建舊的根哈希值
最後的例子展示了一緻性證明如何在已有節點中重建出舊的根哈希值“0123456”。一緻性證明給予我們的節點順序如下：
0123
要重建出原始的根哈希值，我們需要按次序依次結合這些哈希值
45 + 6 = 456
0123 + 456 = 0123456
一緻性驗證中的注意事項
一緻性驗證并不是一個簡單的算法，我們在實作的時候需要遵循以下說明和規則：
- 一緻性驗證是基于計算來驗證樹中前m個葉節點的。當一個新的節點被添加至樹上之後，m為合并後的葉節點數。為了保證資料的所有哈希值的順序和内容沒有被更改，這一步是必不可少的。
- 不過當知道中間根哈希值代表的葉節點數量之後，這個算法可以快速地識别出具有以下特殊的節點：
- 比對的哈希值（如果葉節點的數量為2的n次方）
- 重建中間哈希值所需的子節點組合。
- 這意味着當一棵樹被添加至“日志”（已有的記錄）當中時，樹中節點的數将和根哈希值一起被儲存。
- 在一些情況下，一些特定的系統會單獨負責樹的添加，因為這個系統知道每次添加的樹的葉節點數，是以這個過程會變得很簡單。
- 在分布式系統當中，其他的參與者也可以在樹上新增節點（以及需要避免兩個及以上的參與者同時執行添加操作引入的複雜性），參與者在添加的時候需要聲明自己添加的葉節點的數量以便後續一緻性檢驗的進行。
- 為了減少所需的額外知識，完整的Merkle tree的維護者可以利用字典在需要被添加的樹的根節點與葉節點的數目之間建立映射。這也許是管理樹所需資訊的更安全的方式。
另一方面，由于這個算法從最左側的深度為log2(m)的節點開始，它的效率也是很高的，這種方法在避免從第一個節點開始計算很多葉子的哈希值的同時依然保證了生成的根哈希值的有效性和記錄、記錄次序的合法性。
你可以直接通讀RFC 6962的2.1.2節或者通過下面展示的圖表來了解一緻性證明的正常算法。
規則1：
尋找到樹最左側的節點來開始我們的一緻性證明。一般來說，它會是擷取舊的哈希值所需的葉節點之一。
在給定添加子樹之後主樹的葉節點數之後，我們需要n=log2(m)步來找到最多代表m個葉節點的内部節點索引。索引值從最樹左側的枝開始計數，如下圖所示。
例：
3個葉節點：log2(3) = 1.58(我們從節點“01”開始)
4個葉節點：log2(4) = 2(我們從節點“0123”開始)
6個葉節點：log2(6) = 2.58(我們從節點“0123”開始)
這一規則提供的索引值告訴了我們應當從哪個節點開始計算哈希值。從正确的地方開始的同時我們也知道了子樹将從這個節點開始疊加或這個節點是目前節點哈希和子樹節點哈希組合的位置（如果log2(m)存在餘數的話）。下面的圖示可以幫助你更好地了解（注意到計算得到的索引為3不代表着就有2^3=8個節點，如下圖所示，可能還有部分節點還沒有添加進來）：
除此之外，我們還要設定目前節點包含的子節點數（因為如上圖所示最後一片葉節點可能會丢失，是以我們必須計算他們的葉節點數量）
我們還要将初始的兄弟節點設定為規則一擷取得到的節點的兄弟節點（如果擷取得到的話）。
如果 m-k==0，我們将繼續執行規則3。
下面我們用上面的圖示和三個執行個體一起說明：
m=2：index=1（節點“01”），有兩個葉節點，m-k=0，是以我們繼續執行規則3。
m=4：index=2（節點“0123”），有四個葉節點，m-k=0，我們繼續執行規則3。
m=3：index=1（節點“01”），有兩個葉節點，m-k=1不等于0，是以我們繼續執行規則2。
規則2：
如果m-k == 兄弟節點（SN）的葉節點數，将兄弟節點的哈希值和舊的根哈希值串聯之後取代原先的根哈希值。
如果m-k < 兄弟節點的葉節點數，将兄弟節點設定為兄弟節點的左節點并重複規則2。
如果m-k > 兄弟節點的葉節點數，将兄弟節點的哈希值串聯并将k加上兄弟節點的葉節點數，設定兄弟節點為它的父節點的右節點。
按照這樣的規則我們總是可以從結果的哈希值中重建出舊的根哈希值。
分情況讨論示範：
m=3。k=2（節點“01”下的葉節點數），SN=“23”
SN的葉節點數為2，m-k<2，是以令SN = SN的左子節點“2”
此時SN的節點數為1（SN此時就是葉節點）
m-k= SN的葉節點數，此時可以看到我們可以用哈希值“01”和哈希值“2”重組得到根哈希值“012”。
m=4時由規則1處理。
m=5,k=4（節點“0123”下的葉節點數）。SN=“456”
SN的葉節點數為3
m-k<SN的葉節點數，是以SN=SN的左子節點“45”
SN的葉節點數變為2
m-k<SN的葉節點數，是以SN=SN的左子節點“4”
SN的葉節點數變為1（SN此時為葉節點）
m-k=SN的葉節點數，由此我們得知我們需要使用哈希值“0123”和“4”重建原先的根哈希值“01234”。
這是為從第一個節點開始的任意節點建構一緻性樹的很好的示例，我們不需要考慮舊的根節點是否作為節點被添加至新的主樹上。不過以上情況并不是典型的情況，下面再給出兩個示例作為補充：
m=6，k=4（節點“0123”下的葉節點數），SN=“456”
m-k=SN的葉節點數，由此我們得知我們需要使用哈希值“0123”和“45”重建原先的根哈希值“012345”。
m=7，k=4（節點“0123”下的葉節點數），SN=“456”
m-k=SN的葉節點數，由此我們得知我們需要使用哈希值“0123”和“456”重建原先的根哈希值“0123456”。
規則3：
為一緻性證明中的最後一個節點（不一定是葉節點）做審計證明（使用恰當的左兄弟節點或右兄弟節點）。
舉例來說，如果我們需要為樹的舊哈希值“01234”做審計證明（這是一個比上面更有趣的執行個體）：
在證明中我們擷取根哈希值設計的其他節點哈希值為圖示的“5”和“67”
這是因為我們需要“5”來獲得“45”，用“67”獲得“4567”。我覺得這是一個很酷的東西！
這個demo程式可以讓你體驗建立Merkle Tree和執行審計聲明、一緻性證明的過程。其中的圖形界面是通過嵌入內建
FlowSharp服務實作的。
注意：這個demo程式使用了1100端口上的websocket進行通信以在畫布（canvas）上建立連接配接和圖形。你可能在首次運作的時候看到以下授權提醒：
請點選“Allow access”。
你最多可以設定數量為16。為了友善起見，葉子的哈希值被模拟為0-F
你可以指定你想要進行審計證明的葉節點來進行審計證明（葉子的編号為0-15，10-15在圖示中被表示為A-F），當你點選“Show Me”的時候，下方會展示審計證明的過程，同時圖示中也會高亮參與審計證明的節點）
你可以通過數字來設定執行一緻性證明的葉節點數。參與計算的舊的根節點将會被黃色高亮顯示，完成一緻性證明所需的其他節點會顯示為紫色：
複選框“only to root node”隻是為了友善我讨論一緻性證明時建立截圖所用——在上面讨論的第二步審計證明中并沒有設計紫色節點。
接下來我們要內建Merkle Tree。它包括三個類：
- MerkleHash
- MerkleNode
- MerkleTree
讓我們一個一個來實作。
MerkleHash類
這個類提供了一些靜态的建立方法以及判定相等的測試方法，當然還有用位元組數組，字元串或者其他的兩個MerkleHash執行個體計算哈希值的方法。
namespace Clifton.Blockchain { public class MerkleHash { public byte[] Value { get; protected set; } protected MerkleHash() { } public static MerkleHash Create(byte[] buffer) { MerkleHash hash = new MerkleHash(); hash.ComputeHash(buffer); return hash; } public static MerkleHash Create(string buffer) { return Create(Encoding.UTF8.GetBytes(buffer)); } public static MerkleHash Create(MerkleHash left, MerkleHash right) { return Create(left.Value.Concat(right.Value).ToArray()); } public static bool operator ==(MerkleHash h1, MerkleHash h2) { return h1.Equals(h2); } public static bool operator !=(MerkleHash h1, MerkleHash h2) { return !h1.Equals(h2); } public override int GetHashCode() { return base.GetHashCode(); } public override bool Equals(object obj) { MerkleTree.Contract(() => obj is MerkleHash, "rvalue is not a MerkleHash"); return Equals((MerkleHash)obj); } public override string ToString() { return BitConverter.ToString(Value).Replace("-", ""); } public void ComputeHash(byte[] buffer) { SHA256 sha256 = SHA256.Create(); SetHash(sha256.ComputeHash(buffer)); } public void SetHash(byte[] hash) { MerkleTree.Contract(() => hash.Length == Constants.HASH_LENGTH, "Unexpected hash length."); Value = hash; } public bool Equals(byte[] hash) { return Value.SequenceEqual(hash); } public bool Equals(MerkleHash hash) { bool ret = false; if (((object)hash) != null) { ret = Value.SequenceEqual(hash.Value); } return ret; } } } MerkleNode類
這個類包含了一個節點的所有資訊——它的父節點、子節點以及它的哈希值。MerkleNode唯一有趣的特性是它實作了一個自底向上/自左向右的疊代器。
namespace Clifton.Blockchain { public class MerkleHash { public byte[] Value { get; protected set; } protected MerkleHash() { } public static MerkleHash Create(byte[] buffer) { MerkleHash hash = new MerkleHash(); hash.ComputeHash(buffer); return hash; } public static MerkleHash Create(string buffer) { return Create(Encoding.UTF8.GetBytes(buffer)); } public static MerkleHash Create(MerkleHash left, MerkleHash right) { return Create(left.Value.Concat(right.Value).ToArray()); } public static bool operator ==(MerkleHash h1, MerkleHash h2) { return h1.Equals(h2); } public static bool operator !=(MerkleHash h1, MerkleHash h2) { return !h1.Equals(h2); } public override int GetHashCode() { return base.GetHashCode(); } public override bool Equals(object obj) { MerkleTree.Contract(() => obj is MerkleHash, "rvalue is not a MerkleHash"); return Equals((MerkleHash)obj); } public override string ToString() { return BitConverter.ToString(Value).Replace("-", ""); } public void ComputeHash(byte[] buffer) { SHA256 sha256 = SHA256.Create(); SetHash(sha256.ComputeHash(buffer)); } public void SetHash(byte[] hash) { MerkleTree.Contract(() => hash.Length == Constants.HASH_LENGTH, "Unexpected hash length."); Value = hash; } public bool Equals(byte[] hash) { return Value.SequenceEqual(hash); } public bool Equals(MerkleHash hash) { bool ret = false; if (((object)hash) != null) { ret = Value.SequenceEqual(hash.Value); } return ret; } } } 這個類負責建構樹及執行一緻性證明和審計證明。我已經寫了一組靜态方法來實作審計證明和一緻性證明，是以你不需要再親自編寫驗證算法。我下面已經把類拆分為了組成它的各個元件。
namespace Clifton.Blockchain { public class MerkleTree { public MerkleNode RootNode { get; protected set; } protected List<MerkleNode> nodes; protected List<MerkleNode> leaves; 這是很簡單的。
Contract方法
public static void Contract(Func<bool> action, string msg) { if (!action()) { throw new MerkleException(msg); } } 我使用這個方法進行參數和狀态驗證。
public MerkleTree() { nodes = new List<MerkleNode>(); leaves = new List<MerkleNode>(); } 在已有的樹上添加樹
public MerkleNode AppendLeaf(MerkleNode node) { nodes.Add(node); leaves.Add(node); return node; } public void AppendLeaves(MerkleNode[] nodes) { nodes.ForEach(n => AppendLeaf(n)); } public MerkleNode AppendLeaf(MerkleHash hash) { var node = CreateNode(hash); nodes.Add(node); leaves.Add(node); return node; } public List<MerkleNode> AppendLeaves(MerkleHash[] hashes) { List<MerkleNode> nodes = new List<MerkleNode>(); hashes.ForEach(h => nodes.Add(AppendLeaf(h))); return nodes; } /// <summary> /// Builds the tree for leaves and returns the root node. /// </summary> public MerkleHash BuildTree() { // We do not call FixOddNumberLeaves because we want the ability to append // leaves and add additional trees without creating unecessary wasted space in the tree. Contract(() => leaves.Count > 0, "Cannot build a tree with no leaves."); BuildTree(leaves); return RootNode.Hash; } /// <summary> /// Recursively reduce the current list of n nodes to n/2 parents. /// </summary> /// <param name="nodes"></param> protected void BuildTree(List<MerkleNode> nodes) { Contract(() => nodes.Count > 0, "node list not expected to be empty."); if (nodes.Count == 1) { RootNode = nodes[0]; } else { List<MerkleNode> parents = new List<MerkleNode>(); for (int i = 0; i < nodes.Count; i += 2) { MerkleNode right = (i + 1 < nodes.Count) ? nodes[i + 1] : null; MerkleNode parent = CreateNode(nodes[i], right); parents.Add(parent); } BuildTree(parents); } } 審計證明
/// <summary> /// Returns the audit proof hashes to reconstruct the root hash. /// </summary> /// <param name="leafHash">The leaf hash we want to verify exists in the tree.</param> /// <returns>The audit trail of hashes needed to create the root, or an empty list if the leaf hash doesn't exist.</returns> public List<MerkleProofHash> AuditProof(MerkleHash leafHash) { List<MerkleProofHash> auditTrail = new List<MerkleProofHash>(); var leafNode = FindLeaf(leafHash); if (leafNode != null) { Contract(() => leafNode.Parent != null, "Expected leaf to have a parent."); var parent = leafNode.Parent; BuildAuditTrail(auditTrail, parent, leafNode); } return auditTrail; } protected void BuildAuditTrail(List<MerkleProofHash> auditTrail, MerkleNode parent, MerkleNode child) { if (parent != null) { Contract(() => child.Parent == parent, "Parent of child is not expected parent."); var nextChild = parent.LeftNode == child ? parent.RightNode : parent.LeftNode; var direction = parent.LeftNode == child ? MerkleProofHash.Branch.Left : MerkleProofHash.Branch.Right; // For the last leaf, the right node may not exist. In that case, we ignore it because it's // the hash we are given to verify. if (nextChild != null) { auditTrail.Add(new MerkleProofHash(nextChild.Hash, direction)); } BuildAuditTrail(auditTrail, child.Parent.Parent, child.Parent); } } 一緻性證明
/// <summary> /// Verifies ordering and consistency of the first n leaves, such that we reach the expected subroot. /// This verifies that the prior data has not been changed and that leaf order has been preserved. /// m is the number of leaves for which to do a consistency check. /// </summary> public List<MerkleProofHash> ConsistencyProof(int m) { // Rule 1: // Find the leftmost node of the tree from which we can start our consistency proof. // Set k, the number of leaves for this node. List<MerkleProofHash> hashNodes = new List<MerkleProofHash>(); int idx = (int)Math.Log(m, 2); // Get the leftmost node. MerkleNode node = leaves[0]; // Traverse up the tree until we get to the node specified by idx. while (idx > 0) { node = node.Parent; --idx; } int k = node.Leaves().Count(); hashNodes.Add(new MerkleProofHash(node.Hash, MerkleProofHash.Branch.OldRoot)); if (m == k) { // Continue with Rule 3 -- the remainder is the audit proof } else { // Rule 2: // Set the initial sibling node (SN) to the sibling of the node acquired by Rule 1. // if m-k == # of SN's leaves, concatenate the hash of the sibling SN and exit Rule 2, as this represents the hash of the old root. // if m - k < # of SN's leaves, set SN to SN's left child node and repeat Rule 2. // sibling node: MerkleNode sn = node.Parent.RightNode; bool traverseTree = true; while (traverseTree) { Contract(() => sn != null, "Sibling node must exist because m != k"); int sncount = sn.Leaves().Count(); if (m - k == sncount) { hashNodes.Add(new MerkleProofHash(sn.Hash, MerkleProofHash.Branch.OldRoot)); break; } if (m - k > sncount) { hashNodes.Add(new MerkleProofHash(sn.Hash, MerkleProofHash.Branch.OldRoot)); sn = sn.Parent.RightNode; k += sncount; } else // (m - k < sncount) { sn = sn.LeftNode; } } } // Rule 3: Apply ConsistencyAuditProof below. return hashNodes; } /// <summary> /// Completes the consistency proof with an audit proof using the last node in the consistency proof. /// </summary> public List<MerkleProofHash> ConsistencyAuditProof(MerkleHash nodeHash) { List<MerkleProofHash> auditTrail = new List<MerkleProofHash>(); var node = RootNode.Single(n => n.Hash == nodeHash); var parent = node.Parent; BuildAuditTrail(auditTrail, parent, node); return auditTrail; } ####審計證明校驗
/// <summary> /// Verify that if we walk up the tree from a particular leaf, we encounter the expected root hash. /// </summary> public static bool VerifyAudit(MerkleHash rootHash, MerkleHash leafHash, List<MerkleProofHash> auditTrail) { Contract(() => auditTrail.Count > 0, "Audit trail cannot be empty."); MerkleHash testHash = leafHash; // TODO: Inefficient - compute hashes directly. foreach (MerkleProofHash auditHash in auditTrail) { testHash = auditHash.Direction == MerkleProofHash.Branch.Left ? MerkleHash.Create(testHash.Value.Concat(auditHash.Hash.Value).ToArray()) : MerkleHash.Create(auditHash.Hash.Value.Concat(testHash.Value).ToArray()); } return rootHash == testHash; } 擷取審計證明作為哈希對進行驗證
/// <summary> /// For demo / debugging purposes, we return the pairs of hashes used to verify the audit proof. /// </summary> public static List<Tuple<MerkleHash, MerkleHash>> AuditHashPairs(MerkleHash leafHash, List<MerkleProofHash> auditTrail) { Contract(() => auditTrail.Count > 0, "Audit trail cannot be empty."); var auditPairs = new List<Tuple<MerkleHash, MerkleHash>>(); MerkleHash testHash = leafHash; // TODO: Inefficient - compute hashes directly. foreach (MerkleProofHash auditHash in auditTrail) { switch (auditHash.Direction) { case MerkleProofHash.Branch.Left: auditPairs.Add(new Tuple<MerkleHash, MerkleHash>(testHash, auditHash.Hash)); testHash = MerkleHash.Create(testHash.Value.Concat(auditHash.Hash.Value).ToArray()); break; case MerkleProofHash.Branch.Right: auditPairs.Add(new Tuple<MerkleHash, MerkleHash>(auditHash.Hash, testHash)); testHash = MerkleHash.Create(auditHash.Hash.Value.Concat(testHash.Value).ToArray()); break; } } return auditPairs; } 一緻性驗證驗證
public static bool VerifyConsistency(MerkleHash oldRootHash, List<MerkleProofHash> proof) { MerkleHash hash, lhash, rhash; if (proof.Count > 1) { lhash = proof[proof.Count - 2].Hash; int hidx = proof.Count - 1; hash = rhash = MerkleTree.ComputeHash(lhash, proof[hidx].Hash); hidx -= 2; while (hidx >= 0) { lhash = proof[hidx].Hash; hash = rhash = MerkleTree.ComputeHash(lhash, rhash); --hidx; } } else { hash = proof[0].Hash; } return hash == oldRootHash; } 在葉節點清單中尋找葉節點
protected MerkleNode FindLeaf(MerkleHash leafHash) { // TODO: We can improve the search for the leaf hash by maintaining a sorted list of leaf hashes. // We use First because a tree with an odd number of leaves will duplicate the last leaf // and will therefore have the same hash. return leaves.FirstOrDefault(l => l.Hash == leafHash); } // Override in derived class to extend the behavior. // Alternatively, we could implement a factory pattern. protected virtual MerkleNode CreateNode(MerkleHash hash) { return new MerkleNode(hash); } protected virtual MerkleNode CreateNode(MerkleNode left, MerkleNode right) { return new MerkleNode(left, right); } FixOddNumberLeaves
在比特币中，一棵樹總是有偶數個葉節點。如果樹中的最後一個節點為左子節點，那麼最後一個節點的内容将被複制到右子節點，他們的父節點的哈希值将通過兩個左子節點的哈希值串聯得到，你可以使FixOddNumberLeaves來建立這個行為
/// <summary> /// If we have an odd number of leaves, add a leaf that /// is a duplicate of the last leaf hash so that when we add the leaves of the new tree, /// we don't change the root hash of the current tree. /// This method should only be used if you have a specific reason that you need to balance /// the last node with it's right branch, for example as a pre-step to computing an audit trail /// on the last leaf of an odd number of leaves in the tree. /// </summary> public void FixOddNumberLeaves() { if ((leaves.Count & 1) == 1) { var lastLeaf = leaves.Last(); var l = AppendLeaf(lastLeaf.Hash); } } 計算兩個給定哈希值的哈希
public static MerkleHash ComputeHash(MerkleHash left, MerkleHash right) { return MerkleHash.Create(left.Value.Concat(right.Value).ToArray()); } MerkleProof 類
這個類被用于審計證明，将獲得的左右分支與校驗哈希相關聯，其中子哈希順序的正确性是擷取父哈希的必要條件。
namespace Clifton.Blockchain { public class MerkleProofHash { public enum Branch { Left, Right, OldRoot, // used for linear list of hashes to compute the old root in a consistency proof. } public MerkleHash Hash { get; protected set; } public Branch Direction { get; protected set; } public MerkleProofHash(MerkleHash hash, Branch direction) { Hash = hash; Direction = direction; } public override string ToString() { return Hash.ToString(); } } } 一共有14個單元測試，其中的一些看起來都很蠢，大部分的測試是是很細微的。其中最有趣的單元測試是一緻性證明的單元測試，我下面也隻會對它進行說明。
一緻性證明單元測試
這個單元測試會建立具有3-100個葉節點的樹，測試會為編号從1到n-1的葉節點擷取舊的根哈希值（n也就是測試樹的葉節點數）。
[TestMethod] public void ConsistencyTest() { // Start with a tree with 2 leaves: MerkleTree tree = new MerkleTree(); var startingNodes = tree.AppendLeaves(new MerkleHash[] { MerkleHash.Create("1"), MerkleHash.Create("2"), }); MerkleHash firstRoot = tree.BuildTree(); List<MerkleHash> oldRoots = new List<MerkleHash>() { firstRoot }; // Add a new leaf and verify that each time we add a leaf, we can get a consistency check // for all the previous leaves. for (int i = 2; i < 100; i++) { tree.AppendLeaf(MerkleHash.Create(i.ToString())); //.Text=i.ToString(); tree.BuildTree(); // After adding a leaf, verify that all the old root hashes exist. oldRoots.ForEachWithIndex((oldRootHash, n) => { List<MerkleProofHash> proof = tree.ConsistencyProof(n+2); MerkleHash hash, lhash, rhash; if (proof.Count > 1) { lhash = proof[proof.Count - 2].Hash; int hidx = proof.Count - 1; hash = rhash = MerkleTree.ComputeHash(lhash, proof[hidx].Hash); hidx -= 2; while (hidx >= 0) { lhash = proof[hidx].Hash; hash = rhash = MerkleTree.ComputeHash(lhash, rhash); --hidx; } } else { hash = proof[0].Hash; } Assert.IsTrue(hash == oldRootHash, "Old root hash not found for index " + i + " m = " + (n+2).ToString()); }); // Then we add this root hash as the next old root hash to check. oldRoots.Add(tree.RootNode.Hash); } } 哈希樹是證明資料完整性的一個高效的手段。單調（順序排列）也是使用哈希鍊的一個恰當手段。相應的一個例子就是
Holochain。"…一個由權威的哈希鍊提供支援的單調DHT"。Holochain是“…一個共享式的DHT，其中的每條資料都被植入到一方或者多方的簽名哈希鍊當中。它是一個可驗證的DHT，資料如果沒有經過每個節點共享的驗證規則驗證就無法繼續傳播。”是以，可以将單調哈希鍊和哈希樹兩項技術結合起來。正如
Arthur通過Slack寫給我的一樣：
Merkle Tree可以在holochain中使用來讓其中的每個條目在共享的鍊空間中實作私有資料（而不僅僅是加密）。我的意思是...假設你有一個具有下面6個字段的資料結構：
- Sender_ID
- Sender_Previous_Hash
- Receiver_ID
- Receiver_Previous_Hash
- Number_Credits_Sent
- Transaction_Payload
如果你使用這六個字段作為Merkle Tree的六個葉節點，你可以讓交易的雙方把完整的交易内容送出給私有鍊，然後雙方都拿出其部分的Merkle Tree進行簽名然後送出給共享的DHT，其中并不包括節點#6。這是因為Merkle Tree的證明使用前五個節點的内容來管理貨币就足夠了，這種方法允許他們擁有數字資産或者其他總是隐藏在自己的本地鍊當中的其他類型的資料，這些内容隻有自己才能看到而且不會影響互信的加密貨币的管理。
在區塊鍊上，交易中所有的資料都會進傳入連結中，要保證資料的私有你必須對資料進行加密，還要祈禱你使用的秘鑰和加密方式不會在這個永久、公開的記錄中收到影響。而在Holochain上，由于共享的DHT機制為本地鍊的資料校驗提供了支援，是以你可以利用Merkle證明來采用公開/私有資料混合的方式來保證你的私有資料的私有性。
比特币、以太坊以及其他的區塊鍊也是一個單調哈希鍊（區塊組成的鍊）的例子，其中包含着交易資訊組成的Merkle Tree。
寫這篇文章是“隻有你能教别人的時候你才真正學會了”的一個展現。需要耗費大量的研究和思考才能了解這些算法，尤其是一緻性證明。更關鍵的是，了解“為什麼”并沒有那麼直覺明顯。在最後我為自己做了一個Q&A的環節，我也将這些問題寫在這裡，這樣你也可以看到我嘗試去解答的問題。其中的一些答案可能不是很好，有些可能會引向一些并不重要的複雜細節，是以記住以下隻是我開始寫這篇文章之前調研的一個快照。
在你閱讀我下面的可能很奇怪的調查過程之前，這裡還有我的一個看法：我認為區塊鍊以及它的變體在未來一定會成為分布式管理的核心元件。而Merkle Tree和類似的哈希樹正是這些技術的基石。
資料同步Q&A
- 作為一個用戶端，你正在下載下傳一個大檔案，例如10GB，以大約4096byte大小的塊為機關進行傳播。
- 你需要一個可信的權威的伺服器來告訴你每個傳輸塊是不是有效的。
- 你可以從伺服器擷取根哈希并随着每一個傳輸塊的到來去填充Merkle Tree。
- 但是在驗證根節點之前你必須完成所有資料的下載下傳。
- 與之相對應的，你可以要求伺服器發送給你每個哈希塊相對根哈希的路徑以便你自行校驗。這使得你可以驗證每個傳輸塊是否損壞以便從其他地方重新請求。除此之外你也不需要維護所有塊的哈希值而是自己建構了一個Merkle Tree。這使得驗證一個塊的速度更快并且減少了Merkle Tree所需的記憶體。
- 伺服器作為可信機構并沒有儲存資料，他隻需要具有包含所有葉節點的Merkle Tree即可。
關于資料同步，你基本上有三種選擇：
- 下載下傳所有的資料然後去驗證根哈希值。
- 從可信的機構下載下傳Merkle Tree以便你可以使用不完整的記錄集進行測試。
- 讓伺服器在特定的葉節點進行審計證明。
驗證Q&A
Q1：為什麼不直接問伺服器某個葉節點是否存在于樹的指定節點下呢？
Q2：為什麼伺服器甚至要花時間來存儲葉節點哈希值的Merkle Tree？
A1：你可以這樣做，但是SHA256哈希值隻有32個位元組，雖然這代表了大量的唯一哈希值（2^256），1.15*10^77，但是在樹上各個節點的哈希值再次重複哈希最終得到的根哈希值可以提供很強的校驗。除此之外，審計校驗驗證了各個記錄與其他葉節點之間的關系。我們不單單想知道某個葉節點是否存在，我們還想知道它是否存在于樹的某個特定位置。
A2：假設你有一個大資料集，它被分成了很多小塊。首先你很可能不會維護整個資料集，而是隻維護你負責的部分。如果這一塊的内容發生了變化，你隻需要知道左右分支的哈希值即可重新計算根哈希。
這樣做的副作用也隻是你需要為你的塊保留左右分支，而不是整個Merkle Tree（包括了很多你不關心或者不知道的塊對應的葉節點哈希值）
要同步的時候，另一個使用者會要求你驗證根哈希值。如果根哈希值不同，則會請求左右子節點的哈希值，如果不比對則會一直疊代到識别出更改的塊對應的節點為止。此時你隻需要将更改的塊發送給其他使用者進行同步即可。
異常檢測Q&A
Q3：如果兩個以上的使用者同時修改一個塊的内容會發生什麼？（基于分布式系統的一個想法，你可能希望跨多個peers複制資料來提供彈性）
A1：隻有一個peer有權更改資料。
A2：哈希值可以打上時間戳，隻接受最近的更改，其他的更改會被丢棄。
A3：差異合并（自動或者手動幹預）。
A4：你隻接受了最舊的更改，并丢棄最近更新的其他所有内容。
A5：從技術上來說，一個塊的内容永遠不會改變。如果需要更改，應當将其作為新的交易送出以便實作可審計的變動追蹤（不同于Merkle審計）。因為隻有具有特定的權限才可以被允許修改交易。
A6：某些阻塞機制可能被用于防止資料被同時修改。比方說，你可能在送出變更的時候收到一個“修改權限秘鑰”，如果你的修改權限秘鑰和目前的修改權限秘鑰不比對，你的修改請求會被拒絕并且會要求你同步資料以獲得新的修改秘鑰。
A7：這一點的突出點在于，如果塊的大小很小，那麼你的修改和其他人沖突的可能性就會很小。
為什麼要證明的Q&A
Q4：為什麼伺服器應當向你發送哈希審計跟蹤來校驗一個塊而不是直接傳回給你正确或者錯誤？
A：這是你驗證伺服器是否可信的手段——如果它隻是說“是”，你怎麼知道你可以信任它？通過向你發送左右部分的哈希來告訴你“我是這樣檢驗你的請求的”，而其他僞造的伺服器并不能發送任何審計跟蹤哈希，因為他們會給出一個不同的根哈希值。
原文釋出時間為：2018-03-25
本文作者：Mr.Crypto
本文來源：
騰訊雲 雲+社群，如需轉載請聯系原作者。
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)