Making CRDTs Byzantine Fault Tolerant [pdf] • Hacker News Board

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#21

Post by noodles_nomore » Sat, Mar 05, 2022, 3:29 AM UTC

narush wrote: post #4

Woah. 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!

Consensus 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).

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#22

Post by hecturchi » Sat, Mar 05, 2022, 8:31 AM UTC

The idea of DAG-embedded CRDTs is far from new and was introduced here:

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 .

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#23

Post by archagon » Sat, Mar 05, 2022, 9:34 AM UTC

hecturchi wrote: post #22

The idea of DAG-embedded CRDTs is far from new and was introduced here: 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…

gritzko (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

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#24

Post by rocqua » Sat, Mar 05, 2022, 11:05 AM UTC

noodles_nomore wrote: post #21

narush wrote: post #4

Woah. 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!

Consensus 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 undetecta…

Could 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.

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#25

Post by almog » Sat, Mar 05, 2022, 11:08 AM UTC

adamnemecek wrote: post #18

almog wrote: post #5

I 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…

Did he say anything on the topic of the book?

Not really, in his Patreon page he mentions that one of his plans is to "Write another book to complement Designing Data-Intensive Applications"

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#26

Post by rocqua » Sat, Mar 05, 2022, 11:08 AM UTC

somezero wrote: post #7

> 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…

Sybil proofness does not require a CA. The abstract of your link only states that CAs can be a solution. An alternative approach would be to have the system function as long as one member remains non-sybil.

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#27

Post by almog » Sat, Mar 05, 2022, 1:30 PM UTC

almog wrote: post #11

shanxS wrote: post #6

Earlier quoted context omitted.

Which podcast?

Martin 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-a... https://www.patreon.com/martinkl

Exact 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."

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#28

Post by rnikander » Sat, Mar 05, 2022, 2:29 PM UTC

almog wrote: post #5

I 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…

Does this book give ways to deal with the following: a mobile app that works offline (local replica), and then when it's online, syncs (through a server) with other devices' local replicas? I don't even know what to call this situation. I'm sure CRDTs could help with this.

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#29

Post by JonChesterfield » Sat, Mar 05, 2022, 3:09 PM UTC

hecturchi wrote: post #22

The idea of DAG-embedded CRDTs is far from new and was introduced here: 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…

Protocol 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?

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#30

Post by martinkl » Sat, Mar 05, 2022, 3:19 PM UTC

hecturchi wrote: post #22

The idea of DAG-embedded CRDTs is far from new and was introduced here: 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…

Martin 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!