区块链的共识机制

区块链的共识机制 Blockchain Consensus

区块链如何在分布式场景下达成一致,关键便是共识机制。共识协议的稳定性和防攻击性保证了区块链的安全运行。现整理常见的共识机制,包括PoW工作量证明(Proof of Work)、PoET运行时间证明(Proof of Elapsed Time)、PBFT拜占庭容错算法(Practical Byzantine Fault Tolerance),以及两种新型的共识机制:PoL幸运值证明(Proof of Luck)以及PoUW有效工作证明(Proof of Useful Work)。

工作量证明 Proof of Work

工作量证明是矿工在处理交易数据(对数据也是进行哈希)的同时不断的进行哈希计算,求得一位前23位为0的哈希值,这个值成为nonce黄金数。当全网有一位矿工哈希出nonce时,他就会把自己打包的区块公布出去,其他节点收到区块验证区块后就会一致性认为这个区块接到了区块链上,就继续进行下一个区块的打包和哈希计算。在这个过程中,中本聪通过算力的比拼牺牲了一部分最终一致性(因为会有分叉的产生)并且需要等待多个确认,但是这种简单暴力的方法却保证了整个区块链系统的合法性,而且把区块链系统的健壮性提升到极致,就算全网只剩下一个节点运行,这个区块链系统还是会继续运行下去。最后POW也充分提高了区块链系统的安全性,依靠51%攻击理论去破坏区块链系统是只有政府或者疯子才会采取的方法。

优点:

  • 完全去中心化
  • 节点自由进出,容易实现。
  • 破坏系统花费的成本巨大

缺点:

  • 对节点的性能网络环境要求高
  • 无法达成最终一致性
  • 浪费能源

详情可参见 Bitcoin: A Peer-to-Peer Electronic Cash System

消耗时间证明 Proof of Elapsed Time

为了提高分布式共识的效率,一个优良的彩票函数(lottery function)有以下几个特征:

  • 公平:该函数应在最广泛的可能参与者中进行领导选举的分布
  • 投入:控制领导选举进程的花费,应当与从中的收益成正比
  • 验证:对于所有的参与者而言,验证领导为合法选举产生的步骤应相对简单

消耗时间证明算法使用新型安全的CPU指令来实现上述目标。通过这些特点,PoET保证了领导选举过程的安全性和随机性,而不需要像大多数证明算法一样需要消耗大量资源。

详情可参见Introduction - Sawtooth latest documentation(Proof of Elapsed Time)

拜占庭容错算法 Practical Byzantine Fault Tolerance

这是一种基于消息传递的一致性算法,算法经过三个阶段达成一致性,这些阶段可能因为失败而重复进行。
假设节点总数为3f+1,f为拜占庭错误节点:

当节点发现leader作恶时,通过算法选举其他的replica为leader。
leader通过pre-prepare (第一个协议阶段)消息把它选择的 value广播给其他replica节点,其他的replica节点如果接受则发送 prepare(第二个协议阶段),如果失败则不发送。
一旦2f个节点接受prepare消息,则节点发送commit(第三个协议阶段)消息。
当2f+1个节点接受commit消息后,代表该value值被确定 如下图表示了4个节点,0为leader,同时节点3为fault节点,该节点不响应和发出任何消息。最终节点状态达到commited时,表示该轮共识成功达成。 注:预准备阶段(pre-prepare): 主节点分配一个序列号n给收到的请求,然后向所有备份节点群发预准备消息,预准备消息的格式为<<PRE-PREPARE,v,n,d>,m>,这里v是视图编号,m是客户端发送的请求消息,d是请求消息m的摘要。 准备阶段(prepare): 如果备份节点i接受了预准备消息<,m>,则进入准备阶段。在准备阶段的同时,该节点向所有副本节点发送准备消息<PREPARE,v,n,d,i>,并且将预准备消息和准备消息写入自己的消息日志。如果看预准备消息不顺眼,就什么都不做。 确认阶段(commit): 当(m,v,n,i)条件为真的时候,副本i将<COMMIT,v,n,D(m),i>向其他副本节点广播,于是就进入了确认阶段。
优点:上述其他算法都脱离不了币的存在,币的存在及它的奖励机制会让区块链这一单一的世界穷者更穷,富者更富。
共识效率高,可实现高频交易。
缺点:当系统只剩下33%的节点运行时,系统会停止运行。

幸运值证明 Proof of Luck

来自UC Berkley 的 Mitar Milutinovic等学者为了克服PoW的资源消耗、交易效率低等问题,在可信任执行环境(Trusted Execution Environments)中提出了一种新型共识算法:幸运值证明。在攻击者理性以及大多数参与者良性的情况下,使用最少量的资源与算力以实现交易验证的低延时。
幸运值证明由两个函数组成:PolRound(幸运值证明循环)以及PolMine(幸运值证明挖矿)。在每次循环的开始,参与者准备通过调用PoLRound函数,传递已知的最新区块。经过一段时间(ROUND_TIME)后,参与者调用PoLMine函数挖掘新的区块。PolMine函数会生成[0,1)区间内一个满足均匀分布的随机值,根据该随机值决定这一轮所有的区块中的胜出区块。
与PoET类似,Proof of Luck也是一种彩票函数,保证了随机性与安全性。

有效工作量证明 Proof of Useful Work

面对工作量证明造成的大量浪费,Cornell的Fan Zhang等学者希望可以更充分地利用CPU资源,因此在改进PoET算法的基础上提出了有效工作量证明算法,并根据有效工作量证明设计了名为REM(资源节约型挖矿)的系统。REM系统中有三类实体:区块链代理,一个或多个REM矿工,以及一个或多个有效工作客户。有效工作客户将需要计算的工作以PoUW任务的形式提供给REM矿工,矿工接受区块模板及PoUW工作后便执行有效工作指令,可以执行科学实验、药学研究等。
与PoW的完全去中心化不同的是,PoUW实现的是部分中心化(partially decentralized)。它依赖于Intel的SGX(Software Guard Extension)平台。SGX允许在隔离、免受干扰的环境中执行可信任代码,并且通过远程证明输出代表着执行结果。当然,这一切是基于SGX可信的基础。

Reference:

  1. 区块链共识机制浅谈
  2. Bitcoin: A Peer-to-Peer Electronic Cash System
  3. Introduction - Sawtooth latest documentation
  4. Proof of Luck: an Efficient Blockchain Consensus Protocol
  5. REM: Resource-Efficient Mining for Blockchains