Pages:
Author

Topic: Satoshi didn't solve the Byzantine generals problem - page 11. (Read 13680 times)

legendary
Activity: 1260
Merit: 1000
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.
legendary
Activity: 994
Merit: 1035
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..)
legendary
Activity: 1008
Merit: 1007
yes, i can pull my hash rate AFTEr the attack has occurred
that's fault recovery, not fault tolerance
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.
legendary
Activity: 1008
Merit: 1007
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.
legendary
Activity: 1260
Merit: 1000

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
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
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
hash rate doesn't decide vote, it's delegated proof of work (bitcoin), only the pool owner does
what hash does is irrelevant
you're letting satoshi decide what you can criticize or not
instead of using your own logic
to figure it out
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
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
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)
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
yes, i can pull my hash rate AFTEr the attack has occurred
that's fault recovery, not fault tolerance
this is known as the long con, I'm sure you've heard of it
legendary
Activity: 994
Merit: 1035
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.
legendary
Activity: 1008
Merit: 1007
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.
newbie
Activity: 1
Merit: 0
how likely is a 51% attack or sybil attack within bitcoin and under what conditions can we make it less likely.

under conditions of decreasing number of profitable miners/pools which is why we are talking about this (reactively again of course)..your first question is impossible to know for certain without access to unknown info about the miners.  too many varriables

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

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.  

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.  

whats it been like 2 years now that we've been preaching this magic called math?

just like how bitcoin is all about big numbers giving us security, the math behind this "late in the game" "global stage degree of decentralization" becomes more complex and indeterminate once you cross the threshold where mining pools start to coalesce due to unprofitability.  and of course.. couple that with the fact that you could never know what the other guys are thinking and gaming, etc... there are just too many variables to analyze as accurately as you could when you were describing a system with a total number of nodes that did not exceed the total number of your fingers and toes.  

in bitcoin's younger days, it was more transparent and easy to see that its initial centralized small community of 1 then 2 then 3...etc..had grown into a global, and of course, more decentralized organism... this was a gigantic feat but mathematically simple to prove that the network had obviously become more decentralized than it had been after genesis.. but then how to you measure the change in decentralization on a global scale?  That's where Bitcoin2.0 forked and we started building the first gargantuan global scale smartchain that had to be more physically (based on HARDWARE LOCATION) decentralized... thats of course when then things got fuzzy...

not from all the hookers and blow, but because: once bitcoin was at the physical size of a global hardware unit, and all the big money has been made from the growth phase (and halvings instead of doublings due to the fact that it is a deflationary currency), then the maintenance phase takes over (you want a deflationary currency, then this is what you get)(deflation)...now you have to maintain the mainframes that are unprofitable without the continuing influx of new cash from new users...Just like how the oil drillers stopped opening up new wells when the oil price crashed last year, nobody opens bitcoin mines anymore either in this identical deflationary economic scenaro..

So like Chuck ponzi in search of his next buck... without continuous growth, more miners turn off their unprofitable rigs and leave it to the big guy who just might be your brother......

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

Bitcoin was born, and grew up strong, then became weak in its old age, unable to support itself under the strain of unprofitability.  .. ... please buy BTC to keep another miner alive... help them pay for their electricity to run the fans that are keeping his house from catching fire... or like rOach says, pitch your burnt out ASIC in the garbage can with all the rest of your underutilized technological masterpieces that were only useful for a blink of your lifetime and be still and know that Satoshi and Co. control the majority of the bitcoin mines...

and who knows.. maybe he always did (its impossible to prove otherwise)

http://i3.cpcache.com/product/697015910/be_still_know_that_i_am_god_surgeonpng_classic_th.jpg?height=225&width=225
(hint.. its not the size that counts here)
legendary
Activity: 1008
Merit: 1007
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:

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

Quote
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
legendary
Activity: 994
Merit: 1035
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.
legendary
Activity: 1260
Merit: 1000
(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:

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
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
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).
Pages:
Jump to: