理解 Serenity - 第二部分: Casper

Original post by Vitalik Buterin, on December 28th, 2015

特别感谢Vlad Zamfir，他提出了按块达成共识这个想法，并且说服我认同它和Casper的其它一些核心想法的价值；以及Vlad Zamfir和Greg Meredith，为他们在这个协议上的持续努力。

在这个系列的上一篇中，我们讨论了Serenity的两大旗舰特性之一：深度抽象，它将给平台带来极大的灵活性，使以太坊从“比特币加图灵完备”向“通用去中心化的计算”迈进一大步。现在，让我们把注意力转向另一个主要特性，也是当初设立Serenity里程碑的原因：Casper权益证明算法。

投注共识

Casper向公开经济学共识这个领域引入了一个根本上全新的理念作为自己的基础：投注共识。投注共识的核心思想很简单：为验证人(validator)提供 与协议 对赌哪个块会被最终确定的机会。在这里对某个区块X的投注就是一笔交易，在 所有区块X被处理了的世界中 都会带给验证人Y个币的奖励（奖励是凭空“印”出来的，因而是“与协议”对赌），而在所有区块X没有被处理的世界中会对验证人收取Z个币的罚款（罚金被销毁）。

(译注：一个世界(world)在这里应理解为区块链未来的一种可能状态。)

只有在相信区块X在人们关心的那个世界中被处理的可能性足够大时，这才是值得去做的交易，验证人才会愿意投注。然而，接下来就是经济上递归的有趣部分：人们关心的那个世界，也就是用户的客户端在用户想要知道他们的账户余额或是合约的状态时所展现的那个状态， 本身就是根据人们对哪个区块投注最多推导出来的 。因此，每一个验证人都具有根据他们所预期的其他人的投注情况进行投注的动机，驱使这个过程走向收敛。

一个有帮助的类比是工作量证明共识 - 它本身看起来非常独特，实际上可以成为投注共识的一个特别子模型。理由如下：当你基于一个块挖矿时，你是在花费每秒 E 的电力成本换取每秒 p 的出块概率，并且在 所有包含你的出块的分叉中 获得 R 个币，在其它分叉中分文不得。

因此，每一秒钟，在你挖矿的链上你可以获得 p*R-E 的期望收益，在其它链上遭受 E 的损失；因此你的挖矿选择可以理解为下注赌你所在的链有 E:p*R-E 的相对概率(odds)胜出。比如，假设p等于百万分之一，R是25个币约等于10000美元，而E是0.007美元，则你在胜出链上每秒钟的期望收益是 0.000001 * 10000 - 0.007 = 0.003 ，你在失败链上的损失是 0.007 的电力成本，因此你是在赌自己挖矿的链有7:3的相对概率（或者说70%的概率）胜出。注意工作量证明满足上面所说的经济上递归的要求：用户的客户端通过处理拥有最大工作量的那条链来计算其账户余额。

投注共识可以看作是包含了以特定方式看待的工作量证明的一个框架，也适合为其他多种类型的共识协议提供能促进收敛的经济博弈。例如传统的 拜占庭容错 共识协议中，通常在对某个结果进行最后"commit"之前还有"pre-votes"和"pre-commits"的概念；在投注共识的模型下，我们可以把每一阶段都变成投注，这样后面阶段的参与者就有更大把握相信前面阶段的参与者“真的是这个意思”。

投注共识还可以用于激励链外人类共识(out-of-band human consensus)的正确行为，如果为了克服类似51%攻击的极端情况有需要的话。假设有人购买了一条PoS链上超过一半的币，并进行攻击，那么社区只需要协商出一个让客户端忽略攻击者分叉的补丁，就能自动让攻击者和他的小伙伴们失去他们所有的币。一个极有野心的目标是让在线节点可以自动的产生这种分叉决定 - 如果能成功实现，传统容错研究中的一个被低估但却重要的结论 - 在强同步假设下，即使几乎所有节点都在尝试攻击系统，剩下的节点 依然可以达成共识 - 也可以被纳入投注共识的框架中。

在投注共识的情境中，不同的共识协议只在一件事情上有区别：谁，可以以什么赔率，投多少注？工作量证明只提供了一种赌局：投注胜出链有 E:p*R-E 的相对概率包含你自己出的块。在广义的投注共识中，依据一种被称为 评分规则(scoring rule) 的机制我们本质上可以提供无限多种赌局：在1:1上压极小的一注，在1.000001:1上也压极小注，在1.000002:1上也压极小注，如此继续。

参与者依然可以选择在每一个概率等级上的这些极小边际投注的确切大小，但大体上这个技术让我们能打探出验证人认为某个块会被确认的相当精确的概率读数。如果验证人认为一个块有90%的概率会被确认，那么他们就会接受所有相对概率低于9:1的赌局，拒绝相对概率高于9:1的赌局，而协议就能基于这一点准确得出这个块会被确认的概率是90%的“看法”。事实上， 显示原理(revelation principle) 告诉我们可以要求验证人直接给出他们对某个块被确认概率的“看法”的签名消息，让协议代表验证人计算投注。

多亏了神奇的微积分，我们可以得到在每一个概率等级上计算总奖励和总惩罚的简单函数，计算结果在数学上等价于根据验证人信心在所有概率等级上形成的投注的无限集合的总和。一个简单的例子是 s(p) = p(1-p) 和 f(p) = (p/(1-p))^2/2 ，这里 s 计算如果你投注的事件发生能获得的奖励， f 计算如果没有发生你受到的惩罚。

投注共识的广义形式有一个重要优点。在工作量证明中，给定区块背后的“经济权重”仅仅随着时间线性增加：如果一个块有6个确认，那么要撤销它只需要花费矿工大约6倍于出块奖励（在均衡态下）的成本，而如果一个块有600个确认，那么撤销它的成本就是出块奖励的600倍。在广义的投注共识中，验证人在一个块上投入的经济权重可以指数级增加：如果其他大多数验证人愿意以10:1下注，你可能会想冒险以20:1下注；而一旦几乎所有人都增加到20:1，你可能会跳到40:1或者更高。因此，一个块很可能在几分钟之内，取决于验证人有多少勇气（以及协议提供的激励大小），就达到一种“准最终确定”的状态，这种状态下验证人的所有保证金都成为了支持这个块的投注。

在50000英尺的高度看：区块链是一个关于自身的预测市场。

区块，链，共识与拔河

Casper的另一个独特之处在于它的共识是 按块达成的(by-block) 而不是像工作量证明那样 按链达成的(by-chain) ：共识过程在某个高度上对区块状态的决策是独立于其它所有高度的。这个机制确实会导致一定程度的低效 - 特别是，一次投注必须表达验证人对于每一个高度上区块的意见，而不能仅是链的头部区块 - 但是在这个模型下为投注共识实现投注策略会十分简单，而且它还有个优点是对高速区块链友好：理论上，这个模型中的出块时间甚至可以比网络传播时间还要块，因为区块可以相互独立的被制造出来，虽然有个明显的附带条件，即区块的 最终确定 依然要一段时间。

在按链达成的共识中，我们可以把共识过程看作是正无穷和负无穷在每个分叉点进行的拔河游戏，每次分叉的“状态值”的含义是了右手边最长链的区块数减去左边最长链的区块数：

为了找出“正确的链”我们只需从起源块（genesis block）开始前进，在每一个分叉处，如果状态值是负数则往左边移动，反之向右边移动。这里的经济激励很明显：一旦状态值变正，则说明有很强的经济压力迫使它走向正无穷，尽管过程很缓慢。如果状态值变负，则有很强的经济压力迫使它走向负无穷。

顺便说一句，在这个框架下， GHOST评分规则 的核心思想变成了一种自然的范化：与其只通过最长链的长度来计算状态值，不如计算分叉单边所有块的数量：

在按块达成的共识中，同样有这个拔河游戏，不过此时“状态值”仅仅是通过协议的某些操作可以任意增加或者减少的数字。在每一个高度上，如果状态值为正，客户端就处理这个块，如果为负则不处理。注意虽然工作量证明当前是按链达成共识的，但并非必须如此：我们很容易可以想象一个协议，其中一个包含有效工作量证明的区块不引用父区块，而是给它自身历史上的所有区块投一张+1或者-1票。+1票只有在所投的区块被处理时才获得奖励，而-1票只在所投的区块没有被处理时才得到奖励：

不过，在工作量证明中这样的设计无法很好的工作，原因很简单：如果你需要对 每一个 历史高度进行投票，那么需要进行的投票数量会随着时间的平方增长，很快就能让系统宕机。而在投注共识中，由于拔河游戏可以以指数级速度收敛到最终确定，投票的开销要容易承受的多。

这个机制的一个反直觉结果是，一个块可以在其后的块都最终确定之后依然处于未确认的状态。这看起来像是一个很大的效率问题，因为如果其上有10个块的一个区块状态一直反复变化的话，每一次变动都会导致重新计算这10个块的状态转移，但其实在按链达成的共识中在链与链之间会发生完全相同的事情，而按块的共识实际上可以提供更多的信息给用户：如果他们的交易在第20101个块被确认和最终确定，而且他们知道不管第20100个块的内容是什么，这笔交易都有一个确定的结果，那么他们关心的这个结果就是已经最终确定的，即使结果前的部分历史还不是。按链达成的共识算法永远也不会有这个性质。

那么Casper到底是如何工作的？

在所有基于安全准备金的权益证明协议中，都有一群有担保的验证人，这个信息也记录在系统状态中。如果要投注或者进行某一种协议中的关键操作，你必须先加入这个群体，这样才能确保你的恶意行为会被处罚。加入和退出有担保的验证人都是特殊的交易类型，协议的关键操作例如投注同样也是一种交易类型。投注可以作为独立的对象在网络上被传输，也可以被打包进区块之中。

基于Serenity的抽象精神，所有的逻辑都通过一个 Casper合约 来实现，它提供投注，加入，取款和获取共识信息等一系列功能，因此通过简单的调用Casper合约我们就能提交投注或者进行其他操作。Casper合约的内部状态看起来是这个样子：

这个合约会记录当前的验证人集合，对于每位验证人记录6项主要数据：

• 验证人保证金的返还地址
• 当前验证人保证金的数量（注意验证人的投注会使这个值增加或减少）
• 验证人的 验证代码(validation code)
• 最近一次投注的序号
• 最近一次投注的hash
• 验证人的 意见 表

“验证代码”概念是Serenity的另一个抽象特性。其他的权益证明协议会要求验证人使用某一种特定的签名验证算法，而Serenity的Casper实现允许验证人定制一段代码，这段代码可以接受一个hash和一个签名做参数，返回0或者1，在投注被接受之前，代码就可以用签名来验证投注的hash正确无误。默认的验证代码是一个椭圆曲线签名验证算法，你可以试验其它的算法：多重签名，threshold signature（有发展成去中心化资金池的潜力！），Lamport signature（译注：可抵御量子计算机）等等。

每一次投注都必须包含一个比上一次投注大1的序号，而且每次投注必须包含上次投注的hash。因此，你可以把某位验证人的一系列投注看作是某种“私有链”；这样理解的话，验证人的意见实际上是这条链的状态。验证人意见是描述如下问题的一张表格：

• 在每一个高度，验证人认为哪个是最佳的状态树根节点
• 在每一个高度，验证人认为哪个是最佳的区块hash（如果还没有区块hash产生可以给0）
• 该hash对应的区块有多大概率被最终确定

一次投注是看起来如下的一个对象：

这里的关键信息是：

• 投注的序号
• 上次投注的hash
• 签名
• 意见更新组成的列表

Casper合约中处理投注的函数有三个部分。首先，它会验证投注的序号，上次投注的hash和投注签名。然后它会用投注中的新信息来更新验证人的意见表。一次投注通常只会有少数概率，区块hash和状态树根节点更新，因此意见表的大部分不会变化。最后，它会对意见表应用评分规则：如果你的意见是相信某个块有99%的机会被最终确定，并且，如果在该特定合约运行的特定世界中，这个块被最终确定了，你将会得到99分，否则你会失去4900分。

需要注意的是，由于Casper合约的这个函数是作为状态转移函数的一部分被执行的， 执行过程完全清楚之前的每一个区块和状态树根节点是什么 ，至少在它自己所在的世界中是这样。即使从外部世界来看，对第20125个块进行提议和投票的验证人不知道第20123个块是否会被最终确定，但是当验证人 处理到 那个块的时候他们就知道了 - 或者，他们可能两个世界都处理，然后在决定要跟随哪一个。为了防止验证人在不同的世界中提供不同的投注，我们还有一个简单严格的条款：如果你有两次投注序号一样，或者说你提交了一个无法让Casper合约处理的投注，你将失去所有保证金。

从验证人资金池取款需要两个步骤。首先，你需要提交一个最大高度为-1的投注；它会自动完结投注链，并且启动一个为期四个月的倒计时（在testnet上是20个块/100秒），这之后投注人才能通过调用另一个方法， withdraw ，来收回他的资金。任何人都可以触发取款，资金会被发送回之前发送 join 交易的那个地址。

区块提议

每个区块都包含 (i) 一个代表区块高度的数字， (ii) 提议人的地址，(iii) 交易树根节点hash和 (iv) 提议人签名。一个有效区块的提议人地址必须是协议安排在这个高度出块的验证人的地址，而签名则必须能通过该验证人的验证代码验证。高度为N的区块的提交时间由公式 T = G + N*5 确定，其中 G 是起源块的时间戳。因此，一般来说每5秒中会出现一个新块。

一个NXT风格的随机数发生器被用来决定在每个高度应该由谁来出块，不可避免的，缺失的出块人也会作为熵的一个来源。采取这个方案背后的原因是虽然这个熵是可操纵的，操纵的代价非常高：你必须放弃创建一个块能收取的交易费用收益。如果确实有必要，我们也可以用类似 RANDAO 的协议取代NXT风格的随机数发生器，将这个代价进一步加大数个级别。

验证人策略

那么在Casper协议下作为验证人该如何行动呢？验证人有两类主要活动：出块和投注。出块是一个独立于其它所有事件而发生的过程：验证人收集交易，当轮到他们的出块时间时，他们就制造一个区块，签名，然后发送到网络上。投注的过程更为复杂一些。目前Casper默认的验证人策略被设计为模仿传统的拜占庭容错共识：观察其他的验证人如何投注，取33%处的值，向0或者1进一步移动。

为了实现这个策略，每一位验证人都要收集其他验证人的投注，并且尽可能保持该数据处于最新状态，用于跟踪每一位验证人的当前意见。如果某个高度上还没有或者只有很少的其他验证人发表了意见，那么我们用大致如下的算法来处理：

• 如果这个高度的块还没有出现，且当前时间离这个块应该出现的时间过去不久，则预计概率为0.5
• 如果这个高度的块还没有出现，且离这个块应该出现的时间过去了很长时间，则预计概率为0.3
• 如果这个高度的块已经出现，且按时出现，则预计概率为0.7
• 如果这个高度的块已经出现，但是出现时间过早或者过晚，则预计概率为0.3

这个过程还会增加一些随机性来防止“卡住”的场景，但是基本原则是一样的。

如果对某个高度其他验证人已经发布了许多意见，那么我们使用如下策略：

• 设三分之二验证人的预计高于概率 L ； M 为预期的中位数（即有一半验证人的估值高于 M ）；三分之二验证人的预计低于概率 H 。
• 设 e(x) 是一个让 x 更“极端”的函数，例如让数值远离0.5走向1。一个简单的例子是这个分段函数： e(x) = 0.5 + x/2 if x > 0.5 else x/2 .
• 如果 L > 0.8 , 则预计概率为 e(L)
• 如果 H < 0.2 , 则预计概率为 e(H)
• 其他情况，预计概率为 e(M) , 但是结果不能超出 [0.15, 0.85] 这个区间，因此少于67%的验证人无法强迫其他的验证人大幅调整其预计。

在这个策略中，验证人可以自由的通过改变 e 的形状来选择他们自己的风险厌恶程度。选一个在 x > 0.8 时 e(x) = 0.99999 的函数也可以（而且很可能产生和Tendermint一样的行为），但是它有更高的风险，如果占有了担保资金一大部分的验证人是恶意的，他们只需要很低的成本，就能设计让使用该 e 函数的验证人损失全部保证金（攻击策略为先预计概率为0.9，引诱其他验证人预期0.99999，然后突然改为预计0.1，迫使系统预期收敛到0）。另一方面，一个收敛很慢的函数会导致系统在没有遭受攻击的情况下更低效，因为最终确定会更慢，且验证人对每个高度的投注需要持续更久。

现在，作为 客户端 要如何确定当前状态呢？过程基本如下：一开始先下载所有的区块和投注，然后用上面的算法来形成自己的意见，但是不公布意见。它只要简单的按顺序在每个高度进行观察，如果一个块的概率高于0.5就处理它，否则就跳过它。在处理所有的区块之后得到的状态就可以显示为区块链的“当前状态”。客户端还可以给出对于“最终确定”的主观看法：当高度 k 之前的每个块，意见要么高于99.999%或者低于0.001%，那么客户端就可以认为前 k 个块已经最终确定。

进一步的研究

Casper和一般化的投注共识还需要大量研究。特别包括以下几个方面：

• 给出能表明即使存在一些拜占庭验证人系统也能在经济上激励收敛的证据
• 找出最佳的验证人策略
• 确保把 投注打包进区块 的机制没有漏洞
• 提高效率。目前的概念原型(POC1)能模拟大约16个验证人同时运行，理想情况下这个数字应该越高越好（注意系统在 生产网络 能处理的验证人数量大约是概念原型性能的平方，因为概念原型把所有节点都运行在一台机器上）。

该系列的下一篇文章会介绍Serenity可伸缩性方面的工作，估计会和Serenity的第二个概念原型(POC2)同时发布。