Bitcoin Forum

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

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:

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.

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.

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.

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

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.

"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

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

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

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


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



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?

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.

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.

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.

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.

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

I found this on the Internet - http://zoo.cs.yale.edu/classes/cs426/2012/bib/castro99practical.pdf

“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: cypherpunks@al-qaeda.net
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

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 :D

The first person in history to solve the "Byzantine Generals Problem" was the Byzantine Generals' new mistress.  :D