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 of particular importance to proof-of-work, such as in Bitcoin mining.[1]
Definition
[edit]Here is the formal technical definition of the puzzle friendliness property.[2][1]
- 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 2n.
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?
[edit]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
[edit]The puzzle friendliness property of cryptographic hash functions is used in Bitcoin mining.
See also
[edit]References
[edit]- ^ a b Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, Steven Goldfede (2016). Bitcoin and Cryptocurrency Technologies. Princeton University Press. p. 8 - 10. ISBN 9780691171692.
{{cite book}}: CS1 maint: multiple names: authors list (link) - ^ Ratan K. Ghosh, Hiranmay Ghosh (2023). Distributed Systems Theory and Applications. Wiley. p. 463. ISBN 9781119825951.
| |||||||||||||||||||||||||||||
