ĐẠI HỌC NGÂN HÀNG THÀNH PHỐ HỒ CHÍ MINH
Chapter 3
CONSENSUS PROTOCOL
AND
MINING
TP. HCM 2022
OVERVIEW
§ The Byzantine Generals Problem
§ Proof of Works
§ Proof of Stakes
§ Crypto currency mining
2
THE BYZANTINE GENERALS PROBLEM
The abstract problem:
§ Each division of Byzantine army is directed by its own general.
§ There are n Generals, some of which are traitors.
§ All armies are camped outside enemy castle, observing enemy.
§ Communicate with each other by messengers.
§ Requirements:
o G1: All loyal generals decide upon the same plan of action
o G2: A small number of traitors cannot cause the loyal generals to
adopt a bad plan
§ Note: We do not have to identify the traitors.
3
THE BYZANTINE GENERALS PROBLEM
4
SOLUTION I: ORAL MESSAGES
A commanding general must send an order to his n-1
lieutenant generals such that:
Ø All loyal lieutenants obey the same order
Ø If the commanding general is loyal, then every loyal
lieutenant obeys the order he sends
5
L. Lamport, R. Shostak, and M. Pease, “The Byzantine generals problem,” ACM TOPLAS, vol. 4, pp. 382–401, July 1982.
SOLUTION I: ORAL MESSAGES
COMMANDER
v v
v
v x
LEUTENANT 1 LEUTENANT 2 LEUTENANT 3
v v
traitor
Final decision = majority(v,v,x) = v
6
L. Lamport, R. Shostak, and M. Pease, “The Byzantine generals problem,” ACM TOPLAS, vol. 4, pp. 382–401, July 1982.
SOLUTION I: ORAL MESSAGES
traitor
COMMANDER
x z
y
x z
LEUTENANT 1 LEUTENANT 2 LEUTENANT 3
y y
Final decision = majority(x,y,z) = default decision (retreat)
7
L. Lamport, R. Shostak, and M. Pease, “The Byzantine generals problem,” ACM TOPLAS, vol. 4, pp. 382–401, July 1982.
SOLUTION II: SIGNED MESSAGES
A signed message satisfies all the conditions of
oral message, plus two extra conditions:
§ Signature cannot be forged. Forged message
are detected and discarded by loyal generals.
§ Anyone can verify its authenticity of a
signature.
Signed messages improve resilience.
8
SOLUTION II: SIGNED MESSAGES
COMMANDER
COMMANDER
traitor
1{0} 1{0}
1{0} 0{0}
0{0,2}
traitor 0{0,2}
LEUTENANT 1 LEUTENANT 2 1{0,1}
LEUTENANT 1 LEUTENANT 2
discard
9
SOLUTION II: SIGNED MESSAGES
SIGNATURE PATH
v{0}
1
4
0 v{0,1}
v{0,1,5,4}
v{0,1,5}
5
6
v{0,1,5,4,6}
2 v{0,1,5,4,6,3}
10
BLOCKHAIN CONSENSUS – PROOF OF WORK
difficulty
11
BLOCKHAIN CONSENSUS – PROOF OF WORK
difficulty
12
BLOCKHAIN CONSENSUS – PROOF OF WORK
Pros Cons
Better ability to be Slower transaction
decentralized speeds
Higher costs to
Better security
validate transactions
Higher energy
consumption
13
BLOCKHAIN CONSENSUS – PROOF OF STAKE
14
BLOCKHAIN CONSENSUS – PROOF OF STAKE
15
BLOCKHAIN CONSENSUS – PROOF OF STAKE
Pros Cons
Less energy Harder to truly
consumption decentralize the
network
Less security than
Financial opportunities
PoW
Faster transaction
speeds
16
BLOCKHAIN CONSENSUS
17
BLOCKHAIN CONSENSUS
18
BITCOIN PROOF OF WORK DIFFICULTY
§ Targets 10 minute average block generation time
§ Defined by the # of leading zeros Hash output requires to solve PoW
§ Adjusts every 2016 blocks - about every two weeks
§ Currently, > 18 leading zeros (out of 64 hexadecimal characters)
§ Block 749,952 (08/26/2022)- 19 leading zeros
00000000000000000007edd9a88903ad4f948bf3def71a520635ec769065429a
§ Genesis Block (1/3/09) – 10 leading zeros, though only required 8
000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f
19
https://www.blockchain.com/
BITCOIN PROOF OF WORK DIFFICULTY
20
https://btc.com/stats/diff
EVOLUTION OF BITCOIN MINING
GPU ASIC
2009 2010 2010 2013 2014
CPU Mining pools Mining farms
21
BITCOIN MINING
22
BITCOIN MINING
23
BITCOIN MINING REWARDS
Starts at 50 BTC / mined block Current: 6.25 BTC / mined
block
24
Halves every 210,000 blocks
BITCOIN NETWORK
§ Full Nodes – Store full Blockchain & able to Validate all Transactions
§ Pruning Nodes – Prune transactions after validation and aging
§ Lightweight Nodes - Simplified Payment Verification (SPV) nodes –
Store Blockchain Headers only
§ Miners – Performs Proof of Work & Create new Blocks - Do not need
to be a Full Node Mining Pool Operators
§ Wallets – Store, View, Send and Receive Transactions & Create Key
Pairs
§ Mempool – Pool of unconfirmed (yet validated) Transactions
25
READINGS
1. Narayanan, A., & Clark, J. (2017). Bitcoin's academic
pedigree. Communications of the ACM, 60(12), 36-
45. https://doi.org/10.1145/3132259
2. Ethereum white paper
26
DISCUSSION
27
