Bitcoin and Cryptocurrency Technologies

Catelog

1. Intro to Crypto and Cryptocurrencies
   1. Crypto background
      1. hash functions
      2. digital signatures
      3. … adn applications
   2. Intro to cryptocurrencies
      1. basic digital cash

1. Intro

1.1 Cryptographic Hash Functions

Takes any string as input,
fixed-size output(we’ll use 256 bits),
efficiently computable

Security properties:

1. collision-free

Intro:
Nobody can find x and y such that x != y and H(x) = H(y)
Notion: Collision-free is not equal No-Collision

Notion:
With a valid function, we can find a collision:
try 2^130 randomly chosen inputs, and have 99.8% chance that two of them will collide.
(No matter what hash function is)
(But it takes too long to matter.)
(But here’s no one have been proven a hash fucntion is collision-free.)

Application:
Hash as message digest: If we know H(x) = H(y), we can assume that x = y.
(Useful because the hash is small)

2. hiding

Intro:
Given H(x), it is infeasible to find x.
If r is chosen from a probability distribution that has high min-entropy, then given H(r|x), it is infeasible to find x.

Notion:
High min-entropy means that the distribution is “very spread 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.

Commitment API:

Commitment:
   1. (com, key) := commit(msg)
   2. match := verify(com, key, msg)
Verification:
   1. verify(com, key, msg) := (H(key | msg) == com)
   2. commit(msg) := (H(key | msg), key) *(where key is a random 256-bit value)*

3. puzzle-friendly

Intro:
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

A mathmetical problem, which contains a large searching-space which is given for finding the solusion and where is no shortcut in it.
Puzzle-friendly property implies that no solving strategy is much better than trying random values of x.

Application: Search puzzle

SHA-256 hash function