Week One  Introduction to Crypto and Cryptocurrencies
Hash function
Takes any string as input
fixedsize output (e.g. 256bits just as BitCoin)
efficiently computable
Security properties:
Collisionfree
Nobody can find x and y such that x!=y and H(x)=H(y)
Note: Collisions do exist. The possible outputs is finite(string of 256 bits in size), while the possible inputs can be a string of any size.
To find a collision of any hash function: Trying randomly chosen inputs and chances are 99.8% that two of them will collide. Well, it takes too long to matter.
For some possible H’s, there’s a faster way to find collisions; for others, we haven’t known yet. No H has been proven collisionfree.
Hiding
If r is chosen from a probability distribution that has high minentropy, then given H(rx), it is infeasible to find x.
High minentropy means that the distribution is “very spread out”, so that no particular value is chosen with more than negligible probability.
Puzzlefriendly
For every possible output value y, if k is chosen from a distribution with high minentropy, then it is infeasible to find x such that H(kx)=y.
Applications
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.
It’s useful because the hash is small.
Commitment
Want to “seal a value in an envelope”, and “open the envelope” later.
Commit to a value, reveal it later.


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
.
Search Puzzle
Given a “puzzle ID” id (from high minentropy distribution) and a target set Y,
try to find a “solution” x such that H(idx)∈Y.
Puzzlefriendly property implies that no solving strategy is much better than trying random values of x.
SHA256
Hash Pointer
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.
Data structure of blockchain:
This is blockchain, and it’s similar to linked list.
If some adversary wants to change a block’s data(e.g., the left one), then the content of that block is changed. And the middle block’s hash pointer is not consistent to the left block any more. So the adversary has to change middle block’s header, and next block’s header and so on.
Digital Signature


Requirements for signatures
·Valid signatures verify
·Can’t forge signatures