3 ms·

«for sha-256 using brute force, this probability is totally 0» It's not zero. It's very small, but not zero. The difference between being "theoretically exactl

• rocqua 9y ago
  But sha-256 is actually memory-full. Or rather, lets model sha-256 as a random oracle. Moreover, lets assume there is an input that leads sha-256 to be our target (so the probability of finding a solution isn't 0 at all). Take the shortest input that meets our target, and call it L. Now, brute-force try all inputs up to length L. You know have P(find solution after 2^L tries) = 1. This cannot happen for a memoryless process. If you pick your inputs randomly, it remains a memoryless process.
  • mrb 9y ago
    «lets assume there is an input that leads sha-256 » Your assumption is wrong. Theoretically, there might be no inputs that are solutions to the PoW. Of course in practice there are almost always a large number of solutions, but again the theoretical possibility of it is why it is correct to say the PoW is memoryless. Even if theoretically there was always a solution, there is no way to iterate sequentially over all inputs because after iterating over 2^32 nonces, miners have to change the 256-bit merkel root, which is effectively random. This aspect alone makes mining memoryless.