📐 Bitcoin Algorithms

Proof of Work is like a digital lottery where buying tickets requires real computational energy.

Miners compete to find a special number (nonce) that makes the block hash start with many zeros. The only way to find it is to guess billions of times per second. When someone finds it, they prove they did the work, and the network rewards them with Bitcoin.

Proof of Work solves two critical problems in decentralized systems:

• 🛡️ Sybil Attack prevention: Without PoW, an attacker could create millions of fake nodes to overwhelm the network. PoW requires energy, not identities.
• ⏱️ Byzantine Generals Problem: How do distant nodes agree on the truth? PoW creates an objective measure (most work = truth).
• 💰 No free lunch: Creating blocks costs real money, so miners only produce valid blocks.

Miners collect pending transactions and build a block header. The header is exactly 80 bytes — no more, no less.

Miners calculate the double SHA-256 hash of the block header:

This produces a 256-bit number (64 hex characters).

def calculate_block_hash(version, prev_hash, merkle_root, timestamp, bits, nonce):
    # Assemble the 80-byte header
    header = (
        version.to_bytes(4, 'little') +
        bytes.fromhex(prev_hash) +
        bytes.fromhex(merkle_root) +
        timestamp.to_bytes(4, 'little') +
        bits.to_bytes(4, 'little') +
        nonce.to_bytes(4, 'little')
    )
    
    # Double SHA-256
    return hashlib.sha256(hashlib.sha256(header).digest()).hexdigest()

The target is a 256-bit number that determines how hard mining is. The block hash must be numerically lower than the target.

Miners increment the nonce (and extranonce) billions of times per second until they find a valid hash:

def mine_block(header, target):
    nonce = 0
    extranonce = 0
    
    while True:
        # Update extranonce in coinbase transaction
        # (changes the merkle root)
        header.update_coinbase(extranonce)
        header.update_merkle_root()
        
        # Try all 4 billion nonce values
        for nonce in range(2**32):
            header.nonce = nonce
            block_hash = calculate_block_hash(header)
            
            # Convert hash to integer for comparison
            hash_int = int(block_hash, 16)
            
            if hash_int < target:
                return header, block_hash
        
        # Exhausted 4 billion nonces, try a new extranonce
        extranonce += 1

Difficulty is a human-friendly number that represents how hard mining is relative to the first block in 2009.

When a miner finds a valid hash, they broadcast the block to the network. Other nodes verify the work (instantly — one hash calculation) and if valid, the miner receives:

Satoshi calculated the probability of an attacker catching up from z blocks behind:

If an attacker controls >50% of total hashrate, they can:

• ✅ Double-spend: Send coins to an exchange, then mine a longer chain without that transaction
• ✅ Censor transactions: Refuse to include specific transactions
• ✅ Prevent confirmations: Make the network unresponsive

They CANNOT:

• ❌ Steal existing coins (requires private keys)
• ❌ Create new coins (consensus rules prevent this)
• ❌ Change history beyond the reorganization window

Nakamoto Consensus is the rule that determines which version of the blockchain is the "true" history.

When different nodes see different blocks, they all follow the chain with the most cumulative Proof of Work — the chain that required the most energy to build. This creates an objective way to agree on truth without a central authority.

The Byzantine Generals Problem is a famous computer science dilemma that describes the difficulty of reaching consensus in a decentralized system where some participants may be malicious.

Nodes always follow the chain with the most cumulative Proof of Work — not necessarily the most blocks, but the chain that required the most total energy.

def get_best_chain(chains):
    best_chain = None
    max_work = 0
    
    for chain in chains:
        # Sum the difficulty of each block (Proof of Work)
        total_work = sum(block.difficulty for block in chain)
        
        if total_work > max_work:
            max_work = total_work
            best_chain = chain
    
    return best_chain

# Nodes always build on the best chain
def choose_best_chain(chain_a, chain_b):
    if get_total_work(chain_a) > get_total_work(chain_b):
        return chain_a
    return chain_b

Sometimes two miners find valid blocks at nearly the same time. This creates a temporary fork — two competing chains.

Each new block added on top of a transaction is called a confirmation. The more confirmations, the harder it is to reverse.

Nakamoto Consensus works because of economic incentives. Miners are rewarded for following the rules and penalized for breaking them.

Difficulty Adjustment is like a thermostat for Bitcoin mining — it automatically makes mining harder or easier to keep block times at 10 minutes.

As more miners join the network, blocks would be found faster than 10 minutes. The difficulty adjustment makes the puzzle harder, slowing blocks back down. When miners leave, it makes the puzzle easier, speeding blocks back up.

Without difficulty adjustment, block times would vary wildly as miners join or leave:

Every 2,016 blocks (~2 weeks), the network calculates:

def adjust_difficulty(old_difficulty, actual_time_seconds):
    expected_time = 2016 * 600  # 1,209,600 seconds
    
    # Calculate ratio (how much faster/slower blocks were found)
    ratio = actual_time_seconds / expected_time
    
    # Cap the ratio to prevent extreme changes (safety measure)
    # Max 4x harder, max 0.25x easier
    ratio = max(0.25, min(4.0, ratio))
    
    # Adjust difficulty
    new_difficulty = old_difficulty / ratio
    
    return new_difficulty

# Example 1: Blocks found too fast (600,000 seconds vs 1,209,600)
new_diff = adjust_difficulty(80_000_000_000, 600000)
print(f"New Difficulty: {new_diff:.0f}")  # ~160,000,000,000 (doubled!)

# Example 2: Blocks found too slow (1,800,000 seconds)
new_diff = adjust_difficulty(80_000_000_000, 1800000)
print(f"New Difficulty: {new_diff:.0f}")  # ~53,000,000,000 (reduced by ~34%)

Difficulty and Target are inversely related:

Satoshi chose 2,016 blocks because it's approximately 2 weeks at 10 minutes per block.

In 2017, Bitcoin's price surged from $1,000 to $20,000, causing massive miner entry. Hashrate increased rapidly.

A Merkle Tree is like a family tree of hashes — it summarizes many transactions into a single "root" hash.

Imagine you have 4 transactions. You hash each one (leaves). Then you hash pairs of leaves together (branches). Then you hash the branches together. You end up with one root hash that represents all 4 transactions.

                            [Merkle Root]
                           /            \
                      [Hash AB]        [Hash CD]
                     /       \        /       \
                 [TX1]      [TX2]  [TX3]      [TX4]

Merkle Trees enable two critical features in Bitcoin:

• 📦 Compact block headers: The block header stores only the Merkle Root (32 bytes), not all transactions. This keeps headers small (80 bytes).
• 📱 SPV wallets (mobile wallets): Your phone can verify a transaction exists using only a Merkle Proof (few hundred bytes) instead of downloading the entire block (1-4 MB).

Each transaction is hashed using double SHA-256 to create the leaves of the tree:

def hash_transaction(tx_data):
    # Double SHA-256 (Bitcoin standard)
    return hashlib.sha256(hashlib.sha256(tx_data).digest()).hexdigest()

tx1_hash = hash_transaction(b"Alice pays Bob 1 BTC")
tx2_hash = hash_transaction(b"Charlie pays Dave 2 BTC")
tx3_hash = hash_transaction(b"Eve pays Frank 0.5 BTC")
tx4_hash = hash_transaction(b"Grace pays Henry 0.75 BTC")

leaves = [tx1_hash, tx2_hash, tx3_hash, tx4_hash]

Pairs of adjacent leaves are concatenated and hashed to form parent nodes:

def hash_pair(hash_a, hash_b):
    # Concatenate and double hash
    combined = hash_a + hash_b
    return hashlib.sha256(hashlib.sha256(combined.encode()).digest()).hexdigest()

hash_ab = hash_pair(leaves[0], leaves[1])
hash_cd = hash_pair(leaves[2], leaves[3])

The process continues until only one hash remains — the Merkle Root:

def build_merkle_root(hashes):
    """Build a Merkle tree and return the root"""
    if len(hashes) == 1:
        return hashes[0]
    
    next_level = []
    for i in range(0, len(hashes), 2):
        if i + 1 < len(hashes):
            combined = hashes[i] + hashes[i+1]
        else:
            # Odd number of items — duplicate the last one
            combined = hashes[i] + hashes[i]
        next_level.append(hash_pair(combined))
    
    return build_merkle_root(next_level)

# Build the full tree
merkle_root = build_merkle_root(leaves)
print(f"Merkle Root: {merkle_root}")

A Merkle Proof is like a "receipt" that proves a specific transaction is in a block without downloading the entire block.

It contains the target transaction hash and the "sibling" hashes needed to recompute the Merkle Root. If the recomputed root matches the block header's root, the transaction is proven to be in that block.

Merkle Proofs enable SPV (Simplified Payment Verification) wallets — mobile wallets that don't download the full blockchain.

• 📱 Mobile wallets: Your phone stores only block headers (80 bytes each). When you receive a payment, you request a Merkle Proof from a full node.
• 🔒 Trust-minimized verification: You don't need to trust the full node — the math proves the transaction exists.
• ⚡ Fast sync: Your wallet can verify payments in seconds instead of downloading years of history.

To prove TX₃ is in the block, you only need:

def verify_merkle_proof(tx_hash, proof, merkle_root):
    """
    tx_hash: The transaction hash to verify
    proof: List of (sibling_hash, direction) tuples
    merkle_root: The root from the block header
    """
    current_hash = tx_hash
    
    for sibling, direction in proof:
        if direction == 'left':
            # Sibling is on the left: Hash(Sibling + Current)
            current_hash = hash_pair(sibling, current_hash)
        else:
            # Sibling is on the right: Hash(Current + Sibling)
            current_hash = hash_pair(current_hash, sibling)
    
    return current_hash == merkle_root

# Example proof for TX₃
tx_hash = "hash_of_TX3"
proof = [
    ("hash_of_TX4", "right"),   # sibling of TX3
    ("hash_of_AB", "left")       # sibling of parent
]
merkle_root = "root_from_header"

is_valid = verify_merkle_proof(tx_hash, proof, merkle_root)
print(f"Transaction verified: {is_valid}")

Base58Check is a way to encode Bitcoin addresses so they're easy to read, hard to mistype, and include error detection.

It removes visually confusing characters (0, O, I, l) and adds a checksum that catches typos before you send money to the wrong address.

Bitcoin addresses are binary data (20 bytes + version + checksum). Base58Check converts this binary into a human-readable string that:

• 📝 Is easy to read and share (no confusing characters)
• ✅ Has built-in error detection (catches typos)
• 🔢 Is shorter than hex (34 chars vs 40 hex chars)
• 🔒 Self-validating (invalid addresses are rejected by wallets)

Base58 works like converting a number to a different base (base-58 instead of base-10 or base-16).

ALPHABET = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'

def base58_encode(data):
    """Encode bytes to Base58 string"""
    # Convert bytes to a big integer
    value = int.from_bytes(data, 'big')
    
    encoded = ''
    while value > 0:
        value, remainder = divmod(value, 58)
        encoded = ALPHABET[remainder] + encoded
    
    # Add leading '1's for each leading zero byte
    for byte in data:
        if byte == 0:
            encoded = '1' + encoded
        else:
            break
    
    return encoded

# Example: Encode the number 100
print(base58_encode(b'\x64'))  # '2q' (100 in base-58)

Base58Check adds a 4-byte checksum to the end of the payload:

def base58check_encode(payload):
    # Step 1: Add version byte (0x00 for Bitcoin mainnet)
    versioned = b'\x00' + payload
    
    # Step 2: Calculate checksum (first 4 bytes of double SHA-256)
    checksum = hashlib.sha256(hashlib.sha256(versioned).digest()).digest()[:4]
    
    # Step 3: Append checksum and Base58 encode
    return base58_encode(versioned + checksum)

# Example: Creating a Bitcoin address
public_key_hash = bytes.fromhex('62e907b15cbf27d5425399ebf6f0fb50ebb88f18')
address = base58check_encode(public_key_hash)
print(f"Address: {address}")  # 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa

Bech32 is a modern address format for Bitcoin that's all lowercase, easier to read, and can actually correct typos.

Unlike Base58Check (which only detects errors), Bech32 uses a special error-correcting code that can fix typos automatically. Bech32 addresses start with "bc1" for Bitcoin mainnet.

Bech32 was introduced with SegWit (Segregated Witness) to support native SegWit addresses with several advantages:

• 🔧 Error correction: Can detect up to 4 errors and correct up to 3
• 🔤 All lowercase: Easier to read, type, and QR code
• 💰 Lower fees: Native SegWit addresses are more efficient (smaller transaction size)
• 📏 No ambiguous characters: Like Base58Check, removes confusing letters
• ✅ Better checksum: BCH code detects more errors than Base58Check

A Bech32 address has three distinct parts:

Bech32 uses a BCH (Bose-Chaudhuri-Hocquenghem) code — a powerful error-correcting code that can:

# Example: Typo correction in Bech32
# Original: bc1qar0srrr7xfkvy5l643lydnw9re59gtzzwf5mdq
# Typo:     bc1qar0srrr7xfkvy5l643lydnw9re59gtzzwf5m**dq** (swapped last two chars)
# Wallet can automatically correct this! (Base58Check would just say "invalid")

Bech32 uses a 5-bit alphabet (32 possible characters), but data is normally 8-bit bytes. So Bech32 converts 8-bit bytes to 5-bit groups.

# Bech32 alphabet (32 characters)
BECH32_ALPHABET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"

def convert_bits(data, from_bits, to_bits, pad=True):
    """Convert between bit lengths (e.g., 8-bit bytes to 5-bit groups)"""
    acc = 0
    bits = 0
    ret = []
    maxv = (1 << to_bits) - 1
    max_acc = (1 << (from_bits + to_bits - 1)) - 1
    
    for value in data:
        acc = ((acc << from_bits) | value) & max_acc
        bits += from_bits
        while bits >= to_bits:
            bits -= to_bits
            ret.append((acc >> bits) & maxv)
    
    if pad and bits:
        ret.append((acc << (to_bits - bits)) & maxv)
    
    return ret

# Convert witness program (20 bytes) to 5-bit groups
witness_program = bytes.fromhex('62e907b15cbf27d5425399ebf6f0fb50ebb88f18')
five_bit_data = convert_bits(witness_program, 8, 5, pad=True)

Bech32 was specifically designed for SegWit (Segregated Witness) addresses. SegWit separates transaction signatures (witness data) from transaction data, which:

• 💰 Lowers fees: Witness data is discounted (0.75 bytes per byte)
• 🔧 Fixes malleability: Transaction IDs no longer include signatures
• ⚡ Enables Lightning: Malleability fix made Lightning possible

# Fee comparison (example)
Legacy address (P2PKH):   1 input, 2 outputs → 192 vbytes → fee: 192 × 10 = 1920 sats
SegWit address (Bech32):  1 input, 2 outputs → 144 vbytes → fee: 144 × 10 = 1440 sats
# Savings: 25% lower fees!

Bech32m is a modified version of Bech32 used for Taproot addresses (bc1p...). It fixes a security issue where some Bech32 addresses could be confused with short data.

Gossip Protocol is how Bitcoin nodes spread information — like a rumor spreading through a crowd.

When a node hears a new transaction, it tells its neighbors. Those neighbors tell their neighbors, and within seconds, every node in the world knows about it. There's no central broadcaster — information spreads peer-to-peer.

Without a central server, Bitcoin needs a way for all nodes to learn about new transactions and blocks. Gossip Protocol solves this:

• 🌐 No central point of failure: If a node goes down, information routes around it
• ⚡ Fast propagation: Information reaches 90% of nodes in 1-2 seconds
• 🛡️ Resilient to attacks: Even if some nodes are malicious, honest nodes still communicate
• 📈 Scalable: Works with thousands of nodes

Each Bitcoin node connects to 8-12 random peers. This creates a mesh network where information can spread quickly.

class BitcoinNode:
    def __init__(self):
        self.peers = []  # List of connected nodes
        self.seen_transactions = set()  # Avoid infinite loops
        self.mempool = []  # Unconfirmed transactions
    
    def add_peer(self, peer):
        self.peers.append(peer)
        peer.peers.append(self)  # Bidirectional connection
    
    def broadcast_transaction(self, tx):
        # Prevent infinite loops
        if tx.id in self.seen_transactions:
            return
        
        self.seen_transactions.add(tx.id)
        self.mempool.append(tx)
        
        # Tell all peers about the transaction
        for peer in self.peers:
            peer.receive_transaction_inv(tx.id)
    
    def receive_transaction_inv(self, tx_id):
        # Request the full transaction if we don't have it
        if tx_id not in self.seen_transactions:
            self.request_transaction(tx_id)

Nodes don't broadcast full transactions immediately. They first send an INV (inventory) message containing just transaction hashes (32 bytes each).

# INV message example
inv_message = {
    "type": "inv",
    "inventory": [
        "f4184fc596403b9d638783cf57adfe4c75c605f6356fbc91338530e9831e9e16",
        "4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b"
    ]
}

# Peer responds with GETDATA for transactions they don't have
if tx_id not in local_mempool:
    send_message("getdata", tx_id)

To prevent spam and denial-of-service attacks, nodes follow strict rules:

• 🔍 Validation first: Don't relay transactions you haven't validated
• 🛑 Stop bad rumors: Don't relay invalid transactions (ban the source)
• 🚦 Rate limiting: Limit how many messages a peer can send
• ⚠️ Ban malicious peers: Disconnect and ban peers sending invalid data

Compact Block Relay is like sending only the "missing pieces" of a puzzle instead of the whole puzzle.

Most nodes already have most transactions in their mempool. Instead of sending the full block (1-4 MB), nodes send only the short IDs of transactions. The receiving node reconstructs the block using transactions it already has, requesting only the few it's missing.

Before BIP152 (2017), nodes had to download full blocks from peers. This caused problems:

• 📡 Bandwidth waste: Blocks contain 90%+ transactions already in mempool
• ⏱️ Slow propagation: Large blocks took seconds to transfer, increasing orphan rates
• 🌍 Centralization risk: Only large nodes could afford the bandwidth

Instead of sending full 32-byte TXIDs, compact blocks use 6-byte short IDs (48 bits).

def make_short_id(tx_hash, nonce):
    """
    Create a 6-byte short ID using SipHash
    SipHash is fast, non-cryptographic, and collision-resistant
    """
    import siphash
    
    # SipHash with 64-bit output
    sip = siphash.SipHash_2_4(key=nonce.to_bytes(16, 'little'))
    sip.update(tx_hash)
    
    # Take lowest 48 bits (6 bytes)
    return sip.raw_value() & 0xffffffffffff

# Collision probability: ~1 in 2⁴⁸ (very low, safe for Bitcoin)

# Sender side (miner)
compact_block = {
    'header': block_header,
    'short_ids': [make_short_id(tx) for tx in block.transactions],
    'prefilled_txns': []  # Transactions not in most peers' mempool
}

# Receiver side (node)
def reconstruct_block(compact_block, mempool):
    transactions = []
    missing = []
    
    # Try to find each transaction in mempool using short ID
    for short_id in compact_block.short_ids:
        tx = find_tx_by_short_id(mempool, short_id)
        if tx:
            transactions.append(tx)
        else:
            missing.append(short_id)
    
    # Request missing transactions (should be very few)
    if missing:
        requested_txs = request_missing(missing)
        transactions.extend(requested_txs)
    
    # Reconstruct full block
    return Block(compact_block.header, transactions)

UTXO Selection is how your wallet decides which coins (UTXOs) to spend when you make a payment.

Your wallet has many UTXOs of different sizes (like having a $10 bill, a $5 bill, and three $1 bills). To pay $7, you could use the $5 + two $1 bills (3 inputs) or the $10 bill (1 input but you get $3 change). The algorithm chooses the best combination.

Unlike a bank account (single balance), Bitcoin uses UTXOs — many individual "coins" of different values. Your wallet must decide which ones to spend:

• 💰 Fee optimization: More inputs = larger transaction = higher fees
• 🔒 Privacy: Using certain UTXOs can reveal your transaction history
• 🧹 Dust management: Small UTXOs ("dust") may cost more to spend than they're worth
• ⚡ Speed: More inputs = more signatures = slower to sign

Modern wallets (Bitcoin Core, Electrum) use Branch and Bound for optimal selection:

def select_utxos_bnb(utxos, target, fee_rate):
    """
    Branch and Bound coin selection
    Finds the optimal UTXO set minimizing waste
    """
    # Sort by value (largest first for efficiency)
    utxos = sorted(utxos, key=lambda x: x.value, reverse=True)
    
    best_selection = None
    best_waste = float('inf')
    
    def search(selected, selected_value, effective_value, index):
        nonlocal best_selection, best_waste
        
        # Calculate waste (excess value + fees)
        waste = (selected_value - target) + fee_rate * len(selected)
        
        # Prune branches that can't be better
        if waste < 0 or waste >= best_waste:
            return  # This path is useless, don't explore further
        
        # Found a solution
        if selected_value >= target:
            if waste < best_waste:
                best_waste = waste
                best_selection = selected.copy()
            return
        
        # No more UTXOs to consider
        if index >= len(utxos):
            return
        
        # Branch 1: Include this UTXO
        selected.append(utxos[index])
        search(selected, 
               selected_value + utxos[index].value,
               effective_value + utxos[index].effective_value, 
               index + 1)
        selected.pop()
        
        # Branch 2: Skip this UTXO
        search(selected, selected_value, effective_value, index + 1)
    
    search([], 0, 0, 0)
    return best_selection

Fee Estimation predicts how much you should pay to get your transaction confirmed within a certain time.

Your wallet looks at the current mempool (unconfirmed transactions), analyzes how long transactions with different fees took to confirm recently, and recommends a fee rate (satoshis per vbyte) that will likely get your transaction into a block soon.

Bitcoin has limited block space (1-4 MB per block). When many people want to send transactions, they compete by offering higher fees. Fee estimation helps users:

• ⏱️ Avoid overpaying: Don't pay high fees when network is quiet
• ⚡ Avoid delays: Don't pay too little when network is congested
• 💰 Optimize costs: Balance speed vs. cost based on your needs

All unconfirmed transactions sit in the mempool (memory pool) — a waiting room for transactions waiting to be mined. Miners pick the highest-fee transactions first.

class FeeEstimator:
    def __init__(self):
        self.fee_history = []  # Recent blocks' fee rates
    
    def estimate_fee(self, target_blocks):
        """
        Estimate fee rate for target confirmation time
        target_blocks: 1 = fastest, 6 = standard, 25+ = slowest
        """
        # Collect fee rates from recent blocks
        fee_rates = []
        for block in self.recent_blocks(100):
            # Get minimum fee rate that would have been included in this block
            min_fee = block.get_minimum_included_fee()
            fee_rates.append(min_fee)
        
        # Sort and pick percentile based on target
        fee_rates.sort()
        
        # Faster targets require higher percentiles
        if target_blocks == 1:
            percentile = 90  # Fastest (90th percentile)
        elif target_blocks <= 3:
            percentile = 75  # Medium (75th percentile)
        elif target_blocks <= 6:
            percentile = 50  # Standard (50th percentile)
        else:
            percentile = 25  # Slow (25th percentile)
        
        # Return the fee rate at that percentile
        index = int(len(fee_rates) * percentile / 100)
        return fee_rates[index]

A more accurate method uses the current mempool state directly:

def estimate_from_mempool(mempool, target_blocks):
    """
    Estimate fee by simulating block inclusion from current mempool
    """
    # Sort mempool by fee rate (highest first)
    sorted_txs = sorted(mempool, key=lambda x: x.fee_rate, reverse=True)
    
    block_size = 0
    for tx in sorted_txs:
        block_size += tx.vsize
        # When we've filled enough blocks, return the fee rate
        if block_size >= target_blocks * 1_000_000:  # 1 MB per block
            return tx.fee_rate
    
    # If mempool is empty, return minimum fee
    return 1  # 1 sat/vbyte minimum

If your fee estimate was too low, you have two options to speed up a stuck transaction:

# RBF example: Bump fee from 10 to 50 sat/vB
original_tx.fee_rate = 10
bumped_tx = replace_transaction(original_tx, new_fee_rate=50)

# CPFP example: Parent stuck at 5 sat/vB
parent_tx.fee_rate = 5
child_tx = create_child_transaction(parent_tx, child_fee_rate=100)
# Miners see: parent(5) + child(100) = average 52.5 sat/vB → includes both!