09月19, 2018

NEO dBFT共识机制分析与完善

Zhiniang Peng from Qihoo 360 Core Security

在NEO采用dBFT机制实现共识节点之间的“拜占庭容错”,并在NEO白皮书中描述恶意共识节点小于1/3的时候,该共识机制能够保证系统的安全性和可用性。我们经过研究发现,目前NEO的dBFT机制仅能保证诚实的共识节点之间达成共识。但共识节点之间不存在分叉,并不意味着全网不会存在分叉。NEO目前对dBFT共识机制的实现还不满足 f = \left \lfloor (n-1) / 3) \right \rfloor 的拜占庭容错性质。

NEO dBFT共识机制简介

NEO区块链是一个分布式的智能合约平台。NEO实现了一种委托的拜占庭容错共识算法,它借鉴了一些 PoS 的特点(NEO持有人需要对共识节点进行投票) 利用最小的资源来保障网络免受拜占庭故障的影响,同时也弥补了 PoS 的一些问题。dBFT对由n个共识节点组成的共识系统,提供 f = \left \lfloor (n-1) / 3) \right \rfloor 的容错能力,这种容错能力同时包含安全性和可用性,并适用于任何网络环境。

NEO dBFT共识机制可以详细见NEO官方共识机制白皮书:

拜占庭将军问题和区块链

拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔,为了防御目的,因此每个军队都分隔很远,将军与将军之间只能靠信差传消息。 在战争的时候,拜占庭军队内所有将军和副官必需达成一致的共识,决定是否有赢的机会才去攻打敌人的阵营。但是,在军队内有可能存有叛徒和敌军的间谍,左右将军们的决定又扰乱整体军队的秩序。在进行共识时,结果并不代表大多数人的意见。这时候,在已知有成员谋反的情况下,其余忠诚的将军在不受叛徒的影响下如何达成一致的协议,拜占庭问题就此形成。PBFT算法,是解决拜占庭将军问题的一个经典算法。

区块链是一种去中心化的分布式账本系统,它可以用于登记和发行数字化资产、产权凭证、积分等,并以点对点的方式进行转账、支付和交易。区块链技术最早是由中本聪在一个密码学的邮件列表中提出的,也就是比特币。此后,基于区块链技术的各种应用纷纷出现,比如基于区块链的电子现金系统、基于区块链的股权交易系统、基于区块链的智能合约系统等。区块链系统与传统的中心化账本系统相比,具有完全公开、不可篡改、防止多重支付等优点,并且不依赖于任何的可信第三方。然而,和任何分布式系统一样,区块链系统会面临网络延迟、传输错误、软件错误、安全漏洞、黑客入侵等问题。此外,去中心化的特点决定了此系统的任何一个参与者都不能被信任,可能会出现恶意节点,以及因各方利益不一致导致的数据分歧等问题。为了防范这些潜在的错误,区块链系统需要一个高效的共识机制来确保每一个节点都有一个唯一公认的全局账本。传统的针对某些特定问题的容错方法,并不能完全解决分布式系统以及区块链系统的容错问题,人们需要一种能够容忍任何种类错误的容错方案。

NEO区块链共识机制细节

采用了拜占庭容错委托(dBFT)作为共识机制( http://docs.neo.org/en-us/basic/consensus/consensus.html )。全网中的NEO节点分为两类节点:一类为共识记点,负责和其他共识记点之间进行共识通讯,产生新的区块;另外一类为普通节点,不参与共识,但能够验证和接受新的区块。共识节点由全网用户通过投票产生。NEO节点提出dBFT的背后思想是:PBFT算法能够很好的解决分布式节点的共识问题,但是PBFT共识参与节点数量越大性能就会越低。采用投票选取出相对较小数量的共识节点内部进行PBFT共识生成新区块,然后将该新区块发布到全网中达成全网共识。NEO共识节点之间,产生新区块的正常共识流程如下:

  1. 开启共识的节点分为两大类,非记账人和记账人节点,非记账人的不参与共识,记账人参与共识流程
  2. 选择议长,Neo议长产生机制是根据当前块高度和记账人数量做MOD运算得到,议长实际上按顺序当选
  3. 节点初始化,议长为primary节点,议员为backup节点。
  4. 满足出块条件后议长发送PrepareRequest
  5. 议员收到请求后,验证通过签名发送PrepareResponse
  6. 记账节点接收到PrepareResponse后,节点保存对方的签名信息,检查如果超过三分之二则发送 block
  7. 节点接收到block,PersistCompleted事件触发后整体重新初始化,

为了防止恶意的共识节点或议长,保证系统的安全性和可靠性,NEO提出changeview机制进一步增强dBFT的安全性。当节点 i 在经过 2^{v+1} \cdot t 的时间间隔后仍未达成共识,或接收到包含非法交易的提案后,开始进入视图更换流程:

  1. k = 1 , v_{k} = v + k
  2. 节点 i 发出视图更换请求 \left \langle ChangeView, h, v, i, v_{k} \right \rangle
  3. 任意节点收到至少 n - f 个来自不同 i 的相同 v_{k} 后,视图更换达成,令 v = v_{k} 并开始共识;
  4. 如果在经过