加密经济学: 区块链技术前景之路基 & 论坛 & EthFans | 以太坊爱好者
加密经济学: 区块链技术前景之路基
1888 次阅读
如果你不能乐在其中，那就没有意义了。——“约翰·纳什”，《美丽心灵》（2001）
浏览现下的关于区块链的文章，你将看到关于其应用的有益的讨论，以及，关于某些人最喜爱的加密货币的未来价格走势的无穷无尽的争论。但在所有这些主题中，人们仍然很少提及居于这场运动核心的最迷人的概念——区块链作为一样新奇事物，意味着以物质激励我们所期望的人类行为。
从许多方面来说，区块链技术的神奇之处在于，它使我们可以在荒漠上种庄稼、在狐狸洞里养鸡。伴随对密码学的使用，区块链概念允许我们可靠地证明，历史上什么交易真实地发生了。通过将博弈论和经济学组合进区块链协议的设计中，该系统激励了稳定性，并让这一公共利益走向未来。这一切，居然可以发生在遍布黑客、骗子、盗版和暴民的匿名且敌视的电子世界里！
这就是加密经济学（cryptoeconomics），一个新鲜到运行拼写检查时你需要点选“添加到词典”的术语。如果你对潜藏于区块链技术及其具体系统之下的这一概念探究得足够仔细，你会发现，他们都大量包含了加密经济学的工具。这些工具本是特地设计出来以最小化恶意行为者的影响的。
虽然加密经济学有许多的定义，这些定义相互之间都有细微的不同，为了本文的目的，我将我们的讨论建立在上。
加密经济学综合自密码学、计算机网络和博弈论（它为安全体系提供一些经济激励/反激励集合的展示）。
在这篇文章中，我将讨论这些经济激励（因为他们与区块链相关），发掘加密经济学背后的一些安全性假设，然后描述以太坊平台的新版本，Caspe“小精灵”协议，是如何伴随着对这些观念的深入考虑而设计出来的。
激励与拜占庭容错机制
激励乃是博弈论和经济学在塑造朝向共同利益的人类行为时候的一个核心组成部分。虽然密码学，或者说，为了有效地创造一个可验证的历史而对链上的区块进行的加密与解密，是被普遍接受的，我们之间仍然存在一些分歧与争论，在谈到“为了创造成功的加密货币或平台，激励系统是否真是必要的”的时候。
不简要地讨论支撑去中心化数字经济的问题，即拜占庭将军问题，的话，我们就没法继续下去了。
光荣的拜占庭军队被包围了，并且被围困有一个城堡里。将军们控制着这支军队的不同部分，他们意识到，他们需要决定共同进攻，或者共同撤退；但在物理上，他们却是相互隔离的。重要的是大多数人都同意此种或彼种策略，因为错失时机或者半心半意的攻击对拜占庭人来说将意味着重大伤亡或者一个更为糟糕的结果。
不幸的是，拜占庭军队中，卖国将领的数量是不确定的，他们最想要的就是这场战争悲惨地结束。他们可能给不同的将军发送相互矛盾的信息，企图破坏大家的努力。而且，因为信息必须通过传信官来传达，不可能去断定这些信息是伪造的还是可信的。
所谓的核心问题就在这里：在一个一致意见具有绝对必要性的系统里，如何能够在缺乏信任机制的情况下，通过一个可信的过程，将一个一致意见传达给所有人？换句话来说，这些将军如何能够战胜藏在他们中间的叛徒，形成一个一致的、多数的意见？
在计算机科学里，一个系统的从错误组件（即阻碍其他重要组件形成必要共识的组件）中避免错误的能力，被称为拜占庭容错机制（BFT）。那么，它跟区块链和围绕激励的讨论有什么样的关联呢？
在一个加密货币，比如比特币（Bitcoin），中，如果缺乏一个可以实现BFT的协议，又没有一个中心化的权威，我们就将完全陷入黑暗。就像那些将军，比特币的节点（分享和扩大该区块链的计算机）需要知道哪些交易是有效的。打个比方，就像那些卖国的将军和他们可疑的信息，人们也可以花了比特币却简单地告诉其他节点他们没有花。去中心化的数字货币的关键问题是：没人知道可以相信谁、可以相信什么。
比特币对拜占庭将军问题的应答是位于区块链顶层的工作量证明（PoW）协议。正如你会发现大量关于PoW的讨论和，这一协议背后的一般理念是：让操纵投票变得尽可能困难，出于所需资源（时间，电力以及处理能力）的大量付出。要记录一场投票，每个“将军”都必须完成一个非常复杂的数学问题，该问题会在一瞬间被分享给其他人，待它被解决后，这些人又必须解决另一个复杂的问题。“工作”的链条将创造一个坚固的交易记录，同时，让攻击者们的操纵变得过分昂贵且费时。
激励在此时加入进来，以鼓励参与者们维护该协议——比特币“矿工”，也就是记录那些交易的人，在每一次他们使用他们的计算机算力并且成功地将已验证的交易提交到区块链的时候，都会被奖以12.5个比特币和交易费用作为激励。通过这种方式，他们因向比特币履行了一项关键服务、传播写满了有效且被验证过的交易的区块链而受到奖励。
在以太坊平台上，人们提议的权益证明（PoS）协议走得更远，它使用惩罚来反激励恶意行为。在PoS中，为了参与该系统，验证者们必须缴纳一大笔以太币保证金，作为电力和算力的替代。当验证者们不为该系统的利益采取行动时，他们就冒着失去他们全部权益，或者说保证金，的风险。
那么，加入激励机制有任何缺点吗？因为加密空间里的两个主要角色的协议都对加密经济学表现出强烈的关注，看起来精心设计的激励系统对于区块链技术的成功来说是关键的了。但MIT的教授Silvio Micali，一个密码学世界里的核心权威，并不同意这一点。
正如所报道的，Micali认为，激励应被当作最后手段来使用，因为它们可以导致许多负面的外部性；他还举比特币作为例子。在比特币工作量证明系统中的激励，导致了“工业化规模的矿池”，比特币矿工们将他们的资源聚集在一起然后分享奖励。下图可看出这些矿池的主导地位：
激励变得扭曲？，2017年7月
这些体量巨大的矿池的出现，以及随之而来被分配给它们背后的组织的权力，真切地开始冲击比特币作为一个去中心化的加密货币的理念，同时提高了51%攻击（我们稍后将讨论它）的可能性。简而言之，如果这一趋势持续下去，我们将到达这样一种境地：新比特币的发行将几乎完全由最大的矿工主导。
Micali转而建议，一个更少激励机制的公有区块链，它通过一个随机过程在每一轮中交换将军，借此解决拜占庭将军问题。我将不会在这里讨论该机制的细节，但这一方法避免了工作量证明需要的计算资源的数量，结果产生了更快速的交易。
这些不同的方法，围绕着那个有趣的哲学问题，即：“总体来说，人是被他们的利他主义还是一己私利主导的”，而被反复考虑。Micali的的支持者指出，在Bittorrent和其它分散式的计算机项目比如上长期驻留的无私奉献者证明了我们并不总是需要激励来促进利他行为。同时，以太坊基金会（Ethereum Foundation）的Vitalik Buterin和Vlad Zamfir坚定地站在相反立场上，他们认定：没有激励与惩罚，人们在最好的时候就是无动于衷（为什么要做记录呢？），在最坏的时候是穷凶极恶。
尽管大部分区块链运动都拥抱了激励和加密经济学的理念，Micali的系统肯定是可行的，而它的变体也许会在与现有的区块链平行的道路上生根发芽。
你是否需要激励，这是一个开放性的问题；而且我不认为它可以在一个学术模型中得到解决。实际上它正通过证据得到解答。你大可开发出一些东西，静观其变。
——Charles Hoskinson，以太坊前CEO
尽管比特币的工作量证明机制不是完美的，事实证明，它所建基的范式转换和加密经济学原理（密码学保护过去，经济学保证未来）已然导致了其将近十年的生存与应用。
关于行为的加密经济学假设
加密经济学的现状是：其术语和理论正被区块链的开发者们和思想领袖们日复一日地加以倡导。要强调这个领域内的前沿创新，在写作这篇文章的时候，某些联系着加密经济学的术语的谷歌搜索结果还不到100条！虽然这一领域中的许多观念都是非常理论化的，其余的部分却保证了它们的应用会在区块链技术的发展和应用中取得惊人的成果。
也就是说，加密经济学关心的是设计强悍的协议，主导去中心化的P2P系统和数字经济。换句话来说，加密经济学的概念和技术应被用于塑造导向合意结果的行为。
今天，作为中本聪（Satoshi Nakamoto）的创新的结果，比特币在一个工作量证明激励系统上运行，而该系统几乎既解决了拜占庭将军问题，又鼓励了人们维护该系统的努力。但是，因为Micali指出的负面外部性，比如倒向具有可观影响力的中心化矿池，工作量证明协议不能被认为是有效率的，在加密经济学的意义上。虽然Micali以此为证据指出激励系统完全是有害的，加密经济学的支持却转而主张：激励或者惩罚走得还不够远、还没有被最优地运用。
所以，我们应该通过何种镜头来评估一个协议呢？以太坊基金会的开发者们在他们的分析中使用下列安全模型。这些针对参与者行为所作的假设便是协议设计的基础。
诚实的大多数模型——传统的容错假设，即51%乃至更多的参与者在根本上是诚实的，是“好人”。在加密经济学社区，这一模型在很大程度上是不受欢迎的，经常被认为是在匿名、去中心化的图景中的一厢情愿。
相反，在加密经济学研究中，我们岂止是愤世嫉俗。我们执着于有关攻击者的假设——即他们是如何协作的，为了发动攻击他们必须投入的预算，以及攻击导致的实际成本。
协调选择模型——假设所有的协议参与者都被同一个联合或者代理统一起来了。
在这里，最大的比特币矿池就是一个好例子。因为大多数比特币算力都被控制在一小部分人手中，串谋是一个非常现实且具有威胁性的方案。随着矿池的增大，一个51%攻击，也就是一个机构（或者串谋的代理们）可以通过控制超过一半的挖矿算力来操控比特币区块链，在现实中是完全可行的。
虽然代理不能够重写以往的交易、从人们的钱包里面偷币，或者制造大灾变作为报复，他/她还是能够阻碍其他矿工上传交易到区块，以及“双花”使用所有链的比特币。总的来说，这种威胁看起来暗示了行动者自己的弄巧成拙——这样一种勾结的或巨大的努力将只会使整个比特币贬值，因为参与者们将对这个系统失去信心，并且在这段时间里拒绝确认交易。
罕见瞬间：90%的比特币挖矿算力齐聚一堂
不协调选择模型——假设所有协议参与者都不彼此合作，他们小于一个特定规模，且各怀目的。
这是藏在“去样一个假设之上：宇宙中遍布弱小的、自利的并且无意或者无法相互合作的参与者。
贿赂攻击者模型——该假设建立在不协调选择模型之上，但也假设存在一个拥有足够资源、通过有条件的贿赂来激励其他参与者采取特定行动的攻击者。
这一模型已经在Vitalik以及提出的SchellingCoin案例中得到详尽的描述。为了增加一点趣味性，我将提供一个短小精悍的例子：
让我们假设，在不协调选择模型的宇宙中，存在一个王座争夺游戏。游戏的参与者们将对他们
想坐上钢铁王座还是泡沫王座投票。每一个投票给多数方的人都将赢得100美元，而少数方的所有人将什么也得不到。
在这个游戏中，假设你将投票坐上钢铁王座，因为你想统治七大王国，也因为坐在泡沫王座上实在不讲究。你相信大多数人会因为同样的理由做出同样的选择。因为其他每个人都得出了跟你一样的结论，多数票将投给坐在钢铁王座上，每个人都能拿到100美元。
但是，让我们假设，有个恶意的泡沫经理人试图推销他的不可降解的器皿。经过一番狡猾的算计，他向每个人都发送了一份有条件的要约：“投票给泡沫一方，如果你变成了少数方，我将私下给你110美元！”因为他有一段长期还债的历史，每个人都知道他看重这一承诺，也有财力来支付它。
如图所示，你的收益取决于王座游戏中其他人采取的行动
突然，均衡点就转移了。现在，你投票给泡沫王座就有意义了——如果你是多数方，你拿到100美元；如果你在少数方，你将揣着110美元回家。因为其他每个人再一次得出了与你相同的结论，多数人将投票给泡沫，而那个经理人将允许自己大笑三声，全数不用支付还以零成本达成了他的目标。实际上，他那慷慨的威胁才是他的杀手锏。
这种形式，便是我们所知的攻击，比特币协议就对被这种策略很敏感！将钢铁王座替换成主区块链，泡沫王座替换成攻击者的链，你应该可以看到其弱点——一个恶意行为者激励其他矿工中的大多数接受一个变异的链。尽管如此，因为一个攻击者为了发动攻击必须有能力可靠地展示大量的预算，比特币的工作量证明还是无视这一缺陷，坚持了下来。
以太坊的权益证明机制：下一个实验
我希望你深刻地意识到，区块链技术的发展受到这些安全模型的意涵的驱动。正如控制者团队（）的写的那样，“加密经济学是这整场运动的基本催化剂”。
要评估设计协议的缓解这些安全模型中现存的和理论上的缺陷的能力，开发者们使用这两个概念：
第一个，加密经济学安全边际，衡量那些违反一个协议保证所带来的结果（以损失的美元计）。理论上来说，因为攻击者可以0成本发动P + epsilon攻击，只要他/她有那个预算，比特币的工作量证明系统可以说只有0的加密经济学安全边际！
加密经济学证明在某种程度上也是相似的；这是一份来自网络中某参与者的保证或者信息，断言某物为真。若在某个事件中证明它并不为真，该参与者就将失去一定数量的金钱。
让我们来检验一下今时今日区块链技术领域最具雄心的项目——即将到来的以太坊，它尝试通过将平台从工作量证明调整为权益证明来直捣黄龙。一场关于Casper的权益证明（PoS）机制的复杂之处的讨论将超出这篇文章的范围，但简而言之，权益证明尝试提供一个非常巨大的加密经济学安全边际，通过强制要求大笔的以太坊安全保证金，代替计算机算力，以实现验证者的功能。这一安全保证金，或说加密经济学证明，成了一个强有力的威慑。其含义是一目了然的——制造麻烦，你就将失去一切！
Casper强制参与者加入一个谢林币（SchellingCoin）游戏（如我们的钢铁-泡沫王座例子概述的那样）。参与者们被强制要求将他们的安全保证金押在多数人将下注的事情上。使用同样的（我们在钢铁王座游戏中用到的）递归逻辑，多数参与者将准确地投票给有效的交易，因为每个参与者都预期其他人得出同样的结论。情形就是如此，权益证明可以抵抗P + epsilon攻击，因为在他们最终将投票给少数方的情形中，攻击者将不得不可信地展示巨额的预算以补贴参与者的安全保证金。
在这些安全模型的环境下，我们可以看出Casper的弹性集中在不协调选择模型中，且源自贿赂攻击者。Casper在理论上同样对起源于合作攻击者模型的51%攻击敏感。但是，就像比特币，以太坊将做出如此攻击的成本提高到如此高昂的地步，以至于几乎完全地遏制了它。在Casper的环境下，失去所有相关权益的威胁是一个更强有力的震慑。要获取更多关于Casper进展的信息，请经常查看的。
虽然Casper的许多元素是高度理论化的，权益证明协议自身也激起了关于公平份额的辩论，但有证据表明：这一转变几乎完全在加密经济学的意料之中，也意味着解决了工作量证明系统的许多不足。缓慢但坚定地，区块链空间里的思考者们在我们对去中心化数字经济中最优协议设计的认识上进一步覆地翻天。
一些针对整个区块链技术的批评者们对这样一种理念感到很不自在：今天，太多攻击途径仅在理论上是可行的。我认为这样一种想法没什么意思：只要有足够的金钱和时间，一个攻击者将总是能够破坏任何系统。在最坏的情况下，加密经济学也如坚实壁垒般伫立，努力让这些攻击变得尽可能昂贵、困难而且不可取。
因为我们将走向一个的智能合约时代，这一领域必将变得更加复杂而激动人心。
我希望这篇文章给你一些对生机勃勃、丰饶多姿的加密经济学领域的了解。作为结束，我这里已没有什么资源了，所以我想分享一些对我来说受益匪浅的链接。
，著——本文的灵感来源之一。他也有一些很棒的链接。
，著——关于如何进入这个主题的有趣文章。
（视频）——高手直接布道。Vitalik Buterin舌灿莲花。
——论加密经济学与人工智能研究交叉的文章。
——近来以太坊要解决的问题的候选名单。包含了一些关于加密经济学的有益讨论。
：有关Buterin写作的，但自身也是关于博弈论的优秀读物。
——一本老的但是绝佳的关于博弈论的书。作者是托马斯·谢林，核战略的理论大师（我可是认真的！）。
作者: Kyle Wang
翻译&校对: 阿剑 & Elisa
暂无回复。
后方可回复
如果你还没有账号请点击这里区块链核心技术：拜占庭共识算法之PBFT - 简书
区块链核心技术：拜占庭共识算法之PBFT
PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。该算法是Miguel Castro (卡斯特罗)和Barbara Liskov（利斯科夫）在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。该论文发表在1999年的操作系统设计与实现国际会议上（OSDI99）。没错，这个Loskov就是提出著名的里氏替换原则（LSP）的人，2008年图灵奖得主。
OSDI99这篇论文描述了一种副本复制（replication）算法解决拜占庭容错问题。作者认为拜占庭容错算法将会变得更加重要，因为恶意攻击和软件错误的发生将会越来越多，并且导致失效的节点产生任意行为。（拜占庭节点的任意行为有可能误导其他副本节点产生更大的危害，而不仅仅是宕机失去响应。）而早期的拜占庭容错算法或者基于同步系统的假设，或者由于性能太低而不能在实际系统中运作。这篇论文中描述的算法是实用的，因为该算法可以工作在异步环境中，并且通过优化在早期算法的基础上把响应性能提升了一个数量级以上。作者使用这个算法实现了拜占庭容错的网络文件系统（NFS），性能测试证明了该系统仅比无副本复制的标准NFS慢了3%。
1.概要介绍
第一段大片废话就是说明拜占庭算法越来越重要了，然后说这篇论文提出解决拜占庭容错的状态机副本复制（state machine replication）算法。这个算法在保证活性和安全性（liveness & safety）的前提下提供了(n-1)/3的容错性。从Lamport教授在1982年提出拜占庭问题开始，已经有一大堆算法去解决拜占庭容错了。但是一句话概括：这些算法都是狗屎！PBFT算法跟这些妖艳贱货完全不同，在只读操作中只使用1次消息往返（message round trip），在只写操作中只使用2次消息往返，并且在正常操作中使用了消息验证编码（Message Authentication Code,简称MAC），而造成妖艳贱货性能低下的公钥加密（public-key cryptography）只在发生失效的情况下使用。作者不仅提出算法，而且使用这个算法实现了一个牛逼的系统（拜占庭容错的NFS），反正性能杠杠的。作者先炫耀一下这边论文的贡献亮瞎你们的狗眼：
1）首次提出在异步网络环境下使用状态机副本复制协议2）使用多种优化使性能显著提升3）实现了一种拜占庭容错的分布式文件系统4）为副本复制的性能损耗提供试验数据支持
2.系统模型
这部分主要对节点行为和网络环境进行剧情设定，然后赋予了消息的加密属性，最后对大魔王的能力进行设定。
系统假设为异步分布式的，通过网络传输的消息可能丢失、延迟、重复或者乱序。作者假设节点的失效必须是独立发生的，也就是说代码、操作系统和管理员密码这些东西在各个节点上是不一样的。（那么如果节点失效不独立发生，PBFT算法就失效了吗？）
作者使用了加密技术来防止欺骗攻击和重播攻击，以及检测被破坏的消息。消息包含了公钥签名（其实就是RSA算法）、消息验证编码（MAC）和无碰撞哈希函数生成的消息摘要（message digest）。使用m表示消息，mi表示由节点i签名的消息，D(m)表示消息m的摘要。按照惯例，只对消息的摘要签名，并且附在消息文本的后面。并且假设所有的节点都知道其他节点的公钥以进行签名验证。
系统允许大魔王可以操纵多个失效节点、延迟通讯、甚至延迟正确节点来毁灭世界。但是作者限定大魔王不能无限期地延迟正确的节点，并且大魔王算力有限不能破解加密算法。例如，大魔王不能伪造正确节点的有效签名，不能从摘要数据反向计算出消息内容，或者找到两个有同样摘要的消息。
3.服务属性
这部分描述了副本复制服务的特性
论文算法实现的是一个具有确定性的副本复制服务，这个服务包括了一个状态（state）和多个操作（operations）。这些操作不仅能够进行简单读写，而且能够基于状态和操作参数进行任意确定性的计算。客户端向副本复制服务发起请求来执行操作，并且阻塞以等待回复。副本复制服务由n个节点组成。
针对安全性
算法在失效节点数量不超过（n-1)/3的情况下同时保证安全性和活性（safety & liveness）。安全性是指副本复制服务满足线性一致性（linearizability）,就像中心化系统一样原子化执行操作。安全性要求失效副本的数量不超过上限，但是对客户端失效的数量和是否与副本串谋不做限制。系统通过访问控制来限制失效客户端可能造成的破坏，审核客户端并阻止客户端发起无权执行的操作。同时，服务可以提供操作来改变一个客户端的访问权限。因为算法保证了权限撤销操作可以被所有客户端观察到，这种方法可以提供强大的机制从失效的客户端攻击中恢复。
算法不依赖同步提供安全性，因此必须依靠同步提供活性。否则，这个算法就可以被用来在异步系统中实现共识，而这是不可能的（由Fischer1985的论文证明）。本文的算法保证活性，即所有客户端最终都会收到针对他们请求的回复，只要失效副本的数量不超过（n-1)/3，并且延迟delay(t)不会无限增长。这个delay(t)表示t时刻发出的消息到它被目标最终接收的时间间隔，假设发送者持续重传直到消息被接收。这时一个相当弱的同步假设，因为在真实系统中网络失效最终都会被修复。但是这就规避了Fischer1985提出的异步系统无法达成共识的问题。
下面这段话是关键
本文的算法弹性是达到最优的：当存在f个失效节点时必须保证存在至少3f+1个副本数量，这样才能保证在异步系统中提供安全性和活性。这么多数量的副本是需要的，因为在同n-f个节点通讯后系统必须做出正确判断，由于f个副本有可能失效而不发回响应。但是，有可能f个没有失效的副本不发回响应（是因为网络延迟吗？），因此f个发回响应的副本有可能是失效的。尽管如此，系统仍旧需要足够数量非失效节点的响应，并且这些非失效节点的响应数量必须超过失效节点的响应数量，即n-2f&f，因此得到n&3f。
算法不能解决信息保密的问题，失效的副本有可能将信息泄露给攻击者。在一般情况下不可能提供信息保密，因为服务操作需要使用参数和服务状态处理任意的计算，所有的副本都需要这些信息来有效执行操作。当然，还是有可能在存在恶意副本的情况下通过秘密分享模式（secret sharing scheme）来实现私密性，因为参数和部分状态对服务操作来说是不可见的。
PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示，使用0到|R|-1的整数表示每一个副本。为了描述方便，假设|R|=3f+1，这里f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本，但是额外的副本除了降低性能之外不能提高可靠性。
PBFT的剧情缓缓展开，首先介绍舞台（view）、演员（replica）和角色（primary、backups）
所有的副本在一个被称为视图（View）的轮换过程（succession of configuration）中运作。在某个视图中，一个副本作为主节点（primary），其他的副本作为备份（backups）。视图是连续编号的整数。主节点由公式p = v mod |R|计算得到，这里v是视图编号，p是副本编号，|R|是副本集合的个数。当主节点失效的时候就需要启动视图更换（view change）过程。Viewstamped Replication算法和Paxos算法就是使用类似方法解决良性容错的。
PBFT算法的狗血剧情如下：1.客户端向主节点发送请求调用服务操作2.主节点通过广播将请求发送给其他副本3.所有副本都执行请求并将结果发回客户端4.客户端需要等待f+1个不同副本节点发回相同的结果，作为整个操作的最终结果。
同所有的状态机副本复制技术一样，PBFT对每个副本节点提出了两个限定条件：（1）所有节点必须是确定性的。也就是说，在给定状态和参数相同的情况下，操作执行的结果必须相同；（2）所有节点必须从相同的状态开始执行。在这两个限定条件下，即使失效的副本节点存在，PBFT算法对所有非失效副本节点的请求执行总顺序达成一致，从而保证安全性。
接下去描述简化版本的PBFT算法，忽略磁盘空间不足和消息重传等细节内容。并且，本文假设消息验证过程是通过数字签名方法实现的，而不是更加高效的基于消息验证编码（MAC）的方法。
客户端c向主节点发送&REQUEST,o,t,c&请求执行状态机操作o，这里时间戳t用来保证客户端请求只会执行一次。客户端c发出请求的时间戳是全序排列的，后续发出的请求比早先发出的请求拥有更高的时间戳。例如，请求发起时的本地时钟值可以作为时间戳。
每个由副本节点发给客户端的消息都包含了当前的视图编号，使得客户端能够跟踪视图编号，从而进一步推算出当前主节点的编号。客户端通过点对点消息向它自己认为的主节点发送请求，然后主节点自动将该请求向所有备份节点进行广播。
副本发给客户端的响应为&REPLY,v,t,c,i,r&，v是视图编号，t是时间戳，i是副本的编号，r是请求执行的结果。
客户端等待f+1个从不同副本得到的同样响应，同样响应需要保证签名正确，并且具有同样的时间戳t和执行结果r。这样客户端才能把r作为正确的执行结果，因为失效的副本节点不超过f个，所以f+1个副本的一致响应必定能够保证结果是正确有效的。
如果客户端没有在有限时间内收到回复，请求将向所有副本节点进行广播。如果请求已经在副本节点处理过了，副本就向客户端重发一遍执行结果。如果请求没有在副本节点处理过，该副本节点将把请求转发给主节点。如果主节点没有将该请求进行广播，那么就有认为主节点失效，如果有足够多的副本节点认为主节点失效，则会触发一次视图变更。
本文假设客户端会等待上一个请求完成才会发起下一个请求，但是只要能够保证请求顺序，可以允许请求是异步的。
4.2 PBFT算法主线流程（正常情况）
每个副本节点的状态都包含了服务的整体状态，副本节点上的消息日志(message log)包含了该副本节点接受(accepted)的消息，并且使用一个整数表示副本节点的当前视图编号。
事件的导火索
当主节点p收到客户端的请求m，主节点将该请求向所有副本节点进行广播，由此一场轰轰烈烈的三阶段协议（three-phase protocol）拉开了序幕。在这里，至于什么消息过多需要缓存的情况我们就不管了，这不是重点。
三个阶段的任务
我们重点讨论预准备（pre-prepare）、准备(prepare)和确认(commit)这三个历史性阶段。预准备和准备两个阶段用来确保同一个视图中请求发送的时序性（即使对请求进行排序的主节点失效了），准备和确认两个阶段用来确保在不同的视图之间的确认请求是严格排序的。
预准备阶段
在预准备阶段，主节点分配一个序列号n给收到的请求，然后向所有备份节点群发预准备消息，预准备消息的格式为&&PRE-PREPARE,v,n,d&,m&，这里v是视图编号，m是客户端发送的请求消息，d是请求消息m的摘要。
请求本身是不包含在预准备的消息里面的，这样就能使预准备消息足够小，因为预准备消息的目的是作为一种证明，确定该请求是在视图v中被赋予了序号n，从而在视图变更的过程中可以追索。另外一个层面，将“请求排序协议”和“请求传输协议”进行解耦，有利于对消息传输的效率进行深度优化。
备份节点对预准备消息的态度
只有满足以下条件，各个备份节点才会接受一个预准备消息：
请求和预准备消息的签名正确，并且d与m的摘要一致。
当前视图编号是v。
该备份节点从未在视图v中接受过序号为n但是摘要d不同的消息m。（许仙在这辈子从未见过名字叫白素贞的美貌女子）
预准备消息的序号n必须在水线（watermark）上下限h和H之间。
水线存在的意义在于防止一个失效节点使用一个很大的序号消耗序号空间。
进入准备阶段
如果备份节点i接受了预准备消息&&PRE-PREPARE,v,n,d&,m&，则进入准备阶段。在准备阶段的同时，该节点向所有副本节点发送准备消息&PREPARE,v,n,d,i&，并且将预准备消息和准备消息写入自己的消息日志。如果看预准备消息不顺眼，就什么都不做。
接受准备消息需要满足的条件
包括主节点在内的所有副本节点在收到准备消息之后，对消息的签名是否正确，视图编号是否一致，以及消息序号是否满足水线限制这三个条件进行验证，如果验证通过则把这个准备消息写入消息日志中。
准备阶段完成的标志
我们定义准备阶段完成的标志为副本节点i将(m,v,n,i)记入其消息日志，其中m是请求内容，预准备消息m在视图v中的编号n，以及2f个从不同副本节点收到的与预准备消息一致的准备消息。每个副本节点验证预准备和准备消息的一致性主要检查：视图编号v、消息序号n和摘要d。
预准备阶段和准备阶段确保所有正常节点对同一个视图中的请求序号达成一致。接下去是对这个结论的形式化证明：如果prepared(m,v,n,i)为真，则prepared(m',v,n,j)必不成立，这就意味着至少f+1个正常节点在视图v的预准备或者准备阶段发送了序号为n的消息m。
进入确认阶段
当(m,v,n,i)条件为真的时候，副本i将&COMMIT,v,n,D(m),i&向其他副本节点广播，于是就进入了确认阶段。每个副本接受确认消息的条件是：1）签名正确；2）消息的视图编号与节点的当前视图编号一致；3）消息的序号n满足水线条件，在h和H之间。一旦确认消息的接受条件满足了，则该副本节点将确认消息写入消息日志中。（补充：需要将针对某个请求的所有接受的消息写入日志，这个日志可以是在内存中的）。
接受确认消息需要满足的条件
我们定义确认完成committed(m,v,n)为真得条件为：任意f+1个正常副本节点集合中的所有副本i其prepared(m,v,n,i)为真；本地确认完成committed-local(m,v,n,i)为真的条件为：prepared(m,v,n,i)为真，并且i已经接受了2f+1个确认（包括自身在内）与预准备消息一致。确认与预准备消息一致的条件是具有相同的视图编号、消息序号和消息摘要。
确认被接受的形式化描述
确认阶段保证了以下这个不变式（invariant）：对某个正常节点i来说，如果committed-local(m,v,n,i)为真则committed(m,v,n)也为真。这个不变式和视图变更协议保证了所有正常节点对本地确认的请求的序号达成一致，即使这些请求在每个节点的确认处于不同的视图。更进一步地讲，这个不变式保证了任何正常节点的本地确认最终会确认f+1个更多的正常副本。
故事的终结
每个副本节点i在committed-local(m,v,n,i)为真之后执行m的请求，并且i的状态反映了所有编号小于n的请求依次顺序执行。这就确保了所有正常节点以同样的顺序执行所有请求，这样就保证了算法的正确性（safety）。在完成请求的操作之后，每个副本节点都向客户端发送回复。副本节点会把时间戳比已回复时间戳更小的请求丢弃，以保证请求只会被执行一次。
我们不依赖于消息的顺序传递，因此某个副本节点可能乱序确认请求。因为每个副本节点在请求执行之前已经将预准备、准备和确认这三个消息记录到了日志中，这样乱序就不成问题了。（为什么？）
下图展示了在没有发生主节点失效的情况下算法的正常执行流程，其中副本0是主节点，副本3是失效节点，而C是客户端。
PBFT算法流程
4.3 垃圾回收
为了节省内存，系统需要一种将日志中的无异议消息记录删除的机制。为了保证系统的安全性，副本节点在删除自己的消息日志前，需要确保至少f+1个正常副本节点执行了消息对应的请求，并且可以在视图变更时向其他副本节点证明。另外，如果一些副本节点错过部分消息，但是这些消息已经被所有正常副本节点删除了，这就需要通过传输部分或者全部服务状态实现该副本节点的同步。因此，副本节点同样需要证明状态的正确性。
在每一个操作执行后都生成这样的证明是非常消耗资源的。因此，证明过程只有在请求序号可以被某个常数（比如100）整除的时候才会周期性地进行。我们将这些请求执行后得到的状态称作检查点（checkpoint），并且将具有证明的检查点称作稳定检查点（stable checkpoint）。
副本节点保存了服务状态的多个逻辑拷贝，包括最新的稳定检查点，零个或者多个非稳定的检查点，以及一个当前状态。写时复制技术可以被用来减少存储额外状态拷贝的空间开销。
检查点的正确性证明的生成过程如下：当副本节点i生成一个检查点后，向其他副本节点广播检查点消息&CHECKPOINT,n,d,i&，这里n是最近一个影响状态的请求序号，d是状态的摘要。每个副本节点都默默地在各自的日志中收集并记录其他节点发过来的检查点消息，直到收到来自2f+1个不同副本节点的具有相同序号n和摘要d的检查点消息。这2f+1个消息就是这个检查点的正确性证明。
具有证明的检查点成为稳定检查点，然后副本节点就可以将所有序号小于等于n的预准备、准备和确认消息从日志中删除。同时也可以将之前的检查点和检查点消息一并删除。
检查点协议可以用来更新水线（watermark）的高低值（h和H），这两个高低值限定了可以被接受的消息。水线的低值h与最近稳定检查点的序列号相同，而水线的高值H=h+k，k需要足够大才能使副本不至于为了等待稳定检查点而停顿。加入检查点每100个请求产生一次，k的取值可以是200。
4.4 视图变更，改朝换代
使用计时器的超时机制触发视图变更事件
视图变更协议在主节点失效的时候仍然保证系统的活性。视图变更可以由超时触发，以防止备份节点无期限地等待请求的执行。备份节点等待一个请求，就是该节点接收到一个有效请求，但是还没有执行它。当备份节点接收到一个请求但是计时器还未运行，那么它就启动计时器；当它不再等待请求的执行就把计时器停止，但是当它等待其他请求执行的时候再次情动计时器。
浙江大学博士，趣链科技联合创始人，研究区块链的核心算法与技术实现。
欢迎浏览我的博客，希望里面的内容对你有所帮助。
邮件联系: blighli (a_t)