区块链的共识算法

(Updated: )
区块链 › 共识算法
共识算法, 区块链

区块链的共识算法

创建时间：2020年2月18日

更新时间：2020年2月26日

作者：ShizhiDeng

更新内容：

  • 2020-02-25 

    1
    重新生成每个算法的总结图，重新整理文章，并发布

  • 2020-02-26

    1
    2
    3
    1. 投票直接形成共识的BFT类
    2. 选举代理人间接参与共识的代理类
    3. DAG类共识
    • 2020-02-27
    1
    2
    3
    4
    5
      1. 我的思考更新
      2. 增加共识算法的分类方法2 更新hyperledger部分
      3. Consensus in Hyperledger Fabric(Kafka in Fabric v1)
    4. Consensus in Hyperledger Indy (based on RBFT)
      5. Consensus in Hyperledger Iroha(Sumeragi:based on BFT)

我的思考（持续更）

  • Why consensus?
    The goal of consensus is to generate an agreement on the order and to validate the correctness of the set of transactions that constitute the block.
    • agreement of transaction
    • validation of transaction
  • Core function of consensus
    • Confirms the correctness of all transactions in a proposed block.
    • Agrees on order and correctness and hence on results of execution (implies agreement on global state).
    • Interfaces and depends on smart-contract layer to verify correctness of an ordered set of transactions in a block.

  • Consensus Properties[^ 2 ]

    • Safety: each node is guaranteed the same sequence of inputs and results in the same output on each node. (同一个输入，得到同一个输出)
    • Liveness: each non-faulty node will eventually receive every submitted transaction, assuming that communication does not fail.

  • 节点有相应的概率被选为某个区块的生产者(取得记账权)，在符合一定规则的前提下，由该节点决定区块的内容，再经其 他节点验证。生产合法区块的节点通常可以获得一定的激励。

  • 共识算法：解决一致性问题

区块链的共识算法总结_我的思考

共识算法的分类方法1

根据容错，节点参与共识过程的资格，形成共识的依据和共识的内容可以分成四类^ 1 :

  • Proof of X类
  • 投票直接形成共识的BFT类
  • 选举代理人间接参与共识的代理类
  • 舍弃传统区块概念的DAG类共识

整体分类图见下：

区块链的共识算法总结-分成四类

共识机制的分类标准见下：

区块链的共识算法总结-分类标准

4类共识机制简析

  1. Proof of X类共识机制
    节点获得记账权的概率与该节点拥有某种资源的比例相关，并且这种资源是难以垄断的，同时需要一个能够快速验证某个节点确实拥有这部分资源的算法。
    该类共识算法有PoW、PoS、PoA/PoSV/Casper、PoST/Proof of Authority：

区块链的共识算法总结-PoX类

针对PoX类共识机制，分别对上述几种算法总结如下：

  • PoW

    区块链的共识算法总结-PoW

    • PoS
      区块链的共识算法总结-PoS

    • PoA
      区块链的共识算法总结-PoA

    • PoA
      区块链的共识算法总结-PoA

    • Casper
      区块链的共识算法总结-Casper

    • Ouroboros
      区块链的共识算法总结-Ouroboros

    • PoSV
      区块链的共识算法总结-PoSV

    • 其他PoX
      区块链的共识算法总结-otherPoX

  1. 投票直接形成共识的BFT类

    该类共识算法有pBFT、dBFT和FBA：
    区块链的共识算法总结-BFT类共识机制

    • pBFT

      区块链的共识算法总结-pBFT

      • 1999年提出，首个高效解决拜占庭容错问题的算法

      • Hyperledger Fabric曾采用过此共识算法

      • 解决的问题：分布式系统的一致性问题，拜占庭容错问题。

      • 采用的方法：引入“视图”(View)和“主从节点”(Replica)的概念。 Replica 包括主节点(Primary)以及备份节点(Backups)，主节点通常在每一轮共识过程开始时随机选取或者轮流担任。“视图”表示一次主节点分发请求的过程。

        当一轮共识开始时，首先检查主节点的有效性。如果备份节点检测到主节点失效，需要选举出新的主节点，称为“视图更换”。共识过程分为包括预准备、准备、确认阶段，又称“三阶段协议”。

        截屏2020-02-26下午4.41.24

      • 容错能力：pBFT 算法对于一个 n=3f+1 个节点组成的区块链网络，可以提供 f 的容错能力，容错能力近似为 1/3。

      • pBFT的限制：由于一轮共识过程中节点间的通信次数与𝑛^2^（n为节点数）成正比，考虑到通信延迟的存在，当节点的数量达到一定规模后，pBFT 的效率会严重下降。

    • FBA（Federated Byzantine Agreement 基于联邦拜占庭协议的共识机制）
      区块链的共识算法总结-FBA

      • 思想：通过一种在子网络内部形成信 任(即联邦)，将子网络作为整体视为网络的节点的协议。
      • 基于FBA的共识机制：基于 FBA 的共识机制有RPCA(瑞波共识机制)、恒星共识机制等。
      • 方法：
        • RPCA(瑞波共识机制)：节点分验证节点（信任节点列表：UNL Unique Node list）+非验证节点；共识过程分两个阶段：阶段1. 形成交易集的共识（对每一个交易在 UNL 中投票表决，最终得到 80% 投票的交易会被放入交易集中） 阶段2. 形成新区块的共识（广播区块的hash值，比例最高的 Hash值占比超过80%，则达成共识）
        • 恒星共识机制：与 RPCA 类似，恒星共识机制的特点是通过节点可以自由地选择要加入的“联邦”，无需中心化的组织预先选出“服务节点”。
      • 容错能力：RPCA(瑞波共识机制)为1/5。

  2. 选举代理人间接参与共识的代理类

    • BFT类共识机制的限制：参与共识的节点数量有限制，或者参与共识的部分节点必须是可信任的。

    • 目标：一些公共区块链希望尽可能多的节点参与到共识过程中去。

    • 代理共识机制的思想：借鉴现实社会中的选举，网络定期按照节点的得票数选出一定数量的“共识节点”，仅由共识节点完成区块链网络的共识过程。

    • 限制

      • 由于见证人的数量有限并且公开，攻击者想要发动DDoS攻击较为容易，见证人需要额外的保护措施，增加了运行共识节点的成本。
      • 具有投票权的节点通常有更大的话语权，甚至可以操纵投票结果。
        • 如果限制节点的最高投票权重，也可以通过转移通证到不同的节点来规避。
        • 如果实行“一节点一票”的机制，又会导致“女巫攻击”变得可行。
        • 寻找一个平衡安全性与非中心化的投票算法是较为困难的。

    • 该类共识算法有DPoS和DPoS-BFT：
      区块链的共识算法总结-代理类共识机制

    • DPoS

      区块链的共识算法总结-DPoS

      • 方法：
        • 选举见证人：选票前 101 名的节点获得参与网络共识过程的资格，被称为“见证人”。
        • 每个见证人按照一定的顺序(比如随机)轮流获得生产区块的机会，再根据一定的规则对区块链达成共识。
        • 共识方法：根据类似 PoW 的最长链原则选择在高度最高的区块后添加自己的区块。
        • 注意1：各见证人的记账权利是相同的，不因获票数的多少产生区别。
        • 注意2：见证人未能履行义 务或作出不符合整体利益的行为，见证人会被取消记账权。

    • DPoS-BFT

      区块链的共识算法总结-DPoS_BFT

      • 思想：见证人根据获得获得权益支持的多少选出，见证人形成共识的算法可以是 BFT 或其他算法。
      • 方法：
        • EOS 使用的 DPoS-BFT 共识机制方法：
          • 股权投票选举出见证人(EOS 称为 BP，Block Producer)的基础上
          • 使用 BFT 类算法在 BP 之间形成共识。
          • 见证人 21 名，在BFT的三阶段协议中，区块得到15个BP的确认就可最终确认。
        • NEO 的方法：主要是对见证人形成共识的BFT类算法进行改进
          • NEO 网络中有两种通证，管理通证 NEO 以及燃料通证 GAS。
          • 节点根据持有管理通证的份额获得相应数量的选票，选举出一定数量的见证人(共识节点)
          • 由见证人通过改进的pBFT 算法形成共识，生产区块
          • 区块中会有奖励的燃料通证，按持有 NEO 的比例分配给各节点。

  3. DAG类共识

    该类共识算法有如下特点：
    区块链的共识算法总结-DAG类共识机制

    • 思想：一般节点维护的交易历史是一个区块组成的哈希链表，特点是单向、线性。修改这种数据结构为IOTA 就是采用有向无环图 DAG (Directed Acyclic Graph)作为记录交易历史的数据结构。
    • 特点和优势：
      • Tangle 共识不需要专门负责记账的矿工，而是由新交易给历史交易提供验证，因此不需要交易费用。
      • 不需要将交易打包成区块，交易得到确认的速度取决于新交易 加入Tangle的速度。
    • 缺点
      • 对交易缺乏过滤机制，因此容易遭到大量垃圾交易的攻击，并且没有有效的机制过滤作恶的节点

共识机制对比

截屏2020-02-26下午6.36.41

共识算法的分类方法2[^ 2 ]

  • lottery-based algorithms
    • advantages: scale to a large number of nodes since the winner of the lottery proposes a block and transmits it to the rest
      of the network for validation.
    • disadvantages: lead to forking when two “winners” propose a block. fork must be resolved, which results in a longer time to finality.
  • voting-based algorithms
    • advantages: low-latency finality
    • disadvantages: the more nodes that exist on the network, the more time it takes to reach consensus. This results in a trade-off between scalability and speed.

Consensus in Hyperledger Fabric(Kafka in Fabric v1)[^ 2 ][^ 3 ][^ 4 ]

  • Consensus in Hyperledger Fabric is broken out into 3 phases:
    1. Endorsement: Endorsement is driven by policy (eg m out of n signatures) upon which participants endorse a transaction.
    2. Ordering: Ordering phase accepts the endorsed transactions and agrees to the order to be committed to the ledger.
    3. Validation: Validation takes a block of ordered transactions and validates the correctness of the results, including checking endorsement policy and double-spending.
  • ILLUSTRATION OF ONE POSSIBLE TRANSACTION FLOW(COMMON-CASE PATH) IN HYPERLEDGER FABRIC
    截屏2020-02-27下午4.56.35
  • 可插拔的共识服务：pluggable consensus service
    • the ordering service API allows plugging in BFT-based agreement algorithms
  • The ordering service API consists of two basic operations: broadcast and deliver.
    • broadcast(blob)
    • deliver(seqno, prevhash, blob)
  • Multiple ordering plugins are being developed currently, including BFT Smart, Simplified Byzantine Fault Tolerance (SBFT), Honey Badger of BFT, etc.
  • Fabric v1, Apache Kafka is provided out-of-the-box as a reference implementation.

Consensus in Hyperledger Indy (based on RBFT)

  • Consensus in Hyperledger Indy is based on Redundant Byzantine Fault Tolerance (RBFT)
  • Like PBFT, RBFT needs at least 3f+1 nodes to handle f faulty nodes.
  • RBFT overview:
    截屏2020-02-27下午5.23.15
  • RBFT protocol steps:
    截屏2020-02-27下午5.24.33

Consensus in Hyperledger Iroha(Sumeragi:based on BFT)

  • Insipered by B-Chain Algorithm described by Duan, Meling, Peisert, & Zhang (2014).
  • Concept of a global order over validating peers and sets A and B of peers, where A consists of the first 2f+1 peers and B consists of the remainder.
    截屏2020-02-27下午5.30.17
  • The order of processing nodes is determined based on the server reputation system called hijiri.
  • The case of a failure in the proxy tail is shown in Figure below
    截屏2020-02-27下午5.35.24
  • Consensus in Sumeragi is performed on individual transactions and on the global state resulting from the application of the transaction. When a validating peer receives a transaction over the network, it performs the following steps in order:
    1. Validate the signature (or signatures, in the case of multi-signature transactions) of the transaction.
    2. Validate the contents of the transaction, where applicable. For example, transfer transactions must leave the payer’s account with a non-negative balance.
    3. Temporarily apply the transaction to the ledger. This involves updating the Merkle root of the global state.
    4. Sign the updated Merkle root and the hash of the transaction contents.
    5. Broadcast the tuple, which is a finite ordered list of transactions.
    6. When syncing nodes with each other, valid parts of the Merkle tree are shared until the roots match.

Consensus in Hyperledger Sawtooth(based on PoET)

  • PoET: Proof of Elapsed Time
  • Hyperledger Sawtooth facilitates pluggable consensus for both lottery and voting algorithms.
  • Default algorithm: lottery-based, Nakamoto consensus algorithm called PoET.
  • PoET uses a lottery for leader election based on a guaranteed wait time provided through a Trusted Execution Environment (TEE) (Sandell, Bowman, & Shah, 2016). The current implementation of Hyperledger Sawtooth builds on a TEE provided by Intel’s Software Guard Extensions (SGX).
  • A good lottery function satisfies:
    • Fairness - The function should distribute leader election across the broadest possible population of participants.
    • Investment - The cost of controlling the leader election process should be proportional to the value gained from it.
    • Verification - It should be relatively simple for all participants to verify that the leader was legitimately selected.

Paxos

[^ 2 ]: Hyperledger Architecture, Volume 1 Introduction to Hyperledger Business Blockchain Design Philosophy and Consensus

[^ 3 ]: Fabric Transaction Flow

[^ 4 ]: The Ultimate Guide to Consensus in Hyperledger Fabric