Well, I wrote a Merkle root generator in Go, and it was fun! The full source code can be found on my Github.

This post is a walkthrough of the code for anybody that might be interested, because it’s a nice example of a simple, fast CLI utility - a perfect use-case for Go.

See my previous post for more on what a Merkle tree is and why it’s useful.

Thoughts on Go in general

Go is a wonderfully simple and elegant language.

I really enjoyed reading Rob Pike’s rationale document where he explains his design choices. Go solves a lot of the major issues in C and C++ without sacrificing simplicity or too much performance.

It also has a wonderful concurrency model (very similar to Erlang’s actor model actually) and does away with object inheritance ❤️ which has been one of the most misguided ideas in programming history.

What’s crazy is that Go is for loops all the way down. No map, reduce etc.

I thought I would miss this functional programming sugar that I’ve become accustomed to in Ruby, Clojure, Elixir, Elm etc, but the language actually works perfectly fine without it.

Go gives you low-level control over memory when you need it, and for this reason it can be made fast if you know how.

I always loved C for how raw and pure it is.

It’s so close to the metal… and I love Go for the same reason.

Yet it manages to deliver that whilst solving all the biggest pains of C:

  • The garbage collector relieves you from manual memory management
  • Horrible concurrency primitives like mutexes and threads are replaced with lightweight Goroutines
  • Solid module/namespacing system
  • Memory safety ensures no more buffer overflows
  • … lots more nice things

In short, Go is fast and fun. What’s not to love?

Building a Merkle tree in Go

Enough waffle. Let’s dive into some code! The full source is on Github but I’ll be referencing snippets here.

The first thing to think about is always data. How are we going to represent this data structure?

Data structure

In the case the answer is in the question - it’s a tree, silly! Each node has two children, except leaf nodes which have none. It looks something like this:

Merkle tree illustration

Each node can be represented as a Go struct.

// Branch nodes always have two children
// Leaf nodes have nil children
type Node struct {
    // The node hash
    // If it's a leaf node, it's the hash of the data block
    // If it's a branch node, it's the hash of the two child hashes concatenated together
    value [sha256.Size]byte
    // Pointers to children
    left  *Node
    right *Node
}

Note that we use pointers to refer to the children. Go does support embedded structs but that doesn’t work for our case for a couple of reasons:

  1. Embedded structs must always be present which prevents us from representing leaf nodes with no children
  2. The pressure on the garbage collector would be larger since we’d essentially be copying all of the structs into an entirely new tree every time we went up a level

By using pointers we only have to create each node once and Go’s garbage collector automatically tracks the entire tree from the root node pointer in our code.

We can also represent leaf nodes by using null for the left and right child pointers.

Building the leaf nodes

With our data structure taken care of, let’s see how we go about reading the file and building the tree.

Remember our desired end result is simply one node (the root node) which comes with the entire tree hanging off it.

We still need to build this tree from the bottom up and generate the root node last.

So first we rip through the entire file and generate all the leaf nodes.

Here’s how we do that:

// OPEN FILE FOR READING

// I really like Go's feature of having multiple return values
// It's similar to using :ok/:error tuples in Elixir and allows
// for really nice flow control for errors without having to
// resort to using exceptions.
f, err := os.Open(path)
if err != nil {
    // This will exit the program if the file is missing
    panic(err)
}

// GET SIZE OF FILE
// This allows us to create a slice that's backed by an array
// large enough to contain them all.
// We could easily skip this step and rely on Go's automatic
// array-growing to handle it for us, but it's more efficient
// this way since reading the file size is a O(1) operation but
// growing the array is more like O(log(n))
fileInfo, _ := f.Stat()
nChunks := nChunks(fileInfo)

// nChunks function included for reference
func nChunks(fileInfo os.FileInfo) int {
    size := fileInfo.Size()
    nChunks := int(size / ChunkSize)
    if size%ChunkSize != 0 {
        // Add one more chunk to hold the last bytes if the
        // file size is not exactly divisible by 1024
        nChunks++
    }
    return nChunks

}

// ALLOCATE MEMORY FOR LEAF NODES
// make is Go's way of allocating memory for a slice
leafNodes := make([]Node, nChunks)

// ALLOCATE MEMORY FOR THE DATA BUFFER
// We're going to be reading the file in chunks of 1024 bytes
// each.
// We could slurp the entire file into memory and process that
// in increments but it's much more memory efficient if we
// stream it instead.
// I chose to allocate the buffer outside of the loop and
// re-use it.
// Originally I allocated the buffer inside the loop but I
// realised this would lead to a lot of allocations and put
// unnecessary pressure on the garbage collector. It's more
// efficient to allocate the buffer once before entering the
// loop and re-use it for each chunk.
//
// A possible performance improvement might be to make this
// work concurrently with N Goroutines where N is the number
// of cores.
// I didn't build it this way because it would be premature
// optimisation and besides this task is more likely to be
// IO-bound than CPU bound.
buffer := make([]byte, 1024)

// RIP THROUGH THE FILE
for i := 0; i < nChunks; i++ {
    // READ 1024 BYTES (or until EOF)
    length, err := f.Read(buffer)
    if err != nil {
        panic(err)
    }
    // HASH BYTES AND CREATE THE NODE
    node := Node{
        // Important note! Since the buffer is always 1024
        // bytes long, we want to make sure we only read
        // the bytes that were put into the buffer from this
        // iteration.

        // Without specifying the length, we might
        // accidentally hash garbage on the final block.
        sha256.Sum256(buffer[:length]),
        nil,
        nil,
    }
    // ADD THE NODE TO THE LEAF NODES ARRAY
    leafNodes[i] = node
}

That’s how we build the bottom layer of leaf nodes.

Recursively building the tree

Now we have our leaf nodes, we can recurse upwards to create our tree.

This is standard tree building and Go makes it very elegant.

rootNode := buildTree(nodes)[0]

func buildTree(nodes []Node) []Node {
    // BASE CASE
    // When we get to the top of the tree it's time to return
    // an array with one node in it, which is the root node
    if len(nodes) == 1 {
        return nodes
    }

    // ENSURE THERE ARE TWO CHILDREN FOR EVERY NODE
    // This results in an evenly balanced binary tree
    if len(nodes)%2 == 1 {
        // Double up the last node so there is always an
        // even number (this is also what bitcoin does)
        nodes = append(nodes, nodes[len(nodes)-1])
    }

    // ALLOCATE MEMORY FOR PARENT NODES
    // Dividing by two is safe because there are always
    // an even number of nodes at this point.
    parents := make([]Node, len(nodes)/2)

    // MAIN LOOP
    for i := 0; i < len(nodes); i += 2 {
        left := nodes[i]
        right := nodes[i+1]
        parents[i/2] = makeParent(left, right)
    }

    // DO IT AGAIN :)
    return buildTree(parents)
}

func makeParent(left, right Node) Node {
    // PARENT HASH
    // The parent hash is simply the hash of the two child
    // hashes concatenated together. This is similar to what
    // bitcoin does in it's own Merkle tree implementation.
    var concatenatedHashes [2 * sha256.Size]byte
    copy(concatenatedHashes[:], left.value[:])
    copy(concatenatedHashes[sha256.Size:], right.value[:])
    hash := sha256.Sum256(concatenatedHashes[:])
    return Node{
        hash,
        // Yay pointers. Go will automatically track these
        // and avoid garbage collecting the node as long
        // as we hold onto a reference to one of it's parents.
        &left,
        &right,
    }
}

And that’s how we get to the Merkle root.

Note that this version uses only a single round of SHA256 hashing. Bitcoin core uses two rounds.

That means it takes the SHA256, then another SHA256 of the hash itself.

The reason for this is unclear, but this Stack Overflow post suggests that Satoshi may have chosen two rounds of hashing in order to to protect against length extension attacks.

Final thoughts

This program was a lot of fun to write and the next time I need to do some low level bit-mashing I’ll definitely consider Go as a top choice for the job.