Satoshi didn't solve the Byzantine generals problem

[TPTB_need_war]

Please respect canonical definitions. Byzantine 'agreement' is not what we are talking about in this thread. We are talking about Byzantine fault tolerance. The definitions are on Wikipedia:

I'm tired of repeating myself. Here is an entire paper which proves that bitcoin did solve the BGP: http://nakamotoinstitute.org/static/docs/anonymous-byzantine-consensus.pdf

That paper is flawed. For example,

What really matters is that ownership of the currency is undisputable - everyone can agree on who owns what.

Yet the paper never addresses the issue that no one can know when all observers agree or not on who has lost access due to censored transaction or victim of a double spend (a double spend has a loser and winner but who can prove the loser the victim). The majority hashrate is forced on all observers, regardless. That is not the definition of fault tolerance. Consistency of observer experience is violated. The CAP theorem requires that if Partition tolerance is not allowed (due to the single longest chain partition rule) then either Access or Consistency must be lost.

Monsterer I grow very weary of your proclamations which are nearly always short-sighted. You demand I go do the work that you didn't do. And that isn't fair to me. Just because a white paper claims to prove something, doesn't mean it did.

[Come-from-Beyond]

Suggest a link and I will add it to the linked post. Then I will delete this post.

Is it a joke? My point was that that thread didn't contain the proof. How do you think I'll find the proof if there is none from my point of view? What about you linking to the actual proof instead of giving looping references?

[TPTB_need_war]

Suggest a link and I will add it to the linked post. Then I will delete this post.

Is it a joke? My point was that that thread didn't contain the proof. How do you think I'll find the proof if there is none from my point of view? What about you linking to the actual proof instead of giving looping references?

I have not claimed the word 'proof' and I specifically stated in that linked Decentralization thread that I have not endeavored to produce a formal proof. If you would like me to add a link to your best post in that Decentralization thread where you presented your stance, then please suggest a link.

[Come-from-Beyond]

I have not claimed the word 'proof' and I specifically stated in that linked Decentralization thread that I have not endeavored to produce a formal proof. If you would like me to add a link to your best post in that thread where you presented your stance, then please suggest a link.

So you claim that Iota consensus can't converge but there is no a formal proof? What about a non-formal one?

[TPTB_need_war]

I have not claimed the word 'proof' and I specifically stated in that linked Decentralization thread that I have not endeavored to produce a formal proof. If you would like me to add a link to your best post in that thread where you presented your stance, then please suggest a link.

So you claim that Iota consensus can't converge but there is no a formal proof? What about a non-formal one?

I have presented my logic to back my claim in the Decentralization thread. You are free to disagree. Everyone on these forums is free to express their logic.

[Come-from-Beyond]

I have presented my logic to back my claim in the Decentralization thread. You are free to disagree. Everyone on these forums is free to express their logic.

Got it. I'll back this reply up via WebArchive site and present it every time I see someone saying something like "AnonyMint states that Iota consensus doesn't converge" so people won't think that you provided a proof of that claim.

[TPTB_need_war]

I have presented my logic to back my claim in the Decentralization thread. You are free to disagree. Everyone on these forums is free to express their logic.

Got it. I'll back this reply up via WebArchive site and present it every time I see someone saying something like "AnonyMint states that Iota consensus doesn't converge" so people won't think that you provided a proof of that claim.

Don't lie. I stated it will converge because you are enforcing centralization.

[Come-from-Beyond]

Don't lie. I stated it will converge because you are enforcing centralization.

Oh, thx, forgot centralization part. So you position is that it can't converge without centralization but it's hard to get your logic without reading that long thread. Fixed.

EDIT: Maybe you should find time and provide a brief explanation, so noone will think that you try to evade something by making excuses. The reference to those 33 pages look as an excuse to me, a solid idea doesn't need walls of text to explain.

[TPTB_need_war]

Don't lie. I stated it will converge because you are enforcing centralization.

Oh, thx, forgot centralization part. So you position is that it can't converge without centralization but it's hard to get your logic without reading that long thread. Fixed.

Agreed. Thx.

And note I am claiming every coin design is centralized (or heading there).

I contemplate a design that has decentralized control over centralized verification, but I have nothing to show but words at this point.

[smooth]

Thus per the definition, Satoshi's PoW design is not Byzantine fault tolerant, because the metric of when it is fault tolerant is ill defined (can't be measured). An unknowable state is as reliable (fault tolerant) and a random result, thus no reliability exists.

This is exactly the same as the Byzantine Generals Problem, which is solved up to 1/3 faulty generals (and only then, unless you add externally-assigned identities and unforgeable messages). If there are >1/3 faulty generals, then the honest generals can not determine that they are being tricked, so they will commence a doomed attack and they will all die. This is fault tolerant up to 1/3 traitor generals but not beyond. There is no way for the honest Generals to measure the number of traitor generals. If they could, they would not be tricked into attacking and die.

Likewise, in Bitcoin if there is <50%* faulty hash rate, then there is no effective censorship and functional consensus (including on there being no effective censorship). If there is too much faulty hash rate, then the rest of the system can not measure the faulty hash rate and it can not determine that it is being tricked.

In both cases, an outside observer who is able to see all the interactions can tell the system has failed. Within the system you can not.

[TPTB_need_war]

Thus per the definition, Satoshi's PoW design is not Byzantine fault tolerant, because the metric of when it is fault tolerant is ill defined (can't be measured). An unknowable state is as reliable (fault tolerant) and a random result, thus no reliability exists.

This is exactly the same as the Byzantine Generals Problem, which is solved up to 1/3 faulty generals (and only then, unless you add externally-assigned identities and unforgeable messages). If there are >1/3 faulty generals, then the honest generals can not determine that they are being tricked, so they will commence a doomed attack and they will all die. This is fault tolerant up to 1/3 traitor generals but not beyond. There is no way for the honest Generals to measure the number of traitor generals. If they could, they would not be tricked into attacking and die.

Likewise, in Bitcoin if there is <50%* faulty hash rate, then there is no effective censorship and functional consensus (including on there being no effective censorship). If there is too much faulty hash rate, then the rest of the system can not measure the faulty hash rate and it can not determine that it is being tricked.

In both cases, an outside observer who is able to see all the interactions can tell the system has failed. Within the system you can not.

Who claimed it is solved with 1/3[2/3] of the generals are honest!

That is the statement of the problem. The problem is not fault tolerant!

The only fault tolerant design for a solution is with centralization which obviously doesn't address the requirements of the problem, .e.g as you say "unless you add externally-assigned identities and unforgeable messages".

Thus I wrote upthread there is no solution to BGP. The problem will never be solved as stated.

[Come-from-Beyond]

Thus I wrote upthread there is no solution to BGP. The problem will never be solved as stated.

Can this - https://en.wikipedia.org/wiki/Paxos_(computer_science) - help you somehow in your mission of decentralized money creation?

[smooth]

Thus per the definition, Satoshi's PoW design is not Byzantine fault tolerant, because the metric of when it is fault tolerant is ill defined (can't be measured). An unknowable state is as reliable (fault tolerant) and a random result, thus no reliability exists.

This is exactly the same as the Byzantine Generals Problem, which is solved up to 1/3 faulty generals (and only then, unless you add externally-assigned identities and unforgeable messages). If there are >1/3 faulty generals, then the honest generals can not determine that they are being tricked, so they will commence a doomed attack and they will all die. This is fault tolerant up to 1/3 traitor generals but not beyond. There is no way for the honest Generals to measure the number of traitor generals. If they could, they would not be tricked into attacking and die.

Likewise, in Bitcoin if there is <50%* faulty hash rate, then there is no effective censorship and functional consensus (including on there being no effective censorship). If there is too much faulty hash rate, then the rest of the system can not measure the faulty hash rate and it can not determine that it is being tricked.

In both cases, an outside observer who is able to see all the interactions can tell the system has failed. Within the system you can not.

Who claimed it is solved with 1/3 of the generals are honest!

(<1/3 are dishonest as I wrote above)

Lamport et al.

"It is shown that, using only oral messages, this problem is solvable if and only if more than two-thirds of the generals are loyal"

http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf

That is the statement of the problem. The problem is not fault tolerant!

The only fault tolerant design for a solution is with centralization which obviously doesn't address the requirements of the problem, .e.g as you say "unless you add externally-assigned identities and unforgeable messages".

Thus I wrote upthread there is no solution to BGP. The problem will never be solved as stated.

Thus if you claim it is not solvable, then you have either found an error in their proof, or you have redefined the problem in your own way. I suspect the latter.

As with all such systems, fault tolerance is achieved up to a specified number of faults, and no farther.

[Come-from-Beyond]

Thus if you claim it is not solvable, then you have either found an error in their proof, or you have redefined the problem in your own way. I suspect the latter.

As with all such systems, fault tolerance is achieved up to a specified number of faults, and no farther.

If messages of the generals can't be faked then even 99 of 100 traitors is not a problem. I think he didn't redefine the problem, more likely he just forgot to provide some details.

EDIT:

From that paper:

With unforgeable written messages, the problem is solvable for any number of generals and possible traitors.

[smooth]

Thus if you claim it is not solvable, then you have either found an error in their proof, or you have redefined the problem in your own way. I suspect the latter.

As with all such systems, fault tolerance is achieved up to a specified number of faults, and no farther.

If messages of the generals can't be faked then even 99 of 100 traitors is not a problem. I think he didn't redefine the problem, more likely he just forgot to provide some details.

EDIT:

From that paper:

With unforgeable written messages, the problem is solvable for any number of generals and possible traitors.

No, he mentioned that in his reply, as I did earlier.

.e.g as you say "unless you add externally-assigned identities and unforgeable messages".

He just fails to acknowledge that "Byzantine fault tolerance" only succeeds up to a threshold of faults.

"Correctly functioning components of a Byzantine fault tolerant system will be able to provide the system's service, assuming there are not too many faulty components" https://en.wikipedia.org/wiki/Byzantine_fault_tolerance

You can specify a high threshold but that greatly constrains the available solutions (in my opinion to largely if not entirely useless ones in the context of cryptocurrencies, but not everyone necessarily agrees). Arguably a low threshold is also largely useless (it seems somewhat fewer, at least within the cryptocurrency community, agree with this statement), which would mean there are no very useful cryptocurrencies possible. That would not surprise me much.

[jyakulis]

It amazes me people are thinking this hard about what I already thought about.

Stop thinking so much and try something is my best advice. Throwing a bunch of shit at the wall and seeing what sticks has served me well.

Game theory? Sweet I saw that movie. Didn't that start with figuring out which chick you could bonk easiest?

[Come-from-Beyond]

No, he mentioned that in his reply, as I did earlier.

.e.g as you say "unless you add externally-assigned identities and unforgeable messages".

Ah, right, somehow I overlooked this in front of my nose.

[TPTB_need_war]

My reply to CfB and smooth follows.

The Byzantine Generals Problem (BGP) is at its generate essence (i.e. conditions IC1 and IC2 in the white paper) whether a commanding general can collect the vote (e.g. 'attack' or 'retreat', or other information subject to a consensus) of the other generals and relay that result to other decentralized generals and have the vote of the loyal generals reflect the consensus, but without trusting that the commanding general is loyal. This is functionally equivalent to the case of each loyal general computing the vote independently (i.e. conditions 1 and 2 of the white paper).

Afaics the paper has an important omission which is that when the disloyal generals (traitors) are not colluding (i.e. can't trust each other) then they have no reliable means to disrupt the loyal consensus. So my analysis will focus on the case where the disloyal generals are colluding.

The paper does not also explicitly state that at any number of loyal generals other than exactly 2/3 (wherein the result will be inconclusive 50/50 conflict and failure of consensus), then it is undecidable (from the perspective of each general) whether the consensus result reflects loyalty or disloyalty.

Thus although the paper is correct to state that BGP is solvable if the 2/3 + 1 of the generals are loyal (i.e. 3m + 1 total generals for m traitors), the only way to know that precondition is for the system to be centralized so that the count of the traitors is known. Thus the white paper is poorly written (w.r.t. this issue) because it does not explain that there is no decentralized, trustless solution to the BGP and insinuates the opposite in the mind of the naive reader.

No loyal general ever knows if the system is loyal or not.

There is no decentralized solution to the BGP problem. Period.

(note also that the definition of oral messages assumes conditions A1, A2, and A3 which can't exist in a decentralized network where Sybil attacks are possible)


Damn my illness really restricts me. Normally I would go off on a tangent thinking about how such points ripple into the Halting theorem and unbounded recursion of Turing completeness, but I can barely sustain the mental focus to do the above. I need to get cured. This is really fucking me up.

[Come-from-Beyond]

Afaics the paper has an important omission which is that when the disloyal generals (traitors) are not colluding (i.e. can't trust each other) then they have no reliable means to disrupt the loyal consensus.

This is a good observation, the results should differ depending on capabilities of the traitors and some traitors may compete with each other unintentionally helping the good guys.

PS: By the way, classical BGP mentions somewhere that traitors collude AFAIK.

[monsterer]

Thus although the paper is correct to state that BGP is solvable if the 2/3 + 1 of the generals are loyal (i.e. 3m + 1 total generals for m traitors), the only way to know that precondition is for the system to be centralized so that the count of the traitors is known. Thus the white paper is poorly written (w.r.t. this issue) because it does not explain that there is no decentralized, trustless solution to the BGP and insinuates the opposite in the mind of the naive reader.

No loyal general ever knows if the system is loyal or not.

There is no decentralized solution to the BGP problem. Period.

Another poor conclusion. If the set of all traitors was known a priori, the system would be tollerant to any bound! That is the entire point of the problem; the set of traitor generals is unknown.