Satoshi didn't solve the Byzantine generals problem

[David Rabahy]

This is an immensely valuable topic to understand as deeply and completely as possible.  It would be good to refrain from using any offensive language -- it is possible and often common to misunderstand other points of view.  Let's get the papers written and distributed for the community to evaluate.  If the ideas are sound then hopefully they will be embraced.  If they are not then hopefully they can made be made sound or abandoned accordingly.

Membership: I stood up a full node (non-mining) without any registration with a central authority.  I trusted the software (weak on my part personally but do have at least one person I do personally know very well (my son) building from sources) and the technique it uses to find the "real" Bitcoin network.  I do compare my full node state from time to time with the "public" state as reported at Blockchain.info et al -- although I have become complacent over time.  I feel confident so far but understand that this might bite me in the future.

An ASCI-resistant PoW does seem valuable to me.  Is memory latency the right barrier to stand upon for the ages?  For example, is http://community.hpe.com/t5/Behind-the-scenes-Labs/The-Machine-HP-Labs-launches-a-bold-new-research-initiative-to/ba-p/6793690#.VreSn2b2aUk relevant?  Doesn't cache size eventually eliminate the memory latency issue?  Perhaps the problem size (not just difficulty) can be increased as blocks come in faster and faster?

[1713861484]

1713861484

[1713861484]

1713861484

[1713861484]

1713861484

[1713861484]

1713861484

[1713861484]

1713861484

[1713861484]

1713861484

[monsterer]

So if the LCR is creating censored transactions is that not a fault/failure? What the hell use of Byzantine fault tolerance if it doesn't guarantee a system that can be used by the participants?

Only a 51% attack can censor transactions 100%, any less will just delay them as the honest majority of miners will include transactions which the dishonest minority has censored. Again, this all is within the bounds of the tolerance of the protocol.

[smooth]

So if the LCR is creating censored transactions is that not a fault/failure? What the hell use of Byzantine fault tolerance if it doesn't guarantee a system that can be used by the participants?

There are no censored transactions unless a majority of the CPU power* is conspiring to attack the system.

Bitcoin has a threshold of hostile CPU power that it can tolerate. Below that threshold, it works, above that threshold, it fails.

* selfish mining, etc.

[smooth]

There is no Sybil attack possible on the problem as stated. "A majority of CPU power" is a physical quantity which can't be Sybil attacked. Period.

True, but there are other "attacks". Such as calling up Chinese miners and convince them to do a certain thing.

This only works because Chinese miners have a majority of the CPU power. Otherwise you call them up all you want, but would accomplish nothing. You might as well call someone with an old USB miner stick.

[TPTB_need_war]

monsterer and smooth, I repeat again, how do you prove if a 51% attack is censoring transactions? In other words, how do you even detect it in an objective and provable manner?

A system which doesn't objectively (from the perspective of all observers) know when it is failing is not Byzantine fault tolerant.

Refer again to the Wikipedia definitions:

The following practical, concise definitions are helpful in understanding Byzantine fault tolerance:[3][4]

Byzantine fault
    Any fault presenting different symptoms to different observers
Byzantine failure
    The loss of a system service due to a Byzantine fault in systems that require consensus

This circular logic of yours is getting redundant. I have made my point and you have not refuted it.

[smooth]

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

In Bitcoin "too many faulty components" = majority of the CPU power.

[monsterer]

monsterer and smooth, I repeat again, how do you prove if a 51% attack is censoring transactions? In other words, how do you even detect it in an objective and provable manner?

A system which doesn't objectively (from the perspective of all observers) know when it is failing is not Byzantine fault tolerant.

Refer again to the Wikipedia definitions:

The following practical, concise definitions are helpful in understanding Byzantine fault tolerance:[3][4]

Byzantine fault
    Any fault presenting different symptoms to different observers
Byzantine failure
    The loss of a system service due to a Byzantine fault in systems that require consensus

This circular logic of yours is getting redundant. I have made my point and you have not refuted it.

Bitcoin employs an amortized byzantine consensus. Nodes vote with their hash-power on the branch of the chain which they consider to be truth. Evidence of byzantine failures is the existence of multiple branches; we call these orphans. Each branch presents a different version of truth to observers of the system.

[smooth]

Nodes vote with their hash-power on the branch of the chain which they consider to be truth.

Only correctly functioning nodes do that.

Evidence of byzantine failures is the existence of multiple branches; we call these orphans. Each branch presents a different version of truth to observers of the system.

Not really, those are just evidence of latency. If a majority of the CPU power is conspiring to attack the system and all non-cospirator blocks are orphaned then no one will mine outside the conspiracy and there will be no such orphans (there may still be forks within the conspiracy if they still have latency).

The system will have failed, but it will have failed because it exceeded stated limits.

 

[TPTB_need_war]

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

In Bitcoin "too many faulty components" = majority of the CPU power.

We can't count the components because identities can be Sybil attacked.

But more saliently since I know your retort would be that hashrate is the count, you seem to be going in circles because you ignore what I already wrote:

In bitcoin, BGP is solved to within the stated tolerance of 51% byzantine faulty nodes.

Satoshi's PoW does not distinguish between faulty and non-faulty nodes.

You guys are like a dog chasing its tail.

[monsterer]

Not really, those are just evidence of latency. If a majority of the CPU power is conspiring to attack the system and all non-cospirator blocks are orphaned then no one will mine outside the conspiracy and there will be no such orphans (there may still be forks within the conspiracy if they still have latency).

The system will have failed, but it will have failed because it exceeded stated limits.

I should have written 'fault' instead of failure. Nonetheless, byzantine faults can arise due to latency, or a malicious node - I wasn't describing an attack scenario specifically, just defining how the byzantine consensus applies to bitcoin.

[monsterer]

We can't count the components because identities can be Sybil attacked.

I'm not really sure why you are having such a problem with this; it is obvious that hashing power is the only substitute for the abstract concept of a node, or a component.

[TPTB_need_war]

The system will have failed, but it will have failed because it exceeded stated limits.

The system didn't fail. Who can prove it failed?

You guys keep forgetting the point I made which is that Satoshi's design provides no mechanism to objectively distinguish failure. There is no such thing as faulty nodes in Satoshi's PoW. Even a double-spend attack can not be distinguished from a latency driven orphan w.r.t. to the miners' hashrate. The fact that the payer sent two signed txns is orthogonal to hashrate.

Come on guys turn on your brains now.

[TPTB_need_war]

We can't count the components because identities can be Sybil attacked.

I'm not really sure why you are having such a problem with this; it is obvious that hashing power is the only substitute for the abstract concept of a node, or a component.

Because hash rate doesn't prove faultiness. Bitcoin has no frame of reference.

When you see a corrected design, you will understand why not being able to Sybil attack a frame of reference is what enables establishing blame and making the system Byzantine tolerant.

[monsterer]

We can't count the components because identities can be Sybil attacked.

I'm not really sure why you are having such a problem with this; it is obvious that hashing power is the only substitute for the abstract concept of a node, or a component.

Because hash rate doesn't prove faultiness. Bitcoin has no frame of reference.

Majority is truth. That is the ethos of bitcoin.

[monsterer]

When you see a corrected design, you will understand why not being able to Sybil attack a frame of reference is what enables establishing blame and making the system Byzantine tolerant.

It won't work - you cannot combine the majority-is-truth rule with something which gives power to the minority, because if you do, any faulty minority will be able to overthrow the majority, which leads to divergent chaos.

[smooth]

The system will have failed, but it will have failed because it exceeded stated limits.

The system didn't fail. Who can prove it failed?

Someone who attempts to use the service and is unable to do so.

You can't require everyone to recognize such a failure because that would be a consensus outcome and now you are relying on a failed consensus system to produce consensus.

Consensus only exists within the specified limits.

[smooth]

When you see a corrected design, you will understand why not being able to Sybil attack a frame of reference is what enables establishing blame and making the system Byzantine tolerant.

It won't work - you cannot combine the majority-is-truth rule with something which gives power to the minority, because if you do, any faulty minority will be able to overthrow the majority, which leads to divergent chaos.

It may work, up to its specified limits, but then it will fail a different way.

[TPTB_need_war]

We can't count the components because identities can be Sybil attacked.

I'm not really sure why you are having such a problem with this; it is obvious that hashing power is the only substitute for the abstract concept of a node, or a component.

Because hash rate doesn't prove faultiness. Bitcoin has no frame of reference.

Majority is truth. That is the ethos of bitcoin.

For the 3rd or 4th time, according to definitions the rule of majority presenting different symptoms to different observers is not Byzantine fault tolerance:

A system which doesn't objectively (from the perspective of all observers) know when it is failing is not Byzantine fault tolerant.

Refer again to the Wikipedia definitions:

The following practical, concise definitions are helpful in understanding Byzantine fault tolerance:[3][4]

Byzantine fault
    Any fault presenting different symptoms to different observers
Byzantine failure
    The loss of a system service due to a Byzantine fault in systems that require consensus

This circular logic of yours is getting redundant. I have made my point and you have not refuted it.

I hope I don't have to repeat that again.

Since Bitcoin can not detect faultiness (consistently provable to all observers), then that means you are claiming it is Byzantine fault tolerant with up to 100% of the hashrate faulty. Which obviously violates the fundamental research about what is theoretically plausible. Which thus proves to you that your claim is incorrect.

Bitcoin is the Power Law of Economics, not Byzantine fault tolerance.

[TPTB_need_war]

When you see a corrected design, you will understand why not being able to Sybil attack a frame of reference is what enables establishing blame and making the system Byzantine tolerant.

It won't work - you cannot combine the majority-is-truth rule with something which gives power to the minority, because if you do, any faulty minority will be able to overthrow the majority, which leads to divergent chaos.

It may work, up to its specified limits, but then it will fail a different way.

I find it amusing how monsterer often declares that something is impossible and then I show him it is possible, yet then he is so sure of himself again.

Making mining unprofitable combined with some different responsibilities for organizing the block chain produces a very different system in terms of the issues we are discussing.

Note some centralization is always required. Bitcoin gives us centralization but without any frame of reference thus observers have no way to be objective in order to use decentralized power to prove blame to all observers.

LCR has to do with converging consensus. It doesn't have to do with blame for example of which transactions get censored. Those can be orthogonal if structured in a way that allows unambiguously proving blame (independent of the LCR). In Bitcoin, when you submit a transaction to the network, you can't blame a particular pool for refusing to include it. No one can verify the claim by submitting it to network and identifying a particular pool that is the culprit. If you don't know which pool to blame and the pools are Sybil attacked any way, then you don't even know where to move your mining shares to (besides the fact that payers are not mining in Bitcoin because mining is profitable).

[monsterer]

Since Bitcoin can not detect faultiness (consistently provable to all observers), then that means you are claiming it is Byzantine fault tolerant with up to 100% of the hashrate faulty. Which obviously violates the fundamental research about what is theoretically plausible. Which thus proves to you that your claim is incorrect.

Bitcoin is the Power Law of Economics, not Byzantine fault tolerance.

Apply that logic to any of the attempts to solve the BGP, you will find that none of them solve it, which suggests that your definition is incorrect. Each and every attempt at solving the BGP defines bounds on the failure tolerance; beyond these bounds, all bets are off.

As smooth said, since the system has failed once it passes the tolerance, how can it possibly detect anything? That defies logic.