[somezero]

The only way to provably prevent Sybil attacks are CAs (https://www.freehaven.net/anonbib/cache/sybil.pdf) This is why almost all P2P and DHT papers assumed existence of a CA in their system model eg. Castro’s secure routing etc.

P.S. PoS protocols are also Sybil resistance mechanisms. Look into Tendermint and compare it with, say, PBFT.

[ItsMonkk]

Not true.

> This paper shows that the situation with BFT CRDTs is very different from BFT consensus: it 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, allowing them to be deployed in open P2P systems that anybody can join, without requiring proof-of-work or proof of any other resource.

[0]: https://martin.kleppmann.com/papers/bft-crdt-papoc22.pdf

[somezero]

I’m not saying his paper is wrong or not up to the workshop quality. But he’s saying something against an easy-to-prove impossibility theorem in a seriously sloppy/hand-wavy way. I trust Doceur and the entire early 2000s literature more than his paper. But who knows, I might be wrong.

P.S. Also commented about the paper here: https://news.ycombinator.com/item?id=30561786

[ItsMonkk]

His more recent paper on the move operation[0] goes into some of the details further and while I don't fully understand it myself, the claims he makes along with the proof assistant nature he uses to work through them are fairly compelling.

The simple intuition is that because his CRDT's are associative and everyone else is not using associative data types, he simplifies the space and the impossible becomes possible.

[0]: https://news.ycombinator.com/item?id=30811072

[somezero]

Thanks! I’ll definitely take a look. These works are valuable but my problem is just with that particular claim about CAs.

1. This impossibility theorem is proved in a really broad setting (assuming a “broadcast communication cloud” and a P2P channel). If he wants to circumvent the impossibility theorem he should clearly specify the system model and say how it differs from Doceur’s. There are other instances where by playing with the model you go around an impossibility theorem, but you have to specify the differences. Especially since this theorem is so well known/cited.

2. Some claims in the old paper are just plain wrong. Like, you can’t say it’s Sybil resistant just because it tolerates arbitrary number of Byzantine nodes. Dolev-Strong also needs just one honest party, but it requires a CA.