2
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ So you're saying there are absolutely no tricks to avoiding the brute force approach then. Or at least we don't know what any of them are. That means all algorithms will be roughly the same, would be interested to know if that's true. But you're saying there could be a solution/trick. Wondering now if there is provably no way of reversing the hash. $\endgroup$ – Lance Pollard Feb 17 at 10:22
  • 5
    $\begingroup$ @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. $\endgroup$ – Henno Brandsma Feb 17 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.