Hash functions show up everywhere in Bitcoin. Although you can study Bitcoin without knowing much about hash functions, you’ll struggle at every step. This article explains the problems that hash functions solve and the most important ways in which Bitcoin uses them. No previous experience with programming or cryptography is needed.

What’s in a Name?

Hash functions solve the problem of uniquely and permanently naming digital documents. Why does this matter? Because the users of any distributed system can only publish, review, and compile documents given a universally-agreed system of names.

Consider a distributed system like the Internet. I can use it to access any document, whether it be a cat video or the latest Wikileaks disclosure. There’s just one catch: I need to know the document’s name. On the internet, names come in the form of URLs, the text that appears in your browser’s address bar.

But there are two problems with URLs:

1. The host name part of the URL (e.g., bitzuma.com) is generally administered by a centralized authority.
2. URLs aren’t permanent. For example, I can change the path to any document under bitzuma.com.

The first problem means that document creators depend, at least partially, on the permission of a centralized authority to generate names. The second problem means that those using a document can never be sure that its name will remain constant over time.

The Bitcoin network manages two kinds of documents that require permanent, unique names issued without a centralized authority: transactions and blocks. For example, to verify a payment I’ve been given, I need to know its name. To know when my payment was confirmed, I need to refer to its containing block by name. More than this, transactions and blocks also refer to each other. Consider:

• a transaction must reference its parent to create a chain of ownership;
• a block must reference its parent to create a block chain;
• a block must reference the ordered list of transactions it contains.

Bitcoin needs to provide its users with a system for naming transactions and blocks so that they can later be accessed and linked together. Hash functions solve this problem.

Meet the Random Oracle

We’d like to assign a unique, permanent name to any message. This can be accomplished with the help of an imaginary invention, a random oracle.

To the outside world, a random oracle looks like a black box with two slots cut into it. Anyone can slide a message written on an index card into the input slot. The box responds by pushing a new card from the output slot. On the card is written a name, represented as a sequence of ones and zeros. The length of this name is adjustable, but constant for all documents at a given setting. Re-submitting a message always yields the same name. If two message texts differ, they will be assigned different names.

There are many ways to implement such a black box, especially if imaginary creatures are allowed. Imagine the box contains a gremlin, a book, a pencil, a stack of index cards, and a metal coin. Each page of the book is divided with a vertical line; to the left is the heading “Message” and to the right is the heading “Name.”

Messages are inserted into the input slot. When one arrives, the gremlin scans the book for it. If the message is found, the gremlin writes the corresponding name on an index card. If the message isn’t found, the gremlin generates a new name by flipping a coin. Each time heads comes up, the gremlin writes a one on the card. Each time tails comes up, the gremlin writes a zero. Enough coin tosses are made to fulfill the name length quota used by the black box. Finally, the gremlin pushes the index card with the document’s name through the output slot.

This kind of random oracle solves the problem of assigning unique, permanent names to digital messages, but it scales poorly. Aside from the fact that gremlins don’t exist, the infinite number of possible messages would quickly overwhelm even the most well-stocked black box.

Fortunately, our random oracle can be replaced for all practical purposes with a hash function. Even better, hash functions can be used without understanding their inner workings (although there’s some great documentation on that). Digitally-encoded messages enter the hash function and unique, permanent names exit. These names are called hash values.

Given this background, here are seven things to keep in mind regarding hash functions and Bitcoin.

1. Bitcoin Uses Two Hash Functions

Bitcoin uses two hash functions: SHA-256 and RIPEMD-160. SHA-256, developed by the US National Security Agency (NSA), yields hash values 256 bits in length. RIPEMD-160, developed by an academic group from Belgium, yields hash values 160 bits in length.

A good way to understand how hash functions work is to experiment with them interactively. One resource for doing so is the SHA-256 Online calculator. This tool supports a wide range of hash functions, including SHA-256 and RIPEMD-160.

2. Bitcoin Hash Functions Are Cryptographically Secure

Bitcoin’s security model rests on the assumption that no two documents will share the same hash value. An attacker able to generate a new document with the same hash value as an old one could replace confirmed transactions and existing blocks. Several other attacks would also become possible. The security of a hash function depends on two properties of the output: range and distribution.

Range refers to the largest value that a hash function can produce, measured in bits. For example, a hash function producing 16-bit output can produce at most 65,536 (2¹⁶) hash values. Although widening the output range can decrease the collision rate, adding bits increases storage and transmission costs. As such, Bitcoin’s use of 256- and 160-bit hash functions represents a tradeoff.

Uniformity refers to how evenly distributed hash value are. For example, a hash function capable of 32-bit output that consistently produced a single value would have very poor uniformity despite a large range. Any two messages would produce a collision 100% of the time, even though a much lower collision rate is feasible. To take full advantage of its output range, a good hash function ensures the widest possible distribution of values.

No matter how well-designed, the security of any hash function can in principle be broken in two ways: a collision attack and a preimage attack.

In a preimage attack, a user attempts to find a new document whose hash value matches a predefined target. For example, a Bitcoin user seeking to replace an existing block with one of her own choosing would generate variations until a match was found. The number of attempts she can expect is equal to the length of the output. Assuming perfectly random distribution of output for SHA-256 and RIPEMD-160, we can expect an attacker to require 2²⁵⁶ and 2¹⁶⁰ attempts, respectively. The infeasibility of iterating over such a vast range lies at the root of Bitcoin’s security.

A collision attack, in contrast, attempts to generate two messages with identical hash values. Certain kinds of smart contracts can be attacked in this way.

Regardless of the quality of a hash function’s output, all are subject to limitations imposed by the birthday problem (or birthday paradox). The birthday problem asks for the probability that at least two people in a randomly-selected group share a birthday. The surprising result is that in a group of only 23 people the probability of shared birthdays is over 50%.

The results of the birthday problem say that a random oracle will generate a collision between two random messages in roughly one out of every 2^n/2 attempts, where n is the number of bits in the output value. In the case of a hash function returning 16-bit output, a collision can be expected once every 2^16/2 (256) attempts. At best, adding one bit to the output of a hash function decreases collision frequency by a factor of √2. A preimage attack is not subject to this effect.

The numbers discussed here might sound woefully inadequate to ensure uniqueness over Bitcoin’s lifetime. It helps to consider the magnitude of this number in relation to a familiar reference point. The value 2²⁵⁶ is equal to approximately 10⁷⁷ when expressed in decimal format, or the number “1” followed by 77 zeroes. This number is so vast that just counting that high with an extremely efficient computer would consume the combined energy output of the sun for many centuries. In other words, it’s impossible to even enumerate the values between one and 10⁷⁷, much less execute a hash function that many times.

3. Hash Values are Expressed in Hexadecimal Notation

Working with long sequences of ones and zeros is unwieldy, so Bitcoin uses a more compact notation known as hexadecimal. Hexadecimal notation is a number system based on powers of 16, and uses the digits 0-9 and a-f.

A binary (zero and one) representation of a hash value can be converted into a hexadecimal representation by breaking it up into groups of four digits and replacing each one with the corresponding hexadecimal digit. For example, the binary sequence:

0110110000111111

becomes 6c3f when expressed in hexadecimal notation.

4. Block and Transaction IDs are Hash Values

Blocks and transactions are identified as their SHA-256 hash values, expressed in hexadecimal form.

There’s one complication to be aware of. For reasons that remain unclear to this day, Satoshi Nakamoto designed Bitcoin to use double hashes to derive transaction and block identifiers. In a double hash operation, the hash function is applied once, and then once again to the resulting hash value.

The most likely reason for doing so is to protect against a length extension attack. Here, an attacker uses knowledge of the length of the original document to find a collision in better than brute-force time.

5. Proof-of-Work is a Hash-Based Puzzle

The Bitcoin network only works if the rate of block generation stays constant. This problem is solved through proof-of-work.

Proof-of-work is a method for restricting access to a valuable resource by forcing computational work as a condition of use. Known as “Hashcash,” the idea was proposed in 1997 as a way to discourage email spam. A recipient of a message would only read those messages to which sufficient proof of computational work had been attached. Ordinary users sending individual emails wouldn’t notice the cost, but spammers sending millions of emails would.

Putting proof-of-work into practice requires a proof-of-work function. An essential quality of such a function is asymmetry. This means that verifying a proof-of-work should be fast, but generating it should be slow. With a little creativity, a hash function can serve double-duty as a proof-of-work function.

Recall that a hash function accepts a message as input, reproducibly returning a hash value as output. A hash function can be transformed into a proof-of-work function through the use of a nonce. A nonce, or number used once, is content embedded into a message that changes the output of a hash function. For example, a simple proof-of-work function might append an integer to a message, then return the hash value obtained from the result. The output of a hash-based proof-of-work function is unpredictable, but the same nonce and message will always yield the same hash value. In this way, a proof-of-work can be both easy to verify and difficult to produce.

A proof-of-work function can serve as the basis for a proof-of-work puzzle. Such a puzzle asks for a nonce that when combined with a message gives a hash value less than or equal to a threshold value. The difficulty of the puzzle can be adjusted (or “targeted”) by changing the value of the threshold. Recall that secure hash functions resist preimage attacks. This leaves trial-and-error as the only winning strategy to find a valid proof-of-work. Raising the target value widens the range of acceptable hash values, and therefore reduces the number of guesses and time needed to find a valid solution. Lowering the target value narrows the range of acceptable hash values, decreasing the speed with which a winning nonce can be found.

By revealing a suitable nonce, a user proves that sufficient computational work has been performed to gain access to a communal resource. Others can easily pass the original message and nonce into a hash function and verify that the output falls below the required threshold. In other words, a message, nonce, and target threshold prove that enough computational work was expended to unlock access to a resource.

In Bitcoin, a proof-of-work nonce is contained within every block.

6. An Address is a Specially-Encoded Hash Value

An address is a specially-formatted hash value. If an address starts with a “1,” then it was produced by hashing a public key. If an address starts with a “3,” then a smart contract program known as a script was hashed. An address starting with the letters “bc” results from hashing a transaction witness. All three forms include additional data along with the hash value.

In contrast to transaction and block IDs, public keys and scripts are hashed with subsequent rounds of SHA-256 and RIPEMD-160.

7. Hash Values Are Used in Smart Contracts

Secure hash functions are resistant to preimage attacks. In other words, a hash value can be published without risk that the original message will be guessed. However, anyone receiving the message can easily verify that the previously-published name matches by simply running it through the hash function.

Many applications for preimage resistance in smart contracts are possible. The examples in this section use a visual language designed to simplify discussion of smart contracts.

Taking advantage of preimage attack resistance, Alice can run a primitive contest secured by a hash function. For example, Alice could award ฿1 for the first person to guess her last name (Roberts). To do so, she locks a coin to the hash value h of a secret message (m, her last name). Anyone who can guess Alice’s last name can claim the coin.

Each contestant attempts to guess Alice’s last name by passing it to a hash function and observing the result. Unlike the preimage attack discussed above, this one is easier because the search space is much smaller (fewer than seven billion). When Bob correctly guesses, he includes Alice’s last name in the transaction, allowing him to spend the coin.

A similar principle can be used to mathematically link two otherwise unrelated payments together.

Imagine that Alice owns one bitcoin and Bob owns 100 litecoin. Also imagine that Alice and Bob want to trade their respective holdings. Neither party wants to make the first payment out of fear that the other will just take the money and run.

Alice and Bob can solve this problem with an atomic swap. Here’s how it works.

Alice begins by creating a secret message and obtaining its hash value with a secure hash function. Then she gives this value to Bob. Bob makes a litecoin payment to Alice, but requires her to produce her document as a condition of claiming it.

Next, Alice makes a similar bitcoin payment. If Bob can produce the message matching the hash value she gave him, he gets to keep the payment. After a deadline passes, Alice can reclaim her payment.

For Alice to claim her litecoin, she must supply the document whose hash value h is the one she gave to Bob. When Bob sees Alice’s transaction, he can use the message to claim his bitcoin payment. If Alice fails to claim Bob’s payment before the deadline, she and Bob can both claim their respective refunds.

A variation on this trading method was recently completed. The same basic idea appears in current designs for the Lightning Network as Hashed Timelock Contracts. Chapter 3 of my book Owning Bitcoin discusses hash locks, HTLCs, and other kinds of contracts in detail.

Conclusions

Hash functions play a central role to Bitcoin as a technology platform. They also figure prominently in ongoing attempts to scale Bitcoin to a worldwide audience. If you want to understand Bitcoin, time spent learning about hash functions will pay hefty dividends.