MIT6.824 Lecture18 Fork Consistency

Background

拜占庭问题（Byzantine Generals Problem）得名于一个古老的传说，讲述了拜占庭帝国在战争中的一个失败策略。在这个故事中，多名拜占庭将军要协调进攻或撤退的行动，但是其中一些将军可能会向其他帝国泄露假消息或者出现背叛等行为。这使得其他将军面临了一个难题：应该相信哪些将军的指令才是可靠的？

类比到计算机领域，拜占庭问题就是指在分布式系统中，由于存在节点失效、网络延迟等因素，导致不同节点接收到的信息可能存在不一致或者错误的情况，从而影响系统的正确运行。解决拜占庭问题是分布式系统安全性和可靠性的基础之一。

SUNDER论文就是在这样一个背景下提出的，同时也没有一个可信任的服务商来提供可靠服务，每个人都可能是一个攻击者。

问题解决思考路径

第一个，我们可以通过signature来判断哪个文件被谁修改，这个可以解决第一个问题，防止被别的操作修改。但是在这个拜占庭问题下，我们不能保证，如果发送别的问题，或者发送了一个old version。

通过signed log of operation

一般来说如果我们只记录写操作，读操作不记录，但是在这个情况下，我们不记录读log的话，可能会导致下面的情况，这样我们就读到了不一致的autho,和bank，一个old的，一个new，因为发送的是前缀。

Fork consistency

有点像raft里面的脑裂，两个世界，就像操作系统fork一样，像叉子一样。

Fork一致性是最强的完整性概念，可以在没有在线可信方的情况下实现。假设用户A在线上修改了一个文件，然后下线了。稍后，B上线并读取该文件。如果B不知道A是否访问过文件系统，则无法检测到攻击，其中服务器仅丢弃A所做的更改。Fork一致性意味着这是服务器对文件完整性或一致性的唯一类型的无法检测的攻击。此外，如果A和B有任何通信或看到彼此未来的文件系统操作，则可以检测到攻击。

有了Fork一致性，可以利用任何在线的可信方来获得更强的一致性，甚至是获取-修改一致性。例如，如第5节中后面描述的那样，SUNDR服务器由两个程序组成，一个块存储器用于处理数据，一个具有非常少量状态的一致性服务器。将一致性服务器移动到受信任的机器上可以轻松地保证获取-修改一致性。问题在于，可信赖的机器可能比不可信赖的机器连接性或可用性更差。

为了限制不一致性的时间窗口而不将可信机器放在关键路径上，可以使用“时间戳盒子”来写入单个文件的权限。这个盒子可以通过SUNDR每5秒更新该文件。看到盒子更新的所有用户都知道它们只能在过去的5秒钟内被隔离。这些盒子可以复制以实现拜占庭容错，每个副本更新一个单独的文件。

另外，可以利用直接的客户端-客户端通信来增加一致性。用户可以将当前网络地址的登录和注销记录写入文件，以便找到彼此并持续交换有关其最新操作的信息。如果恶意服务器无法破坏客户端之间的网络通信，则一旦在线客户端了解彼此，它将无法分叉文件系统状态。对于认为恶意网络分区足够严重以至于需要在面对客户端故障时暂停文件访问的人，可以在通信中断期间保守地暂停文件访问。

怎么保障fork一致性

现在，非正式地考虑一下恶意服务器可以做什么。为了说服客户端进行文件修改，服务器必须向其发送已签名的历史记录。假设服务器不知道用户的密钥并且无法伪造签名，则客户端接受的任何修改必须实际上是由授权用户签署的。但是，服务器仍然可以通过隐藏其他用户的以前操作来欺骗用户签署不适当的历史记录。例如，考虑上面历史记录的最后一个操作如果服务器未能向用户B显示对文件f2的最新修改会发生什么。用户A和B将签署以下历史记录：

任何一种历史记录都不是另一种历史记录的前缀。从此时开始，因为客户端始终检查自己用户的历史记录中的前一个操作，在攻击之前，用户享有获取-修改一致性，但在攻击之后，用户被分叉。进一步假设服务器与恶意用户勾结或以其他方式获得了已破解用户的签名密钥。如果我们限制分析仅考虑由诚实（即未被破坏）用户签名的历史记录，我们将看到类似的分叉性质。一旦两个诚实用户签署了不兼容的历史记录，他们将无法在未检测到问题的情况下看到彼此的后续操作。当然，由于服务器可以扩展并签署被破坏用户的历史记录，因此它可以更改任何被破坏用户可以编写的文件。然而，其余的文件只能在诚实用户的历史记录中进行修改，因此仍然保持分叉一致。

分叉一致性是在没有在线可信方的情况下实现最强完整性概念。假设用户A在线上修改了一个文件，然后下线了。稍后，B上线并读取该文件。如果B不知道A是否访问过文件系统，则无法检测到攻击，其中服务器仅丢弃A所做的更改。分叉一致性意味着这是服务器对文件完整性或一致性的唯一类型的无法检测的攻击。此外，如果A和B有任何通信或看到彼此未来的文件系统操作，则可以检测到攻击。

有了分叉一致性，可以利用任何在线的可信方来获得更强的一致性，甚至是获取-修改一致性。例如，如第5节中后面描述的那样，SUNDR服务器由两个程序组成，一个块存储器用于处理数据，一个具有非常少量状态的一致性服务器。将一致性服务器移动到受信任的机器上可以轻松地保证获取-修改一致性。问题在于，可信赖的机器可能比不可信赖的机器连接性或可用性更差。