Recap: the Bitcoin blockchain

genesis
block BH1 BH2 BH3
version (4 bytes)
Bitcoin Scripts and Wallets H prev (32 bytes)
H prev H prev
time (4 bytes) …
bits (4 bytes)
nonce (4 bytes)
Tx root (32 bytes) Tx root Tx root
80 bytes
coinbase Tx
coinbase Tx

1 2

Tx sequence Tx structure (non-coinbase)

input[0] input: TxID 32 byte hash
View the blockchain as a sequence of Tx (append-only) inputs input[1] out-index 4 byte index
input[2] ScriptSig program
… seq ignore
outputs output[0] TxID = H(Tx)
output[1] (excluding witnesses)

value 8 bytes
(segwit) witnesses output:
(part of input) ScriptPK program
coinbase Tx (4 bytes)
locktime
#BTC = value/108
Tx cannot be erased: mistaken Tx ⇒ locked or lost of funds earliest block # that can include Tx

3 4
 Example Example

☓
null locktime null locktime

Tx1: input 2 ScriptPK 5 ScriptPK 0 Tx1: input 2 ScriptPK 5 ScriptPK 0

(funding Tx) value value (funding Tx)
UTXO1 UTXO2 UTXO1 UTXO2
UTXO: unspent Tx output UTXO: unspent Tx output

Tx2: TxID 1 ScriptSig output output 0 Tx2: TxID 1 ScriptSig output output 0
(spending Tx) identifies UTXO3 UTXO4 (spending Tx) identifies UTXO3 UTXO4
a UTXO a UTXO

5 6

Validating Tx2 Transaction types: (1) P2PKH

program from funding Tx: pay to public key hash
Miners check (for each input): under what conditions
can UTXO be spent
Alice want to pay Bob 5 BTC:
• step 1: Bob generates sig key pair (pkB, skB) ⇽ Gen()
1. The program ScriptSig | ScriptPK returns true • step 2: Bob computes his Bitcoin address as addrB ⇽ H(pkB)
• step 3: Bob sends addrB to Alice
program from spending Tx:
2. TxID | index is in the current UTXO set proof that conditions • step 4: Alice posts Tx:
are met UTXOB for Bob UTXOA for Alice (change)
Point to input
3. sum input values ≥ sum output values Alice’s UTXO 7 BTC 5 ScriptPKB 2 ScriptPKA 0

ScriptPKB: DUP HASH256 <addrB> EQVERIFY CHECKSIG

After Tx2 is posted, miners remove UTXO2 from UTXO set
7 8
 Transaction types: (1) P2PKH Transaction types: (1) P2PKH
pay to public key hash
Later, when Bob wants to spend his UTXO: create a Txspend
“input” contains ScriptSig that authorizes spending Alice’s UTXO
• example: ScriptSig contains Alice’s signature on Tx Txspend: TxID 0 ScriptSigB output output 0
⟹ miners cannot change ScriptPKB (will invalidate Alice’s signature) points to
UTXOB
UTXOB for Bob UTXOA for Alice (change)
<sig> <pkB> (authorizes spending UTXOB)
Point to input
Alice’s UTXO 7 BTC 5 ScriptPKB 2 ScriptPKA 0
<sig> = Sign(skB, Tx) where Tx = (Txspend excluding all ScriptSigs) (SIGHASH_ALL)

ScriptPKB: DUP HASH256 <addrB> EQVERIFY CHECKSIG Miners validate that ScriptSigB | ScriptPKB returns true

9 10

P2PKH: comments Segregated Witness

• Alice specifies recipient’s pk in UTXOB ECDSA malleability:
Given (m, sig) anyone can create (m, sig’) with sig ≠ sig’
⇒ miner can change sig in Tx and change TxID = SHA256(Tx)
• Recipient’s pk is not revealed until UTXO is spent
⇒ Tx issuer cannot tell what TxID is, until Tx is posted
(some security against attacks on pk) ⇒ leads to problems and attacks

• Miner cannot change <AddrB> and steal funds: Segregated witness: signature is moved to witness field in Tx
invalidates Alice’s signature that created UTXOB TxID = Hash(Tx without witnesses)

11 12
 Transaction types: (2) P2SH: pay to script hash P2SH
(pre SegWit in 2017)
Payer specifies a redeem script (instead of just pkhash) Miner verifies:
Usage: (1) Bob publishes hash(redeem script) ⟵ Bitcoint addr. (1) <ScriptSig> ScriptPK = true ⟵ spending Tx gave correct script
(2) Alice sends funds to that address in funding Tx
(2) ScriptSig = true ⟵ script is satisfied
(3) Bob can spend UTXO if he can satisfy the script

ScriptPK in UTXO: HASH160 <H(redeem script)> EQUAL

ScriptSig to spend: <sig1> <sig2> … <sign> <redeem script>

payer can specify complex conditions for when UTXO can be spent
13 14

Example P2SH: multisig Abstractly …

Goal: spending a UTXO requires t-out-of-n signatures Multisig address: addr = H(PK1, PK2, PK3, 2-of-3)

Redeem script for 2-out-of-3: (chosen by payer) Tx1: input 5 addr 2 ScriptPKA 0
<2> <PK1> <PK2> <PK3> <3> CHECKMULTISIG (funding Tx)
7 BTC UTXOB for Bob UTXOA for Alice (change)

threshold hash gives P2SH address

Tx2: input: UTXO, sig1, sig3, PK1, PK2, PK3, 2-of-3 output 0
ScriptSig to spend: (by payee) <0> <sig1> <sig3> <redeem script> (spending Tx)

(in the clear)

15 16
 Protecting assets with a co-signatory
Alice stores her funds in UTXOs for addr = 2-of-2(PKA, PKS)

Example Bitcoin scripts PKA

Alice
spending Tx PKS
custody
SKA is this Alice server
yep, it’s me SKS
post Tx with <sigA> <sigS>
<sigS> on Tx

⇒ theft of Alice’s SKA does not compromise BTC

17 18

Escrow service Escrow service: a dispute

Alice wants to buy a backpack for 0.1₿ from merchant Bob (1) Backpack never arrives: (Bob at fault)
Goal: Alice only pays after backpack arrives, but can’t not pay Alice gets her funds back with help of Judge and a Tx:
addr = 2-of-3(PKA, PKB, PKJ) Tx: ( UTXOA ⇾ PKA , sigA, sigJudge ) [2-out-of-3]

(2) Alice never sends sigA: (Alice at fault)

post want backpack for 0.1₿
payment Alice Bob Judge Bob gets paid with help of Judge and a Tx:
once see Tx on chain
of 0.11₿ Tx: ( UTXOA ⇾ PKB , sigB, sigJudge ) [2-out-of-3]
PKA mail backpack PKB PKJ
to addr (3) Both are at fault: Judge publishes <sigJudge> on Tx:
backpack arrives redeem using
(creates Tx: ( UTXOA ⇾ PKA: 0.05, PKB: 0.05, PKJ: 0.01 )
send <sigA> on Tx: <sigA> <sigB>
UTXOA) Now either Alice or Bob can execute this Tx.
UTXOA⇾ (PKB:0.1, PKA:0.01) on Tx
19 20
 Cross Chain Atomic Swap
Alice has 5 BTC, Bob has 2 LTC (LiteCoin). They want to swap.

Want a sequence of Tx on the Bitcoin and Litecoin chains s.t.:

• either success: Alice has 2 LTC and Bob has 5 BTX,
Managing crypto assets: Wallets
• or failure: no funds move.
Swap cannot get stuck halfway.

Goal: design a sequence of Tx to do this.

solution: programming proj #1 ex 4.

21 22

Managing secret keys Managing lots of secret keys

Users can have many PK/SK: Types of wallets:
• one per Bitcoin address, Ethereum address, … • cloud (e.g., Coinbase): cloud holds secret keys … like a bank.
• laptop/phone: Electrum, MetaMask, … client stores
Wallets: • hardware: Trezor, Ledger, Keystone, … secret keys
• Generates PK/SK, and stores SK, • paper: print all sk on paper
• Post and verify Tx,
• brain: memorize sk (bad idea)
• Show balances
• Hybrid: non-custodial cloud wallet (using threshold signatures)
Not your keys, not your coins … but lose key ⇒ lose funds
23 24
 Simplified Payment Verification (SPV) Simplified Payment Verification (SPV)
How does a client wallet display Alice’s current balances? Problems:
• Laptop/phone wallet needs to verify an incoming payment (1) Security: are BH the ones on the blockchain? Can server omit Tx?
• Goal: do so w/o downloading entire blockchain (366 GB) • Electrum: download block headers from ten random servers,
SPV: (1) download all block headers (60 MB) optionally, also from a trusted full node.
block header (2) Tx download: List of servers: [Link]/#community

• wallet ⇾ server: list of my wallet addrs (Bloom filter) (2) Privacy: remote server can test if an addr belongs to wallet
Tx root
• server ⇾ wallet: Tx involving addresses +
Merkle proof to block header.
We will see better light client designs later in the course (e.g. Celo)

25 26

Hardware wallet: Ledger, Trezor, … Hardware wallet: backup

End user can have lots of secret keys. How to store them ??? Lose hardware wallet ⇒ loss of funds. What to do?

ECDSA public key

Hardware wallet (e.g., Ledger Nano X) Idea 1: generate a secret seed k0 ∈ {0,1}256
- connects to laptop or phone wallet using Bluetooth or USB for i=1,2,…: ski ⇽ HMAC(k0, i) , pki ⇽ 𝑔
- manages many secret keys
𝑝𝑘1, 𝑝𝑘2, 𝑝𝑘3, … : random unlinkable addresses (without k0)
- Bolos OS: each coin type is an app on top of OS
- PIN to unlock HW (up to 48 digits)
k0 is stored on HW device and in offline storage (as 24 words)
- screen and buttons to verify and confirm Tx
⇒ in case of loss, buy new device, restore k0, recompute keys

27 28
 On Ledger Example: English word list
When initializing ledger:
• user asked to write down the 24 words
• each word encodes 11 bits (24 ×11 = 268 bits)
• list of 2048 words in different languages (BIP 39)

⋮
save list of
24 words

29 30

Crypto Steel On Ledger

When initializing ledger:
• user asked to write down the 24 words
• each word encodes 11 bits (24 ×11 = 268 bits)
• list of 2048 words in different languages (BIP 39)

Beware of “pre-initialized HW wallet”

• 2018: funds transferred to wallet promptly stolen
Careful with unused letters …

31 32
 How to securely check balances? Idea 2: (used in HD wallets)
With Idea1: need k0 just to check my balance: secret seed: k0 ∈ {0,1}256 ; (𝑘1, 𝑘2) ⇽ HMAC(k0, “init”)
• k0 needed to generate my addresses (𝑝𝑘1, 𝑝𝑘2, 𝑝𝑘3, … )
balance seed: kpub = (𝑘2, ℎ = 𝑔 )
… but k0 can also be used to spend funds
• Can we check balances without the spending key ?? for all i=1,2,…: ski ⇽ 𝑘1 + HMAC(𝑘2, i)

Goal: two seeds pki ⇽ 𝑔 =𝑔 𝑔 ,

=ℎ 𝑔 ,

• k0 lives on Ledger: can generate all secret keys (and addresses) kpub does not reveal sk1, sk2, … computed from kpub
• kpub: lives on laptop/phone wallet: can only generate addresses kpub: on laptop/phone, generates unlinkable addresses 𝑝𝑘1, 𝑝𝑘2, …
(for checking balance) k0: on ledger
33 34

Paper wallet (be careful when generating)

Managing crypto assets in the cloud

How exchanges store assets

signing key (cleartext)

Bitcoin address = base58(hash(PK))
base58 = a-zA-Z0-9 without {0,O,l,1}

35 36
 Hot/cold storage Problems
Coinbase: holds customer assets
Design: 98% of assets (SK) are held in cold storage Can’t prove ownership of assets in cold storage,
without accessing cold storage:
cold storage (98%) hot wallet (2%) • To prove ownership (e.g., in audit or in a proof of solvency)
( )
𝑘 ℎ, 𝑘2 SKhot • To participate in proof-of-stake consensus
( ) 𝑘0 used to 2% of customers
𝑘 Solutions:
verify cold assets
( ) storage • Keep everything in hot wallet (e.g, Anchorage)
𝑘 balances • Proxy keys: keys that prove ownership of assets,
t-out-of-n secret sharing of 𝑘0 but cannot spend assets

37 38

END OF LECTURE

39