区块链共识进化史

[TOC]

POW(Proof of Work)，工作量证明

  • 优点：

    • 自 2009 年以来得到了广泛测试，目前依然得到广泛的使用。

    • 可以抵抗先发优势

  • 缺点：

    • 速度慢。

    • 耗能巨大，对环境不好。

  • 使用者：

    Bitcoin、Ethereum、Litecoin、Dogecoin等。

  • 类型

    有竞争共识

POW的方法最直观——哈希函数是密码学上计算难度经过反复验证的东西，所以用它来做证明是最有效不过的。每发一条消息（上传一个区块）的时候，你要证明你付出了一定的算力，你的证据就是某串你加在区块里的无意义字符串，而加上这个字符串之后，你的区块的哈希值正好小于某个数。哈希函数的特性告诉我们，你没有任何取巧的方法可以做到这一点——唯一的可能是，你真的一个一个字符串地去试了。所以，我们知道你确实付出了很多的代价才能给出这么一个字符串。

POS(Proof of Stake)，权益证明

  • 优点：

    • 节能。

    • 攻击者代价更大。

    • 不易受“规模经济”的影响。

  • 不足：

    • “无利害关系“(Nothing at stake)”攻击问题。

  • 类型：

    有竞争共识。

  • 使用者：

    点点币PeerCoin是第一个使用POS共识的链，它的竞争逻辑同样是计算一个难度值，但是难度值反比于账户币龄，币龄必须要大于30天，并且参与竞争的币龄会在出块后清空

    在点点币中，币龄的计算公式为：币的数量*币所拥有的天数，这使得币龄能够反映交易时刻用户所拥有的货币数量。

  • 备注

    目前，还没有一个区块链真正采用了POS，POS的代表链PeerCoin是有漏洞的，漏洞简单说就是——越有钱的人，作弊付出的代价就越大，所以51%攻击在POS里面更不可行。然而，对于没钱的人而言，他们没代价可付，所以一些恶意行为对于他们是有益的，这就会导致著名的公地悲剧。这种叫Nothing-at-stake attack（无利益攻击），所有POS算法，必须有对付这种攻击的机制，否则就不能用。

    所以POS仍旧是一个缺乏足够实践检验的机制。但是从理论上来看，Ethereum的casper，ALGORAND和Ouroboros是几个比较成熟的POS算法。

DPOS（Delegated Proof-of-Stake），抵押授权证明

  • 优点

    • 节能

    • 共识速度快，EOS为500ms

  • 缺点

    • 略为中心化

  • 类型

    无竞争共识

    DPOS是POS的一个变种，实际上是解决Nothing-at-stake attack（无利益攻击）的另一种方式——没钱的滚蛋，只有有钱才能参加共识。所以，DPOS的本质实际上是一个中心化的共识机制。也因为如此，它的共识速度非常快，EOS是首个达到0.5级别出块速度的区块链平台。

BFT(Byzantine Fault Tolerance)，拜占庭容错

拜占庭算法目前主流的有两种，PBFT（Practical Byzantine Fault Tolerance，实用拜占庭容错）和DBFT（delegated BFT 授权拜占庭容错算法），PBFT是预设出块节点，dBFT则是投票选举出块节点。

  • 优点：

    • 快速。

    • 可扩展

  • 缺点

    • 略为中心化

系统模型

区块链是一个分布式账本系统，参与者通过点对点网络连接，所有消息都通过广播的形式来发送。系统中存在两种角色：普通节点和共识节点。普通节点使用系统来进行转账、交易等操作，并接受账本中的数据；共识节点负责向全网提供记账服务，并维护全局账本。 我们假设在此网络中，消息可能会丢失、损坏、延迟、重复发送，并且接受的顺序与发送的顺序不一致。此外，节点的行为可以是任意的：可以随时加入、退出网络，可以丢弃消息、伪造消息、停止工作等，还可能发生各种人为或非人为的故障。 我们采用密码学技术来保证消息传递的完整性和真实性，消息的发送者要对消息的散列值进行签名。我们定义 〈𝑚〉𝜎𝑖 是节点 𝑖 对消息 𝑚 的电子签名，D(𝑚) 是消息 𝑚 的散列值。如果没有特殊说明，本文所规定的签名都是对消息散列值的签名。

算法

我们的算法同时提供了安全性和可用性，只要参与共识的错误节点不超过 ⌊ (𝑛−1) / 3 ⌋，就能保证整个系统正常运作，其中 𝑛 = |𝑅| 表示参与共识的节点总数，𝑅 是共识节点的集合。令 𝑓 = ⌊ (𝑛−1) / 3 ⌋，则 𝑓 就表示系统所容许的错误节点的最大数量。由于实际上全局账本仅由共识节点来维护，因此系统中的普通节点不参与共识算法，但可以看到完整的共识过程。 参与共识的节点，需要维护一个状态表，用于记录当前的共识状态。一次共识从开始到结束所使用的数据集合，称为视图。如果在当前视图内无法达成共识，则需要更换视图。我们为每一个视图分配一个编号 𝑣，编号从 0 开始，并逐渐递增，直到达成共识为止。 我们为每一个参与共识的节点分配一个编号，从 0 开始，最后一个节点的编号为 𝑛 − 1。每一轮共识都需要有一个节点来充当议长，其它节点则为议员。议长的编号 𝑝 由如下的算法来决定：假设当前共识的区块高度为ℎ，则 𝑝 = (ℎ − 𝑣) 𝑚𝑜𝑑 𝑛，其中 𝑝 的取值范围为 0 ≤ 𝑝 < 𝑛。每一次共识产生一个区块，并附有至少 𝑛 − 𝑓 个共识节点的签名。一旦有新的区块产生，则立即开始新一轮的共识，同时重置 𝑣 = 0。

一般流程

假设系统要求每次产生区块的时间间隔为 𝑡，则在一切正常的情况下，算法按照以下流程执行：

  1. 任意节点向全网广播交易数据，并附上发送者的签名；

  2. 所有共识节点均独立监听全网的交易数据，并记录在内存；

  3. 议长在经过时间 𝑡 后，发送 〈𝑃𝑟𝑒𝑝𝑎𝑟𝑒𝑅𝑒𝑞𝑢𝑒𝑠𝑡,ℎ,𝑣,𝑝,𝑏𝑙𝑜𝑐𝑘,〈𝑏𝑙𝑜𝑐𝑘〉𝜎𝑝〉；

  4. 议员 𝑖 在收到提案后，发送 〈𝑃𝑟𝑒𝑝𝑎𝑟𝑒𝑅𝑒𝑠𝑝𝑜𝑛𝑠𝑒,ℎ,𝑣,𝑖,〈𝑏𝑙𝑜𝑐𝑘〉𝜎𝑖〉；

  5. 任意节点在收到至少 𝑛 − 𝑓 个 〈𝑏𝑙𝑜𝑐𝑘〉𝜎𝑖 后，共识达成并发布完整的区块；

  6. 任意节点在收到完整区块后，将包含的交易从内存中删除，并开始下一轮共识；

该算法要求参与共识的节点中，至少有 𝑛 − 𝑓 个节点具有相同的初始状态：即对于所有的节点 𝑖，具有相同的区块高度 ℎ 和视图编号 𝑣。而这个要求很容易达成：通过区块同步来达到ℎ的一致性，通过视图更换来达到 𝑣 的一致性。区块同步不在本文讨论范畴，不再赘述。视图更换的规则见下文。

节点在监听全网交易以及在收到提案后，需要对交易进行合法性验证。如果发现非法交易，则不能将其写入内存池；如果非法交易包含在提案中，则放弃本次共识并立即开始视图更换。

交易的验证流程如下：

  1. 交易的数据格式是否符合系统规则，如果不符合则判定为非法；

  2. 交易在区块链中是否已经存在，如果存在则判定为非法；

  3. 交易的所有合约脚本是否都正确执行，如果没有则判定为非法；

  4. 交易中有没有多重支付行为，如果有则判定为非法；

  5. 如果以上判定都不符合，则为合法交易；

视图更换

当节点 𝑖 在经过 2𝑣+1 ⋅ 𝑡 的时间间隔后仍未达成共识，或接收到包含非法交易的提案后，开始进入视图更换流程：

  1. 令 𝑘 = 1，𝑣𝑘 = 𝑣 + 𝑘；

  2. 节点 𝑖 发出视图更换请求 〈𝐶ℎ𝑎𝑛𝑔𝑒𝑉𝑖𝑒𝑤,ℎ,𝑣,𝑖,𝑣𝑘〉；

  3. 任意节点收到至少 𝑛 − 𝑓 个来自不同 𝑖 的相同 𝑣𝑘 后，视图更换达成，令 𝑣 = 𝑣𝑘 并开始共识；

  4. 如果在经过 2𝑣+1 ⋅ 𝑡 的时间间隔后，视图更换仍未达成，则 𝑘 递增并回到第 2 步；

随着 𝑘 的增加，超时的等待时间也会呈指数级增加，可以避免频繁的视图更换操作，并使各节点尽快对 𝑣 达成一致。

而在视图更换达成之前，原来的视图 𝑣 依然有效，由此避免了因偶然性的网络延迟超时而导致不必要的视图更换。

流程图

容错能力

我们的算法对由 𝑛 个共识节点组成的共识系统，提供 𝑓 = ⌊ (𝑛−1) / 3 ⌋ 的容错能力，这种容错能力同时包含安全性和可用性，并适用于任何网络环境。由于节点的请求数据包含发送者的签名，恶意的共识节点无法伪造请求，它只能试图将系统的状态回退到过去，从而使系统发生 “分叉”。

我们假设系统所在的网络环境，恰好将所有共识节点分割成 3 个部分，即：𝑅 = 𝑅1 ∪ 𝑅2 ∪ 𝐹，且 𝑅1 ∩ 𝑅2 = ∅，𝑅1 ∩ 𝐹 = ∅，𝑅2 ∩ 𝐹 = ∅。假设 𝑅1 和 𝑅2 都由诚实的共识节点组成，且已形成网络孤岛，各自只能与自己所在集合内的节点通讯；𝐹 全部都是恶意共识节点且已经合谋，可以统一行动；此外，𝐹 的网络条件允许它们和任意节点进行通讯，包括 𝑅1 和 𝑅2。 如果 𝐹 想要使系统发生 “分叉”，只需与 𝑅1 达成共识并发布区块，并在不通知 𝑅2 的情况下与之达成第二次共识，“撤销” 与 𝑅1 的共识。

若想满足这个条件，需满足：|𝑅1| + |𝐹| ≥ 𝑛 − 𝑓，且 |𝑅2| + |𝐹| ≥ 𝑛 − 𝑓。在最坏的情况下，|𝐹| = 𝑓，即恶意节点的数量达到系统所能容忍的最大值，则上述关系变为： |𝑅1| ≥ 𝑛 − 2𝑓，且 |𝑅2| ≥ 𝑛 − 2𝑓。两式相加：|𝑅1| + |𝑅2| ≥ 2𝑛 − 4𝑓，化简后：𝑛 ≤ 3𝑓。已知 𝑓 = ⌊ (𝑛−1) / 3 ⌋ ，与上式矛盾，故可证明系统在容错范围内无法被分叉。

上一页Cosmos下一页Tendermint 的区块构成

最后更新于