改進稀疏Merkle樹，以實現更快、更高效的狀態身份驗證。請加入我們的Discord。
互操作性是許多區塊鏈初創公司、研究人員和開發人員正在探索的一個主題。它旨在將孤立的區塊鏈網路連線在一起，實現價值或資料的跨鏈傳輸。我們也將互操作性視為AERGO的多層架構設計的核心。該設計結合了公共和私有區塊鏈技術，彙集行業精華，可使企業在不犧牲去中心化和資料完整性等關鍵要素的情況下靈活設計dApp。
向我們的未來客戶跨區塊鏈傳輸價值或資料時，需要在這些網路之間進行安全通訊。我們將區塊鏈之間通訊的過程稱為資產橋接。資產橋接需要以有效的機制來驗證不同鏈的狀態。實現這一目標的一個方法便是透過智慧合約驗證其他區塊鏈狀態的Merkle證明（在這種情況下，為資產轉移請求）。這些證明的驗證需輕量且高效，以達到智慧合約的消耗效率。
以太坊使用修改後的Merkle Patricia樹來驗證狀態資料。但是，以太坊的Patricia樹是十六進位制的，每個節點包含16個子節點。這比二叉樹效率更低，且更難處理。實現區塊鏈商用所需的速度和效能要求狀態認證儘可能高效，這就促使我們研究稀疏Merkle樹。
我們的設計迭代首先使我們實現了標準的稀疏Merkle樹。標準的稀疏Merkle樹是一個可以在恆定時間內更新的雜湊樹。但是，我們發現它仍然太慢，無法為我們提供AERGO平臺所需的吞吐量。標準稀疏Merkle樹中速度受限的主要原因是其值都儲存在樹中的0（高度）處，這使得更新一個金鑰需要256次雜湊運算。
因此，為了提高AERGO鏈的吞吐量，我們的一個開發人員，Pierre-Alain Ouvrard，相應地改進了稀疏Merkle樹並用開源方法幫助我們提高了吞吐量。
AERGO StateTrie簡介
AERGO StateTrie將實現快速有效的狀態驗證。在這篇文章中，我將全面概述AERGO StateTrie是什麼，它有什麼功能，以及如何使用它。
AERGO StateTrie是一個改進的稀疏Merkle樹。它將值儲存在只包含一個金鑰的最高子樹中。由此實現的好處是：平均而言，在包含N個隨機金鑰的樹中，更新樹中的金鑰僅需要進行log（N）次雜湊運算。
AERGO改進的稀疏Merkle樹包含以下特徵：
· 高效的Merkle證明驗證（二叉樹結構）
· 透過節點批處理實現高效的資料庫讀取和儲存
· 減少資料儲存（子樹的葉子節點包含1個金鑰）
· 減少雜湊計算（子樹的葉子節點包含1個金鑰）
· 使用goroutine同時更新多個金鑰
限制：非包含的Merkle證明不像標準SMT那樣明確：它可以證明葉子節點位於非包含金鑰的路徑上，或者該值預設位於高度0處。
稀疏Merkle樹
稀疏Merkle樹是指包含用於加密雜湊函式的每個可能輸出的葉子的樹。
圖1.示例稀疏Merkle樹的高度= 4（4位金鑰）；3位金鑰以紅色和藍色顯示；預設節點以綠色顯示；非預設節點以紫色顯示。
值（非預設金鑰）儲存在高度為0的樹的葉子上。如果預設值為D0，則位於高度1處的每個預設節點的值都為D1 = 雜湊（D0，D0）。空樹的根是高度4的預設雜湊。當金鑰插入樹中時，葉子節點的值從預設值（D0）變為指定值，並且只有樹的修改部分需要重新計算。
例如，要將紅色值新增到已包含藍色金鑰的樹中，只需要計算h2，H2，H3和根，以獲取樹的新根。紅色值被新增到樹的左側，因此h3未被修改。
對於輸出256位的雜湊函式，其樹包含256級；或換句話說，具有2²⁵個可能金鑰，這使其無法表示。
樹之所以被稱為稀疏樹是因為如果樹只包含隨機金鑰（稀疏分佈），那麼其包含的大多數節點都有基於節點高度決定的預設值。因此，我們可以透過僅儲存一次預設節點，然後再儲存其餘的非預設節點來對樹進行模擬。
有關SMT及其Merkle證明的詳細概述，請參閱此文章。
稀疏Merkle樹的修改
為了減少更新樹中金鑰所需的雜湊運算次數，我們建立了葉子節點。葉子節點儲存在僅包含1個非預設金鑰的最高子樹中。因此，樹的雜湊從葉子節點的高度開始而不是從高度0開始。如果樹包含N個隨機金鑰，則平均而言，將在高度= log（N）周圍建立若干葉子節點。
圖2. H3是僅包含一個金鑰的最高子樹：紅色子樹。因此，它將在修改後的稀疏Merkle樹中佔據一席之地。
藍色金鑰不稀疏，因為它們僅在最後一位發散，所以它們在樹的底部位置不變。這顯示了在稀疏Merkle樹中使用隨機金鑰的重要性。
Merkle證明
使用二叉樹為我們提供了非常簡單易用的Merkle證明。與Patricia樹不同，Merkle證明由一個金鑰路徑中的所有節點組成。由於Patricia樹中的每個節點都有16個子節點，因此資料量較大，並且不像二進位制資料那樣可以直接驗證。
在上面的例子中，紅色金鑰的Merkle證明由紅色節點組成：[h3]。需注意，此證明比前一個示例（[D0，D1，D2，h3]）短得多，這是因為其值未儲存在高度0處。證明的驗證者將計算雜湊（葉子節點，h3）並檢查根是否如預期的那樣。
壓縮的Merkle證明：與標準的稀疏Merkle樹一樣，Merkle證明也可以壓縮。由於Merkle證明中的大多數節點都是預設的，因此我們可以使用點陣圖併為證明中非預設的每個索引設定一個位。藍色葉子節點包含在樹中的證據是：【葉子節點2，D1，D2，葉子節點】。此證明可以壓縮為1001【葉子節點2，葉子節點】。壓縮的Merkle證明的驗證者應該知道使用D1來計算h2，這是因為點陣圖的第二個索引是0，而D2是用來計算第三個元素的。
非包含的證明：修改的稀疏Merkle樹的侷限性在於非包含的證明不明確：證明金鑰未包含在樹中的證據是葉子節點在非包含金鑰的路徑上或值預設位於高度0處。例如，金鑰 = 0000不包含在樹中的證據同時也是葉子節點位於金鑰路徑上幷包含在樹中的證據。金鑰 = 1111不包含在樹中的證據同時也是值預設位於高度0處（與標準稀疏Merkle樹相同）的證據。
從樹中刪除
從樹中刪除葉子時，Update()函式會特別注意將葉子節點保持在僅包含1個金鑰的最高子樹中。否則，如果節點在樹中具有不同位置，則即使金鑰和值相同，生成的trie根也會不同。
因此，當刪除某個金鑰時，Update()會檢查它的同級是否也是一個葉子節點並將其向上移動，直到最高子樹根包含該非預設金鑰為止。
圖3.修改了其中一個藍色節點後，樹的外觀示例
節點批處理
當將每個節點儲存為具有2個子節點的根時，儲存的節點數量增長非常快。並且，由於多個執行緒從記憶體載入節點，因而產生瓶頸。十六進位制Merkle樹可以解決這個問題。因為每個金鑰有16個子節點，高度較低（為64（256/4））。儘管如前所述，我們需要二進位制的樹。但是，我們可以透過使用節點批處理來實現與十六進位制樹相同的功能。
我們不是為一個節點儲存2個子節點，而是為該節點儲存高度為4的子樹。高度為4的樹在高度0處有16個葉子（如十六進位制）。因此，節點的值是包含4位樹的所有節點的陣列。可以在索引2 * i + 1和2 * i + 2處找到樹中索引i處的節點的子節點。
節點編碼如下：
{根：[ [標記葉子節點的位元組(0/1)], 3–0, 3–1, 2–0, 2–1, 2–2, 2–3, 1–0, 1–1, 1–2, 1–3, 1–4, 1–5, 1–6, 1–7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f ] }
例如，為了獲得陣列中索引id = 1處的節點3-0的子節點，我們可以在索引（2 * id + 1）=索引3處訪問左子節點2-0，並且在索引（2 * id + 2）= 索引4處訪問右邊的子節點2-1。
對於每個節點，我們附加一個位元組標記來識別葉子節點。由於未能提前獲知根的性質，因此位元組標記儲存在節點陣列的第一個索引處。
圖4.節點批處理的視覺化表示形式：第一批是藍色，一批的所有16片葉子都是其他批次（綠色）的根。一批包含30個節點。
節點批處理有兩個好處：
· 減少資料庫讀取次數
· 無需鎖定即可同時更新高度4子樹。
使用goroutines同步更新多個金鑰
不是逐個更新金鑰，而是可以使用更新呼叫功能來更新任意數量的金鑰，並同時更新樹的不同部分。金鑰應按陣列排序，相應的值應位於單獨陣列中的相同索引處（請參閱“用法”）。
如需從樹中刪除金鑰，只需將其值設定為高度0（D0）的預設值。
用法
建立空樹時，將根設定為零。零根表示它等於其高度的預設值。如果您計劃提交若干節點，則請使用自定義雜湊函式或在實用工具中使用雜湊計算器，並指定一個資料庫。
返回指定高度的預設節點
更新將以遞迴方式沿著樹向下進行並根據秘鑰所屬的樹的一側分割金鑰和值：可以同時更新樹的多個部分。
如果在“提交”之前多次呼叫更新，則僅提交最後一次的狀態。
AtomicUpdate同“update”一樣，使用排序的金鑰和值來更新樹。但與“update”不同的是，如果在“提交”之前多次呼叫AtomicUpdate，則會記錄AtomicUpdate呼叫的所有中間狀態。這在驗證每個區塊的狀態時非常有用，但不能立即提交到資料庫。
獲取儲存在樹中的金鑰的值。如果金鑰是預設的，即未儲存秘鑰值，則返回零。
將更新的節點提交到資料庫。呼叫更新時，新節點儲存在smt.db.updatedNodes中。然後，利用“commit”將其儲存到磁碟中。
使用Stash函式，可在不提交的情況下還原更新（例如，如果區塊驗證無效）
呼叫還原時，將從資料庫中刪除要回滾的樹（在當前樹和toOldRoot之間）。
MerkleProof建立了Merkle包含/不包含金鑰的證據。 Merkle證明是一個雜湊陣列。
如果未包含金鑰，則MerkleProof將返回錯誤以及金鑰路徑上的證明葉子。
MerkleProofCompressed可建立與MerkleProof相同的Merkle證明，但使用了點陣圖進行壓縮
驗證金鑰值對是否包含在當前根的樹中。
驗證不包含的證明。驗證葉子（proofKey，proofValue）是否在未包含金鑰的路徑上，或者稽覈路徑“ap”是否支援高度0處的預設值。
驗證金鑰值對是否包含在當前根的樹中。'長度'是要驗證的葉金鑰值的高度。
驗證非包含的壓縮證明。驗證葉子（proofKey，proofValue）是否在非包含金鑰的路徑上，或者稽覈路徑“ap”是否支援高度0處的非預設值。
結論
跨不同區塊鏈系統的通訊是分散式網路和企業區塊鏈未來所需的功能。促進鏈或資料鏈在企業中的鏈到鏈轉移需要有效的狀態驗證手段。標準的稀疏Merkle樹並不完全符合我們心裡所想的效能標準。因此我們對其進行了修改並透過開源得以實現。AERGO StateTrie將用於AERGO平臺，以便在資產橋接過程中和依賴安全狀態驗證的其他應用程式（如錢包和輕客戶端）中快速有效地驗證狀態。
如果您知道其他有趣的實現或想與我們就AERGO的任何技術方面進行互動，請聯絡我們：
