Learning Objectives:

  • Understand the cryptographic primitives used in blockchain

  • Explain hashing, digital signatures, and public-key cryptography

  • Apply cryptographic concepts to blockchain applications

1.3.1: Cryptographic Hash Functions

Definition:
A cryptographic hash function is a mathematical algorithm that maps data of arbitrary size to a fixed-size output (hash value).

Key Properties of Cryptographic Hashes:

 
 
Property Description Importance
Deterministic Same input always produces same output Verification
Fast Computation Hash computation is efficient Performance
Pre-image Resistance Cannot reverse hash to find input Security
Second Pre-image Resistance Cannot find different input with same hash Integrity
Collision Resistance Cannot find two inputs with same hash Uniqueness
Avalanche Effect Small change in input drastically changes output Sensitivity

Common Hash Functions in Blockchain:

 
 
Hash Function Output Size Blockchain Use
SHA-256 256 bits Bitcoin, many others
Keccak-256 (SHA-3) 256 bits Ethereum, zk-SNARKs
RIPEMD-160 160 bits Bitcoin addresses
Blake2b 256-512 bits Filecoin, Zcash
SHA-512 512 bits Some altcoins

Mathematical Representation:

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

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

Example:
H("Blockchain") = 0x8a7c8f4e... (256-bit hash)

1.3.2: Hash Function Properties in Detail

1. Pre-image Resistance

Given a hash value h, it should be computationally infeasible to find any message m such that H(m) = h.

text
Given: H(m) = h
Goal: Find m from h
Difficulty: O(2ⁿ) operations (where n = output bits)

For SHA-256 (n=256): 2²⁵⁶ operations (infeasible)

2. Second Pre-image Resistance

Given a message m₁, it should be computationally infeasible to find m₂ ≠ m₁ such that H(m₂) = H(m₁).

text
Given: H(m₁) = h
Goal: Find m₂ ≠ m₁ with H(m₂) = h
Difficulty: O(2ⁿ) operations

Implication: Cannot change a transaction without changing its hash

3. Collision Resistance

It should be computationally infeasible to find any two distinct messages m₁ and m₂ such that H(m₁) = H(m₂).

text
Goal: Find m₁ ≠ m₂ with H(m₁) = H(m₂)
Difficulty: O(2^(n/2)) operations (Birthday attack)

For SHA-256: 2¹²⁸ operations (infeasible)

1.3.3: Public-Key Cryptography

Definition:
Public-key cryptography uses pairs of keys:

  • Public Key: Can be shared with anyone

  • Private Key: Must be kept secret

text
Key Generation:
Private Key (sk) ──┐
                   ├──→ Public Key (pk)
                   │
                   │  (One-way function: pk = f(sk))
                   │
                   │  Given pk, cannot find sk
                   ▼

Elliptic Curve Cryptography (ECC):

Most blockchain systems use ECC because:

  • Smaller keys (256 bits vs 3072 bits for RSA)

  • Faster computations

  • Stronger security per bit

Bitcoin Address Generation:

text
Private Key (256 bits)
      │
      ▼
Elliptic Curve Multiplication
      │
      ▼
Public Key (33/65 bytes)
      │
      ▼
SHA-256 Hash
      │
      ▼
RIPEMD-160 Hash (20 bytes)
      │
      ▼
Base58Check Encoding
      │
      ▼
Bitcoin Address

1.3.4: Digital Signatures

Definition:
Digital signatures provide proof of authenticity and integrity of a message.

Signature Process:

text
Signing:
Message ──┐
          ├──→ Signature Algorithm ──→ Signature
Private Key─┘

Verification:
Message ──┐
          ├──→ Verification Algorithm ──→ Valid/Invalid
Public Key─┘
Signature─┘

Properties of Digital Signatures:

 
 
Property Description
Authenticity Proof that signer created the signature
Integrity Message cannot be changed without invalidating signature
Non-repudiation Signer cannot deny signing the message
Verifiability Anyone can verify with public key

Signature Schemes in Blockchain:

 
 
Scheme Blockchain Features
ECDSA Bitcoin, Ethereum Standard, widely used
Schnorr Bitcoin (Taproot) More efficient, aggregation
Ed25519 Solana, Zcash Faster, smaller signatures
BLS Ethereum 2.0 Signature aggregation

1. SHA-256 Deep Dive

SHA-256 Algorithm Overview:

text
SHA-256 Processing:

1. Padding:
   - Add '1' bit to end of message
   - Add '0' bits until length ≡ 448 mod 512
   - Add 64-bit representation of original length

2. Initialize Hash Values (8 × 32 bits):
   h₀ = 0x6a09e667
   h₁ = 0xbb67ae85
   h₂ = 0x3c6ef372
   h₃ = 0xa54ff53a
   h₄ = 0x510e527f
   h₅ = 0x9b05688c
   h₆ = 0x1f83d9ab
   h₇ = 0x5be0cd19

3. Process in 512-bit chunks:
   For each chunk:
     a. Create 64 message schedule words (32-bit each)
     b. Initialize working variables
     c. Perform 64 rounds of compression
     d. Add to hash values

4. Final Output:
   Concatenate h₀ to h₇ (256-bit hash)

2. Merkle Trees

Definition:
A Merkle tree is a binary tree where each leaf node is a hash of a transaction, and each internal node is a hash of its children.

text
Merkle Tree Structure:

                    Merkle Root (H₁₂₃₄)
                           │
           ┌───────────────┴───────────────┐
           │                               │
        H₁₂                               H₃₄
           │                               │
     ┌─────┴─────┐                   ┌─────┴─────┐
     │           │                   │           │
    H₁          H₂                  H₃          H₄
     │           │                   │           │
   Tx₁         Tx₂                  Tx₃         Tx₄

Verification:
To prove Tx₃ is in the tree, provide:
- H₄
- H₁₂
- Merkle Root
(Log₂(n) hashes needed for proof)

Merkle Proof Size:

text
Proof Size = log₂(N) hashes

For 1,000,000 transactions:
Proof Size = log₂(1,000,000) ≈ 20 hashes = 640 bytes

This allows light clients to verify transactions efficiently

3. ECDSA Signatures

ECDSA Signing Process:

text
Parameters:
- Curve: secp256k1 (for Bitcoin)
- G = Generator point
- n = Order of curve

Signing:
1. Generate random k (1 ≤ k ≤ n-1)
2. Compute point R = k × G
3. r = R.x mod n
4. Compute s = k⁻¹ × (z + r × priv_key) mod n
5. Signature = (r, s)

Verification:
1. Check 1 ≤ r ≤ n-1 and 1 ≤ s ≤ n-1
2. Compute u₁ = z × s⁻¹ mod n
3. Compute u₂ = r × s⁻¹ mod n
4. Point = u₁ × G + u₂ × pub_key
5. Verify point.x == r

Where z = hash(message)

4. Digital Signature Properties

Security Properties:

text
1. Existential Unforgeability (EUF):
   Cannot create valid signature without private key

2. Strong Unforgeability:
   Cannot create valid signature for any new message

3. Non-repudiation:
   Signer cannot deny signing the message

4. Message Binding:
   Signature is tied to the specific message

5. Key Binding:
   Signature is tied to the specific signer

5. Cryptographic Security Levels

 
 
Security Level Symmetric (AES) RSA ECC Quantum Resistant?
80-bit 80 bits 1024 bits 160 bits No
128-bit 128 bits 3072 bits 256 bits No
192-bit 192 bits 7680 bits 384 bits No
256-bit 256 bits 15360 bits 521 bits Yes (with PQ)

 

PreviousNext