Bitcoin: Publish or Perish 30 November 2017

Bitcoin summary
Bitcoin: Publish or Perish ◦ Public decentralized ledger (block chain)
◦ Of transactions that transfer value (bitcoin) from
◦ one or more “senders” or inputs
P RO F. D R . I R . BA RT P R E N E E L ◦ to one or more “recipients” or outputs
I MEC - CO S I C KU L EU V EN , B E LG I U M ◦ protected by a digital signature
F I RS T N A ME . L A ST N AM E @ ESAT. KU L E U V E N. B E ◦ Integrity of ledger is secured by miners
◦ audit transactions
◦ use proof-of-work to arrive at consensus about the transactions
◦ successful miner receives reward creating new bitcoin
B L O CKCH AIN 2 0 1 7

1 2

Block Chain: a public decentralized ledger Mining hash rate of Bitcoin network
Bitcoin transactions 11 EH/s = 11 ExaHash per second = 1.1 1019 hash/second = 263.3 hash/second = 279.7 hash/day

Block 1 Block 2 Block 3

Exa

block Peta

chain Tera
nonce2 nonce3
(140
nonce1
f “small” f “small” f “small” Gbyte) Giga
0

t1 t2 t3
Mega
Also include in every block timestamp and difficulty level of puzzle
3 4
Bitcoin: Publish or Perish 30 November 2017

Mining has become industrial Mining equipment on Amazon (Feb. 2017)

Sept 2017: $4500

Oct 2017: $3500
Nov 2017: $4098

Slide credit: Joseph Bonneau 5 6

Miners Revenue Block size

7 8
Bitcoin: Publish or Perish 30 November 2017

Cost of Leaderless Consensus Number of Transactions Per Day

Distributed consensus protocol: 3.5 transactions/s
Peak: 7 transactions/s
◦ whichever coalition deploys most hash power, has control of the block chain large share goes to a few addresses
◦ 1.1 1019 hash/second is a significant cost.
Alipay Peak 120.000/s
◦ not performing any useful task! Visa peak 25.000/s
Western Union peak: 750/s
Electricity + Networking costs:
◦ 0.10 W/GH/s or 1000 MWatt
◦ @10 cent per KWh: 1 block costs 16,600$ electricity (12.5 BTC = +/-125,000$)
◦ 0.12% of global electricity consumption; 1 transaction “uses” power of 8 US
households
Profit calculator: http://www.vnbitcoin.org/bitcoincalculator.php
Energy estimates: https://digiconomist.net/bitcoin-energy-consumption

9 10

Cost per Transaction Block Chain Forks

average cost per transaction 5-60$ ◦ Miners check for double spending before including a transaction
◦ Miners broadcast a new valid block to their neighbours immediately, who then propagate it to some of their neighbours etc…
transaction fee/block: 1-2 BTC ◦ The block chain normally is one long chain
◦ Distributed nature of the network can lead to forks:

Block n+1 Block n+2 Block n+3

Block n

Block n+1
transaction fees: 1% of volume
◦ Miners choose on which of 2 possible extensions to work: first block received
◦ Longest chain (weighted by difficulty) will become the main chain, transactions in orphan blocks are rebroadcast
◦ The more block that follow the harder it becomes to change a particular block
◦ Transaction is typically accepted after it is included in 6 blocks (60 minutes)

Visa fees: 2-5% Western Union fees: 2-10% 11 Slide credit: F. Vercauteren 12
Bitcoin: Publish or Perish 30 November 2017

Number of Orphaned blocks Open issues: Bitcoin

Is Bitcoin incentive compatible?
◦ Convergence
◦ Fairness: mining power fraction  revenue fraction
◦ Liveliness

Some proofs exist in simplified models e.g. [Garay-Kiayias-Leonardos, Crypto’17]

13 14

Attacks on Bitcoin Attacks on Bitcoin

◦ Privacy/Anonymity versus other properties
◦ Passive or active
◦ Profit-driven or not

Profit driven
◦ Compliant: not known against Bitcoin
◦ Non-compliant: selfish mining, bribery, double spending
Not-profit driven
e.g. Sybil attack: attacker controls many nodes in network, can refuse relaying or can favour her
own blocks

15 16
Bitcoin: Publish or Perish 30 November 2017

Bitcoin’s Fork Resolving Policy Selfish Mining [bitcointalk2010,Eyal-Sirer’13]

 Longest* chain wins “orphaned
“fork” ” Can gain unfair
 Winner takes all advantage with
23.21% of the
mining power

time time

Selfish miner withholds blocks

(deviates from protocol)
* Longest weighted with difficulty

17 18

Satoshi on Selfish mining Defenses against Selfish mining

Everyone will remain compliant Changing reward structure: no reward for competing blocks; if proof for fork is included
one gets half of lost rewards
◦ miners have invested in mining equipment
◦ not backward compatible
◦ If attacks are detected, value of BTC will crash ◦ opens the door for other attacks
◦ similar issues with collecting signatures on new blocks
Improved mechanism to resolve a tie (e.g. coin flip)
What if you can hide an attack (or plausible deniability)?
◦ works only if selfish miner has less than 23.21%
Attacks have been detected and BTC has not crashed ◦ does not work if miner is ahead

Can we trust human nature? Incorporate time stamp issued by trusted third party
◦ modest improvement
◦ need trusted third party

19 20
Bitcoin: Publish or Perish 30 November 2017

Defenses against Selfish mining (2) Our Assumptions

Decentralized Selfish miners have fraction α < 50% of mining power
Incentive compatible Selfish miner: receives and broadcasts blocks with propagation time = 0
◦ but cannot delay blocks by others
Backward compatible (avoid hard fork)
◦ block validity rules Honest miners: upper bound  on block propagation time between each other
◦ reward distribution policy: only rewards for blocks in main chain Selfish miners do not try to create chaos by publishing blocks with delay  
◦ eventual consensus
In practice:
Sept. 2016: about 50% of nodes receive block within 10 seconds
miners use special propagation networks

21 22

Publish-or-Perish defense: uncles [Zhang-P’17] Publish-or-Perish defense

Miner considers block in time if New Fork Resolution Protocol with parameter k (k=3). Chain wins if
◦ either: it extends its block chain by one ◦ it is ahead by k or more steps
◦ it has the largest weight, where weight is “in time blocks” + number of “in time uncles”
◦ or: same height as current last block but arrives within time 
◦ if weights are tied: flip a coin
( upper bound on block propagation time)
A is an uncle of B if A is an “in time” block that competes with B’s
parent

Miners embed hashes of all uncle blocks in working block

23 24
Bitcoin: Publish or Perish 30 November 2017

Note: second selfish block cannot

include first honest block as uncle as

Publish-or-Perish defense it was created before this block

Evaluation (following [Saphirstein-Sompolinsky-Zohar’16])
Dilemma for selfish miner Markov Decision Process (MDP)
◦ if block S is published, it will be added to the weight of the honest chain as uncle
State: length of honest and selfish chains, weight difference, luck
◦ if block S is hidden, it will be considered to be late and hence not add to the weight (secret non-late block with an honest uncle), who mined last block,
# published selfish blocks
Decision: adopt, override, hide, match, even
Find optimal strategy to maximize reward
Computational overhead: analysis limited to chains of length 13
(approximation)

25 26

Evaluation for α = 0.48

Publish-or-Perish results

27 28
Bitcoin: Publish or Perish 30 November 2017

Bitcoin + publish or perish:

Publish-or-Perish defense: limitations network partitioning
Not 100% incentive compatible Bitcoin: after network partition
Synchronous network ◦ longest chain get all rewards
◦ quick convergence
Broadcasts of blocks around cutoff time ti+ (additional network) ◦ but one can’t tell apart a selfish miner from one separated by a network
Double spending risk if some clients don’t adopt publish-or-perish partition
Natural forks Bitcoin + Publish or Perish
◦ If network partition happens, miners consider the blocks from the other
Transaction fees
side as late hence they don’t count
Bribery ◦ Converge: if one chain is ahead by k or more steps

29 30

Bitcoin + publish or perish:

network partitioning Value of k = tradeoff
Partitioning the network is hard (while selfish mining isn’t) AVERAGE NUMBER OF BLOCKS MINED BEFORE NETWORK
CONVERGENCE
Ethereum’s GHOST protocol also has slow recovery k=2 k=3 k=4

Stellar or Ripple: assume that there is no network partitioning 250

152.14
200

150 95.12

65.03
100
47.08
36.27
28.96 40.96
50 29.9
18.48 23.02
12.97 15.35
4 4.45 4.99 5.69 6.67 7.98
0
0 0. 1 0. 2 0. 3 0. 4 0. 5

31 32
Bitcoin: Publish or Perish 30 November 2017

2017

Complex tradeoff Some observations on Bitcoin

Fast Network Partition Recovery
Can’t distinguish Bitcoin community aspires to be mainstream but behaves as rebels
◦ this is not sustainable
between network
FruitChain
partitioning and selfish Volatile
Bitcoin Backbone (Pass&Shi)
mining (Nakamoto) Paying and secure storage somewhat complex
Winner takes all means No peace of mind for users: if you are hacked, tough luck
that double spending
Most miners are in China (70-80%)
incurs risks
Incentives system complex
Winner Takes All (protect Not clear that the system will survive, but
Incentive Compatible some ideas will for sure
against double-spending)
Publish or Perish
(almost incentive compatible)
33 34

Open issues Questions?

Can we avoid the enormous computational cost? (proof of stake)

Is a zero-governance currency possible?

Bitcoin needs governance for “hard” forks
E.g. Bitcoin cash, argument about Segwit2x and BU

35 36
Bitcoin: Publish or Perish 30 November 2017

Bart Preneel, imec-COSIC KU Leuven

Timestamping (1990)
Collect documents and hash them with a Merkle tree
Chain these trees together with a hash chain
Publish intermediate values on a regular basis

ECRYPT
ADDRESS: Kasteelpark Arenberg 10, 3000 Leuven

WEBSITE: homes.esat.kuleuven.be/~preneel/ CSA

EMAIL: [email protected]   f f
hash
f
TWITTER: @CosicBe 0 chain
TELEPHONE: +32 16 321148
http://www.ecrypt.eu.org t1 t2 t3

37 38

Timestamping: Surety Technologies (1994) Business

http://www.surety.com/ Financial world dislikes
◦ distributed control
◦ full transparency
◦ unclear governance (or anarchy)
◦ uncontrolled money supply

Restrict: write, verify or read (fully private block chain)

39 40
Bitcoin: Publish or Perish 30 November 2017

Distributed Ledger: a range of solutions Distributed Ledger

Public Blockchain
Consortium/Hybrid
Full private Blockchain
distributed database - only needed if
Blockchain ◦ multiple mutually distrustful writers
• No central point of • Controlled by more than • Controlled by one ◦ no intermediate party that is trusted by all players
control by individuals, two individuals, individual, corporation or
corporations or corporations or government (no ◦ interactions or dependencies between the transactions
governments governments consensus needed)
• Permissionless to • Permission on • Permission on
participate participation from participation from owner
Financial sector: disintermediation?
• Concensus based on consortium necessary necessary ◦ 20% seriously investing
“proof ow work” • Arbitrary consensus • Readability of the ◦ 20% planning to invest
• Examples: mechanism blockchain can be public ◦ 20% watching the space very closely
• Bitcoin • Readability of the or restricted to one
• Ethereum blockchain can be public
or restricted to the Aite Group: blockchain market could be worth as much as $400m in annual business by 2019
consortium
• Example: RSCOIN
(UCLondon)

41 42

IBM’s Hyperledger Distributed Ledger

IBM Open Ledger – Hyperledger
(public software)
Accenture, ANZ Bank, CLS, Credits,
Digital Asset, Fujitsu, Initiative for
CryptoCurrencies and Contracts,
Mitsubishi UFJ Financial Group, State
Street, SWIFT, VMware and Wells Fargo

43 https://media.licdn.com 44
Bitcoin: Publish or Perish 30 November 2017

Distributed logging + Privacy Pointers

http://www.project-opacity.com/ http://www.bitcoin.org
http://www.blockchain.com
http://www.vnbitcoin.org/bitcoincalculator.php
http://randomwalker.info/bitcoin/
http://www.coindesk.com/
Nathaniel Popper, Digital Gold, Harper, 2015
Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, Steven Goldfeder. Bitcon and cryptocurrency
technologies, Princeton University Press, 2016
A. Biryukov, D. Khovratovich, I. Pustogarov: Deanonymisation of Clients in Bitcoin P2P Network. ACM Conference
on Computer and Communications Security 2014: 15-29
S. Meiklejohn, M. Pomarole, G. Jordan, K. Levchenko, D. McCoy, G.M. Voelker, S. Savage: A fistful of bitcoins:
characterizing payments among men with no names. Internet Measurement Conference 2013: 127-140
Financial Cryptography conference series

45 46