Digital Currency – CMSC 414
Digital Currency
CMSC 414
Selected History of Digital Currencies
1983 — Blind Signatures for Untraceable Payments, by David
Chaum ⇒ centralized; DigiCash (1990–1999)
1998 — PayPal ⇒ centralized
2008 — Bitcoin: A Peer-to-Peer Electronic Cash System, by
“Satoshi Nakamoto” ⇒ decentralized
I 2011 — Namecoin (blockchain fork)
I 2012 — Peercoin (source fork)
I 2017 — Bitcoin Cash (blockchain fork)
2015 — Ethereum ⇒ Turing-complete “smart contracts”
I 2016 — Ethereum Classic (blockchain fork)
Short Background on Bitcoin
Digital currency (also called a cryptocurrency) — entirely online
First practical decentralized digital currency — no bank, reserve,
or trustee
Creator known only by a pseudonym
Most existing cryptocurrencies are either based directly on Bitcoin
or are variations on the basic protocol
Coins are mined, which
I Increases the currency supply (incentive to mine)
I Processes transactions (provides value to community)
Security/Threat/Trust Models
Security Model
I Anonymity — users should not be identifiable/traceable
I Correctness — coins should not be double-spent, only mining
should be able to create new currency
I Auditability — all transactions publicly visible/verifiable
Threat Model
I Collusion — large enough group of miners can control the
blockchain
I Deanonymization — multiple transactions with the same
public key can potentially reveal information/identity
Trust Model
I Decentralization — no trusted third party
I Honesty — legitimate transactions will be processed;
illegitimate transactions will not
Transactions
A transaction (abbreviated Tx) has:
I Identifier of an input value In
I Public keys of one or more
recipients
I Output values Outi for each of
the recipients
I Signature of the input value’s
owner
Transactions verifiable by anyone
In ≥
∑
i
Outi
Miner claims a transaction fee
F = In −
∑
Outi
Tx0
PubKey1 In0 Sig0
Tx1
PubKey2 In1 Sig1
Tx2
PubKey3 In2 Sig2
Merkle Trees
Transactions are small, but there are a lot of them
Want to save space, but without losing Auditability
Root Hash
H01
H0
Tx0
H1
Tx1
H23
H2
Tx2
H3
Tx3
included in signed block header
pruned when no longer needed
stored until spent
Wallets
Users can create a new public key for every new transaction
I Many don’t
Most users have a wallet to store bitcoins
I Can hold multiple public keys
I Most Bitcoin software comes with this functionality
Much more convenient
I All coins collected in one place ⇒ know current balance
Using a public key multiple times allows others to correlate
transactions ⇒ loss of Anonymity!
Scripts
Bitcoin includes scripts for signing and verifying
There are standard scripts available
Users can supply their own
Expressiveness of scripts ≡ potential vulnerabilities
Timestamping
Similar to CBC mode encryption (prevents splicing)
Previous block hash included in new block header — H(B′)
Hashing this provides block identifier H(B)
Block Header
H(B′) M n
Block Header
H(B′) M n
Block Header
H(B′) M n
M is the root of a Merkel Tree ⇒ transactions in block, but not in
header (which is what needs to be stored)
n is a nonce
Proof-of-Work
Preimages are hard to compute, but not impossible
Partial preimages are still hard, but easier…
Hard problem: Given X , it is hard to find a value n such that
H(X |n) < T , for some threshold value T
A valid extension of the blockchain is a new block, which has a
header 〈H ′, M, n〉 such that H (H ′|M|n) < T
The threshold decreases over time, making new proofs harder to
complete, occasionally increasing slightly to regulate the rate of
block creation
Resistant against Sybil Attacks — adversary creates many fake
identities to overwhelm a voting system or control a p2p network
Creating New Coins
Miners compute valid hashes to extend the blockchain
The first transaction is a Coinbase Transaction ⇒ generates new
bitcoins
Provides incentive for miners to generate new, valid blocks, rather
than modifying earlier blocks
Any transaction fees are claimed by the miner, providing further
incentive
Bitcoin Modes
Full Node clients download entire blockchain
I Never prune Merkle Trees
I Allows clients to verify any/all transactions and blocks
I Join peer-to-peer network, propagating transaction requests
and blocks ⇒ public audit log
I The more Full Node clients, the more assurance the
blockchain has
Simple Payment Verification Node (SPV) clients only download
block headers (80B), unless they need full blocks
I Much less data to download
I Much less storage required
I Don’t propagate blocks
I Ideal for mobile devices and casual users
SPV Weaknesses
Prune Merkle Trees of unneeded transactions/hashes
⇒ Full Node can drop transactions from block info
Only requests full blocks for transactions of interest
⇒ Requested blocks might reveal client’s public key
We can address the latter by requesting more blocks than we need
⇒ Probabilistic additional block requests using Bloom Filters
Bloom Filters
We generally favor accuracy and correctness
Sometimes it’s worth partially sacrificing these
A Bloom Filter trades accuracy for efficiency
Probabilistic set inclusion
Hi : {0, 1}∗ 7→ [0, n), i ∈ [1, k] BF : {0, 1}n
adding element x to BF : BF [Hi (x)]← 1, ∀i ∈ [1, k]
checking for element y
?
∈ BF : BF [Hi (y)]
?= 1, ∀i ∈ [1, k]
y /∈ BF ⇒ y not in set
y ∈ BF ⇒ y might be in set (depends on set size, k, and n)
SPV client gets to choose its BF parameters
Other Currencies
From https://coinmarketcap.com/charts/
https://coinmarketcap.com/charts/
Other Currencies
Bitcoin the first, still the biggest
Ethereum relative newcomer, but very popular (more later)
Bitcoin Cash hard fork of Bitcoin
Litecoin based on Bitcoin, with different hash algorithm
Ripple fixed supply of coins, focused on banking
Dash (aka Darkcoin, XCoin) based on Litecoin
NEM community-designed, uses Proof-of-Importance
instead of Proof-of-Work ⇒ number of coins and
wallet activity
Monero aims for greater privacy than Bitcoin
IOTA uses DAG generalization of blockchain
NEO Chinese-origin cryptocurrency, similar to Ethereum,
uses Proof-of-Stake
Forking the Block Chain
Not forking a codebase and creating a new coin
Normal Fork Two miners produce blockchain extensions
simultaneously, eventually resolved when one
generates a longer chain
Soft Fork Change of blockchain extension rules, where new
blocks are recognized as valid by old software
Hard Fork Change of blockchain extension rules, where new
blocks are not recognized as valid by old software
⇒ can result in two separate blockchains
Ethereum
See https://github.com/ethereum/wiki/wiki/White-Paper
Unlike Bitcoin’s scripts, Ethereum’s are Turing-complete
Transactions come with gas; consumed in evaluating scripts
⇒ This is in addition to transaction fees
Transactions come with data; can be referenced from other Tx
Allows for Smart Contracts ⇒ enable many distributed systems
Decentralized Autonomous Organization
I a crowdfunding instrument where investors vote to spend
funds
I bug in contract led to “theft” of about $50M
I reaction led to revocation of transactions on Ethereum
blockchain, hard fork to Ethereum Classic of unmodified
blockchain by opponents of the revocation
https://github.com/ethereum/wiki/wiki/White-Paper
Non-Economic Block Chains
Blockchains not only used for financial applications
Any time a public decentralized ledger is useful
Don’t necessarily need proof-of-work
Bitcache, DECENT, Steemit, ...
Content creation/distribution with monetary
compensation for creators
Hyperledger
Open-source blockchain and distributed ledger
project, with multiple protocols
KSI
Commercial blockchain that acts as a public notary