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

• I don't think your footnote is correct, because you are not guaranteed that you will ever find a solution. Feel free to explain and prove me wrong, though. Commented Jan 21, 2015 at 21:13

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.

• Then the block wouldn't meet the proof of work. Same as in Bitcoin, I could relay a block and replace a transaction, but it would be rejected by everyone... I think the problem you're talking about is replacement. In the method I proposed, I could replace a transaction in a block with another mined transaction, and it would still validate. Hence, not a viable PoW method. Commented Jan 21, 2015 at 21:33
• You saw nothing! I thought of a better attack: if I see your block on the network, couldn't I replace the coinbase of your block with my own coinbase, assuming it had enough work attached? Commented Jan 21, 2015 at 21:41
• @NickODell Haha, that is better. I thought of a fix, and then a way to break my fix, so I'm just going to quit now, obviously this would never work. :P Commented Jan 21, 2015 at 21:52

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).
• In the last point, don't you mean SPV nodes? Also, it wouldn't be exactly X times, since some of the header data can be reused. Commented Jan 21, 2015 at 20:04
• This might work if the TX set mined was append-only. And I agree with @MeniRosenfeld, it seems like it would only be X times the storage for SPV nodes, but marginally more storage for full nodes. One interesting aspect of this proposal is that pools would be incentivized to find out how far along other pools are. i.e. if another pool has 13/16 headers solved but your pool (same hashing power) got unlucky and only has 2/16 solved, then the other pool would be much more likely to win, so it would probably not be profitable for your pool to continue to mine until the other pool solves the block. Commented Jan 21, 2015 at 20:47