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.
Append-only trusted ledger – an application of digital signatures
  1. Anyone can read
  2.  Anyone can ask the bank to add data to the ledger
  3. If the bank removes a transaction from the ledger, it will be caught

Setup – Bank will sign Transaction T0, then (T0, T1) then  (T0, T1, T2) 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  (T0, T1, T2) and  (T0, T1, T3) with none being the prefix of the other => Transaction set “forked”.

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