3 ms·
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)”
by narush 5y ago
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!
- 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