网络与分布式2022martin.kleppmann.com编辑精选
使 CRDT 能够容忍拜占庭故障
Making CRDTs Byzantine Fault Tolerant
进阶 · 约 90 分钟读完前置知识：CRDT 基础、分布式共识、拜占庭容错
导读
Martin Kleppmann 等人的论文研究如何让 CRDT（无冲突复制数据类型）抵御拜占庭故障节点，即部分参与者恶意篡改数据时仍能保证一致性。核心做法包括用 BRB（拜占庭可靠广播）保护基于版本向量的 CRDT，以及提出嵌入 DAG 的 CRDT 结构，可容忍任意数量的拜占庭节点（对 Sybil 攻击免疫）。
HN 关注点：CRDT 与 BFT 分别是分布式系统两个热门方向，将二者结合触及共识不可能性结果的边界，且作者 Kleppmann 因《DDIA》在 HN 读者中声望很高。
HN 评论精选
这几条评论里：支持 1 质疑 1 亲历 1
亲历亲历者印证论文思路，并指出哈希图 CRDT 可避免 BRB 开销
很高兴看到 BFT 开始在 CRDT 研究中被认真对待。我去年在这个领域做过研究，得到了很多相同的解决方案（比如对基于 VClock 的 CRDT 使用 BRB 保护）。我们最终完全放弃了 VClock CRDT，改用 grow-only 哈希图 CRDT，因为它们不需要 BRB 开销——Martin 的研究也发现了这一点。
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).
质疑指出思路早有先例，并质疑其验证方案的实际可用性，同时分享生产环境经验
DAG 嵌入 CRDT 的想法并不新鲜，我们在这里提出过（arxiv 2004.00107）。不幸的是，作者提出的验证方式（在下层 DAG 验证完成前不接受新更新）要在真实世界使用还需要很多限定条件。目前我们在 ipfs-cluster 部署中将这类 CRDT 用于一个 4000 多万键的键值数据库（go-ds-crdt）。
hecturchi查看英文原文
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 .
支持对'容忍任意数量拜占庭节点'的结论表示惊讶和好奇
哇，这篇论文看起来太棒了，而且令人惊讶！'所提方案可容忍任意数量的拜占庭节点（对 Sybil 攻击免疫）'——这非常引人注目，因为共识算法中关于能容忍多少故障节点有很强的不可能性结果。期待读完整篇而不只是摘要（坦白）。Martin，感谢你所有出色的工作！
narush查看英文原文
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!
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2022Hacker News 讨论帖266 分 · 40 评
同领域还值得读
Paxos vs. Raft：分布式共识是否已达成共识？
Paxos vs. Raft: Have we reached consensus on distributed consensus?
重新审视了 Paxos 与 Raft 两种分布式共识算法之间的差异，试图在一个统一的框架下比较它们，并论证二者的相似程度远高于通常的认知，许多所谓的差别只是表述层面的。
网络与分布式2020 · 343 分 · 65 评 · 引用 10进阶 · 约 28 分钟编辑精选Stellar 协议：互联网级共识的联邦模型
Stellar Protocol: A Federated Model for Internet-Level Consensus (2016)
提出 Stellar Consensus Protocol（SCP），一种面向互联网级共识的联邦拜占庭协议模型。
网络与分布式2018 · 301 分 · 61 评专业 · 约 90 分钟编辑精选拜占庭将军问题（1982）
The Byzantine Generals Problem (1982)
这篇 1982 年论文提出并形式化了拜占庭将军问题：在分布式系统中，部分节点可能叛变或故障、通信不可完全信任时，忠诚节点如何达成一致行动。
网络与分布式2018 · 290 分 · 77 评进阶 · 约 75 分钟编辑精选Google 变差了吗？对搜索引擎中 SEO 垃圾的纵向调查
Is Google Getting Worse? A Longitudinal Investigation of SEO Spam in Search
对搜索引擎结果中的 SEO 垃圾内容做了纵向追踪：作者团队在一段时间内持续采集 Google、Bing、DuckDuckGo 等引擎针对商品评测类查询的结果，用分类器识别联盟营销…
网络与分布式2024 · 276 分 · 274 评入门 · 约 45 分钟编辑精选Filecoin：去中心化存储网络
Filecoin: A Decentralized Storage Network
Filecoin 白皮书介绍了一个去中心化存储网络：用户付费让矿工存储数据，矿工通过复制证明和时空证明来证明自己确实持续存储了数据，并以此获得代币奖励。
网络与分布式2017 · 196 分 · 162 评入门 · 约 45 分钟编辑精选