The University of Sydney Page 1
COMP3221: Distributed
Systems
Concensus-Blockchain
Unit Coordinator
Dr Nguyen Tran
School of Computer Science
The University of Sydney Page 2
Introduction
– Consensus is a fundamental problem of distributed computing.
Existing protocols have relaxed assumptions these past three
decades to solve consensus
– Today, with the recent advent of blockchains, new consensus
implementations were proposed to make replicas reach an
agreement on the order of transactions updating what is often
referred to as a distributed ledger.
The University of Sydney Page 3
Outline
– The Blockchain Abstraction
– Mining and consensus
– Execution
– Resolving a fork
– Impact of mining power
The University of Sydney Page 4
Blockchain Abstraction
Blockchain
The University of Sydney Page 5
The Blockchain abstraction
Let G = ⟨B, P⟩ a directed acyclic graph (DAG) where blocks B point to
each other with pointers
⟨b0, b1⟩ ∈ P is a pointer from current block b1 to previous block b0
The pointer is a representation of a hash of the destination block that
the source block contains
The genesis block is a special block known initially by all participants
Data
Pointer to Data
Hash of Data
Data
Data
Pointer to Data
Hash of Data
Data
Pointer to Data
Hash of Data
Data
Pointer to Data
Hash of Data
Genesis BlockBlock 1Block 2Block 3Block 4
The University of Sydney Page 6
Node types and roles
– Network routing nodes
– All nodes validate and propagate
transactions and blocks.
– Full node
– Maintain a complete up-to-date
copy of the blockchain
– Wallet
– Usually the case with desktop
blockchain clients.
– Maintain only a subset of the
chain.
– Verify transactions using a method
called simplified payment
verification.
– Miner
– Compete to create new blocks.
– Some are full nodes, while others
are lightweight nodes
participating in pool mining.
The University of Sydney Page 7
Blockchain applications
The University of Sydney Page 8
Cyptocurrencies
The University of Sydney Page 9
Distributed implementation of a blockchain
It implements a distributed ledger that is
– Immutable: transactions can only be appended to the ledger
– Pseudonymous: participants are identified by their address
(pseudonym)
It uses:
– A Gossip-based protocol for maintaining an overlay
– Peer-to-peer network where peers are both clients and servers
(miners)
– Public key cryptosystem, participant sign their transactions
– Consensus for the distributed system to decide a block
The University of Sydney Page 10
Why is consensus needed in blockchain?
Consensus is necessary to totally order the blocks, maintaining the chain
Disagreement ⇒
no chain but a DAG
The University of Sydney Page 11
Mining and Consensus
Blockchain
The University of Sydney Page 12
Miners
Mining is the process by which
– New bitcoin is added to the money supply.
– Secures the bitcoin system against fraudulent transactions
Mining rewards
– New coins created with each new block
– Transactions fees from all the transactions included in the block.
To receive these rewards, Miners compete to solve a cryptopuzzle. The
solution to the cryptopuzzle, called the “Proof-of-Work”, is included in the
new block and act as proof that the miner expended significant computing
effort.
The University of Sydney Page 13
Mining Rewards
– Mining reward cut in half every 4 years, precisely every
210,000 blocks
– Started as 50 bitcoins per block in January 2009, down to 12.5
(2016) and then 6.25 (2020) bitcoins per block.
– Then, after the year 2140, when all bitcoins 20.99999998 million
will have issued, no new bitcoins will be issued
– Today, miners earn more from mining rewards, little from
transactions fees.
– After 2140, miners will only receive transactions fees.
– However, the primary purpose of the mining is not the reward or
generation of new coins, but securing the bitcoin system
The University of Sydney Page 14
Quiz 1
Blockchain
The University of Sydney Page 15
Question 1
– Why mining reward is halved in every 4 years ?
The University of Sydney Page 16
Mining Rewards
– Why mining reward is halved in every 4 years ?
– Finite and diminishing issuance creates a fixed monetary supply that resists
inflation. (Bitcoins can never be inflated by printing unlike a fiat currency)
– However, bitcoin will tend to be inherently deflationary, the opposite of the
inflation.
The University of Sydney Page 17
Miners
– Every bitcoin node, including miners, before forwarding
transactions to its neighbours, will first verify the transaction
against a long checklist.
– Checklist – https://en.bitcoin.it/wiki/Protocol_rules
– After validating transactions, they will be added to memory
pool, or mempool, or transaction pool, where transactions wait
until they can be included (mined) into a block.
– To miners, receiving a new block means someone else has won
the current competition, and it is also the time to start the race
for finding the next block.
https://en.bitcoin.it/wiki/Protocol_rules
The University of Sydney Page 18
Constructing a block
– Transactions are selected from the memory pool.
– Transactions are prioritized to include old and high-value
transactions into the current block
– Priority = sum (value of inputs * input age)/ Transaction size
– First 50KB of transaction space on a block is set aside for high-
priority transactions.
– Note: transaction fee is not considered.
– Rest is filled up to the maximum block size by minimum fee
transactions and then if there is space no-fee transactions are
included.
– Miners may ignore to include transactions without fees
– Transactions left in the memory pool will remain there to be included
in the next block.
The University of Sydney Page 19
Constructing a block
– First transaction added to the block is a special transaction,
generation transaction, or coinbase transaction.
– Coinbase transaction contains the mining reward;
– Total reward = Mining reward (6.25) + total transaction fees.
– Constructing the block header
The University of Sydney Page 20
Constructing a block
– Previous block hash
– Hash of the block header of the previous block known (received from
the network) to the miner.
– Merkle Root
– Summary of all transactions selected to be included in the block with a
Merkle tree.
– Merkle tree, also known as a binary hash tree, is a data structure used
for efficiently summarizing and verifying the integrity of large sets of
data
The University of Sydney Page 21
Constructing a block
– Merkle tree
– Pair transactions and calculate double-SHA hash until there is only one
hash, or the merkle root.
• HA = SHA256(SHA256(Transaction A))
– Can check if any transaction is included in the tree with at most
2log2(N) hash calculations.
– This allows Wallet nodes to check whether transactions are
included in a block without downloading the whole block.
The University of Sydney Page 22
Constructing a block
– Difficulty target & Nonce
– Mining is the process of hashing the block header repeatedly changing one
parameter (nonce), until the resulting hash is less than a threshold.
– This threshold is the difficulty target.
– F(block, nonce) à SHA256(SHA256(nonce, block)) < difficulty target
– Hash result cannot be determined in advance, nor can find a
pattern.
– The only way to find a matching hash result is to try again and
again, randomly modifying the input.
– The resulting Nonce is the proof-of-work [DN93]:
– finding the nonce takes time, but
– validating that the nonce is correct is easy.
[DN93] C. Dwork and M. Naor. Pricing via processing or combatting junk mail. In Proceedings of the 12th Annual
International Cryptology Conference on Advances in Cryptology, CRYPTO '92, pages 139-147, 1993.
The University of Sydney Page 23
Constructing a block
– Smaller the threshold it is more difficult to find a nonce.
– Equivalent to how many zeros are at the beginning of resulting 256
bit hash ?
– Bitcoin difficulty is adjusted every 2016 blocks to keep 10minute
block interval (2 weeks).
– Every full node adjust difficulty level by;
– New difficulty = old difficulty * (actual time of last 2016 blocks/20160
minutes)
– Note: theoretically new difficulty can go up or down.
– To avoid extreme volatility, adjustment must be less than a factor
of four.
– Ethereum difficulty adjusted near real-time (block by block) to
keep 12-13 seconds block interval.
The University of Sydney Page 24
Constructing a block
– Once a miner finds a matching nonce, miner immediately
transmits the block to all its peers.
– Each peer validates the block with a series of tests and
propagate the block to the network.
– Validating that the nonce is correct is easy.
– Everyone can verify that someone lied about having solved the puzzle
– Miners practically do not act dishonestly because,
– If someone found that miner is lied, the block will be rejected, miner will
not be rewarded and miner wasted time and electricity without
compensation.
The University of Sydney Page 25
Execution
Blockchain
The University of Sydney Page 26
Gossip-based protocol
Current blockchain state
The University of Sydney Page 27
New transaction
Let’s transfer 10BTC from
my account to Alice’s
account
The University of Sydney Page 28
Broadcast
The University of Sydney Page 29
Broadcast
The University of Sydney Page 30
Mining into a block
The University of Sydney Page 31
Mining into a block
The University of Sydney Page 32
Consensus
The University of Sydney Page 33
Consensus
The University of Sydney Page 34
Consensus
The University of Sydney Page 35
Consensus
To break tie, choose block with the hash that
has the greatest prefix of zeros.
The University of Sydney Page 36
Consensus
The University of Sydney Page 37
Resolving a Fork
Blockchain
The University of Sydney Page 38
Blockchain Forks
– When a new block arrives, the node will try to slot it into the
existing chain based on the “previous block hash” field.
– Nodes maintain three sets of blocks;
– Main blockchain
– Secondary chains – Branches of the main blockchain
– Orphans – Blocks that do not have a known parent
– Bitcoin consensus
– Chain of blocks has the most cumulative difficulty associated with it at
any given time.
– Often this is the chain with most blocks in it, unless there are two equal
length chains and one has more proof-of-work.
The University of Sydney Page 39
Bitcoin’s consensus chooses the deepest branch
State
⟨Bi,Pi⟩ the local blockchain view
Each peer of the blockchain executes:
Receive blocks ⟨Bj, Pj⟩ from j
Bi = Bi ∪Bj
Pi = Pi ∪Pj
depth(b):
if children(b) = ∅ then return 1
else return 1 + max c ∈children(b) depth(c)
Prune shortest branches at i
b = genesis-block(Bi)
while b.next ≠⊥
block = argmax c ∈children(b) { depth(c) }
B = B ∪ {block}
P = P ∪ {⟨block,b⟩}
b = block
⟨Bi,Pi⟩ = ⟨B,P⟩
[Nak08] S. Nakamoto, “Bitcoin: a peer-to-peer electronic cash system,” 2008,
http://www.bitcoin.org.
The University of Sydney Page 40
Bitcoin’s consensus chooses the deepest branch
– It is exceedingly rare more than two blocks of fork in public
blockchain.
The University of Sydney Page 41
Ethereum consensus
[SZ15] Y. Sompolinsky and A. Zohar, “Secure high-rate transaction processing in
bitcoin,” in Financial Cryptography and Data Security FC’15, 2015, pp. 507–527.
… was inspired by the choice of the greedily heaviest
observable subtree (GHOST)
The University of Sydney Page 42
Bitcoin vs. Ethereum/GHOST
The University of Sydney Page 43
Ethereum branch selection
– Ethereum codebase evolved dramatically over the past
two years
– While originally stated as inspired by GHOST, Ethereum’s
branch selection algorithm is currently different:
– Ethereum selects the branch with the highest total difficulty,
which is the sum of the difficulties of all the cryptopuzzles
of its last block and its ancestors.
The University of Sydney Page 44
Quiz 3
Blockchain
The University of Sydney Page 45
Question 4
What are the blocks of the branch selected by Bitcoin?
The University of Sydney Page 46
Question 5
What are the blocks of the branch selected by Bitcoin?
What are the blocks of the branch selected by the GHOST
protocol?
The University of Sydney Page 47
Quiz 4
Blockchain
The University of Sydney Page 48
Question 6
What is the PoW mechanism useful for?
The University of Sydney Page 49
Sybil attack
A Sybil attack is an attack where a malicious user forges identities
It is named after the subject of the book Sybil, a case study of a
woman diagnosed with dissociative identity disorder.
Some solutions [CL02] are prone to Sybil attacks where an adversary
generates fake faulty nodes to have f ≥ n/3 ⇒consensus impossible.
The University of Sydney Page 50
Question 7
What is the PoW mechanism useful for?
What is its major drawback?
The University of Sydney Page 51
Impact of Mining Power
Blockchain
The University of Sydney Page 52
Mining and hashing power race
– From CPU to GPU to FPGA to ASIC (application-specific
integrated circuits)
– ASIC mining lead to a giant leap in mining power, SHA256
function directly on silicon chips specialized for mining. First
ASIC ship had more power than entire bitcoin network in 2010.
– Hashing power growth
– 2009 - 0.5 MH/sec–8 MH/sec (16× growth)
– 2010 - 8 MH/sec–116 GH/sec (14,500× growth)
– 2011 - 16 GH/sec–9 TH/sec (562× growth)
– 2012 - 9 TH/sec–23 TH/sec (2.5× growth)
– 2013 - 23 TH/sec–10 PH/sec (450× growth)
– 2014 - 10 PH/sec–150 PH/sec in August (15× growth)
The University of Sydney Page 53
Impact of mining power
10MH/s
3MH/s
2MH/s
1MH/s
3MH/s
Current Blockchain
The University of Sydney Page 54
b1
b1
10MH/s
3MH/s
2MH/s
1MH/s
3MH/s
Impact of mining power
Current Blockchain
The University of Sydney Page 55
b2
b2
b1
b1
10MH/s
3MH/s
2MH/s
1MH/s
3MH/s
Impact of mining power
Current Blockchain
The University of Sydney Page 56
b2
b1 b3
10MH/s
3MH/s
2MH/s
1MH/s
3MH/s
Impact of mining power
Current Blockchain
b3
The University of Sydney Page 57
b4
b2
b1
b4
b3
10MH/s
3MH/s
2MH/s
1MH/s
3MH/s
Impact of mining power
Current Blockchain
The University of Sydney Page 58
b5
b2
b1
b4
b3
b5
10MH/s
3MH/s
2MH/s
1MH/s
3MH/s
Impact of mining power
Current Blockchain
The University of Sydney Page 59
b5
b2
b1
b4
b3
b5
10MH/s
3MH/s
2MH/s
1MH/s
3MH/s
[Ros12] M. Rosenfeld, “Analysis of
hashrate-based double-spending,” 2012.
Impact of mining power – 51% Attack
Current Blockchain
The University of Sydney Page 60
Quiz 5
Blockchain
The University of Sydney Page 61
Question 8
Why can't we increase the size of each block to speedup Bitcoin?
The University of Sydney Page 62
Question 9
Why can't we reduce the difficulty of a crypto-puzzle to speedup
Bitcoin or Ethereum?
The University of Sydney Page 63
What’s Next ?
– Mid-term quiz on Wednesday.
– Assignment 2 will be out next week.
- First lecture about Machine Learning next week.
– See you all next week !