Why Proof-of-Work WORKS

[jonald_fyookball]

Why is Bitcoin's Proof-of-Work,
combined with the longest-chain-wins
rule, a guaranteed way to achieve
distributed consensus?

In a word: TIME.

Proof of work ensures that it takes a long time
to solve a block.  If we estimate it takes
a node about 1 second to propogate information
to another node, and it takes 10 minutes to
solve a block, that means the consensus-building
effect of longer chains overriding shorter
chains is happening 600 times faster than
new complexity is being introduced into the system.

600 times faster.

It's almost as if time is standing still between
block creation, while the nodes can do hundreds
of consensus-building state changes.

At any given time, if divergence starts to manifest,
the state of the network can be described as N
number of subsets:  S1 ... Sn.

Because of the longest-chain-wins rule,
each state change will see nodes with shorter chains
leave their subset to become part of a subset with a longer
chain. 

This will happen in a somewhat linear fashion,
and so within a short amount of time, the network
will converge into a single set with the longest
chain.

[1715438438]

1715438438

[1715438438]

1715438438

[1715438438]

1715438438

[Peter R]

I believe viewing proof-of-work through this lens is valid and possibly novel. 

Viewed through this lens, it also becomes apparent why decreasing the block-time target too far is dangerous.  If the block-time is no longer long compared to the time scale at which complexity is introduced, consensus may not converge (resulting in multiple forks).  Since it is not clear how quickly information will propagate across the network in situations such as (a) war, (b) internet censorship, (c) severe power failures, (d) physical damage to key infrastructure, a 10 min target was a conservative choice to increase the robustness of the network.

[luv2drnkbr]

ya that's the idea.  10 minutes is a happy medium between reasonably quick and guaranteeing very few orphans

.

Viewed through this lens, it also becomes apparent why decreasing the block-time target too far is dangerous.

ya a lower time gives "confirmation" faster, but assuming the same hashing power, a 1 minute block is only 1/10 as reliable as a 10 minute block.  it doesn't change the cost of a 51% attack or anything.  and with lower times like that, you get a ton more orphans and thus bandwidth bloat, since there will often be many many 2- and 3- block chains in competition with each other, so even a couple confirmations can be magically wiped out.  again, that's why 10 min was chosen-- you rarely get more than one orphan block, and so consensus about the current state of the ledger, even in the very last block, is reasonably reliable, and more than a half dozen or so blocks is virtually guaranteed in all but the very worst of circumstances, like say last March when the network was forked briefly.  and 100+ confirmations is a fucking solid lock.

[Peter R]

I am wondering if Jonald is on to something significant.  Here's some half-backed analysis...

Define:

    T_consensus, as the mean time of network consensus events, and

    T_complexity, as the time scale at which complexity (e.g., transactions, or solved blocks) propagates across the network.

The j-factor

    X_j = T_consensus / T_complexity

describes the how much slower the consensus building efforts are compared to the introduction of new complexity.  We know that for a proof-of-work based consensus system too small a value of X_j leads to higher orphan rates and possibly multiple diverging forks (network split), while a large value of X_j leads to long confirmation times (consensus events).  

I am wondering if this holds true beyond just proof-of-work and in fact describes a fundamental trade-off that all methods of establishing consensus in a peer-to-peer network must make.  Is there some way to answer this question mathematically?  If this relationship does in fact hold true, then I think it also means that any method for establishing consensus in a distributed system must ensure that the consensus events are spaced sufficiently far apart in time.  This would seem rather significant if it were in fact true.  


    

[jonald_fyookball]

It may be significant.

I sat down to try to work out for myself
If I could prove consensus mathematically,
But once I started writing out the problem,
the concept of time being the critical factor
presented itself. 

Because of the 600:1 ratio, the other probabilities
become meaningless.

I think that other kind of consensus would work
if block duration is ensured.

[Peter R]

I think that other kind of consensus would work if block duration is ensured.

Or it could be that there is no other trustless method besides PoW to ensure block duration.  In any case, I'm interested if X_j = T_consensus / T_complexity is an important ratio for all potential methods of establishing consensus in peer-to-peer networks.

[jonald_fyookball]

Well, if the ratio is big as with bitcoin, it seems to be a sufficient condition.

However, we don't know what happens when we go to the other extreme,
Or somewhere in the middle, and what other conditions or factors would be
impactful.

If it was possible to created duration without trust without pow
would we be onto something big?

[Bitcoin Magazine]

the combination of PPcoin and BTCitcoin mining creates a condition where no one can get 51% period.

[counter]

I love how discussions on the inner working of Bitcoin usually leads to some sort of hypothetical philosophical discussions.  This is a topic I'm not very knowledgeable one just yet but it is interesting to read about.

[Brangdon]

Or it could be that there is no other trustless method besides PoW to ensure block duration.

The obvious alternative would be for a protocol to simply require that each block have a timestamp 10 minutes after the previous block to be valid. One problem is that a miner might lie, and add a timestamp that is in the future. Nodes could reject blocks from too far in the future, but since they all have their own clocks this could get a bit hit and miss at the edges. If miners are competing to create blocks, then you'd get a rush of blocks broadcast as the deadline passes. It does feel a bit anti-consensus.

With transparent forging, as I understand it, miners aren't competing to create blocks. Instead, one miner (or a small group, for redundancy) gets nominated in advance as having the honour. I have reservations about transparent forging - it seems to be an invitation for denial of service attacks - but maybe it resolves this issue. Certainly Proof of Stake coins don't seem concerned about their block time being variable. (Although most prefer a shorter block time than Bitcoin.)