Learning Rust - Merkle Tree

Recently, in my spare time, I've started to learn Rust and as an exercise I've decided to implement a Merkle Tree (Wiki).

Sounds easy but it's turned out to be a real adventure :) In this post I'm sharing some of my experiences.

Step 1

I've started with preparing the data structures. Here is something really basic, that would work with many languages:

struct MerkelTree {
    leaves: Vec<MerkelNode>
}

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

Merkel Tree consists of list of nodes labelled as "leaves". Each leaf contains hash of the corresponding data block and link to the parent node. Parent node groups two leaves (binary tree), and contains hash of their hashes. It also contains link to its parent node which groups two nodes at higher level. That rule is repeated upwards, until we end up with a single node at the top - root node. It contains so called "root hash" and it has no parent.

Needless to say - the structures I've designed didn't work.
The error said:

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

It's turned out to be quite well known error in Rust. At compile time it needs to know how much space a type takes up. Which is not possible with the approach I've taken.

There is an easy solution to that problem described here:
Enabling-recursive-types-with-boxes.
So, let's try it out.

Step 2

I've used "box" smart pointer which allows storing data on the heap. In that way my structure has a known, fixed size at compile time.

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

The code above compiles, so I was happy to start implementation. However, even after a few hours I was still not able to make my code compile...
The problem was not with the logic. The problem was that I was not able to express what I wanted in the way that was acceptable by Rust.

Then it came to me - it just can't work and the problem is with the structures again.
Two core rules in Rust say:

• Each value in Rust has an owner.
• There can only be one owner at a time.

But in my case I have, for example, two leaves that point to the same parent. Which one of them is owner of the parent?

Step 3

Ok, I can't have two owners, so it means I have to borrow values and use references:

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

However, above code will not compile because references in structures require using lifetimes:

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

The code looks a bit cluttered but at least it compiles. Let's continue with implementation then.

After another few hours, once again, I came to conclusion - it can't work this way.
I can borrow the value multiple times. That's fine. But what about this rule:

• Each value in Rust has an owner.

Looks like I don't have an owner now. I mean - I have it somewhere along the line, but I don't have any dedicated place to store it for the entire duration of the program.

Step 4

At that point of time I've come to conclusion that I was doing something fundamentally wrong. There must be a pattern in Rust that will allow me to do what I want...

After some googling, I finally found this:
The Reference Counted Smart Pointer

It provides the multiple ownership capability, whoa!

Definition of the structure looks like this:

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

Now, finally, I can have two owners for the same parent node.

There is only one final catch here - Rc<T> allows sharing the data for reading only. It is not sufficient in my case because once I created the node, I need to modify it with the pointer to the parent which is not known at the time of creation.

After an hour or so....

Step 5

It turns out there is an interior mutability pattern in Rust that will allow me to do exactly what I need.

The final definition of the structure looks like this:

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

With this structure I was able to implement working solution. I'm sure there is a lot ot things still to be optimised in my code but today I call it a day and celebrate :)