CST 428 BLOCK CHAIN TECHNOLOGIES
S8 CSE – ELECTIVE
MODULE – 3
Consensus Algorithms and Bitcoin
Consensus Problem
● Distributed systems are classified into two main categories,
namely message passing and sharedmemory.
● In the context of blockchain, we are concerned with the message
passing type of distributed systems, where participants on
the network communicate with each other via passing
messages to each other.
Objective
● To explain Byzantine General Problem.
The Byzantine generals problem
● Problem of reaching agreement in the presence of faults or
Byzantine consensus.
● In distributed systems, a common goal is to achieve consensus
(agreement) among nodes on the network even in the presence
of faults.
● Fundamental requirement in a consensus mechanism is that it
must be fault-tolerant.
The Byzantine generals problem
● It must be able to tolerate a number of failures in a
network and should continue to work even in the
presence of faults.
● Based on the requirement of fault tolerance, consensus
algorithms are also called fault-tolerant algorithms, and there
are two types of fault-tolerant algorithms.
● Crash fault-tolerance (CFT) and the other is Byzantine
fault-tolerance (BFT).
Byzantine fault- tolerance (BFT) algorithms
[Link]
Practical Byzantine Fault Tolerance (PBFT)
● Developed in 1999 by Miguel Castro and Barbara Liskov
● To provide consensus in the presence of Byzantine faults.
● Comprises three sub-protocols called normal operation,
view change, and checkpointing
○ Normal operation is executed when everything is running
normally and no errors are in the system.
○ View change runs when a faulty leader node is detected in the
system.
○ Checkpointing is used to discard the old data from the system.
Practical Byzantine Fault Tolerance (PBFT)
● Comprises of three phases or steps.
● Pre-prepare, Prepare, & Commit.
● The protocol runs in rounds.
● In each round, an elected leader node, called the
primary node, handles the communication with the client.
● The protocol progresses through the three previously
mentioned phases.
Process of PBFT Algorithm
• Client: Client nodes that are responsible for sending
transaction requests.
• Primary: Main nodes that are responsible for packing
transactions into blocks and finalizing blocks. Each
consensus-reaching process has one and only one Primary
node.
• Replica: Replica nodes that are responsible for finalizing
blocks. Each consensus-reaching process involves multiple
Replica nodes, and they all proceed in a similar way.
Practical Byzantine Fault Tolerance (PBFT)
● Participants in the PBFT protocol are called replicas.
● One of the replicas becomes primary as a leader in each
round, and the rest of the nodes acts as backups.
● In order to tolerate Byzantine faults, the minimum number of
nodes required is N = 3F + 1, where N is the number of nodes
and F is the number of faulty nodes.
● PBFT ensures Byzantine fault tolerance as long as the number
of nodes in a system stays N >= 3F + 1
How PBFT works
At a high level, the protocol works as follows:
1. A client sends a request to invoke a service operation in
the primary.
2. The primary multicasts the request to the backups.
3. Replicas execute the request and send a reply to the
client.
4. The client waits for replies from different replicas with
the same result; this is the result of the operation.
In PBFT, a primary node is selected from the network to act as a leader, and it is
responsible for proposing the next block in the blockchain. The other nodes, known as
replicas, receive the proposed block and perform a series of steps to validate it.
Pre-prepare: The leader sends a proposed block to all the replicas in the
network.
Prepare: The replicas validate the proposed block and send a message to all
other replicas indicating that they have validated it.
Commit: Once a replica receives messages from at least two-thirds of the
replicas indicating that they have validated the proposed block, it sends a
commit message to all other replicas, and the block is added to the
blockchain.
The pre-prepare sub-protocol algorithm:
1. Accepts a request from the client.
2. Assigns the next sequence number.
3. Sends the pre-prepare message to all backup
replicas.
The prepare sub-protocol algorithm:
1. Accepts the pre-prepare message. If the backup has
not accepted any pre-prepare messages for the same
view or sequence number, then it accepts the message.
2. Sends the prepare message to all replicas.
The commit sub-protocol algorithm:
1. The replica waits for 2F prepare messages with the same view,
sequence, and request.
2. Sends a commit message to all replicas.
3. Waits until a 2F + 1 valid commit message arrives and is
accepted.
4. Executes the received request.
5. Sends a reply containing the execution result to the client.
Practical Byzantine Fault Tolerance (PBFT)
Specific message types that are exchanged during
the PBFT protocol.
• View-change:
View-change occurs when a primary is suspected faulty. This phase
is required to ensure protocol progress. With the view change sub-
protocol, a new primary is selected, which then starts normal mode
operation again. The new primary is selected in a round-robin fashion.
• The checkpoint sub-protocol:
Checkpointing is a crucial sub-protocol. It is used to discard old
messages in the log of all replicas. With this, the replicas agree on a
stable checkpoint that provides a snapshot of the global state at a
certain point in time.
Practical Byzantine Fault Tolerance (PBFT)
● View-change protocol
Practical Byzantine Fault Tolerance (PBFT)
● Advantages
○ Provides immediate and deterministic transaction finality
○ Energy efficient as compared to PoW
● Disadvantages
○ Not very scalable - more suitable for consortium networks,
instead of public blockchains
○ Faster than PoW protocols
○ Sybil attacks can be carried out
Nakamoto consensus or PoW
● First introduced with Bitcoin in 2009
● Longest-running blockchain network
● The PoW mechanism is designed to mitigate
Sybil attacks, which facilitates consensus
and the security of the network
PoW works as follows:
• PoW makes use of hash puzzles.
• A node proposes a block has to find a nonce such that
H (nonce || previous hash || Tx || Tx|| . . . ||Tx) < Threshold value
Nakamoto consensus or PoW
PoW makes use of hash puzzles.
Nakamoto consensus or PoW
Nakamoto consensus or PoW
● Key idea behind PoW as a solution to the Byzantine
generals problem is that all honest generals (miners in the
Bitcoin world) achieve agreement on the same state
(decision value)
● As long as honest participants control the majority of the
network, PoW solves the Byzantine generals problem
Nakamoto consensus or PoW
● Two main variants of PoW algorithms, based on the
type of hardware used for processing
○ CPU-bound PoW - processing required to find the solution to the
cryptographic hash puzzle is directly proportional to the
calculation speed of the CPU or hardware such as ASICs
○ Memory-bound PoW algorithms rely on system RAM to provide
PoW. The performance is bound by the access speed of the
memory or the size of the memory.
Proof of stake (PoS)
● Energy-efficient alternative to the PoW
● First used in Peercoin, and now, prominent
cryptocurrency blockchains such as EOS, NxT,
Steem, and Tezos are using PoS algorithms
● Stake represents the number of coins (money) in the
consensus protocol staked by a blockchain participant
Proof of stake (PoS)
● Key idea is that if someone has a stake in the system, then
they will not try to sabotage the system
● The chance of proposing the next block is directly proportional
to the value staked by the participant
● Variations of PoS - chain-based PoS, committee-based PoS,
BFT-based PoS, delegated PoS, leased PoS, and master
node PoS
Proof of stake (PoS)
● PoS miner is called either a validator, minter, or stakeholder
● Right to win the next proposer role is usually assigned
randomly.
● Proposers are rewarded either with transaction fees or block
rewards.
● Control over the majority of the network in the form of the
control of a large portion of the stake is required to attack and
control the network.
Proof of stake (PoS)
Selecting a Validator
•Randomized block selection: It uses a formula that uses the lowest
hash value in combination with the highest stake to predict the next
validator.
•Coin age-based selection: It combines randomization with the concept
of coinage. Coinage is the product of the number of coins multiplied
by the number of days the coin has been held.
•Coins that have not been spent for a certain number of days begin
competing for the next block. This system benefits validators with small
and medium-scale coins and prevents rich users from dominating the
blockchain.
Proof of stake (PoS) types
• Chain-based PoS
• Committee-based PoS
• Delegated PoS
Chain-based PoS
● Very similar to PoW
● Only change is the block generation method
● Transactions are picked up from the memory pool and a
candidate block is created
● Hash (B || clock time) < target x stake value
● Hashing puzzle in PoS is solved at regular intervals based on
the clock tick
Committee-based PoS
● Group of stakeholders is chosen randomly, using a
verifiable random function (VRF)
● VRF produces a random set of stakeholders based on
their stake and the current state of the blockchain
● The chosen group of stakeholders becomes responsible
for proposing blocks in sequential order
Delegated PoS
● Instead of using a random function to derive the group of
stakeholders, the group is chosen by stake delegation
● Group selected is a fixed number of minters that create
blocks in a round-robin fashion
● Delegates are chosen via voting by network users
● Votes are proportional to the amount of the stake that
participants have on the network
● used in Lisk, Cosmos, and EOS
Reference
PBFT - [Link]
THANK YOU
42