# 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

1. 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 T1, … Tn, one needs individual commitments/hashes. A more space-efficient way is to use Merkle trees which still keeps the commitment size to one hash.
2. 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) < 2n/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 < 2128.

#### Digital Signatures

Three efficient algorithms

1. Keygen – generates a Public Key (Pk) and Signing Key (Sk), latter remains secret.
2. Sign – σ signature = sign(Sk, m)
3. Verify – verify(Pk, m, σ) outputs “yes”/”no”

Given (mi, σi), the adversary cannot produce a new (m*, σ*).

Famous schemes

1. RSA
2. ECDSA – used by Bitcoin. Bitcoin specifically uses ECDSA Secp256k1. Sk– 256-bit. Pk – 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.