Understanding of Bitcoin Part 4:  Nakamoto Consensus, Proof of Work Mechanism

Understanding of Bitcoin Part 4:  Nakamoto Consensus, Proof of Work Mechanism
Understanding of Bitcoin Part 4:  Nakamoto Consensus, Proof of Work Mechanism. Image by Freepik

Understanding of the Bitcoin Series 

1. Understanding of Bitcoin: Need for decentralization and paradigm shift to Web 3.0 

2. Understanding of Bitcoin: Cryptographic principles of Bitcoin, transactions, and the double-spending problem.

3. Understanding of Bitcoin: Explaining PBFT Algorithm and its Applicability in Bitcoin Network

4. Understanding of Bitcoin – Nakamoto Consensus, Proof of Work Mechanism.

Short Summary

  1. The basics of blocks and UTXO in the Bitcoin network. A block is a unit that enables consensus and state synchronization within the network. It is a collection of transactions that do not contradict each other and processing them to create a block state. UTXO refers to the amount of Bitcoin remaining idle in a particular transaction. Furthermore, it is a fundamental concept that helps ensure the validity and security of transactions. 
  2. The Nakamoto Consensus and Proof of Work Mechanism. They are critical components that ensure the security and integrity of the Bitcoin network. It explains how miners compete to solve complex mathematical puzzles to validate transactions and create new blocks in the blockchain.
  3. PoW requires computing power to validate transactions and create new blocks in the blockchain. This makes it difficult for malicious actors to manipulate the blockchain. Mining is the process of repeatedly trying various values to find a Nonce value that satisfies a specific condition and can be hashed. Miners compete to create new blocks behind the currently propagated block. Successfully mining will receive rewards. (Nakamoto-Consensus-Proof of Work)

1.0 Block and UTXO (Unspent Transaction Output)

Let’s Summarize the contents of the previous post briefly.

1. DAG (Directed Acyclic Graph) — It is a non-cyclic graph concept opposite to cyclic graphs. The characteristic is a single direction, which means that the algorithm has a unidirectional flow. This is a key feature of blockchain, the irreversible unidirectionality property, and it is a similar concept.

2. UTXO (Unspent Transaction Output) — It is a lump of stagnant bitcoins. The unit of the transaction (Tx) has not undergone any changes in ownership transfer. It is an unspent output value.

A Block is a unit that enables consensus and state synchronization within the network. Each block is formed by collecting transactions (Tx) that do not contradict each other and processing them to create a block state.

Each transaction has a partial order and forms a Directed Acyclic Graph (DAG). The set of UTXOs of the last transactions on the DAG graph represents the block state. The block state is not explicitly recorded in the block but is expressed as the sum of UTXOs.

Blockchain 

The state of a block in a blockchain is represented as the sum of the structure of UTXOs within the transactions (Tx) that are included in the block. Each block serves as a unit for consensus and state synchronization within the network. Transactions with no mutual contradictions are collected and processed to create the block state, forming a Directed Acyclic Graph (DAG) with a partial order. The set of UTXOs of the last transactions in the DAG graph represents the state of the block.

The state of the block is not explicitly recorded in the block but is represented as a sum of UTXOs. When a block is completely processed by the occurrence of transactions within it, the next block is created based on the summary data of the previous block state, which refers to the accounts’ financial state in the network. This forms the basis of the blockchain.

As the block progresses, the financial state is fragmented and updated on a block-by-block basis. All transactions within every block from the genesis block to the current block are executed sequentially, and the resulting state of the current block’s Tx information is the final financial state maintained by the Bitcoin network. Therefore, to view the latest financial state of Bitcoin, one must check the state of the synchronized UTXOs of the last block.

Genesis Block​

The genesis block, which contains the transaction history of Satoshi Nakamoto’s anonymous wallet, is the first block ever created that birthed the Bitcoin network.

This is the first block, called the Genesis Block, that was created by the anonymous Satoshi Nakamoto and contains the transaction that gave birth to Bitcoin. It was created on January 9, 2009, and has a difficulty of 1.00. The block includes only one transaction, and the miner (or miners) who mined the block received a block reward of 50 BTC. The identity of the miner(s) is unknown.

Current Block

It is the latest block that contains all the previous transactions that have been excavated so far.

This is the current Block while I am writing this article. Transaction date: April 1st, 2023. Miner: Binance Pool Number of transactions: 3121 Difficulty: 46,843,400,286,276.55 Block reward: 6.45480561 BTC

(*By accessing the Blockcahin.com website, one can transparently verify the state of all networks and blocks in the Bitcoin network.)

2.0 Gossip/Epidemic Protocol -Block Propagation

We have confirmed that the state of financial transactions is stored in a block in the financial system. Furthermore, these blocks contain financial states that serve as a consensus unit. It sequentially verifies the verification records of all blocks whenever a new block is created. It also records the most up-to-date financial state in the last current block.

So, let’s summarize how the state of a block is propagated in the network to create the latest state of the most recent block containing previous transaction history.

The process of a block in the blockchain conveying and synchronizing information with other nodes in the network is based on the Gossip Protocol, which is a propagation system of P2P networks.

A P2P system refers to a horizontal network connection structure between nodes. Therefore, P2P systems are computing systems in which nodes share and exchange resources and information with each other through a horizontal connection network.

(All entities participating in the P2P system network are nodes.)

Existing P2P network propagation methods have various ways. I will briefly explain why these methods are inefficient on the Bitcoin network by looking at two representative methods.

One Node Broadcasting Block Information to all Nodes

If one node tries to broadcast block information to all nodes, the time it takes to synchronize the information on all nodes is proportional to the number of nodes participating in the system. This results in a part of the node’s bandwidth, which is the limit on the number of messages a node can propagate per second, being very inefficient.

Tree-based Propagation Method

If we select certain blocks based on some of the few blocks that participate in the system and propagate data in a tree structure, we can solve the problem that arises from bandwidth. However, there is a limitation. If the core block of the root that delivers information on the blocks in the system disconnects, all the blocks included in that root cannot receive data.

Gossip Protocol

Image from Altervista

Therefore, in blockchain, the way to propagate blocks or transactions to the network is adopted through the Gossip Protocol. It is also known as the Epidemic Protocol. As the name implies, the Gossip Protocol is the process of propagating information among nodes spreading like a rumor. As shown in the picture, one node passes information to its neighboring blocks. It then propagates like rumors until the financial information contained in the blocks converges into a single block. This will overcome the aforementioned limitations.

In other words, all nodes have the same financial information in their blocks. When all nodes have the same financial status, they reach a ‘synchronized state’. Only then can the network create the next block. This method of each node in a P2P network propagating data to its neighboring nodes can quickly propagate and synchronize data while reducing bandwidth waste. Most blockchains adopt this method, including Bitcoin.

3.0 Bitcoin Network Race Condition

However, the gossip protocol propagation method still faces an unresolved issue within the Bitcoin network. The concern lies in determining which synchronized block will be chosen to create the next block.

Bitcoin is an open (public) network where anyone can create a block. However, it is a system where anyone can create a block. Therefore, there is a possibility that all nodes may create blocks haphazardly. There is also a possibility that another block may be created at a point where the state of one block has not been fully updated and synchronized across the entire network.

This also raises the issue of the Singleton Current State problem. It is an issue where not all blocks can maintain the same financial state.

Image from braiins

Let us consider that we have found a new green block in the synchronized red blocks shown in the picture. Each node with the consensus function verifies the state of the new block. Once the verification is complete, the new block is added to the blockchain network.

Singleton Current State Problem

In the same way as the gossip protocol propagation method, the synchronization of red-colored blocks in the picture presents an unsolved issue within the Bitcoin network. The concern lies in deciding which of the many synchronized blocks will create a new block. Bitcoin is an open (public) network where anyone can generate a block. However, if anyone can create a block, all nodes might create blocks randomly. This leads to the possibility of generating another block at a point where the state of one block has not been updated or synchronized with the entire network. Moreover, this causes problems with the “Singleton Current State” issue, where not all blocks can maintain the same financial state.

Assuming that a new green block has been discovered in the synchronized red block, as shown in the picture, each node with consensus functionality verifies the state of the new block. Once the verification is completed, the blockchain network generates a new block.

However, if anyone can create a block as mentioned above, various issues arise on the network. For instance, in the picture, if the orange block discovered a new block and synchronized it with other blocks to form a single financial state, but the green block also discovered a new block simultaneously, then nodes that exist between the creation of the orange and green blocks within the free-to-join Bitcoin network collide, raising a conflict on which block’s new financial state to propagate. In such a case, blocks cannot synchronize with a single block’s state. This causes a problem known as a race condition in computer science. It indicates that the propagation process of orange and green blocks is in a race or competition.

Therefore, these issues demand that the Bitcoin blockchain network requires a new consensus algorithm.

4.0 Cheat Resistant Timer

The solution to these problems is the Cheat Resistant Timer, also known as the Random Timer. It allows anyone to generate blocks and reach a unified latest state. The Random Timer is a timer within the blockchain network for creating new blocks. It generates a random time for anyone to create a block once the timer has expired. By introducing the Random Timer and intentionally slowing down the block generation speed, it resolves the problems mentioned earlier. In other words, if the block generation speed is slow, all nodes can synchronize with the same block state. It can also create and propagate new blocks, and form a single global state.

Therefore, Satoshi Nakamoto explained that his consensus algorithm relies on the principle:

“If the average time for the random timer to expire is similar to the time it takes for blocks to propagate in the Bitcoin network, an optimized result can be obtained, where the network converges to a single block and not flooded with blocks.”

The process of creating a block involves consuming a certain amount of computing power and sealing it with proof (a newly found Nonce value with a certain probability). The process involves repeatedly attempting to change the Nonce included in the block while satisfying specific conditions. This approach of creating a random timer is Nakamoto consensus, most commonly known as proof-of-work.

​5.0 Proof-of-Work (PoW)

The Proof of Work (PoW) consensus mechanism is a process that expends a certain amount of computing power to increase or randomly change the value of the Nonce field. It is a recorded number included in a block until a block is found with a Nonce value that satisfies a specific condition and can be hashed. The Nonce value that can meet the condition is probabilistic, and the more attempts (trials) made, the higher the probability of finding a block that meets the condition. Hashing is a process of mapping arbitrary data of various lengths into fixed-length string values, representing one-way functions that denote data values.

To illustrate this, let us consider a casino slot machine. When a user pays money to play the game, the slot machine provides an opportunity to pull a lever. It has a probability value of winning 777. The value of 777 in the slot machine is highly probabilistic. Furthermore, the probability of winning 777 increases as the user repeats the trial of pulling the lever, and spending their money. This means that if multiple slot machines are run simultaneously, not just one, the chances of winning increase while reducing the time to win.

After continuously spending money on multiple slot machines to find 777, the slot machine Seals (marks) the evidence of the user’s win and issues a cash-out paper. If the user shows the marked paper with the evidence to a casino employee, they can receive the prize money. This is similar to the process of finding a specific nonce value in Bitcoin or blockchain by expending a certain amount of computing power to find a nonce value that satisfies the conditions of a block and then sealing (hashing) it.

An Example

Image from Pooled Mining Makes Selfish Mining Tricky, Suhyeon Lee

On the Bitcoin network, the hash value of the previous blocks and various other fields are combined. The block header, including the Nonce value, inserts into the SHA 256 Hash function until it finds a value smaller than a certain difficulty. The Hash value found by inserting the hash function becomes the Block Hash value of the block.

Through the avalanche effect, even a small change in input results in a significant change in output. When a specific Nonce value that can only be obtained by repeatedly trying various values is found, a new block is propagated on the Bitcoin network.

Mining is the process of repeatedly trying various values, similar to the hard work and laborious process of obtaining gold or diamonds. Therefore, a complex consensus algorithm, the Proof of Work, prevents the creation of new blocks before the block propagates to 90% of the nodes on the network. Anyone can create and generate a block, but the protocol is set up so that miners who find a new Nonce value compete to create a new block behind the currently propagated block.

6.0 Chain Selection Rule

Reorg

By using a Timer, we can delay the block creation speed. Furthermore, multiple blocks will still generate simultaneously to compete with each other. To address this issue, the Longest Chain Rule comes into place to complete the consensus algorithm. The Longest Chain Rule is a method of adopting a longer blockchain (Canonical Chain) depending on which way the next block converges behind any blockchain leaving the state temporarily ignored when a new block is formed before the block is propagated and a Race Condition is formed. Satoshi Nakamoto explained that this method could solve the Race Condition of blocks. In addition, in his Bitcoin paper, when an attacker with malicious intent maintains the Race Condition state, the attacker intentionally mines another Side Chain to make it longer than the Canonical Chain, inducing other ledgers (Reorg) to change by the Longest Chain Rule.

This means that network attackers must consume more computing power to successfully attack the network by creating a longer chain than the existing one. Satoshi Nakamoto mathematically proved that it is impossible to maintain the Canonical Chain during the six blocks. Even if a 49% attacker of computing power attacks the network, Satoshi Nakamoto assumes that there will be an honest 51% correct block. The blocks would then converge into a single block without causing Reorg. This shows the enhanced security of Nakamoto’s consensus as compared to the security of the PBFT consensus process in mathematical algorithmic form. Therefore, we call the method of presenting and announcing this chain selection rules Nakamoto’s Consensus.

Conclusion

To summarize, the Understanding of Bitcoin series provides a comprehensive guide to the key features of blockchain and UTXO, including the need for decentralization, cryptographic principles, consensus algorithms, and more. In this particular series, we explored the Nakamoto Consensus and Proof of Work Mechanism, which are critical components that ensure the security and integrity of the Bitcoin network. By understanding these mechanisms, crypto figures or those beginners can gain a deeper appreciation for how Bitcoin works and its potential to revolutionize finance. Therefore, I personally encourage those readers to continue exploring this crypto industry and stay up-to-date with the latest developments in blockchain technology. 

Blockchain/Crypto Education is Essential

Reference 

1. Blockchain.com Explorer | BCH | ETH | BCH

2. Bitcoin Network | E-learning Spot

3. What Happens When Two Blocks are Mined Simultaneously? Bitcoin Chain Splits Explained | Braiins

4. Bitcoin block structure | Download Scientific Diagram (researchgate.net)

5. (PDF) Pooled Mining Makes Selfish Mining Tricky (researchgate.net)

Personal Note From MEXC Team

Check out our MEXC trading page and find out what we have to offer! You can learn more about cryptocurrency industry news. There are also a ton of interesting articles to get you up to speed with the crypto world. Lastly, join our MEXC Creators project and share your opinion about everything crypto! Happy trading!

Join MEXC and Start Trading Today!