---
# System prepended metadata

title: <center><i class="fa fa-edit"></i> 1.1 Cryptographic Hash Functions </center>
tags: [Blockchain]

---

# <center><i class="fa fa-edit"></i> 1.1 Cryptographic Hash Functions </center>
###### tags: `Blockchain`
The following notes are taken from [Coursera](https://www.coursera.org/learn/cryptocurrency/home/week/2)

---

### Property 1: Collision Free
No one can find `x != y && H(x) = H(y)`
Exists: 
![](https://i.imgur.com/6ehrv1p.png)

**How to find collision**
- try 2¹³⁰ random inputs
- 99.8% chance of a collision 

No H has been *proven* collision-free 

**Application: Hash as message digest**
`H(x) = H(y) -> x = y`
- To recognize a file, just remember its hash
    - Useful since has is small
### Property 2: Hiding
Given `H(x)`, *infeasible* to find `x` 
If `r` is chosen from a probability distribution that has **high min-entropy** (variance), then given `H(r|x)` it is infeasible to find `x`
:::info
**Example: commitment API**
(com, key) := commit(msg)
match := verify(com, key, msg)
publish key, msg

anyone can use verify() to check validity
1. Hiding: given com, infeasible to find msg
2. Binding: committed, so can't claim a false one because verifiable 
:::
### Property 3: Puzzle-friendly
For every possible output `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` 
:::info
**Example: Try to find `H(id|x) ∈ y`**
Puzzle-friendly implies there is no better strategy than trying random values of `x`
:::
### SHA-256
![](https://i.imgur.com/etVEhHS.png)
:::success
Theorem: If `c` is collision-free, then SHA-256 is collision-free
:::
