Appendix D: Cryptographic Primitives Quick Reference

This appendix is a working reference, not a tutorial. It provides the parameters, properties, and code snippets for the cryptographic primitives used in blockchain systems. For conceptual explanations, see Chapters 2 and 3. For rigorous mathematical treatment, see the references in each chapter's Further Reading section.

D.1 Hash Functions

SHA-256

Used by: Bitcoin (block hashing, transaction IDs, Merkle trees, address derivation).

Python usage:

import hashlib

# Single hash
data = b"Hello, blockchain"
digest = hashlib.sha256(data).hexdigest()
# '7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069'

# Double hash (Bitcoin convention for block headers, txids)
double = hashlib.sha256(hashlib.sha256(data).digest()).hexdigest()

# Hash with concatenation (Merkle tree nodes)
left = bytes.fromhex("aabb...")
right = bytes.fromhex("ccdd...")
parent = hashlib.sha256(left + right).hexdigest()

Bitcoin block header hashing:

import struct

def hash_block_header(version, prev_hash, merkle_root, timestamp, bits, nonce):
    """Hash a Bitcoin block header (double SHA-256, little-endian)."""
    header = struct.pack("<I", version)
    header += bytes.fromhex(prev_hash)[::-1]     # Reverse byte order
    header += bytes.fromhex(merkle_root)[::-1]
    header += struct.pack("<I", timestamp)
    header += struct.pack("<I", bits)
    header += struct.pack("<I", nonce)
    return hashlib.sha256(hashlib.sha256(header).digest()).digest()[::-1].hex()

Keccak-256

Used by: Ethereum (address derivation, state trie, function selectors, event topics).

Critical Distinction: Python's hashlib.sha3_256 implements NIST SHA-3, which produces different output from Ethereum's Keccak-256. Use web3.py or pysha3 for Ethereum-compatible hashing.

Python usage:

from web3 import Web3

# Keccak-256 (Ethereum-compatible)
digest = Web3.keccak(text="Hello, blockchain").hex()

# From bytes
digest = Web3.keccak(b"\x01\x02\x03").hex()

# From hex string
digest = Web3.keccak(hexstr="0x0102030405").hex()

Solidity usage:

// Keccak-256 in Solidity
bytes32 hash = keccak256(abi.encodePacked("Hello, blockchain"));

// Hash multiple values (packed encoding)
bytes32 hash = keccak256(abi.encodePacked(addr, amount, nonce));

// Hash multiple values (standard ABI encoding, preferred for structs)
bytes32 hash = keccak256(abi.encode(addr, amount, nonce));

Comparison Table

D.2 ECDSA on secp256k1

The Elliptic Curve Digital Signature Algorithm on the secp256k1 curve is the signature scheme for both Bitcoin and Ethereum.

Curve Parameters

Key Generation

1. Generate a random 256-bit integer k where 1 < k < n.
2. Compute the public key: K = k * G (elliptic curve point multiplication).
3. The private key is k (a 32-byte integer).
4. The public key is K (a 64-byte uncompressed point, or 33-byte compressed).

Python (ecdsa library):

from ecdsa import SigningKey, SECP256k1

# Generate key pair
private_key = SigningKey.generate(curve=SECP256k1)
public_key = private_key.get_verifying_key()

# Export
private_hex = private_key.to_string().hex()       # 32 bytes -> 64 hex chars
public_hex = public_key.to_string().hex()          # 64 bytes -> 128 hex chars (uncompressed, no prefix)
public_compressed = public_key.to_string("compressed").hex()  # 33 bytes

# From existing private key
private_key = SigningKey.from_string(bytes.fromhex(private_hex), curve=SECP256k1)

Python (eth-account for Ethereum):

from eth_account import Account

# Generate new account
acct = Account.create()
print(f"Address:     {acct.address}")
print(f"Private key: {acct.key.hex()}")

# From existing private key
acct = Account.from_key("0xYourPrivateKeyHex")

Signing

The ECDSA signature for message hash z:

1. Choose random nonce r_k where 1 < r_k < n.
2. Compute R = r_k * G, and let r = R.x mod n.
3. Compute s = r_k^(-1) * (z + r * k) mod n.
4. The signature is (r, s).

Python signing:

from ecdsa import SigningKey, SECP256k1
import hashlib

private_key = SigningKey.generate(curve=SECP256k1)

# Sign a message (automatically hashes with SHA-256)
message = b"Transfer 1.5 BTC to Alice"
signature = private_key.sign(message, hashfunc=hashlib.sha256)
# signature is 64 bytes: r (32 bytes) || s (32 bytes)

Ethereum transaction signing:

from eth_account import Account
from web3 import Web3

w3 = Web3(Web3.HTTPProvider("http://127.0.0.1:8545"))
acct = Account.from_key("0xYourPrivateKey")

tx = {
    "nonce": w3.eth.get_transaction_count(acct.address),
    "to": "0xRecipientAddress",
    "value": w3.to_wei(0.1, "ether"),
    "gas": 21000,
    "maxFeePerGas": w3.to_wei(30, "gwei"),
    "maxPriorityFeePerGas": w3.to_wei(2, "gwei"),
    "chainId": 11155111,  # Sepolia
}

signed = acct.sign_transaction(tx)
tx_hash = w3.eth.send_raw_transaction(signed.raw_transaction)

Verification

1. Recover the point R from r and the recovery id v.
2. Compute u1 = z * s^(-1) mod n and u2 = r * s^(-1) mod n.
3. Compute P = u1 * G + u2 * K.
4. The signature is valid if P.x mod n == r.

Python verification:

public_key = private_key.get_verifying_key()

try:
    public_key.verify(signature, message, hashfunc=hashlib.sha256)
    print("Signature is valid")
except Exception:
    print("Signature is INVALID")

Address Derivation

Bitcoin (P2PKH):

1. public_key_bytes (33 or 65 bytes)
2. SHA-256(public_key_bytes)
3. RIPEMD-160(step 2)               -> 20-byte hash
4. Prepend version byte (0x00 mainnet, 0x6f testnet)
5. Double SHA-256 of step 4          -> checksum (first 4 bytes)
6. Base58Check(step 4 + checksum)    -> Bitcoin address (e.g., 1A1zP1...)

Ethereum:

1. public_key_bytes (64 bytes, uncompressed, no 0x04 prefix)
2. Keccak-256(public_key_bytes)      -> 32 bytes
3. Take last 20 bytes               -> Ethereum address
4. Prepend "0x"
5. Apply EIP-55 checksum (mixed-case encoding)

Python (Ethereum address):

from web3 import Web3
from eth_account import Account

acct = Account.create()
address = acct.address  # Checksummed: '0x5B38Da6a...'

# Verify checksum
assert Web3.is_checksum_address(address)

D.3 Schnorr Signatures

Schnorr signatures, activated on Bitcoin via the Taproot upgrade (BIP 340, November 2021), offer several advantages over ECDSA: provable security, linearity (enabling key and signature aggregation), and slightly smaller signatures.

Properties

Signing (BIP 340)

1. Nonce k is derived deterministically from the private key and message.
2. Compute R = k * G. If R.y is odd, negate k.
3. Compute challenge e = tagged_hash("BIP0340/challenge", R.x || P.x || m).
4. Compute s = k + e * d mod n (where d is the private key).
5. Signature: (R.x, s) — 64 bytes total.

Key Aggregation (MuSig2)

Schnorr's linearity enables n-of-n multisignature schemes that produce a single signature indistinguishable from a regular signature:

1. Each participant generates a public key P_i.
2. The aggregate key is computed as P_agg = sum(a_i * P_i) where a_i are challenge coefficients.
3. During signing, each participant produces a partial signature.
4. Partial signatures are combined into a single 64-byte signature.
5. The verifier sees only one public key and one signature (privacy and efficiency).

Taproot Integration

Taproot (BIP 341) uses Schnorr signatures to create a Merkelized Alternative Script Tree (MAST):

• Key path spend: A single Schnorr signature spends the output, revealing nothing about alternative spending conditions.
• Script path spend: If the key path fails, a Merkle proof reveals one script from the MAST, along with a script satisfaction.
• Result: Complex multisig and conditional transactions look identical to simple single-key spends on-chain.

D.4 Merkle Trees

Construction

A Merkle tree is a binary hash tree where:

• Each leaf is the hash of a data element (transaction).
• Each internal node is the hash of the concatenation of its two children.
• If the number of leaves is odd, the last leaf is duplicated.

        Merkle Root
       /            \
    H(AB)          H(CD)
   /     \        /     \
 H(A)   H(B)   H(C)   H(D)
  |       |       |       |
 Tx A   Tx B    Tx C    Tx D

Python implementation:

import hashlib

def sha256d(data: bytes) -> bytes:
    """Double SHA-256 (Bitcoin convention)."""
    return hashlib.sha256(hashlib.sha256(data).digest()).digest()

def build_merkle_root(tx_hashes: list[bytes]) -> bytes:
    """Build a Merkle root from a list of transaction hashes."""
    if len(tx_hashes) == 0:
        return b'\x00' * 32
    if len(tx_hashes) == 1:
        return tx_hashes[0]

    level = list(tx_hashes)
    while len(level) > 1:
        if len(level) % 2 == 1:
            level.append(level[-1])  # Duplicate last element if odd
        next_level = []
        for i in range(0, len(level), 2):
            parent = sha256d(level[i] + level[i + 1])
            next_level.append(parent)
        level = next_level
    return level[0]

Proof Generation and Verification

A Merkle proof for a leaf consists of the sibling hashes along the path from the leaf to the root. Proof size is O(log n).

def generate_merkle_proof(tx_hashes: list[bytes], index: int) -> list[tuple[bytes, str]]:
    """Generate a Merkle proof for the transaction at the given index.
    Returns a list of (hash, direction) tuples where direction is 'L' or 'R'.
    """
    proof = []
    level = list(tx_hashes)

    while len(level) > 1:
        if len(level) % 2 == 1:
            level.append(level[-1])

        next_level = []
        for i in range(0, len(level), 2):
            next_level.append(sha256d(level[i] + level[i + 1]))
            if i == index or i + 1 == index:
                if index % 2 == 0:
                    proof.append((level[i + 1], "R"))
                else:
                    proof.append((level[i], "L"))

        index = index // 2
        level = next_level

    return proof

def verify_merkle_proof(tx_hash: bytes, proof: list[tuple[bytes, str]], root: bytes) -> bool:
    """Verify a Merkle proof against a known root."""
    current = tx_hash
    for sibling, direction in proof:
        if direction == "L":
            current = sha256d(sibling + current)
        else:
            current = sha256d(current + sibling)
    return current == root

Use Cases in Blockchain

D.5 BIP-39 Mnemonic Phrase

BIP-39 defines the standard for encoding wallet seeds as human-readable word sequences.

Generation Process

1. Generate 128-256 bits of entropy (128 = 12 words, 256 = 24 words)
2. Compute SHA-256(entropy)
3. Take first (entropy_bits / 32) bits of the hash as checksum
4. Concatenate entropy + checksum
5. Split into 11-bit groups
6. Map each 11-bit value to a word in the 2048-word BIP-39 wordlist

Seed Derivation

The mnemonic is converted to a 512-bit seed using PBKDF2-HMAC-SHA512:

seed = PBKDF2(
    password = mnemonic_sentence (space-separated words, UTF-8 NFKD normalized),
    salt     = "mnemonic" + optional_passphrase,
    iterations = 2048,
    key_length = 64 bytes
)

The passphrase (sometimes called the "25th word") provides an additional layer of protection. Different passphrases produce completely different seeds from the same mnemonic.

Key Derivation (BIP-32 / BIP-44)

From the 512-bit seed, a hierarchical deterministic (HD) wallet derives keys using a tree structure:

m / purpose' / coin_type' / account' / change / address_index

Examples:
m/44'/0'/0'/0/0     First Bitcoin receiving address
m/44'/0'/0'/1/0     First Bitcoin change address
m/44'/60'/0'/0/0    First Ethereum address
m/84'/0'/0'/0/0     First Bitcoin native SegWit address

The apostrophe (') indicates hardened derivation, which prevents child key compromise from revealing the parent key.

Python (reference only, do not use for real funds):

import hashlib
import hmac

def mnemonic_to_seed(mnemonic: str, passphrase: str = "") -> bytes:
    """Convert a BIP-39 mnemonic to a 512-bit seed."""
    password = mnemonic.encode("utf-8")
    salt = ("mnemonic" + passphrase).encode("utf-8")
    return hashlib.pbkdf2_hmac("sha512", password, salt, 2048, dklen=64)

Security Warning: Never generate real wallet mnemonics in Python scripts. Use hardware wallets or audited wallet software for any funds you cannot afford to lose.

D.6 ABI Encoding

The Application Binary Interface defines how data is encoded for Ethereum smart contract interactions. Understanding ABI encoding is essential for constructing raw transactions, verifying calldata, and debugging contract interactions.

Function Selectors

A function selector is the first 4 bytes of the Keccak-256 hash of the function signature:

from web3 import Web3

# Function selector for transfer(address,uint256)
sig = "transfer(address,uint256)"
selector = Web3.keccak(text=sig)[:4].hex()
# '0xa9059cbb'

# Common selectors
# transfer(address,uint256)        -> 0xa9059cbb
# approve(address,uint256)         -> 0x095ea7b3
# balanceOf(address)               -> 0x70a08231
# totalSupply()                    -> 0x18160ddd
# transferFrom(address,address,uint256) -> 0x23b872dd

Solidity:

bytes4 selector = bytes4(keccak256("transfer(address,uint256)"));
// 0xa9059cbb

Parameter Types and Encoding

ABI encoding uses 32-byte (256-bit) slots. Types are categorized as static or dynamic:

Encoding Examples

Python (eth-abi):

from eth_abi import encode

# Encode a transfer(address, uint256) call
params = encode(
    ["address", "uint256"],
    ["0x5B38Da6a701c568545dCfcB03FcB875f56beddC4", 1000000]
)
# Result: 64 bytes of ABI-encoded parameters

# Full calldata = selector + encoded parameters
selector = bytes.fromhex("a9059cbb")
calldata = selector + params

Python (web3.py contract interface):

from web3 import Web3

w3 = Web3(Web3.HTTPProvider("http://127.0.0.1:8545"))

# Using contract ABI (preferred)
contract = w3.eth.contract(address=token_address, abi=token_abi)
calldata = contract.encodeABI(fn_name="transfer", args=[recipient, amount])

# Decoding return data
result = contract.functions.balanceOf(address).call()

ABI Encoding Rules

1. Static types are encoded in-place in the order they appear.
2. Dynamic types are encoded as a 32-byte offset pointing to the data section, followed by the actual data appended after all static parameters.
3. Arrays are encoded as length (uint256) followed by elements.
4. Strings are encoded as length (uint256) followed by UTF-8 bytes, right-padded.

Example: encoding transfer(address,uint256) with address 0xABC... and amount 1000:

0xa9059cbb                                                       # Function selector
000000000000000000000000ABC0000000000000000000000000000000000000   # address (left-padded)
00000000000000000000000000000000000000000000000000000000000003e8   # uint256 1000

Event Log Encoding

Events use a different encoding scheme:

• Topic 0: Keccak-256 hash of the event signature (unless the event is anonymous).
• Indexed parameters: Stored as additional topics (max 3 indexed parameters). Dynamic types are stored as their Keccak-256 hash.
• Non-indexed parameters: ABI-encoded in the data field.

// Event definition
event Transfer(address indexed from, address indexed to, uint256 value);

// When emitted:
// topic[0] = keccak256("Transfer(address,address,uint256)")
// topic[1] = from address (left-padded to 32 bytes)
// topic[2] = to address (left-padded to 32 bytes)
// data     = ABI-encoded uint256 value

Python (decoding logs with web3.py):

# Get Transfer events
transfer_filter = contract.events.Transfer.create_filter(
    from_block="latest",
    argument_filters={"from": sender_address}
)
events = transfer_filter.get_all_entries()

for event in events:
    print(f"From: {event.args['from']}")
    print(f"To: {event.args['to']}")
    print(f"Value: {event.args['value']}")

Packed Encoding vs. Standard Encoding

Solidity offers two encoding modes:

This reference covers the cryptographic building blocks that underpin every blockchain system discussed in this textbook. For implementation details in specific contexts, consult the chapter indicated in each section.