3 ms·

There’s a reason why the blockchain algorithms are quite different from Raft et. al.; blockchain systems need to deal with the existence of hostile actors, whil

There’s a reason why the blockchain algorithms are quite different from Raft et. al.; blockchain systems need to deal with the existence of hostile actors, while most consensus algorithms need to deal only with unreliable actors. The existence of hostile actors changes the requirements a lot, and goes to explain why cryptocurrencies went a different way.

lapinot 5y ago
Respectful disagree, i believe you are factually wrong. Wikipedia already lists 2 paxos variants that have byzantine security. Not sure about their implementation, but in production there is also SCP, which is used for real-money transactions by the stellar network. All these actually have proofs of some security and liveliness properties under some byzantine faults. Additionaly, blockchains themselves don't solve this problem properly: they don't even have a notion of "commit", any transaction could be reverted, it is just more and more intractable to do so, thus every property is much weaker and only probabilistic.
- madmax96 5y ago
  >Wikipedia already lists 2 paxos variants that have byzantine security One of those mentioned is Fast byzantine consensus (FBC) [1]. FBC provides an optimal algorithm for a 2 phase commit system w/ byzantine agents. But FBC requires that each correct process sends a message to each other. This is O(n^2) and does not scale. Bitcoin (specifically, others differ) maintain some of the invariants with extremely high probability over time. High enough to be useful. In exchange, bitcoin's network scales much better. Really, it just needs O(n) messages to confirm a transaction. Of course, PoS like Ethereum's takes much inspiration from byzantine paxos. But I wouldn't call this a solve problem, and crypto has innovated in this space. We can just debate whether or not the innovation has been worthwhile ;). [1] https://www.cs.utexas.edu/~lorenzo/papers/fab.pdf https://www.cs.utexas.edu/~lorenzo/papers/fab.pdf

lapinot 5y ago

Respectful disagree, i believe you are factually wrong. Wikipedia already lists 2 paxos variants that have byzantine security. Not sure about their implementation, but in production there is also SCP, which is used for real-money transactions by the stellar network. All these actually have proofs of some security and liveliness properties under some byzantine faults. Additionaly, blockchains themselves don't solve this problem properly: they don't even have a notion of "commit", any transaction could be reverted, it is just more and more intractable to do so, thus every property is much weaker and only probabilistic.

madmax96 5y ago
>Wikipedia already lists 2 paxos variants that have byzantine security One of those mentioned is Fast byzantine consensus (FBC) [1]. FBC provides an optimal algorithm for a 2 phase commit system w/ byzantine agents. But FBC requires that each correct process sends a message to each other. This is O(n^2) and does not scale. Bitcoin (specifically, others differ) maintain some of the invariants with extremely high probability over time. High enough to be useful. In exchange, bitcoin's network scales much better. Really, it just needs O(n) messages to confirm a transaction. Of course, PoS like Ethereum's takes much inspiration from byzantine paxos. But I wouldn't call this a solve problem, and crypto has innovated in this space. We can just debate whether or not the innovation has been worthwhile ;). [1] https://www.cs.utexas.edu/~lorenzo/papers/fab.pdf https://www.cs.utexas.edu/~lorenzo/papers/fab.pdf