Are there any stochastically dependent proof of work algorithms?

Question

In bitcoin, the probability of discovering a block on the X-th hash is the same¹ 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.

¹_{Actually, 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.}

Answer 1

Are there proof of work algorithms that are stochastically dependent?

Yes. Another idea similar to the one that Nick described:

Add an extra 8 bytes to the end of each transaction when making the merkle tree, in a field called nEffort. The nBits field in the header describes the total amount of work that must be done (on average) on the block. Split that work up by the number of transactions in the block, and then you can mine each transaction individually by altering nEffort until the leaf of the merkle tree hashes to a low enough value. Note that this does not replace Transactions IDs, it would essentially just be an extra field of each leaf element of the merkle tree.

To check the work, you make sure that each leaf of the merkle tree meets the difficulty/Number_of_transactions parameter.

The downsides of this:

• A block header cannot be verified without having all of the transaction data, which is obviously very limiting for SPV nodes where the security of their transactions is based on how many blocks are including it.
• This could also make double spends easier. Just mine a transaction giving coins to yourself and release it after you send coins to someone else.
• It would disincentivize adding new transactions to your block, as each new transaction would mean all previously mined transactions count for less work.

It's probably not a good idea, but it's another way to do a stochastically dependent proof of work.

Answer 2

Miners using one might have no idea how close to a discovery they are, but they would know that they are "getting closer".

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).