Original postby 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

这个进程还会添加一些随机性来防止“卡住”的场景,可是基本原则是一样的。

假如对某个高度其他验证人现已发布了许多定见,那么咱们运用如下战略:

  • 设三分之二验证人的估计高于概率LM为预期的中位数(即有一半验证人的估值高于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.8e(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)一起发布。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注