3 ms·
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 tar
by 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.