Remember what Merkle trees do:
In more detail: we construct a Merkle tree as follows.
If you store one 32-byte hash digest corresponding to the set of files \(f_1, f_2, \ldots, f_k\), then someone else can prove to you that one file (say, \(f_3\)) is contained within the set \(S\) represented by the Merkle tree.
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.
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.
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).
To give a sense of scale:
With this info, a light client can:
Note that a light client cannot verify:
They must rely on the nodes to perform verification check #1, and on their own memory for property #2.
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, light clients will inherit the liveness and safety guarantees from the nodes.
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.
Question. 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 main key \(m\) that we ask Alice to memorize. She can use it to generate many child keys pseudorandomly.
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 main 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 the main 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 the main key \(m\), from which you can (re)generate as many signing keys for as many cryptocurrencies as you want.
Some important caveats before we continue!
HMAC applied to the hash function.Remember: always make sure to use well-written crypto software that is developed by people who have studied these subtle details. Don’t roll your own crypto software in practice!
We have made Alice’s life somewhat easier: now all she has to do is remember the 32 byte main key. It might look something like this:
from os import urandom
from binascii import hexlify
main_key = urandom(32)
print("Base 16 output:", hexlify(main_key))
from base64 import b64encode
print("Base 64 output:", b64encode(main_key))Base 16 output: b'd70ee60ddbceae19032cc3c9a219b68883ad6666899a9ff3521eb3d2d7a3c92e'
Base 64 output: b'1w7mDdvOrhkDLMPJohm2iIOtZmaJmp/zUh6z0tejyS4='These kinds of string encodings:
This technique uses the same principle that we discussed in Lecture 1:
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.
Or we can choose any other representation that gives us \(2^{12}\) possible values that the data can take… perhaps one that is even easier for humans to remember.
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 main 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['abandon', 'ability', 'able', 'about', 'above', 'absent', 'absorb', 'abstract', 'absurd', 'abuse']
['yard', 'year', 'yellow', 'you', 'young', 'youth', 'zebra', 'zero', 'zone', 'zoo']We can create Alice’s main 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.
words = mnemo.generate(strength=256)
print(words)
seed = mnemo.to_seed(words, passphrase="")
print("\nBase 64 encoding:", b64encode(seed))script frog armed oyster salmon crop horse strong cereal regular tenant royal deliver gate rather nephew own truck inmate avoid weekend allow wife crew
Base 64 encoding: b'5Xsx/kM1DgcdnBFjxan9w8ribFMRLkd7iYNiZARP97RYUGCFH6eu/abIKa4zR2peuyQWxktTgxdcrWqzBpWqCg=='Caution: this code is just for demonstration purposes. Do NOT actually use this seed phrase to hold any money!
So far, we have said that a transaction has the form “Alice pays 1 coin to Bob.”
Actually, this is not quite true. Bitcoin allows for more complicated transactions than this.
A Bitcoin transaction is actually a computer script that looks like this.
In words, a Bitcoin transaction involves Alice posting her own public key and the hash of Bob’s public key. This hash is called Bob’s wallet “address.” The transaction can be thought of as a computer program that says:
“For anyone who shows up later with a public key and claims to be the recipient of this transaction, take the hash of their public key and check if it equals
8ec...b1. If so, give my coins to that person.”
In fact, there are several valid operations that can be performed in a Bitcoin transaction. However, the scripting language is not Turing-complete; that is, you can’t write any computer program.
Relatedly, this is why some Bitcoin transactions take up more space than others: they can be more complicated computer programs.
Ethereum is another cryptocurrency. It was created in 2013 – so, four years after Bitcoin, but still awhile ago. Ethereum takes the idea of scripting much further than Bitcoin does.
The Ethereum blockchain is essentially a global computer where everyone agrees on the state of this computer. The global state is replicated on all nodes that are in the Ethereum network. The Ethereum state can only be changed by users issuing transactions.
Similarities. Ethereum shares several features in common with Bitcoin, such as:
Additionally, Ethereum also has its own digital currency, known as Ether.
Just like Bitcoin transactions:
Differences. However, Ethereum’s primary objective is not to function as a digital currency payment network, and Ether is not intended to be a conventional currency. Instead,
Also, Ethereum’s scripting language is Turing-complete, unlike the one in Bitcoin. So, it can operate as a general-purpose computer and execute code with more complexity.
You can think of Ethereum as a state machine. Ethereum’s state is a large data structure which holds not only all accounts and balances, but a machine state, which can change from block to block according to a pre-defined set of rules, and which can execute arbitrary machine code.
The specific rules of changing state from block to block are defined by the Ethereum Virtual Machine (EVM). Every transaction causes the EVM to run which causes the global state to change. The order of the transaction is very important! The EVM is single threaded.
