LOCUS CHAIN 技術系列 5：可驗證剪枝第 2 章

原文标题：《LOCUS CHAIN TECH SERIES 5: Verifiable Pruning Chapter 2.》

作者：LOCUS CHAIN FOUNDATION

編譯：ChainCatcher

Hierarchical Skewed Merkle Tree：可驗證修剪的數據結構
傳統的傾斜 Merkle 樹

Hierarchical Skewed Merkle Tree (H-SMT) 是支持 Locus Chain 可驗證剪枝的中心數據結構。 H-SMT 基於 Skewed Merkle Tree，它是 Merkle Tree 的變體。

Merkle Tree 是一種樹狀數據結構，每個葉子節點都有一個密碼哈希值標籤，每個非葉子節點都有一個從其子標籤傳遞的密碼哈希值標籤，這些標籤也是哈希值。 在區塊鏈中，Merkle Tree 被廣泛用於證明列表中數據的存在。

Skewed Merkle Tree (SMT) 是 Merkle Tree 的一種形式，每個非葉節點都有一個葉節點和一個非葉節點。 Skewed Merkle Tree 是一種基於 Merkle Tree 的鏈表。 通過在先前的 SMT 之上添加新的根節點，將數據添加到 SMT 鏈表。 先前的根成為新根節點的子節點，新數據塊也作為子節點添加。 SMT中數據塊的個數是SMT的高度減一。 SMT 中的節點通過檢查其子節點中的哈希值來驗證，有效地計算該節點之前所有節點的哈希值。

Hierarchical SMT：基於 SMT 構建的有向無環圖

SMT 是一種簡單的數據結構。 驗證 SMT 的成本與數據長度或 O(N) 成正比。 分層 SMT 通過添加輔助驗證鏈接（"跳轉鏈接"）將性能提高到 O(log N)，"跳轉"節點的指數距離。

SMT 是二叉 Merkle 樹。 Merkle Tree 節點的每個標籤都是其子節點標籤傳遞的哈希值。 在SMT中，一個節點的第一個孩子有新數據塊Tn的哈希值，第二個孩子有前一個根節點Rn-1的標籤。

H-SMT 節點還有一個子節點。 第 3 個子節點是指向過去點中 Merkle Tree 節點的鏈接。 我們將這個第三個孩子表示為"跳轉鏈接"。

跳躍距離

跳轉鏈接是指過去節點的Merkle Root哈希值。 技術上可以使用過去的任何節點。 在 Locus Chain 中，跳轉鏈接節點的相對位置（或"跳轉距離"）是根據預定義的"跳轉基數"值和圖的高度來確定的。

特別地，跳躍距離是跳躍基礎距離的倍數。 最小跳躍距離為 base，最大距離為 base\^base。

添加跳轉鏈接

讓我們舉一個通過在現有 SMT 上添加 base=3 的跳轉鏈接來構建 H-SMT 的示例。

跳躍距離是根據節點到基地的偏移量計算的。 偏移量是節點高度 n 除以基數的提醒值。

offset = n mod 基數

那麼，跳躍距離就是base抵消的力量。 如果 offset=0，則距離是基到基的幂。

Locus BFT Consensus Algorithm 是對offset=1的節點添加跳轉鏈接的例子。 節點 4 的標籤由三個孩子 T4、R3 和 R1 傳遞。

接下來，讓我們為 offset=2 的節點放置跳轉鏈接。 offset=2的節點跳轉距離為3²=9。 實際上，如果鏈接距離變長，省略跳轉鏈接可能會更有效。 圖4中，offset=2的跳轉鏈接只放在高度為(offset+baseoffset*k)的節點上，形成直鏈表。

通過重複這些步驟直到偏移量到達底部來完成該過程。 圖5是base=3的跳轉鏈接的最終結果。

添加一個新的數據塊

相同的算法適用於將新塊 Tn 添加到現有的 SMT。 使用高度計算偏移量和跳躍距離，然後根據h(Tn)、Rn-1和Rn-jump_distance計算新根H-SMT節點的哈希標籤。

驗證塊

假設一個驗證者有一個H-SMT列表中節點的哈希值Ry，驗證者想要驗證前一個區塊Tx，或者區塊h(Tx)的哈希也包含在H-SMT中。 這是一個尋找從 Ry 到 Rx 的路徑的問題，Rx 是 Tx 的直接父節點。 驗證者可以按照下面的過程找到從 Ry 到 Rx 的路徑。

1) 從 Ry 開始，檢查附近的節點 { Ry-1, Ry-2, …, Ry-base } 以找到指向節點 Ri (i>=x) 的最長跳轉鏈接。

2) 記錄 i 並用 Ri 重複步驟 1，直到 i 達到 x。

3) 計算在步驟1和2中找到的所有節點的哈希值鏈。如果最終值匹配Ry，則Tx是Ty的先例。

圖 6 是從節點 R59 找到先行塊 T8 的示例。 緊鄰的先前鏈接用於 R59→R58→R57。 從R57到R30，經過距離為27的跳轉鏈接。 距離 9 的跳轉鏈路用於 R29 到 R11。最後遍歷R11到R8。

此示例中遍歷的鏈接數為 9。在 SMT 中，需要遍歷 59--8 = 51 次。

現實世界的實施

W 在前面的例子中使用了 3 的基數； 但是，較大的基值適合實際使用。 Locus Chain一般情況下使用base值為10，base=10的跳躍距離範圍為10 ~ 10¹⁰。 例如，距離為 1999 的兩個節點的最佳鏈路遍歷數為 28，從 (1*1000 + 9*100 + 9*10 + 9) 傳遞。

檢測偽造鏈接

惡意行為者可能會使用非法跳轉鏈接偽造 H-SMT 節點的哈希值。 在 H-SMT 中，可以通過交叉驗證到節點的多條路徑來識別此類偽造的節點值。

H-SMT是有向無環圖，如果兩個節點之間的距離大於基值，那麼這兩個節點之間總是存在兩條或更多條路徑。 節點之間的每條路徑都是一棵Merkle Tree，每棵Merkle Tree計算的哈希值必須匹配。 如果偽造的節點引用了一個非法的散列值，那麼路徑之間的散列值將不匹配。

通過此屬性，可以通過選擇兩條不同的路徑到隨機遠距離先例並比較路徑的哈希值來驗證節點。

概括

驗證長鏈數據一直是區塊鏈的計算密集型開銷。 一些區塊鏈系統需要數小時的準備時間來驗證賬本數據的完整性。 Locus Chain 通過分層傾斜 Merkle 樹解決了這個問題，這是一種創新的數據結構，可將數據鏈驗證開銷減少到鏈長度的對數尺度。