3 ms·

> There is a huge scientific merit of the algorithms for reaching a distributed consensus when not all participants can be trusted Yes, they existed a long tim

• aleph_minus_one 1y ago
  > Yes, they existed a long time ago and aren't wasteful as a way to generate "value". Can you give me a literature reference for such a result, because this claim surprises me. Of course Merkle trees existed long before - but they are just "cryptographically signed data structures", and thus don't solve the distributed consensus problem. Of course eCash existed long before - but it depended on some central authority. Of course distributed consensus algorithms existed long before - but they depended on the fact that all participants are trustable. Thus, in my opinion Satoshi Nakamoto indeed made a really important scientific contribution for a quite specific algorithmic problem.
  • FabHK 1y ago
    > Of course distributed consensus algorithms existed long before - but they depended on the fact that all participants are trustable. No. They depended on the fact that all participants were known (in other words, the permissioned setting). Among those known ones, some (less than n/3) could go bonkers, all the way byzantine, and the honest nodes would still be guaranteed to find consensus (with consistency and availability).
    • ycombinatrix 1y ago
      I'm pretty sure there's no guarantee to find consensus. Even if all nodes are functional.
      • FabHK 1y ago
        Depending on the networking assumptions, of course there is. That's the whole point of SMR: under certain assumptions, you can attain availability and consistency.
        • ycombinatrix 1y ago
          No. Paxos does not guarantee consensus.
          • FabHK 1y ago
            The basic results of SMR theory are as follows, where "sync", "async" and "partially sync" refer to specific network models; PKI is public key infrastructure (that is, each node knows all the other nodes and has their public keys); "f" is the number of failed/dishonest/byzantine nodes (out of n total nodes); and only deterministic protocols are considered. 1) Permissioned, Sync, PKI: SMR possible, any f (!), Dolev-Strong (1983, [-5]) 2) Permissioned, Sync, no PKI: SMR impossible if f >= n/3, PSL (1980), FLM (1985) (the hexagon proof, [-4]) 3) Permissioned, Async: SMR impossible even with f=1 (!), FLP (1985) ("endless bivalent", [-3]) 4) Permissioned, partially sync: SMR with "eventual availability" impossible if f >= n/3 [-2], possible otherwise (eg Tendermint [-1], Byzantine Paxos, PBFT) In setting 4), PBFT-type protocols such as Tendermint guarantee consistency (among the "honest" nodes following the protocol as intended - you can't make any guarantees wrt to faulty or byzantine nodes) and eventual availability (that is, all requests sent by clients will "sooner or later" be dealt with) once network functionality is resumed. That is consensus, for all intents and purposes, given that more consensus isn't really possible due to 2), 3). And arguably better consensus than Nakamoto consensus, which improves the boundary in 4) to n/2 (without selfish mining) at the cost of being stochastic, not deterministic, but replaces "consistency always, availability eventually" with "consistency eventually, availability always", arguably the wrong choice for financial applications. [-5] https://timroughgarden.github.io/fob21/l/l2.pdf https://timroughgarden.github.io/fob21/l/l2.pdf [-4] https://timroughgarden.github.io/fob21/l/l3.pdf https://timroughgarden.github.io/fob21/l/l3.pdf [-3] https://www.youtube.com/watch?v=vJhm9uhd34E&list=PLEGCF-WLh2RLOHv_xUGLqRts_9JxrckiA&index=17 https://www.youtube.com/watch?v=vJhm9uhd34E&list=PLEGCF-WLh2... [-2] https://timroughgarden.github.io/fob21/l/l6.pdf https://timroughgarden.github.io/fob21/l/l6.pdf [-1] https://timroughgarden.github.io/fob21/l/l7.pdf https://timroughgarden.github.io/fob21/l/l7.pdf