Proof-of-Work

In discussing the simple genius of the Difficulty adjustment, we introduced the topic of Proof of Work.

A quick background, and then we’ll dive into the details.

Proof of Work (PoW) was not invented by Satoshi, but rather the concept was introduced by Adam Back’s Hashcash in 1997 as a method for deterring malicious behavior online – for example, to deter emailers from spamming you.

Later, in 2004, Hal Finney built upon this principle to introduce the concept of Reusable Proofs of Work (RPOW) which allowed for the creation of scarce digital tokens without a double-spending problem, but critically employed the use of a centralized server to ensure the uniqueness of each token.

It wasn’t until Satoshi invented Bitcoin in 2009 that Proof of Work was used as a consensus mechanism for achieving agreement on the state of a ledger across a decentralized network of nodes.

This background illustrates two things: 1) Satoshi didn’t invent Bitcoin from scratch, but rather stood on the shoulders of giants and synthesized many different concepts that came before him in a unique and elegant way; and 2) Proof of Work, like Bitcoin itself, is actually many things in one:

1. Proof that a certain amount of computational effort has been expended
2. A consensus mechanism for decentralized systems
3. A timestamping service which solves the double-spend problem without requiring a trusted third-party
4. “A way to allocate the initial distribution of currency” (Satoshi, in an email to Martii Malmi, May 2009)

But what, though, is the “work” being done? And how is it being “proved”?

The “work” in proof of work being done is to solve a complex math problem which can only be solved via a brute force “guess-and-check” method. The computational effort required to solve Proof of Work problems is directly related to energy consumption, measured in watts, embedding the blockchain within the laws of physics and imposing a real, physical cost on those participating in the network.

Porting physical security into the digital world is a profound invention in and of itself, and it is possible we are only just beginning to understand the implications of this new technology.

The “proof” that the required amount of work has been done lies in the finding of a solution to the math problem itself. Although the problem is arbitrarily difficult and requires significant computational resources to find a solution, once a solution has been found it is trivially easy for others on the network to verify its correctness, simultaneously “proving” that the required amount of work – real world energy expenditure – has been completed to add a new block to the blockchain.

Bitcoin miners engage in a global competition to find a solution to the math problem first, giving them the right to add a new block of transactions to the blockchain and earn the block subsidy and fees included in that block.

Specifically, Bitcoin’s Proof of Work algorithm asks miners to find an input value, called a nonce, that when passed through a hash function produces an output, called a hash, that satisfies the conditions set by the bitcoin network.

A hash function is a cryptographic function that takes any digital data as input and produces a unique output, called a hash. For the same exact input, the hash function will always produce the same exact output. But if you change any one little thing about the input (say, one word in a document), it will produce an entirely different, seemingly random output. Crucially, the input is not able to be known from just knowing the output – the hash function cannot be reversed.

The input to a hash function can be any form of digital data – a number, piece of text, image, or video, for example. For bitcoin, the input includes the nonce (the number the miners are trying to guess via guess-and-check), as well as the previous block’s hash, and a list of all the transactions to be included in the new block.

The cryptographic hash function used by bitcoin is SHA-256, which stands for Secure Hash Algorithm 256 bits. It takes in this data as input, and produces a 256-bit hash as output. This hash takes the form of a 64-character hexadecimal number, for example:

4E75EAFD9D8A100B5D9D4576D8EAF8D4B6975DFD9D4E75EEAF8D4B6975DFD9D4

In hexadecimal notation, each character represents a value from 0-15, using the numbers 0-9 and the letters A-F to represent values ten through fifteen.

The math problem miners must solve is to find a nonce that, when combined with the other block data and run through the hash function, produces a hash that is below a certain threshold. To increase the difficulty of finding such a nonce, the difficulty adjustment algorithm will lower the threshold.

To help understand this, imagine if the hash was just a number between zero and one million. Your goal is to guess an input value that, when run through the hash function, produces a number below a certain threshold.

If the threshold was 999,999, this would be very easy and you would probably get it on your first try as almost all possible inputs will produce a hash below the threshold.

If the threshold was 500,000, it would be more difficult and likely take more guesses, as only 50% of possible inputs will produce a hash below the threshold.

If the threshold was one, it would be much harder and likely take many guesses. Every guess would have only a one in a million chance of producing a hash below the threshold.

In SHA-256, instead of one million there are 2^256 possible hashes. Or, in decimal notation:

115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,560,000,000,000,000,000,000,000,000,000

This makes it so that:

1. There is a vanishingly small probability that the same hash will ever be produced for two different inputs.
2. The bitcoin difficulty adjustment algorithm can continue to adjust the threshold “x” downwards to make it arbitrarily difficult to “find a nonce that produces a hash below threshold x.”

As such, if over time the bitcoin network brings on, say, a thousand times more compute to try and guess a nonce that meets the criteria set by the network, the network can adjust to make it a thousand times more difficult to guess such a nonce.

Or vice-versa – if a significant amount of miners leave the network abruptly for any reason, as happened when China banned bitcoin mining in June 2021, the difficulty adjustment will make it so that it is easier to guess a valid nonce, with the goal always being that it takes the entire network 10 minutes to guess a nonce that meets the criteria.

That a solution has been found to the math problem serves as “proof” that enough “work” was done – enough compute was brought to bear –  by the network to mine a new block and earn the block subsidy.