Quote from: thezerg on October 02, 2014, 03:31:22 PM

Quote from: cypherdoc on October 01, 2014, 05:52:02 PM

Quote from: justusranvier on October 01, 2014, 05:49:17 PM

Given that we know the BGP is mathematically unsolvable

i've heard this a few times already.

can u give a simple layman's description to why this is?

Allright I took fischer's provability class so I'll give it a go:

First of all whether BGP is solvable or not depends on the "powers" given to the honest vs. lying generals. Can the honest generals "broadcast" a message to everyone else? Can lying generals "intercept" and rewrite messages? Do you have a mostly-synchronized clock, or even a local sense of time? So papers basically define these "powers" and then prove a yes or no result based on them.

Let me try to couch why BGP is sometimes unsolvable in what you are familiar with: bitcoin. Let's just say we choose one node to grab all txns and add them to the blockchain. That node can't steal $ because it can't sign the txns. But it could insist that there are no txns, or disappear. If it insists there are no txns (but there are) then no progress is made (algorithm is halted). If it disappears, can you just choose another? No because you can't prove that it is really gone vs just slow. That is, it could seem to disappear causing the rest of the network to pick another "issuer". Then both nodes post a block at the exact same moment resulting in half the nodes using block A and the other half B [1]. Could you then get the network to "settle" on one of the 2 blocks? Well, doing so is equivalent to solving the original problem (picking a block in the first place), so the above strategy made zero progress solving this problem.

But note that if you had some relatively consistent sense of elapsed time (an additional "power"), say all nodes have time accuracy within an interval E (say 5 min), you could do something like: the announcer has until time X to announce a block, at time X+E, we choose another announcer [2]. Ok that works but it requires a synchronized clock. No clock is ever synchronized perfectly. So in practice it solves 99.99% of the problem, but what happens if the announcer issues the block exactly at time X+E. So half of the nodes will think that it is valid, the other half will reject. So now we have to decide whether to accept the proposed block or not. Doing so is equivalent to the original problem. We have made no progress.

How about you use a "fitness function" to choose the best block? Perhaps use the longest block (most txns in it). This doesn't work because at any time someone could add a few more txns to a very old block and reissue it, wiping out the blockchain up to that point. That is, an uncooperative node could cause the algorithm to never make progress. Ok so let's say once the block is issued it can't be "unissued". But what if 2 nodes "issue" conflicting blocks simultaneously. We have to pick one. Oops, we are back to square one! (and what does "issued" mean anyway -- in fact it is not definable in a p2p network).

Bitcoin itself does not even solve the problem. At any time, someone could show up with an alternate blockchain that is full of empty blocks since 2009 (say he's secretly been racing with the public chain) and all clients would switch to that chain where no transactions have happened. So in fact from a theoretical perspective the algorithm can be proved to never make progress. However, from a practical perspective this is unlikely to happen, and if it did, I as a community we could throw in some kind of hard coded change (essentially a centralized decision hard-coded in a new client) that forces "our" chain to be chosen.

So what's cool about Bitcoin is if it breaks down it can essentially "devolve" into (worst case) a centralized scheme. No worse then we had before Bitcoin (and actually a whole lot better in other metrics).

[1] http://cs-www.cs.yale.edu/homes/arvind/cs425/doc/fischer.pdf
[2] http://research.microsoft.com/en-us/um/people/lamport/pubs/reaching.pdf

Quoted For Truth
...
In the smaller chains of the alt coin world, these concerns are dealt with more commonly. Some of them show promise as ways to deal with what might happen if Bitcoin faced existential threats from major powers. Some of these innovations ultimately do matriculate into Bitcoin.

By way of example, A week or two ago such an existential threat materialized in one of the up and coming alt coins with savvy devloper team, (Monero), in which an issued threat of a hostile fork using massive hashpower (and maybe some clever hacks against clocks) was met with an innovative solution. That solution decentralized the chain-fork choice with the option of individual manual interventions, allowing miners/generals to swiftly select a chain without requiring (but still allowing for) the devolution to a centralized scheme.

In effect, this raises the hostility-cost in the battle to be the issuing miner/general, by allowing the other miner/generals an easy tool to select an alliance if the need arises, without waiting for a recompiled code from their HQ to resolve it. This innovation expands individual liberty in time of crisis. It lets the miner/generals act in response to threat if they are cut off from HQ. It also serves to increase the confidence that these crypto currencies are truly 'antifragile' and cleave true to Wei Dai's cypherpunk entreaty to make "the threat of violence impossible because violence is impossible..."