Topic: Who solved the "Bizantine Generals Problem"? (Read 2525 times)
The first person in history to solve the "Byzantine Generals Problem" was the Byzantine Generals' new mistress.
Interesting reading and changed my understanding on the history of Byzantine Generals Problem.
i.e Satoshi was not the first person to solve it.
Also pretty cool to see somebody talking about PoW back in 2004 ... almost sounds like Hal Finney is talking about an altcoin
i.e Satoshi was not the first person to solve it.
Also pretty cool to see somebody talking about PoW back in 2004 ... almost sounds like Hal Finney is talking about an altcoin
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 authoroitative evidence on this subject so I can refute or accept this guy's claim?
Thanks a lot,
Rodrigo
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 authoroitative evidence on this subject so I can refute or accept this guy's claim?
Thanks a lot,
Rodrigo
“RPOW” was added on top of Adam Back’s “HashCash”. (This is how Hal Finney created the solution for the Byzantine General’s Problem which allowed BitGold/Bitcoin to be completed).
-“The computer can be used as a tool to liberate and protect people, rather than to control them” ~ Hal
To: [email protected]
Subject: RPOW - Reusable Proofs of Work
Date: Sun, 15 Aug 2004 10:43:09 -0700 (PDT)
From: hal at finney dot org ("Hal Finney")
I'd like to invite members of this list to try out my new
hashcash-based server, rpow.net.
This system receives hashcash as a Proof of Work (POW) token, and in
exchange creates RSA-signed tokens which I call Reusable Proof of Work
(RPOW) tokens. RPOWs can then be transferred from person to person and
exchanged for new RPOWs at each step. Each RPOW or POW token can only
be used once but since it gives birth to a new one, it is as though the
same token can be handed from person to person.
Because RPOWs are only created from equal-value POWs or RPOWs, they are
as rare and "valuable" as the hashcash that was used to create them.
But they are reusable, unlike hashcash.
The new concept in the server is the security model. The RPOW server
is running on a high-security processor card, the IBM 4758 Secure
Cryptographic Coprocessor, validated to FIPS-140 level 4. This card
has the capability to deliver a signed attestation of the software
configuration on the board, which any (sufficiently motivated) user
can verify against the published source code of the system. This lets
everyone see that the system has no back doors and will only create RPOW
tokens when supplied with POW/RPOW tokens of equal value.
This is what creates trust in RPOWs as actually embodying their claimed
values, the knowledge that they were in fact created based on an equal
value POW (hashcash) token.
I have a lot more information about the system at rpow.net, along with
downloadable source code. There is also a crude web interface which
lets you exchange POWs for RPOWs without downloading the client.
This system is in early beta right now so I'd appreciate any feedback
if anyone has a chance to try it out. Please keep in mind that if there
are problems I may need to reload the server code, which will invalidate
any RPOW tokens which people have previously created. So don't go too
crazy hoarding up RPOWs quite yet.
Thanks very much -
Hal Finney
http://cryptome.org/rpow.htm
Szabo(BitGold), and apparently Satoshi(BitCoin), realized that Hal Finneys “RPOW” could be used to solve the Byzantine General’s Problem, a problem in ordinary computing that demonstrates through “game theory” how a group of potential co-operators can come to the best consensus even with the possibility of having malicious operators among them. This was the final piece to the BitGold/Bitcoin puzzle.
http://www.cs.cornell.edu/courses/cs614/2004sp/papers/lsp82.pdf
http://unenumerated.blogspot.com/2008/04/bit-gold-markets.html?m=1
http://unenumerated.blogspot.com/2005/12/bit-gold.html?m=1
Nick Szabo: “(assuming Nakamoto is not really Finney or Dai)”…..Only Finney (RPOW) and Nakamoto were motivated enough to actually implement such a scheme”.
Szabo has now coined the phrase "Nakamoto Consensus" to refer to Hal's "RPOW" that Satoshi used to make BitCoin work.
http://unenumerated.blogspot.com/2014/12/the-dawn-of-trustworthy-computing.html
I will purchase and read the paper.
I found this on the Internet - http://zoo.cs.yale.edu/classes/cs426/2012/bib/castro99practical.pdf
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.
Lamport assumes or doesn't even address whether one can ultimately trust any of the 2/3rds of the generals. Bitcoin goes beyond Lamport's research.
https://socrates1024.s3.amazonaws.com/consensus.pdf
Yes, I already agreed to this. Bitcoin only solves the BGP if you assume the network isn't compromised. Strictly speaking, Bitcoin cannot solve the Byzantine Generals' Problem, but neither can anything else with 100% confidence. This is why it is a "dilemma" or "problem" and why researchers study probabilistic solutions to solving the Byzantine fault tolerance problems.
Funny, we finally came to an agreement and this didn't take much time!
Aye, as I said, Satoshi "cheated" by using weaker assumptions.
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.
Yes, I already agreed to this. Bitcoin only solves the BGP if you assume the network isn't compromised. Strictly speaking, Bitcoin cannot solve the Byzantine Generals' Problem, but neither can anything else with 100% confidence. This is why it is a "dilemma" or "problem" and why researchers study probabilistic solutions to solving the Byzantine fault tolerance problems.
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.
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.
"The proof-of-work chain is a solution to the Byzantine Generals' Problem." Satoshi Nakamoto
http://satoshi.nakamotoinstitute.org/emails/cryptography/11/
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.
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.
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:
Quote
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.
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:
Quote from: http://hyperledger.com/faqs.html#pow
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.
Quote from: http://hyperledger.com/faqs.html#pow
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?
"The proof-of-work chain is a solution to the Byzantine Generals' Problem." Satoshi Nakamoto
http://satoshi.nakamotoinstitute.org/emails/cryptography/11/
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?
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.
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:
Quote
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.
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.
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
Quote
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.
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.
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.
So are you agreeing with me that there are no known solutions to the BGP in reality?
I disagree.
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/[email protected]/msg09997.html
https://socrates1024.s3.amazonaws.com/consensus.pdf
Quote
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.
model, except for a negligible probability , when Byzantine faults make up less than half the network.
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.
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.
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.
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.
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.
Jump to: