DPOS BFT— Pipelined Byzantine Fault Tolerance 委托权益证明 - 管道式的拜占庭容错

in #eos6 years ago

https://medium.com/eosio/dpos-bft-pipelined-byzantine-fault-tolerance-8a0634a270ba
DPOS BFT— Pipelined Byzantine Fault Tolerance
委托权益证明 - 管道式的拜占庭容错

Author/原作者: Dan Larimer https://steemit.com/@dan
Translater/翻译: https://steemit.com/@guesshu

There are two general blockchain consensus systems: those that produce unambiguous 100% finality given a defined set of validators and those which do not provide 100% finality but instead rely on high probability of finality.
大体上有两类区块链公示系统:一类利用限定的验证者来产生100%的定局;另一类依赖高可能性而不能产生100%的定局;

The first generation blockchain consensus algorithms (Proof of Work, Proof of Stake, and BitShares’ Delegated Proof of Stake) only offer high probability of finality that grows with time. In theory someone could pay enough money to mine an alternative “longer” Bitcoin blockchain that goes all the way back to genesis.
第一代的区块链共识算法(工作证明,权益证明和比特股的委托权益证明)只提供了随时间增长的高可能性的定局。理论上,有人可以付出足够的代价来挖出另一条“更长”的一路追溯到创世块的比特币区块链。

More recent consensus algorithms, whether HashGraph, Casper, Tendermint, or DPOS BFT all adopt long-established principles of Paxos and related consensus algorithms. Under these models it is possible to reach unambiguous finality under all network conditions so long as more than ⅔ of participants are honest
近期出现的共识算法,无论HashGraph, Casper, Tendermint或者DPOS BFT也好,都采用了长期受到认可的Paxos和相关的共识算法。只要超过2/3的参与者是诚实的,这些模型们在任何网络条件下都可能达成不模棱两可的定局。

Objective and unambiguous 100% finality is a critical property for all blockchains that wish to support inter-blockchain communication. Absent 100% finality, a reversion on one chain could have irreconcilable ripple effects across all interconnected chains.
客观和不模棱两可的定局是所有想要实现跨链沟通的区块链的关键性质之一。倘若没有100%的确定性,一条链上的(交易)逆转会引发所有相互连接的链之间的不能协调的涟漪效应。

The abstract protocol for these more recent protocols involves:

  • Propose block
  • All participants acknowledge block (pre-commitment)
  • All participants acknowledge when ⅔+ have sent them pre-commitments (commitment)
  • A block is final once a node has received ⅔+ commitments
  • Unanimous agreement on finality is guaranteed unless ⅓+ are bad and evidence of bad behavior is available to all
    最近出现的这些协议的梗概:
  1. 提议一个区块
  2. 所有参与者公认收到这个区块(预承诺)
  3. 当收到2/3+的参与者发送的预承诺时,所有参与者公认(承诺)
  4. 当一个节点收到2/3+的承诺时,一个区块就被认为是确定了的
  5. 除非1/3+的参与者是不诚实并且不诚实举动的证明对所有人可见,否则一定可以一致同意达成定局


What makes the various consensus protocols different are:

  • Deciding when and who gets to propose a block
  • Deciding how commitments are logged & communicated
  • How byzantine behavior is documented
  • Punishment for byzantine behavior
    这些共识协议的不同之处在于:
  1. 决定何时以及谁可以提议一个区块
  2. 决定承诺时如何被记录和沟通的
  3. 如何记载拜占庭行为
  4. 拜占庭行为的惩罚

Some of these differences are political and some of them are technical in nature. Examples of political differences include:

  • DPOS elects the set of proposers & validators based upon stake
  • Casper relies on proof-of-work to determine when and who and when gets to propose and bonded-stake-weight to determine who the validators are
  • DPOS punishes objective and subjective bad behavior by voting people out
  • Casper only punishes objective bad behavior by slashing bonds
    这些不同点有的是政治上的不同,有的是技术层面的不同。政治不同点的例子包括:
  1. DPOS基于权益选拔提议者和验证者
  2. Casper靠工作证明去决定谁什么时候可以提议和绑定权益重量来决定谁是验证者【翻译也不懂这是什么意思】
  3. DPOS靠投票出局来客观或主观的惩罚恶意行为
  4. Casper只靠削减债务来客观的惩罚恶意行为

Under normal conditions, the political differences make no day-to-day impact on the experience of users relying on the consensus mechanism to order and finalize transactions. The threshold for malicious behavior is so high and the penalties so great that for all practical purposes it doesn’t happen.
通常情况下,政治上的区别对日常的依靠共识机制去排序和最终确定交易的用户体验不造成影响。恶意行为的阈值如此之高,对其的惩罚如此之多,以至于实际上不会发生。

It is the technical differences in the protocols that give rise to real-world impact on user experience. This includes things such as latency until finality, degrees of finality, bandwidth, and proof generation / validation overhead.
这些协议的技术层面的区别反而对用户体验有实际的影响。这其中包括定局的延迟性,定局的程度,带宽,产生/验证证明的经常开销。

The simplest possible algorithm has everyone reach consensus on one block before any progress can be made on the next block. This involves every participant sending every other participant two messages per block. In a global network the speed of light limits the practical latency from time of proposal to the time a node receives ⅔+ commit messages to about one second (500ms round trip latency * 2 round-trips). All networks I have observed seem to be in the 2–3 second latency camp. These simple protocols also have a “timer” which introduces a new proposal if no consensus can be reached over the validity of the current proposal. This timer is generally longer than the expected confirmation time.
用可能最简单的算法,每个人需要对一个区块达成共识,才能进行下一个区块。这牵涉到针对每一个区块,每个参与者向每个其他参与者发送两条信息。在一个全球网络上,光的速度限制了由提议到一个区块收到2/3+承诺信息的实际延迟时间为大概1秒(500微秒往返程延迟*2次往返程)。我观察到的所有网络似乎都是有2-3秒的延迟。这些简单的协议也会有一个“计时器”,当现在这个提议在限定时间内达不成共识的时候就会提出一个新的提议。这个时间限定通常会长过确认时间的期望值。

Protocols like Casper attempt to minimize the overhead by relying on proof-of-work for short-term consensus and only reaching finality over every 100th block (checkpoint). This means Casper-based chains reach finality every 20 to 30 minutes.
像Casper这样的协议尝试靠工作量证明达成短期共识来减少经常开销,且只能每100个区块(检查节点)达成定局。这意味着基于Casper的链每20-30分钟才能达成定局。

DPOS BFT Pipeline Consensus
委托权益证明拜占庭容错管道式共识

Modern Delegated Proof of Stake with BFT as implemented in EOSIO uses a pipelined approach to deliver the proposal, pre-commitment, and commitment messages. This means under normal operating conditions, every block advances the finality of one block and this is achieved by only requiring one proposal per time slot. In other words, the cost of DPOS with BFT finality in terms of signature verifications, hash calculations, network bandwidth, etc., is equal to the cost of older DPOS systems that relied upon eventual consistency and the longest chain rule similar to Bitcoin and Ethereum (pre Casper).
摩登的带有拜占庭容错的委托权益证明(如EOSIO的实施)采用管道式的办法去传递提议,预承诺和承诺信息。这意味着在一般的操作条件下,每个区块使一个区块的定局加速,而这是靠每个时间槽只要求一个提议来实现。换句话说,拜占庭容错的委托权益证明的定局成本(包括签名验证,哈希值计算,网络带宽等等),等于旧式的委托权益证明的成本,这些旧式的委托权益证明依靠结果一致性和最长链规则, 类似于比特币和Casper落地之前的以太网。

Only DPOS BFT can efficiently scale to an unlimited number of validators (at cost to latency). Other protocols grow the resource requirements for finality with O(2N) the number of participants as everyone must talk to everyone twice for each block or checkpoint. With more parties involved,more signatures, network overhead, and storage are required and there is greater latency.
只有拜占庭容错委托权益证明可以有效的扩展到无限个验证者的情况(以延迟性为代价)。其他的协议在参与者数量增长的时候对资源的要求增速为O(2N), 因为每个人需要就每个区块或检查节点和其他每个人交谈两次。当越来越的的人参与进来,则需要越来越多的签名,网络经常开销,和存储;并且延迟也会增加。

Assuming DPOS BFT with two second block interval and 21 producers, finality can be reached after 1 minute, but a new block reaches finality every two seconds. This is achieved by pipelining the BFT confirmations. Platforms like EOSIO produce blocks every 500ms, but only rotate proposers every 12 blocks. This means BFT finality takes about 3 minutes based upon pure BFT DPOS block confirmations. The end result is 10x faster than Casper for finality for individual blocks, but a new block reaches finality every two seconds versus every 30 minutes.
假设一个2秒出块和21个出块者的拜占庭容错委托权益证明,定局每1分钟可以达成,但是每一个新的块可以每两秒达成定局。这是靠用管道运输拜占庭容错确认实现的。像EOSIO一样的平台没500微妙出块,但是只在每12个块的时候轮换提议者。这意味着拜占庭容错定局需要3秒,基于纯粹的拜占庭容错区块确认。最终的结果是这比Casper快10倍能达成每个区块的定局,而每2秒而不是每30分钟有一个新的区块达成定局。

DPOS BFT w/ optional Low-Latency Confirmation
拜占庭容错委托权益证明以及选择性的低延迟确认

DPOS Hybrid Pipeline / Realtime BFT
委托权益证明混合管道/实时拜占庭容错

There are many applications where a three minute time for finality is undesirable and/or the DPOS proofs for light clients for a particular block are larger than desired. In this case, a blockchain can make the design choice to do a BFT pre-commit & commit message over every pending block. This gives DPOS-BFT chains finality latency of 1–2 seconds at the expense of the additional network overhead, storage requirements, and CPU usage. Unlike protocols such as Tendermint/Cosmos there can be multiple proposals “in-the pipeline” at the same time. It is even possible that some blocks never receive the “real time” commitment due to network splits, but never the less they are eventually indirectly confirmed.
在很多应用场景中,3分钟的定局时间是不受欢迎的;或者在轻客户端上,某一个特定的区块的委托权益证明的证明(文件大小)过大。应对这些情况,一个区块链可以做出设计上的决定去给每一个未决区块发送拜占庭容错预承诺和承诺信息。这令到拜占庭容错的委托权益证明的定局延迟只有1-2秒,以附加的网络开销,存储需求和CPU用量为代价。有别于Tendermint/Cosmos一类的协议,可以同时有多个提议“在管道里”。甚至有可能的是,有些区块因为网络分裂的原因从未收到“实时”的承诺,但仍然间接的得到了确认。

With the hybrid approach light clients can validate a block with 15 signatures and/or use more advanced cryptographic techniques to merge commit signatures into a single signature. Without the commit messages light clients can still reach BFT finality using a number of consecutive block headers.
混合式的轻客户端可以验证有15个签名的区块或者利用更加先进的密码学方法去合并承诺签名们为一个签名。即使没有承诺信息,轻客户端仍然可以用一连串的区块块头达成拜占庭容错定局。

Degrees of Security
安全程度

It has long been understood that for many applications, such as blog posts and social media voting, waiting for 100% finality is overkill when 99.999% finality can be achieved in less than a second. Protocols like Casper give users the option of relying on Proof of Work confirmations when waiting for the next checkpoint is overkill.
长期以来,人们都能理解像博客文章或者社交媒体投票一类的的用例,当99.99%的定局在1秒内可以达成,那么追求100%的定局是矫枉过正的。像Casper一类的协议让用户依赖工作量证明去等待下一个检查节点也是矫枉过正的。

Some full nodes may not care to process the overhead of all BFT pre-commit/commit messages when all they require is blockchain state. It is enough to know that the block producers (proposers/validators) are reaching real-time consensus and that their blockheaders eventually prove BFT consensus a couple minutes later.
某些只需要区块链状态的完整节点可能并不关心而不去处理所有拜占庭容错预承诺/承诺信息的开销。知道区块制造者(提议者、验证者)在实时达成共识而且他们的区块块头几分钟后最终会证明达成拜占庭容错共识已经足够。

Each consensus algorithm makes certain choices for users and degrades to less-secure variations in different ways. Tendermint/Cosmos/Ripple don’t give users a choice to operate with anything less than full finality. Ethereum gives users a fall-back to proof-of-work, and DPOS-BFT falls back to the original DPOS guarantees.
每个共识机制都会为用户做出一些选择和以不同的方式降级为相对不安全的变种。Tendermint/Cosmos/Ripple并没有给用户任何选择不去按完全的定局去运作。以太坊用户可以倒退为工作量证明,而拜占庭容错委托权益证明可以倒退为原版的委托权益证明保障。

It is even possible to layer the Casper checkpoint algorithm with slashing conditions on top of the DPOS BFT block proposal system. Such an approach would create multiple independent validator sets with both political and economic incentives for good behavior.
在DPOS BFT区块提议系统之上加有削减条件的Casper检查节点算法也是可能的。这样的办法可以促成多个独立的既有政治层面又有技术层面激励的验证者集合。

User Experience
用户体验

Delegated Proof of Stake with BFT optimizes the nominal case while being no-worse in the worst case. Under normal conditions, elected block producers are trusted public figures with legal liabilities and highly reliable nodes. The probability that a produced block will reach finality is already 99.999% which means that the average user gets near-certain finality in under a second. This is reliable enough for almost all day-to-day financial transactions. Larger financial transactions, such as buying a car, merely require the user to wait a few seconds for absolute finality.
拜占庭容错委托权益证明优化象征性的案例而在最坏情况中没有更差。在一般条件下,选出的出块者是受信任的公众人物,在法律上受到约束且高度可靠的节点。产生出来的区块一秒内达成定局的可能性已经是99.999%,这意味着普通用户在一秒内得到近乎肯定的定局。这对几乎所有的日常金融交易都是足够可靠的。更大额度的金融交易,例如买车,只需要用户为了绝对的定局等待几秒。

Each user can decide for themselves how much overhead and/or delay they wish to incur and how big the proofs they want to generate for inter-blockchain communication, whereas other protocols do not give users that choice.
每个用户可以自己决定对于跨链的沟通他们想要多少开销和延迟以及需要多大的证明,而其他协议并没有提供这个选项。

Conclusion
结论

All modern consensus algorithms that follow the BFT consensus principles originally introduced the 1980’s can reach a secure and final state in the worst-case of a partitioned network with ⅓ byzantine participants. Only DPOS BFT and EOSIO is optimized for the 99.999% case of 100% honest nodes without network partitions. DPOS BFT achieves this optimized performance without sacrificing the security guarantees that other protocols provide.
现在所有的追随拜占庭容错共识原则(1980年代提出)的共识算法可以在1/3拜占庭参与者进行网络分裂的最差情况下达到一个安全和最终的状态。只有DPOS BFT和EOSIO优化了没有网络分裂的有100%诚实节点的99.999%案例。DPOS BFT在不牺牲其他协议也提供的安全保障的前提下达到这种优化的表现。

Sort:  

Congratulations @guesshu! You received a personal award!

Happy Birthday! - You are on the Steem blockchain for 1 year!

You can view your badges on your Steem Board and compare to others on the Steem Ranking

Do not miss the last post from @steemitboard:

Are you a DrugWars early adopter? Benvenuto in famiglia!
Vote for @Steemitboard as a witness to get one more award and increased upvotes!