但绝对可靠的分布式对等系统是不存在的。由于组成分布式对等系统各节点的地理位置不同、网络延迟的存在，节点间的通信总是存在不可预测的延迟，因此不同节点对其接收到消息的先后顺序有不同的判断，这种消息处理模式称为异步模型。除了节点通信过程会发生意外，有时组成网络本身的各节点也会发生故障，表现出不可预测行为，它的存在是设计开放式区块链网络共识机制时必须考虑的因素。
FLP不可能原理表明：异步的分布式系统中不存在能容错（Fault Tolerant）的狭义共识算法。CAP原理表明：分布式系统最多只能同时满足一致性、可用性和分区容错性中的两项特性。
我们根据区块链网络的特点作出有别于传统分布式系统的CAP定义，并以btc及其共识机制工作量证明（PoW）为例，分析其共识机制的原理与过程，从密码学、概率论、博弈论的角度说明最终一致性的可实现性。以及为了满足实际应用场景的需求，PoW如何在一致性、可用性和分区容忍性实现完美平衡。我们还将分析节点可能对区块链网络发动的恶意攻击，并阐明PoW有一定抵御常见的恶意攻击的能力。
最后我们在分析PoW的基础上，抽象出区块链共识机制的八个关键要素，它们决定了共识机制的主要特征。在专题后续文章中，我们将进一步介绍主流的共识机制及其特点。
目录
1 什么是区块链：漫谈分布式系统与非中心化
1.1 记账方式与信任
1.2 分布式与非中心化的融合
2 分布式对等系统内部的通信与共识
2.1 不存在绝对可靠的分布式对等系统
2.2 “狼人杀”与拜占庭将军们
2.3 分布式系统不存在完美的确定性共识算法
2.4 CAP原理与区块链共识机制
3 PoW工作量证明——一致性与可用性的权衡
3.1 BTC实现实际应用中的一致性
3.2 密码学是PoW一致性的基础
3.3 最长链原则与“矿工”间的博弈
3.4 PoW如何防止拜占庭故障破坏共识
4 区分不同共识机制的八个关键要素
正文
1什么是区块链：漫谈分布式系统与非中心化
“资本主义实践将货币单位转换成为合理的成本-利润计算的工具，复式记账法是它高耸的纪念塔。”——熊彼特
1.1 记账方式与信任 如果说，商业活动是驱动人类文明发展的一架马车，那么价值记录则是马匹的四只蹄铁。14世纪晚期，在文艺复兴的发源地意大利——中世纪欧洲的海上贸易中心，复式记账法诞生了。这项500多年前的发明也是现代会计学的重要基础。目前最常用的借贷记账法基于一个简单的恒等式：资产=权益+负债。交易的本质是价值的转移，复式记账法使资金转移过程的记录变得清晰，让验证账本的正确性变得简单，与“记流水账”相比，增加了不诚实的记账人造假的成本。 随着20世纪电子计算机的发明，人类的记账工具开始向数字化演进。数据库技术与互联网的普及，使电子支付成为了可能，数据的规模与处理效率也得到了极大的提升，但这背后的复式记账法则仍然没有改变。在传统的记账方法中，账本由一个单一的记账人维护。这种由单一的中央机构实现对数据的存储、记录以及维护的模式被认为是中心化的。账本的正确性与不可篡改性以记账人的声誉、信用或资产担保。 在中心化的记账体系里，参与交易的双方各自维护着自己的账本，这样就产生了一些问题：双方的账本若不一致该如何处理？如何保证双方不会为了自己的利益篡改账本？为了解决这些信任问题，仍然需要专业机构对公司账目进行审计，带来的额外成本也非常大。于是参与交易的各方共同维护同一个账本的记账方式就应运而生了，这也是分布式账本的思想。 1.2 分布式与非中心化的融合 区块链行业提到的“非中心化分布式”这一概念与传统计算机科学中的分布式计算略有不同。一个分布式计算系统通常出于解决： 单个节点的计算性能瓶颈。 属于同一公司或组织的不同计算节点在地理位置上的分散性。 节点数据的分散储存与备份问题。 一般来说，由能够互相通信的多个能够实现“最小功能”的工作单元以实现同一项任务为目标协同工作组成的系统称为分布式系统。分布式系统的一个工作单元称为节点。 在理想的分布式系统中，用户可以通过任意节点使用系统的完整功能。 那么区块链和传统分布式系统相比有什么特点呢？ 之前提到，区块链最初的目的是进行非中心化的分布式记账，这要求参与交易的各方（各节点）共同记录同一个账本，意味着各节点都保存账本的完整副本，并能够检验账本的正确性。因此，我们可以认为区块链是由多个具有记账功能的节点以维护一个特定账本的完整记录为目标协同工作的分布式系统。 随着技术的发展，其功能也不仅仅局限于单一的“记账”。账本的概念扩展为一个可以增添记录的特定“数据结构”，并定义其为当前系统的“状态”。整个网络的目的就是共同维护一个“系统状态”。 但如果整个分布式记账系统由一个中心节点来控制的话，其实依然可以对账本进行整体化的篡改。而区块链的非中心化性解决了这一问题。 有别于某一些存在中心节点分发并确认任务的分布式系统，在区块链网络中，没有一个节点能够完全决定系统的当前状态。通常说这种不存在某一个或一些特殊的节点能够决定系统状态的分布式系统是非中心化的。 回到区块链究竟是什么的问题上来。大部分人认为它是继互联网之后的又一重大技术革新，极客们认为它是能够不同于中心化体的一套自治的的体系。也有人认为区块链是一个无需第三方信用背书、信息可溯源且不可篡改的数据库。 事实上，非中心化与中心化的概念仍然没有明确的定义，人们对两种模式的争论仍然在继续。 从技术的层面来说，区块链同时具有分布式系统和非中心化的特征，是两者的有机结合。因此它同时具有：节点以维护账本的正确性为目标、没有中心节点可以控制账本的记录的特点。由此带来应用层面的特性包括无需中心机构的可信任性，以及安全信息记录方式。有些区块链网络还实现了智能合约，能够自动地执行流程化的交易，进一步提升了效率。 2分布式对等系统内部的通信与共识
“蜂群意识、经济体行为、超级电脑的思维，以及我的生命分布 在众多更小的单元上。我们所能发现的最有趣的奇迹——生命、智力、进化，全都根植于大型分布式系统中。”——凯文?凯利
2.1 不存在绝对可靠的分布式对等系统 假设有一个由n个节点共同维护的分布式账本，并且每个节点都能够对账本进行本地处理，也能够向其他所有节点发送消息（称为广播一条消息，在有的消息模型中不存在一对多的广播渠道）。如果有数个节点对账本进行了修改，它们会向其他节点发送一条包含修改内容的消息。在实际情况中，会出现各种各样的意外： 消息损坏、消息被恶意篡改：解决方案是为消息添加校验信息。 消息丢失：由于通信网络不能正常工作，可能有部分或全部的节点没有收到某条消息。 不确定的消息延迟：由于各节点的地理位置、网络状况不同，收到来自其他节点消息的时刻与该节点发送消息的时刻之间总是存在不可预测的延迟，因此不同节点对其接收到消息的先后顺序有不同的判断。 我们一般认为不同的节点本身的时钟也是不完全同步的，又由于消息丢失和不确定延迟的存在，所以当节点在处理消息时，不能使用基于时间的控制流程：“在某时某刻，开始执行某操作”、“先处理来自节点i的消息，再处理来自节点j的消息”，而只能采用基于事件的控制流程：“当收到来自节点i的消息，开始执行某操作”。这种处理方式称为异步模型（Asynchronous Model）。在异步模型中，我们假设节点在本地对消息的处理时间要远远短于消息的延迟。 除了传递消息的通信过程会发生意外，有时组成网络本身的各个节点也会发生故障。一个著名的例子就是拜占庭将军问题，在下一节会具体介绍。 我们先简单地假设n个节点中存在f个不能正常工作的节点，但网络通信都是可靠的，即不存在消息丢失这一情况，并且假设初始条件下所有节点保存了相同的账本。当一笔交易发生后，需要对账本增加一条记录，参与交易的节点会向其他节点发送一条消息，称这条记录了修改内容的消息为节点发出的一个提案。当节点收到来自其他节点的提案时，需要从全部提案中选出一个提案作为自己的决策，决策应该满足三个条件： 合同性（Agreement）：所有正常工作节点的决策应该相同，即对账本应该记录的内容达成一致。 有效性（Validity）：决策必须从提案中选出。 可终止性（Termination）：节点选择决策的时间必须是有限的。 满足条件的决策值即作为一条新的记录被添加到账本中，同时成为新的系统状态。 狭义概念的共识可以表述为，节点收到来自其他节点的提案并根据一定的规则作出满足上述三个条件的决策的过程。 很多人都有过抢购火车票的经历，考虑这样一个“分布式”售票系统：由数个售票节点组成的分布式系统，维护一个记录车票余量和购买信息的数据库，以及请求购票服务的用户节点A和B。当用户发出购买车票的请求后，节点应当就车票余量与用户购买是否成功达成一致判断。 这个系统若要达成狭义的共识，要求所有正常工作的售票服务器应当就上次达成共识状态后，到本次共识完成前，在有限时间内对数据库的修改提案作出相同的决策。尤其是对于消息的先后顺序也应达成一致的判断，否则，如果车票只有一张，而用户A和B几乎同时发出一次购买请求，不同的售票节点对于A和B谁先发出请求可能存在不同的判断。在传统的中心化系统中，可以通过判断A和B发出请求时间的先后决定票应该卖给谁。但在我们讨论的“分布式对等系统各节点不能访问一个同步的时间服务器”情况下，解决这个问题将会变的更加复杂。 2.2 “狼人杀”与拜占庭将军们 上个世纪的航空航天专家们为了提高飞机的安全系数，曾经对飞机上安装的传感器发生的错误进行统计建模。他们发现，在高空环境下，失灵的仪器不但会停止工作，还会随机地发出错误的信号，极大影响飞行员对于飞机状况的判断，从而造成安全事故。 在通信网络的研究中，有一个著名的拜占庭将军问题：假设有n个将军需要合作进攻地方的城池，他们的军队驻扎在n个不同的驻点，相互间只能通过信使通信，根据其他将军的提案作出行动决策。为了简化问题，将军的提案限定于“进攻”与“撤退”两种，必须通过投票来决定所有军队是一起进攻或一起撤退。将军们可看作分布式对等系统的节点，而信使则是不可靠的信道。除此之外，将军中还可能出现反叛者，反叛者将不会遵守忠诚将军的行为规范，甚至会蓄意破坏忠诚将军之间的共识。参考下图，考虑5名将军组成的系统，其中有1名反叛者，如果2名忠诚将军发送“进攻”的提案（绿色的将军），2名忠诚将军发送“撤退”的提案（橙色的将军），那么反叛者在收到提案后可以向发送“进攻”的将军发送“进攻”的提案（绿色的箭头），并同时向发送“撤退”的将军发送一个“撤退”的提案（橙色的箭头），这样在每一名忠诚的将军看来，自己的提案都是占多数的，因此投“进攻”的将军会进攻，投“撤退”的将军会撤退，军队的一致性被打破。除此之外，信使也可能被敌人截杀或者反叛等。可见由于节点的背叛或者通信系统的不可靠，系统的一致性便得不到保障。 这就像“狼人杀”游戏里的村民和狼人。在每一个夜晚结束后，所有玩家（节点）就上一轮被处死的玩家达成了共识，并通过轮流发言（类比相互通信），指出自己认为的凶手（提案），并经过投票表决（决策）选出凶手（达成共识）。由于狼人的存在（表现出恶意行为的节点）、信道的不完美、玩家之间身份的不透明，狭义的共识是很难达成的。（当然这个类比也有不完美之处） 2.3 分布式系统不存在完美的确定性算法 关于一个分布式系统能否达成狭义共识的问题，已经有很多学者研究过。我们继续之前的假设，即使一个网络通信都可靠的分布式系统，并且节点发出的提案非常简单：只从0和1当中取值，那么是否存在一个算法，使这个系统在异步模型下能够达成狭义共识呢？ 遗憾的是，Fischer，Lynch，Patterson三位科学家在1985年发表的论文中证明了，在这样的分布式系统中，即使存在一个可能失效的节点（f=1），也不存在一个确定性的算法，总能在异步模型下达成狭义共识，这就是著名的FLP不可能原理。 在一个分布式系统中，节点可能出现多种故障。 我们定义分布式系统的三个特性（CAP）： 一致性（Consistency）：系统的所有节点访问同一份最新的数据副本。 可用性（Availability）：每次请求都能获取到非错的响应，但是不保证获取的数据为最新数据。 分区容忍性（Partition Tolerance）：以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间作出选择。 CAP原理表明，分布式系统无法同时满足一致性、可用性、分区容忍性，最多只能同时满足其中两个特性。 CAP原理适用于传统的分布式系统，但区块链这样的分布式和非中心化结合的网络有很多不同之处。我们将说明当前的区块链共识机制可以实现三者接近完美的平衡。 2.4 CAP原理与区块链共识机制 我们将CAP三个条件放在区块链网络的实际应用场景中考虑，了解一下区块链对CAP特性的适用性： 一致性（Consistency）：分布式对等系统中的概率共识可以解决拜占庭故障，从而达到最终的一致性。 可用性（Availability）：每次请求都能获取到非错的响应，但是不保证获取的数据为最新数据。 分区容忍性（Partition Tolerance）：系统能够在一定的时限内达成数据一致性。 比如在PoW的共识机制中，当两个节点分处分区两侧时，区块链会根据其概率共识（51%的算力支持）来确定某个数据结果，并确认整条主链，主链上每一个节点的最新数据副本相同，保证了C性质；而分区一侧有不同结果的节点会被更新状态，继续参与记账，保证了A性质；在这一段时间内，两个节点依然可以互相通信，保证了P性质。 从而使PoW可以实现CAP接近完美的平衡。 区块链能够在一定时间内通过概率共识对系统节点进行更新，并达成一致性，从而满足CAP特性。 3PoW工作量证明——一致性与可用性的权衡 3.1 BTC实现实际应用中的一致性 以之前的“分布式售票系统”举例来说明最终一致性。也许当你在查询车票时，用户节点存储的数据库是“有票”状态，但在你完成购票之前另一名用户已经完成了购票操作，售票节点的数据库已经更新。当你点下付款按钮时，售票节点通知用户节点更新系统的状态，这时就会提醒你“车票已售完”。“双十一”抢购时天猫等购物网站的系统也有类似设计。 我们并不需要在任何时刻都保证节点读取同样的系统状态，而是保证所有拜占庭故障经过有限时间后就系统的状态达成一致，称为最终一致性。 从这个例子还可以看出，在某个时间段内，节点可能保存的系统的状态不同，因此发出的提案可能存在冲突，需要一个冲突解决机制避免冲突的提案对系统状态的影响，并使节点最终对某个系统状态达成共识。 BTC网络是一个任何节点都可自由加入、不记名的区块链网络，要达成一个全部节点参与的、满足一致性的共识是很难的。PoW机制通过一些巧妙的机制，实现了应用环境可信强度的一致性。 为什么最终一致性可以替代一致性，系统如何选择出一个状态成为最终的共识呢？为了解答这个问题，我们首先需要了解区块链的结构和PoW的工作原理。 3.2 密码学是PoW一致性的基础 BTC是一个分布式对等账本。一个加入BTC网络的用户可以生产任意个成对的公钥和私钥。私钥由用户保存，是不应该泄露给他人的。私钥可以用于对消息签名，签名不可伪造，并且是可以通过私钥对应的公钥验证的。密码学保证签名具有以下特点： 有效性。如果用户用私钥签名了一个消息，那么其他任何人使用私钥对应的公钥、消息原文来验证签名，该签名必须是有效的。 不可伪造性。如果没有掌握某个私钥，就无法对一条之前该私钥没有签过名的消息生成一个签名，并且使它可以被公钥验证为有效。也就是说，仅仅掌握了公钥是无法伪造相应私钥的签名的。在实际情况中，找到公钥对应私钥的代价通常非常巨大，以至于我们认为这是“无法完成的”。 在BTC的世界中，公钥代表节点的身份。地址通常是公钥经过数次哈希处理得到的字符串，与公钥存在对应关系。地址也被用于标识一定数量的比特币的归属。 在BTC的网络里，一笔交易是一个特殊的数据结构，它包含了若干个输入和若干个输出，描述的是一次BTC使用权的转移情况。 一个输出是一个包含了一定数额的BTC和一个使用条件组成的列表。使用条件一般与某个地址相关联。输出存在已使用和未使用两个状态。BTC账本并不记录某个地址对应的BTC余额，地址的余额是某一时刻与它关联的所有未使用输出的BTC数额之和。所有未使用的交易输出（Unspent Transaction Outputs，UTXO）就构成了BTC这个区块链网络的一个状态。网络中的（全功能）节点各自维护一个状态的副本，并在某一时刻就系统的状态达成最终一致。 一个输入同样也是一个列表，包含对之前一个未使用输出的引用，以及能够证明交易创建者满足该输出使用条件的有效签名。即证明交易创建者对他引用的未使用输出中BTC的使用权，被引用的输出会从UTXO中删除。一笔交易还要满足以下条件：输出所包含的总金额应小于等于输入所包含的总金额。这时输入与输出的差额作为交易费作为激励费用奖励给记账的节点。满足以上输入与输出的交易被看作是“合法的”。 当一个地址要发布一笔交易时，它所做的其实是向BTC整个网络中的节点广播该条交易，该条交易会被标记为“未确认的”（Unconfirmed）。BTC网络并不是收到一条广播就立刻更新系统的状态，而是有区块以及内存池的设计。 在某一个时刻，所有BTC节点都维护着一个记录UTXO的账本，并有一个接收未确认交易的内存池（Mempool），当收到一条交易广播时，节点就会把该交易加入自己的内存池。由于网络通信的原因，各个节点内存池中的交易都不完全相同。 一“轮”共识过程开始于节点对“哪些未确认的交易应该被确认”发出提案。在BTC网络中，交易都是被“打包”放进区块进行处理的。区块（Block）是一个精心设计的数据结构，它包含两部分。第一部分是一个哈希指针，它包含上一区块的哈希值，可以表明自己上一个区块的信息。第二部分是一个Merkle树，它的叶节点是被打包进该区块的所有交易的哈希值，非叶子节点则是根据它的两个子节点计算出的哈希值。通过Merkle各节点的哈希可以方便地验证该区块内所有交易的完整性。这样的一个个区块由哈希指针连接组成的“链”被形象地称为区块链。 一个区块还包含了一个coinbase交易（币基交易），这个交易仅包含一个名义上的输入，它不指向之前任何一笔未确认的输出，输出的总金额等于一个固定的数值（当前是12.5，表示打包一个区块获得的奖励），加上该区块里所有交易的交易费。币基交易不消耗未确认的输出，因此这部分固定的奖励BTC是被新“创造”出来的，将被支付给打包这个区块的节点。这也是唯一一种“发行”新的BTC的方式。 因为这种奖励的存在，使得节点之间有竞争“记账权”的动力，每个节点都希望自己打包的区块成为系统的长期共识（最终一致性共识），因为只有这样自己才能获得币基交易的奖励。BTC采用工作量证明模式限制一段时间内能够发出提案的节点数量，从而避免同一时间段节点发出不同的提案数目过多，影响最后节点决策的效率与最终一致性。 任何一个希望发出决定下一个区块内容的提案的节点都需要完成一个“数字解谜”的小游戏。这个小游戏的目的在于： 任何一个成功解谜的节点都可以通过展示谜底，证明它至少完成了一定量的“计算”，即为工作量证明。 整个网络希望可以通过算法调整谜题的难度，可以动态地根据网络中节点的计算能力进行调整，保证出现一个节点解开谜题的时间期望是相对恒定的。 这个谜题不应该设计成总是只能由计算能力最强的节点解开，也不能被巧妙的算法破解，每个节点成功解谜的概率应与其计算能力成正比。 这个谜底应该是可验证的。当一个节点宣布解开谜题时，它会将区块以及谜底广播到其他节点，其他节点应该能迅速的验证谜底的正确性。 密码学再一次给了我们惊喜。哈希函数便是满足以上所有条件的一个“谜面”。前面提到一个区块包括一个哈希指针，以及一棵包含区块内交易及哈希值的Merkle树。现在BTC网络给所有节点发布了一个谜题：在区块的前面加上一个随机数nonce，计算整个区块的哈希值，谜底便是使区块哈希值小于特定的目标值的那个随机数。这样第一个找出对应nonce的节点就幸运地取得了下一个区块的记账权，节点找出nonce的概率与它计算哈希值的速度成正比，也称为节点的算力，这样解谜的过程也被称为挖矿。节点可以将自己挖掘的区块广播出去，其他节点在验证谜题的正确性与区块内交易的合法性之后，就会以： 停止自己正在进行的解谜工作。 将此轮记账节点打包的区块加入到自己维护的区块链账本最后。 清理本地的内存池，删除已经被确认的交易、以及与已经被打包的区块冲突的交易。 下一个区块的开头引用这个 区块的哈希指针。 方式表达自己对这个区块提案的支持，从而决策过程完成，该区块中的所有交易变为已确认的状态，我们说这些交易得到了1个区块的确认。随后各节点在延长后的新链上开始新一轮的解谜过程。
发表评论 取消回复