Satoshi didn't solve the Byzantine generals problem

[r0ach]

(disclaimer: Bitcoin is still the best effort that exists at creating a decentralized currency and no altcoin has made a better method.)

I feel this topic deserves it's own thread and would get stonewalled with popular opinion somewhere in the Bitcoin section.  My argument here is:

<r0ach> you can't solve byzantine generals problem with a probabilistic model unless you've first solved sybil with a probabilistic model and Bitcoin doesn't do that
<r0ach> because there's no way of telling if all pools are owned by the same person, then it's not collusion or 51% attack, it's a sybil attack
<r0ach> since the essence of the byzantine generals problem is sybil attack, dealing with sybil comes first in the hierarchy before byzantine generals is discussed at all

The Byzantine problem deals with a minority of actors or signal throwing off the consensus of the system or majority.  If you can't determine how many actors even exist in the first place, you're probably always going to lose this test.  This fact might give credence to some form of deterministic block validators model, but that's outside the scope of this post.

The part where the biggest disagreement will come from, is that people will claim there are incentives against a big hash man owning several pools that make up the majority of hash rate.  This is obviously false.  There are no incentives against him taking this course of action, since he can do so in secrecy, there are only incentives against him making double spends.  I would argue that even if he isn't double spending the security model is broken.  If you accept this security model, there's no reason to not accept a security model of one guy always having 90% hashrate out in the open (not trustless, they can double spend at any time).

How this argument began:

only POW provably solves the byzantine generals problem in the face of sybil attack

Delegated proof of work, which Bitcoin is, doesn't.  If 70% of the hash rate is in china owned by three pools, you have no way of knowing these pools aren't owned by the same person (sybil).  The only way is to audit them yourself, which is the purpose of the voting mechanism in DPoS, to audit the block validators for sybil.  The only difference is, the audit mechanism is built into the protocol of DPoS and excluded entirely from Bitcoin (delegated proof of work).

[BitUsher]

Bitcoin is Byzantine resilient because of PoW and Game theory. Bitcoin follows Nakamoto consensus, but all Byzantine consensus algos are only resistant up to 51% or less.

The bigger question is how likely a 51% attack or sybil attack is within bitcoin and under what conditions can we make it less likely.

With PoW there is at least physical limitations and better signals that limit sybil attacks vs PoS. Nothing is trustless or completely immutable but we can get closer to these ideals with decentralization and the right security mechanisms.

[monsterer]

I feel this topic deserves it's own thread and would get stonewalled with popular opinion somewhere in the Bitcoin section.  My argument here is:

<r0ach> you can't solve byzantine generals problem with a probabilistic model unless you've first solved sybil with a probabilistic model and Bitcoin doesn't do that
<r0ach> because there's no way of telling if all pools are owned by the same person, then it's not collusion or 51% attack, it's a sybil attack
<r0ach> since the essence of the byzantine generals problem is sybil attack, dealing with sybil comes first in the hierarchy before byzantine generals is discussed at all

The Byzantine problem deals with a minority of actors or signal throwing off the consensus of the system or majority.  If you can't determine how many actors even exist in the first place, you're probably always going to lose this test.  This fact also probably gives credence to the deterministic # of block validators model.

Proof that Proof of work is the only solution to the byzantine generals problem:

ref: oleganza

The problem of blockchain synchronization is the following:

Imagine you are sitting in a bunker. You have no idea what people are out there and what are their intentions. You only receive some incoming messages from strangers that may contain anything. They can be just random garbage or deliberately crafted messages to confuse you or lie to you. You never know. You cannot trust anyone.e

The problem of "money" or any other "social contract" is that everyone should be able to know what the majority agrees to without trusting some intermediaries (otherwise they can easily obuse their special position). If everyone votes for "X", then you sitting in a bunker must somehow independently figure out that all those other people indeed voted for "X" and not for "Y" or "Z". But remember: you cannot trust anyone's message and messages are the only thing you get from the outside world.

When two propositions arrive into your bunker, "X" and "Y", we have no trusted reference point to figure out which one is supported by the majority of other people. We only have "data in itself" to judge which one we should choose as the main one. To make things simpler we are not trying to apply subjective judgement to either proposition, but only trying to make everyone agree to a single option. In case of Bitcoin it is a reasonable assumption: everyone is owner of their money, so no one really cares which version of the history is chosen as long as their own balance is respected.

So how X should be distinct from Y that we know for sure that no one can accidentally choose Y, Z or W? First property: this data should be "recent". So we know that we are not sitting on some old agreement while everyone else has moved onto something else. Second property: any "recent" alternative should be impossible to produce. Because if it was possible to produce, then there is always a chance that some number of people could see it and accept that alternative. And you have no way to estimate how many such alternatives exist and how many people accepted it (because you are sitting in a bunker and you cannot trust incoming messages or know how many message did you miss).

How do we define "impossible"? It means either of two things: either it is logically impossible, or it is practically (economically) impossible. If it is logically impossible, than we can know all future agreements in advance (like a deterministic chain of numbers), just by using induction. But this does not work because we'd have to have some agreement about starting point in the first place. So we end up with requiring practical impossibility. In other words we need the following:

"Message X should be provably recent and alternatives should be practically impossible to produce."

Practical impossibility can be reframed in terms of "opportunity cost": there are limited physical resources and those should have been largely allocated to X than to Y so we can see that X sucked in all resources from any alternatives. Because if it didn't, then there is a huge uncertainty about whether remaining resources are used for alternative Y or they do not interfere with the voting process. Is it possible that X did not suck in a lot of resources while alternatives are still not possible? Then it would mean that X logically follows from whatever previous state of the system and there is no voting process needed.

Therefore: message X should be provably recent and should have employed provably big amount of resources, big enough that there are not enough resources left for any alternative Y to produce in a reasonably short time frame. Also, the message X should be always "recent" and always outcompete any alternative. Because we cannot reliably compare "old" messages: is Y an "old" one that was just delivered now, or was it produced just now after resources spent on X were released?

This logically leads us to the following: we should accept only the messages with the biggest Proof-of-Work attached, and that proof-of-work should be the greatest possible ever, so there would not be any possibility for any alternative to be produce in the short window of time. And that proof-of-work must be constantly reinforced or the value of previous consensus begins to fade quickly as the opportunity for alternatives grows.

Expensive, highly specialized computer farms is the most reliable way to achieve consensus. If we were to use non-specialized resources, it would be harder to gauge whether the majority of them are indeed used for proof-of-work computations. By observing that enormous amount of work happens in a very specific, easy-to-observe part of the economy, we can estimate how expensive it is to produce an alternative, equally difficult message. In case of Bitcoin mining farms, such an alternative would require a very expensive and complex production chain, requring either outcompeting other firms that use chip foundries or building single use datacenters in the most cost-effective locations on the planet (with the cheapest electricity, coldest weather, low latency connectivity etc.)

Conclusion.

If achieving consensus in a non-trust manner is ever possible in practice, then it is only possible with a Proof-of-Work scheme and highly specialized expensive production chains. Also, consensus is only valuable for a short period of time so it must be constantly reinforced.

https://gist.github.com/oleganza/8cc921e48f396515c6d6

[monsterer]

Bitcoin is Byzantine resilient because of PoW and Game theory. Bitcoin follows Nakamoto consensus, but all Byzantine consensus algos are only resistant up to 51% or less.

Before satoshi, byzantine agreement models could only deal with 33% bad actors.

[BitUsher]

Bitcoin is Byzantine resilient because of PoW and Game theory. Bitcoin follows Nakamoto consensus, but all Byzantine consensus algos are only resistant up to 51% or less.

Before satoshi, byzantine agreement models could only deal with 33% bad actors.

Which is why I suggest Nakamoto and Byzantine algos can reach up to 51%. There is no denying the importance of PoW and Nakamoto consensus which is essentially a form of a pseudonymous Byzantine consensus. It only solves the Byzantine generals problem to a probabilistic degree of trust and not completely. we shouldn't overstate our case and suggest it solves the dilemma or consider bitcoin trustless. There is a real tangible crisis occurring where bitcoins security is both increasing as hash rate increases and decreasing as nodes drop and mining becomes centralized. This trend may reverse but no one has proven solutions yet.

[r0ach]

https://gist.github.com/oleganza/8cc921e48f396515c6d6

You can't use Bitcoin itself as an example of Byzantine consensus in an effort to justify it's own existence.  That page is moving the goal posts all around and adding a bunch of new variables that aren't even in the original problem.  All that page is doing is saying, Bitcoin works, therefore, the solution Bitcoin used is the answer.  Circular reasoning.


Battle of the century of r0ach vs smooth regarding this issue.  They call him "smooth" because it's like talking to Bill Clinton.  You tell me who won:

<@smooth> The BGP as usually stated has a concept of identity ("Generals") which is specificaly not part of the problem definition in Bitcoin (which is what makes it sybil resistant). Bitcoin doesn't care
<r0ach> I made the arguement that byzantine generals is a ridiculous ivory tower example with too many open ended variables and the only real problem is sibil prevention
<@smooth> yes and for the millionth time bitcoin is totally sybil resistant
<@smooth> because identity doesn't matter
<r0ach> it's not sybil resistant, all pools can be owned by the same guy
<@smooth> pools are not actors in bitcoin. hash rate is
<@smooth> hash rate can't be sybil attacked, it is a physcal property
<r0ach> hash rate doesn't decide vote, it's delegated proof of work (bitcoin), only the pool owner does
<r0ach> what hash does is irrelevant
<r0ach> you're letting satoshi decide what you can criticize or not
<r0ach> instead of using your own logic
<r0ach> to figure it out
<r0ach> because the model that exists is nothing like the PDF
<@smooth> well if you are critizing bitcoin, you are criticizing somethign he defined
<@smooth> if you want to redefine it, and then criticize that, that's perfect valid science, just make a specific definition first
<r0ach> bitcoin does not function in the way his PDF describes at all, so when you cite satoshi, it's pretty much meaningless in that context
<@smooth> I disagree
<@smooth> the only portion that does not apply is the convergence proof
<@smooth> but that is because of hash rate concentration, not because of pools
<@smooth> even with pools (and I'll admit this is not a precise argument), if 50% of hash rate is honest, pools can't do anything because the hash rate will quickly flee a dishonest pool
<@smooth> Note this is not true if KnC Bitfury etc. is not honest, because their hash rate can't flee
<@smooth> even 1 cpu 1 vote is actually true still
<@smooth> again, cpus are a physical entity, can't be sybiled
<r0ach> it doesn't matter what the hell the cpus are doing since you're going through a 2nd layer of abstraction known as delegation (pool)
<r0ach> and the 2nd layer takes precedent over the 1st
<@smooth> i would argue the opposite
<@smooth> the 1st takes precendence over the 2nd, because is I said, you pull your hash rate
<r0ach> yes, i can pull my hash rate AFTEr the attack has occurred
<r0ach> that's fault recovery, not fault tolerance
<r0ach> this is known as the long con, I'm sure you've heard of it

[monsterer]

Here's the battle of the century of r0ach vs smooth regarding this issue.  They call him "smooth" because it's like talking to Bill Clinton.  You tell me who won:

I suspect you are attempting to justify other consensus mechanisms by trying to find loopholes in definitions to prove a point. Satoshi did solve the byzantine problem in the face of sybil attack, it's been proven.

There have been other solutions, such as ripple's consensus - which is only resistant against 20% byzantine failures. By applying proof of work to the problem, satoshi was able to increase this to 50% which is the theoretical optimum.

Satoshi's solution is not perfect, of course - the pools centralise and ASICs worsen the situation, but the core of the idea is sound.

[monsterer]

<r0ach> yes, i can pull my hash rate AFTEr the attack has occurred
<r0ach> that's fault recovery, not fault tolerance
<r0ach> this is known as the long con, I'm sure you've heard of it

Re-reading this, I see the misunderstanding here. Byzantine agreement failure in satoshi's blockchain design are orphaned blocks. These are the misinformation, or disagreement between the generals. The way this disagreement is resolved (or recovered, using your own language) is by choosing the longest chain of work - this happens at the protocol level, not by mining pools agreeing to take an action.

[BitUsher]

I suspect you are attempting to justify other consensus mechanisms by trying to find loopholes in definitions to prove a point. Satoshi did solve the byzantine problem in the face of sybil attack, it's been proven.

Satoshi did not technically solve the byzantine problem, merely solved it in a probabilistic or pragmatic manner with game theory where someone is incentivized to secure the network instead of attack it. Sybil attacks can still occur by a persistent and motivated attacker but they are extremely expensive and because of PoW(vs PoS/PoI/DPoS) there are signals that can pre-emptively leak of a potential or upcoming attack. (I.E... If the NSA wanted to attack bitcoin they would need to either build a secret ASIC factory or start purchasing ASICs in large quantities. This would in turn signal a concern to the manufacturers and the greater community with unexpected rising ASIC costs or a leaker would let the community know of the secret ASIC factory)

With PoS/PoI/DPoS a sybil attack can come without any notice and with potentially much cheaper costs. (No, an attacker need not have to "buy" coins to attack, They can create an exchange/bank that pays interest/dividends to corner a good chunk of coins 5-30% needed depending upon the algo, Or they can create a popular wallet with a backdoor, Or they can compromise several large bagholders computers, Or a few large holders could short and attack their own coin, ect..)

[r0ach]

I suspect you are attempting to justify other consensus mechanisms

No, I'm proving that Bitcoin doesn't function at all like the PDF states.  Words used like "trustless" are obviously not correct because a second layer of abstraction was added (pools) that invalidates much of what he says about voting.  You're not participating in democracy, you're participating in a republic.  If it was trustless, it would be a democracy.  This is why PoW is a less efficient, worse scaling, resource wasting form of DPoS.  They're both republics.  One is designed to be that way, the other reaches the same conclusion by creating a Rube Goldberg machine that eats megatons of coal and spits out a less decentralized, lower performing system afterwards.  Both systems are republics, both systems are delegation, denying it is intellectually dishonest.

by trying to find loopholes in definitions to prove a point.

If by "loopholes in definitions" from your quote, you mean me stating that it's easier to collude with myself (sybil in the form of the same entity owning the 3 high hash rate pools) than it is to collude with other people who own pools?  Most consensus models seem to make a large differentiation in the two.  They aren't the same.  Like I said, it's not collusion, it's a sybil attack.  There is no prevention mechanism against it in Bitcoin either.  The actor can do so in complete secrecy, eternally, until whenever he wants to pull a long con or other strategy.  Some coins like Darkcoin and Vanillacoin try to use collateral requirement (coins) to create a node.  All this does is put an upper limit on the number of sybil nodes you can produce.

[BitUsher]

If it was trustless, it would be a democracy.  This is why PoW is a less efficient, worse scaling, resource wasting form of DPoS.  They're both republics.  One is designed to be that way, the other reaches the same conclusion by creating a Rube Goldberg machine that eats megatons of coal and spits out a less decentralized, lower performing system afterwards.  Both systems are republics, both systems are delegation, denying it is intellectually dishonest.

PoW may be less efficient than DPoS(some would argue this would eventually change as evidenced by expensive elections), but certainly not more effective. There has already been plenty of examples where miners have left pools in anticipation of a potential attack. Additionally, many miners are setup with fallback pools or to switch between pools in event problems arise.

This is not to say that pools create no security weaknesses or concerns , merely you are overstating your case. Additionally, it is possible for these trends to reverse themselves with proper incentives set in place to cover the cost or reward p2p pools.

If it was trustless, it would be a democracy.  

What an odd statement to make. How is trust in anyway related to democracies? Pure Democracies are far from trustless and consist of two wolves and a sheep deciding whats for dinner. No cryptocurrency is trustless... people really need to stop using that term inappropriately.

[r0ach]

If it was trustless, it would be a democracy.  

What an odd statement to make. How is trust in anyway related to democracies? Pure Democracies are far from trustless and consist of two wolves and a sheep deciding whats for dinner. No crypto is trustless... people really need to stop using that term inappropriately.

Not odd at all.  I guess I should refine my statement with the words "direct democracy" or something.

[BitUsher]

Not odd at all.  I guess I should refine my statement with the words "direct democracy" or something.

This is over simplified. Double spends/DOS attacks can occur at much lower thresholds of hashing power than 51%. The bitcoin blockchain isn't exclusively controlled by miners either but split between miners and nodes with separate voting and separate powers granted to each. Indirectly developers, exchanges, wallets, and merchants have a large role as well.

Politically, bitcoin doesn't represent republics/democracy either because all users have ultimate veto power and can break consensus at any moment by forking or just choosing not to upgrade to new changes they disagree with(thus causing a fork). It is more similar to certain forms of anarchy in nature because of this quality.

Would you call I completely voluntary and open governance model that allows for any user(citizen) to instantly veto any change they disprove of a republic/democracy? The smaller fork has every right to call their currency bitcoin regardless of the majorities objections.

[r0ach]

This is over simplified.  The smaller fork has every right to call their currency bitcoin regardless of the majorities objections.

Gavin would be the confederacy in that case.

[BitUsher]

This is over simplified.  The smaller fork has every right to call their currency bitcoin regardless of the majorities objections.

Gavin would be the confederacy in that case.

I don't agree with Gavin/Hearn and believe they made some mistakes with consensus and XT, but they aren't the enemy or boogeymen and have made great contributions to the bitcoin ecosystem. In fact their insistence and persistence is forcing other hands to really tackle this issue with some creative solutions and great research.

[smooth]

Satoshi did not technically solve the byzantine problem, merely solved it in a probabilistic or pragmatic manner with game theory where someone is incentivized to secure the network instead of attack it.

Yes that's exactly right and I explained this on another of one of r0ach's thread spam Sybils.

There is a globally unique longest chain, although your confidence that you know what it is depends on the distribution of hash rate in the network.

The issue of resistance to attack is one of a tradeoff between concentration of hash rate and the rate with which confidence in an apparently-longest chain being the correct chain increasing over time. This is seen in Satoshi's paper where he analyzes the case of a single 45% attacker and concludes that you would need to wait 340 confirmations for 1/1000 confidence (which isn't even that strong if the exposure is high).

He doesn't generally discuss the question of concentration though, outside of an explicit "attack". In fact the issue has broader implications.

There is an enormous amount of concentration now that does't come from pools. This has the same effect of weakening the security model that pools do, or possibly worse (since you can't pull hash rate from KnC if they decide to misbehave).

In the future this will likely evolve in one of three ways: 1) increased concentration, decreased value and increased irrelevance; 2) continued equilibrium between some degree of "acceptable concentration" and limited value and relevance; or 3) a break from the status quo where concentration decreases due to limits to economy of scale and commoditization of ASICs along with increased value and relevance (perhaps enormously so).

[BitUsher]

There is an enormous amount of concentration now that does't come from pools. This has the same effect of weakening the security model that pools do, or possibly worse (since you can't pull hash rate from KnC if they decide to misbehave).

This is one reason why cloudmining must be avoided like the plague(or possibly exposing you to a ponzi) , and another incentive structure must be developed to encourage decentralized p2p mining.

Switching to an ASIC resistant PoW coin doesn't solve this problem but merely delays the inevitable. As interest and hash power grows ASICS will be developed within time regardless.

This is why their is such a contentious debate between raising the blocksize limit. The people in favor of smaller blocks know the mining is already heavily centralized and that fight may be lost (without a novel solution) and want to at minimum keep node count high and decentralized to balance the centralization of mining.

[Come-from-Beyond]

Bitcoin is Byzantine resilient because of PoW and Game theory. Bitcoin follows Nakamoto consensus, but all Byzantine consensus algos are only resistant up to 51% or less.

Before satoshi, byzantine agreement models could only deal with 33% bad actors.

Bitcoin is resistant to 33% only, 51% number was mistakenly calculated without taking Selfish Mining into account.

[monsterer]

No, I'm proving that Bitcoin doesn't function at all like the PDF states.  Words used like "trustless" are obviously not correct because a second layer of abstraction was added (pools) that invalidates much of what he says about voting.  You're not participating in democracy, you're participating in a republic.  If it was trustless, it would be a democracy.  This is why PoW is a less efficient, worse scaling, resource wasting form of DPoS.

Your idea of a proof is something that I don't recognise. I'm not entirely sure what kind of government you have where you live, but where I live, you have to trust politicians, and that trust is abused on a regular basis.

POW is nothing like DPOS. DPOS is just plain POS turned on its head with a deterministic block production order. It is a reactive design subject to all kinds of social engineering attacks on top of the regular nothing at stake attacks. Producing a block costs nothing, therefore neither does attacking the chain.

[Come-from-Beyond]

Producing a block costs nothing, therefore neither does attacking the chain.

The gap is pretty large and "therefore" is not enough here. The fact that we don't observe such attacks hints that you are plain wrong.