All currencies need some way to control supply and enforce various security properties to prevent cheating. In fiat currencies, organizations like central banks control the money supply and add anti-counterfeiting features to physical currency. These security features raise the bar for an attacker, but they don’t make money impossible to counterfeit. Ultimately, law enforcement is necessary for stopping people from breaking the rules of the system.
Cryptocurrencies too must have security measures that prevent people from tampering with the state of the system and from equivocating (that is, making mutually inconsistent statements to different people). If Alice convinces Bob that she paid him a digital coin, for example, she should not be able to convince Carol that she paid her that same coin. But unlike fiat currencies, the security rules of cryptocurrencies need to be enforced purely technologically and without relying on a central authority.
As the word suggests, cryptocurrencies make heavy use of cryptography. Cryptography provides a mechanism for securely encoding the rules of a cryptocurrency system in the system itself. We can use it to prevent tampering and equivocation, as well as to encode, in a mathematical protocol, the rules for the creation of new units of the currency. Thus, before we can properly understand cryptocurrencies, we need to delve into the cryptographic foundations that they rely on. Cryptography is a deep academic research field using many advanced mathematical techniques that are notoriously subtle and complicated. Fortunately, Bitcoin relies on only a handful of relatively simple and well-known cryptographic constructions. In this chapter, we specifically study cryptographic hashes and digital signatures, two primitives that prove to be useful for building cryptocurrencies. Later chapters introduce more complicated cryptographic schemes, such as zero-knowledge proofs, that are used in proposed extensions and modifications to Bitcoin.
CRYPTOGRAPHIC HASH FUNCTIONS
The first cryptographic primitive that we need to understand is a cryptographic hash function. A hash function is a mathematical function with the following three properties:
- Its input can be any string of any size.
- It produces a fixed-sized output. For the purpose of making the discussion in this chapter concrete, we will assume a 256-bit output size. However, our discussion holds true for any output size, as long as it is sufficiently large.
- It is efficiently computable. Intuitively this means that for a given input string, you can figure out what the output of the hash function is in a reasonable amount of time. More technically, computing the hash of an n-bit string should have a running time that is O(n).
These properties define a general hash function, one that could be used to build a data structure, such as a hash table. We’re going to focus exclusively on cryptographic hash functions. For a hash function to be cryptographically secure, we require that it has the following three additional properties: (1) collision resistance, (2) hiding, and (3) puzzle friendliness.
Now, to make things even worse, we said that it has to be impossible to find a collision. Yet there are methods that are guaranteed to find a collision. Consider the following simple method for finding a collision for a hash function with a 256-bit output size: pick 2 256 + 1 distinct value, compute the hashes of each of them, and check whether any two outputs are equal. Since we picked more inputs than possible outputs, some pairs of them must collide when you apply the hash function.
Last word
Yet for other hash functions, we don’t know whether such methods exist. We suspect that they are collision-resistant. However, no hash functions have been proven to be collision-resistant. The cryptographic hash functions that we rely on in practice are just functions for which people have tried really, really hard to find collisions and haven’t yet succeeded.
