All currencies require mechanisms to control supply and enforce security properties to prevent cheating. In traditional fiat currencies, central banks manage the money supply and incorporate anti-counterfeiting features into physical currency. These security measures increase the difficulty for attackers but don't eliminate counterfeiting entirely—law enforcement remains necessary to address rule violations.
Cryptocurrencies similarly require security measures to prevent system tampering and equivocation (making inconsistent statements to different parties). For example, if Alice convinces Bob she paid him a digital coin, she shouldn't be able to convince Carol she paid that same coin to her. Unlike fiat currencies, cryptocurrency security must be enforced purely through technological means without relying on central authorities.
The Role of Cryptography
Cryptocurrencies heavily utilize cryptography—the word itself combines "crypto" (hidden) and "currency." Cryptography provides mechanisms to securely encode the rules of cryptocurrency systems directly within the system itself. It prevents tampering and equivocation while mathematically encoding protocols for creating new currency units.
Before understanding cryptocurrencies, we must explore their cryptographic foundations. While cryptography is a deep research field using advanced mathematics, Bitcoin relies on relatively simple and well-known cryptographic constructions. This chapter focuses on cryptographic hashes and digital signatures—primitives essential for building cryptocurrencies. Later chapters introduce more complex schemes like zero-knowledge proofs used in Bitcoin extensions.
Cryptographic Hash Functions
The first cryptographic primitive we examine is the cryptographic hash function. A hash function is a mathematical function with three key properties:
- Accepts any string input of any size
- Produces fixed-size output (typically 256 bits in our examples)
- Efficiently computable with O(n) running time for n-bit strings
While these properties define general hash functions (useful for data structures like hash tables), cryptographic hash functions require three additional security properties: collision resistance, hiding, and puzzle friendliness.
Property 1: Collision Resistance
A hash function H is collision resistant if finding two distinct inputs x and y such that H(x) = H(y) is computationally infeasible. Note that collisions must exist mathematically since the input space is infinite while the output space is finite, but finding them should be practically impossible.
The generic collision detection algorithm requires approximately 2¹²⁸ operations for a 256-bit hash function—an astronomically large number that would take current computers over 10²⁷ years to compute. While this algorithm works for every hash function, it's completely impractical.
Some hash functions have efficient collision-finding methods. For example, H(x) = x mod 2²⁵⁶ simply returns the last 256 bits of input, making collisions easy to find (e.g., 3 and 3 + 2²⁵⁶). Cryptographic hash functions are those for which no efficient collision-finding method is known, and researchers have extensively attempted to find collisions without success.
Application: Message Digests
Collision resistance enables using hash outputs as message digests. Consider SecureBox, an authenticated online file storage system. Instead of storing entire files locally to verify integrity, users can store only the hash of the original file. When downloading later, they compute the hash of the downloaded file and compare it to the stored hash. Matching hashes confirm file integrity, while mismatches indicate tampering—even by the storage provider itself.
Property 2: Hiding
The hiding property asserts that given a hash output y = H(x), it's infeasible to determine the input x. This property requires that the input x comes from a distribution with high min-entropy (very spread out, with no particularly likely values).
For inputs that aren't naturally spread out, we can achieve hiding by concatenating with a random value r chosen from a high min-entropy distribution (e.g., a random 256-bit string) and computing H(r ‖ x).
Application: Commitments
Commitment schemes are digital analogs of sealing a value in an envelope. They consist of two algorithms:
- com := commit(msg, nonce): Takes a message and secret random nonce, returns commitment
- verify(com, msg, nonce): Verifies if commitment matches message and nonce
Security properties require:
- Hiding: Given com, finding msg is infeasible
- Binding: Finding two pairs (msg, nonce) and (msg′, nonce′) with msg ≠ msg′ but same commitment is infeasible
We can implement commitments using hash functions: commit(msg, nonce) := H(nonce ‖ msg). The hiding property of the hash function ensures the commitment hides the message, while collision resistance ensures binding.
Property 3: Puzzle Friendliness
A hash function H is puzzle friendly if for every possible n-bit output value y, when k is chosen from a high min-entropy distribution, finding x such that H(k ‖ x) = y requires time approximately 2ⁿ.
This property means that if someone wants to target a specific output value y, and part of the input is properly randomized, finding an input that hits exactly that target is very difficult.
Application: Search Puzzles
Search puzzles require searching a large space to find a solution with no shortcuts. A search puzzle consists of:
- A hash function H
- A puzzle-ID chosen from a high min-entropy distribution
- A target set Y
A solution is a value x such that H(id ‖ x) ∈ Y. Puzzle friendliness ensures no strategy exists that's significantly better than trying random x values.
SHA-256 Hash Function
Bitcoin primarily uses the SHA-256 hash function, which operates on arbitrary-length inputs through the Merkle-Damgård transform. This method converts a fixed-length compression function (taking 768-bit inputs and producing 256-bit outputs) into a hash function for arbitrary-length inputs by processing 512-bit blocks sequentially.
The construction works by:
- Dividing input into 512-bit blocks
- Processing each block with the compression function along with the previous block's output
- Using a standard initialization vector (IV) for the first block
- Returning the last block's output as the final hash
Hash Pointers and Data Structures
Hash pointers combine regular pointers with cryptographic hashes of the information they point to, enabling verification that the information hasn't changed.
Block Chain
A block chain is a linked list using hash pointers instead of regular pointers. Each block contains data and a hash pointer to the previous block. Remembering just the head hash pointer makes the entire chain tamper-evident—any change to any block would require changing all subsequent hash pointers, ultimately conflicting with the stored head pointer.
Merkle Trees
Merkle trees are binary trees built with hash pointers. Data blocks form the leaves, paired and hashed to create parent nodes, which are then paired and hashed recursively until reaching a single root hash. This structure allows efficient verification that data hasn't been tampered with using just the root hash.
Merkle trees also enable concise membership proofs. Proving a data block belongs to the tree requires showing only the path from the block to the root—about log(n) items for n nodes. Verification requires log(n) time and space.
Sorted Merkle trees (with leaves ordered by some criteria) enable efficient non-membership proofs by showing paths to the items immediately before and after where the missing item would appear.
Digital Signatures
Digital signatures provide the digital equivalent of handwritten signatures with two key properties:
- Only you can make your signature, but anyone can verify it
- The signature is tied to a specific document
A digital signature scheme consists of three algorithms:
- (sk, pk) := generateKeys(keysize): Generates secret signing key sk and public verification key pk
- sig := sign(sk, message): Creates signature for message using sk
- isValid := verify(pk, message, sig): Verifies signature against message and pk
Required properties:
- Valid signatures must verify correctly
- Existential unforgeability: Computational infeasibility to forge signatures on new messages
Practical Considerations
Digital signature implementations must address:
- Good randomness sources (critical for security)
- Message size limitations (solved by signing message hashes)
- Signing hash pointers (effectively signs entire structures)
ECDSA in Bitcoin
Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) over the secp256k1 curve, providing approximately 128 bits of security. Key sizes:
- Private key: 256 bits
- Public key (uncompressed): 512 bits
- Public key (compressed): 257 bits
- Signature: 512 bits
Messages are always hashed before signing, allowing arbitrary-length messages. Using good randomness is absolutely critical—poor randomness during signing can leak private keys.
Public Keys as Identities
A powerful technique treats public keys as identities. If you see a message with a signature that verifies under public key pk, you can consider pk as making that statement. From this perspective, the public key is an identity, and the corresponding secret key allows speaking for that identity.
This approach enables decentralized identity management—anyone can generate a new identity anytime by creating a new key pair. These identities appear random by default, providing potential anonymity (though behavioral patterns might eventually reveal real-world identities).
In Bitcoin, these identities are called addresses (hashes of public keys). Users can create multiple addresses without centralized registration.
Two Simple Cryptocurrencies
Goofycoin
Goofycoin operates with two simple rules:
- Goofy can create new coins by signing "CreateCoin [uniqueCoinID]" statements
- Coin owners can transfer coins by signing "Pay this to X" statements (X being a public key)
Anyone can verify coin validity by following the chain of hash pointers back to creation, verifying all signatures. However, Goofycoin suffers from double-spending attacks—owners can sign conflicting transactions spending the same coin multiple times.
Scroogecoin
Scroogecoin adds an append-only ledger (implemented as a digitally signed block chain) published by a central authority named Scrooge. Transactions only count if included in Scrooge-signed blocks.
Scroogecoin features two transaction types:
- CreateCoins: Signed by Scrooge, creates new coins with specified values and recipients
- PayCoins: Consumes existing coins and creates new coins of equal total value, requiring signatures from all spending coin owners
PayCoins transactions are valid if:
- Consumed coins were validly created previously
- Consumed coins haven't been spent already
- Total output value equals total input value
- Transaction signed by all consumed coin owners
While Scroogecoin prevents double-spending, it suffers from centralization—Scrooge has too much power. He can deny service, demand fees, create unlimited coins for himself, or abandon the system entirely.
The fundamental challenge becomes: Can we create a Scroogecoin-like system without a centralized authority? Can users agree on a single transaction history without central control? Solving these problems leads to systems like Bitcoin.
👉 Explore advanced cryptographic techniques
Frequently Asked Questions
What's the difference between regular hash functions and cryptographic hash functions?
Regular hash functions need to efficiently map inputs to fixed-size outputs for data structure applications. Cryptographic hash functions additionally require collision resistance, hiding, and puzzle friendliness—security properties that enable their use in security applications like digital signatures and cryptocurrencies.
Why is collision resistance important for cryptocurrencies?
Collision resistance ensures that different transactions always produce different hashes. This prevents attackers from creating two different transactions that hash to the same value, which could enable fraud like double-spending or creating fake transaction histories.
How do digital signatures provide security in cryptocurrency transactions?
Digital signatures cryptographically prove that the owner of specific coins authorized a transaction. Since only the private key holder can create a valid signature, and everyone can verify signatures with the corresponding public key, signatures provide non-repudiable proof of transaction authorization without revealing private keys.
What's the practical difference between Goofycoin and Scroogecoin?
Goofycoin demonstrates basic cryptocurrency concepts but suffers from double-spending attacks because it lacks a consensus mechanism. Scroogecoin solves double-spending through a centralized ledger but introduces centralization risks. Bitcoin essentially solves both problems by implementing a decentralized consensus mechanism.
Why are hash pointers more useful than regular pointers in distributed systems?
Hash pointers combine location information with cryptographic hashes of the data, enabling verification that the data hasn't changed. This is crucial in distributed systems where participants don't trust each other, as it allows detection of tampering without requiring trusted third parties.
How does puzzle friendliness relate to Bitcoin mining?
Bitcoin mining is essentially a search puzzle where miners attempt to find a nonce value that makes the block hash meet certain criteria (below a target value). The puzzle-friendly property of SHA-256 ensures that no strategy exists significantly better than trying random nonce values, making mining a fair competition.