Why Proof of Work is Hard

Question

I am finally beginning to understand how Proof of Work (PoW) works, and am wondering briefly why it is considered "hard" mathematically to solve. The whole goal of it (it sounds like) is for it to take the computer a decent amount of time to solve.

I am not sure yet what techniques the computer uses to solve a computational puzzle such as "finding the SHA-256 hash of some string like 'Hello, world!' that is smaller than $2^{40}$."

"Hello, world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64 = 2^252.253458683
"Hello, world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8 = 2^255.868431117
"Hello, world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7 = 2^255.444730341
...
"Hello, world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965 = 2^254.782233115
"Hello, world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6 = 2^255.585082774
"Hello, world!4250" => 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9 = 2^239.61238653

"4251 hashes on a modern computer is not very much work (most computers can achieve at least 4 million hashes per second)."

So the implementation of that would be basically "try 0, then 1, then 2, ... until we find an integer that works". Basically it's a brute force approach.

I think these might be algorithms-ish to use in finding such a value:

• Integer square root modulo a large prime
• Weaken Fiat–Shamir signatures
• Partial hash inversion
• Hash sequences
• Diffie–Hellman-based puzzle
• Moderate
• Mbound
• Hokkaido
• Cuckoo Cycle
• Merkle tree based
• Guided tour puzzle protocol

I'm wondering though if there are algorithms out there, or at least if it is theoretically possible to find an algorithm out there, that can solve this problem easily (or other proof of work problems easily). That is, I am wondering why this and other PoW problems are considered hard, if it's because they all (provably) need to be done with a brute force approach, or some other limiting constraint. Haven't been able to find a description of that.

Answer 1

A hash of $64$ hexadecimal digits contains 256 bits. There are more than $10^{77}$ different hashes, which is one hundred billions billions billions billions billions billions billions billions … billions. As we don't know a way to "invert" the hash, there is no much better method than exhaustive search, which takes far longer than the lifetime of the Universe. This is considered hard.