RChain的Casper共识算法

RChain的Casper共识算法是基于Vlad Zamfir的correct-by-construction共识协议和CTO Greg Meredith和其他RChain成员讨论而来的。他们还为Casper开发了一个模拟器：https://github.com/rchain/Casper-Proof-of-Stake/tree/simulation-dev。

1、通用预估安全协议

一个预估安全协议需要以下内容：

1）一个可能共识的值的集合C 

2）一个逻辑Lc，用来判断集合C中的元素声明的命题是正确或者是错误

3）一个分类，∑代表协议，∑中的对象是协议状态和态射的协议执行

4）一个调用评估器的函数ε，用于把协议状态映射到逻辑中的命令

我们假设这么一个命题：P是一个已经预估过安全的协议状态，Q是所有可能的未来状态都被预估器标明是P。

在逻辑中给定少数合理的约束以及预估器，我们可以得到以下的安全共识结果：

1) 如果Q1和Q2有共同的未来状态，那么它们的安全预估就不可能相互矛盾（如果P是安全的，非P肯定是不安全的）。因此如果节点按照预估器的行为，就不可能到达不可调和的状态，因此达成共识是可能的。再者，一旦一个节点看到一个命题是安全的，它知道最终的公示结果也会保持是正确的。

2、RChain的预估安全协议

RChain在通用预估安全协议上扩展以满足自身的需求，同时仍然保留上面所希望的一致安全结果。

2.1 The Consensus Values

集合C会包括所有可能的块DAG(blockDAGs) 。与链结构相反，DAG结构的原因在于共识协议的某些部分需要多个父块指针。

在区块的上下文中需要有以下的属性：

1）父区块的指针

2）政治资本（PC）

3）数据

4）原则 （指向其他区块的指针，那些在创建的时候就被验证器看到的区块）

一个区块包含的数据取决于它是什么类型的区块，与用户最相关的将是运行在RhoVM上包含计划交易的区块，但是与当前讨论最相关的将是包含DAG中其他区块的“确认”的区块。这些区块在共识协议当中扮演者重要的角色。这些数据还可能会强制执行“削减条件”，从而惩罚生成无效块的验证人。

2.2 The Logic and Propositions

其次，我们需要定义我们用来谈论blockDAG的逻辑Lc。 在这里，想想自然陈述是真的还是假的，似乎是最简单也是最明智的。例如，“区块在DAG中”或“区块有父母”。 最终，我们最关心的声明将是前者，因为这是我们的“分岔选择规则”。 （对于严格的数学处理，我们需要对逻辑细节做更精确的描述，但上面的直觉对我们来说已经足够了。）

2.3 The Protocol's Specification

现在我们要给定一个明确的协议规范，这在数学上我们认为是一个类别∑。协议的状态是来自一个元组的集合中的{A, P, H}. A∈{"propose", "acknowledge"}是预期的行为，P∈R 是政治资本的平衡条件，H是接收过的历史消息。 消息里面包括用户执行智能合约的请求和来自其它验证器的区块。那些包含区块的消息必须只有创建它的验证器的签名。协议执行的操作是“更改意图”、“执行”和“接收消息”（以及“不做任何事”的动作和各种动作的任何组合，因为这是一个类别的需求）。

在给出每个协议执行如何更新协议状态的细节之前，我们需要定义预估器ε。前面提到过，估计器最关心的是那些与DAG中哪些块有关的逻辑命题。ε是分叉选择规则，它选择多个可能的替代块中的选出区块来继续结构。在工作证明的区块链协议它的是最大工作量的链的头部。这里我们选择的是greedy heaviest observed sub-tree (GHOST) 算法，它会选择得分最高的区块来继续这个结构。一个区块的得分b，关于消息历史，H，它是DAG中来自其发送者的最近消息中的区块的权重的总和。

一个区块的权重的公司可以用下面的公司来定义：

其中f是参数的一个协议，0<f<1, ack(b)是确认b的区块，pca(b)是连接到b的政治资本的数量。

下面是一个具体的例子：

假设有3个验证器：A, B, C，让我们以A的角度来看，假设她有一个与下图一致的消息历史：

在图中，区块在其创建者之上对齐。每个区块上都标有它的名字还有政治资本的数量，箭头指示父区块指针。

此外，标有“ACK”的标记还表示目标区块中的确认数据存在于来源区块中。消息历史记录显示来自每个发件人的最新消息是 A - b6, B - b5, C - b4。

因此只有这些块有非0的得分，按照上面的公司，W(b6) = 3, W(b5) = 4f2, and W(b4) = 2f。然后遍历整个DAG，我们计算出来得分：

Score(b6) = 3 +4f2 + 2f, Score(b5) = 4f2 + 2f, Score(b4) = 2f。因此b6有最高的得分，未来通过A创建的区块必须从b6构建，除非它收到一条改变得分的消息。

注意，如果我们回顾一条消息（在创建B6之前），Score(b5) = 4f2 + 2f + 2（+2是来自b1，它具有A最近的消息，b6没有）它的得分是最高的，这是为什么b6是建立在b5之后的原因。

还要注意的是，b3和b4可以被认为是另外“促进”A的区块两个验证人，b5充当前两个非冲突块的区块“连接”成一个区块，这样就可以使结构继续扩展，又不留下任何已经确认一致的块。

我们再回到指定协议执行上，更改意向协议执行只是改变了预期的行为，而行为触发了当前的预期行动。这里有两种可能采取的行动：

1、提议（Propose），根据消息历史记录中的一个或多个未处理的智能合同请求创建交易计划，创建一个区块需要根据合约中涉及的父区块的名字、GHOST分叉规则、政治资本的数量（由验证器选择，需要注意的的是政治中心越多区块的权重越高，这以为着它更可能被GHOST分叉规则选出来）、作为数据创建的计划、从消息历史记录中可作为理由的所有区块（这里可以做的一个哟优化是，只选择那些相关的区块）。

2、承认（Acknowledge），促进或者连接。从发件人中选择消息历史记录中最新消息的任意数量的独立块(一个区块是一个选项，它将是"promoting")。独立性的含义是既不能通过DAG连接从另一个达到，并且包含在它们的未连接的DAG的部分中的任何数据不冲突。然后创建一个新的区块，需要的东西和提议是一样。

两种执行对协议状态的影响是将生成的块添加到消息历史中（验证器立即收到所有发送给网络的消息），减少区块的政治资本的余额。政治资本的余额的增加是根据递归公式在区块中确认的。

pce(b）是区块b挣到的政治资本数量。需要注意的是，最新的消息的约束会组织它去增加旧的区块的政治资本。 单一确认规则同样可以防止重复提交同一区块进行的快速“政治资本挖掘”。

最后的协议执行，接受消息，并没有像它刚开始表现的那么简单。当然，它把新消息添加到消息历史中，但同样重要的是这条消息是在这个动作当中验证。 这一步是必要的，以确保blockDAG的完整性。实际上，因为这是一个不信任的系统，所有验证人都需要独立的验证它所受到的所有消息。 收到新消息时，有几个不同的事情需要验证：

1）消息不产生歧义。歧义的定义是，来自同一个发送方的两条消息没法证明另外一条消息。也就是说，这两个消息都不出现在另一条消息的理由（或递归地在这些理由中）。这是一种拜占庭式的故障，因为它表明发送方的行为就像在运行协议的两个独立版本。否则，发件人的最新消息将包含发件人在其理由中的所有过去消息。

2）如果一条消息是一个包含交易的区块，那么它的所有交易都是合法的。即智能合约还没有被前面的区块执行，并且使用事务来更新虚拟机状态成功没有错误。 例如。 导致双重花费的交易应该是错误的，因此是无效的。

3）如果消息是连接类型的确认，那么区块是相互独立的，并且之前没有被相同的发送方确认过。 同样的事务不会存在于多个确认区块中。

4）如果消息是一个削减区块，它确实对应于一个真正的违反行为。

5）如果消息是任何类型的确认，那么确认的所有区块都是有效的。也就是说，这个子弹使验证成为一个递归过程。

如果上述的任何条件违反了，那么这条消息就是无效的。这种违规行为就会被报告。在这种情况下，将创建一个新的“削减”块，惩罚无效消息的违规发件人。

协议的最后一部分是终结的概念，即我们怎么知道这个区块会永久的存在于DAG当中？目前的区块链使用区块的深度作为最终的代理，并且在技术上没有区块是结束了。这里用一个区块的深度以便了解一个区块是否仍然是主DAG的一部分的可能性，然而我们也可以引入合理的“同步约束”来具有真正的结束。一个验证人（或者用户）在消息已经存在它的历史当中有一段时间T（假设说是1星期），就会认为一个区块已经结束了。这表示终结的概念是相对的，它取决于消息的接收，但实际上，在时限足够长的时候，这并不构成太大的问题。如果两个节点完成相互排斥的区块，这确实允许共识失败的可能性，但是当时间窗口很长并且由于下面讨论的激励时，这种情况也是不可能的。

2.4 Economic Considerations: 

与其他区块链一样，提出交易块的验证人也包括反映验证人为执行计算而获得的“费用”（以REV的形式）的一些交易。因此，验证人被激励来确保他们创建的区块保留在主DAG中，否则他们被奖励的交易将会丢失。GHOST分支选择规则会导致更多权重的区块更可能在主DAG中结束，因此，将大量政治资本附加到他们创建的去块上的验证人更可能保留他们获得小费。因此，在提出区块时花费政治资本是经济上的激励。而且，由于政治资本被纳入共识协议，花费之后赚取政治资本的唯一途径就是承认其他区块。被别人承认的区块（自己提议的区块没有政治资本，得分会比原来的要低，因为f<1，并且GHOST只会考虑最近的消息）是最有可能用于扩展DAG的，因为他们的得分比较高。因此，推动区块对于每个人都是有利的，因为推动者可获得政治资本供未来使用，而推广者可有可能获得小费。因此，连接区块是更加激励，因为它把所有个人促销的好处的进行了加和。

个人行为的好处：

1、自动轮流验证人。最好赚取政治资本的方式是从别的验证人花费的，政治资本的流动（以及因此提出障碍的能力）在不同的验证人之间;

2、减少分叉。推动区块和合并区块工作，以保持单一的主要DAG。

2.5 Slashing: Punishments for invalid blocks

产生无效块的验证人应该避免他再次这样做，因此惩罚应该包括减少他们的政治资本。事实上，允许通过惩罚减少政治资本，可以防止一个坏的验证人。然而，和解原则上总是可能的，因为验证人仍然可以获得政治资本，并且如果需要的话，慢慢地将他们的余额回到零以上。

有关各种违规行为的确切数额的细节尚未制定出来。

 2.6 The one free parameter in the protocol f

f的值应该是多少呢？f的值会不会因为网络中的参与者数量的变化而随时间改变？这些问题还需要通过模拟器进行更多的验证。

2.7 Initiating the protocol: Where do the first validators and political capital come from?

由于政治资本只能通过已经拥有政治资本的区块来推动，所以一个自然的问题是第一个政治资本来自哪里。一个解决办法是让创世纪块有一定的政治资本附在他们身上。

所有的验证人需要推进至少一个区块，为了增加政治资本（初始值为0）。单一承认规则防止这种剥削获得无限量的政治资本。请注意, 即使一个验证器人创建了一个无限链，它从创世区块开始不断的推进区块, 但是几何系列将收敛到一个有限的值。此外, 单一确认规则可防止创建多个此类链。

一个相关的问题是，谁会成为验证人？一个简单的答案，任何人。每一个用户加入网络之后，它的政治资本是0，他们不能提出创建新的区块，但是他们可以参与验证的过程。只有参与共识过程的用户才能获得政治资本。我们确保只有那些真正对网络感兴趣的人才能贡献未来的区块，同时仍然让任何人都有机会达到这个水平。

 2.8 Bad Behaviour Technically Allowed in Present Protocol Specification

1、提出一个区块，自己马上去推销它。这可以防止别人马上承认了你提出的区块。这可以减少对手从你的提议里面获得的政治资本。确实减少了你正在构建的分支的分数（因为得分只考虑了最近的消息，而升级区块的权重将低于原来的），因此有一种可能性，你的的区块将错过叉选择规则。因此，目前尚不清楚在这种情况下垄断政治资本的策略是否会成功。

2、用毫无意义的确认淹没网络，试图崩溃更小的节点。例如，写一个脚本，在创世区块的基础上创建一个全是确认区块的无限链，类似于DDOS攻击。如上所述，这种攻击行为是不被系统本身鼓励的，但是出于一些外部的原因，有人想搞垮RChain的话，这是一种可以想到的方法。

一个简单的（虽然不方便）的方式去这将验证人在发出确认之前要出入一个验证码。另外一个选项是内置一个防火墙，在检测到这种攻击的时候能自动的屏蔽掉另外的验证人。

 2.9 Future Optimizations

允许冲突区块的连接，解决冲突的一个方案是在提出区块的同时确认独立区块的分片。

Other Notes

1、一个验证人离开了几个月，然后又回来怎么办？怎么样在保证网络不受攻击的情况下重新建立信任？

政治资本是通过在达成共识的过程中积极活动而获得的，因此是信任的代表。这个问题是政治资本有某种“半衰期”的一个很好的论据。这就意味着当验证人离开之后，他需要重新努力才能回到以前的地位。关于这个半衰期是多久，这个还在讨论中。

2、我们有没有解决囚徒困境的方法？

交易收入（代替验证人验证每个共享跨分片状态的分片）就是一个囚徒困境。囚徒困境，作为一个无限重复博弈的游戏。它有一个最优的默认合作策略，甚至在失去信任之前原谅一次背叛。我们简化了这个游戏，值得信任的名称空间将得到很好的处理，而不可信的命名空间与网络的其他部分隔离开来。我们还会有一些跨名字空间的验证人，确保不会被一些垃圾玩家把整个网络都搞臭了。

 3、有没有可能操纵共识协议来获得免费的存储？也就是说，因为共识的历史需要作为证据永久存储，那这些信息是否可以由客户端使用，而不需要支付适当的存储费用。

这是可能的，可以通过设定确认区块中的数据格式来避免这种情况。

该文章翻译自：https://rchain.atlassian.net/wiki/spaces/CORE/pages/92536846/Casper+for+RChain 

翻译水平有限，我本身对区块链的了解也有限，如有错误，请及时联系我，大家一起提高，谢谢！

相关文章：

1、https://medium.com/rchain-cooperative/a-visualization-for-the-future-of-blockchain-consensus-b6710b2f50d6

2、https://github.com/ethereum/research/blob/master/papers/cbc-consensus/AbstractCBC.pdf

3、https://github.com/ethereum/research/blob/master/papers/CasperTFG/CasperTFG.pdf

对区块链技术感兴趣的童鞋可以添加QQ群：711399035。大家一起研究区块链技术，投资好的区块链项目。