Decreased-variance PoW logic

[kek-coin]

Currently the mining process is very sensitive to variance. This is due to the fact that mining a block is essentially a question of rolling a die and checking if the result is good enough; if it is, you've mined a block, if it isn't, you roll it again until it is. This has the consequence that the expected value of the amount of necessary rolls is equal to 1/p_success where p_success represents the chance that any roll is a success.

The same expected value for the amount of rolls can be achieved by requiring n rolls to all meet a given lower difficulty threshold instead. In other words, p_partialsuccess = p_success/n. In this new scheme, the variance in time to finding a block is reduced to the variance in time to finding n blocks in the old scheme.

This has a couple of notable advantages.

1. Better user experience due to more predictability in confirmation time.
2. Difficulty readjustment logic can be vastly improved. For the same amount of resilience to variance as in current Bitcoin, only 2016/n blocks are needed to a difficulty readjustment period.
3. Mining payout becomes more reliable, and therefore small pools/solo mining becomes more feasible, aiding in mining decentralization.

I have not yet worked out the details of the implementation as I first wanted to collect feedback on the concept, but one implementation could work by making the nonce field n times as long and let every ith (i from 1 to n) partial-hash be calculated over the blockheader including only the first 32*i bits of the nonce field.

[luke-jr]

This would break the proof-of-work by enabling progress on solutions. The end result is that the fastest miner always wins... Did I miss something?

[kek-coin]

Right, good point. Essentially, you'd want a scheme where the miner who mined the first part of the block didn't get all the rewards, but instead they were spread around over the n partial blocks. This would encourage publication of the first partial-block, because as soon as someone else mines one they will put it out on the network and everyone will start mining on top of that.

This could be implemented as n-1 "confirmation blocks" on top of the original block; each partial block (original is considered partial as well) needs to meet the partial difficulty requirement and may claim only 1/n of the block rewards (mining reward + TX fees). The confirmation blocks are not allowed to contain any TX besides one to claim part of the rewards. This reward claim can be implemented as a TX with two outputs, 1 with maximum size total_reward/n that pays out to the miner, and one anyone-can-spend (for real this time) for the next miner to claim a portion of.

These confirmation blocks should be relatively tiny, so shouldn't put too much strain on the network bandwidth-wise.

[weedcoder]

Is there a possibility to have a race condition created by multiple proposed partial block?

[kek-coin]

Well you could have a chainsplit just like normally, just one that would be resolved more quickly and also be less likely to roll back TXes, since only 1/n partial blocks actually contain those TXes. This would also give a lot more time for low-bandwidth miners to pull in and validate the block before the next one with TXes could be mined, so would get rid of the empty blocks resulting from spy mining.

[jacob-eliosoff]

I don't follow all the discussion here but @kek-coin's broad idea makes sense to me (as I understand it). Replacing "find one soln of difficulty x" with, eg, "find 10 solutions of difficulty x/10" would certainly reduce block time variance.

A possible additional tweak could be to "chain" the solns, eg, require the 2nd to start with the suffix of the 1st, etc. This would prevent pooling partial solutions which might be useful somehow...

[luke-jr]

@jacob-eliosoff The problem is that the fastest miner would disproportionately (almost always for 10 solutions) find the block first. The variance is what makes it a fair lottery.

[jacob-eliosoff]

@luke-jr Ahh, I see, thank you. And now I understand your exchange w/ @kek-coin above. His refined proposal makes sense to me: eg, 10 solutions (of difficulty x/10) are required before the block is finalized (valid, can be built on by miners, etc), but those 10 solns can be submitted by different miners and each soln is worth 1/10 of the block reward.

Still a little unclear to me which of the 10 winning miners submits the actual block of txs. (The first one? And the other 9 include that block's hash to indicate they're building on it?)