What Is A Cryptographic Hash?
June 9, 2017
Cryptographic hashes play a fundamental role in the structure of blockchains, which is what Bitcoin is built on.
Essentially, hashes act as digital fingerprints for data. If you have a person and a fingerprint, it is easy to verify that the fingerprint belongs to the person, but a fingerprint alone tells you very little about someone. We will later see that this property is useful for verifying the authenticity of a blockchain.
Let’s explore this more formally in this pre-introductory post to Bitcoin.
What’s A Hash Function?
A hash is a function $H: X \to Y$ which satisfies the three following properties.
The input space X is the set of strings of arbitrary length.
This means that ‘helloworld’ and ‘helloworldhelloworldhelloworld’ are both perfectly fine inputs.
The output space Y is a set of strings fixed length.
Regardless of their different lengths, both inputs would map to something of the same length, say $H(\text{‘helloworld’})=\text{‘l1’}$ and $H(‘helloworldhelloworldhelloworld’) = ‘3x’$.
Bitcoin uses SHA256 as its hash function. The 256 part stands for the number of bits in its fixed-sized output.
The hash function $H$ is efficient to compute.
Given a string $s$ of length $n$, the complexity to produce $H(s)$ is $O(n)$.
This ease of computation is what give blockchains the property of being easily verifiable to prevent tampering. As we will see later, we can verify if a block is “authentic” in a blockchain by simply computing the hash of a block, which is a cost-effective operation (computation-wise).
What Is A Cryptographic Hash Function
In addition to the three properties of hash functionslisted above, cryptographic hash functions have the following additional properties.
Collision Resistance
A collision happens when a hash function maps two different inputs to the same output.So collisions happen on points where the function isn’t injective.
Since the target space is of a fixed sized (say 256 bits) while the input size is infinite, a hash function cannot be truly injective by the Pigeonhole principleThe principle that if I throw 4 balls in 3 holes, one hole is going to have more than 1 ball. . A collision resistant function is one where it is computationally infeasible to find a collision. What is infeasible, of course, changes with technological progress.
For a “good” hash function with 256-bit output (which is what Bitcoin uses), it takes $2^{128}$ computations on average to produce a collision. If a computer calculates 10,000 hashes per second, it would take one octillion ($10^{27}$) years to calculate $2^{128}$ hashes in order to produce a collision. Source.
A example of a hash function where it’s feasible to find a collision is $H(x) = x \mod 2^{256}$. This function satisfies our fixed length property, but it is easy to find a collision as $H^{-1}(x)$ is simply $x + r \cdot 2^{256}, \quad r \in \mathbb{Z}$, so each number which differs by an integer multiple of $2^{256}$ collide once they are mapped by this hash function.
As of now, no function has been proven to be collision resistant yetIn fact, we have been wrong in the past. The MD5 function was assumed to be collision resistant but after a couple years people have found collisions. What is computationally costly in the past won’t be as much in the future. , so the cryptographic functions we are using nowadays are functions for which we have yet to find collisions for.
Application: Collision resistance is what gives cryptographic hash the property of acting like fingerprints/identifiers of data. Although we cannot usually deduce from the hash what the data looks like (as we will see below), the data is (until proven otherwise) uniquely identified to its hash function, which is of fixed length. As we will see later, this allows us to identify blocks in the blockchain of Bitcoin by hashing them. It also makes the blocks resistant to tampering since changing the data changes the hash.
Hiding
Intuitively, we want the hash functions to “hide” the space of practical inputs. Given the hash $y = H(x)$, an attacker should have to generate the hash of every $x’$ in the input space randomly in order to be able to find $x$ which generated $y$. This makes it infeasible to predict which input will result in the right hash.
For example, if the information we are hashing is of the form “Alice pays Bob”, “Bob pays Eve”, then the input space is easily guessable to be of the form “Person1 pays Person2”.
This is a situation we want to avoid, because it makes computing inverse images becomes easy: generate all the hashes of the form $H(\text{“Person1 pays Person2”})$ (assuming strings of these form are finite), and we now have a lookup table of every input-output pair.
To remedy the situation, each time we want to input to our hash function, we must pick random fixed length string (say a 256-bit one) $r$ from a “spread out” (high min-entropy) probability distribution. In Bitcoin, this random string $r$ is called the nonce, for number used once. We then concatenate our string $x$ with $r$. From this concatenation, we have spread our space of practical input which was low entropy (high information) to a space with high entropy (low information).
Given a hash function $H$, we will now write $H(x)$ when we really mean $H(x) = H(r || x) = y$ with the $||$ symbol denoting concatenation. Now given $y$, it is infeasible to find $x$ because there are too many combinations $r’ ||x’$ to try out. Constructing a lookup table is now unfeasible.
Application: The hiding property allows us to make a commitment scheme. Given a message $x$, we may send a hash of the message $y = H(r || x)$ to announce a commitment to this message without revealing what it is. In other words, given $H(r||x)$ we cannot figure out what $x$ is by the hiding property. Then, once we are ready to reveal the message, we can declare it along with the nonce, meaning we are declaring the tuple $(r,x)$. Then, someone can compute the hash of the nonce and the message in linear time, confirming that this message was indeed the one committed. By the collision-free property, we may not have edited our message because it infeasible to find a tuple $(r’,x’)$ which hash to the same thing.
Puzzle Friendliness
We have just seen that given an output, we want to make it difficult to find the input.
Puzzle friendliness is the property that given part of the input $k$ which is picked from a high min-entropy distribution and an $n$-bit output $y$, it is infeasible to find $x$ so that $H(k || x) = y$ in time significantly less than $2^n$.
Basically, even given part of the input and the output, it is very difficult for us to find the rest of the input.
Application: As we will see later, this property is central to Bitcoin mining, which is essentially a race to solve a cryptographic puzzle by essentially trying out solutions uniformly randomly. Bitcoin achieves its distributed consensus by allowing the first person to solve the puzzle to decide the next block. This why having access to more computational power increases your leverage in Bitcoin.
As computational power increases over time, it gets easier and easier to solve Bitcoin’s cryptographic puzzle. Moore’s law states that computational power increases as $2^T$, where $T$ is time. Puzzle friendliness allows us to keep the required time to solve Bitcoin’s cryptographic puzzle roughly constant by increasing the length of $y$, the hash output we want to find in the puzzle. By definition of puzzle friendliness, the difficulty of the puzzle evolves as $2^n$ where $n$ is the length of $y$. This cancels the effect of Moore’s law, as well as bigger players entering the Bitcoin ecosystem. In fact, Bitcoin keeps the average time to mine a new block to 10 minutes.
That’s all for now! In a next post, we will see how these properties of the crytographic hash make the hash pointer in a blockchain resistant to tempering, a property that is fundamental to the Bitcoin system. Stay tuned!
Summary
In summary, the hash function has these three properties.
- Takes as input a string of arbitrary length,
- Returns as output a string of fixed length,
- The output of the function is easy to compute relative to the length of the input.
A cryptographic hash has these three additional properties.
- Collision resistance: we are very unlikely to find two inputs which give the same output, no matter how hard we try.
- Hiding: given a hash, it is infeasible to find its associated input and the optimal way to do so is to try every possibility uniformly randomly.
- Puzzle friendliness: given a hash and part of the input that has been chosen in a suitably random way, the optimal way to find the rest of the input is still to try every possibility randomly. The difficulty of that task is exponential in the length of the hash, making it easy to adjust the difficulty of the puzzle by varying the restriction on the desired hash output.
Source
Bitcoin and Cryptocurrency Technologies great theoretical textbook on Bitcoin with free lectures available.
This post was written from the perspective of a mathy beginner.
Special thanks to Jake Hickey for guiding through my cryptocurrency learning and providing valuable feedback for this blog post.