Blockchain Unit 2
Blockchain Unit 2
Blockchain Unit 2
Consensus:
A procedure to reach in a common agreement in a distributed or decentralized multi-agent
platform
Important for a message passing system
Why Need Consensus?
Reliability and fault tolerance in a distributed system
– Ensure correct operations in the presence of faulty individuals
• Example:
– Commit a transaction in a database
– State machine replication
– Clock synchronization
Why Consensus Can be Difficult in Certain Scenarios?
In message passing system, node behave maliciously
Distributed Consensus
If there is no failure, it is easy and trivial to reach in a consensus
– Broadcast the personal choice to all
– Apply a choice function, say the maximum of all the values
Different types of distributed consensus fault:
There can be various types of faults in a distributed system.
• Crash Fault: A node suddenly crashes or becomes unavailable in the middle of a
communication
• Network or Partitioned Faults: A network fault occurs (say the link failure) and the network
gets partitioned
• Byzantine Faults: A node starts behaving maliciously
Properties of Distributed Consensus
Termination: Every correct individual decides some value at the end of the
consensus protocol
• Validity: If all the individuals proposes the same value, then all correct individuals
decide on that value
• Integrity: Every correct individual decides at most one value, and the decided
value must be proposed by some individuals
• Agreement: Every correct individual must agree on the same value
Synchronous vs Asynchronous Systems
Synchronous Message Passing System: The message must be received within a predefined
time interval
– Strong guarantee on message transmission delay
• Asynchronous Message Passing System: There is no upper bound on the message
transmission delay or the message reception time
– No timing constraint, message can be delayed for arbitrary period of times
Correctness of a Distributed Consensus Protocol
Safety: Correct individuals must not agree on an incorrect value
Nothing bad happend
• Liveliness (or Liveness): Every correct value must be accepted eventually
o Something good eventually happens
• The nodes also has a list of outstanding transactions that need to be validated against the block
of committed transactions
May not be Feasible:
You do not have a global clock! How much time will you wait to hear the transactions
Remember the impossibility result
Observation - 1:
• Any valid block (a block with all valid transactions) can be accepted, even if it is proposed by
only one miner
Observation - 2:
• The protocol can work in rounds
• Broadcast the accepted block to the peers
• Collect the next set of transactions
Solution:
• Every miner independently tries to solve a challenge
• The block is accepted for the miner who can prove first that the challenge has been solved
Permissionless Blockchain :
The permissionless or open model of blockchain – any user can join the network and participate
in transactions
– Bitcoin is developed on this principle
• The blockchain provides the backbone of the permissionless digital currency
– Provides a decentralized architecture
– Tamper-proof through hash-chain
• Miners ensures the consensus in the system
Different permisionless blockchain consensus algorithm are as follows,
1. Proof of Work (Pow)
2. Proof of Stake(PoS)
3. Proof of Burn(PoB)
4. Proof of Elapsed Time(PoET)
• Used in Hashcash, a proof of work that can be added with an email as a “good-will” token
Bitcoin Proof of Work System
Most implementations of Bitcoin PoW use double SHA256 hash function
• The miners collect the transactions for 10 minutes (default setup) and starts mining the PoW
• The probability of getting a PoW is low – it is difficult to say which miner will be able to generate
the block
– No miner will be able to control the bitcoin network single handedly
Based on Hashcash PoW system
– The miners need to give a proof that they have done some work, before
proposing a new block
– The attackers will be discouraged to propose a new block, or make a change
in the existing blocks
Permissioned Blockchain
A blockchain architecture where users are authenticated apriory
• Users know each other
• However, users may not trust each other – Security and consensus are still
required.
• Run blockchain among known and identified participants
Design Limitations of Permissioned Blockchain
1) Sequential Execution
– Execute transactions sequentially based on consensus
– Requests to the application (smart contract) are ordered by the consensus, and executed
in the same order
– This give a bound on the effective throughput – throughput is inversely proportional
– Can be a possible attack on the smart contract platform – introduce contract which will
take long time to execute
2) Non-deterministic Execution
– Consider golang – iteration over a map may produce a different order in two executions
PaXoS
• First Consensus Algorithm proposed by L.
• Lamport in 1989
• Objective: choosing a single value under crash
or network fault
• System process
– Making a proposal
– Accepting a value
– Handling Failures
Types of nodes:
• Proposer: propose values that should be chosen by the consensus
• Acceptor: form the consensus and accept values
• Learner: learn which value was chosen by each acceptor
Making a Proposal: Proposer Process
proposal number: form a timeline, biggest number considered up-to-date
Acceptor Decision:
RAFT Consensus
Designed as an alternative to Paxos
• A generic way to distribute a state machine among a set of servers
– Ensures that every server agrees upon same series of state transitions
• Basic idea -
– The nodes collectively selects a leader; others become followers
– The leader is responsible for state transition log replication across the followers
(1) Electing the Leader: Voting Request
term: last calculated # known to candidate + 1
index: committed transaction available to the candidate
(2) Electing the leader: Follower Node’s Decision Making
• Communicating only by messenger, the generals must agree upon a common battle
plan. However, one or more of them may be traitors who will try to confuse the
others.
The problem : To find an algorithm to ensure that loyal generals will reach a the
desired agreement.
Three Byzantine Generals Problem
Case: 1 Lieutenant Faulty
Round1:
– Commander correctly sends same message to
Lieutenants
• Round 2:
– Lieutenant1 correctly echoes to Lieutenant2
– Lieutenant2 incorrectly echoes to Lieutenant1
Lieutenant1 received differing message
• By integrity condition, Lieutenant1 bound to decide on Commander message
• What if Commander is faculty?
Case: 2 Commander Faulty
Round 1:
– Commander sends differing message to Lieutenants
• Round 2:
– Lieutenant1 correctly echoes to Lieutenant2
– Lieutenant2 correctly echoes to Lieutenant1
• Lieutenant1 received differing message
• By integrity condition, both Lieutenants conclude with Commander’s message
• This contradicts the agreement condition
• No solution possible for three generals including one faulty
2) Prepare:
– Replicas agree on the assigned sequence number