# Cryptographic hash functions and Cryptocurrency
## Hash properties
- Collision-free
- Hiding
- Puzzle-friendly
About the same as [Properties of hash function](/Lq9U6xg3RzuSvfGOznxM4w)

## Hash function used in Bitcoin
- SHA-256

## Data structure with hash pointers
- Tamper-evident log
- Merkel tree
- proving membership: $O(log\ n)$ time
- 
- variant: sorted Merkel tree
- prove non-membership in $O(log\ n)$
- show items before, after missing one

## API for digital signature
$(sk, pk):=generateKeys(keysize)$
> sk: private (secret) key
> pk: public key
>
$sig:=sign(sk, message)$
$isValid=verify(pk, message, sig)$

## Practical digital signature
- Bitcoin uses *ECDSA* standard
- Elliptic Curve Digital Signature Algorithm

## Public key == identity
A address that sees $sig$ and can say $verify(pk, msg, sig) == true$ must have a matching $sk$

## First try: GoofyCoin
- Simple but can't prevent ***double spending attack***

## Second try: ScroogeCoin
- Every transaction has a pointer to all history
- Double spending doesn't work here, since we can look into the history and figure out
### PayCoins transaction
#### Conditions of a valid PayCoins transaction
- cousumed coins are valid
- not already consumed
- total vale out == total value in
- signed by owners of all consumed coins


#### Immutable coins
- Coins can't be transfered, subdivided, or combined
- But you can get the same effects with transactions