注：本文档已于2015年3月进行了大量修改。旧版本可以在
?https://download.wpsoftware.net/bitcoin/old-pos.pdf找到。
引言
2009年，中本聪创造了比特币。比特币是一种互联网货币系统，可以实现点对点的数字代币转账。为确保所有人就代币所有权达成共识，中本聪采用了一种可由所有网络参与者复制并验证的公共账本。为了避免单点故障，该账本采用一种动态成员多方签名机制来证实，即，在每次“心跳”时对整个账本历史执行一次高成本计算。
不同于传统的数字签名，DMMS中没有“可伪造性”的概念。每个DMMS的创建成本都很高，并且，这种行为可以得到账本上增发的新货币作为奖励。由于这些新代币必须得到其他人的认可才有用，参与者会受到激励来共同扩展“真正的账本”，而非自行创建账本?1。
由于比特币的DMMS在计算和热力学方面成本非常高，人们已经提出了其它更为经济环保的方案。最常被提议的方案是PoS，它是一种低成本的分布式共识机制。正如AndrewPoelstra在2014年所言，PoS是不可行的，但还是涌现出各种形式的PoS方案。与此同时，各种论坛上经常有人声称Poelstra的论点是“虚假”或“错误”的，尽管他们从来没有提出任何有说服力的反例或错误。此外，也有人给出了中肯的意见，认为Poelstra的这篇论文写得晦涩枯燥。由此可见，这篇论文还有许多不足之处。虽然Poelstra没有发现他的前作有任何不准确之处，但是他准备借此机会进一步地正式阐述他的论点。
相比Poelstra撰写论文时，人们对比特币共识的科学认识已经有了巨大进步。
本文旨在更新Poelstra的论文，阐明比特币所解决的问题，PoS背后的设计原理，以及PoS之类的机制无法在比特币的信任模型中产生分布式共识的原因。
注1:为了确保所有参与者都可以看到“真正的账本”，我们需要一个同步网络：所有数据都能在一定的时间长度λ内到达所有参与者，而且网络心跳时间比λ长得多。如果没有同步网络，分布式共识的难度会大得多。
分布式共识
在讨论比特币对于分布式共识问题的解决方案之前，我们首先要理解这个问题的本质。分布式共识是一种彼此之间缺乏信任的参与方之间达成的共识。这些参与方都是匿名的，而且在系统建立时并不一定存在。正如Poelstra在其论文中所解释的那样：
就密码学货币而言，仅在交易的时间顺序上达成分布式共识就足够了，即，就“第一个转移特定资金的交易达成共识”。这样可以确保整个网络都认可新的资金所有者。
之所以需要达成这种共识，是为了防止?重复花费?问题。在所有去中心化数字货币机制中，都有可能出现付款方将同一笔资金发送给两个不同的人的情况，而且这两笔交易看起来都是有效的。因此，收款方需要能够确保没有发生冲突，或者在有冲突的情况下，网络会认可其交易为正确版本。就交易顺序达成分布式共识可以实现这一目的：在发生冲突的情况下，每个人都认可第一笔交易是有效的，其余交易是无效的。
重点是，我们应该意识到，尽管分布式共识是个难题，但是普通共识更加容易，经过了更深入的研究，而且使用受信任且可识别的签名方可以将效率提高数万亿倍。因此，引入了受信任方的密码学货币都应该考虑的一点是，其新型信任模型是不是能帮助降低达成共识的难度。对更高效的、具备受信任方的共识机制感兴趣的读者可以研究一下。
动态成员多方签名
比特币的账本是公开可用的，比特币网络中的所有参与者都可以验证账本上每笔交易的有效性。然而，由于账本在根本上属于历史记录，密码学无法辨别真伪，必须要有人来证明账本，而且其他人必须相信这个人不会签署错误的历史。
最早的数字现金系统都由单个非匿名者签署所有交易。然而，这样不仅为系统引入了单点故障风险，而且可以让签署方审查交易或发起重复花费。虽然我们可以采用盲签名来防止审查制度，但是无法防范单点故障和重复花费问题。多方签名或许有可以解决后面两个问题，但是所有签名方难以同时遭到胁迫与所有签名方必须得到所有参与者的信任这两个要求是相互冲突的。非匿名性也意味着，特定攻击者总能持续攻击系统。
比特币的解决方案是完全去掉固定且可识别的签名者。比特币的账本由一组被称为矿工的签名者验证，他们不向其它参与者公开自己的身份，或许还可以零成本进入或退出系统。矿工通过叫做“挖矿”?的过程来生成签名。在挖矿过程中，他们会共同为连续的、由交易数据组成的区块生成?工作量证明?。
在本节中，我们将解释挖矿是如何运作以及如何提供验证的。
匿名世界里的鉴别
密码学数字签名机制的运作原理如下。签名方生成“签名”和“验证”密钥对，并将v连同其姓名一起发布在某个公共渠道上。该签名方可以根据给定消息m生成签名σ，任何人都可以验证σ的有效性。也就是说，将v，m和σ输入验证算法，如果签名是有效的，总是会输出1。
为了安全起见，传统数字签名必须具备抗伪造性，即，任何计算能力有限的攻击者伪造签名的概率都微乎其微。具体而言，“伪造”指的是能在下列游戏中胜出：
签名者将验证密钥v交给攻击者。
攻击者将消息m_i发送给签名者，并收到这些消息的有效签名σ_i。攻击者可以多次重复该操作。
攻击者生成一个新的消息m连同一个基于m的有效签名σ。
这种安全性被称为?选择明文攻击下的不可伪造性，是密码学文献中的常见标准。
在多方签名机制中，每个签名者都有一个验证密钥。只有签名者的“可采信子集”生成的签名才有效。在定义安全性时，上述游戏经过了修改，允许攻击者请求签名密钥，只要该攻击者获得的密钥无法组成“可采信子集”即可。
可以看出，验证算法使用验证密钥v来验证签名，并通过这种方式来验证签名者的“身份”。由于任何人都可以创建密钥对，若想签名具有价值，必须通过公共记录将验证密钥与签名者的真实身份联系起来。如果出现失信行为，失信方会被问责。
这样来看，身份鉴别并不适用于签名者匿名且不固定的系统。事实上，我们还不清楚“身份鉴别”在这类系统中能发挥什么作用！如果任何人都能以匿名方式生成签名，就无法区分诚实的签名和不诚实的签名、真实的历史和虚假的历史。那么上述安全性定义就丧失了意义，因为攻击者可以自由加入签名者集，并“伪造签名”2。
为了解决这一问题，比特币采用了另一种安全模型。在该模型中，所有参与者都平等，但是他们会在经济激励下保持诚实。在下一部分，我们将介绍该安全模型。
注2:正如我们在第四部分所见，如果是密码学货币，匿名参与方就有可能锁定保证金，并通过某种机制在无需确认任何人的身份的情况下，惩罚失信行为者。这实际上就是权益证明。然而，密码学货币离不开共识，因此“如果是密码学货币”这个前提导致我们在这里无法使用权益证明，否则就会陷入循环推理。我们会在下一部分解决这个问题。
为DMMS定义安全性
就DMMS而言，所有参与方都是平等的；无法通过让“敌手”仅拥有不完全知识来获得安全性。因此，我们使用以下三部分定义了DMMS。这些部分都不同于传统签名的密钥生成算法：
使用代价函数c来追踪算法的执行并输出“代价”t∈?，其中?是某个“代价域”。该函数必须是线性的，因为连续运行两个算法的成本是它们各自成本的总和。
随机化算法AttemptSign将消息m作为输入，输入签名σ。输入任何消息m，该算法的代价都应该是1。
确定性算法Verify将消息m、签名σ和目标代价T作为输入，输出0或1。
当且仅当Verify(m,T,AttempSign(m))=1对所有属于?的T都有1/T的概率成立，则我们说该DMMS是正确的，这个概率是由AtemptSign算法来保证的；当且仅当任意多项式算法?实现Verify(m,T,A(m))=1的概率都不超过1?(1?1/T)t，则我们说这样的DMMS是安全的。
换言之，安全的DMMS指的是没有比重复执行AttemptSign更好的签名算法。
我们简要论证了我们的安全性定义。为了实现动态成员集合，我们不能让参与成本过于昂贵，也不能让已有签名者通过显而易见的手段或经济因素排斥新加入的签名者。这就意味着，签名过程应该是“可分割的”，既不需要也不激励签名者之间进行任何通信。也就是说，花两倍长的时间运行一个签名算法应该与在同样的两个硬件上并行运行该签名算法的成功概率一样高。在极端情况下，这意味着最好的签名算法应该由对单一基础步骤的重复、独立执行来组成，这是由定义推导出来的。
挖矿机制作为一种DMMS
比特币挖矿采用的是基于哈希函数的工作量证明算法hashcash。这是一种使用随机数神谕模型的DMMS。作为一种计算模型，随机神谕是指，该模型把哈希函数当成一个“随机数神谕”，或者说真随机函数?3，其输出都是纯然随机的，而且只有通过该函数才能计算出来。
虽然随机数神谕模型的使用引起了很多争议，但是有力的实证证据证实了它可以用来保障安全性。下文中，H指的是输入可多达256位的哈希函数，它被当成是一个随机数神谕。
比特币的DMMS如下：
代价函数给出执行中调用随机数神谕的次数。
AttemptSign将消息m作为输入，并输出随机数σ∈{0,1}?256。
Verify将签名σ、消息m和目标T作为输入。仅当H(m||σ)<2256/T时，输出1。
不难看出，在随机数神谕模型中，没有比重复运行哈希函数更好的创建有效签名的方法。
注3：该模型是完全不现实的，因为真正的随机函数，from,say,512bitsto256bits，平均需要2512·256位来表示，已经超过了目前已知的表达极限。
没有世界时间
请注意，在上一部分，我们将哈希函数调用的数量作为我们的代价函数，它与计算次数大致成正比，而计算次数又与散热量大致成正比。最后，散热量与创建这些签名的经济和环境成本大致成正比。
一个显而易见的问题是，我们是否可以采用“成本更低”的代价函数？尤其是，为什么我们不能直接使用时钟时间？为什么我们使用DMMS对区块进行签名来创建区块链，而非直接按照时间顺序对交易进行排序来解决共识冲突？
答案是，分布式系统中缺少明确定义的时钟时间。网络延迟限制了信息的传播速度。根据狭义相对论可知，如果是几乎同时发生的事件，不同的观察者无法就其时间顺序达成共识。
如果只是这个问题，那么要求每笔交易之间间隔几秒钟即可。但是，实际情况会更加糟糕，原因有两点：
“网络延迟”在恶意环境中无法得到限制。攻击者或能使用拒绝服务攻击来任意降低系统速度，并通过其它方式对网络进行物理分区。
用相对论来说，这意味着无论将等待时间设为多久，都无法确保参与者不会与网络中的其他参与者类空分离。
新加入网络或最近离线的用户需要访问历史数据。但是，没有办法可以事后验证交易发生的顺序，因此在出现交易冲突的情况下，用户无法保证他们收到的交易是先发生的。
来自DMMS的共识
既然我们已经了解了DMMS，并解释了为什么比特币的hashcash是一个安全的算法，接着来思考如何通过DMMS实现分布式共识。
我们的主张是，通过DMMS实现分布式共识是有可能的。
我们首先需要通过我们的代价函数来衡量某种无法一次为多个消息创建签名的稀缺资源，和创建签名所需的平均时间。
以比特币为例，我们的代价函数的定义是“哈希函数调用的次数”。我们主张，该函数实际上用来衡量计算签名所需消耗的能源，并且得到了Landauerlimit的论证。从物理学上来说，所谓的能源，就是任意不可逆的位操作所需消耗的最低热量。通过计算sha256计算中涉及的不可逆位操作的数量，我们可以为创建一个比特币DMMS所需消耗的能源量设定下限。
代价函数也可以用来衡量创建签名所需的时间，因为每单位时间只能消耗一定量的能源，除非你去制造黑洞。当然了，在现实生活中，比特币矿工不会在接近黑洞极限的情况下操作，而且所需时间取决于挖矿硬件的速度。随着挖矿硬件的改进，以及同时在线的硬件数量增多，创建DMMS所需的时间减少。在比特币中，目标代价会根据这一情况进行调整，将创建每个签名所需的时间保持在10分钟左右?4。
注4：鉴于3.4中提到的无世界时间，读者可能会想知道如何准确调整时间。实际上，时间戳是由矿工插入区块的，而且确实没有任何方法可以防止矿工弄虚作假。比特币可以抵御不实时间戳导致的较小目标偏离，并且也禁止了目标过快地发生变化。因此，想要制造大幅的目标偏离是非常昂贵的，而且有可能遭到不配合的矿工的阻挠。关于更多讨论，请参阅。
那么，有了一个可以通过代价函数来衡量稀缺资源的安全DMMS，我们该如何获得共识历史？首先，我们假设网络是同步的，因此参与者可以在一定时间λ内获得所有有效数据。我们将交易历史分割成一系列区块，其中每个区块都包含一系列交易，以及前一个区块的密码学承诺?5。每个有效区块必须拥有一个已经设定好目标的DMMS，且目标使得创建区块所需的时间比λ长的多。需要明确的是，每个DMMS的目标代价是由系统规则定义的，不由矿工决定。
注5：承诺是一种密码学对象，由某个秘密数据计算得出，但是不会泄漏该数据，因此该数据在事后无法修改。抗碰撞哈希函数就是一例：给定数据x，你可以先发布H(x)，之后再公开x。验证者可以使用公开的值计算H(x)，来确认这个值是否与原始值相同。
网络参与者的运作方式是：首先考虑以同一个创世块开头的所有有效区块分支。然后计算每个区块上的DMMS的目标成本总和得出每条区块分支的重量。最重的区块分支会被视为“真实的”历史。
在创建区块时，矿工根据自己的意愿选择交易，并加入一个特殊的“奖励交易”用来将其它交易的费用以及网络定义的补贴分配给自己，再加上最新区块的承诺，然后计算DMMS。如果另一名矿工创建并发布了一个区块，矿工就会相应地更新他们的“真实历史上的最新区块”，并在自己所挖的区块中改变承诺以适配这种变化。计算出一个DMMS之后，他们会把这个完成的区块公布到网络中。
我们主张这样就能形成一个共识的历史，是说整个网络会渐进地对到底哪些区块是真实历史的一部分达成共识，而且不一致只会发生在最近的历史中。具体的论述可见Miller和LaViolaJr.，但我们这里附上一个不那么正式的论证。
因为网络是同步的，区块传输的时间大大短于区块生产的时间，所以所有参与者都能迅速认识到最重的历史。
我们还进一步认为，网络中的大部分参与者都会参与生产能延伸真实历史的DMMS。一个优雅且正确的理由是由VitalikButerin提出的：因为“奖励交易”当且仅当其区块属于真实历史才会被大家接受，所以对每一个矿工来说，纳什均衡就是服从绝大多数?6。
注6：也是在同一篇文章里，Buterin说：“要是你已经厌烦了PoS的反对者老是跟你引用AndrewPoelstra写的这篇文章，请尽情链上本文，作为还击。”不太清楚他这么说是什么意思；自始至终，无论在哪儿，他都没能驳倒本文的主张：除了消耗一种系统外的资源，没有别的产生共识的办法。
要想改变“真实历史”，攻击者必须产生另一个权重更大的历史。他具有的资源比正在延伸真实历史的矿工团体要少，因为那个矿工团体才是多数。所以，他在网络中能胜出的概率是小于1的，而且，要想让自己的历史超过真实历史，他还必须胜出N次以上。如果胜出一次的概率是P<1，那他胜出N次的概率就是PN，N足够大这个概率就小到可以忽略不计了。
原文链接:
https://download.wpsoftware.net/bitcoin/pos.pdf
作者:?AndrewPoelstra
翻译&校对:?闵敏&阿剑
科普|分布式共识的工作原理，Part-1：分布式系统的定义及属性
观点|剖析工作量证明
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。