# Cryptographic Foundations of Bitcoin - Glossary
###### tags: `bitcoin` `cryptography` `fundamentals`

**Tabla de contenido**
[TOC]

## Autores
[Dulce Villarreal](https://www.linkedin.com/in/dulcevillarreal/)
Mail para correcciones, comentarios o sugerencias: [[e-mail]](https://twitter.com/Entreplanctony1)

El presente documentos fue elaborado para el curso de [Bitcoin Fundamentals](https://libreriadesatoshi.com/) a través de [@libreriadesatoshi](https://twitter.com/libdesatoshi).

# Cryptographic Foundations of Bitcoin - Glossary

*Definitions organized by curriculum module order*

---

## **Module 1: Cryptographic Foundations**

### **Cryptography**
**Brief Definition:** The science of securing communication and data through mathematical techniques, ensuring confidentiality, integrity, and authenticity.

**Technical Definition:** Cryptography is the mathematical science that designs algorithms and protocols to secure information systems against adversarial attacks. It encompasses four main goals:
(1) **Confidentiality** - ensuring data is accessible only to authorized parties,
(2) **Integrity** - detecting unauthorized data modification,
(3) **Authenticity** - verifying the source of data, and
(4) **Non-repudiation** - preventing denial of actions. Modern cryptography relies on computational complexity theory, where security is based on the assumption that certain mathematical problems (like integer factorization or discrete logarithms) are computationally intractable for large inputs.

**Example:** Consider Alice sending a message to Bob through an insecure channel monitored by Eve (eavesdropper):

Plaintext:  "Transfer $100 to Bob"
Key:        k = 0x2A3F...
Encryption: E(message, k) → ciphertext
Ciphertext: 0x8B9C2D...
Decryption: D(ciphertext, k) → "Transfer $100 to Bob"

### **Confidentiality**
**Brief Definition:** The property that information is accessible only to authorized parties; data remains secret from unauthorized observers.

**Technical Definition:** Confidentiality in cryptography is formally defined using semantic security or indistinguishability. A cryptographic scheme provides confidentiality if an adversary cannot distinguish between encryptions of two messages of their choice, even when given access to an encryption oracle. This is formalized through games like IND-CPA (Indistinguishability under Chosen Plaintext Attack) where the adversary's advantage in distinguishing encryptions must be negligible.

**Example:** Bitcoin addresses provide computational confidentiality through ECDSA:

Private Key: d = 0x18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725
Public Key:  Q = d × G (elliptic curve point multiplication)
Address:     RIPEMD160(SHA256(Q)) → 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2

Without knowledge of private key `d`, it's computationally infeasible to link the address to the owner.

### **Integrity**
**Brief Definition:** The assurance that data has not been altered, corrupted, or tampered with during transmission or storage.

**Technical Definition:** Cryptographic integrity is achieved through Message Authentication Codes (MACs) or digital signatures. A scheme provides integrity if an adversary cannot produce a valid authentication tag for a message they haven't seen before, formalized through EUF-CMA (Existential Unforgeability under Chosen Message Attack). The integrity property ensures that any modification to data will be detected with overwhelming probability.

**Example:** Bitcoin transaction integrity using digital signatures:

Transaction: {from: Alice, to: Bob, amount: 1 BTC, nonce: 12345}
Hash: H(transaction) = SHA256(transaction) = 0x7A8B9C...
Signature: σ = ECDSA_sign(private_key, H(transaction))
Verification: ECDSA_verify(public_key, H(transaction), σ) → True/False

If anyone modifies the transaction (even changing 1 BTC to 2 BTC), the signature verification will fail, detecting the tampering.

### **Authenticity**
**Brief Definition:** The verification that a message, transaction, or data originates from a claimed source and has not been forged.

**Technical Definition:** Authenticity combines integrity with source verification. In public-key cryptography, authenticity is achieved through digital signatures that bind a message to a specific private key holder. The security relies on the unforgeability property: given a public key, it's computationally infeasible to produce a valid signature without knowing the corresponding private key. This is formalized through the EUF-CMA security model.

**Example:** Bitcoin transaction authenticity verification:

Alice claims to send 1 BTC to Bob:

Transaction Data:
  Input: Previous UTXO reference
  Output: Bob's address, 1 BTC
  Signature: σ_Alice

Verification Process:
1. Extract Alice's public key from previous transaction
2. Compute message hash: h = SHA256(transaction_data)
3. Verify: ECDSA_verify(pub_Alice, h, σ_Alice)
4. If True → transaction is authentic from Alice
   If False → transaction is forged or corrupted

### **Symmetric Cryptography**
**Brief Definition:** A cryptographic system where the same key is used for both encryption and decryption; requires secure key distribution.

**Technical Definition:** Symmetric cryptography uses a single secret key K shared between communicating parties. Security relies on keeping K secret and using algorithms like AES (Advanced Encryption Standard). The system provides semantic security if the encryption algorithm is indistinguishable from random under chosen-plaintext attacks. Key management is the primary challenge, requiring secure channels for key distribution and periodic key rotation.

**Example:** AES-256 encryption (not directly used in Bitcoin, but illustrative):

Key: K = 0x000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F
Plaintext:  "Hello Bitcoin World!"
IV:         0x101112131415161718191A1B1C1D1E1F (Initialization Vector)

Encryption: C = AES-256-CBC(K, IV, plaintext)
Ciphertext: 0x8E73B0F7DA0E6452C810F32B809079E562F8EAD2522C6B7B

Decryption: AES-256-CBC-Decrypt(K, IV, C) → "Hello Bitcoin World!"

### **Asymmetric Cryptography (Public-Key Cryptography)**
**Brief Definition:** A cryptographic system using pairs of mathematically related keys: a public key (shared openly) and a private key (kept secret).

**Technical Definition:** Public-key cryptography relies on mathematical trapdoor functions - functions that are easy to compute in one direction but hard to reverse without special information (the trapdoor). The system uses key pairs (pk, sk) where pk is public and sk is private. Security is based on hard mathematical problems like integer factorization (RSA) or discrete logarithm problem (ECDSA). The fundamental property is that knowing pk provides no computationally feasible way to determine sk.

**Example:** ECDSA key generation in Bitcoin:

Elliptic Curve: secp256k1: y² ≡ x³ + 7 (mod p)
Generator Point: G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D9..., 
                     0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08F...)

Key Generation:
1. Choose random private key: d ∈ [1, n-1] where n = curve order
   d = 0x18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725

2. Calculate public key: Q = d × G (elliptic curve scalar multiplication)
   Q = (0x50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352,
        0x2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6)

Mathematical Relationship: Q = d × G, but finding d from Q and G is the ECDLP (hard problem)

### **Discrete Logarithm Problem**
**Brief Definition:** The computational problem of finding the exponent x in the equation g^x ≡ h (mod p), believed to be difficult for large values.

**Technical Definition:** Given a cyclic group G of order n with generator g, and an element h ∈ G, the discrete logarithm problem is to find the unique integer x ∈ [0, n-1] such that g^x = h. The best known algorithms for solving this problem (like Pollard's rho) require O(√n) operations, making it intractable for sufficiently large n. In elliptic curve cryptography, this becomes the Elliptic Curve Discrete Logarithm Problem (ECDLP).

**Example:** Discrete logarithm in the context of Bitcoin's secp256k1:

Given:
- Elliptic curve secp256k1
- Generator point G
- Public key point Q = d × G

Problem: Find private key d given Q and G

Mathematical formulation:
Q = d × G = G + G + ... + G (d times)

Known: Q = (x_Q, y_Q), G = (x_G, y_G)
Unknown: d (the discrete logarithm)

Security: Best known algorithms require approximately 2^128 operations
         for secp256k1's 256-bit keys, making it computationally infeasible

Example values:
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
     0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

If d = 123456789, then Q = 123456789 × G
Finding d from Q is the hard problem that secures Bitcoin addresses

---

## **Module 2: Hash Functions and Data Integrity**

### **Hash Function**
**Brief Definition:** A mathematical function that transforms input data of any size into a fixed-size output (hash value or digest).

**Technical Definition:** A cryptographic hash function H: {0,1}* → {0,1}^n is a deterministic algorithm that maps arbitrary-length bit strings to fixed-length n-bit strings. It must satisfy three security properties: (1) Preimage resistance: given h, it's hard to find m such that H(m) = h, (2) Second preimage resistance: given m₁, it's hard to find m₂ ≠ m₁ such that H(m₁) = H(m₂), (3) Collision resistance: it's hard to find any m₁ ≠ m₂ such that H(m₁) = H(m₂). The function should also exhibit the avalanche effect and produce uniformly distributed outputs.

**Example:** SHA-256 hash function used in Bitcoin:

Input message: "Hello Bitcoin"
Binary representation: 01001000 01100101 01101100 01101100 01101111 00100000 01000010 01101001 01110100 01100011 01101111 01101001 01101110

SHA-256 Processing:
1. Preprocessing: Pad message to 512-bit blocks
   Original: "Hello Bitcoin" (13 bytes = 104 bits)
   Padded: 104 bits + 1 bit + 407 zero bits + 64-bit length = 512 bits

2. Initialize hash values (first 32 bits of fractional parts of square roots of first 8 primes):
   h₀ = 0x6a09e667, h₁ = 0xbb67ae85, h₂ = 0x3c6ef372, h₃ = 0xa54ff53a
   h₄ = 0x510e527f, h₅ = 0x9b05688c, h₆ = 0x1f83d9ab, h₇ = 0x5be0cd19

3. Process blocks through 64 rounds of operations
4. Final hash: 0x1D4F6625B446E8AC5ED8848C06FA9F1FB73C04AED9F77A90F0CB8FDD9F0A9D2C

Properties demonstrated:
- Deterministic: Same input always produces same hash
- Fixed output: Always 256 bits regardless of input size
- Avalanche effect: Changing one bit in input drastically changes output

### **Avalanche Effect**
**Brief Definition:** A property where a small change in input produces a dramatically different output; crucial for security.

**Technical Definition:** The avalanche effect requires that changing any single input bit results in each output bit changing with probability 1/2. Mathematically, for a hash function H, if inputs x and x' differ in exactly one bit, then H(x) and H(x') should differ in approximately n/2 bits for an n-bit output. This property ensures that similar inputs don't produce similar outputs, preventing pattern analysis attacks and ensuring uniform distribution of hash values.

**Example:** Demonstrating avalanche effect in SHA-256:

Original message: "Bitcoin"
SHA-256: 0x6B88C087247AA2F07EE1C5956B8E1A9F4C7F892A70E324F1BB3D161E05CA107B

Changed message: "bitcoin" (only capitalization changed)
SHA-256: 0x7FA9F77DC04BE0E0FFC5CF513DC0E4F29E0B81DEF7A5C28B9689DA9E84FF5C62

Bit difference analysis:
Original:  0110101110001000110000100111...
Changed:   0111111110101001110111000000...
XOR:       0001010000101101000111000111...

Hamming distance: 131 bits different out of 256 (51.2% ≈ 50% ideal)

This demonstrates perfect avalanche effect - a tiny input change 
causes approximately half the output bits to flip.

### **Hash Pointer**
**Brief Definition:** A data structure that contains both the location of data and a cryptographic hash of that data, enabling tamper detection.

**Technical Definition:** A hash pointer is a tuple (ptr, H(data)) where ptr is a memory address or reference to data, and H(data) is the cryptographic hash of that data. This structure provides both addressing capability and integrity verification. Any modification to the referenced data will cause a hash mismatch, immediately detecting tampering. Hash pointers can be chained to create tamper-evident data structures like blockchains.

**Example:** Bitcoin blockchain using hash pointers:

Block Structure:
┌─────────────────────────────────────┐
│            Block Header             │
│  ┌─────────────────────────────────┐ │
│  │ Previous Block Hash (Hash Ptr)  │ │ ← Points to previous block
│  │ Merkle Root                     │ │ ← Hash of all transactions
│  │ Timestamp                       │ │
│  │ Difficulty Target              │ │
│  │ Nonce                          │ │
│  └─────────────────────────────────┘ │
├─────────────────────────────────────┤
│            Transactions             │
│  Transaction 1                      │
│  Transaction 2                      │
│  ...                               │
│  Transaction n                      │
└─────────────────────────────────────┘

Hash Pointer Chain:
Block N-1 → Block N → Block N+1
    ↑         ↑         ↑
   Hash     Hash     Hash
   Ptr      Ptr      Ptr

Example:
Block 100 Header Hash: 0x00000000000003ba27aa200b1cecaad478d2b00432346c3f1f3986da1afd33e506
Block 101 Previous Hash: 0x00000000000003ba27aa200b1cecaad478d2b00432346c3f1f3986da1afd33e506

If Block 100 is tampered with:
- New Block 100 Hash: 0x00000000000003ba27aa200b1cecaad478d2b00432346c3f1f3986da1afd33e999
- Block 101 Previous Hash: 0x00000000000003ba27aa200b1cecaad478d2b00432346c3f1f3986da1afd33e506
- Mismatch detected! Chain integrity violated.

### **Merkle Tree**
**Brief Definition:** A binary tree data structure where leaf nodes contain data hashes and internal nodes contain hashes of their children.

**Technical Definition:** A Merkle tree is a complete binary tree where each leaf node contains the hash of a data block, and each internal node contains the hash of the concatenation of its children's hashes. For a tree with n leaves, the root represents a commitment to all n data blocks. The tree enables efficient membership proofs: to prove a data block is included, one only needs to provide O(log n) hashes (the siblings along the path from leaf to root). The security relies on the collision resistance of the underlying hash function.

**Example:** Bitcoin transaction Merkle tree:

Consider 4 transactions in a block:

Transactions (leaves):
Tx1: "Alice → Bob: 1 BTC"     → H(Tx1) = 0xA1B2...
Tx2: "Bob → Carol: 0.5 BTC"   → H(Tx2) = 0xC3D4...
Tx3: "Carol → Dave: 0.3 BTC"  → H(Tx3) = 0xE5F6...
Tx4: "Dave → Eve: 0.2 BTC"    → H(Tx4) = 0x7890...

Merkle Tree Construction:
                    Root
                 H(H12 + H34)
                /           \
           H12               H34
        H(H1+H2)          H(H3+H4)
        /      \          /      \
    H(Tx1)   H(Tx2)   H(Tx3)   H(Tx4)
     A1B2     C3D4     E5F6     7890

Step-by-step calculation:
Level 1: H12 = SHA256(A1B2 + C3D4) = 0x1234...
         H34 = SHA256(E5F6 + 7890) = 0x5678...

Level 0: Root = SHA256(1234 + 5678) = 0x9ABC...

Inclusion proof for Tx1:
Proof = [H(Tx2), H34] = [C3D4, 5678]
Verification:
1. Compute H12' = SHA256(A1B2 + C3D4) ✓
2. Compute Root' = SHA256(H12' + 5678) ✓
3. Check Root' == Root ✓

Efficiency: Only 2 hashes needed instead of all 4 transactions

### **SPV (Simplified Payment Verification)**
**Brief Definition:** A method for Bitcoin clients to verify transactions without downloading the entire blockchain by using Merkle proofs.

**Technical Definition:** SPV is a lightweight verification method where clients download only block headers (80 bytes each) instead of full blocks (typically 1-4 MB). To verify a transaction, the client requests a Merkle proof from full nodes. The client can verify transaction inclusion by: (1) Computing the Merkle root using the proof, (2) Checking that the computed root matches the Merkle root in the block header, (3) Verifying the block header has sufficient proof-of-work. SPV provides probabilistic security: the more confirmations (subsequent blocks), the higher the confidence.

**Example:** SPV verification process:

SPV Client wants to verify: "Alice sent 1 BTC to Bob" in Block 750,000

Step 1: Download block headers only
Block 750,000 Header (80 bytes):
├─ Previous Hash: 0x000000000000000000024bead8df69990852c202db0e0097c1a12ea637d7e96d
├─ Merkle Root:   0x4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b
├─ Timestamp:     1659277149
├─ Difficulty:    0x1712daa9
├─ Nonce:         1914849169

Step 2: Request Merkle proof for Alice→Bob transaction
Proof received:
├─ Transaction Hash: 0x8b30c40183ce5c3dc6ba146da61c55c456abc955c5cd6513b8cbfb04c28c3717
├─ Merkle Path: [0x2f37b56d4e, 0x9a45c831f2, 0x6b8e7d23a1] (sibling hashes)
├─ Path Indices: [0, 1, 0] (left=0, right=1 at each level)

Step 3: Verify inclusion
merkle_root_calculated = verify_merkle_proof(
    tx_hash=0x8b30c40183ce5c3dc6ba146da61c55c456abc955c5cd6513b8cbfb04c28c3717,
    proof=[0x2f37b56d4e, 0x9a45c831f2, 0x6b8e7d23a1],
    indices=[0, 1, 0]
)

Level 2: SHA256(0x8b30c40183... + 0x2f37b56d4e) = 0x1a2b3c...
Level 1: SHA256(0x9a45c831f2 + 0x1a2b3c...) = 0x4d5e6f...  
Level 0: SHA256(0x4d5e6f... + 0x6b8e7d23a1) = 0x4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b

Result: Calculated root matches header Merkle root ✓
Storage: ~300 bytes vs ~2MB full block (99.985% reduction)

---

## **Module 4: Digital Signatures**

### **ECDSA (Elliptic Curve Digital Signature Algorithm)**
**Brief Definition:** Bitcoin's primary digital signature scheme based on elliptic curve cryptography and discrete logarithms.

**Technical Definition:** ECDSA is a variant of DSA using elliptic curve arithmetic. It operates on the secp256k1 curve: y² ≡ x³ + 7 (mod p) where p = 2²⁵⁶ - 2³² - 977. The algorithm consists of three phases: (1) Key generation: select random private key d ∈ [1, n-1] and compute public key Q = d×G, (2) Signing: for message m, select random k, compute r = (k×G).x mod n and s = k⁻¹(H(m) + d×r) mod n, output (r,s), (3) Verification: compute u₁ = H(m)×s⁻¹ mod n and u₂ = r×s⁻¹ mod n, check if r ≡ (u₁×G + u₂×Q).x mod n.

**Example:** Complete ECDSA signature process:

Elliptic Curve Parameters (secp256k1):
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
     0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

Key Generation:
Private key: d = 0x18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725
Public key:  Q = d × G = (Qx, Qy)

Message to sign: "Transfer 1 BTC to Bob"
Message hash: z = SHA256("Transfer 1 BTC to Bob") = 0x1D2E3F...

Signature Generation:
1. Generate random nonce: k = 0x2A5B7C8D9E0F1A2B3C4D5E6F7A8B9C0D1E2F3A4B5C6D7E8F9A0B1C2D3E4F5A6B
2. Compute point: (x₁, y₁) = k × G
3. Compute r = x₁ mod n = 0x4B5A6C7D...
4. Compute s = k⁻¹(z + d×r) mod n = 0x8E9F0A1B...
5. Signature: (r, s) = (0x4B5A6C7D..., 0x8E9F0A1B...)

Verification:
1. Check 0 < r < n and 0 < s < n ✓
2. Compute w = s⁻¹ mod n
3. Compute u₁ = z×w mod n and u₂ = r×w mod n
4. Compute point: (x₂, y₂) = u₁×G + u₂×Q
5. Verify: r ≡ x₂ mod n ✓

Security: Breaking requires solving ECDLP (finding d from Q) or breaking SHA-256

### **Nonce**
**Brief Definition:** A random value used in signature generation that must be unique for each signature to maintain security.

**Technical Definition:** In ECDSA, the nonce k is a cryptographically secure random integer in the range [1, n-1] where n is the curve order. The nonce must satisfy three critical properties: (1) Unpredictability: each k must be uniformly random and independent, (2) Uniqueness: k must never be reused with the same private key, (3) Secrecy: k must remain secret after signature generation. Failure in any property leads to private key recovery. The nonce directly affects the signature component r = (k×G).x mod n.

**Example:** Nonce reuse attack (Sony PlayStation 3 vulnerability):

ECDSA Signature with nonce reuse:
Message 1: m₁ = "Firmware update 1"
Message 2: m₂ = "Firmware update 2"  
Same nonce: k (used for both signatures)

Signature 1: (r₁, s₁) where r₁ = (k×G).x mod n
            s₁ = k⁻¹(H(m₁) + d×r₁) mod n

Signature 2: (r₂, s₂) where r₂ = (k×G).x mod n = r₁
            s₂ = k⁻¹(H(m₂) + d×r₁) mod n

Attack - Private Key Recovery:
Since r₁ = r₂, we can solve for k:
s₁ - s₂ = k⁻¹(H(m₁) - H(m₂)) mod n
k = (H(m₁) - H(m₂))/(s₁ - s₂) mod n

With k known, recover private key d:
d = (s₁×k - H(m₁))/r₁ mod n

Example calculation (simplified):
H(m₁) = 0x1234, H(m₂) = 0x5678
s₁ = 0x9ABC, s₂ = 0xDEF0, r₁ = r₂ = 0x2468

k = (0x1234 - 0x5678)/(0x9ABC - 0xDEF0) mod n
d = (0x9ABC × k - 0x1234)/0x2468 mod n

Result: Complete private key compromise from nonce reuse!

### **Schnorr Signature**
**Brief Definition:** An alternative digital signature scheme offering advantages like linearity and batch verification over ECDSA.

**Technical Definition:** Schnorr signatures operate on the same elliptic curve as ECDSA but use a simpler, more elegant construction. The signature algorithm: (1) Key generation: private key x, public key P = x×G, (2) Signing: choose random k, compute R = k×G, e = H(R || P || m), s = k + e×x mod n, output (R, s), (3) Verification: compute e = H(R || P || m) and check s×G = R + e×P. Schnorr signatures are provably secure under the discrete logarithm assumption and provide signature aggregation through their linear property.

**Example:** Schnorr signature with aggregation:

BIP 340 Schnorr Implementation:

Single Signature:
Private key: x = 0x0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710
Public key:  P = x×G (lift_x coordinate only per BIP 340)

Message: m = "Schnorr test message"
Auxiliary random data: a = 0x0000...0001

Signature Generation:
1. Compute t = (x ⊕ H(a)) where ⊕ is XOR
2. Generate k = H(t || P || m) mod n (deterministic nonce)
3. Compute R = k×G, if R.y is odd, negate k
4. Compute e = H(R.x || P || m) (challenge hash)
5. Compute s = (k + e×x) mod n
6. Output: (R.x, s) (64 bytes total)

Multi-signature Aggregation (2-of-2):
Alice: private key x₁, public key P₁ = x₁×G
Bob:   private key x₂, public key P₂ = x₂×G

Combined public key: P = P₁ + P₂ (key aggregation)

Individual signatures:
Alice: (R₁, s₁) for message m
Bob:   (R₂, s₂) for same message m

Aggregate signature:
R = R₁ + R₂
s = s₁ + s₂ mod n

Verification of aggregate:
s×G = R + e×(P₁ + P₂) where e = H(R || P₁+P₂ || m)

Benefits:
- Linear: signatures can be added mathematically
- Batch verification: multiple signatures verified together
- Non-malleability: signatures have unique representation
- Provable security: reduction to discrete logarithm problem

---

## **Module 5: Public-Key Cryptography in Bitcoin**

### **Bitcoin Address**
**Brief Definition:** A string of alphanumeric characters representing a destination for Bitcoin payments, derived from public keys.

**Technical Definition:** A Bitcoin address is a Base58Check encoded representation of a hashed public key or script, designed to be shorter and more user-friendly than raw public keys while maintaining security through hash function preimage resistance. Different address types use different encoding schemes: P2PKH uses RIPEMD160(SHA256(pubkey)), P2SH uses RIPEMD160(SHA256(script)), and Bech32 addresses use witness programs. The address generation process includes checksums to detect transcription errors.

**Example:** Complete address generation process:

Starting from private key to address:

Step 1 - Private Key (256 bits):
privkey = 0x18E14A7B6A307F426A94F8114701E7C8E774E7F9A47E2C2035DB29A206321725

Step 2 - Public Key Generation:
pubkey = privkey × G (elliptic curve multiplication)
pubkey_uncompressed = 04 || x_coordinate || y_coordinate (65 bytes)
pubkey_compressed = 02/03 || x_coordinate (33 bytes, preferred)

pubkey_compressed = 0x0250863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352

Step 3 - Address Generation (P2PKH):
sha256_hash = SHA256(pubkey_compressed) = 0x0b7c28c9b7290c98d7438e70b3d3f7c848fbd7d1e04b395b...
ripemd160_hash = RIPEMD160(sha256_hash) = 0x010966776006953d5567439e5e39f86a0d273bee

Step 4 - Add Network Byte:
network_byte = 0x00 (mainnet)
extended_hash = 0x00 || 0x010966776006953d5567439e5e39f86a0d273bee

Step 5 - Calculate Checksum:
checksum = SHA256(SHA256(extended_hash))[0:4]
checksum = 0xb0c4294d

Step 6 - Base58 Encoding:
final_address_bytes = extended_hash || checksum
final_address_bytes = 0x00010966776006953d5567439e5e39f86a0d273beeb0c4294d

Base58 encoded: 16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM

Address Types Comparison:
┌─────────────┬─────────────────┬─────────────────────────────────────┐
│ Type        │ Prefix          │ Example                             │
├─────────────┼─────────────────┼─────────────────────────────────────┤
│ P2PKH       │ 1               │ 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2  │
│ P2SH        │ 3               │ 3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLy  │
│ Bech32      │ bc1q            │ bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t4 │
│ Bech32m     │ bc1p            │ bc1p5d7rjq7g6rdk2yhzks9smlaqtedr4dekq08ge8ztwac72sfr9rusxg3297 │
└─────────────┴─────────────────┴─────────────────────────────────────┘

### **Hierarchical Deterministic (HD) Wallet**
**Brief Definition:** A wallet system generating all keys from a single seed, enabling organized key management and backup.

**Technical Definition:** HD wallets (BIP 32) use a tree structure to derive multiple key pairs from a single master seed through a deterministic process. The system employs HMAC-SHA512 for key derivation, creating a hierarchy where each level can generate 2³¹ normal child keys and 2³¹ hardened child keys. The derivation path uses notation m/purpose'/coin_type'/account'/change/address_index where ' indicates hardened derivation. Hardened derivation (index ≥ 2³¹) requires the private key, while non-hardened derivation can be performed with only the public key, enabling watch-only wallets.

**Example:** HD wallet key derivation (BIP 44 structure):

Seed Generation:
Mnemonic: "abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon about"
Seed = PBKDF2(mnemonic, "mnemonic" + passphrase, 2048 iterations, 512 bits)
Seed = 0x5eb00bbddcf069084889a8ab9155568165f5c453ccb85e70811aaed6f6da5fc19a5ac40b389cd370d086206dec8aa6c43daea6690f20ad3d8d48b2d2ce9e38e4

Master Key Generation:
I = HMAC-SHA512("Bitcoin seed", seed)
master_private_key = I[0:32] = 0x1837c1be8e2995ec11cda2b066151be2cfb48adf9e47b151d46adab3a21cdf67
master_chain_code = I[32:64] = 0x9452b549be8cea3ecb7a84bec10dcfd94afe4d129ebfd3b3cb58eedf394ed271

BIP 44 Derivation Path: m/44'/0'/0'/0/0
(purpose=44, coin_type=0 (Bitcoin), account=0, change=0 (receive), address_index=0)

Level 1 - Purpose (m/44'):
index = 44 + 2³¹ = 2147483692 (hardened)
I₁ = HMAC-SHA512(master_chain_code, 0x00 || master_private_key || index)
private_key₁ = (master_private_key + I₁[0:32]) mod n
chain_code₁ = I₁[32:64]

Level 2 - Coin Type (m/44'/0'):
index = 0 + 2³¹ = 2147483648 (hardened)
I₂ = HMAC-SHA512(chain_code₁, 0x00 || private_key₁ || index)
private_key₂ = (private_key₁ + I₂[0:32]) mod n
chain_code₂ = I₂[32:64]

Level 3 - Account (m/44'/0'/0'):
index = 0 + 2³¹ = 2147483648 (hardened)
I₃ = HMAC-SHA512(chain_code₂, 0x00 || private_key₂ || index)
private_key₃ = (private_key₂ + I₃[0:32]) mod n
chain_code₃ = I₃[32:64]

Level 4 - Change (m/44'/0'/0'/0):
index = 0 (non-hardened)
public_key₃ = private_key₃ × G
I₄ = HMAC-SHA512(chain_code₃, public_key₃ || index)
private_key₄ = (private_key₃ + I₄[0:32]) mod n
chain_code₄ = I₄[32:64]

Level 5 - Address Index (m/44'/0'/0'/0/0):
index = 0 (non-hardened)
public_key₄ = private_key₄ × G
I₅ = HMAC-SHA512(chain_code₄, public_key₄ || index)
final_private_key = (private_key₄ + I₅[0:32]) mod n
final_public_key = final_private_key × G

Final Bitcoin Address: 1LqBGSKuX5yYUonjxT5qGfpUsXKYYWeabA

Advantages:
- Single backup (seed phrase) protects infinite keys
- Hierarchical organization (accounts, change addresses)
- Extended public keys enable watch-only wallets
- Deterministic: same seed always generates same keys

### **Multi-signature (Multisig)**
**Brief Definition:** A scheme requiring multiple valid signatures from different keys to authorize a transaction or operation.

**Technical Definition:** Bitcoin multisig uses M-of-N threshold schemes where M signatures out of N possible public keys are required to spend funds. Implemented through P2SH (Pay-to-Script-Hash) or native SegWit, the redeem script specifies the threshold and public keys. The transaction is valid only if M valid signatures are provided, where each signature must be from a different private key corresponding to the specified public keys. The script execution follows Bitcoin's stack-based virtual machine, verifying each signature against the transaction hash.

**Example:** 2-of-3 multisig implementation:

Setup Phase:
Alice's key pair:   (priv_A, pub_A) 
Bob's key pair:     (priv_B, pub_B)
Charlie's key pair: (priv_C, pub_C)

Redeem Script Creation:
OP_2                          # Require 2 signatures
pub_A                         # Alice's public key (33 bytes)
pub_B                         # Bob's public key (33 bytes)  
pub_C                         # Charlie's public key (33 bytes)
OP_3                          # Out of 3 total keys
OP_CHECKMULTISIG             # Verify multisig condition

redeem_script = 0x522102b4a72e4aaa69ba04873e3eb00e4a4b9cbdc73e54fb2f2d9a28d8e9c45b6b3e8c192103c11c3b1e6b54d8b7c8d9e0f1a2b3c4d5e6f7a8b9c0d1e2f3a4b5c6d7e8f9a0b121034d5e6f7a8b9c0d1e2f3a4b5c6d7e8f9a0b1c2d3e4f5a6b7c8d9e0f1a2b3c4d5e53ae

P2SH Address Generation:
script_hash = RIPEMD160(SHA256(redeem_script))
p2sh_address = Base58Check(0x05 || script_hash)  # Starts with '3'
p2sh_address = 3QJmV3qfvL9SuYo34YihAf3sRCW3qSinyC

Spending Transaction (Alice + Bob sign):
Transaction to sign:
{
  "inputs": [{
    "prev_hash": "a1b2c3d4...",
    "prev_index": 0,
    "script_sig": "", # To be filled
    "sequence": 0xffffffff
  }],
  "outputs": [{
    "value": 100000000, # 1 BTC in satoshis
    "script_pubkey": "76a914...88ac" # Pay to Dave
  }],
  "locktime": 0
}

Signature Generation:
tx_hash = SHA256(SHA256(transaction_for_signing))

Alice's signature:
sig_A = ECDSA_sign(priv_A, tx_hash) || 0x01 # SIGHASH_ALL
sig_A = 0x304402203e4516da7253cf068effec6b95c41221c0cf3a8e6ccb8cbf1725b562e9afde2c022054e1c258c2981cdfba5df64e841288edc1d6f1db6e18f8b4c2f3e9e9b4d8a6f01

Bob's signature:
sig_B = ECDSA_sign(priv_B, tx_hash) || 0x01 # SIGHASH_ALL
sig_B = 0x3045022100f2389c5b24a8b2f3e9e9b4d8a6f07c8d9e0f1a2b3c4d5e6f7a8b9c0d1e2f3a4b0220123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef01

ScriptSig Construction:
script_sig = OP_0 || sig_A || sig_B || redeem_script
script_sig = 0x00 || [sig_A] || [sig_B] || [redeem_script]

Verification Process:
1. Extract redeem_script from scriptSig
2. Verify script_hash matches P2SH address ✓
3. Execute redeem_script with remaining stack items:
   Stack: [OP_0, sig_A, sig_B]
   Script: [OP_2, pub_A, pub_B, pub_C, OP_3, OP_CHECKMULTISIG]
   
4. OP_CHECKMULTISIG verification:
   - Check sig_A against pub_A: ECDSA_verify(pub_A, tx_hash, sig_A) ✓
   - Check sig_B against pub_B: ECDSA_verify(pub_B, tx_hash, sig_B) ✓
   - Verify 2 valid signatures out of 3 ✓

Result: Transaction valid and funds transferred

### **Cold Storage**
**Brief Definition:** Cryptocurrency storage kept offline, providing enhanced security but reduced accessibility.

**Technical Definition:** Cold storage refers to keeping private keys on devices never connected to the internet, eliminating remote attack vectors. Implementation methods include: (1) Paper wallets: private keys printed or written on paper, (2) Hardware wallets: specialized devices with secure elements and air-gapped communication, (3) Air-gapped computers: dedicated offline machines for key generation and transaction signing. The security model assumes physical security of the storage medium and protection against side-channel attacks during limited online exposure for transaction broadcasting.

**Example:** Hardware wallet transaction signing process:

Cold Storage Setup (Hardware Wallet):
Device: Ledger/Trezor with secure element chip
Private keys: Stored in tamper-resistant hardware
Communication: USB/Bluetooth with limited, auditable protocol

Transaction Signing Workflow:

Step 1 - Online Computer (Hot Environment):
transaction_template = {
  "inputs": [{
    "prev_hash": "a1b2c3d4e5f6...",
    "prev_index": 0,
    "value": 100000000,  # 1 BTC
    "script_pubkey": "76a914...88ac"
  }],
  "outputs": [{
    "value": 95000000,   # 0.95 BTC to recipient
    "address": "1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2"
  }, {
    "value": 4900000,    # 0.049 BTC change
    "address": "1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa"
  }],
  "fee": 100000         # 0.001 BTC fee
}

Step 2 - Transfer to Hardware Wallet:
# Transaction sent via USB in structured format
# No private keys leave the hardware device

Step 3 - Hardware Wallet Processing:
# Device displays transaction details on secure screen
# User confirms: "Send 0.95 BTC to 1BvBM...N2? Fee: 0.001 BTC"
# User presses physical button to approve

Step 4 - Signing (Inside Secure Element):
# Derive private key for input using HD path m/44'/0'/0'/0/5
hd_path = [44 | 0x80000000, 0 | 0x80000000, 0 | 0x80000000, 0, 5]
private_key = derive_key(master_seed, hd_path)

# Create signature hash
tx_hash = SHA256(SHA256(transaction_for_signing))
signature = ECDSA_sign(private_key, tx_hash)

Step 5 - Return Signed Transaction:
signed_tx = {
  ...transaction_template,
  "inputs": [{
    ...input_data,
    "script_sig": signature + public_key  # scriptSig
  }]
}

Step 6 - Broadcast (Online Computer):
# Signed transaction broadcasted to Bitcoin network
# Private key never exposed to online environment

Security Benefits:
- Private keys never leave secure hardware
- Physical confirmation required for each transaction  
- Immune to software malware and remote attacks
- Tamper-resistant hardware protects against physical attacks
- PIN/passphrase protection against theft

Air Gap Verification:
QR Code Method:
Online PC → QR Code → Camera → Hardware Wallet → Sign → QR Code → Online PC
          Transaction        Display                     Signed TX

This maintains complete air gap while enabling transaction signing

---

## **Additional Important Terms**

### **Proof of Work**
**Brief Definition:** A consensus mechanism requiring participants to perform computational work to validate transactions and secure the network.

**Technical Definition:** Proof of Work is a cryptographic consensus algorithm where participants (miners) compete to find a nonce value that, when combined with block data, produces a hash with a specific number of leading zeros (difficulty target). The process involves computing SHA-256(SHA-256(block_header)) repeatedly with different nonce values until the result is below the target threshold. The probability of success per attempt is 1/difficulty, making the process a Poisson process with predictable average block times. The longest valid chain represents the consensus, as it demonstrates the most cumulative computational work.

**Example:** Bitcoin mining process:

Block Header Structure (80 bytes):
┌─────────────────┬─────────────────┬─────────────────┬─────────────────┐
│ Previous Hash   │ Merkle Root     │ Timestamp       │ Difficulty      │
│ (32 bytes)      │ (32 bytes)      │ (4 bytes)       │ (4 bytes)       │
├─────────────────┼─────────────────┼─────────────────┼─────────────────┤
│ Nonce           │ Version         │                 │                 │
│ (4 bytes)       │ (4 bytes)       │                 │                 │
└─────────────────┴─────────────────┴─────────────────┴─────────────────┘

Mining Process:
Target: 0x0000000000000000000696f4000000000000000000000000000000000000
(Approximately 19 leading zero bits for this difficulty)

Attempt 1:
nonce = 0
block_header = previous_hash || merkle_root || timestamp || difficulty || nonce || version
hash = SHA256(SHA256(block_header)) = 0x8b5c2a3d7f9e1b4c6a8d2f5e9c3a7b1d4f8e2a5c9b6d3f7a1e4c8b5f2d9e6a3c
Result: hash > target (too large, continue)

Attempt 2:
nonce = 1
hash = SHA256(SHA256(block_header)) = 0x3f7a1e4c8b5f2d9e6a3c7b1d4f8e2a5c9b6d3f7a1e4c8b5f2d9e6a3c8b5c2a3d
Result: hash > target (continue)

...

Attempt 2,083,236,893:
nonce = 2083236893
hash = SHA256(SHA256(block_header)) = 0x0000000000000000000435a2f7b8c3e9d1a4c8f5e2b7d6a3f8c1e5b2d9a6f4c7
Result: hash < target ✓ (VALID BLOCK FOUND!)

Network Verification:
1. Check hash ≤ target: 0x0000000000000000000435a2... ≤ 0x0000000000000000000696f4... ✓
2. Verify all transactions in block ✓
3. Check previous block hash exists ✓
4. Validate timestamp within acceptable range ✓

Mining Statistics:
- Current difficulty: ~36,835,682,546,788
- Average attempts needed: 36,835,682,546,788
- Network hash rate: ~450 EH/s (450 × 10^18 hashes/second)
- Average block time: 10 minutes (600 seconds)
- Energy consumption: ~150 TWh annually

Economic Incentives:
Block reward (as of 2024): 3.125 BTC + transaction fees
Mining cost: Electricity + hardware + operational expenses
Profitability = (block_reward × BTC_price) - mining_costs

### **51% Attack**
**Brief Definition:** A theoretical attack where a single entity controls more than half of the network's mining power, potentially allowing transaction manipulation.

**Technical Definition:** A 51% attack occurs when an adversary controls >50% of the network's total hash rate, enabling them to: (1) Create the longest chain consistently, (2) Double-spend transactions by creating conflicting chains, (3) Prevent specific transactions from confirming, (4) Reorganize recent blocks. However, the attacker cannot: steal coins from addresses they don't control, create coins from nothing, or modify old blocks without enormous computational cost. The attack's success probability follows P = (q/p)^(z+1) where q is attacker's hash rate, p is honest hash rate, and z is confirmation depth.

**Example:** 51% attack scenario and countermeasures:

Attack Scenario:
Network total hash rate: 450 EH/s
Attacker hash rate: 230 EH/s (51.1%)
Honest miners hash rate: 220 EH/s (48.9%)

Double Spend Attack:
Block Height: 800,000 (current)

Honest Chain:               Attacker's Secret Chain:
Block 800,000               Block 800,000
├─ Tx1: Attacker→Exchange   ├─ Tx1': Attacker→Self
├─ Tx2: Alice→Bob          ├─ Tx2: Alice→Bob
└─ Tx3: Carol→Dave         └─ Tx3: Carol→Dave

Block 800,001               Block 800,001
├─ Normal transactions     ├─ Secret mining...
                          
Block 800,002               Block 800,002
├─ Exchange→Attacker       ├─ Secret mining...
   (Fiat withdrawal)

Attack Execution:
1. Attacker sends Bitcoin to exchange (Tx1)
2. Exchange sees 6 confirmations, credits attacker's account
3. Attacker withdraws fiat currency
4. Attacker broadcasts longer secret chain with Tx1' (sends to self)
5. Network adopts longer chain, Tx1 becomes invalid
6. Attacker keeps both Bitcoin and fiat

Probability of Success:
For z confirmations, success probability ≈ e^(-λ) where λ = 0.1z
- 1 confirmation: ~90% success
- 3 confirmations: ~74% success  
- 6 confirmations: ~55% success
- 12 confirmations: ~30% success

Attack Costs (Conservative Estimate):
Hash rate acquisition: $15 billion (ASIC hardware)
Electricity costs: $50 million/day at $0.05/kWh
Opportunity cost: $15 million/day (lost legitimate mining rewards)
Total daily cost: ~$65 million

Economic Reality:
Maximum profitable theft: Must exceed daily costs ($65M)
Largest exchange holdings: ~$10-50 billion Bitcoin
Network effect: Attack would crash Bitcoin price
Rational attacker: More profitable to mine honestly long-term

Defense Mechanisms:
1. Confirmation requirements scaling with transaction value:
   - Small payments: 1-3 confirmations
   - Large payments: 6-12 confirmations
   - Exchange deposits: 3-6 confirmations

2. Network monitoring:
   - Hash rate distribution tracking
   - Unusual reorganization detection
   - Mining pool concentration alerts

3. Economic deterrents:
   - Mining hardware resale value drops if Bitcoin loses trust
   - Electricity contracts become unprofitable
   - Legal consequences for exchange theft

4. Protocol improvements:
   - Checkpointing for very old blocks
   - Finality gadgets (research area)
   - Multiple confirmation algorithms

Historical Cases:
- Ethereum Classic (2020): $1.1M double-spend, ~12% network control
- Bitcoin Gold (2018): $18M attack with rented hash power
- Vertcoin (2018): Multiple reorganizations with <10% of network cost

Bitcoin's Security:
Current impossibility factors:
- Hardware cost: ~$15-30 billion minimum investment
- Geographic distribution: miners across 100+ countries  
- Electricity requirements: 0.3% of global consumption
- Economic irrationality: attack destroys asset value

*Note: This glossary provides foundational and technical definitions with practical examples. Each concept represents critical knowledge for understanding Bitcoin's cryptographic security model and implementation details.*