Quote from: didiksky on March 07, 2017, 12:43:47 PM

上周， Yoich发布了一篇博客文章，详细地介绍了我的惩罚条件的最小化的过程，并正式论证了惩罚条件的最小化所提供的安全性和活力性。这是拜占庭容错算法、安全下的异步（safe-under-asynchrony ）和密码经济安全（cryptoeconomically）共识算法的关键组成部分，而拜占庭容错算法、安全下的异步和密码经济安全共识算法，也是我权益证明路线图的核心。在这篇文章中，我想进一步详细地解释这个算法到底是什么，它重大意义表现在哪里，它一般如何适用于权益证明的研究中。
Casper研究的一个关键性目标是实现经济确定数，经济确定数我们可以半正式地定义如下：

如果一个客户能够证明 (i) 区块B1永远会是这个规范链条的一部分，或者证明(ii) 导致区块B1被恢复的参与者们一定会被保证受到等额X美元的惩罚，那么这个区块B1在经济是被最终确定的，在密码经济安全的边际是X美元。
我们暂且想象X约等于7000万美元。基本上，如果一个区块被最终确定，那么这个区块就变成了这个链条的一部分，并且想要改变这一事实是非常非常昂贵的。工作量证明是达不到这一效果的，这也是权益证明独一无二的特征。我们的意图是使得51%的攻击非常的昂贵，并且即使大部分的验证器一起协力也不能将已经确定的区块回滚，除非他们愿意承受极大的经济损失这个经济损失如此的大，以至于当攻击成功了，这会提高底层加密货币的价格，因为市场会对总硬币供应的减少做出强烈的反应，而不是启用紧急硬分叉来纠正攻击（这里参见基本哲学深入的概述）。

经济确定数在Casper研究中得以完成，通过要求验证者缴纳保证金才能参加，并且如果协议确定验证者们违反了一系列的规则，那么验证者们的保证金会被拿走（惩罚条件）。

一个惩罚条件可能会像是这样：

如果一个验证器发送一个表单的签名信息：
["PREPARE", epoch, HASH1, epoch_source1]
一个表单的签名信息：
["PREPARE", epoch, HASH2, epoch_source2]
当HASH1 != HASH2或者epoch_source1 != epoch_source2，但是epoch的价值在两个信息中都是一样的，那么这个验证器的保证金就被取消了（ie：删除）
协议定义了一系列的惩罚条件，诚实的验证节点遵循一个协议，保证不触发任何的条件（注意：有时候我们说违反一个惩罚条件，他的同义词是触发，把惩罚条件当作一个法律，你不应该违反法律）。永远不要发送PREPARE的消息2次，这一点对于一个诚实的验证节点来说一点都不难。

PREPARE和COMMIT是从传统的拜占庭容错共识理论中借用的术语。现在，我们来假设他们代表了两种不同类型的消息，在后面的协议内容中我们会介绍。你可以认为共识协议要求两轮不同的协议，其中PREPARE代表了一轮协议，COMMIT代表了第二轮协议。

同时也有另一个确定性条件，他描述了当客户能确定一些特定的哈希区块是确定数的。这很容易理解，我们继续，在现在版本的Casper研究中表述唯一的确定条件。

如果一些特定的epoch存在一系列签名消息的表单里，那么一个HASH是被确定的。
["COMMIT", epoch, HASH]

如果您将创建这些签名邮件的验证者的存款余额相加，则您获得的金额大于当前活动验证者集合的总存款余额的2/3。

作为速记，我们可以说哈希在某个特定的时期由三分之二的验证器提交。，或者说哈希在某个特定的时期有三分之二是保证的。

惩罚条件需要满足下面两个情况：

责任安全：如果两个冲突的哈希值被最终确定，那么至少能够被证实，存在至少三分之一的验证节点违反了惩罚条件
合理的活跃性：必须存在一组至少有三分之二的验证节点发送的一组消息，并且必须在没有违反惩罚条件的情况下能确定一些新的哈希区块，除非有至少三分之一的验证器违反了惩罚条件。
责任的安全给我们带来了经济确定数的想法，如果两个互相矛盾的哈希值都得到了确定（比如说，分叉），那么我们有数学的证明说，一大系列的验证节点都违反了一些惩罚条件，我们可以向区块链提交这一项证据并且对这些违反了惩罚条件的验证节点们实行惩罚。

合理的活跃性基本上是说算法不应该被卡住，并且不应该确定任何的事情。

为了说明清楚这两个概念的含义，我们可以考虑两种玩具算法，一种可以满足安全性但是不能满足活跃性，另一种可以满足活跃性但是不能满足安全性。

算法1：每一个验证器节点都有一个机会发送一个形式为[COMMIT，HASH]的消息，如果三分之二的验证器节点为同一个哈希发送一个COMMIT，那么这个哈希值是被确定的。发送两个COMMIT则是违法了惩罚条件的。
这里，有一个明显的证据可以证明这个算法是安全的：如果HASH1和HASH2都得到了确定，那么可以证明这两个哈希每一个都至少有三分之二的承诺，因此必须会有三分之一的重叠发生，所以有三分之一的验证器节点被削减了（Slashed），但是他不是真实的活着地：如果有二分之一提交A，有二分之一提交B（一个完全合理地可能意外发生的事情），那么有六分之一的验证器节点必须自愿砍掉自己以确定一个哈希值。
算法2：每一个验证节点都有一个机会发送一个列表的信息["COMMIT", HASH, epoch]，如果三分之二的验证节点在同一个epoch发送给同一个哈希一个COMMIT，那么这个哈希被确定了。在同一个epoch给不同的哈希发送两个COMMIT消息则违反了惩罚条件。
这解决了先前算法中的问题，如同在同一个epoch我们得到了50/50，一半一半的情况，那么我们在下一个epoch再做尝试，但这引入了另外一个安全的缺陷：两个不同的哈希可以在不同的时期完成。
事实证明，有可能在同一个时间得到两个哈希值。但这是不平凡的，需要满足四个惩罚条件，加上1000行代码给Yoichi 完成以正式证明他实际上是可行的。

这些惩罚条件有：

[COMMIT_REQ]如果一个验证器节点发送一个签名信息列表：
["COMMIT", epoch, HASH]
除非一些特定的价值epoch_source以及-1 <= epoch_source < epoch，列表消息
["PREPARE", epoch, HASH, epoch_source]
这些已经由2/3的验证者签字和广播，那么验证者的存款被扣掉了。
用英语简单来讲，发送一次请求需要有三分之二的验证器节点做好准备。

[PREPARE_REQ]如果一个验证器节点发送一个签名信息列表：
["PREPARE", epoch, HASH, epoch_source]
当epoch_source != -1，除非一些特定的价值epoch_source_source，有-1 <= epoch_source_source < epoch_source消息列表
["PREPARE", epoch_source, ANCESTOR_HASH, epoch_source_source]
当ANCESTOR_HASH是(epochpoch_source)，HASH的祖先已经由2/3的验证者签署和广播，那么验证者的存款被扣掉。
如果你想提前准备在某个时期指定某个特定的先前时期，那么需要三分之二的验证节点在这个时期提前准备好，这些准备必须必须指向同一个之前的时期（例如，三分之二的验证节点在时期41准备指向时期35是可以的，三分之二的验证节点在时期41只有一半准备指向时期35有另外一半准备指向时期37是不可以的，六分之五的验证节点在时期41准备，其中有五分之四指向时期35也是可以的，因为六分之五的五分之四是三分之二，因此你可以忽略剩下的六分之一。

第n阶祖先（n-th degree ancestor），在区块链哈希上的含义来说，是始祖的意思，其中比如说，以太坊的区块第 3017225是以太坊区块第3017240的15阶祖先区块。请注意，一个区块只能有一个父辈，因此对于一个特定数字n只有一个第n阶祖先。

如果验证器发送一个列表信息[PREPARE_COMMIT_CONSISTENCY]
["COMMIT", epoch1, HASH1]

还有一个准备列表信息

["PREPARE", epoch2, HASH2, epoch_source]

当epoch_source < epoch1 < epoch2，然后不管是否HASH1 ?= HASH2，这个验证器都被削减了。

当你在某个时期做出提交，那么你可以很清晰的看到有三分之二的准备在这某个时期发生。所以在未来你准备的任何的准备都应该做的更好来指引这个时期或者更新的东西。

如果一个验证器发送一个信息列表[NO_DBL_PREPARE]
["PREPARE", epoch, HASH1, epoch_source1]

有一个信息列表

["PREPARE", epoch, HASH2, epoch_source2]

当HASH1 != HASH2或者epoch_source1 != epoch_source2，但是epoch的价值在两个信息列表中都是一样的，那么这个验证器就削减了。

在单一的时期内不可能准备两次

通过这四个惩罚条件，可以证明出来，保证可靠的安全性的同时保证合理的活跃性是可行的。

请注意，使用上述的规则的话，两个不同的哈希得到最终的确定是可以实现的如果两个哈希都是同一段历史的一部分，那么他们是可以被最终确定的，并且，实际上，当有越来越多的哈希在这个一直增长的链条的末端被不断的确定正是我们想要的结果。

左边：不同的哈希值可以在遵循的这些规则下被确定，但是如果他们都是同一个链条的一部分的话，那么他们就是按照预期来运行的。右边：不属于同一历史的哈希是互相冲突的；有证据证明上述四个惩罚条件能够组织两个互相冲突的哈希被最终确定，除非至少有三分之一的验证器被剑手了。
现在，让我们把这些事情都拼凑在一起。这里有一个满是验证器的池（任何一个人都可以自由加入，虽然有一些延迟，需要上交存款保证金，当然任何参与者都可以自由离开，然后在更高的延迟之后撤回它们的资金），并且这些验证器有权签署和发送列表信息。

["PREPARE", epoch, HASH, epoch_source]

["COMMIT", epoch, HASH]

如果在某个特定的epoch有足够多的COMMIT消息给这个HASH，那么这个HASH就被最终确定了。哈希都互相连接在一起，每一个哈希都指向着之前的一些哈希，我们希望能够看到，随着时间的增加，这个越老越增长的链条上有越来越多的新加入的哈希链接在一起并且被最终确定。我们为验证器们添加了经济上的奖励来鼓励他们发送PREPARE和COMMIT，以便及时发送足够的消息以实现最终确定的完成。

一般来说，你可以使用任何具有同步下保证的活跃性，在异步下保证安全性的拜占庭容错共识机制的算法PBFT，并将他转化成一组惩罚条件来给予你可靠的安全性和合理的活跃性。上述的条件都是受拜占庭容错共识机制（PBFT）和Tendermint的结合的启发，但也有其他的点可能会产生不一样的结果。

请注意，合理的活跃性和实际的活跃性其实不是一回事；合理的活跃性意思是，理论上说我们总是可以个某些事情进行最终确定，但他也可能总是这样的情况-我们总是非常不走运，总是反复重复永远不结束确定任何事情。为了解决这个问题，我们需要想出一个提议机制，并且确保这个提议机制能够具备这样的属性，这个属性需要实际上能够达到帮助我们实现活跃性的目的。

提议机制是提议哈希的机制，其余的使用COMMIT和PREPARE消息来尽力完成最终确定。这种机制有时候也是会有缺陷的；他做的是惩罚条件需要做的事情，就是尽管这个提议机制是有缺陷的，但是投他也能有效保障安全性，并且一旦提议机制停止并产生故障，这个协议可以使这个事情得到最终确认。

在许多传统的拜占庭容错共识机制算法中，提议机制和其他部分的算法都紧密的联系在一起。在拜占庭容错共识算法中，每个视图（大致相当于一个纪元）都被分配到单个验证器去，并且这个验证器可以自由的提议他们想要提议的东西，这个验证器可能会不提出任何的提议，或者说提出无效哈希，亦或者提出多个哈希而产生不良操作，但是其他部分的拜占庭容错共识算法会确保这些操作都不会是致命的，并且这个算法会自动切换到下一个时期。在这里，我们实际上可以将我们的惩罚条件和和许多其他的提议机制相结合，只需要他们能够满足一些条件。

首先，这个提议机制必须在每一个时期都只可以提议一个哈希值，并且这个哈希必须是有效的哈希（有效性条件可以使非常复杂的，在以太坊这个情况下，以太坊涉及了以太坊环状态转换函数的验证和执行，以及设计数据可用性的验证环节）。

第二，哈希们必须形成一条链，也就是说，在时期N提交的一个哈希必须有一个父辈，这个父辈必须是在N-1时期提交的一个哈希，第二度的祖先必须是在N-2时期提交的哈希。

第三，哈希必须是哈希，惩罚条件不会妨碍验证器们最终确定这个哈希值。这个可以说是非常微妙的。现在我们来考虑这样的一个情景，在时期O中，提议机制提议了哈希0，在时期1，提议机制提议了哈希1,（哈希0的直接子哈希），不管出于什么原因，这些哈希中没有任何的哈希有得到足够的准备来获得提交。那么，这个提议机制（由于一些临时故障)为时期0提出了另一个哈希0，这需要获得三分之二的准备和二分之一的提交。
现在，这个提议机制有两种选择。第一种可能是，它可能会提出HASH2（HASH1的子哈希），然后HASH3（HASH2的子哈希）等等。然而，惩罚条件确保了在没有六分之一的验证器被剑手的情况下，没有任何的哈希可以被提交。另外一个可能，也是正确的可能性是，他提交HASH1（HASH0的子哈希），同时期待哈希可能永远不会被确定，因为他的竞争对手HASH1已经超过三分之一的准备了，所以HASH1得不到他所需要的三分之二的准备了，然后提出HASH2（HASH1的子哈希），HASH2是可以被提交的，然后这个提议机制可以继续提议新的哈希，每个哈希都是前一个哈希的子哈希

一个直接想法是，一些人可能有：我们可以做出一个传统的工作量证明的链条，遵循的是最长链条的规则把他作为提议机制吗？每第100个区块都是一个检查站，在这里，第N*100的区块哈希成为对于时期N的提议。但是这不能保证这能够继续运行，因为在上述情况中，提议机制会尝试提交的是HASH2而不是HASH1，所以他永远不会完成任何哈希的最终确定（这不是我们说的卡住，因为想要摆脱这样的情况是不需要有任何人被削减，但确实需要矿工们在包含了HASH0的链条上互相串通，即使包含了HASH1的链条在工作量证明理论中是比HASH0更长的）。然而，我们能做的是，使用一个传统的工作量证明区块链与能够修改分叉选择的规则相结合。

分叉选择规则是一个功能，这个功能是由客户端评估产生的，其将区块的集合和已经产生的其他消息作为输入，并向客户端输出什么是规范链条，最长的有效的链条是正确的链条是一个简单的分叉选择规则，这点非常适用于工作量证明，Zohar和Sompolinsky的GHOST是一个更复杂的例子。我们可以来定义一个分叉选择规则，这可以允许区块链作为共识机制算法的提议机制，并且具有上述的属性，如下可见：

开始HEAD是一个成因
找到HEAD有三分之二的准备和最大提交数量的有效后代
将HEAD设置为和他的后代对等，然后返回到第二个步骤
当步骤2再也不能找到具有三分之二的准备和任何提交的后代时候，使用区块链的基础分叉选择规则（无论是最长的链条，还是GHOST，还是其他的）来找到提示。
请注意，在我们上述的例子中，这会更加有利于HASH0而不是HASH1，所以这会导致有期望的行为发生。也请注意，如果有一个最终确定的链条，那么他会总是选择最终被确定的链条。

上面的惩罚规则确保了特定类型的故障的产生会是非常昂贵的：分叉的最终还原。然而，同时还会有其他类型的故障，这些分叉不是这个惩罚规则能够解决的。特别地，要确定一个无效的哈希，以及确定一个代表了包含无效数据的链条的哈希。目前，能够解决绝对加密经济安全这个问题的最简单的并且已经实现的方式是实现完全的节点下载并且验证所有的区块，所以你才可以完全无视无效的区块。因此，确定这个哈希是不是被最终确定的可以通过两个步骤来进行：1)检查者三分之二的提交2）一直检查这个链条直到可以证明这个哈希是有效的。

要为轻客户端最出最终确定的值，有两种方式。第一种方式是添加另一个类型的节点来发送消息（就像["ATTEST", HASH, epoch]），这具有的效果是如果这个消息被提交到一个链条，并且这里面的哈希实际上是在那个时期的哈希，那么这个验证器会获得一部分的奖励，如果这个哈希并不是那个时期的哈希，那么他们将会遭受到很大的惩罚。因此，验证器只会在确定这个给定的哈希是客户端看到的规范链条上的一部分的时候，他们才会发送消息，并会永远这样继续（验证器这样做的好时机是在他们个人完全验证从区块链到哈希之后，并检查他们的三分之二的提交）。

第二是给予轻客户端有权限访问各种加密经济技术，使得他们能够在少数假设的帮助下能够非常有效的验证数据的可用性和有效性。这将可能涉及擦除码和交互验证的组合。这是一种类似于对分片进行的研究相似，并且两者之间的联系非常的紧密上述第一种方法需要验证器本身就是一个完整的节点，而第二种方法不需要验证器本身就是一个完整的节点，并且分片本身是有关于创造一个区块链，这个区块链中没有任何一方是一个完整的节点，关于这个话题的博文在后续中会继续更新。

特别感谢Yoichi Hirai, River Keefer 和 Ed帮我审视了一遍这篇文章。
注：
1.一些人可能会认为，工作量证明有经济上的决定性与安全边际R * k，其中R是区块奖励，k是正在恢复的区块数，但这不是真的，如果你成功实施了51%的攻击，那么你会得到区块奖励的补偿51％攻击的预算要求确实大致R * k，但是你成功实施攻击的成本却是0.

2.三分之一的比率取自传统的拜占庭容错理论，并被选择以最大化容错的总水平中选择。一般来说，在这篇文章中你可以用任何t> 1/2的价值来替换掉本文中的提出的三分之二的惩罚条件。你可以从活跃度角度将容错度计算为1-t（因为如果超过1-t离线，则不能得到t），从安全角度来看，容错程度为2t-1 （如果t能够最终确定A，t也能最终确定B，那么加起来2t> 1 ，所以至少2t-1必须是重复的）。 t = 2/3最大化了两个（1-t = 1 / 3,2t-1 = 1/3）的最小值;您还可以尝试t = 3/5（活跃度：2/5的容错力，安全性：1/5），或者t = 3/4（活跃度：1/4，安全性：1/2）。还请注意到，值t < 1/2在关于有多少节点可能离线这些情况的常识下也是会有意义的，但是在解决这些情况，并且主观最终性阈值的更宽泛的概念中，是我下一次会在另外一篇文章中更加深入探讨到的另外一个主题。

3.当然，除非这些保证金已经被撤回了，但是这个（远程攻击）将会是我写的另外一篇文章的主题，虽然今天的这篇文章是我两年前就应该发表的。

4.至少，只要他使用了哈希和签名联合起来的加密。如果它使用阈值签名，那么这个会更加困难。因为2/3个恶意节点的联盟可以伪造任何其他参与者的签名。
原文：https://medium.com/@VitalikButerin/minimal-slashing-conditions-20f0b500fc6c#.4s8pm7fu5
作者：Vitalik Buterin
编译：Lola

好复杂啊看不懂求解释

w5929057chunchun

Posts

Merits