6 ms·
Making CRDTs Byzantine Fault Tolerant [pdf]
- omeze 5y agoThis is pretty interesting! Skiff (https://www.skiff.org/ https://www.skiff.org/) also uses private, encrypted CRDTs for their collaborative docs, but not in a BFT manner (the updates are encrypted but still sent to a central server AFAIK).
- amilich 5y agoYes, we use E2EE CRDTs! They don't have to be centralized because we still get composable updates using YJS (https://github.com/yjs/yjs https://github.com/yjs/yjs). This would still help a ton given the p2p nature of updates (malicious or broken clients can cause havoc for documents).
- 9wzYQbTYsAIc 5y agoIs Byzantine Fault Tolerance starting to pick up steam in interest? Any other related news anyone knows of off the top of their head?
- posharma 5y agoMartin's writing and explanation style is truly awesome! I read his book DDIA (Designing data intensive applications) and listened to his distributed systems class lectures [1]. It was a joy learning. I wish I had him or someone like him in graduate school. I would've probably taken all his courses :-). [1] https://www.youtube.com/watch?v=UEAMfLPZZhE&list=PLeKd45zvjcDFUEv_ohr_HdUFe97RItdiB https://www.youtube.com/watch?v=UEAMfLPZZhE&list=PLeKd45zvjc...
- fwoty 5y agoSeriously. My advice to all, if you see "Kleppmann", click the link.
- narush 5y agoWoah. This paper looks freaking awesome - and surprising! “The proposed scheme can tolerate any num- ber of Byzantine nodes (making it immune to Sybil attacks)” - this is really intriguing because of the strong impossibility results in consensus algorithms around how many faulty nodes can be tolerated. I’m looking forward to reading more than just the abstract tho (confession). Martin - thanks for all your cool work!
- noodles_nomore 5y agoConsensus is only necessary when one needs to decide between conflicting choices, and CRDTs are by definition conflict-free. Nodes only need to verify that any update to the CRDT is in fact a legal operation on the data structure. Essentially, the paper details how to ensure two properties: (1) All nodes will eventually receive all legal updates, and (2) no node will accept a malformed update, (and crafting undetectable malformed updates is infeasible).
- rocqua 5y agoCould this be used to prevent double spends by marking such a spend as 'an illegal update'? I imagine not, but I wonder what limitation of CRDTs would prevent this.
- Ar-Curunir 5y agospends don’t commute: if two transactions both consume $1, and the senders account only contains $1, there’s no way to apply both transactions and end up in a valid state.
- rocqua 5y agoThat makes sense. Thanks.
- dboreham 5y agoMoney requires consensus. I think it's the FLP Impossibility result that ultimately prevents CRDT-type (eventually consistent) schemes from implementing consensus. Researchers in eventual consistency pretty much just assume this. e.g. in the original CRDT papers -- bottom of page 10 in : https://arxiv.org/pdf/1805.06358.pdf https://arxiv.org/pdf/1805.06358.pdf; top of page 11 in : https://hal.inria.fr/inria-00609399v1/document https://hal.inria.fr/inria-00609399v1/document
- almog 5y agoI recently finished a 2nd reading of DDIA and while listening to a podcast featuring an interview with Martin Kleppmann, I got so thrilled when he mentioned that he plans to release another book in the coming years. DDIA is so good that I feel the same kind of anticipation I have as when waiting for a next in a series fantasy book to take me back to a parallel world with characters I've come to love and miss like one misses a good friend they haven't seen for a while.
- shanxS 5y agoWhich podcast?
- almog 5y agoMartin mentioned it during the last few minutes of Coding Over Cocktails as one reason why you might want to support his Patreon page: https://www.torocloud.com/podcast/designing-data-intensive-applications-martin-kleppmann https://www.torocloud.com/podcast/designing-data-intensive-a... https://www.patreon.com/martinkl https://www.patreon.com/martinkl
- almog 5y agoExact quote (via transcript): "And finally, if you're interested in supporting this kind of thing financially, I did set up a Patreon account with the goal of trying to turn this into a potential career of an independent researcher, not tied to any institution necessarily, but just being able to continue doing the research and the teaching the work that I do, perhaps writing books, and the second edition of my current book is potentially in the works."
- autoconfig 5y agoDDIA = Designing Data Intensive Applications
- adamnemecek 5y agoDid he say anything on the topic of the book?
- somezero 5y ago> The 3f + 1 assumption means these protocols cannot be deployed in open peer-to-peer systems, since they would be vulnerable to Sybil attacks. In contrast, my approach makes no assumption about the number of Byzantine nodes. I'm confused - probably because I haven't finished reading the paper. 1. Sybil-proof-ness requires a CA [1]. It's orthogonal to whether or not a protocol is BFT. Specifically, the classical BFT protocols "assume" there exist a CA, and then prove their protocols to be BFT. 2. I won't comment whether 3f+1 protocols cannot be deployed in open P2P systems (they can), but "makes no assumption about the number of Byzantine nodes" is weird. This result is valid in a particular system/time model eg. With PKI, in synchronous setting, for any `f` one can achieve consensus in `f+1` rounds using Dolev-Strong. This means you make no assumption about `n`, but the protocol is impractical for variety of reasons eg. large `n`, strong synchrony etc. [1] https://www.microsoft.com/en-us/research/wp-content/uploads/2002/01/IPTPS2002.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
- pdpi 5y agoThe big novel feature in Nakamoto consensus (the Bitcoin paper one) is precisely that it gives you Sybil-proof BFT without a CA. That's the whole reason for the massive energy consumption.
- somezero 5y agoIt doesn't give you sybil-proof. It gives you sybil-resistance, and that, in a non-deterministic protocol.
- wyager 5y agoIt gives you sybil resistance with arbitrarily low probability of failure, so you might as well say "proof".
- somezero 5y agoI'm fine with a sybil resistance mechanism (although it's not sybil-proof, and some particular forms of sybil-resistance are based on faulty models [1]) The problem is that this paper doesn't employ such mechanisms: > This assumption is problematic for P2P systems...they must either exercise centralised control over which nodes are allowed to join the network, or employ expensive Sybil countermeasures such as proof-of-work [30]. This paper shows... is possible to guarantee the standard CRDT consistency properties even in systems in which arbitrarily many nodes are Byzantine, e.g. where the Byzantine nodes outnumber the correct nodes. This makes the algorithms immune to Sybil attacks... This argument is incorrect. The counter-example is Dolev-Strong [2]. The number of faulty nodes is not fixed, but still needs a CA. [1] https://eprint.iacr.org/2020/019.pdf https://eprint.iacr.org/2020/019.pdf [2] Section 3.4 of http://elaineshi.com/docs/blockchain-book.pdf http://elaineshi.com/docs/blockchain-book.pdf
- sbazerque 5y agoHyper Hyper Space [1] is a library for modeling distributed data structures that uses operational CRDTs represented over a Merkle-DAG (using the partial order defined by causal relationships, like the paper describes). It is also designed to work in a Byzantine environment (it can run inside a browser, using WebCrypto, WebRTC, etc. to connect to untrusted peers over the open internet). [1] https://www.hyperhyperspace.org https://www.hyperhyperspace.org
- davidrusu 5y agoReally nice to see BFT starting to be taken seriously in CRDT research. I had done some research in this area last year and came to a lot of the same solutions (i.e. BRB protected CRDTs when dealing with VClock based CRDTs): https://github.com/davidrusu/bft-crdts https://github.com/davidrusu/bft-crdts We ended up moving away from VClock crdts entirely for our work and going with grow-only hash-graph CRDTs as they have don't need the BRB overhead (as Martin has found in his research as well).
- hecturchi 5y agoThe idea of DAG-embedded CRDTs is far from new and was introduced here: https://arxiv.org/abs/2004.00107 https://arxiv.org/abs/2004.00107 (I'm among the authors) Unfortunately, the verification that the author proposes (not accepting new updates until the dag below is verified) will need a lot of caveats for real world usage. Currently we use these CRDTs for a key value database of 40M+ keys in a deployment of ipfs-cluster, which uses https://github.com/ipfs/go-ds-crdt https://github.com/ipfs/go-ds-crdt .
- archagon 5y agogritzko (always on the vanguard!) has also been doing this kind of stuff in RON for a while, though I haven't looked into it deeply enough to determine how much it overlaps with Kleppmann's approach: https://replicated.cc https://replicated.cc
- JonChesterfield 5y agoProtocol looks computationally expensive to me. I think the dag size could get out of hand if an offline but otherwise correct node comes back online. What caveats do you have in mind?
- hecturchi 5y agoDAG size gets out of hand when many operations happen (akin to how a blockchain grows indefinitely). Nodes could however rely on some form of "consensus" to compact/reset the graph at intervals. But then you have invited a consensus into the party which is the opposite of what CRDTs want to have.
- martinkl 5y agoMartin here. I cited your paper in the related work section. It's a good start, but it does not cover everything that's required to achieve BFT — in particular, the issue that an operation may be valid in some contexts and invalid in others, and all correct nodes need to agree on whether an operation is valid or not. If you have more details on the caveats you have discovered, it would be great if you could write them up so that others can learn from your experience!
- mactavish88 5y ago> Further work is required to demonstrate whether the techniques presented here are indeed effective in the context of particular CRDT algorithms, to prove their correctness in the face of Byzantine nodes, and to measure the performance impact of Byzantine fault tolerance. This paper is super interesting, but it'd be even more interesting when we see this future work is completed.