区块链常用共识算法总结

这两年，区块链的技术可以说非常火爆。如果你什么都不知道，很难说你是在互联网上。有人把区块链称为互联网2.0，可以说区块链将对现有的互联网技术进行改造升级。那么，让我们来了解一下什么是区块链。

简单来说，所谓区块链技术，也称为分布式账本技术，是一种互联网数据库技术，其特点是去中心化、公开透明，让每个人都可以参与数据库记录。区块链技术需要注意三个概念：

区块链拜占庭将军问题的核心算法

拜占庭的故事大概是这样的：拜占庭帝国拥有巨额财富，周围的10个邻居已经存在很久了，但是拜占庭的城墙坚固到没有一个邻居可以成功入侵。单个邻居的任何入侵都将失败，并且本身可能会被其他 9 个邻居入侵。拜占庭帝国的防御能力如此之强，以至于周边十国至少有一半同时进攻，才有可能突破。但是，如果一个或几个邻居自己答应一起进攻，但实际过程却是背叛，那么入侵者就可以全军覆没。所以双方都谨慎行事，不敢轻易相信邻国。这就是拜占庭将军问题。

拜占庭系统

上述问题源于计算机网络，也就是说在一个有n个节点的系统中，整个系统对于每个请求都满足以下条件：

同时，在拜占庭系统的实际运行中，一般假设系统中的拜占庭节点不超过m个，每个请求满足两个指标：

拜占庭系统的核心协议1，一致性协议

一致协议的目标是使来自客户端的请求在每台服务器上以确定的顺序执行。在协议中，一般有一台服务器称为主节点，负责对客户端的请求进行排序；其余的服务器称为从节点，按照主节点提供的顺序执行请求。所有服务器都在相同的配置信息下工作。这种配置信息称为视图。每次更换主节点，视图都会相应变化。

一致性协议至少包含三个阶段：发送请求、分配序列号和返回结果。根据协议的设计，可能包括相互交互和序列号确认等阶段。

一致性协议主要包括：

2、检查点协议

拜占庭系统每执行一次请求，服务器都需要记录一个日志。如果不及时清理日志，会导致大量日志占用系统资源，影响系统性能和可用性。另一方面，由于拜占庭服务器的存在，共识协议不能保证每台服务器执行相同的请求，因此不同服务器的状态可能不一致。例如，有些服务器可能由于网络延迟而从某个序列号开始，后续的请求不会被执行。因此，拜占庭系统中设置了一个周期性的检查点协议，将系统中的服务器同步到某个相同的状态。因此，周期性检查点协议可以周期性地处理日志，节省资源的同时及时纠正服务器状态。

处理日志的主要问题是区分那些可以清理的日志和那些仍然需要保留的日志。如果一个请求已被 m+1 个非拜占庭服务器执行，并且我可以向其他服务器证明这一点的服务器，那么我可以删除有关此请求的日志。目前常用的协议是服务器每执行一定数量的请求，就将自己的状态发送给所有服务器，并执行其中一种协议。如果一个服务器接收到2m+1台服务器的状态，那么一致部分就是至少m+1台非拜占庭服务器经历过的状态。因此，可以删除这部分日志，同时将自己的状态更新为较新的状态。

3、视图替换

在一致性协议中，已知主节点在整个系统中具有序列号分配、请求转发等核心能力，支配着系统的运行行为。但是一旦主节点自身出错，可能会导致从节点接收到相同序号的不同请求，或者同一个请求被分配多个序号等，会直接导致请求无法执行正确。视图替换协议的作用是在主节点无法继续履行职责时，将主节点替换为从节点，并保证非拜占庭服务器执行过的请求不被篡改。

视图替换协议一般有两种触发方式：

1）仅由服务器触发。在这种触发方式中，判断是否达到服务端一致性的工作是服务端自己的职责，客户端无法从请求的整个执行过程中获取服务端运行状态的信息；

2）客户端被触发。服务器是否达成协议，如果没有，则可以判断服务器运行有问题。如果问题是主节点，则需要服务器更换主节点。

视图替换协议需要解决的问题是如何保证已经被非拜占庭服务器执行的请求不被改变。由于系统达成共识后至少有 m+1 个非拜占庭服务器执行了请求，所以目前的方法是：新的主节点收集至少 2m+1 个服务器的状态信息，而这些状态信息必须包括所有的执行然后，新的主节点将这些状态信息发送给所有的服务器，服务器按照同样的原理同步在前一个主节点上完成的请求。同步后，所有节点都处于相同状态，则可以执行新的请求。

因此，在分布式系统中，虽然有坏人，但坏人可以做任何事（不受协议限制），比如不响应、发送错误信息、向不同节点发送不同的决策、不同的坏节点联合起来做坏事等等。但是，只要大多数人都是好人，完全有可能以去中心化的方式达成共识。

工作量证明

PoW是英文Proof of Work的缩写。 PoW 对节点提交的区块 B 的格式有如下要求：

H(B) ≤目标

其中 H 是哈希算法，target 是一个固定的数字。也就是说，整个区块的哈希值小于给定的数字目标。只有当区块满足这个条件时，一个节点是合法区块，这个区块才能被其他节点接受。当一个节点发现这样一个合法的区块区块链和比特币的总结，也就是挖了一个矿井，就会获得一定的数字货币奖励。这也解决了非中心化多节点结果的决策问题：全网使用找到最早合法区块的节点的数据。

散列函数产生的散列值是随机的，对于原始数据来说具有非常小的值。的变化可以使哈希值与以前完全不同。为了得到一个有效的block，我们可以在block中添加一个冗余的整数nonce，通过不断尝试不同的nonce来找到一个有效的block（比如可以从1开始，不断累积尝试）。

target的值会定期自动调整区块链和比特币的总结，保证出块时间基本固定，比如比特币保证每十分钟生成一个新块。目标值越小，出块难度越大。假设哈希值的最大值为：HASHmax，则每次尝试找到有效块的概率为：

。从这个公式可以看出，目标越小，每次尝试找到有效区块的概率就越小。

在比特币中，每 2016 个区块（两周），target 的值将通过以下公式进行调整：

其中 t2016 表示生成前一个 2016 块所需的时间。花费的时间越短，最终的目标值就越小。生成区块的难度值也可以通过以下公式计算：

特点：

使用POW算法的优点是安全，完全去中心化，主流数字货币都采用了这种方案；比如比特币、莱特币。缺点是效率低，平均每秒只能处理5到7笔交易；

会很耗电；

权益证明

PoS 是 Proof of Stake 的缩写，在 PoW 中找到一个有效的区块需要大量的计算，会耗费大量的电力和时间。为了加快出块速度，PoS 也会综合考虑节点持有的数字货币份额。 PoS的实现方式有很多种，其中一种是混合模式，利用账户余额来调整挖矿难度：

其中balance代表账户余额，t为A时间戳，一般对t有时间范围限制，比如一小时，即一个节点最多只能尝试7200次。

POS：也称为权益证明，类似于存储在银行中的财产，该模型将根据您持有的数字货币的数量和时间为您分配相应的利息。简而言之，它是一个根据您持有的货币数量和时间向您支付利息的系统。在 PoS POS 模式中，有一个术语叫做币龄，每种币每天产生 1 个币龄。有100个硬币，总共持有30天。那么，你的币龄为3000。此时，如果你发现一个POS区块，你的币龄将被清为0。每清空365个币，你将获得0.05个感兴趣的币。块（假设利息可以理解为年利率5%），那么在这种情况下，利息= 3000 * 5% / 365 = 0.41个币，这个很有意思，持币有利息.

POS的优点是提高了处理效率；基于 PoS 的以太坊每秒可以处理大约 30 笔交易。缺点是没有PoW安全，容易受到各种攻击。

DPoS

DPoS 会通过不同的策略在不同的时间通过投票产生一小群节点，这些节点将负责新区块的创建、验证和相互监督。 DPoS 和 PoS 的主要区别在于前者会选举几个代理，代理完成记账。

附件：