坎坷的“共识机制”之路——区块链技术引卷

 

导读如果说商业活动是驱动人类文明发展的一架马车,那么价值记录则是马匹的四只蹄铁。自人类500年前发明复式记账以来,价值记录工具、方法随着科技的进步发生了一次次翻天覆地的变化,以区块链为代表的分布式记账也是其中之一。本文将从阐述分布式和非中心化的基本思想开始,带领读者了解区块链及其共识机制,为什么共识在区块链里得以扮演如此重要的角色。摘要

区块链可以看作一个非中心化分布式的账本,参与交易的各方共同维护着同样的账本记录,这意味着各节点都保存账本的完整副本,并认可账本的正确性,没有一个节点能够完全控制记账的权利。它实现了人类记账规则与记账方式的重要突破,从而为线上价值转移提供了基础。

但绝对可靠的分布式对等系统是不存在的。由于组成分布式对等系统各节点的地理位置不同、网络延迟的存在,节点间的通信总是存在不可预测的延迟,因此不同节点对其接收到消息的先后顺序有不同的判断,这种消息处理模式称为异步模型。除了节点通信过程会发生意外,有时组成网络本身的各节点也会发生故障,表现出不可预测行为,它的存在是设计开放式区块链网络共识机制时必须考虑的因素。

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采用工作量证明模式限制一段时间内能够发出提案的节点数量,从而避免同一时间段节点发出不同的提案数目过多,影响最后节点决策的效率与最终一致性。

任何一个希望发出决定下一个区块内容的提案的节点都需要完成一个“数字解谜”的小游戏。这个小游戏的目的在于:

  1. 任何一个成功解谜的节点都可以通过展示谜底,证明它至少完成了一定量的“计算”,即为工作量证明。
  2. 整个网络希望可以通过算法调整谜题的难度,可以动态地根据网络中节点的计算能力进行调整,保证出现一个节点解开谜题的时间期望是相对恒定的。
  3. 这个谜题不应该设计成总是只能由计算能力最强的节点解开,也不能被巧妙的算法破解,每个节点成功解谜的概率应与其计算能力成正比。
  4. 这个谜底应该是可验证的。当一个节点宣布解开谜题时,它会将区块以及谜底广播到其他节点,其他节点应该能迅速的验证谜底的正确性。

密码学再一次给了我们惊喜。哈希函数便是满足以上所有条件的一个“谜面”。前面提到一个区块包括一个哈希指针,以及一棵包含区块内交易及哈希值的Merkle树。现在BTC网络给所有节点发布了一个谜题:在区块的前面加上一个随机数nonce,计算整个区块的哈希值,谜底便是使区块哈希值小于特定的目标值的那个随机数。这样第一个找出对应nonce的节点就幸运地取得了下一个区块的记账权,节点找出nonce的概率与它计算哈希值的速度成正比,也称为节点的算力,这样解谜的过程也被称为挖矿。节点可以将自己挖掘的区块广播出去,其他节点在验证谜题的正确性与区块内交易的合法性之后,就会以:

  1. 停止自己正在进行的解谜工作。
  2. 将此轮记账节点打包的区块加入到自己维护的区块链账本最后。
  3. 清理本地的内存池,删除已经被确认的交易、以及与已经被打包的区块冲突的交易。
  4. 下一个区块的开头引用这个这个区块的哈希指针。

方式表达自己对这个区块提案的支持,从而决策过程完成,该区块中的所有交易变为已确认的状态,我们说这些交易得到了1个区块的确认。随后各节点在延长后的新链上开始新一轮的解谜过程。

坎坷的“共识机制”之路——区块链技术引卷

3.3  最长链原则与“矿工”间的博弈

在刚才提到的“一轮”共识过程中,我们发现,如果单单只靠工作量证明机制,并不能保证系统的最终一致性。因为当节点收到来自其他节点的区块时,没有任何强制性措施让它接受这一区块并加到自己维护的历史区块链之后,另外,由于节点可能存在网络通信等故障,它可能并没有接收到其他节点发出的提案。

BTC网络中通过最长链原则解决系统最终一致性的问题。每个区块都包含有一个指向前一区块的哈希指针,并由此可以追溯到创世区块,我们定义从创世区块到这个区块所形成的“链”上的区块总数为该区块的区块高度。BTC网络规定,当网络中存在所谓的“分叉”时,即多个区块同时引用了同一个区块的哈希指针,只有最长链(即区块高度最高的链)上的交易会被承认。

这样每个节点在选择自己将在哪一个区块进行自己的解谜工作时,如果节点预期自己找出一个谜底所花费的成本低于能从挖掘一个区块中获取的收益,那么它会主动在当前的最长链上进行解谜游戏,因为只有最长链上的交易能够得到确认。

由于这种哈希函数解谜本质上是一个分布式的随机计算过程,同时由两个不同节点解出两个谜底的情况也是可能出现的,这样就导致了分叉的产生。这样一个节点可能根据本地收到分叉区块的顺序选择一个分叉进行解谜工作,但这种分叉是不可持续的。在不同的分支上,同时发现新区块的概率将呈指数级下降。避免网络分叉也是限制一段时间内能够发布提案的节点个数的原因之一。

工作在较短链上的节点一方面损失了可能获得的区块奖励,另一方面增加了在最长链上解谜的节点挖掘区块的概率,因为谜题的难度没有那么快调整。博弈论告诉我们,如果在短链上解谜的节点是理性的,那么它们应该立即抛弃这条较短的链,切换回最长链。因此,整个系统必然会在一个时刻,使所有接入网络的节点对系统的状态达成一致,所达成的共识就是当前的最长链。

此外,这也表明PoW是一种概率性的共识机制。一笔交易经过n次交易确认后,没能成为最终共识的概率随n指数性降低。中本聪经过计算推荐n的取值为6,也就是一笔交易要等待约60分钟才会被看作“一致性”的共识。BTC为了实现更强的一致性而延长了交易得到确认的时间,牺牲了一部分可用性。

3.4  PoW如何防止拜占庭故障破坏共识

设想一个开放性、节点可无需身份验证自由加入的区块链网络,恶意节点的存在是必然的。假设有这样一个攻击者,希望通过操纵区块链网络使自己获益,他可能采取这样几种攻击方式。

女巫攻击:得名于电影《女巫》。《女巫》讲述了一个患有身份认同障碍的化名“女巫”(Sybil)的女性进行心理治疗的故事,她同时具有16种不同的人格。

在某些分布式对等系统中,投票的表决权是与节点个数成正比的。如果网络对新加入的节点的身份不做任何验证,可以任意地创建新的节点,或是攻击者可以攻破身份验证系统,使他创建的节点们看起来像是拥有不同的“身份”,但其实都是由同一个人控制的,这会给系统的安全带来极大的威胁。这种攻击方式称为“女巫攻击”。

在采用PoW共识机制的区块链网络中,仅仅创建节点是不能给攻击者带来额外收益的,因为攻击者的实际算力并没有真的增加,所以PoW是能够抵抗女巫攻击的。

盗取属于其他节点的权益:这一点在区块链网络里也是无法做到的。即使攻击者已经获得了下一个区块的记账权利,要构造出一笔能够通过其他节点检验的合法交易来使用不属于他的货币也是无法实现的。因为这要求攻击者伪造出货币持有者的签名,如果该区块链网络采取的密码学机制是安全的,除非拥有该地址对应的私钥,否则无法构造出可以通过公钥检验的签名。

拒绝服务攻击:攻击者拒绝将特定节点发起的交易请求打包进区块,以干扰这些节点正常使用区块链网络的功能。但其实只要轮到下一次正常节点获得记账权,这些之前未确认的交易都会被打包进区块。

双重支付攻击:考虑攻击者向一个商家发起一笔交易x,支付一定数额的BTC购买某项商品,并且这笔交易x已经被打包进区块,并由一个正常节点广播到网络并得到1次确认,商家看到确认以后把商品出售给了攻击者。如果攻击者此时马上发起另一笔双重支付交易y,它使用与交易x相同的输入(重复消费已使用的输出),但是输出却指向一个攻击者拥有的地址。在交易x已经被确认的情况下,交易y会被记账节点认为是不合法的。

如果攻击者选择将交易x和y分别向一半的节点广播,虽然这两笔交易在其他节点看来都是合法交易,但最后还是只有包含了其中一笔交易的区块会被先挖出。如果恰好有两个节点同时挖出了包含这两笔交易的不同区块(这样的概率已经很低了),则网络发生分叉。攻击者向商家展示交易x获得1次确认的那条链,此时将会有各一半节点在两条链上挖矿,下一个区块被挖出时,最长链也就确定了。但此时已得到1次确认的交易x可能会因为在较短的链上而被取消。为了避免这种情况,商家只需要看到交易经过2次区块确认再交付商品就可以了。

由于BTC的最终一致性,互相冲突的双重支付x和y最终只有一笔会被纳入到长期的共识链当中。一笔交易无法做到同时被支付给两个地址,如果双重支付攻击成功,那么攻击者没有花费BTC就得到了商品,而商家收到BTC的交易成为了无效交易。

如果攻击者拥有一定比例的算力,他可以主动丢弃打包了交易x的区块,重新在前一个区块上挖矿,并且将双重交易y放进新的区块里。如果攻击者掌握的算力足够多,或者运气足够好,能够在包含交易y的链上挖出足够多的区块,使原来包含转账给商家的交易x的链成为短链,被所有节点放弃,从而使双重支付攻击成功。

对于商家来说,可以采用等待多次区块确认的方式避免自己遭受到这种攻击。一笔经过n个区块确认的交易,一般的采用双重支付攻击手段的攻击者如果要丢弃这笔交易及之后的n个区块,重新构造出双重支付交易,并通过算力优势重新追上较长链的区块高度的可能性随n增大指数性降低。但如果攻击者掌握了超过一半的算力,那么他正在挖矿的那条链成为最长链只是时间问题。这也就是下面提到的获取记账权的攻击方式,在PoW共识中又称51%攻击。

获取记账权:如果攻击者采用各种方式尽可能地提高自己获得记账权的概率。当攻击者有51%以上的概率获得记账权时,分叉攻击和双重支付攻击都会变得容易进行,因此我们说PoW共识机制的容错能力为1/2。BTC以一个较巧妙的方式减少了这类攻击发生的可能,一方面,基于工作量证明的共识机制要求节点获得记账权的概率与节点的计算能力成正比,发动此类攻击的成本过高。另一方面,只要出现51%算力的节点,即使没有出现分叉攻击等事件,人们也可能对BTC网络失去信任,导致其价格与内在的价值下降。攻击者虽然掌握了记账权,但是获取的收益却远远不及成本。

坎坷的“共识机制”之路——区块链技术引卷

 

4区分不同共识机制的八个关键要素

BTC、ETH以及其他采用各种共识机制的数字通证的稳定长期运行告诉我们,现有的多种共识机制使区块链网络可以在实际环境中达成可信的共识。

经过对PoW共识机制的分析,我们可以总结出区块链共识过程中的以下八个关键问题,对这几个问题的不同处理方式决定了共识机制的整体特性。
整体:1.  共识机制如何容忍拜占庭故障?

2.  共识机制如何在实际应用中实现一致性、可用性、分区容忍性?

提案发布阶段:

3.  节点如何获得发布提案的资格?

4.  如何选择发布提案的节点?

5.  提案应该包括什么内容?具体地说,应该就区块链网络的哪些数据达成“共识”?

决策阶段:

6.  节点根据什么算法对自己收到的提案集合作出决策?

形成共识:

7.  对记账节点是否存在激励机制?

8.  对恶意节点是否存在惩罚机制?

除此之外,BTC的一些有别于传统的分布式系统的特殊机制也对最终一致性的达成起了关键的作用。例如最长链原则,这个规则的实现需要系统维护一个具有哈希链表结构的“区块链”。以及激励机制,这在传统的分布式数据库中是较难实现的。

如果区块链账本只是单纯的存储交易的历史记录,而不给予记账的节点奖励,由于节点维护一个账本需要付出大量成本,最后会没有节点愿意承担记账责任,导致共识无法形成。这也是区块链技术与传统分布式系统的区别所在。

除了以上分析,我们还可以就安全性、可扩展性、交易性能、匿名性等其他的指标评价共识机制。在本专题后续文章中,我们会从技术、实用性、应用场景等维度对其他主流共识机制进行分析。

附注:

因一些原因,本文中的一些名词标注并不是十分精准,主要如:通证、数字通证、数字currency、货币、token、Crowdsale等,读者如有疑问,可来电来函共同探讨。坎坷的“共识机制”之路——区块链技术引卷
FENBUSHI DIGITAL × 通证通研究院 联合出品

文:宋双杰,CFA;Rin,FENBUSHI投资总监;Hanru,分析师

特别顾问:沈波

转载声明:本文 由CoinON抓取收录,观点仅代表作者本人,不代表CoinON资讯立场,CoinON不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。若以此作为投资依据,请自行承担全部责任。

声明:图文来源于网络,如有侵权请联系删除

风险提示:投资有风险,入市需谨慎。本资讯不作为投资理财建议。

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 2019年1月2日 下午6:37
下一篇 2019年1月2日 下午6:38

相关推荐

坎坷的“共识机制”之路——区块链技术引卷

星期三 2019-01-02 18:37:45

 

导读如果说商业活动是驱动人类文明发展的一架马车,那么价值记录则是马匹的四只蹄铁。自人类500年前发明复式记账以来,价值记录工具、方法随着科技的进步发生了一次次翻天覆地的变化,以区块链为代表的分布式记账也是其中之一。本文将从阐述分布式和非中心化的基本思想开始,带领读者了解区块链及其共识机制,为什么共识在区块链里得以扮演如此重要的角色。摘要

区块链可以看作一个非中心化分布式的账本,参与交易的各方共同维护着同样的账本记录,这意味着各节点都保存账本的完整副本,并认可账本的正确性,没有一个节点能够完全控制记账的权利。它实现了人类记账规则与记账方式的重要突破,从而为线上价值转移提供了基础。

但绝对可靠的分布式对等系统是不存在的。由于组成分布式对等系统各节点的地理位置不同、网络延迟的存在,节点间的通信总是存在不可预测的延迟,因此不同节点对其接收到消息的先后顺序有不同的判断,这种消息处理模式称为异步模型。除了节点通信过程会发生意外,有时组成网络本身的各节点也会发生故障,表现出不可预测行为,它的存在是设计开放式区块链网络共识机制时必须考虑的因素。

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采用工作量证明模式限制一段时间内能够发出提案的节点数量,从而避免同一时间段节点发出不同的提案数目过多,影响最后节点决策的效率与最终一致性。

任何一个希望发出决定下一个区块内容的提案的节点都需要完成一个“数字解谜”的小游戏。这个小游戏的目的在于:

  1. 任何一个成功解谜的节点都可以通过展示谜底,证明它至少完成了一定量的“计算”,即为工作量证明。
  2. 整个网络希望可以通过算法调整谜题的难度,可以动态地根据网络中节点的计算能力进行调整,保证出现一个节点解开谜题的时间期望是相对恒定的。
  3. 这个谜题不应该设计成总是只能由计算能力最强的节点解开,也不能被巧妙的算法破解,每个节点成功解谜的概率应与其计算能力成正比。
  4. 这个谜底应该是可验证的。当一个节点宣布解开谜题时,它会将区块以及谜底广播到其他节点,其他节点应该能迅速的验证谜底的正确性。

密码学再一次给了我们惊喜。哈希函数便是满足以上所有条件的一个“谜面”。前面提到一个区块包括一个哈希指针,以及一棵包含区块内交易及哈希值的Merkle树。现在BTC网络给所有节点发布了一个谜题:在区块的前面加上一个随机数nonce,计算整个区块的哈希值,谜底便是使区块哈希值小于特定的目标值的那个随机数。这样第一个找出对应nonce的节点就幸运地取得了下一个区块的记账权,节点找出nonce的概率与它计算哈希值的速度成正比,也称为节点的算力,这样解谜的过程也被称为挖矿。节点可以将自己挖掘的区块广播出去,其他节点在验证谜题的正确性与区块内交易的合法性之后,就会以:

  1. 停止自己正在进行的解谜工作。
  2. 将此轮记账节点打包的区块加入到自己维护的区块链账本最后。
  3. 清理本地的内存池,删除已经被确认的交易、以及与已经被打包的区块冲突的交易。
  4. 下一个区块的开头引用这个这个区块的哈希指针。

方式表达自己对这个区块提案的支持,从而决策过程完成,该区块中的所有交易变为已确认的状态,我们说这些交易得到了1个区块的确认。随后各节点在延长后的新链上开始新一轮的解谜过程。

坎坷的“共识机制”之路——区块链技术引卷

3.3  最长链原则与“矿工”间的博弈

在刚才提到的“一轮”共识过程中,我们发现,如果单单只靠工作量证明机制,并不能保证系统的最终一致性。因为当节点收到来自其他节点的区块时,没有任何强制性措施让它接受这一区块并加到自己维护的历史区块链之后,另外,由于节点可能存在网络通信等故障,它可能并没有接收到其他节点发出的提案。

BTC网络中通过最长链原则解决系统最终一致性的问题。每个区块都包含有一个指向前一区块的哈希指针,并由此可以追溯到创世区块,我们定义从创世区块到这个区块所形成的“链”上的区块总数为该区块的区块高度。BTC网络规定,当网络中存在所谓的“分叉”时,即多个区块同时引用了同一个区块的哈希指针,只有最长链(即区块高度最高的链)上的交易会被承认。

这样每个节点在选择自己将在哪一个区块进行自己的解谜工作时,如果节点预期自己找出一个谜底所花费的成本低于能从挖掘一个区块中获取的收益,那么它会主动在当前的最长链上进行解谜游戏,因为只有最长链上的交易能够得到确认。

由于这种哈希函数解谜本质上是一个分布式的随机计算过程,同时由两个不同节点解出两个谜底的情况也是可能出现的,这样就导致了分叉的产生。这样一个节点可能根据本地收到分叉区块的顺序选择一个分叉进行解谜工作,但这种分叉是不可持续的。在不同的分支上,同时发现新区块的概率将呈指数级下降。避免网络分叉也是限制一段时间内能够发布提案的节点个数的原因之一。

工作在较短链上的节点一方面损失了可能获得的区块奖励,另一方面增加了在最长链上解谜的节点挖掘区块的概率,因为谜题的难度没有那么快调整。博弈论告诉我们,如果在短链上解谜的节点是理性的,那么它们应该立即抛弃这条较短的链,切换回最长链。因此,整个系统必然会在一个时刻,使所有接入网络的节点对系统的状态达成一致,所达成的共识就是当前的最长链。

此外,这也表明PoW是一种概率性的共识机制。一笔交易经过n次交易确认后,没能成为最终共识的概率随n指数性降低。中本聪经过计算推荐n的取值为6,也就是一笔交易要等待约60分钟才会被看作“一致性”的共识。BTC为了实现更强的一致性而延长了交易得到确认的时间,牺牲了一部分可用性。

3.4  PoW如何防止拜占庭故障破坏共识

设想一个开放性、节点可无需身份验证自由加入的区块链网络,恶意节点的存在是必然的。假设有这样一个攻击者,希望通过操纵区块链网络使自己获益,他可能采取这样几种攻击方式。

女巫攻击:得名于电影《女巫》。《女巫》讲述了一个患有身份认同障碍的化名“女巫”(Sybil)的女性进行心理治疗的故事,她同时具有16种不同的人格。

在某些分布式对等系统中,投票的表决权是与节点个数成正比的。如果网络对新加入的节点的身份不做任何验证,可以任意地创建新的节点,或是攻击者可以攻破身份验证系统,使他创建的节点们看起来像是拥有不同的“身份”,但其实都是由同一个人控制的,这会给系统的安全带来极大的威胁。这种攻击方式称为“女巫攻击”。

在采用PoW共识机制的区块链网络中,仅仅创建节点是不能给攻击者带来额外收益的,因为攻击者的实际算力并没有真的增加,所以PoW是能够抵抗女巫攻击的。

盗取属于其他节点的权益:这一点在区块链网络里也是无法做到的。即使攻击者已经获得了下一个区块的记账权利,要构造出一笔能够通过其他节点检验的合法交易来使用不属于他的货币也是无法实现的。因为这要求攻击者伪造出货币持有者的签名,如果该区块链网络采取的密码学机制是安全的,除非拥有该地址对应的私钥,否则无法构造出可以通过公钥检验的签名。

拒绝服务攻击:攻击者拒绝将特定节点发起的交易请求打包进区块,以干扰这些节点正常使用区块链网络的功能。但其实只要轮到下一次正常节点获得记账权,这些之前未确认的交易都会被打包进区块。

双重支付攻击:考虑攻击者向一个商家发起一笔交易x,支付一定数额的BTC购买某项商品,并且这笔交易x已经被打包进区块,并由一个正常节点广播到网络并得到1次确认,商家看到确认以后把商品出售给了攻击者。如果攻击者此时马上发起另一笔双重支付交易y,它使用与交易x相同的输入(重复消费已使用的输出),但是输出却指向一个攻击者拥有的地址。在交易x已经被确认的情况下,交易y会被记账节点认为是不合法的。

如果攻击者选择将交易x和y分别向一半的节点广播,虽然这两笔交易在其他节点看来都是合法交易,但最后还是只有包含了其中一笔交易的区块会被先挖出。如果恰好有两个节点同时挖出了包含这两笔交易的不同区块(这样的概率已经很低了),则网络发生分叉。攻击者向商家展示交易x获得1次确认的那条链,此时将会有各一半节点在两条链上挖矿,下一个区块被挖出时,最长链也就确定了。但此时已得到1次确认的交易x可能会因为在较短的链上而被取消。为了避免这种情况,商家只需要看到交易经过2次区块确认再交付商品就可以了。

由于BTC的最终一致性,互相冲突的双重支付x和y最终只有一笔会被纳入到长期的共识链当中。一笔交易无法做到同时被支付给两个地址,如果双重支付攻击成功,那么攻击者没有花费BTC就得到了商品,而商家收到BTC的交易成为了无效交易。

如果攻击者拥有一定比例的算力,他可以主动丢弃打包了交易x的区块,重新在前一个区块上挖矿,并且将双重交易y放进新的区块里。如果攻击者掌握的算力足够多,或者运气足够好,能够在包含交易y的链上挖出足够多的区块,使原来包含转账给商家的交易x的链成为短链,被所有节点放弃,从而使双重支付攻击成功。

对于商家来说,可以采用等待多次区块确认的方式避免自己遭受到这种攻击。一笔经过n个区块确认的交易,一般的采用双重支付攻击手段的攻击者如果要丢弃这笔交易及之后的n个区块,重新构造出双重支付交易,并通过算力优势重新追上较长链的区块高度的可能性随n增大指数性降低。但如果攻击者掌握了超过一半的算力,那么他正在挖矿的那条链成为最长链只是时间问题。这也就是下面提到的获取记账权的攻击方式,在PoW共识中又称51%攻击。

获取记账权:如果攻击者采用各种方式尽可能地提高自己获得记账权的概率。当攻击者有51%以上的概率获得记账权时,分叉攻击和双重支付攻击都会变得容易进行,因此我们说PoW共识机制的容错能力为1/2。BTC以一个较巧妙的方式减少了这类攻击发生的可能,一方面,基于工作量证明的共识机制要求节点获得记账权的概率与节点的计算能力成正比,发动此类攻击的成本过高。另一方面,只要出现51%算力的节点,即使没有出现分叉攻击等事件,人们也可能对BTC网络失去信任,导致其价格与内在的价值下降。攻击者虽然掌握了记账权,但是获取的收益却远远不及成本。

坎坷的“共识机制”之路——区块链技术引卷

 

4区分不同共识机制的八个关键要素

BTC、ETH以及其他采用各种共识机制的数字通证的稳定长期运行告诉我们,现有的多种共识机制使区块链网络可以在实际环境中达成可信的共识。

经过对PoW共识机制的分析,我们可以总结出区块链共识过程中的以下八个关键问题,对这几个问题的不同处理方式决定了共识机制的整体特性。
整体:1.  共识机制如何容忍拜占庭故障?

2.  共识机制如何在实际应用中实现一致性、可用性、分区容忍性?

提案发布阶段:

3.  节点如何获得发布提案的资格?

4.  如何选择发布提案的节点?

5.  提案应该包括什么内容?具体地说,应该就区块链网络的哪些数据达成“共识”?

决策阶段:

6.  节点根据什么算法对自己收到的提案集合作出决策?

形成共识:

7.  对记账节点是否存在激励机制?

8.  对恶意节点是否存在惩罚机制?

除此之外,BTC的一些有别于传统的分布式系统的特殊机制也对最终一致性的达成起了关键的作用。例如最长链原则,这个规则的实现需要系统维护一个具有哈希链表结构的“区块链”。以及激励机制,这在传统的分布式数据库中是较难实现的。

如果区块链账本只是单纯的存储交易的历史记录,而不给予记账的节点奖励,由于节点维护一个账本需要付出大量成本,最后会没有节点愿意承担记账责任,导致共识无法形成。这也是区块链技术与传统分布式系统的区别所在。

除了以上分析,我们还可以就安全性、可扩展性、交易性能、匿名性等其他的指标评价共识机制。在本专题后续文章中,我们会从技术、实用性、应用场景等维度对其他主流共识机制进行分析。

附注:

因一些原因,本文中的一些名词标注并不是十分精准,主要如:通证、数字通证、数字currency、货币、token、Crowdsale等,读者如有疑问,可来电来函共同探讨。坎坷的“共识机制”之路——区块链技术引卷
FENBUSHI DIGITAL × 通证通研究院 联合出品

文:宋双杰,CFA;Rin,FENBUSHI投资总监;Hanru,分析师

特别顾问:沈波