Lecture 1.1: Hash functions

• Takes any string as input
• Fixed-size output
• Efficiently computable

Security properties

• Collision-free
• Hiding
• Puzzle friendly

Hash property 1: Collision-free

• Nobody can find x and y such that x != y and H(x) = H(y).
• Collisions do exist because the sample space of x and y is infinite, whereas H(x) and H(y) is limited to a a fixed set of bits.

How to find a colliison

• Try $2^{130}$ randomly chosen inputs
• 99.8% chance that two of them will collide
• This method works no matter what the H is
• ... but it takes too long to matter
• $2^{130}$ is an astronomical number
  • Is there a faster way to find collisions?
• For some possible H's, yes
• For others, we don't know of one
  • No H has been proven to be collision-free

Application: Hash as message digest

• If we know H(x) = H(y), it's safe to assume that x = y.
• To recognize a file that we saw before, just remember its hash.
• Useful because the hash is small.

Hash property 2: Hiding

• Given H(x), it is infeasible to find x.
• Example:
  • Flip a coin, and return H('heads') or H('tails') depending upon the outcome of the flip.
  • It is easy to find x in this scenario!
  • The reason why an adversary can guess the value of x is that there are only a couple of possible values for x.
• Hiding property: If r is chosen from a probability distribution that has high min-entropy, then given H(r | x), it is infeasible to find x.
• High min-entropy means that the distribution is "very spead out", so that no particular value is chosen with more than negligible probability.

Application: Commitment

• Want to "seal a value in an envelope", and "open the envelope" later.
• Commit to a value, reveal it later.

Commitment API

(com, key) := commit(msg)
match := verify(com, key, msg)

To seal msg in envelope,

• (com, key) := commit(msg) => then publish com

To open envelope,

• publish key, msg
• anyone can use verify() to check validity

Security properties:

• Hiding: given com, infeasible to find msg.
• Binding: infeasible to find msg != msg' such that

    verify(commit(msg), msg') == true

Using the Commitment API

commit(msg) := H(key | msg), H(key)
verify(com, key, msg) := H(key | msg) == com

where key is a random 256-bit value (say)

Security properties:

• Hiding: given H(key | msg), infeasible to find msg.
• Binding: infeasible to find msg != msg' such that

    H(key | msg) == H(key | msg')

Hash property 3: Puzzle-friendly

For every possible output value y, if k is chosen from a distribution with high min-entropy, then it is infeasible to find x such that H(k | x) = y.

Application: Search puzzle

Given a "puzzle ID" id (from a high min-entropy distribution), and a target set Y, try to find a "solution" x such that

H(id | x) in Y

Puzzle-friendly property implies that no solving strategy is much better than trying random values of x. Useful property in Bitcoin mining.

Lecture 1.2: Hash Pointers and Data Structures

A hash pointer is:

• pointer to where some info is stored, and
• (cryptographic) hash of the info

If we have a hash pointer, we can

• Ask to get the info back, and
• Verify that it hasn't changed

The key idea here is to build data structures with hash pointers.

Application: detecting tampering

Merkle tree

Merkle tree is a binary tree with hash pointers.

For proving membership in a Merkle tree, one needs to show only O(log n) items.

Advantages of Merkle trees

• Tree holds many items. We just need to remember the root hash.
• Can verify membership in O(log n) time/space.

Variant: sorted Merkle tree

• Can verify non-membership in O(log n), by just showing items before and after the missing data block.

We can use hash pointers in any pointer-based data structure that has no cycles.

Lecture 1.3: Digital signatures

What we from signatures:

• Only you can sign, but anyone can verify.
• Signature is tied to a particular document. Can't be cut-and-pasted to another document.

API for digital signatures

(sk, pk) := generateKeys(keysize)
sig := sign(sk, message)
isValid := verify(pk, message, sig)

Note:

• sk = secret signing key
• pk = public verification key
• generateKeys must be a randomized algorithm

Requirements for signatures

• Valid signatures verify

    verify(pk, message, sign(sk, message)) == true

• Can't forge signatures

  An adversary who knows the pk, and gets to see signatures on messages of his choice, can't produce a verificable signature on another message.

Practical stuff

• Algorithms are randomized

  • Need good source of randomness
  • Attacks on the source of randomness are a favourite trick of intelligence agencies

• Limit on message size

  • Fix: use Hash(message) rather than the message itself

• Fun trick: sign a hash pointer

  • Signature "covers" the whole structure.
  • If you sign a hash pointer at the end of blockchain, you are effectively digitally signing the entire contents of the blockchain.

• Bitcoin uses ECDSA standard

  • Elliptic Curve Digital Signature Algorithm
  • Relies on hairy math
  • Good randomness is essential in ECDSA. If you used bad randomness in generateKeys() or sign(), you've probably leaked your private key. GAME OVER.

Lecture 1.4: Public keys as Identities

If you see sig such that verify(pk, msg, sig) == true, think of it as:

    pk says, "[msg]".

To "speak for" pk, you must know matching secret key sk.

How to make a new identity

• create a new, random key-pair (sk, pk)
• pk is the public "name" you can use [usually better to use Hash(pk) because public keys are big]
• sk lets you "speak for" the identity
• you control the identity, because only you know sk
• if pk "looks random", nobody needs to know who you are

Decentralized identity management

• anybody can make a new idnetity at any time
• make as many as you want
• no central point of coordination
• these identitites are called "addresses" in Bitcoin

Privacy

• Addresses not directly connected to real-world identity
• But observer can link together an address's activity over time, make inferences.

Lecture 1.5: A Simple Cryptocurrency

The main design challenge in digital currency

Solving the double-spend problem - Scrooge Coin

Immutable coins

• Coins can't be transferred, subdivided, or combined.
• But: you can get the same effect by using transactions. To subdivide:
  • create new transactions
  • consume your coin
  • pay out two new coins to yourself

Core problem of Scrooge Coin

• Scrooge Coin will work; people can see which coins are valid; it prevents double spending because people can see the blockchain and verify that all coins are consumed only once.
• BUT, the problem we have here is centralization.
• Crucial question: can we descroogify the currency, and operate without any central, trusted party?