区块链解决了在不可信信道上传输可信信息、价值转移的问题,而共识机制解决了区块链如何在分布式场景下达成一致性的问题,奠定了比特币系统的安全性。
1.分布式一致性问题(共识算法)
1. 一致性问题(Consensus Problem)
一致(Agreement) :每个正确的执行过程应该在相同的值上达成一致;
完整(Integrity) :每个正确的执行过程最多只能决定一个值。如果它决定了某个值的话,这个值一定是被某个执行过程提出的;
终止(Termination) :所有的执行过程最终会做出一个决定;
正确(Validity) :如果所有正确的执行过程提出了相同的值V,那么所有正确的执行过程都会决定值V。
2. FLP不可能性(FLP impossibility)
实际的计算机集群中,可能会存在以下问题:
1.节点处理事务的能力不同,网络节点数据的吞吐量有差异
2.节点间通讯的信道可能不安全
3.可能会有作恶节点出现
4.当异步处理能力达到高度一致时,系统的可扩展性就会变差(容不下新节点的加入)。
FLP不可能性定理证明了在分布式情景下,无论任何算法,即使是只有一个进程挂掉,对于其他非失败进程,都存在着无法达成一致的可能。在假设网络可靠、计算节点只会因崩溃而失效的最小化异步模型系统中,仍然不存在一个可以解决一致性问题的确定性算法。
FLP是Fischer, Lynch,Patterson三位作者名字组合的简写,表明这定理是由它们三位发明的。
证明
更多参考
3. CAP定理
分布式计算系统不可能同时确保一致性、可用性和分区容忍性。
一致性(Consistency) :所有节点在同一时刻能够看到同样的数据,也即“强一致性”;
可用性(Availability) :确保每个请求都可以收到确定其是否成功的响应;
分区容忍性(Partition tolerance) :因为网络故障导致的系统分区不影响系统正常运行。
这也就意味着,我们虽然不能使某个分布式场景同时满足三个性质,但可以使之同时满足三个中的两个。更进一步说,对于包含多个分布式场景的分布式系统,我们甚至可以在三个性质的程度上进行适当的权衡^footnote。
more...