拜占庭区块链共识算法,拜占庭算法的数学起源

  

     

  

  SCRY。信息   

  

  区块链架构是一种分布式架构。其部署模式包括公有链、联盟链和私有链,分别对应于分散分布式系统、部分分散分布式系统和弱集中分布式系统。   

  

  在分布式系统中,多个主机通过异步通信形成一个网络集群。在这样的异步系统中,需要主机之间的状态复制来确保每个主机达成一致的状态共识。但是,在异步系统中,可能存在无法通信的故障主机,并且主机的性能可能下降,网络可能拥塞,这可能导致错误信息在系统中传播。因此,有必要在默认的不可靠异步网络中定义一个容错协议,以确保所有主机达成安全可靠的状态共识。   

  

  利用区块链构建基于互联网的分散账本,首先要解决的问题是如何实现不同账本节点上账本数据的一致性和正确性。因此,需要借鉴现有的分布式系统中实现状态一致的算法,确定网络中选择记账节点的机制,以及如何保证账簿数据在全网形成正确一致的一致。   

  

  20世纪80年代出现的分布式系统一致性算法是区块链一致性算法的基础。拜占庭容错(BFT)是分布式计算中的一种容错技术。拜占庭是现实世界的典范。由于硬件错误、网络拥塞或中断、恶意攻击等原因,计算机和网络可能会出现意外行为。拜占庭容错技术就是为了处理这些异常行为,满足待解决问题的规范要求而设计的。   

  

  于是,拜占庭将军的问题可以描述为:一个将军发出命令,就会向其他n-1个将军发出命令,这样:   

  

  IC1。所有接受命令的忠诚将军都服从同样的命令;   

  

  IC。如果发出命令的将军是忠诚的,那么所有收到命令的忠诚将军都服从收到的命令。   

  

  Lamport对拜占庭将军的研究表明,当n3m,即叛徒数量M小于将军总数N的1/3时,通过口头同步沟通(假设沟通是可靠的),可以构造出同时满足IC1和IC2的解,即将军们可以达成约定的顺序。然而,如果通信是可证明的和防篡改的(例如PKI认证、消息签名等)。),可以用任意数量的叛徒(至少两个忠诚的将军)找到解决办法。   

  

  然而,在不同的交流情况下,情况就不那么愉快了。   

  

  费歇尔-林奇-佩特森定理证明,只要有叛徒,拜占庭一般问题无解。翻译成分布式计算语言,在多进程异步系统中,只要有一个进程不可靠,就不存在协议,可以保证所有进程在有限的时间内达成协议。因此,拜占庭一般问题在分布式系统中是一个非常具有挑战性的问题。因为分布式系统不能依赖同步通信,否则性能和效率都会很低。因此,寻找一种实用的算法来解决拜占庭通用问题一直是分布式计算领域的重要问题。   

相关文章