Re:It's time for us in the tech world to speak out about cry...
by ashtonkem on Monday May 31, 2021 @03:15PM
(#27347259)
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.
Re:It's time for us in the tech world to speak out about cry...
by lapinot on Monday May 31, 2021 @05:33PM
(#27348193)
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.
Re:It's time for us in the tech world to speak out about cry...
by madmax96 on Monday May 31, 2021 @07:46PM
(#27349342)
>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 ;).
https://en.wikipedia.org/wiki/Paxos_(computer_science) An old algorithm used for sharding big-data databases.
https://en.wikipedia.org/wiki/Raft_(algorithm) A simplified version of paxos.
http://www.scs.stanford.edu/~dm/home/papers/losa:stellar-ins... The new paper about SCP which allows replication with subjective notions of trust (no central participant-stake list like paxos/raft).
ps: actually i remove "chained" from the idea. If you want to keep the whole authenticated linked-list thing and do it right you'll end up somewhere near https://irmin.org/ (a generalization of git), which is very useful, but doesn't tackle the "strong decentralized commit". You'll probably want to either centrally manage the "lastest-hash(s)" (like git is usually done), or pair it with a state-machine replication protocol. In that last case it may seem useless to use the chained thing if you already have a real replication protocol, but it is much like using public-key crypto for encrypting small ephemeral symmetric keys and encrypting actual data with symmetric crypto: it's an optimization.