Hash Function: H: {0,1}* → {0,1}ⁿ

Where:
- {0,1}* = Any binary input (arbitrary length)
- {0,1}ⁿ = Fixed-length output (n bits)

Example (SHA-256):
H("Blockchain") = 0x8a7c8f4e5a3b2c1d9e0f8a7b6c5d4e3f2a1b0c9d8e7f6a5b4c3d2e1f0a9b8c7d

Properties:
1. Deterministic: Same input → Same output
2. Fast Computation: O(n) time complexity
3. Pre-image Resistance: Cannot reverse
4. Second Pre-image Resistance: Cannot find collisions
5. Collision Resistance: Cannot find any collisions
6. Avalanche Effect: Small change → Big change

Avalanche Effect:
For any input x and y where Hamming Distance(x, y) = 1:
Probability(H(x) ⊕ H(y) has bit i = 1) ≈ 0.5 for all i

Where:
- Hamming Distance = Number of differing bits
- ⊕ = XOR operation

Example (SHA-256):
Input 1: "Blockchain"
Input 2: "Blockchian" (one character changed)
Hash 1: 0x8a7c8f4e5a3b2c1d9e0f8a7b6c5d4e3f...
Hash 2: 0xf3e2d1c0b9a8f7e6d5c4b3a2f1e0d9c8...
Hamming Distance ≈ 128 bits (50% of 256 bits)

Input: "Hello, World!"
Hash: 0x1234...

Input: "Hello, World?" (one character changed)
Hash: 0xabcd...

Bit Differences:
Original: 0101 0011 1100 0001 ...
Changed:  1010 1100 0011 1110 ...
XOR:      1111 1111 1111 1111 ...
≈ 50% bits changed

SHA-256 Overview:
- Output Size: 256 bits (32 bytes)
- Input Size: Up to 2⁶⁴ - 1 bits
- Block Size: 512 bits (64 bytes)
- Security Level: 128-bit collision resistance
- Used In: Bitcoin, many altcoins

SHA-256 Algorithm Structure:
1. Padding: Add '1' bit, then zeros
2. Message Schedule: 64 words (32-bit each)
3. Compression Function: 64 rounds
4. Initial Hash Values: 8 constants
5. Final Output: Concatenate 8 words

SHA-256 Constants:
h₀ = 0x6a09e667
h₁ = 0xbb67ae85
h₂ = 0x3c6ef372
h₃ = 0xa54ff53a
h₄ = 0x510e527f
h₅ = 0x9b05688c
h₆ = 0x1f83d9ab
h₇ = 0x5be0cd19

Keccak-256 Overview:
- Output Size: 256 bits (32 bytes)
- Sponge Construction: Absorb + Squeeze
- Security: 128-bit collision resistance
- Used In: Ethereum, zk-SNARKs

Sponge Construction:
1. Absorb Phase: XOR input into state
2. Squeeze Phase: Extract output
3. Security: Resistant to length extension

Why Ethereum chose Keccak-256:
- Faster on 64-bit processors
- Different from SHA-256 (diversity)
- Proven security from SHA-3 competition
- Suitable for smart contracts

RIPEMD-160 Overview:
- Output Size: 160 bits (20 bytes)
- Developed in Europe (RIPE)
- Used In: Bitcoin addresses

Bitcoin Address Creation:
1. Public Key → SHA-256 → RIPEMD-160
2. Result: 160-bit address hash
3. Add checksum (4 bytes)
4. Base58Check encode

Why RIPEMD-160:
- Shorter addresses (160 vs 256 bits)
- Better user experience
- Combined security (SHA-256 + RIPEMD-160)

Birthday Attack Probability:
Probability of collision after k hashes:
P ≈ 1 - e^(-k² / 2^(n+1))

For 128-bit security (n=256):
k ≈ 2¹²⁸ hashes to find collision

For 80-bit security (n=160):
k ≈ 2⁸⁰ hashes to find collision

Birthday Paradox:
- 23 people: 50% chance of shared birthday
- 2^(n/2) hashes: 50% chance of collision

Transaction ID:
TxID = SHA-256(SHA-256(Transaction_Data))

Double Hashing (Bitcoin):
1. First hash: SHA-256(data)
2. Second hash: SHA-256(first_hash)

Why Double Hashing:
- Length extension attack protection
- Consistency with merkle trees
- Bitcoin protocol standard

Block Hash:
Block_Hash = SHA-256(SHA-256(Block_Header))

Block_Header contains:
- Version
- Previous Block Hash
- Merkle Root
- Timestamp
- Difficulty Target
- Nonce

Miners modify Nonce to find valid block hash

Address Generation Flow:

Private Key (256 bits)
     │
     ▼
Public Key (33/65 bytes)
     │
     ▼
SHA-256 Hash (32 bytes)
     │
     ▼
RIPEMD-160 Hash (20 bytes)
     │
     ▼
Add Version Byte (0x00 for Mainnet)
     │
     ▼
Double SHA-256 Checksum (4 bytes)
     │
     ▼
Base58Check Encoding
     │
     ▼
Bitcoin Address

Merkle Tree Construction:
1. Hash each transaction: H(Tx_i)
2. Hash pairs: H(H(Tx₁) + H(Tx₂))
3. Repeat until single hash (Merkle Root)
4. Merkle Root in block header

Merkle Proof:
1. Provide transaction hash
2. Provide sibling hashes on path to root
3. Verifier recomputes hashes
4. Compare to Merkle Root

Proof Size: log₂(N) hashes
Where N = number of transactions

Quantum Computing Threats:

Grover's Algorithm:
- Pre-image search: 2^(n/2) instead of 2^n
- SHA-256: 2¹²⁸ operations (still secure)
- RIPEMD-160: 2⁸⁰ operations (vulnerable)

Shor's Algorithm:
- Does not affect hash functions directly
- Affects RSA, ECC (public-key cryptography)

Post-Quantum Recommendations:
- Larger hash outputs (SHA-512)
- Quantum-resistant hash-based signatures
- SPHINCS+ (hash-based signature scheme)

For t = 0 to 63:
If t < 16:
    W[t] = M[t] (message words)
Else:
    W[t] = σ1(W[t-2]) + W[t-7] + σ0(W[t-15]) + W[t-16]

Where:
σ0(x) = ROTR⁷(x) ⊕ ROTR¹⁸(x) ⊕ SHR³(x)
σ1(x) = ROTR¹⁷(x) ⊕ ROTR¹⁹(x) ⊕ SHR¹⁰(x)

ROTR = Rotate Right (circular shift)
SHR = Shift Right (logical)
⊕ = XOR operation

For t = 0 to 63:
T₁ = h + Σ1(e) + Ch(e,f,g) + K[t] + W[t]
T₂ = Σ0(a) + Maj(a,b,c)
h = g
g = f
f = e
e = d + T₁
d = c
c = b
b = a
a = T₁ + T₂

Where:
Σ0(x) = ROTR²(x) ⊕ ROTR¹³(x) ⊕ ROTR²²(x)
Σ1(x) = ROTR⁶(x) ⊕ ROTR¹¹(x) ⊕ ROTR²⁵(x)
Ch(x,y,z) = (x ∧ y) ⊕ (¬x ∧ z)
Maj(x,y,z) = (x ∧ y) ⊕ (x ∧ z) ⊕ (y ∧ z)

K[t] = 64 constants (first 32 bits of cube roots of primes)

Keccak Sponge:

State Size: 1600 bits (5×5×64)
Bit Rate (r): 1088 bits (for 256-bit output)
Capacity (c): 512 bits
Security Level: c/2 = 256 bits

Absorb Phase:
1. Pad input to multiple of r
2. XOR r bits into state
3. Apply Keccak-f permutation (24 rounds)
4. Repeat until input exhausted

Squeeze Phase:
1. Extract r bits from state
2. If more output needed:
   a. Apply Keccak-f permutation
   b. Extract next r bits
3. Return output

Keccak-f Permutation:
- 24 rounds of operations
- Theta, Rho, Pi, Chi, Iota steps
- High diffusion and confusion

MPT Structure:
1. Leaf Node: Key-value pair
2. Branch Node: Up to 16 children
3. Extension Node: Common prefix

Benefits:
- Efficient state storage
- Cryptographic proofs
- Versioning (history)
- Fast updates

State Root:
- Hash of root node
- Included in block header
- Represents entire state

MMR Structure:
- Binary tree with peaks
- Append-only (immutable)
- Efficient proofs
- Used for history storage

Properties:
- Append-only
- Immutable
- Efficient verification
- Logarithmic proof size

Hash Function Memory:
- SHA-256: 32 bytes (state) + 256 bytes (schedule)
- Keccak: 200 bytes (state) + buffer
- BLAKE2b: 64 bytes (state) + message

Implementation:
- Stack allocation for speed
- Heap allocation for large data
- Reuse buffers for efficiency
- Memory alignment for performance