请选择 进入手机版 | 继续访问电脑版

KIBO社区

找回密码
加入会员

QQ登录

只需一步,快速开始

查看: 273|回复: 0
收起左侧

V神的75条刷屏推文:以太坊Casper研究的历史及发展状况

[复制链接]

370

主题

393

帖子

4849

积分

管理员

Rank: 9Rank: 9Rank: 9

活跃
3004
威望
551
金钱
100
发表于 2018-8-19 09:46:48 | 显示全部楼层 |阅读模式
今天我要发一长串推文来解释以太坊Casper研究的历史和现状,包括FFG(Friendly Finality Gadget)与CBC(Correct-by-Construction)之间的竞争,混合PoS=>完全PoS的转变,随机性的作用,机制设计问题等等。
1.jpg

“长程攻击”

以太坊权益证明(POS)的研究开始于2014年1月的Slasher[1]。虽然算法非常不理想,但它引入了一些重要的想法,特别是使用惩罚来解决无利害关系(Nothing-At-Stake)问题[2]。过去的例子说明,我使用的惩罚力度非常小,只取消了签名奖励。

Vlad Zamfir于2014年年中加入进来,他很快就要求验证者缴纳保证金。保证金数额远大于奖励,而且可能因不当行为而被收缴。我们在2014年底花费了大量时间试图处理“长程攻击(long range attacks)”,即攻击者从主链上的保证金中撤回他们的赌注(stake),并利用它创建一个比主链拥有更多签名的替代性“攻击链”,这样他们可以欺骗客户转换到这条“攻击链”上。

如果攻击链在最近的时间点分叉离开主链,这不是问题,因为如果验证者为两个冲突的链签署两条冲突的消息,则可以将其用作惩罚它们并拿走其保证金的证据。但如果分叉在很久以前就已经发生(因此称为长程攻击),攻击者可以撤回他们的保证金,避免任何一个链的惩罚。

我们最终得出结论,长程攻击是不可避免的,差不多和PoW支持者所说的原因那样。但是,我们并没有接受他们的结论。我们意识到我们可以通过引入额外的安全假设来处理长程攻击:用户每四个月至少登录一次(保证金需要四个月才能取出),这样用户会拒绝回滚到这之前。

这对PoW支持者来说是一种让人讨厌的东西,因为它感觉像是一种信任假设:当你第一次同步时,你需要从一些可信来源获得区块链。但对于我们这些主观主义者来说,这似乎并不是什么大不了的事。你需要一些可靠的源告诉你区块链的共识规则在各种情况下是什么(并且不要忘记软件更新),因此这个PoS假设所需的额外信任度并不大。

既然我们已经确定了保证金和惩罚的机制,那么我们必须决定这些保证金和惩罚是什么。我们知道我们想要一个“经济最终确定(Economic Finality)”的属性,验证者会以这样的方式在区块上签名:如果一个块被“最终确定”,则不会有冲突块被最终确定,除非大部分验证者对与其早前消息有冲突的消息进行签名,但对有冲突的信息签名区块链是可以检测到,从而进行惩罚的。

投注共识

在一个我称之为“投注共识(consensus by bet)”的方向上,我进行了一次很长的但最终效果不佳的思考。[3]

通过投注达成的共识是一个有趣的结构,验证者将对哪个区块会被最终确定进行投注,并且投注本身决定了用哪条链实现共识。理论上说,PoW也有这个属性,因为挖矿是一种投注,如果你投中对的链,你可以获得收益(奖励-采矿成本);如果你投中错的链,挖矿成本就是你的损失。而PoS中,我们可以将投注推高很多。验证者投注的量开始很低,但随着验证者对一个区块越来越有信心,每个人的投注量都会呈指数级上升,直到他们最终将全部保证金押在一个区块上。这将是“最终确定”。

拜占庭容错(BFT)与CBC

与此同时,Vlad开始大量研究机制设计,特别是着眼于让Casper更加强大以应对寡头垄断。我们也开始研究受传统拜占庭容错(BFT)理论启发的共识算法,如Tendermint。

Vlad认为传统的BFT很蹩脚(他特别讨厌硬阈值[4],比如PBFT和Tendermint的2/3)。他尝试从头开始有效地重新发明BFT理论,使用他称之为“Correct by Construction”的方法,即CBC。

CBC的理念与传统的BFT非常不同,在后者中“最终确定”完全是主观的。在CBC的理念中,验证者签署消息,如果他们签署的消息与他们之前的消息相冲突,他们必须提交“理由”来证明:他们投票的新事物比他们投票的旧事物拥有更多的支持,故而他们有权转向新事物。

为了检测最终确定,客户要寻找可以证明大多数验证者对区块B进行可靠投票的消息模式和规律,而可靠投票使得他们无法在没有大部分验证器“非法”转换投票的情况下转换到别的区块上。

例如,如果每个人都投票支持B,那么每个人都会对包含每个人对B的投票的区块进行投票,这证明他们支持B并且知道其他人都支持B,因此他们没有合理的理由转而为别的区块投票。

实用拜占庭容错(PBFT)与FFG

我最终放弃了投注共识,因为这种方法似乎过于冒险。所以我转而试图理解像PBFT(实用拜占庭容错算法)这样的算法是如何运行的。这花了一段时间,但几个月后我明白了。

我设法简化了PBFT[5]并将其转换到区块链的环境中,将其描述为四个“削减条件(slashing conditions)”,这些规则说明了哪些消息的组合是自相矛盾并因此是非法的。[6]

我定义了一个规则,用于确定块何时被最终确定,并证明了关键的“安全性”和“可信活跃性(plausible liveness)”属性:(i)如果块已最终确定,那么在没有> =1/3验证者违反削减条件的情况下,冲突块无法最终确定(ii)如果一个区块最终确定,2/3诚实的验证者总是可以合作以最终确定一个新的区块。因此,只要> 2/3是诚实的,该算法既不能“回头”也不会“卡住”

我最终将最小的削减条件从四个简化为两个,并从那里得到了Friendly Finality Gadget(FFG),它被设计为可用作任何PoW或PoS或其他区块链之上的覆盖层,以增加最终确定的保证。

CBC与FFG之间的分歧

最终确定是一个非常重要的进步:一旦块被最终确定,无论网络延迟如何都是安全的(与PoW中的确定不同),并且逆转区块需要≥= 1/3的验证者作弊,但这种行为是可检测到的,验证者的保证金也会被扣除。因此,逆转最终确定的成本可能会达到数十亿美元。Casper CBC和Casper FFG方法都实现了这一目标,尽管技术上有所不同。
2.png

请注意,虽然两者以不同的方式运行,但Casper CBC和Casper FFG都是需要在某些现有的分叉选择规则之上应用的“覆盖层”。简单来说,在Casper CBC中,最终确定覆盖适应分叉选择规则,而在Casper FFG中,分叉选择规则适应最终覆盖。

Vlad最初对分叉选择规则的偏好是“最新消息驱动的GHOST”,让GHOST适应PoS[7]。我最初的偏好是开始使用混合PoS,使用PoW作为基本分叉选择规则。在Casper FFG的初始版本中,PoW将逐个区块地“运行”链,随后PoS将最终确定块。 Casper CBC从一开始就完全的PoS。

与此同时,Vlad和我都提出了我们对共识*激励*理论各自的看法。

在这里,一个非常重要的区别存在于*唯一可归因错误*和*非唯一可归因错误*之间,前者你可以说出谁负责,因此可以惩罚他们,而后者多方中的一方可能导致错误的发生。非唯一可归因错误的典型案例是离线与审查,也称为“说话人——听众错误等同(speaker-listener fault equivalence)”。惩罚唯一可归因错误(例如Casper FFG削减条件)很容易。惩罚非唯一不可归因错误很难。

如果由于少数群体下线或者大多数人对少数群体进行审查而无法判断区块是否已停止最终确定怎么办?在这个问题上基本上有三种思想流派[8]:(i)对双方进行一定程度的惩罚(ii)对双方进行严厉惩罚(Vlad的偏好)(iii)将链分叉为两条,对每条链上的一方进行惩罚,并让市场决定哪条链更有价值(我的偏好)。

2017年11月,Casper FFG削减条件,加上我通过“quadratic leak”机制解决“1/3离线”问题的想法,成为一篇论文[9]。

当然,我很清楚吸引社交层来解决51%的攻击并不是一件好事,所以我开始寻找方法来至少允许在线客户*自动*实时检测哪个链是“合法的”,哪个是“攻击链”。

我之前有一些想法(每个客户都有一个“可疑分”)[10]。这个想法有些内容,但仍然不是最理想的;除非网络延迟正好为零,否则只能保证客户的可疑分最多会有差异,而不能保证客户完全同意。

与此同时,我对Vlad模型的主要批评与“受挫攻击(discouragement attacks)”有关,攻击者可以威胁要进行51%的攻击,导致每个人都亏损,从而逼迫其他人退出,从而在接近零成本的情况在主宰这个链。而Vlad(和Georgios Piliouras一起)也开始研究经济模型,以估计在他的模型下这种攻击的实际成本。

值得注意的是,所有这些问题并不是PoS所独有的。事实上,在PoW中,人们倾向于放弃对这些问题的思考并假设51%的攻击是不可能的,但是一旦要发生,51%的攻击是必须不惜一切代价防止的世界末日。

但是,正如以太坊的传统一样,Vlad和我都没有意识到“雄心勃勃”这个词可能只是一种恭维,继续致力于我们各自的方法,以降低51%攻击的激励,减少和恢复其带来的破坏。

FFG的发展历程——从混合PoS到完全PoS

在2018年初,Vlad在CBC上的工作开始迅速推进,并在安全证明方面取得了很大进展。对于2018年3月的进展情况,请参阅这个史诗般的两小时演讲:https://www.youtube.com/watch?v=GNGbd_RbrzE

与此同时,Casper FFG也取得了巨大进展。我们决定将其作为将发布到以太坊区块链的合约来实施,这让开发变得容易。在2017年12月31日23:40,我们发布了一个用python编写的测试网络。[11]不幸的是,FFG的发展随后放缓了。将FFG作为合约实施的决定使一些事情变得更容易,但它使其他事情变得更加困难,这也意味着最终从EVM切换到EWASM,以及单链Casper切换到分片Casper会更难。

此外,团队的工作分为“主链Casper”和“分片链Casper”,但很显然Casper和分片团队之间的很多重复工作是非常不必要的。在2018年6月,我们决定放弃“将混合Casper FFG作为合约”,而是追求作为一个独立链的完整Casper,这样能让分片的整合会容易。
3.png

转向完全的PoS让我开始更加努力地考虑PoS分叉选择规则。

Casper FFG(和CBC)都要求* 所有 *验证者在每个“epoch”中投票以最终确定块,这意味着每秒会有数十到数百个签名。就计算费用而来,BLS签名聚合让这一切变得可行。但我想尝试利用所有这些额外的签名来使链更加“稳定”,在几秒钟内获得“100次确认”的安全性。

我最初做过一些尝试。[12]然而,所有这些针对分叉选择规则的方法都有一个缺点:它们将验证者分成“证明者(attesters)”和“提议者(proposers)”,而作为块生产关键驱动因素的提议者拥有过大的权力。这是不可取的,主要是因为这要求我们有一个强大的链上随机数生成源来公平地选择提议者。但实现链上的随机很难,像RANDAO这样的简单方法看起来越来越成问题。[13]

Justin Drake和我以两种方式解决了这个问题:Justin使用了具有确定性和可验证输出的可验证延迟函数,但是需要大量不可并行的连续时间来计算,提前进行操作是不可能的;而我自己对Vlad™Cult的做出了重大让步,使用基于GHOST的分叉选择规则来大大减少对提议者的依赖,只要50%以上的证明者是善意的,即使90%以上的提议者是恶意的,链也能不受干扰地发展

Vlad非常高兴,虽然彻底的高兴:他更喜欢基于验证者*最新消息*的GHOST版本,而我更喜欢基于*即时(immediate)*消息的版本。[14]

大约在这个时候,我还设法找到了一个将Casper FFG流水线化(pipeline)[15]的方法,将最终确定的时间从2.5个epoch缩短到理论上最佳的2个。

我很高兴RPJ分叉选择规则(我已经改名为“即时消息驱动的GHOST”)与Casper FFG很好地兼容,并且它具有非常重要的“稳定”属性:这一分叉选择是对未来分叉选择的良好预测。这看起来很明显,但让分叉选择规则不具有此属性是很容易发生的。

最新的开发结果是,最新消息驱动GHOST可能由于技术性,在两轮内只能提供25%的容错能力,但是即时消息驱动的GHOST(使用FFG或CBC)仍然可以提供全部的33%

FFG和CBC之间的主要权衡是CBC似乎具有更好的理论属性,但FFG似乎更容易实施。

99%容错算法

与此同时,我们在可验证的延迟函数方面取得了很多进展[16]。此外,我最近决定研究Leslie Lamport在1982年的论文[17]。其中,如果你假设所有节点(包括观察者)在线并且网络延迟较低,那么他的共识算法具有99%的容错能力。

可以说,网络延迟假设让这个想法不适合作为主要的共识算法。然而,有一个用例在很好的运行:替代51%审查检测的可疑分。基本上,如果51%的验证者开始审查区块,其他验证者和客户可以检测到这种情况正在发生,并使用99%的容错共识来同意这种情况正在发生,并协调少数派进行分叉。

这项研究的长期目标是尽可能减少对社交层的依赖,并最大限度地增加破坏链稳定性的成本以至于逆转到社交层是必要的。

现在还剩下什么?在FFG方面,主要有正式的证明,对规范的改进以及实施的持续进展(已由> = 3个团队开始!),并着眼于安全和快速部署。在CBC方面,大致相同。继续加油!

1.可见V神的文章Slasher: A Punitive Proof-of-Stake Algorithm https://blog.ethereum.org/2014/01/15/slasher-a-punitive-proof-of-stake-algorithm/

2. 在分叉发生时,无论分支是偶然的还是恶意尝试重写历史并逆转交易,矿工的最佳策略是在每条链上都挖矿,以便无论哪个分叉获胜,矿工都会获得奖励。 因此,假设有大量想要获取经济利益的矿工,攻击者可能能够发送交易以换取一些数字商品(通常是另一种加密货币),收到后从交易后的一个区块开始分支,将钱汇给自己。即使只拥有总权益的1%,攻击者的分叉也会赢,因为其他人都在两条链上挖矿。↵

3.详情可见Understanding Serenity, Part 2: Casper https://blog.ethereum.org/2015/12/28/understanding-serenity-part-2-casper/

4.任何一项活动超过限制就失败或不被允许↵

5.具体可见http://pmg.csail.mit.edu/papers/osdi99.pdf

6.具体可见https://medium.com/@VitalikButerin/minimal-slashing-conditions-20f0b500fc6c

7.具体可见 https://eprint.iacr.org/2013/881.pdf

8.V神自己对三种流派的看法,可见The Triangle of Harm,https://vitalik.ca/general/2017/07/16/triangle_of_harm.html

9.论文可见 arxiv.org/abs/1710.09437 ↵

10.论文可见https://ethresear.ch/t/censorship-rejection-through-suspicion-scores/305

11. Alpha Casper FFG Testnet Instructions: https://hackmd.io/s/Hk6UiFU7z

12. Attestation committee based full PoS chains: https://ethresear.ch/t/attestation-committee-based-full-pos-chains/2259

13.Randao beacon exploitability analysis,round 2: https://ethresear.ch/t/randao-beacon-exploitability-analysis-round-2/1980

14.Recursive proximity to justification as FFG fork choice rule:https://ethresear.ch/t/recursive-proximity-to-justification-as-ffg-fork-choice-rule/2561

15.Beacon chian casper FFG RPJ mini-spec:https://ethresear.ch/t/beacon-chain-casper-ffg-rpj-mini-spec/2760

16.具体可见https://notes.ethereum.org/52JZtwErThe9KmN6TNd1lg

17.A Guide to 99% Fault Tolerance Consensus:https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html


原文:https://twitter.com/VitalikButerin/status/1029906682388799488
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 加入会员

本版积分规则

手机版|小黑屋| KIBO社区   KIBO

Copyright © 2001-2017 Comsenz Inc.   All Rights Reserved.

Powered by Discuz! X3.3 技术支持: 异样设计 Licensed

快速回复 返回顶部 返回列表