Tech explained: Hash puzzles and proofs of work

Posted by on Tue, Sep 6, 2016

Following my blockchain Computerworld article, I’ve been getting quite a few questions about how the Bitcoin blockchain is protected by ‘difficulty’.  Mining blocks is hard, so, what are miners doing that uses so much time, effort and power? They’re proving their work, by solving hash-puzzles.

See also: Burning coin - estimating the energy use of the Bitcoin network in 2016.

Puzzles as Proofs of Work

Puzzles come in many shapes and forms: from the common jigsaw puzzle, to number puzzles, and even crosswords. Regardless of the type of puzzle, they all have some similarities: puzzles take time to solve, they have varying levels of difficulty, and most solutions are obvious and easy to check.

With most puzzles, it is possible to alter the difficulty by changing parameters. For example an easy jigsaw might have 100 pieces, while a difficult one has 5000 pieces.

The more difficult a puzzle is, the longer it will take to solve.

 Similarly, hash-puzzles take time to solve, vary in difficulty, and are easy to check. However, unlike solving a jigsaw puzzle, logic doesn’t help. Hash-puzzles are much harder, and they can only be solved by trial and error.

How a hash works

A hash is like a fingerprint. It’s a massive, random-looking number that uniquely identifies a piece of information. Given any electronic data, it is possible to generate its hash (which looks like a very long serial number). Hashes are infinitely sensitive to change, even a tiny change to the input results in a wildly different hash output.

See also: Tech explained: What is a hash, what is brute force and are hashes secure?

While hashes appear random and unpredictable, they are deterministic. For each input, only one hash output exists — every time I use the same hash inputs, the same output value will come out.  Hash-puzzles rely on both the random and deterministic properties of hashes to prove and verify work.

Solve this

If I challenge you to roll a dice until you saw a two: for each roll you’d have a 1/6 chance of throwing a 2. If I gave you two dice and wanted double twos, the likelihood of that is 1/6 X 1/6 = 1/36 (and with three dice, 1/216). The difficulty increases exponentially, and the challenge takes longer to complete.

Screenshot of a hash puzzle. The screenshot shows a python script that takes an input extends it with a random value and check for a hash that starts with a predetermined sequence
A short python script to solve hash puzzles. Using random values (a nonce) to make the hash result match the rules of the puzzle. The difficulty of the puzzle is affected by the complexity and length required to match the puzzle's rules. The more letters, the more difficult the puzzle - A single letter is easy to match, but three letters starts to take a long time!

I can do the same with a hash-puzzle. I can say “roll hashes until you find one starting with the letter ‘A’” (probability 1/64), or roll a hash that starts with something longer e.g.: “Hi” (1/4096) or “Dog” (1/262,144). The only way to solve the puzzle is to try random input values, perform the hash operation, and then look at the output to see if it matched the puzzle rules. If I want to make the puzzle take longer or require more resources, I just make the rule harder to match.

I can also require that you find a solution where the input starts with some pre-defined content. Your task is to append some random value to my starting content, hash, test and repeat. My input doesn’t affect your effort, but it does ensure you start from scratch.

Bitcoin puzzles

Bitcoin uses the transaction data, and ‘chains’ the previous block’s hash value as a starting input for the next block’s. Miners then race to tack on massive random numbers until they find one that produces a hash that matches a specific pattern with a certain level of difficulty.

The blockchain is protected from modification because the hash-puzzle takes (on average) about a one-hundred-billion-billion attempts to find — it’s more work the any individual is capable of producing. But, the miners work in parallel competing to solve the next puzzle — thousands of miners, rolling the hash-puzzle-dice, over a million-million-million times per second.

Hash-puzzles are an elegant solution that provides security to the Bitcoin blockchain.