Building a Blockchain in Go PT: II - Proof Of Work

Alright everyone. Congratulations on making a simple blockchain! If you are coming to this post and haven't checked out part 1, I suggest you do that before reading further. Although I'm just a guy on the internet, so do what you want I suppose.

If you aren't interested in how the tech works, you can go down to the "Building the Algorithm" portion of the post.

Proof Of Work

From where we left off, we can simply add blocks to the chain willy-nilly. This is a bit of a problem if we want to sell others on the security aspect of the blockchain. Blockchains are secured by doing "work," which can be recreated to tell the other nodes that the new data you are trying to add is legit. This "work" is simply high levels of computational power.

To recreate a new chain, you would have to compute every single hash leading up to the block you were trying to create. As you can imagine, calculating all of the hashes would take a very long time. By the time you got to the block you were originally trying to create, the chain would have already left you behind. This is what makes the blockchain secure from attacks from bad actors.

The technology that allows this to happen is an algorithm called proof of work or PoW. The idea is that lots of work has to be done to create a new block on the chain. But there is another piece; we need to be able to verify that the work has actually been done. PoW in a nutshell says that performing the algorithm is hard "work", but proving that the "work" was done should be easy.

Analogies always help me, so in the name of learning we will use a moat. It is very hard to actually dig a moat, but very easy to see that someone did in fact dig it. Imagine you dig a moat and call it the "Moat of Neverland". In the blockchain world, someone would have to dig that exact moat down to the last inch of dirt before they could claim it as the new "Moat of Neverland". Not only is there a high barrier to entry, but they would have to do all that work before you made a single change to your moat.

This is how the blockchain stays secure. Anyone is welcome to grab a shovel and help you with the official moat, which is what bitcoin "miners" do. But to create a new one and pretend that it's your moat, is very, very difficult.

Okay enough of the idea behind proof of work and yadda yadda. Let's write a proof of work algorithm and add it to our program.

Building the Algorithm

First we need to refactor our program a bit.

Refactoring

Everything is in main.go currently, and I would like to add a bit of structure to our program. Go ahead and create a blockchain folder, and add block.go and proof.go to the folder. We will be moving most of the logic in main.go to the blockchain folder, and main.go will be responsible only for the printing out of the blockchain. This will also get you some experience with making your own go packages.

There is one thing to quickly note before hopping into the file. Normally in a PoW algorithm, the "work" that has to be put in is itself an entire algorithm. This allows the difficulty of the "work" put in to be dynamic, so that blocks are created at a consistent rate.

We will not be implementing this feature in our chain. At least not yet. For the time being we are just sticking a global variable at the top of our file, and we will reference that. You can start with this file, and add code below it for the remainder of this post.

// proof.go

package blockchain

import (
    "bytes"
    "crypto/sha256"
    "encoding/binary"
    "fmt"
    "log"
    "math"
    "math/big"
)
const Difficulty = 12

Alright, with the new files in place, we will open up Proof.go and begin work there. Having gone over what we want the PoW to accomplish, you may be left wondering how we actually make that happen with code. We are going to set a requirement: The first few bytes must contain 0's. With this in mind, the step-by-step looks something like this:

1. Grab the data from the block

2. Create a nonce

3. Create a hash of the data from the block + the nonce

4. Check the proceeding hash to see if it meets the requirements we listed above. (the first few bytes must be 0's).

Now that we know what we're trying to accomplish, things should be a bit more clear.

ProofOfWork struct

We will want a struct for PoW like we did with the blocks:

type ProofOfWork struct {
  Block *Block
  Target *big.Int
}

This struct will hold the contents of the block, as well as the Target.

Initializing the struct

I think it would be a good idea to have a way to create this struct we just made, and to be able to adjust the difficulty to show you how it affects how much "work" needs to be done.

func NewProofOfWork(b *Block) *ProofOfWork {
    target := big.NewInt(1)
    target.Lsh(target, uint(256-Difficulty))

    pow := &ProofOfWork{b, target}

    return pow
}

I think this explains itself pretty well besides the target.Lsh() function. We're shifting the first arg target, however many units left we set our 2nd arg. The closer we get to 256, the easier the computation will be. Increasing our difficulty will increase the runtime of our algorithm.

Since we have a way to hold our data now, we should probably make something worth holding. We'll start with a function to initialize our nonce, and put it into our Block.

That means our function will need to return a byte. I think we should make a utility function that will help us out with that. Don't worry if this doesn't completely make sense, essentially this is just a way to convert int --> []byte.

func ToHex(num int64) []byte {
    buff := new(bytes.Buffer)
    err := binary.Write(buff, binary.BigEndian, num)
    if err != nil {
        log.Panic(err)
    }
    return buff.Bytes()
}

Creating a nonce

With that out of the way, we can loop back to the initialization of our nonce.

func (pow *ProofOfWork) InitNonce(nonce int) []byte {
    data := bytes.Join(
        [][]byte{
            pow.Block.PrevHash,
            pow.Block.Data,
            ToHex(int64(nonce)),
            ToHex(int64(Difficulty)),
        },
        []byte{},
    )
    return data
}

Running the algorithm

This should allow us to have all of the information about our block, including the counter all in one spot so we can hash it, and then see if it meets our target requirements. If it doesn't, then we can increment our nonce, and try again. Let's see what that looks like.

func (pow *ProofOfWork) Run() (int, []byte) {
    var intHash big.Int
    var hash [32]byte

    nonce := 0
        // This is essentially an infinite loop due to how large
        // MaxInt64 is.
    for nonce < math.MaxInt64 {
        data := pow.InitNonce(nonce)
        hash = sha256.Sum256(data)

        fmt.Printf("\r%x", hash)
        intHash.SetBytes(hash[:])

        if intHash.Cmp(pow.Target) == -1 {
            break
        } else {
            nonce++
        }

    }
    fmt.Println()

    return nonce, hash[:]
}

This is taking the block, along with our nonce, and hashing it. After we have it hashed, we then compare it to the target. If we've got a valid hash then we stop, otherwise we increment our nonce and try it all over again. Hashing is quite CPU intensive, and running all of these hashes and checking them is what creates the "work" we've been referring to.

Validating the algorithm

With a way to actually create valid blocks, we now need a way to validate them in a way that isn't as work intensive. Since we return a tuple from our previous function, we have preserved the nonce that was used to create a successful hash. This means that we should be able to use the data from the block, along with the nonce from the tuple, and run that one hash. The hash we just made should equal the target we set from ProofOfWork.

To reiterate, our function needs to return a boolean, should be comparing the hash that the block generated, vs the hash that this function generates, and then giving us the true/false value resulting from that evaluation.

func (pow *ProofOfWork) Validate() bool {
    var intHash big.Int

    data := pow.InitNonce(pow.Block.Nonce)

    hash := sha256.Sum256(data)
    intHash.SetBytes(hash[:])

    return intHash.Cmp(pow.Target) == -1
}

Implementing the algorithm

Now we are done with proof.go, we will start working on the block.go file. You are a smart cookie, I'm sure, and might have speculated that this is where the logic for the individual blocks will go. You are correct. We will also go ahead and put our blockchain functionality in here for now, as it doesn't make sense for us to have an entire file just for the blockchain struct.

Modifying structs

We can start with moving the structs over. We will also want to add the Nonce to our Block struct.

// block.go

package blockchain

type BlockChain struct {
    Blocks []*Block
}

type Block struct {
    Hash     []byte
    Data     []byte
    PrevHash []byte
    Nonce    int
}

More Refactoring

After this we can remove the DeriveHash() function from main.go. Then we will copy over the CreateBlock, AddBlock, Genesis, and InitBlockChain functions over to block.go. At this point your block.go file should look like this:

package blockchain

type BlockChain struct {
    Blocks []*Block
}

type Block struct {
    Hash     []byte
    Data     []byte
    PrevHash []byte
    Nonce    int
}

func CreateBlock(data string, prevHash []byte) *Block {
    block := &Block{[]byte{}, []byte(data), prevHash}
        block.DeriveHash()
    return block
}

func (chain *BlockChain) AddBlock(data string) {
    prevBlock := chain.blocks[len(chain.blocks)-1]
    new := CreateBlock(data, prevBlock.Hash)
    chain.blocks = append(chain.blocks, new)
}

func Genesis() *Block {
    return CreateBlock("Genesis", []byte{})
}

func InitBlockChain() *BlockChain {
    return &BlockChain{[]*Block{Genesis()}}
}

We no longer have the DeriveHash function. This is a bit of a problem, as we aren't hashing the blocks at all! We need to implement this hot, new, sexy, PoW functionality we built out a few moments ago.

Adding PoW to our blocks

Now we need to do the hashing in our CreateBlock function like we were doing before with the DeriveHash.

func CreateBlock(data string, prevHash []byte) *Block {
    block := &Block{[]byte{}, []byte(data), prevHash, 0} 
    // Don't forget to add the 0 at the end for the nonce!
    pow := NewProofOfWork(block)
    nonce, hash := pow.Run()

    block.Hash = hash[:]
    block.Nonce = nonce

    return block
}

So walking through the above, we are:

• Making an empty block
• Making a NewProofOfWork
• Running the algorithm on the pow
• Storing the Hash of the new block
• Storing the Nonce of the new block

Conclusion

That's it! We've added a Proof of Work algorithm to our blockchain. The only thing left is to add some printout statements in our main.go file to see what happens. Below is what your main.go file should look like after all of our refactoring.

// main.go

package main

import (
    "fmt"
    "strconv"

    "github.com/nheingit/learnGo/blockchain"
)

func main() {

    chain := blockchain.InitBlockChain()

    chain.AddBlock("first block after genesis")
    chain.AddBlock("second block after genesis")
    chain.AddBlock("third block after genesis")

    for _, block := range chain.Blocks {

        fmt.Printf("Previous hash: %x\n", block.PrevHash)
        fmt.Printf("data: %s\n", block.Data)
        fmt.Printf("hash: %x\n", block.Hash)

        pow := blockchain.NewProofOfWork(block)
        fmt.Printf("Pow: %s\n", strconv.FormatBool(pow.Validate()))
        fmt.Println()
    }

}

To see the fruit of your labor, run go run main.go in your command line. If you would like to see how the difficulty changes how much "work" needs to be done, try changing the difficulty from 12 to 18! Play around and have fun with it.

The end result of your code should look like this

I hope you learned a thing or two following along. I know I sure learned a few things teaching all of this. I'll see you next time! :)