Assignment 3: Blockchains with Go
Introduction
For this assignment, you will be building functionality to create a simple
blockchain (https://en.wikipedia.org/wiki/Blockchain) system. Our blockchain will include a proof-of- work (https://en.wikipedia.org/wiki/Proof-of-work_system) , so we will have to do some computation to create valid blocks.
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 (https://en.wikipedia.org/wiki/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 from the chain and believe that its hash is valid, then you can also verify block . Block must hash to the ¡°previous hash¡± from block . Similarly, you can verify blocks , ….
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 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, that the last bits of the hash value (including the proof in the data that is hashed) be zero. only be considered valid if its hash ends with zero bits.
the hash
and insist A block can
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 (so the last 2 bytes = 4 hex characters are zeros), we end up with a blockchain that looks like this:
1/7
Block 0 Block 1 Block 2
Prev Hash: 00000000 Data: “”
Other stuff: …
Proof: 7386
Hash: bde0f90000
Prev Hash: bde0f90000 Data: “first message” Other stuff: …
Proof: 79359
Hash: 323b2b0000
Prev Hash: 323b2b0000 Data: “more message” Other stuff: …
Proof: 26090
Hash: 4aa4020000
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 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.
2/7
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 (https://golang.org/pkg/encoding/hex/#EncodeToString) ; 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.]
3/7
We will use the SHA256 (https://golang.org/pkg/crypto/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<