分布式系统与计算机网络 漫谈分布式系统(6)

具体来说，根据Paxos的论文所说，Paxos的设计是基于异步(asynchronous)、非拜占庭(non-Byzantine)的系统模型，即：节点可以以任意速度运行，可能宕机、重启。但是，算法执行过程中需要记录的一些变量，在重启后应该能够恢复。消息可以延迟任意长时间，可以重复(duplicated)，可以丢失(lost)，但不能损坏(corrupted)。

上面第一条其实是要求数据在中持久化，并且要保证在落盘过程中没有发生拜占庭错误（我们前面刚提到过）。但实际中由于突然断电、磁盘缓存等现实问题，拜占庭错误是有可能发生的（虽然概率很低），所以这就要求工程上做一些特殊处理。

上面第二条，消息损坏，属于拜占庭错误。所以Paxos要求不能有消息损坏发生。这在使用TCP协议进行消息传输的情况下，可以认为是能够满足要求的。

综上分析，解决「拜占庭将军问题」的算法，提供了最强的容错性，即BFT，而Paxos只能容忍非拜占庭错误。但是，在只有非拜占庭错误出现的前提下，Paxos基于异步模型，是比同步模型更弱的系统假设，因此算法更鲁棒。当然，Paxos也更高效。

区块链

在现实中，真正需要达到BFT容错性的系统很少，除非是一些容错性要求非常高的系统，比如波音飞机上的控制系统，或者SpaceX Dragon太空船这类系统（参见…）。

我们平常能接触到的BFT的一个典型的例子，就是区块链了。一个区块链网络是一个完全开放的网络，其中的矿工节点(miner)是可以自由加入和自由退出的。这些节点当然有可能是恶意的，所以区块链网络在设计的时候必须要考虑这个问题。这实际上就是典型的「拜占庭将军问题」。

接下来为了将区块链与「拜占庭将军问题」之间的联系讨论得更加清楚，我们先来非常粗略地介绍一下区块链技术。

以比特币网络为例，它的核心操作就是进行比特币交易，即某个比特币的拥有者将自己一定数量的比特币转移给其他人。首先，比特币的拥有者要发起交易(transaction)，他需要先用自己的私钥对交易进行签名，然后将交易请求发给矿工节点。矿工将收到的所有交易打包到一个区块(block)当中，并通过一系列复杂度很高的运算找到一个nonce值，保证对于它和区块内其它信息进行hash计算后的结果能够符合预定的要求。这一步对于整个区块链网络至关重要，被称为工作量证明(Proof of Work)。然后矿工把该区块在全网发布，由其它矿工来验证这个区块。这个验证既包括对交易签名进行验证（使用比特币拥有者的公钥），也包括对工作量证明的有效性进行验证。如果验证通过，就把这个区块挂在当前最长的区块链上。

如果两个矿工几乎同时完成了区块的打包和工作量证明，它们可能都会将区块进行发布，这时区块链就会分叉(fork)。但矿工会不停地产生新区块，并将新区块挂在当前最长的区块链上，所以最终哪个分叉变得更长，哪个分叉就会被多数矿工节点承认。这么看来，区块链其实不是一个链，而是一棵树。我们知道，在树这种数据结构中，从根节点到叶子节点只有唯一的一条路径。因此，当前有效的区块链其实是这棵树中从根节点到叶子节点最长的那条路径。只要一个区块在最长的链上，那么它就是有效的，它里面包含的所有交易就被固化下来了（被多数节点承认）。

我们只是非常粗略地介绍了一下区块链的工作原理。如果想了解细节，建议研究一下以太坊的官方wiki，地址是：github.com/ethereum/wi…

下面我们开始讨论区块链技术与「拜占庭将军问题」的关联。

前面我们讨论「拜占庭将军问题」的时候，得到过以下结论：如果使用口头消息，那么至少需要多于2/3的将军是忠诚的。如果使用签名消息，那么对忠诚将军的数量是没有要求的。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-65268-6.html