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

Yup but the 'set' remains unknown in the conditional solution (conditioned on only the 'count') offered by that white paper. You are wrong and there was no "poor conclusion" on my part. And what is with your condescending use of the word "another" since your prior attempt of presenting a white paper was also rebutted successfully by me.

And that it is conditional, is why I rebutted smooth upthread that he was stating the problem—not the solution—in the decentralized context because the count can only be conjectured (e.g. probabilistic estimates of hardware failure which was the focus of the paper) in a centralized (non-Sybil attacked application).

monsterer you are boastfully filling the thread with errors and useless noise. Stop the boastful and condescending and take more time to think over your points, so our discussion can remain high S/N and mutually respectful. When I asked you in the past to please cut down on the noise, you might have taken this personally. Sorry but I have limited bandwidth and time. So do readers. Try to make high quality contributions. I am suffering from an illness and it doesn't help when you shoot my cortisol sky high! And make very strong statements which require me to go read a white paper that I don't have time and energy to read. At least show that you aren't wrong most of the time, so you aren't being disrespectful of my limitations.

Edit: I can sincerely appreciate your contribution and also be totally unable to accept it if the S/N ratio is too low, because I have finite resources to expend here.

For a moment, just consider this; you are saying that there is no solution to BGP in trustless anonymous systems, but: If you take a snapshot of the current bitcoin hash rate and equally divide it out between N generals of fixed and equal hash rate, this is now classical BGP. You must be forced to concede that you are in fact saying that there is no solution to BGP at all, which is clearly false.

Both the set of, and the count of traitor generals are unknown in BGP; that is the specification of the problem.

monsterer I am sad to conclude that you've turned into a time wasting Dunning-Kruger troll with a chip on your shoulder.

Your reading comprehension sucks! I wrote about the 'number/count of' not the 'set of' (where the latter requires knowing which of the generals are the traitors, not just the count of traitors).

There is no fault in my logic. Sorry dude.

They can't be forged in the traditional sense, but if a traitor has 2x the hashing power of a loyal general, he can replace the message from the loyal general with an identical message* (and then another one) at the same block height.

*) basically, a block with identical contents, signed by the traitor instead of the loyal general

They can't be forged, but the sender isn't known either, so the problem specification is different, which is what I've been saying all along. I don't know whether a proper reduction is possible. Maybe that paper from Andrew Miller does something along those lines; I haven't read it yet.

As far as proportionality, I don't think that matters. If generals can collude, which must be assumed, then one general with more hash rate is equivalent to many colluding generals each with the same hash rate.

The reason why bitcoin's 51% tolerance is controversial in the face of classical BGP is that the ability for the generals to lie is proportional to the hash rate of each general. Their messages are computationally signed against being forged.

You could specify the number of traitors but not their identities. But I agree with you that is not as useful a problem, in practice. The whole context of the paper and the people writing it was as a metaphor for building reliable distributed computing systems, where the number of failures is not set or known in advance.

Unless you specify that they can't, a proper solution (the problem statement uses the word "ensure") has to survive it, so it can be assumed.

Yes we know this. And the same applies to Bitcoin's CPU power.

Thus in some sense the problems are equivalent and the thread topic is incorrect (though I still question whether the problems are in fact equivalent). Just as BGP is solvable conditionally, so is Bitcoin secure conditionally.

I call it a condition rather than a precondition because in some setups it is clear that the former is more useful. For example, a safety control system may specify that it continue to function properly as long as <1/3 of its components fail.

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.

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.

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.

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

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?

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


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.

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:

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


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.

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

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.