Learn Linked Lists by building a Blockchain (in Go 1.13)

Daniel — Mon, 07 Oct 2019 22:17:28 +0000

So, in this tutorial series I want to teach you fundamental computer science topics you might dread, have forgotten about or simply never bothered to learn by implementing popular and impactful technology in use today. My hope is that by the end of this tutorial (and hopefully the whole series) you'll have a greater understanding of the inner workings of various pieces of technologies you most likely use, understand the value of knowing about fundamental CompSci topics such as algorithms and data structures, ace programming interviews, be a more well-rounded professional and in general, have lots of fun by working through these tutorials with me.

Linked Lists as one of the foundational concepts behind Blockchains

If we take a look at what a Blockchain is, we can boil it down to a list of data, more concretely, a linked list of be it transactions, contracts or whatever flavor of Blockchain we might have.

The specific variation of such a data structure in particular is a doubly linked list, that is a list whose elements hold a reference to the previous element in the list and a reference to the next item.

So without further ado, let's get to it

Installation

First, if you don't already have it installed, you're gonna need to install Go (1.13) to be able to follow along and run the code samples.

Windows

You can download the installer for the latest version of Go from here. Once downloaded, follow its instructions to finalize the setup.

MacOS

if you have Homebrew installed you could simply do:

brew install go

Otherwise you can download the installer for the latest version of Go from here. Once downloaded, follow its instructions to finalize the setup.

GNU/Linux

If you're on Linux, chances are you already have your preferred method of package management, know how to install it and/or already have it installed. So here you can grab the compiled binaries and the source code as well.

If everything ran smoothly, you should be able to run in your terminal go version and see some output.

The Block

First we need to define how our blocks are gonna look like. We need a Hash that would serve as an ID for it, then we need a reference to the previous block in the chain as well as the block positioned immediately after the current one.

// blockchain-in-go/ledger/block.go

package ledger

type Block struct {
    Hash     string
    Previous *Block
    Next     *Block
}

The Chain

Now onto the chain:

// blockchain-in-go/ledger/ledger.go

package ledger

// This import is used later on, so it's useful we add it by now
import (
    "errors"
)

type Ledger struct {
    Genesis *Block
}

// Method definitions in this file will happen after this comment

Notice the only field we're defining on our chain is the Genesis block, which is a pointer to a Block. The reason being, that by the nature of linked lists, we only need to get ahold of one item on the list to be able to traverse it, even more so when we talk about doubly linked lists. We'll demonstrate this in the following sections.

Now that we have our blocks and our chains, we need to marry these structs together to be able to form our intended data structure and operate on it.

Operations

Normally linked lists should implement four operations: insertion at the end of the list, insertion at the begining, removal at the end of the list and removal at the beginning. But since we're building a blockchain, which are somewhat immutable (thanks in great part to consensus algorithms), we're only going to implement insertion at the end of the list and a way to retrieve a node given an ID.

Add

We assign a reference to our ledger as the receiver for this method since we need to access it and modify it during our insert operation. We also pass a string as a parameter which would be the hash we're going to use to identify the block.

// blockchain-in-go/ledger/ledger.go
func (l *Ledger) Add(h string) int {
    //  Method body
}

We then define our base case for this function. If the list is empty, then whatever we append to the list gets designated as our Genesis block. It's important to note here, that in general, a doubly linked list can have a referece to the last item in it on its head, these are called cyclical linked lists, but since blockchains aren't cyclical, we always set the Previous value of our Genesis to nil

// blockchain-in-go/ledger/ledger.go
func (l *Ledger) Add(h string) int {
    if l.Genesis == nil {
        // If there's no block on the ledger, then we create our genesis block
        l.Genesis = &Block{Hash: h, Next: nil, Previous: nil}
        return h
    }
}

Now, what we do when the list isn't empty is a bit more contrived and essentially the linked part of our list:

// blockchain-in-go/ledger/ledger.go
func (l *Ledger) Add(h string) string {

    // --- Previous code ---

    // --- New code ---
    // We start counting from the genesis block
    block := l.Genesis

    // We traverse the blocks
    for block.Next != nil {
        block = block.Next
    }

    // We then add the block to the end of the list
    block.Next = &Block{Hash: h, Next: nil, Previous: block}

    // We return it's index so we can reference our newly created block later on
    return h

}

Let's break down what's happening here:

If the list isn't empty we assume that there's a Genesis block so we set it as our current block.
We then iterate over the blocks until we find the last one in our list, that is, the one with the Next attribute set to nil.
Then we instatiate a new block and assign it as the Next attribute to our current block.
We set the Previous attribute of our newly created block to be a pointer to the current block.
Then we set the newly created block's hash to be the one we passed to the method as an argument.
And lastly, we return the hash of the newly created block so we can use it to reference it later.

After we're done, our method should look like this:

// blockchain-in-go/ledger/ledger.go

func (l *Ledger) Add(h string) string {
    if l.Genesis == nil {
        // If there's no block on the ledger, then we create our genesis block
        l.Genesis = &Block{Hash: h, Next: nil, Previous: nil}
        return h
    }

    // We start counting from the genesis block
    block := l.Genesis

    // We traverse the blocks
    for block.Next != nil {
        block = block.Next
    }

    // We then add the block to the end of the list
    block.Next = &Block{Hash: h, Next: nil, Previous: block}

    // We return its hash so we can reference our newly created block later on
    return h
}

Get

Now that we've created a way to append blocks to our chain, we'd need a way to retrieve a single block from it. This method is actually pretty similar to the previous Add but a bit more straightforward.

We start by checking if the chain is empty. If it is, then we return an error value.


// blockchain-in-go/ledger/ledger.go
func (l *Ledger) Get(h string) (*Block, error) {
    if l.Genesis == nil {
        return nil, errors.New("The chain is Empty")
    }
}

Then we check if the hash passed as a parameter and the hash of the current block match. If they do, then we return the block. If by any reason, the hash we passed in as a parameter is invalid or no block has a hash that matches, we return an error value.

func (l *Ledger) Get(h string) (*Block, error) {

    // --- Previous Code ---

    block := l.Genesis
    hash := l.Genesis.Hash

    for block != nil {
        // If hashes match, then we return the current block and no errors
        if hash == h {
            return block, nil
        }
        block = block.Next
        hash = block.Hash
    }

    return nil, errors.New("Block not found")
}

Here's how this method should look like.

// blockchain-in-go/ledger/ledger.go

func (l *Ledger) Get(h string) (*Block, error) {
    if l.Genesis == nil {
        return nil, errors.New("The chain is Empty")
    }

    block := l.Genesis
    hash := l.Genesis.Hash

    for block != nil {
        // If hashes match, then we return the current block and no errors
        if hash == h {
            return block, nil
        }
        block = block.Next
        hash = block.Hash
    }

    return nil, errors.New("Block not found")

}

Conclusion

With this small example we've built a fully functional doubly linked list. Below is the link to the repo with the annotated source code.

GitHub repo

Hopefully this was a fun and insightful way to help you understand Linked Lists a little better. Let me know in the comments if you'd like me to write a tutorial on how to build a fully functional CLI app and server for our little Blockchain (similar to Geth).

Forem: Daniel