Understanding of 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 PBFT (Practical Byzantine Fault Tolerance) consensus algorithm is used in blockchain and crypto technologies to ensure that all nodes in a network agree on the state of the ledger, even in the presence of malicious actors.
2. The PBFT algorithm achieves consensus among nodes on the network by tolerating malicious nodes that may attempt to disrupt the consensus process.
3. The time complexity of the PBFT algorithm addresses the proportion of malicious nodes to the total number of nodes in the network. Furthermore, the consensus process is feasible when the number of traitor nodes is less than one-third of the total nodes on the network.
1.0 Leslie Lamport PBFT
What is Leslie Lamport’s PBFT (Practical Byzantine Fault Tolerance) consensus algorithm? It describes the Byzantine General’s Problem, involving nodes on the network reaching consensus through continuous message passing. The algorithm achieves consensus by tolerating Byzantine faults, i.e., malicious nodes that may attempt to disrupt the consensus process.
In terms of time complexity (O), the algorithm’s formula addresses the proportion of malicious nodes, i.e., traitor nodes, to the total number of nodes in the network. Additionally, the algorithm’s consensus process is feasible when the number of traitor nodes (t) is less than one-third of the total nodes (N) on the network (N > 3t).
Blockchain and crypto technologies often employ consensus algorithms such as PBFT. It ensures that all nodes in a network agree on the state of the ledger. It still applies even in the presence of malicious actors. Additionally, blockchain systems using a network distribution of nodes and cryptographic mechanisms can achieve Byzantine fault tolerance. It can also protect against fraudulent activity.
Looking at the formula for time complexity O, the increase in the number of malicious nodes t is proportional to the increase in the total number of nodes n. As shown in the table, to achieve the PBFT consensus algorithm on the network, when the number of malicious nodes t is 1, the total number of nodes N must be increased to n² to achieve the consensus method mentioned earlier, where N > 1/3. When the number of malicious nodes t is 2, N increases to N³ proportionally. When t is 3, n increases to n⁴ proportionally.
In other words, PBFT describes a consensus algorithm that exponentially increases the number of nodes n proportionally to the increase in the number of malicious nodes T.
Flaws of Byzantine Fault-Tolerant Consensus
When considering t as problems that malicious system operators cannot manage during system operation, the number of nodes n is a value that can be predetermined and managed within the system. The increase in n according to the increase in t serves as a system-level constraint to identify Byzantine malicious nodes.
As mentioned earlier, each node in the Byzantine fault-tolerant consensus algorithm passes one voting right (message). This leads to a critical flaw in that consensus cannot be achieved if a geometrically increasing number of nodes participate or leave the system. If a consensus that requires a geometrically increasing number of nodes continues to be enforced within the system, it may lead to closed problems that restrict the system’s overload or openness. This indicates that it is not a suitable consensus algorithm for an open network like Bitcoin, where users can freely participate and leave the system.
Satoshi Nakamoto developed a new consensus algorithm called Nakamoto’s Consensus. It creates an open network where participants (nodes) can join and leave the system at any time. It is different than a system with a fixed number of nodes. This consensus algorithm can facilitate the creation of a suitable open network for the decentralized nature of the blockchain.
2.0 Nakamoto’s Consensus
Bitcoin’s block is a unit that synchronizes the state of consensus and the P2P network. Bitcoin is classified as an Electronic Cash System that handles a single currency, known as digital gold. Within this system, the unit of consensus is a block. It is a collection of transactions that transfer money as a single unit. To achieve consensus within the Bitcoin network, transactions are packaged into a block. Meanwhile, all participating nodes in the system undergo a consensus process. It synchronizes the state of each block for Bitcoin financial transactions.
To understand the Bitcoin consensus algorithm more closely, it is necessary to understand the concepts of Directed Acyclic Graph (DAG) and Unspent Transaction Output (UTXO). The UTXO model tracks the ownership of Bitcoin within the system. Meanwhile, DAG represents the data structure of transactions in a distributed and decentralized manner. This way, the consensus algorithm is achievable through a distributed network following the integrity of each block in the chain. Whereas, cryptographic techniques and mathematical algorithms maintain it.
Directed Acyclic Graph
Image from
DAG (Directed Acyclic Graph) is a concept of a graph that has a single direction. It is the opposite of a cyclic graph. The algorithm of DAG is characterized by its single-directional property. Furthermore, it is similar to the core characteristic of blockchain, the irreversible one-way nature. (The property that it is difficult or impossible to reverse the direction of the state transition)
In the first-generation blockchain, Bitcoin, the verification process of transactions is similar to the process of offline cash transactions. As explained in an earlier poster, the verification process of transactions in Ethereum is similar to online banking. Users generate Tx and the transaction history remains online. In comparison, the UTXO Tx generation process and transaction verification method of the Bitcoin network are similar to the process of offline transactions where people exchange cash with each other.
3.0 UTXO
Let’s consider a simple example from daily life. A wants to transfer 30,000 won to B via online banking.
If A gives 30,000 won to B, online banking can create a consensus result similar to A giving 30,000 won to B. It deducts 30,000 won from A’s account and adds 30,000 won to B’s account. On the other hand, let’s assume that A gives 30,000 won to B in cash as shown in the picture above, in an offline situation.
When B receives 30,000 won from A, the 30,000 won held by B will be a tangible asset. It has a value that does not disappear until B generates a transaction for the 30,000 won held by C. It can be an ATM, or another trader (Arbitrary Time Period).
In contrast to the online situation, the offline transaction method described above is very similar to the transaction verification method of UTXO (Unspent Transaction Output) within Bitcoin.
UTXO is defined as a chunk/output value of unspent bitcoins in which the ownership has not been transferred or the unit of Tx (Transaction) whose output value has not been changed. UTXO is widely used as a method for verifying transactions in Bitcoin/QTUM/Ravencoin, among others. Let’s explain the concept of UTXO in more detail with an example and a picture.
Assuming a scenario where three people, A-Jaeha, B-Won, and C-Yooncheol, have generated Tx on the Bitcoin network.
UTXO Scenarios
The investor’s mother of Jaeha sent him 20 Bitcoins in his wallet. Jaeha’s wallet currently holds 20BTC. When dealing with Tx of UTXO on the Bitcoin network, it is important to note whether the output value of Tx in the block is currently in progress for consensus with other blocks or completed by verifying the work of the data across the Bitcoin network. To further explain this, a scenario-based example is given.
Scenario 1:
Jaeha’s mother sent him 20 Bitcoins, and the Tx has been completed. Assuming that Jaeha has not generated another Tx INPUT value for his 20 BTC for other nodes, the 20BTC that Jaeha received from his mother at this point can be defined as an Unspent Transaction Output (UTXO). It is an output value of 20BTC. Furthermore, it is spendable for the next Tx with another user on the network or an unspent output value.
Scenario 2:
Jaeha, who has 20 BTC UTXO, wants to send 5BTC to Yuncheol. At this point, he is trying to initiate the transaction via TX A script as shown in the figure. When Jaeha sends 5BTC to Yuncheol, the status of Jaeha’s 20 UTXO is destroyed. This is because UTXO is a chunk/output value of Bitcoin that has not undergone any change in the unit of Tx or transfer of ownership. Therefore, the condition of UTXO disappears when Jaeha tries to change the ownership of his Tx by initiating the transaction with Yuncheol.
The Tx A Script destroys Jaeha’s UTXO Tx block for 20 BTC which sends 5BTC to Yuncheol as input. (Change in the unit of Tx generation. Thus, the information for 20 BTC’s UTXO is destroyed. However, the new UTXO remains in Jaeha’s wallet, with a new UTXO of 15BTC recording. This is the remaining balance of 15BTC after subtracting the 5BTC sent to Yuncheol from the initial 20BTC.
Scenario 3:
Let’s take a look at Yuncheol’s wallet. At the time when the Tx for 5BTC from Jaeha was completed, Yuncheol’s wallet contained 1BTC received from a stranger. It also has 3BTC from Yunho and 5BTC from Jaeha. The most significant reason why UTXO chain verification is possible is that the results of each block-stored operation are not combined but are stored as individual objects. Therefore, Yuncheol’s wallet contains information on 1BTC, 5BTC, and 3BTC as individual Tx units. It is not a block containing a total of 9BTC information.
Scenario 4:
Therefore, Yuncheol’s wallet holds assets in the form of UTXOs as (1BTC), (5BTC), and (3BTC) objects. Yuncheol wants to send 7 BTC to Won. In order to do so, he needs to dissolve another UTXO asset in his wallet as the money he wants to send is larger than the 5BTC received from Jaeha. Yuncheol creates a Tx by partially ordering the UTXOs he can pay with. He combines the 3BTC from Yunho and the 5BTC from Jaeha. This creates a total of 8BTC, generating the Input through Tx B script as shown in the figure. When he sends 7BTC to Won, the remaining 1BTC is recorded in Yuncheol’s wallet in the form of a UTXO.
Ultimately, at the point where all the Tx that Yuncheol generates to Won are in the DAG form, each UTXO of Jaeha, Yuncheol, and Won becomes a set block of the last UTXO on the DAG. Therefore, the values of each UTXO’s Tx saved on the DAG derived from this table are as follows:
Jaeha — 15 BTC
Yuncheol — 1BTC, 1 BTC
Won — 7 BTC
This shows that each block references the previous block like a chain and specifies its order. The state of a block is a set of UTXOs, and to know the latest state of a block, one needs to explore the data of all the blocks.
4.0 Gassip/Epidemic Protocol: Block Propagation
Through the UTXO validation technique, we have explored how financial assets are verified and stored in a block. Now, we will investigate how these blocks are propagated in the network. In the Bitcoin network, blocks are propagated using the Gossip Protocol, also known as the Epidemic Protocol, as shown in the picture above. As the name suggests, each block spreads like a rumor, exchanging metadata within the block and transmitting data.
This propagation method is the most effective way to disseminate information about stored transactions in a block in all blockchains, including Bitcoin.
The Gossip Protocol is the most effective method for propagating stored transaction (Tx) information in all P2P network-based blockchains, including Bitcoin. This is because, for example, if one node attempts to relay block Tx information to all nodes, the time required to synchronize all nodes to the same state for a single block is proportional to the number of nodes participating in the system, making it highly inefficient due to the bandwidth limitation of each node.
If data is propagated by selecting a few specific blocks based on certain blocks that have participated in the system in a tree structure, the problem caused by bandwidth can be resolved. However, there is a limitation. If the key block of the root for transmitting information about the information of the block in the system goes missing, all blocks included in that root cannot receive data.
The advantage of the Gossip Protocol propagation method is that one node relays information to its neighboring blocks, which in turn propagates the information like a rumor, allowing all blocks to receiving financial news contained in the block without the aforementioned limitation.
An Issue in the Block Propagation Method
However, there is one issue that needs addressing in this block propagation method. That is, who can create these blocks?
Following the PBFT approach, the number of nodes does not change, and the participating nodes in the system take turns creating blocks. However, in Nakamoto’s Consensus approach, due to the open nature of the Bitcoin network, where nodes can join and leave at any time, it imposes a special condition where anyone should be able to create blocks.
However, if anyone can create blocks, it will lead to the difficulty of synchronizing the Tx shared information between blocks, as another node might create a new block while another is already creating one without taking into account the predetermined interval.
To synchronize the nodes in the system, it is necessary to prevent new block creation before the previous block propagates to 90% of the entire Bitcoin network.
Therefore, Satoshi Nakamoto came up with a solution called the Random Timer. It allows anyone to create blocks and reach the latest unified state. The Random Timer is a timer to create new blocks in the blockchain network. The block creation speed receives adjustments to the timer so that anyone can create a block when the random time of the timer expires. This means that a lucky person can create a block as the timer’s time is random.
Conclusion
Satoshi Nakamoto explained that if the average time the random timer expires is similar to the time it takes for a block to propagate across the Bitcoin network. The network can converge to a single block, resulting in an optimized outcome. However, the Bitcoin network has a variable shape due to the free movement of nodes. Therefore, adjusting the random timer is essential, and Satoshi proved this with the Proof of Work (PoW) method.
Reference
1.Unspent Transaction Output (UTXO) – Wiki | Golden
2.Gnutella: an Intro to Gossip (nakamoto.com)
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!
