Topic: How To Describe Bitcoins Solution To The Byzantine Generals Problem? (Read 1494 times)

Your approach is very complex.The generals do not decide a date, they decide the target and to attack or not.

If you decide tower1 and attack.The generals majority have attacked to tower2.There are more soldiers attacking to tower (chain length is longer).Being the part of army you quit your position and attack to tower2 to take part of the victory.

Precisely! it sound simple enough, just create order without a central power being in charge, but turns out to be pretty darn complicated, though possible as is proven by the success of bitcoin.

Reading Satoshi's White Paper I found this:


The only thing I am missing in my previous description it seems is steps 5 and 6.

So a general receives votes from all 10 generals which is something like 6 for sunday, 3 for saturday, and one for monday, and he works on the sudoku puzzle to record these votes. Then he receives a completed puzzle which shows 10 votes for monday. He can verify that the puzzle is solved correctly, but he doesn't trust the votes attached to it, so he can reject it!

He then either receives a different solved block with the correct votes from another general who noticed the same thing or he does this himself, broadcasting his recorded votes with the solved puzzle, and getting to work on the next block.

I just re-read this:
https://bitcointalk.org/oldSiteFiles/byzantine.html (related to proof-of-work chains)
and found a nice classic version:
http://pages.cs.wisc.edu/~sschang/OS-Qual/reliability/byzantine.htm

There are two directions to choose from:
1) Complex, precise, "military style":

Byzantine General Problem
   The Classic Problem
   Each division of Byzantine army are directed its own general
   Generals, some of which are traitors, communicate each other by messengers
   Requirements:
   All loyal generals decide upon the same plan of action
   A small number of traitors cannot cause the loyal generals to adopt a bad plan
   The problem can be restated as:
   All loyal generals receive the same information upon which they will somehow get to the same decision
   The information sent by a loyal general should be used by all the other loyal generals
   The above problem can be reduced into a series of one commanding general and multiple lieutenants problem - Byzantine Generals Problem :
   All loyal lieutenants obey the same order
   If the commanding general is loyal, then every loyal lieutenant obeys the order she sends
Reliability by Majority Voting
   One way to achieve reliability is to have multiple replica of system (or component) and take the majority voting among them
   In order for the majority voting to yield a reliable system, the following two conditions should be satisfied:
   All non-faulty components must use the same input value
   If the input unit is non-faulty, then all non-faulty components use the value it provides as input
Impossibility Results
   No solution exists if less than or equal to 2/3 generals are loyal
A Solution with Oral Messages - No Signature
Oral Message Requirements and their Implications
   A1 - Every message that is sent is delivered correctly
   The failure of communication medium connecting two components is indistinguishable from component failure
   Line failure just adds one more traitor component
   A2 - The receiver of a message knows who sent it
   No switched network is allowed
   The later requirement -- A4 nullifies this constraint
   A3 - The absence of a message can be detected
   Timeout mechanism is needed
Solution
   If less than 1/3 generals are traitors, this problem can be solved....
http://pages.cs.wisc.edu/~sschang/OS-Qual/reliability/byzantine.htm


2) Simple:
The essence is creating order without a central power being in charge.
"The first general to send a text message about a current victory wins a cash prize, and everyone starts the next battle". 

Thank you that was one question i had.

So the problem the generals have is they are trying to arrive at an agreement on what time to attack the city, obviously the attack will occur in the future after the agreement is made.

When a block is solved, what is broadcast to the network is first a "proof of work" but also a record of all of the generals votes. Essentially whoever is able to solve the block first has the authority to set in stone what all of the votes were for that round. After twelve rounds, they agree that whichever time had the most votes as recorded in all 12 blocks of the block chain will be the time they will all attack the city.

Does this sound like a good description? I feel like I'm getting closer!

Too complicated (for example), why vote on the date? The block (once solved) is happening now, not later (more details below)



If anyone was working on a different attack time, they switch to this one...
If a 2nd "general" solves a block a split-second after the original, then the 1st one "wins" since they broadcast earlier and will get above 51% of the network following their chain first.

what if the others were all working on puzzles that said, "Retreat"?
Bitcoin never retreats, the puzzle gets attacked relentlessly, until victory is achieved.
ps. The "message" being sent is very simple (in this case, a 'block' of transactions) there is no direct comparison to a "real battlefield" during wartime.

turning clock times into equal-length strings, I have no idea what this means. sounds interesting though

I guess I am trying to work this out within the analogy of the Byzantine Generals, I try to layout what I have so far:

There are 10 Generals in separated camps surround the city. They decide that they will agree to whatever time has the most votes after 12 puzzles are solved. As they begin, each Generals sends out 9 messengers with his preferred attack time. He then receives messengers from each of the other Generals with their own preferred attack times and he begins working on the first sudoku puzzle.

Soon a messenger arrives with a completed version of the puzzle along with a record showing that there were 3 generals who wanted to attack on saturday, 4 generals who wanted to attack on Sunday, 2 who wanted Wedsnday, and one that wanted Monday. The general then sends 9 messengers out to the other generals saying that he agrees that they should attack on Saturday, the other generals do the same and he receives all of their votes for the second round, and begins working on the second sudoku puzzle.

Soon a messenger arrives with a completed second puzzle attached to the record kept during the first puzzle. The Second completed puzzle arrives with a record showing that there were 5 votes for Sunday, 4 votes for Saturday, and just one vote for Monday. The general then sends out 9 messengers with his vote for Saturday, and soon 9 messengers arrive with new votes from each of the other generals, and he begins working not he third puzzle.

This time he sup rising even himself, by luck almost, is actually able to solve the sudoku puzzle himself! He records that he received this time 7 votes for Sunday, 2 votes for saturday, and just one vote for Monday, he attaches this to the completed third puzzle along with the chain of the previous two puzzles and sends 9 copies out to each of the Generals.

This process repeats and after 12 rounds of this the record shows that Sunday received the most votes, and so they agree to attack on Sunday.

Is this accurate? Any changes you'd suggest?

To keep it simple, you might only consider the attack time, just
as Satoshi does, not commands.

Satoshi goes on to say that the general starts to hash "the first
attack time he receives", but it seems to me that it would be
equally good for them to hash different attack times until a hash
is found that satisfies some condition, on which they had agreed
previously - like the hash being lower than a predefined number
(representing difficulty).

I don't have experience in sudoku, so I can't say how well
it would translate to that metaphor. But the idea that hashing in
this case is like turning clock times into equal-length strings,
would not be beyond most "laymen".

I've read that before yes, he says,
I think I will be settling on Sudoku puzzles as my metaphor. But how would that go? So the generals are all trying to agree either to "attack" or "retreat" in it's simplest form. So at first, everyone sends out messengers to the others saying either "attack" or "retreat". Whatever a general hears first, he starts formulating that into a sudoku puzzle. Whichever general solves the sudoku puzzle then sends the completed puzzle to all the other generals with the word "attack" imbedded in it.

That seems to work okay, but what I am confused about is what happens next. Satoshi says,
So does that mean whatever that first completed puzzle says is what they inevitably must go with?? What if the person who solved the first puzzle was the only General who wanted to attack, what if the others were all working on puzzles that said, "Retreat"? After they receive the first completed puzzle that says, "Attack", is it possible the next completed puzzle could say "retreat"?

The best explanation, from the master himself:

http://satoshi.nakamotoinstitute.org/emails/cryptography/11/

Im wondering if Sudoku puzzles is the best metaphor as suggested by Andreas Antonopolus….

Satoshi resolved the Byzantine Generals Problem by implementing a proof of work chain. yeah cool but that means nothing to civilian walking down the street. How is the best way to describe satoshis solution to a lamen?

The generals are surrounding the city they wish to attack and need to arrive at an agreement about what time to attack, or whether to retreat and they can only communicate through messengers. Well there's the setup, now how does Satoshi's solution translate into the scenario?

Should we say that each general sets to work trying to build a structure of some, like a duplicate of the mona lisa or a famous sculpture, or they are each given a box with a combination lock that needs to be cracked to open it, once they crack the combination they can put their plan to attack at a given time in the box and sending to the others with their messenger? Maybe the combination of the first box is needed to begin working on the next box's combination and whoever cracks that combination first can put his plan of attack and in time in with the first one?

I don't know, I want to be able to make this an easy to understand and accurate analogy, but I'm having trouble!