In
cryptography
Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
, puzzle friendliness is a property of
cryptographic hash function
A cryptographic hash function (CHF) is a hash algorithm (a map (mathematics), map of an arbitrary binary string to a binary string with a fixed size of n bits) that has special properties desirable for a cryptography, cryptographic application: ...
s. Not all cryptographic hash functions have this property.
SHA-256
SHA-2 (Secure Hash Algorithm 2) is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compressi ...
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
Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equi ...
. Although the property is very general, it is of particular importance to proof-of-work, such as in
Bitcoin mining
The bitcoin protocol is the set of rules that govern the functioning of bitcoin. Its key components and principles are: a peer-to-peer decentralized network with no central oversight; the blockchain technology, a public ledger that records all ...
.
Definition
Here is the formal technical definition of the puzzle friendliness 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
The min-entropy, in information theory, is the smallest of the Rényi family of entropies, corresponding to the most conservative way of measuring the unpredictability of a set of outcomes, as the negative logarithm of the probability of the ''mo ...
, then it is infeasible to find ''x'' such that ''H''( ''k'' , , ''x'' ) = ''y'' (where the symbol ", , " denotes concatenation) in time significantly less than 2
''n''.
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
A puzzle is a game, problem, or toy that tests a person's ingenuity or knowledge. In a puzzle, the solver is expected to put pieces together ( or take them apart) in a logical way, in order to find the solution of the puzzle. There are differe ...
. 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
In cryptography, collision resistance is a property of cryptographic hash functions: a hash function ''H'' is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs ''a'' and ''b'' where ''a'' ≠ ' ...
*
Collision attack
In cryptography, a collision attack on a cryptographic hash tries to find two inputs producing the same hash value, i.e. a hash collision. This is in contrast to a preimage attack where a specific target hash value is specified.
There are roughly ...
*
Preimage attack
In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage (set of possible inputs).
In the context of attack, the ...
References
{{Cryptography navbox, hash
Cryptographic hash functions
Hashing
Theory of cryptography
Bitcoin