Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Making CRDTs Byzantine Fault Tolerant [pdf]

martin.kleppmann.com

Post reply on HN
Print view View original

11–20 of 41 posts

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#11

Post by almog »

shanxS wrote: post #6
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…

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

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#12

Post by wyager »

somezero wrote: post #10
pdpi wrote: post #9

Earlier quoted context omitted.

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

It doesn't give you sybil-proof. It gives you sybil-resistance, and that, in a non-deterministic protocol.

It gives you sybil resistance with arbitrarily low probability of failure, so you might as well say "proof".

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#13

Post by somezero »

wyager wrote: post #12
somezero wrote: post #10

Earlier quoted context omitted.

It doesn't give you sybil-proof. It gives you sybil-resistance, and that, in a non-deterministic protocol.

It gives you sybil resistance with arbitrarily low probability of failure, so you might as well say "proof".

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

[2] Section 3.4 of http://elaineshi.com/docs/blockchain-book.pdf

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#14

Post by sbazerque »

Hyper 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

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#16

Post by amilich »

omeze wrote: post #15

This is pretty interesting! Skiff ( 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).

Yes, we use E2EE CRDTs! They don't have to be centralized because we still get composable updates using 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).

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#18

Post by adamnemecek »

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?

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#19

Post by davidrusu »

Really 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

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

Re: Making CRDTs Byzantine Fault Tolerant [pdf]

#20

Post by wyager »

somezero wrote: post #13
wyager wrote: post #12

Earlier quoted context omitted.

It gives you sybil resistance with arbitrarily low probability of failure, so you might as well say "proof".

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

I think we're on the same page - I was referring to Bitcoin's algorithm giving you arbitrarily low failure probability, not the OP's paper.
Post reply on HN