Why Proof of Work is Hard

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.

• It is not "considered" mathematically hard, it has to be for the mechanism to make sense. Reversing a hash is hard with current technology. – Yves Daoust Feb 17 at 9:31
• I get that much, I don't understand why though. – Lance Pollard Feb 17 at 9:31
• To understand why, try to reverse one – Prince M Feb 17 at 9:42

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.
• @LancePollard We cannot prove mathematically we cannot reverse the hash. That would basically amount to showing $P \neq NP$. But we believe we cannot. PoW is a matter of believe in the state of the art of our current knowledge (or lack thereof). There is no purely mathematical foundation. – Henno Brandsma Feb 17 at 10:28