# Assignment 3: Blockchains with Go

## Introduction

For this assignment, you will be building functionality to create a simple blockchain system. Our blockchain will include a proof-of-work, so we will have to do some computation to create valid blocks.

As with the Go exercises, I have provided a code skeleton with some structure and hints.

### Blockchain Basics

A single *block* in a blockchain is fundamentally a data structure that contains some information (more on what information later). That data is hashed with a cryptographic hash function. As long as the hash function matches the contents, we will say that it's a *valid* hash (but we'll refine the idea under “Proof-Of-Work” below).

Blocks become a blockchain when they are joined together. This happens because one of the pieces of data in each block is the hash value from the **previous block**.

That means that if you have the block \(n\) from the chain and believe that its hash is valid, then you can also verify block \(n-1\). Block \(n-1\) must hash to the “previous hash” from block \(n\). Similarly, you can verify blocks \(n-2\), \(n-3\)….

As a result, we need a very small amount of information (one block) to be able to certify all steps in the chain since the beginning of time.

### Proof-Of-Work Basics

If just verifying a sequence of blocks is all you want, then we're done. The *proof-of-work* forces certain amount of computation to be required before someone can create a “valid” block.

The “proof” part of the proof-of-work requires that we have some value that is difficult to produce/find, but easy to verify once it is found. Any calculation with that property will do, but we will use the hash values we already need in the blockchain.

We will add a *proof* value to each block which can be any integer.
We will select a difficulty, \(d\) and insist that the last \(d\) bits of the hash value (including the proof in the data that is hashed) be zero. A block can only be considered valid if its hash ends with \(d\) zero bits.

That means in order to find a valid block, we have to iterate through possible “proof” values until we find one that makes the block's hash end in null bits. That work is (1) unavoidable as long as the hashing algorithm is good, and (2) easy to verify, since we just have to re-hash the block to check that it was done.

In a (simplified) diagram with \(d=16\) (so the last 2 bytes = 4 hex characters are zeros), we end up with a blockchain that looks like this:

In each case, we had to choose a “proof” value that made all of the block's data (in the dashed box) hash to a value ending in \(d\) zero bits. That hash becomes part of the data for the next block, and the chain continues.

## Work Queue

We need to be able to compute the proof-of-work in parallel in order to calculate it as quickly as possible. We also need to be able to stop the calculations and return a valid proof as soon as we find one, without doing a bunch of (now useless) calculations.

I think this is a situation where solving the more general problem is easier than doing it in the context of the blockchain mining.

See the provided `work_queue/work_queue.go`

for an outline of how we need a work queue to behave for this assignment.

When a new queue is created, it needs to have channels created for jobs going into the queue, results coming out, and requests to halt the computations. (Our work queue doesn't distinguish between results from the tasks: they come out of the `Results`

queue in whatever order they are produced.) Worker goroutines also need to be created which will watch the `Jobs`

queue for work to do.

When a job (`Worker`

instance) is put into the `Jobs`

channel, it should be started (by calling `.Run()`

) as soon as possible by one of the worker goroutines. Its result should be put into the `Results`

channel.

Other code using the queue should be able to read from the `.Results`

channel for results from any of the tasks, and deal with them as necessary.

### Stopping the Queue

We will need our work queue to do a slightly non-standard trick: once we find a result (proof-of-work in this case), we want to stop processing work because all subsequent calculations are unnecessary.

In the `.worker()`

method, that will mean processing jobs as until the channel is closed and all messages in it are received (exactly what `for range`

does).

When the queue's `.Shutdown`

method is called, the `.Jobs`

channel should be closed (so and `for range`

loops exit, and no more messages can be sent) and any messages in `.Jobs`

should be received (but not run).

### Tests

The provided `work_queue_test.go`

contains two tests. The first is for the basic “process jobs and give back results” behaviour of the queue. The second checks that the queue stops at the correct time when asked.

You do not need to add any additional tests to `work_queue_test.go`

. The provided tests should check all required functionality.

## Blocks

In `blockchain/block.go`

, we will start creating blocks. A `struct`

that holds all of the data we need has been provided.

The first block in a blockchain in a little special. It will have generation 0, difficulty as specified in the argument to `Initial`

, the empty string for data, and a previous hash of 32 zero bytes (`"\x00"`

). **Create a function** `Initial`

that generates the initial block for the chain.

To continue the chain, we will call a method on the last block on the chain. If we have a block `b`

, calling `b.Next(message)`

should create and return a new block that can go in the chain after `b`

. That is, it will have one higher generation; the same difficulty; data as given in the argument; previous hash equal to `b`

's hash. **Create a method** `.Next`

that creates a next-in-chain block.

Note that **these functions will not set the block's proof-of-work or hash** (and can leave then at the defaults when they are created by Go). That comes later…

## Valid Blocks

Recall: a block is *valid* if it has a “proof” value that makes it hash to a value that ends in `.Difficulty`

zero bits.
We need a few things to check this: the actual data to hash, a function calculate the hash, and a function to check if the hash ends in zero bits.

### Hashing Blocks

These fields will go into our hash string, separated by colons. The integers will be in the usual decimal integer representation (i.e. the number ten is `"10"`

):

- the previous hash, encoded to a string in hexadecimal;
- the generation;
- the difficulty;
- the data string;
- the proof-of-work.

After this code…

```
b0 := Initial(16)
b0.Mine(1)
b1 := b0.Next("message")
b1.Mine(1)
```

… my two hash strings are:

```
"0000000000000000000000000000000000000000000000000000000000000000:0:16::56231"
"6c71ff02a08a22309b7dbbcee45d291d4ce955caa32031c50d941e3e9dbd0000:1:16:message:2159"
```

[You might not have mining working as you read this, but you will soon.]

We will use the SHA256 hash function to hash these strings. **Write a method** `.CalcHash()`

that calculates the hash value of a block.

My hashes with the code above, and hex-encoded (i.e. these are the result of `hex.EncodeToString(block.CalcHash())`

) are:

```
"6c71ff02a08a22309b7dbbcee45d291d4ce955caa32031c50d941e3e9dbd0000"
"9b4417b36afa6d31c728eed7abc14dd84468fdb055d8f3cbe308b0179df40000"
```

### Valid Hashes

We have a “valid” proof of work a block if the block's hash ends in `.Difficulty`

zero bits. We need to check that.

Write a method `.ValidHash`

that returns true if (and only if) the block's hash ends in `.Difficulty`

zero bits.

The hash value will be a byte slice. The easiest way to check for `difficulty`

zero bits at the end of the slice is probably something like:

`nBytes = difficulty/8`

`nBits = difficulty%8`

- Check each of the last
`nBytes`

bytes are`'\x00'`

. - Check that the next byte (from the end) is divisible by
`1<<nBits`

(one left-shifted`nBits`

times is equal to \(2^\mathit{nBits}\)).

In the example above, we can see that if we create an initial block with `b0 := Initial(16)`

then `b0.ValidHash()`

should return `false`

, but if we set `b0.Proof = 56231`

then `b0.ValidHash()`

should be `true`

.

Another example, with this setup, `b1`

is valid and has *exactly* 19 zero bits at the end of its hash:

```
b0 := Initial(19)
b0.SetProof(87745)
b1 := b0.Next("hash example 1234")
b1.SetProof(1407891)
```

But if we did this, the block it **not** valid. It has only 18 zero bits at the end of its hash:

```
b1.SetProof(346082)
```

## Mining

Now that we have the basic structure for blocks, we need to do some mining. Put this functionality in `blockchain/mining.go`

.

The process of mining a block is conceptually easy: check proof-of-work values until you find one that would make `block.ValidHash()`

true. Once you have found it, set `block.Proof`

and `block.Hash`

to make the block valid. (The provided `.SetProof`

does the last step.)

A function `mineSequential`

is provided that loops over proof values starting a 0 until a valid one is found. You don't need this, but it completely avoids the need for the work queue, and may be convenient for testing the more complex implementation we're about to create…

A mining task will be a range of possible proof-of-work values: we want to check those value and return *any one of them* that makes the block's hash valid.

### Mining Tasks

We will use our work queue for this. We will need a `struct`

that implements the `Worker`

interface, i.e. has a `.Run()`

method. We can also use the `struct`

for any other information needed to do the mining we want done.

The `.Run()`

call should return a `MiningResult`

struct that includes (at least) a `.Proof`

(proof-of-work value, if found) and `.Found`

(indicating if the search was successful).

Once you have that, you can use it in `block.MineRange(start, end, workers, chunks)`

. This should check proof values for this block, from `start`

to `end`

(**inclusive**). The calculation should be done in parallel by the given number of workers, and dividing the work into `chunks`

approximately-equal parts.

This must be done using the work queue created above. If that is implemented correctly, it should be fairly easy to do this work in parallel, and to stop checking proof values (soon) after a valid proof is found.

A note on handling types and interfaces: the work queue will insist you return an `interface{}`

value from `.Run()`

. To actually use the result, it will have to be treated as a `MiningResult`

. You will need a “type assertion” to get that to work.

## Example Blocks

Here is an example of valid hashes being mined, and the proof values I get:

```
b0 := Initial(7)
b0.Mine(1)
fmt.Println(b0.Proof, hex.EncodeToString(b0.Hash))
b1 := b0.Next("this is an interesting message")
b1.Mine(1)
fmt.Println(b1.Proof, hex.EncodeToString(b1.Hash))
b2 := b1.Next("this is not interesting")
b2.Mine(1)
fmt.Println(b2.Proof, hex.EncodeToString(b2.Hash))
```

This outputs:

```
385 379bf2fb1a558872f09442a45e300e72f00f03f2c6f4dd29971f67ea4f3d5300
20 4a1c722d8021346fa2f440d7f0bbaa585e632f68fd20fed812fc944613b92500
40 ba2f9bf0f9ec629db726f1a5fe7312eb76270459e3f5bfdc4e213df9e47cd380
```

There are other valid proof values for these blocks, but these are the ones my code finds (and the numerically-smallest). Changing to difficulty 20 in the above code, it outputs:

```
1209938 19e2d3b3f0e2ebda3891979d76f957a5d51e1ba0b43f4296d8fb37c470600000
989099 a42b7e319ee2dee845f1eb842c31dac60a94c04432319638ec1b9f989d000000
1017262 6c589f7a3d2df217fdb39cd969006bc8651a0a3251ffb50470cbc9a0e4d00000
```

## Valid Blockchains

In `blockchain.go`

, we will finally put our blocks together into a blockchain, so we can have a chain and verify the validity of each block.

A simple `struct`

for a blockchain is provided. Complete a method `.Add`

that appends a new block to the chain.

The method `.IsValid`

will check a few aspects of the blockchain to make sure it is valid. The whole point: this is computationally efficient, but creating the blockchain (with proofs) was hard.

## Tests

The provided `blockchain_test.go`

doesn't actually contain any tests, but it should.

Write some tests that check the core functionality of the `Block`

. Your tests should ensure that at least some of the functionality described above is correct. There is no requirement for complete code coverage or testing every single thing mentioned.

You should **write at least three or four tests** (depending on the complexity of each test, of course) and cover a reasonable variety of the requirements for the assignment. At least some tests should be on examples **not** directly from the assignment description.

You can assume that the testify/assert package is available when we're marking. You can install it like:

```
go get github.com/stretchr/testify/assert
```

## Summary

All of the functions provided in the code skeleton should be complete with arguments and return values as specified. We will expect them to be there when testing your implementation.

Pieces provided that shouldn't be changed:

`blockchain.Block`

,`….MiningResult`

,`….Blockchain`

`blockchain.Block.SetProof`

,`….Mine`

These structs/functions/methods as in the provided code skeleton should be completed to work as described above:

`work_queue.Create`

`work_queue.WorkQueue`

`work_queue.WorkQueue.Enqueue`

,`….Shutdown`

`blockchain.Initial`

`blockchain.Block.Next`

,`….CalcHash`

,`….ValidHash`

,`….MineRange`

`blockchain.Blockchain.Add`

- Some tests in
`blockchain_test.go`

.

Where there are stub implementations in the provided hints, you aren't required to use them, as long as the functions listed here work as specified.

## Blockchains Revisited

There is a lingering question here: is this a “good” blockchain implementation?

The answer is clear: no. You are dangerously bad at cryptography, and so am I. But, it does contain and illustrate some of the core ideas.

## Submitting

Submit your files through CourSys for Assignment 3.