4 ms·

Taking away the money part you'll probably want to replace "distributed chained ledger" with "distributed database" or "state-machine replication". There's actu

Taking away the money part you'll probably want to replace "distributed chained ledger" with "distributed database" or "state-machine replication". There's actually a nice academic literature on this topic of having distributed databases that have strong notions of "commit". This is never the case with stuff that gets called "blockchain". I've yet to encounter something that isn't a variation on "rate-limit the ingest so we have time to replicate operations world-wide" or "create internal monkey-money incentives for agents not to diverge from corretness", both of which are trivial hacks that don't advance anything from a scientific point of view. Not my field tho, so here's the few refs i know. https://en.wikipedia.org/wiki/Paxos_(computer_science) https://en.wikipedia.org/wiki/Paxos_(computer_science) An old algorithm used for sharding big-data databases. https://en.wikipedia.org/wiki/Raft_(algorithm) https://en.wikipedia.org/wiki/Raft_(algorithm) A simplified version of paxos. http://www.scs.stanford.edu/~dm/home/papers/losa:stellar-instantiation.pdf 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/ 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.

ashtonkem 5y ago
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

ashtonkem 5y ago

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