BSV Academy Logo over wireframe concept

Ch5: The Bitcoin white paper - Proof-of-Work

Oct 27, 2022

The BSV Academy’s free introduction to Bitcoin Theory course covers the design of Bitcoin as a system as prescribed by Satoshi Nakamoto. This course is open to anyone who is interested in Bitcoin and is the beginner course in this series. Some technical experience would be helpful to complete the course, however, it is open to anyone regardless of experience.

The course goes through the Bitcoin white paper section by section elaborating on the concepts contained within each. This section focuses on the concept of Proof-of-Work and why it is integral to the BSV blockchain.

To make it as effortless as possible for you to have access to this educational material, we are publishing the entire course here on our blog. Stay tuned for a section-by-section release, and remember that you are still welcome to enrol in the BSV Academy to gain a certificate of completion to add to your resume.

Proof-of-work

To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proof-of-work system similar to Adam Back's Hashcash, rather than newspaper or Usenet posts. 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.

For our timestamp network, 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.

Proof of work illustration

The proof-of-work also solves the problem of determining representation in majority decision-making. If the majority were based on one-IP-address-one-vote, it could be subverted by anyone able to allocate many IPs.

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.

To modify a past block, an attacker would have to redo the proof-of-work of the block and all blocks after it and then catch up with and surpass the work of the honest nodes. We will show later that 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 targeting an average number of blocks per hour. If they're generated too fast, the difficulty increases.

Hashcash

To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proof-of-work system similar to Adam Back's Hashcash [6], rather than newspaper or Usenet posts.

- Satoshi Nakamoto, Bitcoin Whitepaper

Proof of work demonstration

The implementation of Bitcoin’s distributed timestamp uses hash-based proof-of-work to give nodes the ability to demonstrate their willingness to both invest in network infrastructure and place operational expenditure at risk via the hashing competition.

Hashpower can be dynamically deployed giving owners of hashing machinery the ability to vote for nodes they believe are most capable at gathering and timestamping events. Hashcash was originally conceived as an anti-spam measure for email inboxes and was intended as a means to set a price on sending an email to disincentivise the creation of the hundreds of billions of spam emails that are sent every day to user inboxes.

In the context of Bitcoin, the proof-of-work is used as a signal from one node to another that they are a capable and dedicated player on the network whose block solutions deserve consideration for insertion into the chain.

This is important because the cost of one node connecting to, receiving and validating a block from another node is not trivial. Famously, this solution solves the Byzantine Generals Problem* which has long stood in the way of the implementation of distributed computing networks that do not require a central governance system.

*Byzantine Generals Problem is a term used in computing to explain a situation where components of a system may fail if participants don’t agree on a strategy to deal with the problem. The problem assumes that some of the participants are bad actors who may spread misinformation or are in some way unreliable.

Imagining a war where many different armies must work together to conquer a common enemy in a situation where there are an odd number of armies, common consensus must be reached in order to successfully attack. But, certain generals of some armies choose to disagree, leading to a critical system failure.

This failure is known as a Byzantine Fault, in computing this is when it is unclear whether a component in a network is working properly or not. In Bitcoin each node is considered a ‘general’ who contributes to the consensus of a network.

Scanning random space

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.

- Satoshi Nakamoto, Bitcoin Whitepaper

Proof of Work Demonstration

The proof-of-work process involves taking a block header which is arranged in a pre-defined format and using it plus a ‘nonce’ value (a nonce is an arbitrary number that can be used just once in cryptographic communication) as the message to be hashed.

The node passes out block headers containing a hashed record of all the transactions the block includes plus a timestamp and a unique identifier to hash machines whose hashing power is being applied to solving its block.

Critically, validation of the proof-of-work is as simple as hashing the block header including the winning nonce value. Nodes do this before verifying the block’s contents to ensure they are working on a block solution which has been solved by a capable node.

Learn more about Block headers here.

Nonce

For our timestamp network, 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.

- Satoshi Nakamoto, Bitcoin Whitepaper

Proof of Work table

What is a Nonce?

A Nonce is a ‘Number used ONCE’ and is the means by which the block header is iterated during the proof-of-work process. A section of the block header is changed by a small amount each time so that a new hash can be calculated from the number.

A Hash is a one-way function which takes a given input and produces a deterministic output. Someone given the output cannot reveal the input, but anyone with the input can verify its authenticity if its hash is public.

The hash machines take the block header and begin testing different message hashes by incrementing the 4-byte nonce value and re-hashing the message as many times as possible per second. A block is solved when a hash machine finds a nonce value that when combined with the block header creates a message that hashes to a value which is less than the difficulty target which is stored in the block header as a 4-byte floating point number.

Thanks to optimisations in hardware, most hashing machines can cycle through the approx. 4.3 billion different values the 32-bit nonce can represent in a matter of seconds, so further ‘Extra Nonce’ fields are used within the coinbase transaction to increase the amount of hashing each hash machine can perform on a given block template by causing a change to the merkle root.

Learn about Nonce.

Immutable work

Once the CPU effort has been expended to make it satisfy the proof-of-work, the block cannot be changed without redoing the work.

- Satoshi Nakamoto, Bitcoin Whitepaper

Immutable work blockchain example

The nature of proof-of-work is that it can only be attempted upon a fixed block of information. In this way, capable nodes will always ensure that power expended performing proof-of-work is used on blocks that are fully complete and do not waste energy. Once discovered, a block with a valid proof-of-work solution cannot be modified in any way without changing its message hash and invalidating the work.

Nodes who waste hashpower will find that the owners of the hashpower soon migrate to other more capable nodes, reducing their ability to generate blocks and cutting their revenue generating ability. This incentivises all nodes to act with honesty and to create blocks that are both valid and economical.

Chain effort

As later blocks are chained after it, the work to change the block would include redoing all the blocks after it.

- Satoshi Nakamoto, Bitcoin Whitepaper

Once a block has been created and accepted as valid by other nodes on the network, the network collectively begins trying to build the next block using the hash of this block as part of the new block header.

Every block since the Genesis block is built upon a previous block in the chain, so overwriting information stored at a certain point in the chain would require the proof-of-work on the block containing the information being overwritten, and every block discovered since in order for the network to recognise the new version of the time chain as valid history.

Anyone seeking to overwrite a transaction using this method must build the new proof-of-work chain and outpace the constantly lengthening chain-tip for their blocks to be considered as valid, making it computationally impractical to erase information that has been captured in a block.

In this way, information contained in blocks that have an established quantity of proof-of-work on top of them are considered unchangeable, or immutable.

One CPU, one vote

The proof-of-work also solves the problem of determining representation in majority decision making. If the majority were based on one-IP-address-one-vote, it could be subverted by anyone able to allocate many IPs. proof-of-work is essentially one-CPU-one-vote.

- Satoshi Nakamoto, Bitcoin Whitepaper

One CPU One Vote Demonstration

The very nature of proof-of-work is such that it cannot be faked, misrepresented or otherwise falsified. Without a Central Processing Unit (CPU) to cycle through combinations of nonce and block header, a node cannot participate in the block building process.

Because proof-of-work requires the accumulation of infrastructure and the expenditure of energy, there is an inherent need for any node that wishes to participate in the activity of block building to have CPU power available to it in order to continuously process new combinations of block header and nonce to solve proof-of-work.

A system such as one-IP-address-one-vote or proof of stake can be gamed by accumulation of resources that aren’t representative of an investment in the reliability and security of the network. This discourages investment in network infrastructure as any costs related to the construction of more capable hardware takes away from the node’s accumulated holdings reducing the node’s ability to monetize its position.

In this way these methods of achieving consensus can be shown to create instability and reduced levels of investment in the network.

It is only via proof-of-work that all network participants can be evaluated on an even footing as to their node’s capability and suitability to create blocks and to receive votes from hash generating CPUs. This system incentivises a race to find the most efficient ways of processing block headers and has already led to advances in hardware driving the block difficulty rate up many orders of magnitude since the beginning of the network.

The majority decision

The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it.

- Satoshi Nakamoto, Bitcoin Whitepaper

Node Majority Decision

At any given moment, it is possible for anyone to look at the longest chain of blocks that has been produced to determine where the greatest amount of work has been applied by multiple unconnected parties. This enables users of the network who are not interested in participating in the creation of blocks to become simple observers of the chain.

The accumulated proof-of-work of the whole network acts as a signal that highly invested parties have come to agreement as a means to determine the validity of any given block or transaction.

From time to time, competing chain-tips will emerge, however in time the competitors in the network will always unite their effort back to a single point upon which the cumulative power of all nodes is applied as a foundation for the continuance of the chain.

The honest chain

If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains.

- Satoshi Nakamoto, Bitcoin Whitepaper

Honest Chain Example and Demonstration

As long as more than half of the CPU power used to perform proof-of-work is controlled by honest nodes, the honest chain will remain the longest chain and the most easy to follow chain by the users of the network. This is true even when a chain tip is extended by nodes who use their hashpower to accept a set of dishonest transactions, or to enforce rules that go against the will of the honest nodes in the system.

Importantly, while a set of dishonest nodes is able to extend their chain faster than the cumulative effort of the honest nodes in the system, their chain will have the appearance of representing the longest chain of proof-of-work to casual users of the network. However, for the dishonest nodes to maintain their lead and retain the longest chain they must continuously perform proof-of-work at a rate equal or greater than that of the honest chain for an indefinite period.

This strategy is extremely costly to pursue. This shows that the network incentivises honest behaviour by allowing honest nodes to continuously work without the need to aggregate resources to pursue a dishonest end.

Attacking the longest chain

To modify a past block, an attacker would have to redo the proof-of-work of the block and all blocks after it and then catch up with and surpass the work of the honest nodes. We will show later that the probability of a slower attacker catching up diminishes exponentially as subsequent blocks are added.

- Satoshi Nakamoto, Bitcoin Whitepaper

Attacking the longest chain example

Thanks to the cumulative nature of Bitcoin’s proof-of-work process, it can be shown that for an attacking node to overwrite a particular block or record which has already been built upon by the honest operators on the network, they would first have to create a competing block.

This block includes or excludes the information targeted by the attack before creating a new chain of blocks that is longer than the existing chain of honest blocks being built upon by the network.

In order to uphold the fraud, the dishonest nodes must now also perform enough proof-of-work to generate new blocks at a rate that exceeds the generation of the honest blocks for as long as they require to perpetrate their fraud. They must do so in a way that is completely public, exposing their dishonesty to the entire world and leaving a direct trail to their system for law enforcement to follow.

It should be noted that as the requirement for proof-of-work grows with the size of the network as a whole, the operation of a node leaves a larger and larger footprint that becomes near impossible to hide. Thus, further disincentivizing dishonest behaviour to the ease of identifying the dishonest actor.

In a subsequent section of the whitepaper, Satoshi uses mathematics that show the difficulty of creating and maintaining a competing dishonest chain, which we will cover in a later section of this module.

Controlling the block discovery rate

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 targeting an average number of blocks per hour. If they're generated too fast, the difficulty increases.

- Satoshi Nakamoto, Bitcoin Whitepaper

Controlling the block discovery rate

In order to allow for node operators who invest in more efficient hardware to help discover more valid blocks through the proof-of-work process, the network uses an algorithm that adjusts the network difficulty to maintain a steady rate of block discovery no matter how many CPU cycles are applied to the proof-of-work process.

The original Bitcoin client updated the difficulty target every 2016 blocks to try and control the block discovery rate to a speed as close to 6 blocks per hour as possible, however the current difficulty adjustment algorithm changes the rate every block in an attempt to compensate for the dynamics of the multiple competing SHA256 chains that currently exist.

The difficulty algorithm will be adjusted back to the original 2016 block adjustment rate in the near future.

This results in an ideal average of 144 blocks per day and means that the nodes would update the difficulty target every 2 weeks in a case where the network hashrate remained relatively static. The reality is that the block discovery process is a randomised process and can result in blocks being discovered at constantly changing rates.

Learn more about the Bitcoin blockchain here.

Learn more about Bitcoin as Timechain here.

Ryan Brothwell
Ryan Brothwell

Deputy Editor, Bitcoin Association