对Cardano的Ourobos算法的看法

译者:kzzz

原文地:https://steemit.com/cardamon/@dan/peer-review-of-cardano-s-ouroboros

声明:未经允许,在非用于商业和教育用途的前提下 (即,除了收取费用或商业目的),如果注明原始出处并使用声明的版权,任何人可以使用、复制或发布本文内的任何内容。

最近我有机会回顾了一下Cardano在youtube上介绍共识算法的演示。在这里可以找到原文。市面上说Cardano和Ourobos的最主要的点首个“同行评定的”“数学上可证明安全的”pos共识算法。在阅读他们的论文时可以看出,对于那些熟悉BitShares 1.0,Graphene,Steem和EOS的人来说,ouroboros只是拷贝了dpos,然后做了一些适得其反的修改。事实上,他们的论文中有17次提到“πDPoS”,却没有提到或承认我以前的任何贡献。

在对Ouroboros做更多的技术审查之前,让我们看看它最终产品的性能。

块间隔

块间隔决定了直到第一个块包含一笔交易的延迟。这是建立在协议上的去中心应用响应性的下界。除非有低延迟和高确定性,否则像Steem和BitShares这样的应用是不可行的。

EOS: 0.5 秒
Steem/BitShares: 3 秒
Ouroboros: 20 秒

不可逆性

这个特性说的是人们必须等待多久才能确定一个交易不会被新的/更长的fork(发布出来排除该交易)撤销。不可逆性对于任何多步骤交易都非常重要。在付款确认之前,你是不想发货的。在先前的交易被锁定之前,您无法进行交易。去中心化交易所在一个延迟很高的平台上是不可行的。

EOS: <= 2秒

Steem/BitShares: <= 45秒
Ouroboros: > 5小时

Ouroboros不适合去中心化应用

如果我们假设Ouroboros在某种安全定义下是真的“更数字证明安全的”,那么它就没有什么实际价值,因为按照规定,安全性实际上是让步于实际情况的。这就像要求一件防弹背心“数学证明安全”,但却重达400磅。在某些时候,系统设计的时候,要优秀考虑其他因素。

不幸的是,我们不能简单地认为它已被证明是安全的。我将证明,尽管有相反的要求,但由于其设计中的错误假设,Ouroboros远没有想象那么安全。换句话说,Ouroboros是一种400磅的防弹背心,实际上并不能真正防住子弹。

dpos的组成部分(aka Ouroboros)

dpos算法分为两部分:

选择一组区块生产者

安排生产者到时间槽

选择区块生产者的过程通常来自于可能被委托的pos。 该组区块生产者定期更新。 在BitShares中,每个维护间隔(1小时)更新一次,在Steem和EOS则每轮更新一次(N个块,其中N被定义为集合中的生产者数量)。根据Charles Hoskinson在一次采访中的介绍, Ouroboros5天才更新一次。

一旦选择了一组生产者,他们会被分配到时间段中,他们可以生产区块也可以不生产。最具有共识的链将有最少的流失,因此它会是最长的链。在ouroboros他们称之为链的“密度”,但概念是相同的。

选择区块生产者

在Ouroboros下,任何想要成为生产者的人都可以被选而得到一个slot,这与他们拥有或代理给他们的股份数量成比例。这与Steem如何在每个组中选择1个生产者类似(也就是每分钟)。而Steem只能以这种方式在每21个时间槽(slot)中安排一个,而Ouroboros则用这个数学分布来安排所有的时间槽(slot)。在Ouroboros的情况下,只有那些授权给他们至少1%股份的人才有资格成为生产者,但是Steem没有下限。

将区块生产者安排到槽(slot)

Steem和Ouroboros系统之间的主要区别在于Steem使用伪随机洗牌(shuffling)的确定性调度方式,Ouroboros使用从随机选择的股东委员会创建的可证明的随机性来源抽样方式。Oroboros非常重视对随机性的无信任源的需求,以确保生产者调度不受制于块生产者操纵区块内容以控制调度。

随机性解决安全问题

区块链安全的核心是知道在每一个确认窗口中,由一组不太可能串通共谋的实体来产生区块。不可逆转的时间取决于需要多长时间才能从2/3以上的潜在生产者得到输入。

如果生产者调度的顺序可以由生产者控制,则存在循环依赖。 这是Ouroboros这个名字的起源(一条吃自己的尾巴的蛇)。 Ouroboros设计的重点是确保2/3 +诚实的生产者可以不受干扰的被调度。 这就是为什么他们把一组生产者锁上几天,并使用一套可证明的随机的方式对他们进行调度,这样就没人能操纵这个过程。

Steem / BitShares / EOS

现有的DPOS链通过批准投票选出一组不太可能串通的实体,然后以伪随机顺序安排它们。 这种洗牌(shuffling)并不是真的需要,因为一旦他们每个参与一个块,一个2/3 +的共识就可以确定。 这就是EOS将彻底去除随机洗牌的原因。

在Ouroboros中,获得2/3 +股份的时间长度是“随机选择”的,是不知道的。 完全有可能在一些窗口中,所有的块生产者槽(slot)被随机分配给同一个生产者。虽然这在概率上是不太可能的,但是把一长串的区块分配给一起串谋的同伙,这是有可能的。

你可以把Ouroboros上的确认过程想象成一个随机增加的安装进度条。 有时候,它会迅速前进,有时候它会嘲笑你,尽管有新的块被生产出来,但没有取得任何真正的进展。

这给了Ouroboros不可预知的延迟,就像比特币一样。 在最好的情况下,2/3以上的股份可能被安排在六个区块内,但在平均情况下需要更长的时间,特别是如果有很多生产者拥有1%的权重或生产者拥有50%的权重,即使是随机的也会获得多次机会。

分发安全问题

之前我曾经提到BitShares、Steem和EOS是最去中心化的,因为它们具有每个最独特的确认窗口。在比特币中,6个区块确认窗口,平均情况下只有5个独特的个人确认一个区块(通常一个矿池至少在随机的6个区块窗口中得到两次机会)。在Steem中,14人每轮确认一个区块。

由于股权和投票是按帕累托原则分配的,我们知道Ouroboros将区块分配给生产者,如挖矿指定矿池。不太可能是100个生产者每个都有1%的代理股份。更有可能的是,将有不足20人拥有超过1%需认证的股份。此外,投票中存在投票悖论,投票给股份不足1%或更少的人的票是浪费。

在之前关于pos的文章中,我也表明,即使Ouroboros取消了1%的参与要求,它在经济上也是不可行的,因为它从区块回报中的收入少于1%,无法承担运营一个节点的成本。我以前也曾经说过,由于股权是按照帕累托原则来分配的,候选人的选举也是由帕累托原则来选择的,所以生产者之间的利益分配是帕累托平方。换言之,股权加权投票是高度中心化的,只能通过给予前n个人同等的权重(就像比特股,Steem和EOS这样),由他们进行投票才能反对。

即使股东分配他们的股权和投票,试图平衡生产者权重,最终系统仍然是帕累托的,1%的个人控制51%的股份。腐败发生在个人层面,而不是股权层面。此外,假设大股东将表现得像一组规模相似的小股东那样是错误的。不管他们的股份是多少,他们只有一个观点和一个利益,因此他们为系统贡献的信息(有利的或有害的)与其股份的大小无关。

结论

由于对由帕累托原理分配的股权和个人判断间的关系的假设错误,Cardano的Ouroboros算法在数学上是不安全的。此外,他们的算法不是“新”的,而是对我在2014年4月引入的最初的DPOS算法上粗略改动。该论文的作者没有引用相关的现有技术,也没能解释为什么他们没有引用相关现有技术是一种改进。

区块链共识算法的同行评定需要考虑他们的同行是谁,而且这些评论都应该公开。在区块链领域,我们的同行是其他区块链技术公司。由此我们可以看出,在选择独立项目的数量方面,DPOS(及其变体)是增长最快的共识算法之一。

我认为Cardano团队进行的大部分学术研究和证明仅支持一些DPOS的核心概念,即使他们的方法与EOS,BitShares和Steem的设计相比并不理想。