Pages:
Author

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

sr. member
Activity: 420
Merit: 262
when an inestimable condition for Byzantine fault tolerance is COMBINED with inability to observe faults consistently among all observers, then no state is trustworthy

Your first point is irrelevant because that is the natural state for any byzantine system that we are concerned with. The second point is just plain incorrect, because a byzantine fault is a fork in bitcoin, and all observers can see the fork.

"an inestimable condition for Byzantine fault tolerance" is not an natural state of all applications of byzantine systems as I have explained for example for modeling hardware.

"inability to observe faults consistently among all observers" is correct and is inarguable for BGP as already explained and to which even smooth agreed.

Readers must I continue to refute monsterer because this is impinging on my time? He has been wrong on ever post in this thread lately. I think it is time to put him on Ignore.

Orphaned chains (not sustained forks!) are a natural and can't be proven to be an attack. Even those longer-con chains which orphan another chain which do not fall within the expected variance due to natural orphan rate can't be distinguished from natural (non-attack) network connectivity issues. Also I already explained upthread that an emphemeral fork (which orphans another chain) can't be blamed for a double-spend or censored transaction, because there is no provable correlation. Seems you've forgotten where I had to teach you in my Decentralized thread why it is impossible for a minority chain to prove anything (because the state of the chain is never absolute w.r.t. to any external chain/clock and is always moving forward). Which is the same analogous mistake enet made upthread.

Fuck man, you can't even keep all the concepts in your head from the past discussions!



We covered this earlier monsterer, but I don't agree that observers can necessarily see the fault. If mining is centralized and no one outside of the collusion mines (because it is not economically viable to do so), then there will be no forks.

However, it is accurate to say that if we know there are miners who aren't part of a collusion and we don't see forks that exceed those accounted for by natural propagation, then there is no attack.

Sorry smooth none of that shit is true per what I wrote above to monsterer.

Besides collusion is unknowable due to Sybil attacks.

You guys are chasing your tails in circles.

I believe the bolded condition is a near certainty today, and the italic condition is very likely true.

Therefore Bitcoin is solving (something like) BGP for the moment.

Analyzing the present based on available evidence is the only objective statement anyone can make on the matter.

Nonsense. There is no objective evidence in longest chain rule other than the longest chain. Period.

Anyway, it turns out that monsterer is actually correct, and failures are observable in Bitcoin after all. You can't censor transactions without controlling either all the miners or creating forks. As long as neither condition is observed we know it hasn't failed.

Nonsense all. monsterer isn't correct.

Attacker only needs 51% of hashrate to censor transactions perpetually (and less % to delay transactions).

There is no (sustained) fork in the longest chain rule.
legendary
Activity: 2968
Merit: 1198
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.

I suggest you also read the paper more carefully. Specifically Section "6. Reliable Systems" which we are referring to.

What it says is that as the hardware fails the outputs can become like traitor inputs to other hardware components causing the cascade to lie, which is precisely the BGP problem and what the solution is modeling by a count of traitors (passing along a traitor's lie doesn't create a new traitor). Even in the case where the derivative computation is corrupted due to the corrupted input, this is still a quantified probability of cascade of traitors obtainable from engineering and math/models applied from hardware MTBF rates. It is more exact science or estimation than not knowing. There is no decentralization, Sybil attacked introduced which otherwise makes the estimation highly unknowable and unmeasurable (science requires measurement to validate that models are predictive).

The examples in the paper are toy examples. Now consider a real system with many interconnected computers each running million or billions of lines of code. Passing along a lie does not create a new traitor, but responding incorrectly to an unexpected input does create new traitors. So it is very difficult to ever know how many Manchurian Candidate traitors exist, ready to be triggered. Byzantine fault tolerance is used because it allows robustness against complex failures to a greater degree than simple majority voting, even when the components are not simple bits of hardware with an easily-quantifiable MTBF (which are often bullshit, BTW).

Anyway, it turns out that monsterer is actually correct, and failures are observable in Bitcoin after all. You can't censor transactions without controlling either all the miners or creating forks. As long as neither condition is observed we know it hasn't failed.


sr. member
Activity: 420
Merit: 262
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.

I suggest you also read the paper more carefully. Specifically Section "6. Reliable Systems" which we are referring to.

What it says is that as the hardware fails the outputs can become like traitor inputs to other hardware components causing the cascade to lie, which is precisely the BGP problem and what the solution is modeling by a count of traitors (passing along a traitor's lie doesn't create a new traitor). Even in the case where the derivative computation is corrupted due to the corrupted input, this is still a quantified probability of cascade of traitors obtainable from engineering and math/models applied from hardware MTBF rates. It is more exact science or estimation than not knowing. There is no decentralization, Sybil attacked introduced which otherwise makes the estimation highly unknowable and unmeasurable (science requires measurement to validate that models are predictive).
legendary
Activity: 2968
Merit: 1198
We covered this earlier monsterer, but I don't agree that observers can necessarily see the fault. If mining is centralized and no one outside of the collusion mines (because it is not economically viable to do so), then there will be no forks.

However, it is accurate to say that if we know there are miners who aren't part of a collusion and we don't see forks that exceed those accounted for by natural propagation, then there is no attack.

I believe the bolded condition is a near certainty today, and the italic condition is very likely true.

Therefore Bitcoin is solving (something like) BGP for the moment.

Analyzing the present based on available evidence is the only objective statement anyone can make on the matter. Speculations about the future are just that.
legendary
Activity: 1008
Merit: 1007
when an inestimable condition for Byzantine fault tolerance is COMBINED with inability to observe faults consistently among all observers, then no state is trustworthy

Your first point is irrelevant because that is the natural state for any byzantine system that we are concerned with. The second point is just plain incorrect, because a byzantine fault is a fork in bitcoin, and all observers can see the fork.
legendary
Activity: 2968
Merit: 1198
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"

I am not ignoring it. You are ignoring the point that the condition on count of traitors is unknowable from any sane engineering estimation and thus no state of the decentralized, trustless consensus system (Satoshi's variant when conjectured to be decentralized, trustless) can ever be distinguished from a Byzantine fault, regardless whether the condition threshold has been reached or not.

That is true even if you can estimate probabilities. There will still be some probability of faults (which may different from your possibly-incorrect estimate, but even if not) that exceed the tolerance and those are not detectable. Generals then charge off to their deaths.

And in reality, in the case of Bitcoin, you do estimate a probability (as being close to 1) and so does everyone else (a range, not all close to 1). That is at the root of why you think it is not a solution. It has nothing to do with the solution to the BGP, which is a mathematical construction that may or may not apply to Bitcoin (I still don't know).

sr. member
Activity: 420
Merit: 262
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"

I am not ignoring it. You are ignoring the point that the condition on count of traitors is unknowable from any sane engineering estimation (which btw is why the point about Sybil attacked pools is relevant) and thus no state of the decentralized, trustless consensus system (Satoshi's variant when conjectured to be decentralized, trustless) can ever be distinguished from a Byzantine fault, regardless whether the condition threshold has been reached or not.

Your myopia Bill, is that (you smoked too much MJ and) when an inestimable condition for Byzantine fault tolerance is COMBINED with inability to observe faults consistently among all observers, then no state is trustworthy (which fails the goal of the solution). The "solution" collapses into a non-solution in the decentralized, trustless context.

Hopefully you will finally admit it.
legendary
Activity: 2968
Merit: 1198
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.

What use is a condition if it can't be measured?

The entire construction is an exercise in theoretical computer science, i.e. mathematics. You state a problem and you solve it. In this case (as in many others), the solution has necessary conditions.

It also happens to have some practical applications. Some of those involve measuring or estimating probabilities, some may not. An example of the latter would be comparing two available solutions to the same problem, where the input probability is unknown, but one solution or the other must be chosen. In that case you would very likely choose the solution with the weaker necessary condition (or at least you would consider that against cost).

I'm not going to respond to the rest of your message because I think it basically comes down to you being convinced that economics will certainly cause a permanent centralization of Bitcoin (which is effectively >1/3 or 50% collusion), and it will therefore fail. That's a fair belief, and I consider it a very significant probability, but I don't share your belief in the certainty of it.

sr. member
Activity: 420
Merit: 262
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.

You are delusional. Well beyond delusional to blinded by your anger and desire for me to be wrong. Sorry you are wrong monsterer, just as you were wrong in the other thread (and peskered me endlessly).
sr. member
Activity: 420
Merit: 262
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.

What use is a condition if it can't be measured?

The Lamport paper was aimed at hardware MTBF rates which can indeed be measured and verified.

I am into engineering. I guess you prefer black magic and voodoo (and I am from New Orleans, lol).

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

I agree with this part.

Thanks. It is unarguable fact.

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.

Incorrect. MTBF rates for hardware are objective engineering measurements. Seems you are referring to "feelings", "speculation" or something other than engineering.

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.

No I provided an overview of what can be put into a mathematical proof. That is objective engineering, not conjecture.

The asymptotic probability can be described quantitatively because of the inviolable economics (which derive from CAP theorem but we can prove just from the economic realities).

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.

Non-sequitor.

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.

For all intent & purposes, shitcoins that have $10 floats are dead and will fully die eventually.
legendary
Activity: 1008
Merit: 1007
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.
legendary
Activity: 2968
Merit: 1198
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"

Quote
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.
sr. member
Activity: 420
Merit: 262
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.
legendary
Activity: 2968
Merit: 1198
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.

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.

sr. member
Activity: 420
Merit: 262
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.
legendary
Activity: 1008
Merit: 1007
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.
sr. member
Activity: 420
Merit: 262
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.
legendary
Activity: 1008
Merit: 1007
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.
sr. member
Activity: 420
Merit: 262
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).
legendary
Activity: 2968
Merit: 1198
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.

Pages:
Jump to: