用 Rust 實現默克爾樹

聽起來很簡單，但事實證明這是一場真正的冒險，在這篇文章中，我將分享一些我的經歷。

第一步

從準備數據結構開始，這裏有一些非常基本的東西，它適用於許多語言：

struct MerkelTree {
    leaves: Vec<MerkelNode>
}

struct MerkelNode {
    parent: Option<MerkelNode>,
    hash: String
}

默克爾樹由標記爲 “葉子” 的節點列表組成。每個葉子節點都包含相應數據塊的 hash 值和到父節點的鏈接。父節點對兩個葉子節點 (二叉樹) 進行分組，幷包含它們的 hash 值。這個規則向上重複，直到在最頂端的根節點上有一個節點。它包含所謂的“根哈希”，它沒有父節點。

如圖：

不用說，現在設計的這個 struct 不起作用，錯誤提示：

struct MerkelNode {
   | ^^^^^^^^^^^^^^^^^ recursive type has infinite size

事實證明，這是 Rust 中非常著名的錯誤。在編譯時，它需要知道一個類型佔用了多少空間。

第二步

我們使用 Box 智能指針，它允許在堆上存儲數據。這樣，我們的 struct 在編譯時就有了一個已知的固定大小。

struct MerkelNode {
    parent: Option<Box<MerkelNode>>,
    hash: String
}

上面的代碼可以編譯，所以我很高興開始實現。然而，即使在幾個小時後，我仍然不能使我的代碼編譯… 問題不在於邏輯，問題是我不能用 rust 能接受的方式表達我想要的東西。

問題又出在 struct 上了，Rust 的所有權規則是：

但在這個例子中，有兩個葉子結點指向同一個父結點。哪一個是父節點的所有者？

第三步

好吧，我不能有兩個所有者，所以這意味着我必須借用值並使用引用：

struct MerkelNode {
    parent: Option<Box<&MerkelNode>>,
    hash: String
}

然而，上面的代碼將無法編譯，因爲 struct 中的引用需要使用生命週期：

struct MerkelNode<'a> {
    parent: Option<Box<&'a MerkelNode<'a>>>,
    hash: String
}

代碼看起來有點雜亂，但至少可以編譯。接下來讓我們繼續實現， 又過了幾個小時，我又一次得出結論——這是行不通的。

我可以借用這個值很多次了，這很好。但是，在整個程序期間，我沒有任何專門的地方去存儲它。

第四步

使用 Rc，引用計數智能指針：

struct MerkelNode {
    parent:Option<Rc<MerkelNode>>,
    hash: String
}

現在，可以爲同一個父節點擁有兩個所有者。

這裏只有最後一個問題——Rc 允許共享僅用於讀取的數據。這是不夠的，因爲一旦創建了節點，需要用指向父節點的指針修改它。

第五步

使用智能指針 RefCeff，可以進行內部可變性，struct 的最終定義如下：

struct MerkelNode {
     parent: Option<Rc<RefCell<MerkelNode>>>,
     hash: String
}

有了這個結構，就能夠繼續實現接下來的功能了。在這個代碼中還有很多東西需要優化，如多線程環境下該如何修改？

本文翻譯自： https://dev.to/msedzins/learning-rust-merkel-tree-9p

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/tvLAYfxReBRlTMG0SsYTvw

猜你喜歡