Proof Of Work

Proof of work is one of the main ways used to secure the network of a lot of cryptocurrencies, it was the first used mining system and lasted quite a while with no competitor until Proof Of Stake started to take some of the control away, Proof Of Work is a beautiful concept that we can see in everyday life almost all of the time, for an example, if you’ve ever worked in a sales job, you’d know that you might have a certain target that you need to hit throughout the month, if you hit that target you get extra money, 
employee of the month or maybe even a promotion, hitting that target is proofing to the network that you did the work needed to sustain the network and you should be rewarded for that.

Same thing happens in every cryptocurrency that’s built on Proof Of Work, but instead of you working and hitting a target, you delegate that work to a CPU, GPU or an ASIC, which is an Application Specific Integrated Circuit. These devices use electricity as a resource and provide solutions to mathematical problems as an outcome, these mathematical problems
are mostly used to add blocks onto the ledger, Proof Of Work is used to sustain the security of the network in which you’d have to do the same amount of work to change a block that someone did to include it, and once more blocks are built onto that block, you’d have to do the cumulative work done by all these block discoverers just to change that block, so you’d have to have the processing power of more than 51% (sometimes less, sometimes more) of the miners just to be able to fiddle with the history of the transactions.

PoW relies heavily on something called a cryptographic hash function, a hash function is a function that takes in certain data and spits out a seemingly random string of characters that can be traced back to that data, hash functions used in cryptography are mostly fast to compute and even faster to verify, as we don’t want anyone checking a transaction in a block explorer to be doing significant amount of work, but we do want the miner including the blocks to work enough for it. Now to explain how PoW works, we’re going to take examples of two different approaches, one used in Bitcoin and the other used in Ethereum.

Bitcoin’s algorithm of choice is something called SHA256, it stands for Secure Hash Algorithm, which is an algorithm that relies solely on CPU cycles, the faster the CPU you’ve got the more “Hashes per second” you can compute, but what do we compute in the Bitcoin blockchain? Well if you look at any block on any of the blockchain explorers, you’ll find that the block includes quite a sum of data around it, most importantly for anyone using the chain, it includes the transactions, a hash of the previous block, difficulty and nonce. 
The transaction list is self explanatory, blockchain is a ledger that stores transactions so its quite normal to have them in each block, the hash of the previous block is used to create the chain effect as every hash relies on the hash of the block before it, that way as we mentioned before if you want to change a block in the middle of the chain, you’d have to also change the rest of the chain built on it.

Now we get to the most important thing PoW wise, the difficulty and the nonce. How mining happens in bitcoin is that we serialize all of the information in the block into one big string, then we enter that string into a double SHA256 function and out comes the block hash, but we want to make a competition out of this so that the whole mining network can race towards the solutions and the one who gets it first gets to make the block, and here comes the difficulty, a difficulty is basically a value that the block hash should not exceed, the difficulty is a number that changes every 2016 blocks depending on the strength of the mining network, as we want to have a solution every 10 minutes on average, so if our mining network consists of 10 super computers and another 10 join the network, we expect the difficulty to rise dramatically to adjust to the strength of competition. But if we only hash the block’s metadata we only get one hash and nothing more, the nonce’s function is that it is an arbitrary number that exists just to help the miners try out more hashes, as we know any cryptographic hash function will spit out a totally different result if a single number or character is changed in the string, so the nonce is usually used to change the input string to the function until we get a hash that is lower in value than the difficulty, once a miner finds this hash he is allowed to broadcast his block to the network and gets his Bitcoin reward. The beauty of the nonce here is that you can’t prematurely know what nonce will produce what hash until you actually calculate it, and you can never be sure which miner on the network is going to find it first, its all a statistics game.

Image provided by CryptoGraphics.info

One of the reasons developers started using different hashing algorithms in different coins is because of the CPU cycle advantage of the SHA256 algorithm, as it only relies on CPU cycles doing the same thing again and again, it wasn’t long before special hardware was produced just to mine Bitcoin, and people’s consumer grade CPUs and GPUs were left in the dust, some people argue that this hurts decentralization, as ASICs are more suitable for big factories and mining farms and not the average home miner, and that this could create a monopoly on the hash power in which only the big guys are able to compete. Through this came the dagger-hashimoto algorithm which is used by Ethereum, it was created to rely on not just CPU cycles, but also Input and Output operations done on Random Access Memory, which is mostly used in every consumer grade computer and is highly resistant to ASICs.

Dagger-Hashimoto is actually a two algorithms rolled in one, part dagger, part hashimoto. The Dagger algorithm was made by Ethereum co-founder Vitalik Buterin and Hashimoto created by Thaddues Dryja.

Dagger algorithm works by creating something called a DAG, it stands for Directed Acyclic Graph, which is something like a tree with a root node and children nodes with children nodes being able to have more than one parent, the Dagger algorithm works by creating ten levels of nodes with a total of 2²⁵- 1 values, every level’s nodes values depend on one or more of the earlier level nodes, and then the algorithm hashes some of the data computed in some of the nodes above combined with the nonce to produce a valid or invalid Proof Of Work depending on the difficulty, computing the DAG and storing it in RAM creates the memory hardness effect, but this was not found to be enough to force out the ASICs so the Hashimoto part had to be included.

Hashimoto algorithm uses the SHA256 as a building block, it firsts calculates a SHA256 hash of the previous block hash, the merkle root, which is a proof of the transactions included in the block, and the nonce. Notice here we do a single hash, not a double one like bitcoin. It then uses this hash to pick a transaction from the blockchain through a series of operations using bitwise shifting and modulo arithmetic. It repeats this operations a fixed sum of times until it has a fixed number of transaction Ids, it then XORs them all together and use this input along with the nonce to calculate the Proof Of Work.

Ethereum uses both these algorithms to provide a memory hard, Input/Output operations dependent algorithm which is highly resistant to ASIC miners and was thought to help decentralization but the usage of mining pools which further centralizes mining in a dozen points of service is still a concern for true decentralization. If you need to further read on both these algorithms, i advise you to read the whitepapers linked here for the Hashimoto algorithm and here for the Dagger algorithm.

This blog is the second of a series explaining the basic terms you’ll hear in block chain, if you find any mistakes or just want to have a chat, you can reach me on @TheIncrypt on twitter and you can also check the first of the series on decentralization in here!