Are there any stochastically dependent proof of work algorithms? In bitcoin, the probability of discovering a block on the X-th hash is the same1 as it is on the Y-th hash. As such, the probability of discovery is stochastically independent.

Are there proof of work algorithms that are stochastically dependent? Miners using one might have no idea how close to a discovery they are, but they would know that they are "getting closer".



Read on if you would like a quick and dirty description of why I think such an algorithm could be interesting:

A consequence of bitcoin's stochastical independence is that whenever a miner discovers a block, none of the other competing miners are "any closer" to rediscovering the same block (with a different, yet valid hash also meeting the difficulty). It is of course only natural then that bitcoin doesn't provide any incentive/reward for rediscovering blocks, as that proof of work is better spent attempting to discover the newest block. Unfortunately though, an attacker with enough hashing power and time has a good chance of besting the competition several times in a row; which is why it's said that to be safe you need to wait for 6 confirmations, which amounts to an hour of transaction waiting time for. We could say that in bitcoin confirmations are serial.

In contrast, stochastically dependent proof of work could allow for efficient implementation of parallel confirmations; thereby greatly reducing transaction waiting time, since rediscoveries could be expected to follow shortly after the first discovery of a block. Assume a cryptocurrency using such proofs to reward not just the first discovery of a block, but also the first X of its rediscoveries. The payment receiver then only needs to verify that the transaction is listed in all the block's discoveries (or at least a high enough percentage thereof). The amount of hash power needed by an attacker to make rediscoveries should ideally be the same as it was for the initial discovery (grow linearly). These rediscovery hashes could be recorded in the same way as transactions, by being included for a fee/reward in a child block.

1Actually, the probability increases ever so slightly when no blocks have been discovered yet, and only a fixed minimum of bits are altered such as when only the nonce field is increased; but the difference is so small as to make no matter, given the astronomical number of possible hashes meeting the current difficulty.
Miners using one might have no idea how close to a discovery they are, but they would know that they are &quot;getting closer&quot;.

Yes, this is possible.
Instead of requiring one block header with difficult A, you could require 16 block headers with difficulty A/16. This would make it possible to figure out how far along you are in the process.

In contrast, stochastically dependent proof of work could allow for efficient implementation of parallel confirmations; thereby greatly reducing transaction waiting time, since rediscoveries could be expected to follow shortly after the first discovery of a block. Assume a cryptocurrency using such proofs to reward not just the first discovery of a block, but also the first X of its rediscoveries.

That's possible too. You could do this by having each block in Bitcoin have 1 or more parents. You'd need some sort of way rule to decide which transactions to keep in a merge block (since some would inevitably conflict).
Drawbacks of the previous two changes:

Normally, a miner includes transactions as soon as they hear about them. Including a transaction doesn't mean that you lose any progress. But if you were getting closer, you wouldn't want to abandon that.
Only the X strongest miners and mining pools would stay in business. Everyone else may as well not bother with mining.
Full nodes would need X times more bandwidth to verify blocks. Once the blocks were verified, it would also take extra storage. If the blocks were very different, it could take X times more storage space. If the blocks were identical, it would be only an extra ~350 bytes per block (coinbase and block header).