Proof of work

General
,
1

cover_forum_blockchains-study
cover_forum_blockchains-study2400×1350 170 KB

This post is part of our Blockchains Study Group and the Cryptography series. Take a look there to learn more about related topics.

Prerequisite knowledge: Hash functions.

I found this video from the Binance Academy, a nice way to get started here.

Proof of work was initially proposed in 1993 as a way of attaching computational cost to resource allocation requests. It has also been proposed as a method for controlling spam, as a deterrent against denial-of-service attacks, for metering access, for verifying computations, for implementing delays, and as uncheatable benchmarks. [1]

This idea was then used in the Bitcoin whitepaper as a solution to the double-spending problem. If Alice has only 5 coins, she can transfer those 5 coins to Bob. If she later denied the transfer and subsequently transferred 5 coins to Charly, she would obviously be double-spending her coins. The state of the balance sheet or ledger tracking these coins would be internally consistent (since the transfer to Bob would be forgotten) but historically inaccurate.

Transactions in blockchains are changes in the state of the decentralized ledger, for example, the transfer of some coins from one account to another. Transactions are grouped into a block. The hash of the previous block (working as a unique and unforgeable identifier) is added to this block, which links them forming a chain.

The internal consistency of transactions within their block and with previous blocks can be easily verified by an honest client. However, in order to make sure that the transactions are effectively immutable, creating a block has to be hard and expensive. Introducing a block that contradicts or ignores part of the existing chain (by mistake or because Alice is evil) has to be more expensive than the potential reward earned by following the existing consensus of the blockchain.

The nodes of a blockchain network execute the proof of work algorithm to create a new block. This algorithm requires each participant to come up with a random number called a nonce, append it to the list of transactions that form a block, hash the block, and check if the resulting hash starts with a specified number of zeros. If it does not, they generate a new random nonce and try again.

The processor of the node machine will be generating many hashes until it succeeds, which makes it a CPU intensive task.

Due to the properties of hash functions, every nonce (and thus every iteration of the proof of work algorithm) has the same probability to result in the required value. Creating a block becomes a competition between all the nodes in the network. It is like a lottery. The nodes with a higher probability of finding the right nonce are the ones that can try more nonces in parallel.

This is what we call mining. Nodes that are successful earn a reward, which can come from newly minted coins, from fees paid by the senders of the transactions, or both.

When a valid block is mined, all the nodes update their state to accept the transactions it includes. Then they resume mining, trying to form a new valid block from all the transactions that are still pending.

Also due to the properties of hash functions, it is possible for two nodes to find a valid nonce at relatively the same time. If this happens, there will be two competing chains with different tips. The other nodes in the network will have to choose one of them before resuming their mining work, because the block they are trying to produce has to include the hash of the block at the tip of the chain. Eventually, one of the chains will clearly be larger. All the nodes still working on the smaller chain will jump to the larger chain, dropping all the blocks that were mined on their chain.

In a sense, proof of work uses the electricity required to run the hashing algorithm in order to provide security for the network. If an evil organization wants to introduce a block that doesn't follow the rules of the chain, making a double-spend, for example, they will need to have control over more than 50% of the hashing power of the network, which means to spend a lot of money in electricity.

Controlling the majority would allow an attacker to make a transaction transferring some coins from their account and let that chain continue until it has been acknowledged by the recipient. Then, they can start mining on top of the block that preceded their transaction and continue mining on this new alternate chain. Because they have the majority of hashing power, eventually, this alternate chain will be larger, and all the other nodes will drop the chain that included their transaction. With their balance state reverted, they can proceed to spend the same coins again. The original recipient will have their state reverted, too, but by this time they would have already provided the service to the attacker, with no way to recover for the loss.

Under normal conditions, it would be more profitable to spend less money, follow the rules, find the right nonce, and earn the rewards.

Before moving on, take a look at some interesting snips related to proof-of-work from my good friend and neighbor, Don Satoshi [2]:

[The peer-to-peer network] timestamps transactions by hashing them into an ongoing chain of hash-based proof-of-work, forming a record that cannot be changed without redoing the proof-of-work.

The proof-of-work involves scanning for a value that when hashed, such as with SHA-256, the hash begins with a number of zero bits. The average work required is exponential in the number of zero bits required and can be verified by executing a single hash.

We implement the proof-of-work by incrementing a nonce in the block until a value is found that gives the block's hash the required zero bits. Once the CPU effort has been expended to make it satisfy the proof-of-work, the block cannot be changed without redoing the work. As later blocks are chained after it, the work to change the block would include redoing all the blocks after it.

The proof-of-work also solves the problem of determining representation in majority decision making. Proof-of-work is essentially one-CPU-one-vote. The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it. If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains.

The probability of a slower attacker catching up diminishes exponentially as subsequent blocks are added.

To compensate for increasing hardware speed and varying interest in running nodes over time, the proof-of-work difficulty is determined by a moving average target.

Proof of work in Bitcoin

In his Mastering Bitcoin book, Andreas Antonopoulos gives a great explanation of the proof of work algorithm that Bitcoin uses. He includes a demonstration of a simple python script that hashes a nonce until it finds one that matches an expected value. I recommend reading that whole chapter.

A few important details specific to Bitcoin:

  • The hashing algorithm used for this proof of work is SHA-256.
  • The difficulty is a measure of how difficult it is to find a block that produces a hash that the other nodes will accept. In more simple terms, it tells the number of zeros at the start of a hash that the miners are looking for.
  • The difficulty is recalculated every 2 016 blocks (around two weeks). The idea is to keep the average time it takes to find a new block constant around 10 minutes.
  • If miners join the network, making the production of new blocks faster than 10 minutes, the difficulty is increased.
  • If miners leave the network, making the production of new blocks slower than 10 minutes, the difficulty is decreased.
  • It never changes by more than a factor of 4 to prevent large changes in difficulty.

To find other nitty-gritty details, read the pages about Difficulty and Target in the Bitcoin wiki.

Because the Bitcoin algorithm is completely CPU bound, the miners with the fastest and fanciest CPUs to execute SHA-256 hashes are the ones more likely to find a valid block. Many expensive ASICs have been produced to speed up Bitcoin mining, making it practically impossible for a normal computer to earn rewards. Without this economic incentive, most of the Bitcoin users don't even try to mine, centralizing the security of the network in the hands of the organizations that can purchase ASICs.

For this reason, many projects are trying to find better ways to produce and validate blocks without making the network insecure. Ethereum has made a few adjustments, so let's see that next...

Proof of work in Ethereum

Ethereum also uses proof of work, but the algorithm is different from the Bitcoin one. It is called Ethash. It is more complicated, but the idea is to make it a little more ASIC-resistant by using more memory than CPU.

This and other design objectives are explained in the article Ethash Design Rationale from the Ethereum wiki.

(1) The algorithm starts by computing a seed from the headers of the previous blocks.

(2) The seed is used to generate a 16 MB pseudorandom cache. This step with the small cache is used to simplify the work for Ethereum light clients, a topic we will explore elsewhere, maybe when covering the Ethereum-specific topic.

(3) From the cache, a 1 GB dataset is generated.

(4) Miners take random sections of this large dataset, hash them, and compare the resulting hash with the required difficulty to see if they have found a valid block. Note that here, instead of just using a random nonce that is immediate to generate like in Bitcoin, the Ethereum algorithm requires the miners to continuously read lots of data from memory.

(5) Every 30 000 blocks a new dataset has to be regenerated.

In Ethereum, the difficulty tries to generate a new block a lot faster than in Bitcoin. Every 12 seconds on average.

And remember how we described above when two valid blocks are found almost at the same time, but only one of them is eventually valid, and the miner of the discarded block is not rewarded? This is a little different in Ethereum. It introduced the concept of ommers, which allows the miners of valid blocks that are not part of the longer chain to earn partial rewards.

The Ethash article in the Ethereum wiki has many more technical details about this proof of work algorithm.

In the end, this algorithm is not ASIC-resistant either. It just made the job harder to produce Ethereum ASICs. The next step in the evolution of blockchains seems to be Proof of Stake, a completely different way to produce blocks and secure the network. That will also be the next step in our Blockchains Study Group. If you are curious about this, jump in.

References and more learning resources

2 Likes