Satoshi didn't solve the Byzantine generals problem

[HCLivess]

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.

Yes, for PoS the security is exponential to amount of users

[rnicoll]

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.

Yes, for PoS the security is exponential to amount of users

Except that major exchanges tend to hold vastly more coins than individuals, so they replace mining pools in being the 51% risk, and (much) worse, their mining security can be anonymously and easily moved if it's accessed by a hacker. See for example MintPal (Viacoin) and Bter (NXT)

[monsterer]

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.

I'm not sure what gap you are referring to?

A double spend in POS has a constant cost proportional to the amount of stake you own. In POW, the cost is superlinear in the number of blocks you produce.

[BitUsher]

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.

I'm not sure what gap you are referring to?

A double spend in POS has a constant cost proportional to the amount of stake you own.

Yes, for PoS the security is exponential to amount of users

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

[monsterer]

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

These are social engineering attacks, of course.  I guess the equivalent in POW would be to 'borrow' someone's server farm.

[BitUsher]

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

These are social engineering attacks, of course.  I guess the equivalent in POW would be to 'borrow' someone's server farm.

Some of it does involve Social engineering, yes. The distinction between PoW and PoS/PoI/DPoS is that several of these attack vectors cannot be accomplished with PoW. With PoW all you can do is steal the account holders coins with a mtgox, ponzi scheme, or when a large bagholder is compromised. With PoS you can also attack the network and steal other peoples coins as well. Additionally, a compromised wallet cannot attack the network with a 51% attack with PoW as in PoS.

I suppose one could social engineer their way into Ant-pools mine and covertly reflash the firmware on all the miners. This attack would be much more difficult to do because large farms have multiple engineers who look over things and they have to constantly check their equipment and have large incentives to keep ontop of everything because of razor thin profit margins.  

It is no surprise that many PoS coins use checkpoints to add another security layer which is essentially centralization by a few developers approval. Checkpoints don't prevent these attacks just narrow the window of attack which is absolutely no problem. Developers Like Vitalik have studied these security weaknesses long and hard and despite desperately wanting to use some form of TaPoS for security still have not found an acceptable solution to mitigate these threats.  

Perhaps one day someone will develop a solution for PoS, until than both bitcoin and all other coins need a lot of work to improve security.

[r0ach]

Sybil attacks can still occur by a persistent and motivated attacker but they are extremely expensive (in PoW)

In my original post I give an example of why that's not true.  The same guy can own all the big PoW hashing pools in secrecy, which is a sybil attack, not collusion.  He can operate profitably the entire time and initiate the long con or other strategy whenever he wants.

[monsterer]

In my original post I give an example of why that's not true.  The same guy can own all the big PoW hashing pools in secrecy, which is a sybil attack, not collusion.  He can operate profitably the entire time and initiate the long con or other strategy whenever he wants.

The only thing he needs to do is to buy all that mining hardware.... Oh, and to produce some blocks... the cost of which is superlinear in the number of blocks...  Mmmm....

[smooth]

In my original post I give an example of why that's not true.  The same guy can own all the big PoW hashing pools in secrecy, which is a sybil attack, not collusion.  He can operate profitably the entire time and initiate the long con or other strategy whenever he wants.

The only thing he needs to do is to buy all that mining hardware.... Oh, and to produce some blocks... the cost of which is superlinear in the number of blocks...  Mmmm....

No there is a social engineering attack at work. r0ach wants to rename it as a sybil attack, which isn't entirely wrong since the social engineering attack does use a sybil technique.

By making pools appear smaller they encourage independent miners to (continue to) send hash rate there. Thus the evil pool operator doesn't need buy the hash rate himself, he's tricking miners into letting him use it.

Without the social engineering component the pool sybil attack doesn't really do anything. Split a 50% pool into five 10% pools and you still only have 50%.

[Marlo Stanfield]

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.

Yes, for PoS the security is exponential to amount of users

Except that major exchanges tend to hold vastly more coins than individuals, so they replace mining pools in being the 51% risk, and (much) worse, their mining security can be anonymously and easily moved if it's accessed by a hacker. See for example MintPal (Viacoin) and Bter (NXT)

MintPal was Vericoin rather than Viacoin(PoW), just fyi. That was a legit attack that resulted in an attacker having control of a large enough amount of VRC to cause VRC users to choose to roll back as the lesser of two evils(debatable of course, but I remember the dev making a decent argument that it was pretty much the only option aside from complete death).

BTER's NXT being hacked is a completely different an unrelated situation though. It was simply a hacker stealing around 50m NXT. There was no resulting security issue with this theft in regards to the NXT network. Mounting a successful attack on NXT appears to be extremely difficult from what I can tell.

[monsterer]

By making pools appear smaller they encourage independent miners to (continue to) send hash rate there. Thus the evil pool operator doesn't need buy the hash rate himself, he's tricking miners into letting him use it.

True. I suppose creating a fake pool for a long con is equivalent to creating a fake exchange to gather POS coins with which to vote... With the exception that the fake pool will be at capacity for the attack, whereas the exchange voting with stake is much harder to detect, and is passive.

[iCEBREAKER]

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

Even if KnC/Bitfury/etc. were >50% and dishonest, the socioeconomic majority can flee their corrupted PoW by forking to something besides SHA256.

So smooth won, but for a reason not explained.   

[smooth]

Even if KnC/Bitfury/etc. were >50% and dishonest, the socioeconomic majority can flee their corrupted PoW by forking to something besides SHA256.

Not clear that isn't just a treadmill though. If SHA256 became corrupted than given the same structure something else might very well become corrupted too.

Various arguments could be made about difference in absolute time, relative ASIC-resistance of the function, etc. but I'm not sure how compelling they are.

[smooth]

By making pools appear smaller they encourage independent miners to (continue to) send hash rate there. Thus the evil pool operator doesn't need buy the hash rate himself, he's tricking miners into letting him use it.

True. I suppose creating a fake pool for a long con is equivalent to creating a fake exchange to gather POS coins with which to vote... With the exception that the fake pool will be at capacity for the attack, whereas the exchange voting with stake is much harder to detect, and is passive.

Agree, and not just a single fake exchange either. There could be all manner of corrupt platforms and investment schemes that exist, at least in part, to collect stake. In fact the market forces kind of dictate this, since such platforms and vehicles can likely pay a higher yields than honest ones. Furthermore they are paying those yields in units where they, alone, with privileged knowledge of their future plans, have good visibility as to underlying value. Not really so different from the fiat banking system in a lot of ways.

[monsterer]

I'm just going to leave this here for reference purposes:

Anonymous Byzantine Consensus from
Moderately-Hard Puzzles: A Model for Bitcoin

http://nakamotoinstitute.org/static/docs/anonymous-byzantine-consensus.pdf

[TPTB_need_war]

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

These are social engineering attacks, of course.  I guess the equivalent in POW would be to 'borrow' someone's server farm.

Some of it does involve Social engineering, yes. The distinction between PoW and PoS/PoI/DPoS is that several of these attack vectors cannot be accomplished with PoW. With PoW all you can do is steal the account holders coins with a mtgox, ponzi scheme, or when a large bagholder is compromised. With PoS you can also attack the network and steal other peoples coins as well. Additionally, a compromised wallet cannot attack the network with a 51% attack with PoW as in PoS.

I suppose one could social engineer their way into Ant-pools mine and covertly reflash the firmware on all the miners. This attack would be much more difficult to do because large farms have multiple engineers who look over things and they have to constantly check their equipment and have large incentives to keep ontop of everything because of razor thin profit margins.  

It is no surprise that many PoS coins use checkpoints to add another security layer which is essentially centralization by a few developers approval. Checkpoints don't prevent these attacks just narrow the window of attack which is absolutely no problem. Developers Like Vitalik have studied these security weaknesses long and hard and despite desperately wanting to use some form of TaPoS for security still have not found an acceptable solution to mitigate these threats.

[...]

I have added the above quote to my epic post about all the flaws in PoS.

[TPTB_need_war]

<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

I made this same point in either 2013 or 2014.

Afaics, the only solution is unprofitable PoW which is the design I am now pursuing.

[TPTB_need_war]

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

I believe it is possible to design a memory hard PoW that is not electrically more efficient on an ASIC, but it will be very slow. I originally didn't think so, but have since realized I had a mistake in my 2013/4 research on memory hard hashes. It is possible that Cuckoo Hash already achieves this, but it is more difficult to be certain and it is very slow when DRAM economics are maximized (although it adds asymmetric validation which is important for DDoS rejection if the transaction signatures are ECC and not Winternitz and for verification when PoW share difficulty can't be high because each PoW trial is so slow).

Cryptonote's memory hard hash can't possibly be ASIC resistant, because by my computation it could not possibly have 100 hashes/second on Intel CPUs and be ASIC resistant.

See also Zcash's analysis thus far.

[monsterer]

<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

I made this same point in either 2013 or 2014.

Afaics, the only solution is unprofitable PoW which is the design I am now pursuing.

Bitcoin solves the byzantine generals problem within the bounds of the assumptions in the model. If one entity controls a majority of hashing power, that is outside of the bounds.

[TPTB_need_war]

<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

I made this same point in either 2013 or 2014.

Afaics, the only solution is unprofitable PoW which is the design I am now pursuing.

Bitcoin solves the byzantine generals problem within the bounds of the assumptions in the model. If one entity controls a majority of hashing power, that is outside of the bounds.

Circular logic. Bitcoin didn't solve the Sybil attack problem when pools control 51% and no one can know whether they do and reroute their PoW shares.