proof-of-work based blockchain explained with golang
by Emile `iMil' Heitor - 2019-10-12
Yet another “blockchain explained” article, I know, I really thought about if releasing it or not, but you know, you only understand what you can explain clearly, so I hope I’ll be able to explain proof of work and blockchain as clearly as it is clear in my mind.
The originality of this post is that I’ll try to make those concepts clear through pieces of code extensively explained so it doesn’t feel like a theoretical expose where you get the idea without the taste.
First thing first, as you probably have read 1M times, a blockchain is, well, a chain of blocks. Yeah thank you iMil that was helpful. From a coding point of view, this seems like an inverse linked list. Remember?
---------------- ---------------- ----------------
| data: first | | data: foo | | data: bar |
| addr: 0x1000 |<-. | addr: 0x1001 |<-. | addr: 0x1002 | ...
| prev: 0x0 | \| prev: 0x1000 | \| prev: 0x1001 |
---------------- ---------------- ----------------
Those are blocks, and the block n+1
has a reference to its predecessor thanks to the prev
element, which points to the addr
from the previous block. I present you a blockchain :)
There are plenty of very well put articles and videos explaining how this helps making an unmodifiable list, this one is probably one of the best I’ve watched.
Actually, known blockchains use hashes
as their parent reference, and this is where the fun begins. What is the actual hash
using as reference from one block to its parent? Well, it’s the solution to a puzzle. Or more precisely, the result of a proof of work.
Consider the following structure:
type Block struct {
Index int
Timestamp int64
Hash []byte
Data string
PrevHash []byte
}
Let’s produce some data with it, for example, by adding two structure members. To give an idea, Data + PrevHash
would produce a certain amount of data, which in turn we could use to make a sha256 hash
.
This would give us this type of function:
// data is of type Block.Data, and prev is Block.PrevHash
func genhash(data string, prev []byte) []byte {
// merge data and prev as bytes using bytes.Join
head := bytes.Join([][]byte{prev, []byte(data)}, []byte{})
// create a sha256 hash from this merge
h32 := sha256.Sum256(head)
fmt.Printf("Header hash: %x\n", h32)
// sha256.Sum256() returns a [32]byte value, we will use it as a []byte
// value in the next part of this article, thus the [:] trick
return h32[:]
}
From this value we will now try to solve a puzzle. There could be many ideas of such puzzles, but the one used in Bitcoin and many more cryptocurrencies is to find a number (called a nonce), which when added with the hash
we got from adding struct
values, will produce a result inferior to a determined target.
This target, again in this scenario, is a binary number beginning with difficulty * number of zeroes
. I.e. if difficulty = 5
, the puzzle solution is a number inferior to a number obtained by left shifting 1
from 256 - 5
(256 being the hash size and 5 the difficulty), so in binary form, 1
followed by 251 zeroes.
The process of solving this puzzle is called mining and as the correct hash
has been found, it can be easily verified by anyone by adding the header values with the nonce and thus proving there was a work to find it. Once done, this process validates the block, which can then be added to the blockchain.
Here’s what this code look like:
// the receive bytes represent the previously generated header hash
func mine(hash []byte) []byte {
// we use math/big in order to manipulate big numbers
target := big.NewInt(1)
// this is the left shift creating the target puzzle
target = target.Lsh(target, uint(256-difficulty))
fmt.Printf("target: %x\n", target)
// this is the value that will be incremented and added to the header hash
var nonce int64
// Now loop until max int64 size is reached, this is 100% arbitrary
for nonce = 0; nonce < math.MaxInt64; nonce++ {
// create a new test number
testNum := big.NewInt(0)
// sum header hash with the nonce
testNum.Add(testNum.SetBytes(hash), big.NewInt(nonce))
// and create a hash from it
testHash := sha256.Sum256(testNum.Bytes())
fmt.Printf("\rproof: %x (nonce: %d)", testHash, nonce)
// is the target number (0x8000...) bigger than our created hash?
if target.Cmp(testNum.SetBytes(testHash[:])) > 0 {
// if yes, we solved the puzzle
fmt.Println("\nFound!")
// again, sha256 returns a [32]byte, return type is []byte{}
return testHash[:]
}
}
return []byte{}
}
Now all we need to finish this exercise is to actually create blocks and piling them up, we will use a simple string slice with some data in it:
func main() {
// here is the string slice
bdatas := []string{"Genesis", "2d block", "3rd block", "4th block"}
// we do not have previous hash
prev := []byte{}
for i, d := range bdatas {
// create the new block
b := NewBlock(i, d, prev)
fmt.Printf("Id: %d\nHash; %x\nData: %s\nPrevious: %x\n",
b.Index,
b.Hash,
b.Data,
b.PrevHash,
)
// and record current found hash for future block
prev = b.Hash
}
}
The NewBlock
function is pretty straightforward, it returns a complete block, which hash has been mined using its header hash
func NewBlock(id int, data string, prev []byte) *Block {
return &Block{
// block Index
id,
// current Unix time
time.Now().Unix(),
// first compute a hash with block's header, then mine it
mine(genhash(data, prev)),
// actual data
data,
// reference to previous block
prev,
}
}
Fully working code for this example is available here, try increasing the difficulty
and witness the time to solve the puzzle increase.
This exercise is really the tip of the blockchain iceberg, yet I find it is the building block (pun intended) of a proof-of-work based one. Hope I manged to demystify these concepts as clearly as I picture them today, if you feel something written here is wrong, please leave a comment and I’ll try to fix it the best way I can.
Many thanks to Jeiwan for his fantastic blockchain implementation in golang, which has been a great source of inspiration for this article.