1 of 40

Consensus Protocols in Blockchain

Cong Yan

Jan 30, 2018

2 of 40

Recap: Proof of Work

3 of 40

4 of 40

5 of 40

6 of 40

Alternative Consensus Protocols

Practical Byzantine Fault Tolerance (PBFT), Proof of Stake (PoS)
Make different tradeoffs:

Efficiency: txn throughput and energy consumption
Security: handling attacks in a public network
Simplicity: how complicated it is to design the protocol

	Efficiency	Security	Simplicity
PoW
PBFT
PoS

7 of 40

Agenda

Basic: Practical Byzantine Fault Tolerance (PBFT)
Basic: Proof of State (PoS)
Case study: Ethereum Casper
Case study: Hyperledger Fabric

8 of 40

Practical Byzantine Fault Tolerance (PBFT)

Byzantine Fault: nodes exhibit Byzantine (i.e., arbitrary) behavior
PBFT: an algorithm that offers liveness and safety guarantee when at most f out of (3f+1) nodes are faulty.

9 of 40

Practical Byzantine Fault Tolerance (PBFT)

Client:

Primary:

v: view number

n: sequence number

d: message digest

: primary p’s signature

m: value to agree on

10 of 40

Practical Byzantine Fault Tolerance (PBFT)

Client:

Primary:

If node i receives >=2f ‘prepare’ with the same m as itself, then ‘prepare’ is confirmed.

v: view number

n: sequence number

i : replica i

m: value to agree on

11 of 40

Practical Byzantine Fault Tolerance (PBFT)

Client:

Primary:

If node i receives >=2f ‘prepare’ with the same m as itself, then ‘prepare’ is confirmed.

Even if f faulty nodes are among the (2f+1) nodes, the rest (f+1) non-faulty nodes are majority.
f faulty nodes may not respond, so in worst case node i can only receive 2f ‘prepare’ msg.

v: view number

n: sequence number

i : replica i

m: value to agree on

12 of 40

Practical Byzantine Fault Tolerance (PBFT)

Client:

Primary:

v: view number

n: sequence number

i : replica i

m: value to agree on

If ‘prepare’ is confirmed, and node i receives >=2f ‘commit’ with the same m as itself and the m in ‘prepare’, then ‘commit’ is confirmed.

13 of 40

Practical Byzantine Fault Tolerance (PBFT)

Client:

Primary:

If a client receives >f replies, the result is confirmed.

i : replica i

r: reply

14 of 40

Practical Byzantine Fault Tolerance (PBFT)

Sequence number n:

Produce checkpoint
Broadcast checkpoint, if confirmed stable, previous history can be discarded

View number v:

Primary is defined as node (v mod N) (with N nodes in network)
When primary fails to send response for a while, propose a view change

For more details, check http://pmg.csail.mit.edu/papers/osdi99.pdf

15 of 40

PBFT Recap

A protocol that enables non-faulty nodes reach consensus (i.e., agree on a value m) despite some other nodes exhibits byzantine behavior
However…

Works only for a fixed set of nodes
messages each round

16 of 40

Proof of Stake: basic

The creator of the next block is chosen with prob. proportionally to a person’s stake

Stake: coin’s age (peercoin), money, ...

17 of 40

Proof of Stake: basic

Forks in chain are common, but problematic

As long as there’s network delay
‘Nothing-at-stake’ problem: without penalty, creator will creates block on all forks to guarantee his/her block reward

18 of 40

Proof of Stake: basic

Forks in chain are common, but problematic

As long as there’s network delay
‘Nothing-at-stake’ problem: without penalty, creator will creates block on all forks to guarantee his/her block reward
When will a txn gets confirmed to be included in blockchain

19 of 40

Casper

Proof-of-Stake finality system which overlays an existing blockchain
Currently being developed Ethereum Foundation
A combination of PoS and PBFT

White paper: https://arxiv.org/abs/1710.09437

20 of 40

Original Ethereum

$$$: block rewards +

$: transaction fee

21 of 40

Ethereum with Casper

Casper gets validators agree on which path to choose

$: transaction fee

$$$: block rewards

22 of 40

Goals of Casper’s Validator Protocol

Define a finalizing condition: when a block can be confirmed in the chain
Define a slashing condition: when a bad validator gets penalized
Provide safety and plausible liveness

23 of 40

Casper Checkpoint Tree

Root

Checkpoint (every 100 blocks, for efficiency reason)

Supermajority link: >⅔ validators vote on this link

Finalized checkpoint

24 of 40

Casper Slashing Condition

s1, s2: source

t1, t2: target

h(s): height of s

V: vote

25 of 40

Casper Slashing Condition

Condition 1:

b’

1

2

3

4

5

6

7

26 of 40

Casper Slashing Condition

Condition 2:

1

2

3

4

5

6

7

27 of 40

Casper Discussion

Scalability and throughput (?)
Proper economic incentives

Encourage people to be validators and actively vote, while punish misbehavior
Carefully differentiate ‘intentional bad behavior’ from ‘just lost connection’

Validator set

How to make nodes agree on validators in a peer-to-peer network
How long to keep the deposit

Casper CBC (correct-by-construction)

Varies the voting decision process of each validator dynamically, based on the history of messages one sees from other validators
No static ⅔ threshold: varies according to network delay, #of malicious nodes, etc

Scalability and throughput depends on the number of validators, as well as many other factors.

Casper throughput: not confirmed. Some estimate thousands of txn per second. Still not comparable with current transaction processing speed, but much faster than pure PoW.

Now we have seen a brief picture of how casper works.

However, designing a good Proof of Stake protocol is way more complicated.

Here I list some of the concerns in designing PoS protocol. These are not completely solved by Casper and still being discussed.

When some validator doesn’t send votes, how to know whether the current votes are sent by malicious validators and punish the present validators, or the absent ones are offline and punish them for not participating?

Safety faults vs liveness fault

Model of participation

Fault tolerance threshold: hardcoded in protocol since nodes need to agree when and how a node needs to be punished

Basically CBC is aiming at a faster consensus process while making things harder for attackers.

28 of 40

Hyperledger Fabric

A framework to build private blockchain applications
Assumes the app will operate in an environment with partial trust
Mainly uses PBFT to reach consensus
Targets at providing modular, secure and scalable solutions

29 of 40

Hyperledger Fabric Architecture

Application

Peers with distributed ledger

Smart contract

Figure source: https://hyperledger-fabric.readthedocs.io

30 of 40

Hyperledger Fabric Architecture

31 of 40

Hyperledger Fabric Architecture

32 of 40

Hyperledger Fabric Architecture

client

endorsing peers

global ordering service

33 of 40

Hyperledger Fabric Consensus Process

Step 1:

proposal

34 of 40

Hyperledger Fabric Consensus Process

Step 2:

endorsement

35 of 40

Hyperledger Fabric Consensus Process

Step 3:

Transaction

(encrypted)

36 of 40

Hyperledger Fabric Consensus Process

Step 4:

Block of txns to be executed

37 of 40

Hyperledger Fabric Consensus Process

Step 5:

Confirmed txn result

38 of 40

Hyperledger Fabric Discussion

Ordering service is a geo-replicated state machine, which assembles txn into blocks and orders blocks. Txns come from all kinds of apps.
Ordering service adopts an variant of PBFT to reach consensus.
Ordering service is “partially” trusted

Byzantine-fault tolerant
but no penalty for faulty behavior

39 of 40

Hyperledger Fabric Throughput

Figure source: BLOCKBENCH: A Framework for Analyzing Private Blockchains , SIGMOD’17

40 of 40

Conclusion

Tradeoffs made in PoW, PBFT, PoS
Actual systems usually use a combination of consensus protocols
Two case studies: Casper and Hyperledger Fabric

	Efficiency	Security	Simplicity
PoW
PBFT
PoS