Blockchains
CS 3IS3
Ryszard Janicki
Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada
Acknowledgments: Based on material provided by Mark Stamp
Ryszard Janicki
Blockchains 1/38
Digital Currency
We want create an all-digital currency Like $, or , or £, or …., but “better”
Real cash is (relatively) anonymous So digital currency should be too
Digital currency is “better” since. . .
No central authority (i.e., banks)
No government to issue currency, etc.
Ryszard Janicki
Blockchains 2/38
Preliminaries: Work
How to measure (digital) work ? Our unit of work will be 1 hash
Suppose that we have a hash function h(x) that generates an N-bit output
Then randomly chosen input generates one of 2N equally likely outputs
For any input R, have, 0 ≤ h(R) ≤ 2N Different R yield uncorrelated hashes
Ryszard Janicki
Blockchains 3/38
Hashing and Work
Suppose we have a 16-bit hash function
For any R, we have 0 ≤ h(R) < 65,536
If we want R so that h(R) < 64 = 000000000010000, then how many R values do we need to hash?
Since
h(R) = y = (y15y14y13y12y11y10y9y8y7y6y5y4y3y2y1y0) we want output like (10 leading 0s). . .
h(R) = y = (0000000000y5y4y3y2y1y0)
For 16-bit hash, how many hashes until h(R) = y = (0000000000y5y4y3y2y1y0)?
For random R, we have a 1/2 chance that
y = (0y14y13y12y11y10y9y8y7y6y5y4y3y2y1y0) And 1/4 chance that
y = (00y13y12y11y10y9y8y7y6y5y4y3y2y1y0) And 1/8 chance that
y = (000y12y11y10y9y8y7y6y5y4y3y2y1y0) And so on...
Ryszard Janicki
Blockchains 4/38
Work and Hashing
For 16-bit hash, if someone gives us an R such that h(R) < 64 = 000000000010000
Then expected number of hashes computed is 210 = 1024 (“expected” means average case)
That is, they have done 1024 units of work
We use hashing to show work was done
We can adjust parameter so more work (or less) is required
For N-bit hash, if we require h(R) < 2n then expected work is 2N−n hashes
Note: We can easily verify that the expected amount of work was done
Only requires a single hash
No matter how much work to find R
Ryszard Janicki
Blockchains 5/38
Preliminaries: Ledgers
Ledger is a book of financial accounts
Suppose Alice, Bob, Charlie, Trudy play weekly poker game
online
They all insert ledger entries such as,
“Bob owes Alice $10”, “Charlie owes Trudy $30”, “Trudy owes Alice $25”, and so on
Once a month, they meet and settle up Any possible problems here?
Ryszard Janicki
Blockchains 6/38
Signed Ledger Entries
How to prevent Trudy from inserting, say, “Bob owes Trudy $1M” ?
Let’s require digital signatures
For ledger entry to be valid, Bob must sign “Bob owes Alice $10”, Trudy must sign “Trudy owes Alice $25”, and so on . . .
Then we know ledger entries are valid That is, the payer agrees to pay
Public Key Notation
Sign message M with Alice’s private key: [M]Alice Encrypt message M with Alice’s public key: {M}Alice
Ledger now looks like
[Bob owes Alice $10]Bob
[Charlie owes Trudy $30]Charlie [Trudy owes Alice $25]Trudy and so on ...
And we know ledger entries are valid But, still some problems here. . .
Ryszard Janicki
Blockchains 7/38
Signed Ledger in Detail
Ledger now looks like
[Bob owes Alice $10]Bob
[Charlie owes Trudy $30]Charlie [Trudy owes Alice $25]Trudy and so on ...
As an aside, note that signatures above really look like (M1,[h(M1)]Bob), where M1 = “Bob owes Alice $10”
(M2, [h(M2)]Charlie ), M2 = “Charlie owes Trudy $30” (M3, [h(M3)]Trudy ), M3 = “Trudy owes Alice $25” And so on ...
We’ll use the shorthand from the beginning of this slide
Ryszard Janicki
Blockchains 8/38
Ledger Duplication and Unique Ledger Entries
Still, nothing to prevent Trudy from duplicatinga line. . . [Bob owes Alice $10]Bob
[Charlie owes Trudy $30]Charlie [Trudy owes Alice $25]Trudy [Charlie owes Trudy $30]Charlie
Signatures are still all valid
How to prevent this attack?
Include unique transaction numbers
[1, Bob owes Alice $10]Bob
[2, Charlie owes Trudy $30]Charlie [3, Trudy owes Alice $25]Trudy and so on ...
Why does this help?
We will never have an exact duplicate So any duplicate is invalid
Ryszard Janicki
Blockchains 9/38
Ledger Prepayment I
How to be sure participants pay up?
Can start with Alice, Bob, Charlie, and Trudy all putting money into the pot
And don’t allow any transaction that would result in negative balance
Transaction must still be signed and . . .
. . . now, nobody can “overdraw” account Ledger example. . .
Alice has $100 // Alice’s initial stake Bob has $100 // Bob’s initial stake Charlie has $100 // Charlie’s initial stake Trudy has $100 // Trudy’s initial stake [1, Bob owes Alice $10]Bob // valid
[2, Charlie owes Trudy $30]Charlie // valid [3, Trudy owes Alice $25]Trudy // valid [3, Trudy owes Bob $120]Trudy // invalid
Ryszard Janicki
Blockchains 10/38
Ledger Prepayment II
Ledger example. . .
Alice has $100 // Alice’s initial stake
Bob has $100 // Bob’s initial stake Charlie has $100 // Charlie’s initial stake Trudy has $100 // Trudy’s initial stake [1, Bob owes Alice $10]Bob // valid
[2, Charlie owes Trudy $30]Charlie // valid [3, Trudy owes Alice $25]Trudy // valid [3, Trudy owes Bob $120]Trudy // invalid
Note that we must know the entire transaction history So that we can know current balances
Then we can be sure a given transaction does not cause user to be overdrawn
This seems like kind of a hassle, but some big benefits come from it
Ryszard Janicki
Blockchains 11/38
Eternal Ledger?
Alice, Bob, Charlie, and Trudy could continue to settle accounts each month
But, as the ledger currently stands, settling accounts is not necessary!
We know the current balances, and no risk of anyone being “overdrawn”
So, could play poker for months, years, or forever, without settling accounts
Ryszard Janicki
Blockchains 12/38
Ledger as Currency
This ledger can act as its own currency! We need a symbol, let’s use “§”
Transactions within ledger are all in terms of § currency protocol
Anyone can exchanged ledger currency (i.e., §) for $, or £, or , or ...
But, such exchanges occur outside the ledger currency protocol
Ryszard Janicki
Blockchains 13/38
Ledger Currency
For example, Alice could pay Bob $10 in real world dollars for, say, §5 of currency in the ledger system
Comparable to exchanging, say, CAN$ for £
But, ledger is a history of transactions within the ledger
currency system
In fact, the ledger is the currency
This is the key insight for cryptocurrency
Ryszard Janicki
Blockchains 14/38
Distributed Ledger I
The ledger is the currency
So who is in charge of the ledger?
A government? The UN? A bank? An individual?
We don’t trust them, so let’s make everybody in charge of the ledger
Anybody can have copy of ledger, anyone can add entries (there is a protocol. . . )
Protocol without a central authority
What problem(s) do you foresee?
Ryszard Janicki
Blockchains 15/38
Distributed Ledger II
1 Transactions must be signed
2 Nobody can be overdrawn
3 Transactions broadcast to everybody
How to have a consistent view of this distributed ledger? Multiple ledgers exist at any time
This is the heart of the issue for a distributed cryptocurrency (e.g. Bitcoin)
Ryszard Janicki
Blockchains 16/38
Distributed Ledger and Work
Every ledger will have some amount of work associated with it And, ledger with most work “wins”
That is, everyone accepts ledger that has the most work put into it
Recall, work is measured in hashes So, more hashes is “more better”
Ryszard Janicki
Blockchains 17/38
Blocks and Hashes
Each transaction is signed
Transactions grouped into blocks
Let B be one such block
Find (nonce) R so that h(B, R) < 2n
Just fancy way of saying h(B,R) starts with a specified number of 0s
Work required to find R?
On average 2N−n hashes for N-bit hash
Ryszard Janicki
Blockchains 18/38
Chain
We don’t want to revalidate each block, want to order blocks, and so on
We’ll chain blocks together
Put hash of previous block in header of current block before
computing hash
So, must find a nonce R so that h(Y,B,R) < 2n Where Y is hash of previous block
Ryszard Janicki
Blockchains 19/38
Blockchain
We now have
Yi+1 = h(Yi,Bi,Ri) < 2n
Yi+2 = h(Yi+1, Bi+1, Ri+1) < 2n Yi+3 = h(Yi+2, Bi+2, Ri+2) < 2n
Each B is a block
Block is a group of signed transactions Each nonce R is chosen so inequality holds Much work to find R, easy to verify Yj < 2n
Ryszard Janicki
Blockchains 20/38
Mining?
Anyone can create a new block
But lots of work to find a valid hash
So what is the incentive to do work? “Free” money!
Get (new) money for doing work, say, § 1
Put this info at start of block, does not need to be signed (since new money)
Ryszard Janicki
Blockchains 21/38
One Block
One Block
lock B looks like... iBlockBi lookslike...
chain
Ryszard Janicki
Blockchains 22/38
B
k
Mining I
Free money, so miners are in a race to find hashes that yield valid blocks
The more computing power a miner has, the better chance to win race
Once a valid hash is found, miner sends the block out to everybody
Again, easy to verify hash is correct
Ryszard Janicki
Blockchains 23/38
Blockchain
Blockchain
Blockchain looks like... Blockchainlooks like. . .
Blockchain
Ryszard Janicki
Blockchains 24/38
Mining II
Why is “mining” called mining ? Really, just finding a valid block hash
Miner is doing work, and creating new money that did not previously exist
In a sense, this is comparable to mining gold or silver (for example)
This may be the most misunderstood part of cryptocurrency protocols
Ryszard Janicki
Blockchains 25/38
Non-Miners
Users do not have to be miners
Non-miner just wants blockchain
Needed to know how many §s others have
Also, non-miner sends out transactions for others to make blocks (and mine)
User might see conflicting blockchains What to do in such cases???
More work is “more better”!
Ryszard Janicki
Blockchains 26/38
More Work
If conflicting blockchains, how to know which represents more work?
Each block is a fixed amount of work In terms of expected number of hashes So, longer block chain is more work Thus, longer block chain always wins If it’s a tie, wait until one is longer
Ryszard Janicki
Blockchains 27/38
Summary of Protocol
1 New transactions broadcast
2 Miners collect transactions into blocks
3 Miners race to find valid block hash
4 When miner finds hash, broadcast it
5 Block accepted if all transactions signed, no overdraft, and block hash valid
6 New block extends blockchain
Miners use hash of new block in next block
Ryszard Janicki
Blockchains 28/38
Attack Scenario
Suppose Trudy makes a block B that includes transaction [Trudy pays Alice §100]Trudy
Trudy sends B to Alice only, nobody else
Question: Why would Trudy do this? Answer: So she can spend that §100 again
Trudy likes double spending! It’s free money!
Ryszard Janicki
Blockchains 29/38
Double Spending
For Trudy’s double spending attack to work, she must compute valid hash.
That is, find R, so that h(Y,B,R) < 2n
And send chain with block B to Alice
But, nobody else knows about B, or the chain that contains it
All other miners working on other chains Those other chains can (and will) grow Trudy is in ongoing race with all miners
Ryszard Janicki
Blockchains 30/38
Double Spending Attack
Alice will reject Trudy’s chain once a longer chain appears Trudy would need most of computing power in the network to
win
Trudy needs to win a lot!
Or, miners collude with Trudy
But is it in their interest to do so?
Ryszard Janicki
Blockchains 31/38
Blockchain
From users perspective. . .
Transaction in last block might not be entirely trustworthy
Possibility of double spending attack
But, the more blocks that follow, the more certain that a transaction is valid
Just wait until a few more blocks are added before accepting a transaction
Ryszard Janicki
Blockchains 32/38
Refinements I
Number of hashes can change so that winning hash takes constant time
Computing power in network can increase In Bitcoin, new block every 10 minutes
Can decrease mining reward so money supply does not grow forever
E.g., maximum of 21,000,000 bitcoins Then what will be incentive for miners?
Ryszard Janicki
Blockchains 33/38
Merkle Tree
A hash tree or Merkle tree is a tree in which every leaf node is labelled with the cryptographic hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes.
Hash trees allow efficient and secure verification of the contents of large data structures.
Hash trees are a generalization of hash lists and hash chains.
Demonstrating that a leaf node is a part of a given binary hash tree requires computing a number of hashes proportional to the logarithm of the number of leaf nodes of the tree
This contrasts with hash lists, where the number is proportional to the number of leaf nodes itself.
Ryszard Janicki
Blockchains 34/38
Merkle Tree Example
An example of a binary hash tree.
Hashes 0-0 and 0-1 are the hash values of data blocks L1 and L2, respectively, and hash 0 is the hash of the concatenation
About this interface | Discussion | Help
of hashes 0-0 and 0-1.
Ryszard Janicki
Blockchains 35/38
Refinements II
Merkle tree can be used to reduce storage requirements
Transactions in a block hashed in a tree, only the root is needed in block hash
Simplified payment verification
In effect, rely on others to verify for you Combining and splitting value
Transaction can have multiple input/output
Ryszard Janicki
Blockchains 36/38
Privacy?
Can use pseudonym in public key
But, can still connect transactions to a specific public key
Might be able to tie public key to an individual based on transactions
We’ll see examples like this later. . . Not a strong form of anonymity Bitcoinis said to be “pseudonymous”
Ryszard Janicki
Blockchains 37/38
Future of Blockchains?
Blockchaincan be viewed as a way to implement a distributed ledger
Useful for cryptocurrency, but many other possible applications too
Blockchain are said to be a “foundational” and/or “disruptive” technology
Controversial , but probably neither...
See an excellent video about bockchains: https://www.youtube.com/watch?v=bBC-nXj3Ng4
Read a paper about ’bitcoins’ that on the course website
Ryszard Janicki
Blockchains 38/38