9 ms·

To the uninitiated, bitcoin solves the byzantine general's problem by having each "general" work on a mathematical problem that is known to take a certain avera

by eof 13y ago

To the uninitiated, bitcoin solves the byzantine general's problem by having each "general" work on a mathematical problem that is known to take a certain average amount of time; and, when they solve the problem pass their solution onto the other generals who will then incorporate the answer to the previous problem into a new problem. The "consensus" is intrinsically linked to the "math problem" so that the generals will always "trust" the chain-of-answers which is the longest; as it would be impractical / impossible for an attacker to counterfeit the long-chain-of-answers. Bitcoin uses sha256(sha256( x )) < `target` as its "math problem" where X contains the a hash of the previous "consensus" and new transactions which should become part of the new "consensus". `target` is adjusted over time

tomp 13y ago
Bitcoin doesn't really solve the Byzantine General's Problem, as demonstrated by the March 2012 network split [1], which was later resolved by consensus between users (lead developers and biggest miners) using communication channels outside of the Bitcoin network. [1]: http://en.wikipedia.org/wiki/History_of_Bitcoin#The_fork_of_March_2013 http://en.wikipedia.org/wiki/History_of_Bitcoin#The_fork_of_...
- DennisP 13y ago
  A cursory look at your link reveals that it was caused by an incompatibility between different versions of the bitcoin client; the older client wouldn't accept blocks as large as the later one. People downgraded to the older version, and then "The network reached consensus and continued to operate as normal a few hours after the split." So I guess you could say it only solves the problem when everybody's software implements the same protocol.
  - goldenkey 13y ago
    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.
- deleted 13y ago
  [deleted]
allochthon 13y ago
As problems get more difficult, I think there will be less and less proof-of-work, and people will see less and less of an incentive to keep miners online. Doesn't this mean that security begins to break down as people give up on mining?
- zik 13y ago
  Miners are paid in two ways - from creating new bitcoins and from transaction fees. The transaction fees are small but add up to enough to make it worth mining.
  - wmf 13y ago
    If you do the math on a 1MB block that pays, say, 12.5 BTC of fees the result is pretty sobering. Like over $1 per transaction.
    - gibybo 13y ago
      I would wager pretty strongly that the 1 MB limit will be raised (or removed) in the not-to-distant future.
tikhon 13y ago
i'm a fan of everything by cdixon -- but check out satoshi and others like bohm: Here's satoshi: http://www.mail-archive.com/cryptography@metzdowd.com/msg09997.html http://www.mail-archive.com/cryptography@metzdowd.com/msg099... and paul bohm: http://paulbohm.com/articles/bitcoins-value-is-decentralization/ http://paulbohm.com/articles/bitcoins-value-is-decentralizat...

by eof 13y ago

tomp 13y ago

Bitcoin doesn't really solve the Byzantine General's Problem, as demonstrated by the March 2012 network split [1], which was later resolved by consensus between users (lead developers and biggest miners) using communication channels outside of the Bitcoin network. [1]: http://en.wikipedia.org/wiki/History_of_Bitcoin#The_fork_of_March_2013 http://en.wikipedia.org/wiki/History_of_Bitcoin#The_fork_of_...

DennisP 13y ago
A cursory look at your link reveals that it was caused by an incompatibility between different versions of the bitcoin client; the older client wouldn't accept blocks as large as the later one. People downgraded to the older version, and then "The network reached consensus and continued to operate as normal a few hours after the split." So I guess you could say it only solves the problem when everybody's software implements the same protocol.
- goldenkey 13y ago
  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.
deleted 13y ago
[deleted]

allochthon 13y ago

As problems get more difficult, I think there will be less and less proof-of-work, and people will see less and less of an incentive to keep miners online. Doesn't this mean that security begins to break down as people give up on mining?

zik 13y ago
Miners are paid in two ways - from creating new bitcoins and from transaction fees. The transaction fees are small but add up to enough to make it worth mining.
- wmf 13y ago
  If you do the math on a 1MB block that pays, say, 12.5 BTC of fees the result is pretty sobering. Like over $1 per transaction.
  - gibybo 13y ago
    I would wager pretty strongly that the 1 MB limit will be raised (or removed) in the not-to-distant future.

tikhon 13y ago

i'm a fan of everything by cdixon -- but check out satoshi and others like bohm: Here's satoshi: http://www.mail-archive.com/cryptography@metzdowd.com/msg09997.html http://www.mail-archive.com/cryptography@metzdowd.com/msg099... and paul bohm: http://paulbohm.com/articles/bitcoins-value-is-decentralization/ http://paulbohm.com/articles/bitcoins-value-is-decentralizat...