Announcements¶
Homework
- Homework 1 has been posted on Piazza. It is due on Friday 2/3 on Gradescope.
- Please see Piazza note 27 about removing the requirement to generate the same signature as we did.
- Homework 2 will be posted later this week, and due Friday 2/10.
Office hours
- Nicolas: Monday 1-3pm in CCDS room 1322
- Mayank: Thursday 11:30am-1pm in CCDS room 1343
- Office hours will be in a hybrid format
Lecture 5: Making Bitcoin Simpler to Use¶
Review from last lecture¶
Our starting point into cryptocurrencies is to build a digital version of a banking system, where electronic monetary transfers should be "secure" against "powerful adversaries."
More precisely, we want to record all transactions within a blockchain. It is a sequence of blocks, which themselves contain several transactions.
If everyone acts honestly, the intention is that the chain is append-only: new blocks are only added to the end of the chain.
[Image source: Nakamoto whitepaper]
At a high level, there are three types of participants within Bitcoin.
A light client only needs to hold one or more secret keys for a digital signature scheme. (And optionally also a small amount of additional data, which we will discuss today.)
A node additionally stores the entire state of the blockchain (currently 451 GB) and oftentimes connects to other nodes.
A miner additionally tries to write new blocks on the blockchain.
At any given time, many (but not all) of the nodes and miners are connected through a peer-to-peer network that they can use to broadcast new transactions and blocks.
Bitcoin relies on the following assumption:
The majority of the computational power used for mining (at any given time) is controlled by honest miners -- that is, miners who will obey the rules out of a combination of good-will and self-interest.
If this assumption is violated, then Bitcoin could be unstable. This is called a 51% attack.
Even if this assumption holds, we must ensure that the currency is resilient even if some of the miners are dishonest!
A dishonest miner could potentially cause a lot of havoc to a cryptocurrency. It cannot digitally sign away your money, but still there are 3 types of attacks that we want to avoid.
Censorship: The miner refuses to post certain transactions.
Inconsistency: The miner sends different states of the blockchain to different nodes.
Double spending: The miner deletes or overwrites transactions from earlier blocks.
[Image source: Mango Research]
Bitcoin addresses all of these problems through its proof of work puzzles. They provide several features.
- Randomized leader election: miners can only create a new block by performing a lot of computational effort. Specifically, they must find a
noncethat causes the entire block to hash to a number that is smaller than the prescribed difficulty level. - Eventual consistency: nodes and miners always use the largest blockchain (or more precisely, the one with the most cumulative difficulty to create).
[Image source: blockchain.info]
Overall, here is the high-level idea of Bitcoin's consensus algorithm (adapted from Abhishek Jain's slides)
- New transactions are broadcast to all nodes that happen to be online right now
- Each miner collects new transactions into a block
- After solving a proof of work puzzle, a random miner gets to broadcast its block
- Other nodes accept the block only if all transactions in it are valid (unspent, valid signatures)
- Miners express their acceptance of the block by including its hash in the next block they create
This consensus algorithm guarantees that blocks that are sufficiently deep in the chain (say, 6 blocks deep) are finalized, which means that nodes agree on them and they will never change.
More formally, Bitcoin's consensus protocol guarantees the following two properties.
- Liveness: Every transaction is eventually finalized by all honest nodes.
- Safety: Honest nodes do not finalize different blocks at the same height.
In order to achieve these goals, Bitcoin is purposely designed to be:
- Slow, in that transactions take awhile to become finalized.
- Bounded, in that only a small number of transactions can be inserted in each block.
- Computationally intensive, in order to distinguish the honest majority from the dishonest minority.
Over the next few weeks of this course, we will explore alternative ways to satisfy the liveness and safety goals with different tradeoffs.
5.1 Simplified Payment Verification¶
First though, let's revisit those light clients, and see how we can extend liveness and safety to them.
Remember that a light client doesn't have the hard drive space to store the 451 gigabytes of data in the Bitcoin blockchain. Still though, they can periodically connect to the Internet and download some data.
It would be great if we could compress all transactions into a small dataset. Unfortunately, that's impossible.
Instead, we can leverage the fact that the nodes (1) know the full list of transactions and (2) are available to provide transaction data to the light clients.
The clients just need to verify the accuracy of the transactions -- that is, to make sure that the nodes are telling them the truth. To do that, we can use a Merkle tree.
Merkle trees¶
We will see many uses of hash functions throughout this course. We have already seen two of them so far:
- They can be used within the construction of digital signatures, due to the collision resistance property.
- They can be used as the basis of proof-of-work puzzles, due to the puzzle friendliness property.
Here is another application. Suppose you want to store a large file $f$ on a cloud service like Dropbox or Google Drive. The file is important to you, so when you retrieve it later, you want to be able to check that the file hasn't been altered or corrupted on the cloud.
How can you do this?
Here's one common approach:
Given a file $f$, compute its hash digest $h = \operatorname{SHA256}(f)$ before you upload the file $f$ to the cloud. Store $h$ on your own computer. (Remember that $h$ is small, only 32 bytes in size.)
When you later download a file $f'$, check that $\operatorname{SHA256}(f') \overset{?}{=} h$ in order to verify that $f'$ is indeed the same as the file $f$ that you previously uploaded.
This approach is both simple and secure.
Modern hash functions are very quick to compute, even on large files that are gigabytes in size.
Due to collision resistance, even a malicious cloud cannot find a new file $f'$ that is different from your original and yet still hashes to the same string $h$.
What if you want to upload many files $f_1, f_2, \ldots, f_k$ to the cloud? It would be tedious to store one hash digest for each file.
Fortunately, there is a better approach: before uploading the files, construct a Merkle tree as follows.
- Take the hash of each individual file.
- Then, take the hash of each pair of hashes.
- Only store the hash at the root of the tree.
Source: Alin Tomescu, Decentralized Thoughts blog
The nice part about Merkle trees is that:
- You only have to store one 32-byte hash digest corresponding to the set of files $f_1, f_2, \ldots, f_k$.
- Later, the cloud provider can send you one file and prove to you that this file is contained "within" the Merkle tree.
To do so, the cloud provider sends $\log(k)$ hash digests so you can recompute the path from the desired file to the root. We will discuss Merkle trees in more detail in subsequent lectures.
Source: Alin Tomescu, Decentralized Thoughts blog
Application to SPV¶
How does this relate to Bitcoin? Well, if you think about the transactions in blocks as "files," we can do something similar here.
To support light clients, we are going to make two changes to the way that Bitcoin works. The first change applies to everyone, and the second change applies only to light clients.
First, each block will contain the Merkle root of all transactions within the block. The block itself will also contain all transactions, as before.
We will call the block header as just the following items: the nonce of the current block, the root of a Merkle tree for all transactions within that block, and the pointer to the previous block's hash.
Because the Merkle root binds together all of the transactions, it now suffices to create a proof-of-work puzzle where the hash is only taken over the header, and not the transactions themselves.
[Image source: Nakamoto whitepaper]
A light client will follow the same rule as nodes: find the blockchain of the largest height (or more accurately, the most cumulative difficulty).
But the light client only downloads the block headers, not the full blocks (i.e., they won't know the transactions). This is substantially smaller: each header is 80 bytes in size, so downloading all block headers for Bitcoin is about 62 MB of data right now. This is much smaller than 451 GB for the full blocks!
With this info, a light client can:
- Verify the proof of work puzzles themselves.
- Query a full node to ask whether they have received money. That is: if the client believes it has received money in block $N$, it can ask a node to send (1) the transaction that pays its public key and (2) a Merkle proof that it is contained within the set represented by that block's Merkle root.
Note that a light client cannot verify:
- That the full block is valid (in particular, that the transactions have valid signatures)
- That their money hasn't yet been spent in a subsequent block.
They must rely on the nodes to perform these checks. This makes light clients more vulnerable to attackers than nodes. For instance, a malicious miner can just create a single "bad" block that contains invalid signatures; nodes will reject it but a light client will be fooled.
For this reason, light clients should be even more careful when finalizing a transaction. Eventually though, they will inherit the liveness and safety guarantees from the nodes.
5.2 Pseudorandom Generation¶
Next, let's explore in detail one point that I briefly mentioned when defining light clients.
A light client only needs to hold one or more secret keys.
Why might you want to have more than one signing key in Bitcoin?
Let's consider the following scenario: suppose you are Alice, and you already have some Bitcoins. This means that you already have created secret/public keys for a digital signature scheme.
Then you have two interactions throughout the day.
In the morning, you visit a coffee shop and pay its store owner Bob in Bitcoin. This requires posting your public key and a digital signature to the globally-viewable blockchain.
In the afternoon, you talk to your friend Carol, and she decides to send you some money. To do so, she's asking you to give her a public key that she can (hash and) use as a destination address for the transaction.
What should you tell Carol?
You already have the secret/public keys from your old wallet. It's perfectly acceptable to reuse that one.
But there is a downside: now the entire world will see that the same person who went to the coffee shop in the morning is the person who is receiving coins right now. That is: the two transactions would be linkable.
A better approach is to run KeyGen again and generate a fresh secret/public key pair for this new transaction. This would provide some measure of pseudonymity.
(We will discuss the level of anonymity that Bitcoin achieves -- or fails to achieve -- in a future lecture. But still, this is better than nothing.)
Signing keys are quick and easy to create. But if you do this every day, quickly you will find yourself needing to remember a lot of signing keys, and that sounds cumbersome and error-prone. How can we make your life easier?
Quality of life improvement #1: generating many keys from one¶
At its core, the problem here is that Alice is generating many signing keys at random. They have no connection to each other, so she needs to store them all.
On the other hand, randomness was essential for the digital signature scheme to work. It is crucial that everyone chooses the secret key from a very large space, so that an attacker cannot brute force it. If everyone picked the same secret key for instance, then the signature scheme falls apart.
So here we reach a conundrum: we want a process that Alice can use to reliably and deterministically produce secret keys, but also one that "looks random" to an outsider.
Is there anything in our cryptographic toolbox that allows us to do this?
A cryptographic hash function $H$ provides this kind of property. Here's one way that we can leverage it.
Suppose we have one single master key $m$ that we ask Alice to memorize. She can use it to generate many child keys pseudorandomly.
- For her morning interaction with Bob, she can use $H(m, 0)$ to generate the first signing key.
- For her afternoon interaction with Carol, she can use $H(m, 1)$ to generate the second signing key.
This idea is effective thanks to the properties of the underlying hash function.
Due to preimage resistance, even if one signing key happens to be compromised and exposed to the world, nobody can use it to reverse-engineer the master key $m$.
Also, the rows of the truth table of $H$ appear to be independent. So the two signing keys -- and their associated public keys -- have no discernible connection to each other.
We can take this idea one step further: from a single master key $m$, we can generate several keys for different cryptocurrencies like Bitcoin, Ethereum, ZCash, and more. Then we can apply the previous idea to those keys in order to generate many secret/public key pairs.
This is the basic idea of a Bitcoin Improvement Protocol, or BIP, called hierarchical deterministic wallets.
With HD wallets, you only have to remember a single master key $m$, from which you can (re)generate as many signing keys for as many cryptocurrencies as you want.
[Image source: BIP-32 specification]
Some important caveats before we continue!
- The actual function you need to run here is not quite $H$, but rather a slightly more complicated construction called HMAC applied to the hash function.
- And there's more work required to go from the hash digest to something that has the structure of a digital signing key.
- And there are even more subtle details that are very important in practice, but out of scope for this lecture.
Always make sure to use well-written crypto software that is developed by people who have studied this subtlety; don't roll your own crypto software in practice!
Quality of life improvement #2: a human-memorable seed¶
We have made Alice's life somewhat easier: now all she has to do is remember a 32 byte master key. It might look something like this:
from os import urandom
from binascii import hexlify
master_key = urandom(32)
print("Base 16 output:", hexlify(master_key))
from base64 import b64encode
print("Base 64 output:", b64encode(master_key))
As discussed in Lab 2, these kinds of string encodings are incredibly useful for computer programs to ingest, process, and output printable characters for other computer programs to use.
But Alice is a person. This style of encoding is not meant for her.
What we need is a better way to encode 256 bits' worth of random decisions, but in a way that makes sense for people to remember or write down.
[Image source: xkcd.com]
This technique uses the same principle you learned about in Lab 2: all information is data, and all data can be encoded into bits.
Specifically, let's think about the ways that we can store 12 bits worth of data.
- We can write the data in binary, for example $0101 1010 0011$.
- We can write the data as hex characters as $6a4$.
- We can write the data in base 64 as "Wj"
Or we can choose any other representation that gives us $2^{12}$ possible values that the data can take.
There is another Bitcoin Improvement Protocol standard made for this purpose: creating human-memorable seeds. It defines a set of $2^{11} = 2048$ words and records every 11 bits of the master key using one word.
Let's look at its set of words. I'll use English in this example, although other languages are specified in the standard too.
# source: https://github.com/trezor/python-mnemonic
# pip install mnemonic
from mnemonic import Mnemonic
mnemo = Mnemonic("english")
print(mnemo.wordlist[:10]) # first ten words
print(mnemo.wordlist[-10:]) # last ten words
We can create a master key by sampling 24 of these words at random, each of which encodes 11 bits of data. So collectively, they encode the 256 bits of entropy that we need.
# CAUTION: do not actually use this seed phrase to hold any money!
words = mnemo.generate(strength=256)
print(words)
seed = mnemo.to_seed(words, passphrase="")
print("\nBase 64 encoding:", b64encode(seed))
5.3 A Smaller Signature Scheme¶
Next, let's discuss a new kind of digital signature that can make life easier for the nodes.
Last week, we saw the RSA digital signature scheme. It is named after its inventors: Rivest, Shamir, and Adleman. While RSA works fine, one concern is that its keys and signatures are about a few thousand bits long.
That may not sound big, and indeed a single signature is small. But they add up quickly.
Remember that each node stores a record of every single transaction, and so far there have been over 800 million transactions on Bitcoin.
The punchline here is: space on the blockchain is a valuable resource, so we should try to minimize usage of it. Let's discuss another signature scheme that can use less space.
Recall that digital signature schemes have a tricky property: from the public key it is impossible to create a digital signature but easy to verify if someone else has done so.
As a result, we must build signature schemes from math problems that we believe to have this property of "difficult to solve but easy to check."