13 ms·

So we could say, the newest version of the bitcoin software correctly solves the Byzantine General problem, though older versions faltered. And this could be t

So we could say, the newest version of the bitcoin software correctly solves the Byzantine General problem, though older versions faltered. And this could be the case ad infinitum if the protocol needs to be changed due to newly discovered flaws. In summary, unless there are no bugs in your p2p software, it's very hard to solve the Byzantine General problem without outside consensus.

DennisP 13y ago
No, either version alone solved the problem just fine. It was just when some people had one version, and other people had another version, that the problem arose. The solution was actually to revert to the older version. The new version wasn't buggy, but had made a small and intentional change to the protocol. So what it showed was that it's hard to reach consensus between two groups who aren't running the same protocol. Bitcoin is pretty conservative about protocol changes for this reason, though they've worked on getting better at managing it.
- goldenkey 13y ago
  Right on. So basically, Bitcoin solved part of the problem. The bigger unsolved, ie. not automated, problem would be adaptive updating with care to the intricacies of the diff between old and new behavior. And security in the process to prevent a mutiny or hostile takeover in the vulnerable split state. Obviously updates can't be atomic with so many players. This kind of topic is worthy of a thesis. Thoughts?
  - tadfisher 13y ago
    Include a complete description of the protocol in `x`?
  - greyman 13y ago
    Yes, this is something above the Byzantine Generals Problem - that scenario didn't take into consideration, that the general's "agenda" is changing over time. Another interesting angle is, that in case of Bitcoin, both groups have vested interest to cooperate with the other group and having the matter resolved as soon as possible; that's what actually happened in March. It seems to me like a variant of the "Prisoner's dilemma". This is what I think that the "hostile takeover" is highly unlikely (in Bitcoin scenario), since that would very quickly brought the BTC value down. So like in the Prisoner's dilemma, both groups will become silent and cooperate, rather than "betray" the other.
chrisseaton 13y ago
I still don't understand how it solves it. I get that you can agree a time, but how does it solve the problem that each general needs to be certain that all the other generals are also certain? I may have seen a completed block chain for the attack and time, but how do I know all the other generals have also seen it? I know they signed part of it, but how do I know the completed chain then got back to them? If it didn't they're not going to attack and my army will be destroyed.
- greyman 13y ago
  By proof-of-work mechanism. Here I dug up the explanation of the Satoshi himself: http://www.mail-archive.com/cryptography@metzdowd.com/msg09997.html http://www.mail-archive.com/cryptography@metzdowd.com/msg099...
- SkyMarshal 13y ago
  The time delay introduced by the proof of work is the key to all your questions. Imagine 10 generals in the network all trying to agree on a time of attack. Each simultaneously sends 9 couriers to the other generals suggesting an attack time. That's 90 couriers with 10 different messages all pinging around the system simultaneously. Each general receives 9 messages at roughly the same time, and either has to choose one to sign and rebroadcast, or cheat and sign multiple and rebroadcast them. There are too many options available at any given time, and odds of reaching consensus aren't good. However, by introducing a time delay you slow the rate of message passing enough to be manageable - now's there's only 9 couriers and 1 message pinging around the system at the same time. All nodes in the network work the same problem, but only one will find a solution first and broadcast it, and with the time delay there's enough time for that solution to disseminate through most of the network before another node discovers another solution and broadcasts it. By the time the second and subsequent solutions are found, the the first has disseminated to enough nodes that they've already incorporated it into the next proof-of-work, and reject subsequent solutions to the prior PoW.
  - chrisseaton 13y ago
    I still don't see the solution - doesn't any solution have to solve the problem of messages being lost? Say that after some time a block that is long enough is made by some general A and is distributed to generals B and C. General D doesn't get it though - his messenger is killed in transit. He helped make an earlier block, but has never seen the fully completed block. How do the other generals know that he hasn't got the final block that is long enough? Or is it just the case that a majority of generals know when to attack? I thought it had to be all of them, but maybe that's the two-general problem and Byzantine-general's is an easier problem. I was pretty sure there were multiple good proofs of the impossibility of a solution.

DennisP 13y ago

No, either version alone solved the problem just fine. It was just when some people had one version, and other people had another version, that the problem arose. The solution was actually to revert to the older version. The new version wasn't buggy, but had made a small and intentional change to the protocol. So what it showed was that it's hard to reach consensus between two groups who aren't running the same protocol. Bitcoin is pretty conservative about protocol changes for this reason, though they've worked on getting better at managing it.

goldenkey 13y ago
Right on. So basically, Bitcoin solved part of the problem. The bigger unsolved, ie. not automated, problem would be adaptive updating with care to the intricacies of the diff between old and new behavior. And security in the process to prevent a mutiny or hostile takeover in the vulnerable split state. Obviously updates can't be atomic with so many players. This kind of topic is worthy of a thesis. Thoughts?
- tadfisher 13y ago
  Include a complete description of the protocol in `x`?
- greyman 13y ago
  Yes, this is something above the Byzantine Generals Problem - that scenario didn't take into consideration, that the general's "agenda" is changing over time. Another interesting angle is, that in case of Bitcoin, both groups have vested interest to cooperate with the other group and having the matter resolved as soon as possible; that's what actually happened in March. It seems to me like a variant of the "Prisoner's dilemma". This is what I think that the "hostile takeover" is highly unlikely (in Bitcoin scenario), since that would very quickly brought the BTC value down. So like in the Prisoner's dilemma, both groups will become silent and cooperate, rather than "betray" the other.

chrisseaton 13y ago

I still don't understand how it solves it. I get that you can agree a time, but how does it solve the problem that each general needs to be certain that all the other generals are also certain? I may have seen a completed block chain for the attack and time, but how do I know all the other generals have also seen it? I know they signed part of it, but how do I know the completed chain then got back to them? If it didn't they're not going to attack and my army will be destroyed.

greyman 13y ago
By proof-of-work mechanism. Here I dug up the explanation of the Satoshi himself: http://www.mail-archive.com/cryptography@metzdowd.com/msg09997.html http://www.mail-archive.com/cryptography@metzdowd.com/msg099...
SkyMarshal 13y ago
The time delay introduced by the proof of work is the key to all your questions. Imagine 10 generals in the network all trying to agree on a time of attack. Each simultaneously sends 9 couriers to the other generals suggesting an attack time. That's 90 couriers with 10 different messages all pinging around the system simultaneously. Each general receives 9 messages at roughly the same time, and either has to choose one to sign and rebroadcast, or cheat and sign multiple and rebroadcast them. There are too many options available at any given time, and odds of reaching consensus aren't good. However, by introducing a time delay you slow the rate of message passing enough to be manageable - now's there's only 9 couriers and 1 message pinging around the system at the same time. All nodes in the network work the same problem, but only one will find a solution first and broadcast it, and with the time delay there's enough time for that solution to disseminate through most of the network before another node discovers another solution and broadcasts it. By the time the second and subsequent solutions are found, the the first has disseminated to enough nodes that they've already incorporated it into the next proof-of-work, and reject subsequent solutions to the prior PoW.
- chrisseaton 13y ago
  I still don't see the solution - doesn't any solution have to solve the problem of messages being lost? Say that after some time a block that is long enough is made by some general A and is distributed to generals B and C. General D doesn't get it though - his messenger is killed in transit. He helped make an earlier block, but has never seen the fully completed block. How do the other generals know that he hasn't got the final block that is long enough? Or is it just the case that a majority of generals know when to attack? I thought it had to be all of them, but maybe that's the two-general problem and Byzantine-general's is an easier problem. I was pretty sure there were multiple good proofs of the impossibility of a solution.