Satoshi didn't solve the Byzantine generals problem

[smooth]

the only way to know that precondition is for the system to be centralized so that the count of the traitors is known

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.

[smooth]

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.

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.

[smooth]

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.

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.

[monsterer]

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.

[smooth]

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.

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.

[monsterer]

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.

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.

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

[TPTB_need_war]

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.

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.

[monsterer]

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.

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

[monsterer]

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

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.

[TPTB_need_war]

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.

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

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.

[smooth]

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

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.

Look he is saying there is no "unconditional" solution, which is absolutely correct. There is a solution, which may work, or may not work, depending on the state of the world when it is applied.

That is very much the same as Bitcoin, and stated as such by Satoshi in the white paper. Bitcoin is not unconditionally anything. If a majority of CPU power is conspiring to attack it, then it is failing.

Though Bitcoin does have a somewhat nice recovery property in that the failure only persists as long as 50% of the CPU power is conspiring to attack it. Unlike, an airplane for example. If too many components "temporarily" fail, then it may be catastrophically disassembled before they recover.

[TPTB_need_war]

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.

Yes the Lamport et al BGP paper was focused on cases where failure rates (where traitors are faulty components/nodes) can be conjectured (c.f. the end of the paper), not on Sybil attacks in a decentralized setting.

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

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.

You are conflating the decentralized, trustless, Sybil attackable scenario with the scenarios where the precondition can be conjectured probabilistically and thus where Lamport's "solution" has quantitative merit/utility as I stated:

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]

Look he is saying there is no "unconditional" solution, which is absolutely correct. There is a solution, which may work, or may not work, depending on the state of the world when it is applied.

That is trivially obvious though. Of course there is no solution which works at all times, in all circumstances, that is why any proposed solution has specified bounds. To take 5 pages of back and forth to arrive here with that result would be very disappointing indeed.

[TPTB_need_war]

Look he is saying there is no "unconditional" solution, which is absolutely correct. There is a solution, which may work, or may not work, depending on the state of the world when it is applied.

That is trivially obvious though. Of course there is no solution which works at all times, in all circumstances, that is why any proposed solution has specified bounds. To take 5 pages of back and forth to arrive here with that result would be very disappointing indeed.

The salient point continues to fly right over your head.

That is that the cases where the count of faulty nodes can be conjectured quantitatively (such as MTBF failure rates for hardware components) does not include the trustless, decentralized, Sybil attacked applications such as Satoshi's PoW design.

My statement is fact:

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

[monsterer]

You are conflating the decentralized, trustless, Sybil attackable scenario with the scenarios where the precondition can be conjectured probabilistically and thus where Lamport's "solution" has quantitative merit/utility as I stated:

No, I was reducing the problem down into its fundamental parts to illustrate that, at any given moment, the bitcoin network is functionally equivalent to any other BGP consensus system.

Just because you cannot quantify the number of traitors does not mean the system will produce invalid results within the bounds. This is true of any BGP consensus and has absolutely nothing to do with trustless, decentralised solutions.

[TPTB_need_war]

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

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.

Look he is saying there is no "unconditional" solution, which is absolutely correct. There is a solution, which may work, or may not work, depending on the state of the world when it is applied.

That is very much the same as Bitcoin, and stated as such by Satoshi in the white paper. Bitcoin is not unconditionally anything. If a majority of CPU power is conspiring to attack it, then it is failing.

Agreed, but please note my point is deeper than that.

I am saying that in a decentralized, trustless, Sybil-attackable scenario, there is also no conditional solution to BGP, because the participants have no way to conjecture the probabilities of 51% attack (nor does any solution to BGP provide all participants a consistent, provable observation when the system state is attacked).

The condition of count of traitors has only utility in applications where the probabilistic rate of traitors can be conjectured.

I have also I think argued convincingly that Satoshi's PoW design (and every decentralized consensus design) must trend towards and rely on centralization. Thus the asymptotic probability of 51% attack is ~1.

Though Bitcoin does have a somewhat nice recovery property in that the failure only persists as long as 50% of the CPU power is conspiring to attack it. Unlike, an airplane for example. If too many components "temporarily" fail, then it may be catastrophically disassembled before they recover.

I can think of scenarios where that isn't necessarily true. For example, such an attack convinces speculators that the attack can be repeated at-will and so they flee the coin. Crash and burn.

[smooth]

I am saying that in a decentralized, trustless, Sybil-attackable scenario, there is also no conditional solution to BGP, because the participants have no way to conjecture the probabilities of 51% attack

We'll have to agree to disagree. As long as I can write down a solution, and write down the condition under which it applies, then I consider that a conditional solution. I do not need to state a probability that such a condition will be satisfied.

(nor does any solution to BGP provide all participants a consistent, provable observation when the system state is attacked).

I agree with this part.

The condition of count of traitors has only utility in applications where the probabilistic rate of traitors can be conjectured.

Utility is necessarily subjective. Also, ability to conjecture a probability is subjective.

I have also I think argued convincingly that Satoshi's PoW design (and every decentralized consensus design) must trend towards and rely on centralization. Thus the asymptotic probability of 51% attack is ~1.

See there, you just conjectured one!

Others likely conjecture a different one.

Though Bitcoin does have a somewhat nice recovery property in that the failure only persists as long as 50% of the CPU power is conspiring to attack it. Unlike, an airplane for example. If too many components "temporarily" fail, then it may be catastrophically disassembled before they recover.

I can think of scenarios where that isn't necessarily true. For example, such an attack convinces speculators that the attack can be repeated at-will and so they flee the coin. Crash and burn.

The system can still recover. There is no catastrophic disassembly.

You will never convince all the speculators to leave either. It is a bit like infinite divisibility. You have infinite reducibility of speculative value. Altcoin at #1000 in market cap still has a (tiny) value, there is still a (tiny) incentive to mine, and its blockchain still functions.

[TPTB_need_war]

Just because you cannot quantify the number of traitors does not mean the system will produce invalid results within the bounds. This is true of any BGP consensus and has absolutely nothing to do with trustless, decentralised solutions.

For Christ's sake, you cause me to repeat all the points I made upthread over and over again.

I already explained to you invalid results where the observers can't know whether the state was attacked or not, which is a Byzantine fault! There is no way to compute this risk and in fact the asymptotic risk is 100% (probability = ~1) because all decentralized consensus systems must centralize (which I explained in detail upthread).

Whereas, with a quantified probability of traitors (e.g. hardware MTBF), the risk of Byzantine fault is computed. Which was the intent of Lamport et al's paper.

[smooth]

Just because you cannot quantify the number of traitors does not mean the system will produce invalid results within the bounds. This is true of any BGP consensus and has absolutely nothing to do with trustless, decentralised solutions.

For Christ's sake, you cause me to repeat all the points I made upthread over and over again.

I already explained to you invalid results where the observers can't know whether the state was attacked or not, which is a Byzantine fault! There is no way to compute this risk and in fact the asymptotic risk is 100% (probability = ~1) because all decentralized consensus systems must centralize (which I explained in detail upthread).

You keep linking that page, and you keep ignoring the statement on that page that says "assuming there are not too many faulty components"

Whereas, with a quantified probability of traitors (e.g. hardware MTBF), the risk of Byzantine fault is computed. Which was the intent of Lamport et al's paper.

That's not really the case. Read the paper more carefully. Simple probabilistic hardware failure is easy to cope with using redundancy and majority voting. The hard problem is failures that are more subtle and complex, which can mimic deception and collusion.

The algorithm becomes a tool in a toolbox which is used to improve robustness against certain types of failures, but the robustness is still never absolute, and in real systems the actual probability of failure is still not known.

[monsterer]

Just because you cannot quantify the number of traitors does not mean the system will produce invalid results within the bounds. This is true of any BGP consensus and has absolutely nothing to do with trustless, decentralised solutions.

For Christ's sake, you cause me to repeat all the points I made upthread over and over again.

I already explained to you invalid results where the observers can't know whether the state was attacked or not, which is a Byzantine fault! There is no way to compute this risk and in fact the asymptotic risk is 100% (probability = ~1) because all decentralized consensus systems must centralize (which I explained in detail upthread).

Whereas, with a quantified probability of traitors (e.g. hardware MTBF), the risk of Byzantine fault is computed. Which was the intent of Lamport et al's paper.

Your points are irrelevant, you don't understand the problem as stated. You are desperately clinging to wikipedia definitions in an attempt to save face, when the honest thing would be to admit your mistake; no one will judge you for it.