AD
带你了解以太坊高Gas费背后引发的区块链可扩展性问题
高额交易费的背后是区块链可扩展性问题。这个问题众所周知，甚至还有一个专门维基百科页面。可扩展性是目前区块链发展的最大限制，除此之外还有确定性时间长、易出现抢先交易、跨链互操作性等问题
01
杂沓的“一致性”问题Consensus != Consistency
受翻译影响，网上很多议论 paxos 或 raft 的博客运用“分布式一致性协定”或许“分布式一致性算法”如许的字眼，虽然在汉语中“杀青共鸣”和“杀青一致”是一个意义，然则必须要申明在这里议论的是 consensus 问题，运用“共鸣”来表达更清楚一些。而 CAP 定理中的 C 和数据库 ACID 的 C 才是真正的“一致性”—— consistency 问题，只管这两个 C 议论的也不是同一个问题，但在这里不睁开。
为了范例和清楚表达，在议论 consensus 问题的时候一致运用“共鸣”一词。
注：在早些的文献中，共鸣（consensus）也叫做协商（agreement）。
02
共鸣问题 那末共鸣问题究竟是什么呢？举个生活中的例子，小明和小王出去聚首，小明问：“小王，我们喝点什么吧？” 小王：“喝咖啡怎样？” 小明：“好啊，那就来杯咖啡。”在上面的场景中，小王提议喝一杯咖啡，小明表示同意，两人就“喝杯咖啡”这个问题杀青共鸣，并依据这个效果采用行为。这就是生活中的共鸣。
在分布式体系中，共鸣就是体系中的多个节点对某个值杀青一致。共鸣问题可以用数学言语来形貌：一个分布式体系包含 n 个历程 ，每一个历程都有一个初值，历程之间相互通信，设想一种算法使得只管涌现毛病，历程们仍协商出某个不可打消的终究决议值，且每次实行都满足以下三个性子：
住手性（Termination）：一切准确的历程终究都邑认同某一个值。
协定性（Agreement）：一切准确的历程认同的值都是同一个值。
完整性（Integrity），也称作有效性（Validity）：假如准确的历程都提议同一个值，那末一切处于认同状况的准确历程都挑选该值。
完整性可以有一些变化，比方，一种较弱的完整性是认定值即是某些准确经常提议的值，而不必是一切历程提议的值。完整性也隐含了，终究被认同的值必定是某个节点提出过的。
03
为何要杀青共鸣？我们起首引见分布式体系杀青共鸣的效果。
在前文中，我们已相识到分布式体系的几个主要困难：
收集问题
时钟问题
节点毛病问题
第一篇提到共鸣问题的文献[1]来自于 lamport 的 "Time, Clocks and the Ordering of Events in a Distributed System[2]"，只管它并没有明白的提出共鸣(consensus)或许协商(agreement)的观点。论文论述了在分布式体系中，你没法推断事宜 A 是不是发生在事宜 B 之前，除非 A 和 B 存在某种依托关联。由此还引出了分布式状况机的观点。
在分布式体系中，共鸣就经常运用在这类多副本状况机（Replicated state machines），状况机在每台节点上都存有副本，这些状况机都有雷同的初始状况，每次状况改变、下个状况是什么都由相干历程配合决议，每一台节点的日记的值和次序都雷同。每一个状况机在“哪一个状况是下一个须要处置惩罚的状况”这个问题上杀青共鸣，这就是一个共鸣问题。
终究，这些节点看起来就像一个零丁的、高牢靠的状况机。Raft 的论文[3]提到，运用状况机我们就可以战胜上述三个问题：
满足在一切非拜占庭前提下确保平安（不会返回毛病效果），包含收集耽误、分区、丢包、反复和重排序。•不依托于时序。
高可用。只需集群中的大部份节点平常运转，并可以相互通信且可以同客户端通信，这个集群就完整可用。因而，具有5个节点的集群可以容忍个中的2个节点失利。倘使经由历程停掉某些节点使其失利，稍后它们会从耐久化存储的状况举行恢复，并重新加入到集群中。
不仅如此，杀青共鸣还可以处理分布式体系中的以下典范问题：
互斥（Mutual exclusion）：哪一个历程进入临界区接见资本？
选主（Leader election）：在单主复制的数据库，须要一切节点就哪一个节点是指导者杀青共鸣。假如一些由于收集毛病而没法与其他节点通信，大概会发生两个指导者，它们都邑接收写入，数据就大概会发生分歧，从而致使数据不一致或丧失。
原子提交（Atomic commit）：跨多节点或跨多分区事件的数据库中，一个事件大概在某些节点上失利，但在其他节点上胜利。假如我们想要保护这类事件的原子性，必需让一切节点对事件的效果杀青共鸣：要么悉数提交，要么悉数中断/回滚。
总而言之，在共鸣的协助下，分布式体系就可以够像单一节点一样事情——所以共鸣问题是分布式体系最基本的问题。
04
体系模子在斟酌怎样杀青共鸣之前，须要斟酌分布式体系中有哪些可供挑选的盘算模子。主要有以下几个方面：
收集模子：
同步（Synchronous）：相应时候是在一个牢固且已知的有限局限内。
异步（Asynchronous）：相应时候是无穷的。
毛病范例：
Fail-stop failures：节点倏忽宕机并住手相应别的节点。
Byzantine failures[4]：源自“拜占庭将军问题” ，是指节点相应的数据会发生没法预感的效果，大概会相互矛盾或完整没有意义，这个节点以至是在“撒谎”，比方一个被黑客入侵的节点。
音讯模子：
行动音讯(oral messages)：音讯被转述的时候是大概被改动的。
署名音讯(signed messages)：音讯被发出来以后是没法捏造的，只需被改动就会被发明。
作为最罕见的，我们将离别议论在同步体系和异步体系中的共鸣。在同步通信体系中杀青共鸣是可行的(下文将会议论这点)，然则，在现实的分布式体系中同步通信是不切现实的，我们不知道音讯是毛病了照样耽误了。异步与同步比拟是一种更通用的状况。一个适用于异步体系的算法，也能被用于同步体系，然则反过来并不竖立。
让我们先从异步的状况入手下手。
05
异步体系中的共鸣 FLP 不大概（FLP Impossibility）早在 1985 年，Fischer、Lynch 和 Paterson （FLP）在 "Impossibility of Distributed Consensus with One Faulty Process[5]" 证实了：在一个异步体系中，纵然只要一个历程涌现了毛病，也没有算法能保证杀青共鸣。
简朴来讲，由于在一个异步体系中，历程可以随时发出相应，所以没有方法区分一个历程是速率很慢照样已崩溃，这不满足住手性（Termination）。细致的证实已超越本文局限，不在细述。
此时，人们意想到一个分布式共鸣算法须要具有的两个属性：平安性(safety)和活性(liveness)。平安性意味着一切准确的历程都认同同一个值，活性意味着分布式体系终究会认同某一个值。每一个共鸣算法要么牺牲掉一个属性，要么放宽对收集异步的假定。
虽然 FLP 不大概定理听着让人望而却步，但也给厥后的人们供应了研讨的思绪——不再尝试寻觅异步通信体系中共鸣问题完整准确的解法。FLP 不多是指没法确保杀青共鸣，并不是说假若有一个历程失足，就永久没法杀青共鸣。这类不大概的效果来自于算法流程中最坏的效果：
一个完整异步的体系
发生了毛病
末了，不大概有一个肯定的共鸣算法。
针对这些最坏的状况，可以找到一些要领，尽大概去绕过 FLP 不大概，能满足大部份状况下都能杀青共鸣。《分布式体系：观点与设想》[6]提到平常有三种方法：
毛病屏障（Fault masking）
运用毛病检测器（Failure detectors）
运用随机性算法（Non-Determinism）
1、毛病屏障（Fault masking）既然异步体系中没法证实可以杀青共鸣，我们可以将异步体系转换为同步体系，毛病屏障就是第一种要领。毛病屏障假定毛病的历程终究会恢复，并找到一种重新加入分布式体系的体式格局。假如没有收到来自某个历程的音讯，就一向守候直到收到预期的音讯。
比方，两阶段提交事件运用耐久存储，可以从崩溃中恢复。假如一个历程崩溃，它会被重启（自动重启或由管理员重启）。历程在程序的症结点的耐久存储中保留了足够多的信息，以便在崩溃和重启时可以运用这些数据继承事情。换句话说毛病程序也可以像准确的历程一样事情，只是它有时候须要很长时候来实行一个恢复处置惩罚。
毛病屏障被运用在种种体系设想中。
2、运用毛病检测器（Failure detectors）将异步体系转换为同步体系的第二个方法就是引入毛病检测器，历程可以以为在凌驾肯定时候没有相应的历程已毛病。一种很罕见的毛病检测器的完成：超时（timeout）。
然则，这类方法请求毛病检测器是准确的。假如毛病器不准确的话，体系大概摒弃一个平常的历程；假如超时时候设定得很长，历程就须要守候（而且不能实行任何事情）较长的时候才得出失足的结论。这个要领以至有大概致使收集分区。
处理方法是运用“不圆满”的毛病检测器。Chanadra 和 Toueg 在 "The weakest failure detector for solving consensus[7]" 中剖析了一个毛病检测器必需具有的两个属性：
完整性（Completeness）：每一个毛病的历程都邑被每一个准确的历程疑心。
准确性（Accuracy）：准确的历程没有被疑心。
同时，他们还证实了，纵然是运用不牢靠的毛病检测器，只需通信牢靠，崩溃的历程不凌驾 N/2，那末共鸣问题是可以处理的。我们不须要完成 Strong Completeness 和 Strong Accuracy，只须要一个终究弱毛病检测器（eventually weakly failure detector），该检测器具有以下性子：
终究弱完整性（eventually weakly complete）：每一个毛病历程终究经常被一些准确历程疑心；
终究弱准确性（eventually weakly accurate）：经由某个时候后，最少一个准确的历程从来没有被别的准确历程疑心。
该论文还证实了，在异步体系中，我们不能只依托音讯来完成一个终究弱毛病检测器。然则，现实的毛病检测器可以依据观察到的相应时候调治它的超时价。假如一个历程或许一个到检测器的衔接很慢，那末超时价就会增添，那末毛病地疑心一个历程的状况将变得很少。从有用目标来看，如许的弱毛病检测器与抱负的终究弱毛病检测器非常靠近。
3、运用随机性算法(Non-Determinism)这类处理不大概性的手艺是引入一个随机算法，随机算法的输出不仅取决于外部的输入，还取决于实行历程当中的随机几率。因而，给定两个完整雷同的输入，该算法大概会输出两个差别的值。随机性算法使得“仇人”不能有效地障碍杀青共鸣。
和传统选出指导、节点再合作的形式差别，像区块链这类共鸣是基于哪一个节点最快盘算出困难来杀青的。区块链中每一个新区块都由本轮最快盘算出数学困难的节点增加，全部份布式收集延续不断地竖立这条有时候戳的区块链，而承载了最多盘算量的区块链恰是杀青了共鸣的主链（即积累盘算难度最大）。
比特币运用了 PoW（Proof of Work）来保持共鸣，一些别的加密钱银（如 DASH、NEO）运用 PoS（Proof of Stake），另有一些（如 Ripple）运用分布式帐本（ledger）。
然则，这些随机性算法都没法严厉满足平安性(safety)。进击者可以囤积巨量算力，从而掌握或影响收集的大批平常节点，比方掌握 50% 以上收集算力即可以对 PoW 提议女巫进击（Sybil Attack）[8]。只不过前提是进击者须要支付一大笔资金来囤积算力，现实中这类风险性很低，假若有这么强的算力还不如直接挖矿赚取收益。
06
同步体系中的共鸣上述的要领 1 和 2，都想方法让体系比较“同步”。我们熟知的 Paxos 在异步体系中，由于活锁的存在，并没有完整处理共鸣问题（liveness不满足）。但 Paxos 被普遍运用在种种分布式体系中，就是由于在杀青共鸣之前，体系并没有那末“异步”，照样有极大几率杀青共鸣的。
Dolev 和 Strong 在论文 "Authenticated Algorithms for Byzantine Agreement[9]" 中证实了：同步体系中，假如 N 个历程中最多有 f 个会涌现崩溃毛病，那末经由 f + 1 轮音讯通报后即可杀青共鸣。
Fischer 和 Lynch 的论文 "A lower bound for the time to assure interactive consistency[10]" 证实了，该结论一样适用于拜占庭毛病。
基于此，大多数现实运用都依托于同步体系或部份同步体系的假定。
07
同步体系中的拜占庭将军问题Leslie Lamport、Robert Shostak 和 Marshall Pease 在 "拜占庭将军问题（The Byzantine General’s Problem)[11]" 论文中议论了 3 个历程相互发送未署名（行动的）的音讯，并证实了只需有一个历程涌现毛病，就没法满足拜占庭将军的前提。但假如运用署名的音讯，那末 3 个将军中有一个涌现毛病，也能完成拜占庭共鸣。
Pease 将这类状况推行到了 N 个历程，也就是在一个有 f 个拜占庭毛病节点的体系中，必需统共最少有 3f + 1 个节点才可以杀青共鸣。即 N = 3f + 1。
虽然同步体系下拜占庭将军问题确实存在解，然则价值很高，须要 O(N^f+1 ) 的信息交换量，只要在那些平安要挟很严重的处所运用（比方：航天工业）。
PBFT 算法PBFT(Practical Byzantine Fault Tolerance)[12] 算法望文生义是一种有用的拜占庭容错算法，由 Miguel Castro 和 Barbara Liskov 发表于 1999 年。
算法的主要细节不再睁开。PBFT 也是经由历程运用同步假定保证活性来绕过 FLP 不大概。PBFT 算法容错数目一样也是 N = 3f + 1，但只须要 O(n^2 ) 信息交换量，即每台盘算机都须要与收集中其他一切盘算机通信。
虽然 PBFT 已有了肯定的革新，但在大批参与者的场景照样不够有用，不过在拜占庭容错上已作出很主要的打破，一些主要的头脑也被背面的共鸣算法所自创。
08
本文参考了很多材料文献，对“共鸣问题”的研讨汗青做一些基本概述，愿望能对你带来一点协助。
本文提到的论文，很多直接议论效果，疏忽了个中的数学证实，一是本文只是提纲挈领的议论共鸣问题，竖立一个学问框架，后续轻易往里面添补内容；二是斟酌到大部份读者对数学证实历程并不敢兴致，也不想本文变成一本书那末长。本文也脱漏很多主要算法，后续若有必要会继承补充。
加入新手交流群：每天早盘分析、币种行情分析
添加助理微信，一对一专业指导：chengqing930520
上一篇：带你相识世界各地的加密钱银税法
加入新手交流群：每天早盘分析、币种行情分析，添加助理微信
一对一专业指导：chengqing930520
最新资讯
