4 ms·

Paxos is Byzantine Fault Tolerant. A malicious node is a special case of failed node. "The objective of Byzantine fault tolerance is to be able to defend again

by sigil 13y ago

Paxos is Byzantine Fault Tolerant. A malicious node is a special case of failed node. "The objective of Byzantine fault tolerance is to be able to defend against Byzantine failures, in which components of a system fail in arbitrary ways (i.e., not just by stopping or crashing but by processing requests incorrectly, corrupting their local state, and/or producing incorrect or inconsistent outputs)." http://en.wikipedia.org/wiki/Byzantine_fault_tolerance http://en.wikipedia.org/wiki/Byzantine_fault_tolerance

VMG 13y ago
This is what I found about it: > The bitcoin system is based around the "block chain", whose main purpose is to implement a distributed timestamp. With a known set of participants, this is a solved problem (Paxos algorithm); on the public Internet with undefined participant list, it's hard. http://www.baum.com.au/~jiri/ae/blog/01306143707 http://www.baum.com.au/~jiri/ae/blog/01306143707
hendzen 13y ago
That is a correct definition of BFT, but as I said, Paxos does not tolerate Byzantine faults. Here's a direct quote [0] from Leslie Lamport, the author of the Paxos algorithm. Assume that agents can communicate with one another by sending messages. We use the customary asynchronous, non-Byzantine model, in which: • Agents operate at arbitrary speed, may fail by stopping, and may restart. Since all agents may fail after a value is chosen and then restart, a solution is impossible unless some information can be remembered by an agent that has failed and restarted. • Messages can take arbitrarily long to be delivered, can be duplicated, and can be lost, but they are not corrupted. So, to be clear, Paxos tolerates processes that crash arbitrarily, but not processes that send malicious or incorrect messages. For a consensus algorithm that does tolerate Byzantine faults, see Liskov's Practical Byzantine Fault Tolerance [1]. [0] - http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf http://research.microsoft.com/en-us/um/people/lamport/pubs/p... [1] - http://www.pmg.lcs.mit.edu/papers/osdi99.pdf http://www.pmg.lcs.mit.edu/papers/osdi99.pdf
- sigil 13y ago
  I referred in the top level comment above to Byzantine Paxos, a modified version of Paxos that is BFT. http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzantine_Paxos http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzant...
  - hendzen 13y ago
    Ah - when the term Paxos is used it is usually in reference to the original, non-BFT algorithm. Also, Google's implementations of Paxos (in Chubby, as well as Megastore) are non-BFT, and I am not aware of any use of Byzantine Paxos in production elsewhere.
    - sigil 13y ago
      Interesting, and makes sense. Why would you need the full BFT Paxos among trusted participants? Still, the claim that Bitcoin represents "a breakthrough in computer science" on the Byzantine Generals Problem rings false to me. First, we already had BFT algorithms, just no compelling need for them. Second, if this is really a computer science breakthrough, where's the proof? Don't get me wrong, I think Bitcoin is an enormous breakthrough in engineering terms. It's just too important now to not have the proven properties we're relying on.

by sigil 13y ago

VMG 13y ago

This is what I found about it: > The bitcoin system is based around the "block chain", whose main purpose is to implement a distributed timestamp. With a known set of participants, this is a solved problem (Paxos algorithm); on the public Internet with undefined participant list, it's hard. http://www.baum.com.au/~jiri/ae/blog/01306143707 http://www.baum.com.au/~jiri/ae/blog/01306143707

hendzen 13y ago

That is a correct definition of BFT, but as I said, Paxos does not tolerate Byzantine faults. Here's a direct quote [0] from Leslie Lamport, the author of the Paxos algorithm. Assume that agents can communicate with one another by sending messages. We use the customary asynchronous, non-Byzantine model, in which: • Agents operate at arbitrary speed, may fail by stopping, and may restart. Since all agents may fail after a value is chosen and then restart, a solution is impossible unless some information can be remembered by an agent that has failed and restarted. • Messages can take arbitrarily long to be delivered, can be duplicated, and can be lost, but they are not corrupted. So, to be clear, Paxos tolerates processes that crash arbitrarily, but not processes that send malicious or incorrect messages. For a consensus algorithm that does tolerate Byzantine faults, see Liskov's Practical Byzantine Fault Tolerance [1]. [0] - http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf http://research.microsoft.com/en-us/um/people/lamport/pubs/p... [1] - http://www.pmg.lcs.mit.edu/papers/osdi99.pdf http://www.pmg.lcs.mit.edu/papers/osdi99.pdf

sigil 13y ago
I referred in the top level comment above to Byzantine Paxos, a modified version of Paxos that is BFT. http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzantine_Paxos http://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzant...
- hendzen 13y ago
  Ah - when the term Paxos is used it is usually in reference to the original, non-BFT algorithm. Also, Google's implementations of Paxos (in Chubby, as well as Megastore) are non-BFT, and I am not aware of any use of Byzantine Paxos in production elsewhere.
  - sigil 13y ago
    Interesting, and makes sense. Why would you need the full BFT Paxos among trusted participants? Still, the claim that Bitcoin represents "a breakthrough in computer science" on the Byzantine Generals Problem rings false to me. First, we already had BFT algorithms, just no compelling need for them. Second, if this is really a computer science breakthrough, where's the proof? Don't get me wrong, I think Bitcoin is an enormous breakthrough in engineering terms. It's just too important now to not have the proven properties we're relying on.