Puzzle friendliness

In cryptography, puzzle friendliness is a property of cryptographic hash functions. Not all cryptographic hash functions have this property. SHA-256 is a cryptographic hash function that has this property. Informally, a hash function is puzzle friendly if no solution exists, which is better than just making random guesses and the only way to find a solution is the brute force method. Although the property is very general, it is really important only in Bitcoin mining.

Definition

Here is the formal technical definition of the puzzle frierndliness property.

• A hash function H is said to be puzzle friendly if for every possible n-bit output value y, if k is chosen with a distribution with high min-entropy, then it is infeasible to find x such that H( k || x ) = y (where the symbol "||" denotes concatenation) in time significantly less than 2ⁿ.

In the above definition, the distribution has high min-entropy means that the distribution from which k is chosen is hugely distributed so that choosing some particular random value from the distribution has only a negligible probability.

Why this property is called puzzle friendliness?

Let H be a cryptographic hash function and let an output y be given. Let it be required to find z such that H( z ) = y. Let us also assume that a part of the string z, say k, is known. Then, the problem of determining z boils down to finding x that should be concatenated with k to get z. The problem of determining x can be thought of a puzzle. It is really a puzzle only if the task of finding x is nontrivial and is nearly infeasible. Thus the puzzle friendliness property of a cryptographic hash function makes the problem of finding x closer to being a real puzzle.

Application in cryptocurrency

The puzzle friendliness property of cryptographic hash functions is used in Bitcoin mining.

See also

• Collision resistance
• Collision attack
• Preimage attack