Who solved the "Bizantine Generals Problem"?

[CRServers]

Hello to all!

I recently gave a talk about Bitcoin to a group of business and university professors, and in that talk I said that Satoshi Nakamoto had solved the "Bizantine Generals Problem".

I had read that from several documents and also heard it from a couple of prominent Bitcoin talkers.
To my surprise, one professor disputed my affirmation, got up, and said that another person had solved it before. He mentioned the name but I forgot it.

Now I'm perplexed about the issue and want to know what the real story is, so I can contact this person and conciliate the truth with him.

Can anybody point me to some authoritative evidence on this subject so I can refute or accept this guy's claim?

Thanks a lot,

Rodrigo

 

[Come-from-Beyond]

Hello to all!

I recently gave a talk about Bitcoin to a group of business and university professors, and in that talk I said that Satoshi Nakamoto had solved the "Bizantine Generals Problem".

I had read that from several documents and also heard it from a couple of prominent Bitcoin talkers.
To my surprise, one professor disputed my affirmation, got up, and said that another person had solved it before. He mentioned the name but I forgot it.

Now I'm perplexed about the issue and want to know what the real story is, so I can contact this person and conciliate the truth with him.

Can anybody point me to some authoritative evidence on this subject so I can refute or accept this guy's claim?

Thanks a lot,

Rodrigo

  

http://dl.acm.org/citation.cfm?doid=571637.571640

[CRServers]

Hello  Come-from-Beyond,

Thanks for the link.
I will purchase and read the paper.

But what's the short answer.
Did Satoshi Nakamoto solve the "Bizantine Generals Problem"? Yes or No

Thanks,
 

[Come-from-Beyond]

Hello  Come-from-Beyond,

Thanks for the link.
I will purchase and read the paper.

But what's the short answer.
Did Satoshi Nakamoto solve the "Bizantine Generals Problem"? Yes or No

Thanks,
 

No. His assumptions are weaker, otherwise we would talk about 33% attack, not 51%.

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

Reliable computer systems must handle malfunctioning components that give conflicting information
to different parts of the system. This situation can be expressed abstractly in terms of a group of
generals of the Byzantine army camped with their troops around an enemy city. Communicating only
by messenger, the generals must agree upon a common battle plan. However, one or more of them
may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that
the loyal generals will reach agreement. 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; so a single traitor can confound
two loyal generals. With unforgeable written messages, the problem is solvable for any number of
generals and possible traitors. Applications of the solutions to reliable computer systems are then
discussed.

[inBitweTrust]

Your professor is correct. Satoshi wasn't the first person to solve the Byzantine fault tolerance dilemma.
Bitcoin is merely one widely used application that has successfully solved the Byzantine generals dilemma.

The first practical solution was represented by Miguel Castro and Barbara Liskov in 1999 with the Practical Byzantine Fault Tolerance" (PBFT) algorithm:
https://dl.acm.org/citation.cfm?doid=571637.571640

With regards to Bitcoin :

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

2/3rds deals with communication between untrusted parties where unforgeable written messages aren't in use. Of course Bitcoin messages can be forgeable, but the genius of the system is both the consensus mechanism and the incentive structure both discourage users from doing so and make it increasing more difficult to do so with time.

Thus Bitcoin does solve the Byzantine fault tolerance dilemma until a "51% attack" occurs as the authentic blockchain is trusted until such an event occurs.

Some may suggest that if Bitcoin is dependent upon trusting the validity of the blockchain upon solving the Byzantine generals dilemma it may refute the whole notion of ultimate trust as a 51% attack can happen at any moment. Unlike with multiple messengers or couriers in the original dilemma, blockchain based crypto-currencies use of a public ledger system make immediate acknowledgement and demarcate the attack so the "generals" or users can identify if the message is to be trusted or not. Before a 51% attack occurs you can be probabilistically sure to a certain degree based upon the amount of nodes and time passed that a transaction is valid. If a 51% attack occurs it merely shifts the recognition of these false transactions until shortly after they occur until the attacker is dealt with.

All solutions to the Byzantine's General dilemma are dependent upon trusting a non compromised network or system and with bitcoin the network is decentralized and extremely difficult to compromise.

[Come-from-Beyond]

If 51% is enough then it's not Byzantine Generals problem.

[inBitweTrust]

If 51% is enough then it's not Byzantine Generals problem.

A 51% attack indicates a compromised system.  As soon as it occurs the "generals" will be aware of the exploit as well as an added benefit. Other examples of solutions like "Practical Byzantine Fault Tolerance" (PBFT) algorithm" cannot equally be trusted with a compromised system.

You are correct insomuch as we cannot be 100% reliant upon trusting any proposed solution to the Byzantine Generals Dilemma as every solution is reliant upon trusting that the network or system wasn't compromised.

This is just a statement about security and epistemology in general however.

[Come-from-Beyond]

A 51% attack indicates a compromised system.  As soon as it occurs the "generals" will be aware of the exploit as well as an added benefit. Other examples of solutions like "Practical Byzantine Fault Tolerance" (PBFT) algorithm" cannot equally be trusted with a compromised system.

You are correct insomuch as we cannot be 100% reliant upon trusting any proposed solution to the Byzantine Generals Dilemma as every solution is reliant upon trusting that the network or system wasn't compromised.

This is just a statement about security and epistemology in general however.

My point is that Satoshi added extra assumptions. They reduced percentage of loyal generals from 67% to 51%, but it's not Byzantine Generals problem anymore. We already have a mathematical proof that 2/3 is the lowest bound.

Statement that Satoshi solved BGP is just an urban legend that doesn't stand deep analysis.

[inBitweTrust]

My point is that Satoshi added extra assumptions. They reduced percentage of loyal generals from 67% to 51%, but it's not Byzantine Generals problem anymore. We already have a mathematical proof that 2/3 is the lowest bound.

Statement that Satoshi solved BGP is just an urban legend that doesn't stand deep analysis.

I believe you are conflating 2/3 of the generals being loyal with a 51% attack. With bitcoin the incentive structure probabilistically encourages that over 99 % of "generals" are loyal regardless of their selfish motivations through game theory. Thus with time the "generals" can be probabilistically sure the couriers messages are accurate.

I agree with you if you are suggesting that there are no known or practical solutions to the Byzantine Generals problem in existence as all must inherently trust the protocol or network not being compromised. What bitcoin does solve is the Byzantine Generals problem in a practical and probabilistic sense.

In reality is there is no such thing as perfect security in the analog or digital world.

[Come-from-Beyond]

What bitcoin does solve is the Byzantine Generals problem in a practical and probabilistic sense.

You can generate as many definitions of your BGP as you wish but those that require less than 2/3 don't solve the problem that we discuss. Simple as contradictio in contrarium.

[inBitweTrust]

What bitcoin does solve is the Byzantine Generals problem in a practical and probabilistic sense.

You can generate as many definitions of your BGP as you wish but those that require less than 2/3 don't solve the problem that we discuss. Simple as contradictio in contrarium.

If you noticed , I was discussing 2 different definitions, not my definition.

So are you agreeing with me that there are no known solutions to the BGP in reality? If not, than what proposal allows us to be confident that 2/3rds of the "generals " can be trusted?

p.s.... I am looking for a proposal that has been tested and implemented like - https://dl.acm.org/citation.cfm?doid=571637.571640
which doesn't address whether or not we can trust the "generals" or not.

More information as BGP relates to bitcoin:

http://www.mail-archive.com/cryptography@metzdowd.com/msg09997.html
https://socrates1024.s3.amazonaws.com/consensus.pdf

Our main contribution is a proof that the Bitcoin protocol achieves consensus in this
model, except for a negligible probability , when Byzantine faults make up less than half the network.

[Come-from-Beyond]

So are you agreeing with me that there are no known solutions to the BGP in reality?

I disagree.

[inBitweTrust]

So are you agreeing with me that there are no known solutions to the BGP in reality?

I disagree.

If not, than what proposal allows us to be confident that 2/3rds of the "generals " can be trusted?

p.s.... I am looking for a proposal that has been tested and implemented like - https://dl.acm.org/citation.cfm?doid=571637.571640
which doesn't address whether or not we can trust the "generals" or not.

Don't waste your time posting the same research papers dealing with hypothetical models which ignore how one can ultimately trust any generals. I am looking for examples that solve the BGP which have been implemented and tested in reality.

[bentrader]

Statement that Satoshi solved BGP is just an urban legend that doesn't stand deep analysis.

"The proof-of-work chain is a solution to the Byzantine Generals' Problem." Satoshi Nakamoto
http://satoshi.nakamotoinstitute.org/emails/cryptography/11/

Blockchain is a solution for BGP in a form different than original proposed in the original paper http://research.microsoft.com/en-us/um/people/lamport/pubs/byz.pdf
One might come up with a better description for BGP as it applies in this context. BGP of course has nothing to do with "money" in the original description. Blockchain is a much more general construct which solves an unenumerable set of problems.

Btw, fun fact: Satoshi did not use the word blockchain in the beginning only in December 2009: https://github.com/NakamotoInstitute/nakamotoinstitute.org/blob/master/satoshiposts.json#L4225

The proof-of-work chain is a solution to the Byzantine Generals' Problem. I'll
try to rephrase it in that context.

A number of Byzantine Generals each have a computer and want to attack the
King's wi-fi by brute forcing the password, which they've learned is a certain
number of characters in length. Once they stimulate the network to generate a
packet, they must crack the password within a limited time to break in and
erase the logs, otherwise they will be discovered and get in trouble. They
only have enough CPU power to crack it fast enough if a majority of them attack
at the same time.

They don't particularly care when the attack will be, just that they all agree.
It has been decided that anyone who feels like it will announce a time, and
whatever time is heard first will be the official attack time. The problem is
that the network is not instantaneous, and if two generals announce different
attack times at close to the same time, some may hear one first and others hear
the other first.

They use a proof-of-work chain to solve the problem. Once each general
receives whatever attack time he hears first, he sets his computer to solve an
extremely difficult proof-of-work problem that includes the attack time in its
hash. The proof-of-work is so difficult, it's expected to take 10 minutes of
them all working at once before one of them finds a solution. Once one of the
generals finds a proof-of-work, he broadcasts it to the network, and everyone
changes their current proof-of-work computation to include that proof-of-work
in the hash they're working on. If anyone was working on a different attack
time, they switch to this one, because its proof-of-work chain is now longer.

After two hours, one attack time should be hashed by a chain of 12
proofs-of-work. Every general, just by verifying the difficulty of the
proof-of-work chain, can estimate how much parallel CPU power per hour was
expended on it and see that it must have required the majority of the computers
to produce that much proof-of-work in the allotted time. They had to all have
seen it because the proof-of-work is proof that they worked on it. If the CPU
power exhibited by the proof-of-work chain is sufficient to crack the password,
they can safely attack at the agreed time.

The proof-of-work chain is how all the synchronisation, distributed database
and global view problems you've asked about are solved.

[Come-from-Beyond]

If not, than what proposal allows us to be confident that 2/3rds of the "generals " can be trusted?

p.s.... I am looking for a proposal that has been tested and implemented like - https://dl.acm.org/citation.cfm?doid=571637.571640
which doesn't address whether or not we can trust the "generals" or not.

Don't waste your time posting the same research papers dealing with hypothetical models which ignore how one can ultimately trust any generals. I am looking for examples that solve the BGP which have been implemented and tested in reality.

http://hyperledger.com/faqs.html#pow:

DOES HYPERLEDGER USE PROOF OF WORK OR MINING?

No, hyperledger does not use Proof of Work or mining, instead it relies on achieving consensus through a mechanism based on the Practical Byzantine Fault Tolerance algorithm.

[Come-from-Beyond]

"The proof-of-work chain is a solution to the Byzantine Generals' Problem." Satoshi Nakamoto
http://satoshi.nakamotoinstitute.org/emails/cryptography/11/

BGP is not reliable in case of 60 loyal generals and 40 traitors. What the point of 51% attack then?

[inBitweTrust]

If not, than what proposal allows us to be confident that 2/3rds of the "generals " can be trusted?

p.s.... I am looking for a proposal that has been tested and implemented like - https://dl.acm.org/citation.cfm?doid=571637.571640
which doesn't address whether or not we can trust the "generals" or not.

Don't waste your time posting the same research papers dealing with hypothetical models which ignore how one can ultimately trust any generals. I am looking for examples that solve the BGP which have been implemented and tested in reality.

http://hyperledger.com/faqs.html#pow:

DOES HYPERLEDGER USE PROOF OF WORK OR MINING?

No, hyperledger does not use Proof of Work or mining, instead it relies on achieving consensus through a mechanism based on the Practical Byzantine Fault Tolerance algorithm.

Ok, so you are providing an example that is more vulnerable than bitcoin:

However, consensus in an asynchronous system with potentially malicious nodes requires greater than 2/3rds of the nodes to be honest but since bad nodes are automatically detected and expelled quickly, we don’t believe this is an issue.

Bitcoin requires 51% honest nodes, HYPERLEDGER requires 66.6% honest nodes.

but since bad nodes are automatically detected and expelled quickly, we don’t believe this is an issue.

Fixing the problem after the fact, where the attack has already occurred. Just like with Bitcoin, but worse.


Does HYPERLEDGER really solve the Bizantine Generals problem if it has to assume that 66.6% of nodes are trusted?

[bentrader]

"The proof-of-work chain is a solution to the Byzantine Generals' Problem." Satoshi Nakamoto
http://satoshi.nakamotoinstitute.org/emails/cryptography/11/

BGP is not reliable in case of 60 loyal generals and 40 traitors. What the point of 51% attack then?

Absolute majority is a fact of mathematics. Any set S with size N has exactly one majority, i.e. a partition of S in two parts has one smaller and one larger part (or they are exactly equally split, which can easily be stopped by having the size be N%2=1 ). One can consider smaller partitions in of S, where each partition can be called a "coalition". That's basically what political parties are. It would great to have a system where some changes require super-majority of 2/3 or 9/10 - but couldn't the majority simply force minority into a rule change, such that majority vote is sufficient for any vote? I.e. if there are 51 loyal generals they can dominate 49 traitors, even if the rules requires more.

[Come-from-Beyond]

Does HYPERLEDGER really solve the Bizantine Generals problem if it has to assume that 66.6% of nodes are trusted?

I can't say anything regarding this issue.

Well, maybe BGP is not solved yet. Anyway, this doesn't change the fact that Satoshi didn't solve BGP.

[Come-from-Beyond]

Absolute majority is a fact of mathematics. Any set S with size N has exactly one majority, i.e. a partition of S in two parts has one smaller and one larger part (or they are exactly equally split, which can easily be stopped by having the size be N%2=1 ). One can consider smaller partitions in of S, where each partition can be called a "coalition". That's basically what political parties are. It would great to have a system where some changes require super-majority of 2/3 or 9/10 - but couldn't the majority simply force minority into a rule change, such that majority vote is sufficient for any vote? I.e. if there are 51 loyal generals they can dominate 49 traitors, even if the rules requires more.

If you claim that 51% is enough then where is the mistake in the proof presented in Lamport's whitepaper? He claims that 51% (and even 60%) is not enough. I tend to trust Lamport because he provided a formal proof. Your "math" doesn't look very convincing.