7 min read
On this page

Blockchain Cryptography

Hash Chains

A hash chain is a sequence where each element is the hash of the previous: h_i = H(h_{i-1}). The chain is computed forward but verification works backward (given any element, apply H to verify subsequent elements).

Applications:

  • Lamport's one-time passwords: Precompute chain h_0, h_1, ..., h_n. Reveal h_n first, then h_{n-1}, etc. Each password is verified by hashing once and comparing to the previous.
  • Blockchain linking: Each block includes H(previous_block_header), creating a tamper-evident chain. Modifying any block invalidates all subsequent blocks.
  • Timelock puzzles: Sequential hashing as a proof-of-sequential-work.

Merkle Trees

Binary hash trees enabling efficient and authenticated data structures.

Construction: Leaf nodes contain H(data_i). Internal nodes contain H(left_child || right_child). The root is a single hash committing to all data.

Membership proof (Merkle proof): To prove data_i is in the tree, provide the sibling hashes along the path from leaf to root. Verifier recomputes the root using O(log n) hashes. Proof size: O(log n) hashes.

Applications in blockchain:

  • Transaction Merkle tree: Block header contains the Merkle root of all transactions. SPV (Simplified Payment Verification) clients verify transaction inclusion without downloading the full block.
  • State trie (Ethereum): Modified Merkle-Patricia trie storing account states. Enables succinct proofs that an account has a particular balance/nonce/code.
  • Merkle Mountain Range (MMR): Append-only Merkle structure for efficiently proving membership in a growing set.

Sparse Merkle trees: Tree of depth 256 (for SHA-256), mostly empty. Efficient non-membership proofs. Used in certificate transparency and authenticated dictionaries.

Consensus Mechanisms

Proof of Work (PoW)

Miners compete to find nonce such that H(block_header || nonce) < target. The difficulty target adjusts to maintain a constant average block time.

Security model: An adversary controlling < 50% of hash power cannot reliably outpace the honest chain (Nakamoto consensus). The probability of a k-block reorganization decreases exponentially with k.

Properties: Permissionless, Sybil-resistant (cost of participation scales with computation), energy-intensive. Bitcoin uses SHA-256d (double SHA-256); Ethereum previously used Ethash (memory-hard to resist ASICs).

Analysis: Selfish mining attacks can be profitable with >1/3 hash power (Eyal-Sirer). The honest majority assumption actually requires >1/2 after accounting for network delays.

Proof of Stake (PoS)

Validators stake cryptocurrency as collateral. Block proposers selected proportionally to stake. Misbehavior results in slashing (forfeiture of stake).

Variants:

  • Chain-based PoS: Validators extend the longest chain (similar to PoW). Vulnerable to nothing-at-stake (validators can cheaply support multiple forks).
  • BFT-based PoS (Ethereum post-Merge): Validators vote on blocks. Finality achieved when 2/3 of stake attests to a block (Casper FFG). Combines LMD-GHOST fork choice with Casper finality.

Randomness: Validator selection requires unpredictable randomness. RANDAO (chained hash commitments from validators) + VDF (Verifiable Delay Function) in some designs. See VRF section below.

Byzantine Fault Tolerance (BFT)

PBFT (Practical BFT, Castro-Liskov 1999): Deterministic consensus tolerating f < n/3 Byzantine nodes. Three phases: pre-prepare, prepare, commit. O(n^2) message complexity per consensus round.

Tendermint/CometBFT: BFT consensus for blockchain with optimistic responsiveness. Combines proposer rotation, prevote/precommit rounds, and timeout mechanisms.

HotStuff: Linear message complexity BFT (O(n) per phase via threshold signatures). Used in Diem/Libra. Three-phase commit with pipelining for throughput. Key insight: leader-based protocol where the leader aggregates votes using threshold signatures.

DAG-based consensus (Narwhal-Tusk, Bullshark): Separate data dissemination (DAG of batches) from consensus ordering. Achieves high throughput by allowing parallel block proposal.

Ring Signatures

A ring signature allows a signer to sign on behalf of a group (ring) without revealing which member signed. No setup or cooperation required from other ring members.

Construction (simplified, based on Rivest-Shamir-Tauman):

  1. Signer selects a ring of public keys {pk_1, ..., pk_n} including their own pk_s
  2. Generates signature that proves knowledge of one secret key without revealing which
  3. Verifier checks that the signature is valid with respect to the ring

Linkable ring signatures: Include a key image I = x * H_p(pk) (where x is secret key). Two signatures from the same signer produce the same key image, enabling double-spend detection without revealing the signer. Used in Monero (RingCT).

Security properties: Unforgeability (cannot sign without a private key in the ring), anonymity (cannot determine signer), and linkability (detect reuse).

Commitment Schemes

Pedersen Commitment

Setup: Group G of prime order q, generators g, h (nobody knows log_g(h)).

Commit: C = g^m * h^r for message m and random blinding factor r.

Properties:

  • Perfectly hiding: C is uniformly random in G for any m (information-theoretic)
  • Computationally binding: Opening to a different m' requires solving discrete log
  • Homomorphic: C_1 * C_2 = g^{m_1+m_2} * h^{r_1+r_2} = Commit(m_1+m_2, r_1+r_2)

Applications: Confidential transactions (commit to transaction amounts), zero-knowledge protocols (commit to witness before receiving challenge), coin flipping, auction bids.

Vector Pedersen commitment: C = g_1^{m_1} * g_2^{m_2} * ... * g_n^{m_n} * h^r. Commits to a vector of values. Basis for Bulletproofs inner product arguments.

Verifiable Random Functions (VRF)

A VRF is a pseudorandom function with a proof of correctness. Given secret key sk and input x:

  • Output: y = VRF(sk, x) -- deterministic, pseudorandom
  • Proof: pi = Prove(sk, x) -- proves y is correctly computed

Anyone with the public key can verify: Verify(pk, x, y, pi) = accept/reject.

Properties: Uniqueness (only one valid output per input), pseudorandomness (output indistinguishable from random without sk), verifiability (proof convinces verifier).

Construction (ECVRF, RFC 9381): Based on elliptic curves. Gamma = sk * H(x), y = H'(Gamma), pi is a Schnorr-like proof that Gamma is correctly computed.

Blockchain applications: Leader election in PoS (Algorand's cryptographic sortition), randomness beacons, lottery mechanisms. Each validator evaluates VRF on round number; low outputs indicate selection as proposer.

Threshold and Multi-Signatures

Schnorr Multi-Signatures

Enable n signers to produce a single signature verifiable against an aggregate public key.

Naive approach: Sum public keys X_agg = sum X_i, sum nonces R_agg = sum R_i, each signer provides partial signature s_i = r_i + c * x_i. Final signature (R_agg, s = sum s_i).

Rogue key attack: Adversary chooses X_n = g^{x_n} - sum_{i<n} X_i, making X_agg = g^{x_n}. They can forge signatures alone.

MuSig2

Two-round Schnorr multi-signature protocol (Nick-Jonas-Ruffing 2021).

Protocol:

  1. Key aggregation: X_agg = prod X_i^{a_i} where a_i = H(X_i, {X_1,...,X_n}) (key coefficient prevents rogue key attack)
  2. Round 1 (nonce exchange): Each signer generates and broadcasts two nonce commitments (R_{i,1}, R_{i,2})
  3. Round 2 (signing): Aggregate nonces R = prod R_{i,1} * prod R_{i,2}^b where b = H(X_agg, R_{i,j}, msg). Each signer computes partial signature s_i. Aggregate: s = sum s_i.

Output: Standard Schnorr signature (R, s) verifiable against X_agg. On-chain, indistinguishable from a single-signer signature. Used in Bitcoin Taproot (BIP 340/341).

FROST (Flexible Round-Optimized Schnorr Threshold)

Threshold Schnorr signature: t-of-n signers produce a signature.

Setup: Distributed key generation (DKG) via Shamir secret sharing. Each party holds a share of the signing key.

Signing (two rounds):

  1. Each participating signer generates and broadcasts nonce commitments
  2. Each signer computes a partial signature using their key share and Lagrange interpolation coefficients
  3. Aggregate partial signatures to obtain the threshold signature

Properties: Standard Schnorr signature output, t-of-n threshold, robust against up to t-1 malicious signers (with identifiable aborts). IETF RFC 9591.

Applications: Cryptocurrency custody (multisig wallets), distributed key management, certificate authority key protection.

Additional Blockchain Primitives

Verifiable Delay Functions (VDF)

Functions requiring sequential computation time T but with quickly verifiable proofs. Used for unbiasable randomness in consensus.

Constructions: Repeated squaring in RSA groups (Pietrzak, Wesolowski). Compute y = x^{2^T} mod N; proof enables verification in O(log T) time.

Zero-Knowledge Rollups

Layer-2 scaling using ZK proofs. Execute transactions off-chain, post a succinct proof of correct execution on-chain. The proof verifies thousands of transactions in a single on-chain verification. Combines ZK-SNARKs/STARKs with Merkle tree state commitments.

Accountable Assertions

Proof of reserves: Exchange proves it holds sufficient assets via Merkle sum tree (each node stores sum of balances) with ZK proofs that all balances are non-negative.

Proof of solvency: Prove assets >= liabilities without revealing exact amounts. Combines Pedersen commitments and range proofs.