# Stanford CS251: Lecture 1

### Lecture 1: Introduction

Bitcoin is a cryptocurrency with distributed trust. The blockchain is a public append-only ledger. The append-only property is sufficient for having a currency.

Hash functions: H: M -> T where |M| >> |T| that is space of messages is larger than space of the hash. If H(m0) =H(m1) => collision. Hash function H is collision-resistant if it is hard to find the collision of H. For example, SHA-256 maps long strings to 256-bit hashes.

Bitcoin’s Hash function: H(m) = SHA256(SHA256(m)). Two rounds of SHA-256 are used since a single round is susceptible to Length Extension Attack.

#### Application of hash functions

- Binding commitments

For software package T, publish H(T) on a secure location while T is distributed via insecure third-parties. The user will download T and verify that H(T) matches the published hash. For multiple files T_{1}, … T_{n}, one needs individual commitments/hashes. A more space-efficient way is to use Merkle trees which still keeps the commitment size to one hash. - Proof of Work

For every email, the sender will solve a unique “puzzle” which takes ~ 1 second of CPU time. Solving this puzzle will cut down spamming drastically. The puzzle is to get Hash(email contents, s) < 2^{n}/d. n is the bit-length of the hash function output. The value of d can be increased the difficulty of the puzzle. The sender would try different “s” until the solution is found. It will take d * Time(H) to find the solution. A normal sender wouldn’t mind the amount of effort, but this will be a lot of work for a spammer sending millions of emails. This didn’t work because of sending email to mailing lists breaks down.

A hash function is **Proof-of-work secure** if the probability of finding a solution is proportional to time invested in it, or in other words, there is no way to do it better than the brute-force. It is strongly believed that SHA256-squared, the Bitcoin hash function, is POW-secure for difficulty d < 2^{128}.

#### Digital Signatures

Three efficient algorithms

- Keygen – generates a Public Key (P
_{k}) and Signing Key (S_{k}), latter remains secret. - Sign – σ signature = sign(S
_{k}, m) - Verify – verify(P
_{k}, m, σ) outputs “yes”/”no”

Given (m_{i}, σ_{i}), the adversary cannot produce a new (m*, σ*).

Famous schemes

- RSA
- ECDSA – used by Bitcoin. Bitcoin specifically uses ECDSA Secp256k1. S
_{k}– 256-bit. P_{k}– 512-bits (257-bits compressed). 512-bit uncompressed notation consists of 256-bit X and 256-bit Y coordinate, but since there are only two Y-coordinates, one positive and one negative, for a single X-coordinate, one can store X-coordinate + 1-bit polarity of the Y-coordinate in the compressed notation of 257-bits. The message is 256-bits and signature is 512-bits.**The signature size is unusually large**and newer schemes do much better on the signature size, but bitcoin is stuck with this. Since message length is 256-bits, ECDSA is used for signing the hash of the message. The transaction, thus, becomes an**Authenticated Data Structure**.

##### Append-only trusted ledger – an application of digital signatures

- Anyone can read
- Anyone can ask the bank to add data to the ledger
- If the bank removes a transaction from the ledger, it will be caught

Setup – Bank will sign Transaction T_{0}, then (T_{0}, T_{1}) then (T_{0}, T_{1}, T_{2}) and will publish these after every signature. If the bank now removes a transaction from the ledger, then everyone will notice that there are two blocks (T_{0}, T_{1}, T_{2}) and (T_{0}, T_{1}, T_{3}) with none being the prefix of the other => Transaction set “forked”.

Bitcoin takes this a step further to an append-only distributed ledger.

[…] Introduction […]