- A+
写在前面:原文就是没问题的,因为B服务器会返回version 1。
查询协议:现在我们需要处理服务器的查询问题。问题是,当客户端查询服务器时,它可能会捕获未完成的更新。例如,假设到目前为止,version 2只写到{A,C}。查询{A,C,D}的客户端将从C获得包含version 2的响应。但是,如果客户端查询{B,C,D},由于C是拜占庭式的,并且它可能会隐藏version 2,则仅返回version 1。更糟糕的是,C可能会来回切换,使用version 2来响应某些客户端,而对其他客户端则保持隐藏状态。
为了解决这个问题,我们将在查询协议中使用两个阶段:第一阶段,客户端为当前version查询2f+1台服务器,第二阶段将最高的version写回给2f+1台服务器。这样,假设客户端查询 {A, C, D},并返回version 2。那它就将version 2 写回给2f+1台服务器,比如 {A, C, D},从而保证version 2的更新已经完成。
注:由于解决键-值存储一直不是我们的重点,我们掩盖了上面的某些细节。另外,作为补充说明,在n=3f+1的情况下,解决键-值存储问题不需要客户端签名,请参阅此处的示例解决方案。
有趣场景的系统生成
注意我们在设计键-值存储时所做的一些事情:
- 我们创建了一些简单的场景,每个场景都有少量的服务器和少量的交换步骤;
- 在每个交换步骤中,我们选择f台服务器来进行排除:第一个客户端从阶段1和阶段2中排除{D},第二个客户端从阶段1中排除{A},依此类推;
- 我们允许拜占庭服务器C返回到旧状态并用旧值响应;
将上述内容放入一个结构化的场景中,我们通过拜占庭式服务器创建了以下一系列的交换,分区和“内部状态遗忘”:
- Exchange 1: client-1 phase-1 with {A,B,C};
- Exchange 2: client-1 phase-2 with {A,B,C};
- Exchange 3: client-2 phase-1 with {B,C,D};
- Exchange 4 (partial): client-2 phase-2 with {A,C} (and crash);
- Exchange 5: client-3 with {B,C,D}, C has its internal state erased.
Twins系统地生成类似上面的场景,并通过拜占庭节点的孪生实例模拟遗忘等行为。重要的是,对于相当小的场景,Twins可以有效地枚举上述场景,以暴露协议漏洞。
总结
使用拜占庭容错(BFT)算法设计分布式协议并不容易。数十年来,研究人员一直在努力应对令人担忧的安全与活性(liveness)漏洞,在某些情况下,这些漏洞需要花上数十年的时间才能够被人发现。
Twins是一种新的BFT测试方法,它覆盖了很多(但并非全部)拜占庭式攻击,关于该方案的具体设计,读者可以看原论文。
Twins: White-Glove Approach for BFT Testing : https://arxiv.org/pdf/2004.10617.pdf
- 我的微信
- 这是我的微信扫一扫
- 我的电报
- 这是我的电报扫一扫