Implementing PBFT in Blockchain

Published in

Coinmonks

14 min readAug 5, 2019

In this article, we will understand the working of practical byzantine fault tolerance in Blockchain systems, the math behind this algorithm, its significance, write its pseudo code, and then implement it in node.js

Declaimer: This article is NOT a tutorial on blockchain. It is assumed that readers have sufficient knowledge about blockchain/bitcoin.

Before talking about PBFT lets understand some terminologies that revolve around it.

Fault tolerance and Fault tolerant systems

Imagine that something wrong happens with the engine of your car, yet it keeps working, however, the speed of the car is significantly reduced, we’ll call the car as fault tolerant and it exhibits fault tolerance properties.

Any system that continues to operate under the influence of unknown or known faults, which results in the reduced capacity of the systems, can be called a fault tolerant system and it exhibits fault tolerance properties.

Fault tolerant systems, unlike other systems, do not breakdown when a fault occurs, instead, the system operates even in the presence of a fault, but at a reduced throughput or high latency.

Byzantine fault tolerance

Byzantine faults are particularly present in distributed systems. These faults are an outcome of misinformation among the system nodes. The reasons for these faults/misinformation are mostly unknown to the members of the distributed systems. Therefore, in this case, a node may be behaving strangely and sending a different response to different nodes in the network, as a result, it is difficult to classify this node as malicious or faulty. Therefore, to make a decision regarding the faulty node, the honest nodes of the system arrive at a consensus and a system that can arrive at a conclusion that is not affected by a malicious/faulty node can be considered as Byzantine fault tolerant system.

Systems exhibiting byzantine fault tolerance tackle the problems presented in the byzantine generals problem.

Instead of identifying the faulty/malicious and figuring out the problem, byzantine fault tolerant continue to operate equivalent to the case when no members of the systems were faulty. (The throughput and efficiency, would therefore be reduced)

Let’s dive into PBFT.

Practical Byzantine Fault Tolerance

Castro and Liskov developed a novel method to achieve consensus in distributed systems that can tolerate faulty/malicious nodes by replicating nodes/state machines. But PBFT can only tolerate such nodes until the number of faulty nodes is less than one-third of all the nodes. Nodes in the network reach consensus about a decision by passing messages among each other about the decision. The more the honest nodes, the more secure the system. Since more number of honest nodes will agree on a correct decision than faulty/malicious nodes agreeing on an incorrect decision, false information will be rejected by the majority.

In order to keep the system secure, pbft requires 3f+1 nodes in the system, where f is the maximum number of faulty nodes that the system can tolerate. Therefore, for the group of nodes to make any decision, approval from 2f+1 nodes is required.

PBFT in Blockchain

Practical byzantine fault tolerance algorithm in blockchain inherits many concepts from its version used in distributed systems. The consensus is achieved, in this case, to decide the validity of a block.

Nodes in the system share messages among each other to commit a block to the chain. Malicious nodes, in this case, may broadcast tampered blocks, as a result, the block which is considered valid by a maximum number of nodes is considered valid in its entirety by the entire network.

Significance of PBFT

In bitcoin(proof of work), block proposer is the fastest miner, whereas, in proof of stake, block proposer is the richest miner. In PBFT, the block creator may not be any special miner, but the proposed block which is committed to the chain would be the most agreed block. Thereby serving the same purpose that PoW and PoS do, i.e. adding a new block to the chain.

States and Messages

This section described the various states of each node at different sessions and different messages that the nodes pass between each other during any round of block proposal:

NEW ROUND: Proposer to send new block proposal. Validators wait for PRE-PREPARE message.
PRE-PREPARED: A validator has received PRE-PREPARE message and broadcasts PREPARE message. Then it waits for 2F + 1 of PREPARE or COMMIT messages.
PREPARED: A validator has received 2F + 1 of PREPARE messages and broadcasts COMMITmessages. Then it waits for 2F + 1 of COMMIT messages.
COMMITTED: A validator has received 2F + 1 of COMMIT messages and is able to insert the proposed block into the blockchain.
FINAL COMMITTED: A new block is successfully inserted into the blockchain and the validator is ready for the next round.
ROUND CHANGE: A validator is waiting for 2F + 1 of ROUND CHANGE messages on the same proposed round number

Note: These states have been referred from this issue on GitHub.

Algorithm

NEW ROUND

A proposer is elected in a round-robin fashion.
The proposer collects transactions from the transaction pool.
Proposer creates a block proposal and broadcasts it to the network. The state of the proposer now changes to PRE-PERPARED state.
Validators receive the PRE-PREPARE message and enter the PRE-PREPARED state.
Validators now verify the proposal and then broadcast a PREPARE message to the other validators.

PRE-PREPARED

Validators wait for 2F+1 valid PREPARE messages, and then enter the PREPARED state.
Validators now broadcast COMMIT messages upon entering PREPAPRED state.

PREPARED

Validators wait for 2F+1 commit messages and then enter COMMITTED state.

COMMITTED

Validators append the 2F+1 commit messages received into the block, and add the block into the blockchain.
Validators now move a FINAL COMMITED state when the block is inserted in the chain

FINAL COMMITTED

A new round is initiated with a new proposer election.

Pseudocode

This section presents pseudocode for the above-mentioned algorithm:

// NEW_ROUND:State = NEW_ROUND
proposer = get_proposers_address( blockchain )
if ( current_validator == proposer )
    block = create_block( transaction_pool )
    broadcast_block( block )
    State = PRE_PREPARED// PRE_PREPARED:ON message.type == PRE_PREPARE
    verify_block( message.block )
    verify_validator( message.block )
    broadcast_prepare( message.block )
    State = PREPARED// PREPARED:ON message.type == PREPARE
    verify_prepare( message.prepare )
    verify_validator( message.prepare )
    prepare_pool.add( message.prepare )if ( prepare_pool.length > 2F+1 )
        broadcast_commit( message.prepare )
    
    State = COMMITTED// COMMITTED:ON message.type == COMMIT
    verify_commit( message.commit )
    verify_validator( message.commit )
    commit_pool.add( message.commit )if ( commit_pool.length > 2F+1 )
        commit_list = commit_pool.get_commits()
        block.append( commit_list )
        blockchain.append( block )
    
    State = FINAL_COMMITTED// FINAL_COMMITTED:new_round()

Graphical Illustration

This section will illustrate the algorithm diagrammatically for better understanding:

Before a new round begins, transactions are broadcasted among nodes so that all the nodes have the same transactions in their pool. After a sufficient number of transactions in their pool, these nodes start a new round.

A proposer is chosen in a round-robin fashion. Node 8 becomes the proposer and rest of the nodes agree upon on it. The proposer sends a PRE-PREPARE message and each node enters PRE-PREPARED state.

The proposer broadcasted a PRE-PREPARE message, which contains a proposed block. The rest of the nodes broadcast this message to other nodes.

Each node sends a PREPARE message if they agree upon the proposed block. After 2F+1 such messages, nodes change state to PREPARED.

Prepared nodes send COMMIT messages to each other, upon 2F+1 commits, nodes move to COMMIT state and add the block to the chain. After adding the block they move to the FINAL COMMITTED state.

After FINAL COMMITTED, nodes calculate a new proposer.

Mathematical Proof of PBFT

In practical byzantine fault tolerance, a system of N nodes can tolerate F faulty nodes if N=3F+1.
Each decision in a practical byzantine fault tolerant system needs 2F+1 approvals, where Fare the faulty nodes.

We will now mathematically prove the above two definitions, which are a corollary of each other. The following calculation is a simplification of the math found in Stanford University’s notes.

Two important properties of distributed systems are Liveness and Safety.

Liveness

Liveness is the term used in the context of distributed systems when the system continues to operate. It means that the system will not stall and will function even if some errors occur. In the case of blockchain, Liveness means that the system will continue to add new blocks to the chain and at no point of time the system will stop working.

Safety

Safety is the term used in the context of distributed systems when the system converges to a single decision. In a distributed system nodes may diverge into two decisions or split further, Safety of the distributed system ensures that the network will end up with a single decision across all honest nodes even if there exist faulty nodes.

Proof

Non-byzantine failures

Given N nodes in a network, with f fault nodes, what is the Quorum size Q required to guarantee Liveness and Safety?

Quorum is defined as the minimum number of nodes needed for the network to run properly and make valid decisions. Quorum comprises of the honest nodes.

Liveness

In order to avoid the network from stalling, there must exist at-least one non-faulty node.

Hence, for liveness :

Safety

In order to avoid the network from splitting into multiple decisions, the majority should be present. Since we need an honest majority, Quorum size should be greater than half of the total number of nodes, for the decision to be in our favor.

Hence for Safety:

By combing the two conditions we get,

therefore, for non-byzantine failures

Byzantine Failure

Given N nodes in a network, with f fault nodes which might experience byzantine failure, what is the Quorum size Q required to guarantee Liveness and Safety?

Node experiencing byzantine failure can vote for an invalid block or decision, leading to a split in decision and as a result forking.

Liveness

In order to avoid the network from stalling, there must exist at-least one non-faulty node or quorum. Since it is possible that Byzantine nodes may not reply.

Hence, for liveness :

Safety

In order to avoid the network from splitting into multiple decisions, the majority should be present. However, unlike non-byzantine failure, nodes in byzantine failure can also vote, therefore we need to consider the faulty nodes in the voting process as well.

this equation provides the maximum number of failed nodes that can be present in the network.

Hence for Safety, it can also be written as:

where f is the maximum number of tolerable faulty nodes.

By combining the two conditions we get

therefore, for byzantine failures

Implementation of PBFT in Node.js

In this section, we will implement a blockchain with PBFT as its consensus algorithm. It may be noted that this blockchain would not use a cryptocurrency but can be if we use an account model. Moreover, PBFT can only operate under a permissioned environment since it is vulnerable to Sybil attacks, the members of the network are required to be known.

Prerequisites

Node.js
Postman
VS code
Knowledge about blockchain concepts

Architecture and Design

To implement PBFT we will develop the following components:

Wallet class — for public key and signing data.
Transaction class — to create transactions and verify them.
Block class — to create blocks, verify blocks and verify proposer of the block.
Blockchain class — to create a chain, add blocks, calculate proposer, validate blocks, update blocks.
P2p Server class — to broadcast and receive data among peers.
Validators — to generate and verify validators
Transaction pool, block pool, commit pool, prepare pool and message pool — to store transactions, blocks, commits, prepare and new round messages respectively.
App — Express API to interact with the blockchain
Config — to store global variables
Chain Utilities — to store common functions such as hashing and verifying signatures.

Code

Create a root directory pbft and cd into it. All the files in this project are present in the root directory.

mkdir pbft && cd pbft

The ChainUtil Class

We will start off by creating a chain-util.js file which will be used multiple times in this project. This file will be used to create key pair for signing data, generating id’s for transactions, hashing data and verifying signatures.

We need three modules to perform these functions. Therefore we need to install them.

npm i --save elliptic uuid crypto-js

Create a class ChainUtil and export it.

The Transaction Class

Next, we’ll make a transaction class. Create file transaction.js in the project folder. Transactions in this project will contain the following properties:

id — for identification
from — the senders address
input — an object that further contains data to be stored and timestamp
hash — the SHA256 of input
signature — the hash signed by the sender

Create a class Transaction in the file and export it.

The Wallet Class

Up next is wallet. The wallet holds the public key and key pair. It is also responsible for signing data hashes and creating signed transactions.

Create a file wallet.js in the project directory. Add a class Wallet and export it.

The Validator Class

Since PBFT is a permissioned blockchain consensus algorithm we need to store the address of all the nodes in each nodes system. We can do this manually by choosing a secret, creating a wallet, getting its public key and storing this key into a file and when we run our project it reads this file for keys.

But instead of doing this manually we can automate this by creating a class and adding a function that can return a list of public keys of N number of nodes.

We will create a Validator class that will generate a list of public keys known to every node. In this project, we have used the secret phrase for each node as

NODE1, NODE2, NODE3......

This way it would be easier for us to make a list of public keys and create the nodes from the command line with the same public key.

NOTE: Secret phrase should never be made public. It is only for the demonstration that we have used such Secret phrases. In real-world projects, a registration request is sent to make a node a validator. If the whole network approves this request, the node becomes a validator and the public key is added to the list.

The Config.js file

The number of validators in the network can be passed through the command line but instead it easier to store it in a file and import it where ever needed.

Create a file config.js and create three variables NUMBER_OF_NODES ,MIN_APPROVALS and TRANSACTION_THRESHOLD

The Block Class

Next we will create the block class. In the project directory, create a file block.js and make a class Block in it. Block will have the following properties:

timestamp — the time at which the block was made
lastHash — hash value of the last block
hash — hash value of the current block
data — the transactions that the block holds
proposer — the public key of the creator of the block
signature — the signed hash of the block
sequenceNo — the sequence number of block

The TransactionPool Class

We need a place to store transactions received from other nodes. Therefore we will make a TransactionPool class to store all transactions. Create a file called transaction-pool.js

The BlockPool Class

To store blocks temporarily we will also make block pool. Create a file block-pool.js in which the BlockPool class holds the blocks until it is added to the chain. A block is added to the block pool when a PRE-PREPARE message is received.

There are many other data objects received from the nodes that need to be stored. PREPARE , COMMIT andNEW_ROUND messages

Therefore will create three more pools namely, PreparePool , CommitPool and MessagePool . MessagePool will hold the NEW_ROUND messages.

The PreparePool Class

The CommitPool Class

Commit messages are added after 2f+1 prepare messages are received, therefore we use the prepare message to get the block hash instead of passing the entire block.

The MessagePool Class

MessagePool will work similarly to the other two pools. The only difference would be the extra message it takes with it.

The Blockchain Class

We have all of the classes required to make our blockchain class. We can now create a file blockchain.js The Blockchain class will have the following properties:

chain — list of blocks that are confirmed
validatorsList — validators list for the given network

The P2pserver Class

How do we send messages to other nodes? We will make a P2p Server. Create a class P2pserver in a file p2p-server.js

To create a p2p server we will make use of sockets. In order to use sockets we will install a ‘ws’ module. This module makes it utterly easy to work with sockets.

npm i --save ws

P2pserver class is where the consensus algorithm is implemented. It is the core of the project. This class is responsible for handling messages and broadcasting them.

The App

Now we will connect all the files using an application created using express module. Install the express module using npm.

npm i express --save

Our application will instantiate the pools, wallet, blockchain, p2pserver and declare some endpoints to interact with our blockchain.

Following are the minimum endpoints required, (you may add more):

POST: ‘/transact’ — creates transactions, request object consists of data to be stored in the transaction
GET: ‘/transactions’ — sends the transactions in the transaction pool as a response
GET: ‘/blocks’ — sends the chain of the blockchain as a response

This completes our coding. You test this application by running the following in the separate terminals:

First node:

SECRET="NODE0" P2P_PORT=5000 HTTP_PORT=3000 node app

Second node:

SECRET="NODE1" P2P_PORT=5001 HTTP_PORT=3001 PEERS=ws://localhost:5000 node app

Third node:

SECRET="NODE2" P2P_PORT=5002 HTTP_PORT=3002 PEERS=ws://localhost:5001,ws://localhost:5000 node app

You can make as many as you want. Do update the total number of nodes config file before creating more nodes.

Hit the endpoint for any node until the pool fills up and check the chain by hitting the /blocks endpoint.

Also, hit the endpoint /transactions to check if the transaction pool is empty.

You can also make more such endpoints for commit, prepare and message pool.

Further Ideas

Create a proper folder structure
Combine all pools into one.
Add STATE variable in the project and update it whenever a new state is reached.
Clear commit, prepare and message pool after new round.
Create a registration method in blockchain to add new validators dynamically.
Create a cryptocurrency using this project as a base.
Use multi-threading to make this project concurrent and faster.

Thanks a lot for reading. If you found it useful, throw a bunch of claps. If you have any question, comment below.

The entire code of this project can be found on my GitHub Repo. If you find any bug, feel free to create a PR.

Join Coinmonks Telegram Channel and Youtube Channel get daily Crypto News