Show Posts
91
中文 (Chinese) / PLAY中最后一个受托人作恶问题综述及其他攻击方式
« on: April 09, 2015, 03:09:00 am »
PLAY中最后一个受托人作恶问题综述及其他攻击方式
首发http://playtalk.org/index.php?topic=323.0
本文将重点描述最后一个受托人作恶问题以及目前的一些改善措施。
首先回顾DPOS的基本结构，我们主要关注以下两个特征：
1，101位受托人每一轮随机轮换位置
2，每一个块带两个参数，一个是previous_secret，一个是next_secret_hash。
同时在分析攻击时所应面对的最差情况是：系统中有50个受托人作恶。
如果有超过50个受托人作恶，那么整个出块机制都会面临威胁，此时就没有必要分析了。
下面详述最后一个受托人作恶问题的由来。
一个博彩游戏可以利用每一个块内部secret（以下简称S）来组合生成一个开奖依据，在此引入两个概念：
下注块B0（或最后可下注块）和开奖块Bf。
B0顾名思义就是在此块之后，不能再对本局游戏下注。
Bf即，此块公布后，本局游戏的胜负就已经确定，一般来说这个块包含着开奖所需的最后一个信息。
在最简单的情况下，B0与Bf是相邻的。我们看看会带来什么问题。
Bf包含着开奖所需的最后一个S，那么在发布块之前，他就知道了开奖结果，如果他在之前下注了，他发现自己没有中奖，他就可以选择不发布这个块，从而下一个受托人会发布一个块（带有不同的S），这样故意miss的受托人就躲过了一次没中奖。
在此假设返奖率是100%，中奖的话可以获得k倍奖金，中奖的机会是1/k。
我们可以计算他的数学期望是（注意，作恶受托人仅会在确定自己是最后一个受托人时下注）：
(1/k)*k+(1-1/k)*(1/k)*k = 2-1/k。
可以看到如果k是250万（即花两元，有1/250万的机会中500万）时，数序期望接近于2，这意味着受托人可以做到持续盈利，并且利润基本等于本金，可见优势是巨大的。
在PLAY的技术白皮书里(http://dacplay.org/pdf/BitSharesPlayWhitePaper_CN.pdf)提出了一种改善措施，基本思路是B0与Bf不是相邻的，而是B0，B1，B2，B3，其中B1，B2，B3都有机会成为Bf，而究竟谁是Bf是由B0的S最终确定的（确定过程也可能包含B0之前的S）。如此的好处是受托人不能很早的（特别是在可以下注阶段）就确定自己是Bf，不能极度有针对性的选择在哪一局游戏下注。
但是这也没有完全解决问题，我们来计算一下这种情况下的作恶者的数学期望（注意，作恶受托人仅会在确定自己有可能是最后一个受托人时下注）：(1-1/N)*k*(1/k)+(1/N)*[k*(1/k)+(1-1/k)*(1/k)*k] = 1+(1/N)*(1-1/k)
此处N为B0与Bf的间隔数（相邻时N=1），在上例中N = 3。在上例中假设k极大，那么作恶者的数学期望也将达到4/3，即可以稳定获利，利润是本金的1/3。而且此时开奖速度最慢将会达到10N秒（10为DPOS的平均出块间隔）。
在目前的结构下，只要Bf在出块前知道本局游戏结果，他就可以选择miss。
他可以在所有的块中都下注，此时他的数学期望是：1+(1/101)*(1-1/k)。k极大时为接近1.01。这也是目前结构的理论上最佳结果。即使DPOS完全取消轮值洗牌模式，每个块的出块者都是在上一个块出完后才能知道自己才是下一个块的出块者的情况下，作恶受托人仍然具备的最小优势。对于下一个块完全随机指定出块者的方式，我们已有一些策略，暂不在本文中描述。
游戏实际运行时，我们应确保不能有玩家的数学期望大于1，数学期望大于1意味着可以稳定盈利，长期来看游戏必然不可持续，由此我们可以引入摩擦a。a的定义是对于一般玩家你投入本金是1+a，回报是1。而1/(1+a)即为返奖率。此时作恶者的数学期望要乘以返奖率，从而降到1以下，将会极大的降低作恶动机，但他相比其他玩家仍然具备优势。
要更好的解决最后一个受托人问题，另一种思路是尽可能确保信息发布，即使有受托人故意miss，随机数信息仍然可以在将来发布出去（将导致延迟开奖，但可以抑制作恶动机，因此可能是很实用的）。相关策略暂时不在本文中描述。
下面说说另外的一些攻击方式，包括DPOS机制导致的攻击方式和受托人合谋的攻击。
在DPOS机制中采用了每轮轮值洗牌的模式，每一轮中顺序固定且已知。当有人控制了多个受托人时，如果他确定他控制的受托人在未来存在如下顺序：AXXXXXA，在这样一个序列里，作恶者可以在第一个A块时就构造第二个A块的随机数，由此构造以第二个A块为最终信息的游戏的结果。其结果不再是逃过一次输的机会，而是直接可以指定该轮游戏的结果。该问题由BTSdac在https://bitsharestalk.org/index.php/topic,15545.0.html提出，并预计在将来的DPOS轮值洗牌算法中修正，算法悬赏见https://bitsharestalk.org/index.php/topic,15547.0.html。修正后相同受托人的间隔将大于50，这意味着必须51个受托人联合才能作恶，但此时系统的安全性都不再能保证，此类作恶就不再是考虑范畴。
另一种攻击，是在B0和Bf之间（含两端）的所有受托人都被同一人控制的情况下，在B0可下注阶段，此人就已经知道了本局游戏的结果，从而直接在B0块下注并必胜。对此的策略是N至少要50才能保证绝对安全，N等于50时，如果还有人可以作恶意味着他已经控制了至少51个受托人，此时此种作恶就不再是考虑范畴。(但此时游戏的开奖时间将延迟到500秒)
当网络延迟时，一个受托人签出的块可能没有被其他人收到而被认定为miss，但是此时收到的人却可以保存下这个数据并提前获知了其中的S，当这个S作为下一轮某游戏的最终信息时（即这个miss的受托人下一轮成为了某局游戏的Bf），那么提前获取这个S的人就获得了一些优势。但是在N>>1的情况下，这个问题并不是很容易被利用。
其他攻击方式陆续添加。
首发http://playtalk.org/index.php?topic=323.0
本文将重点描述最后一个受托人作恶问题以及目前的一些改善措施。
首先回顾DPOS的基本结构，我们主要关注以下两个特征：
1，101位受托人每一轮随机轮换位置
2，每一个块带两个参数，一个是previous_secret，一个是next_secret_hash。
同时在分析攻击时所应面对的最差情况是：系统中有50个受托人作恶。
如果有超过50个受托人作恶，那么整个出块机制都会面临威胁，此时就没有必要分析了。
下面详述最后一个受托人作恶问题的由来。
一个博彩游戏可以利用每一个块内部secret（以下简称S）来组合生成一个开奖依据，在此引入两个概念：
下注块B0（或最后可下注块）和开奖块Bf。
B0顾名思义就是在此块之后，不能再对本局游戏下注。
Bf即，此块公布后，本局游戏的胜负就已经确定，一般来说这个块包含着开奖所需的最后一个信息。
在最简单的情况下，B0与Bf是相邻的。我们看看会带来什么问题。
Bf包含着开奖所需的最后一个S，那么在发布块之前，他就知道了开奖结果，如果他在之前下注了，他发现自己没有中奖，他就可以选择不发布这个块，从而下一个受托人会发布一个块（带有不同的S），这样故意miss的受托人就躲过了一次没中奖。
在此假设返奖率是100%，中奖的话可以获得k倍奖金，中奖的机会是1/k。
我们可以计算他的数学期望是（注意，作恶受托人仅会在确定自己是最后一个受托人时下注）：
(1/k)*k+(1-1/k)*(1/k)*k = 2-1/k。
可以看到如果k是250万（即花两元，有1/250万的机会中500万）时，数序期望接近于2，这意味着受托人可以做到持续盈利，并且利润基本等于本金，可见优势是巨大的。
在PLAY的技术白皮书里(http://dacplay.org/pdf/BitSharesPlayWhitePaper_CN.pdf)提出了一种改善措施，基本思路是B0与Bf不是相邻的，而是B0，B1，B2，B3，其中B1，B2，B3都有机会成为Bf，而究竟谁是Bf是由B0的S最终确定的（确定过程也可能包含B0之前的S）。如此的好处是受托人不能很早的（特别是在可以下注阶段）就确定自己是Bf，不能极度有针对性的选择在哪一局游戏下注。
但是这也没有完全解决问题，我们来计算一下这种情况下的作恶者的数学期望（注意，作恶受托人仅会在确定自己有可能是最后一个受托人时下注）：(1-1/N)*k*(1/k)+(1/N)*[k*(1/k)+(1-1/k)*(1/k)*k] = 1+(1/N)*(1-1/k)
此处N为B0与Bf的间隔数（相邻时N=1），在上例中N = 3。在上例中假设k极大，那么作恶者的数学期望也将达到4/3，即可以稳定获利，利润是本金的1/3。而且此时开奖速度最慢将会达到10N秒（10为DPOS的平均出块间隔）。
在目前的结构下，只要Bf在出块前知道本局游戏结果，他就可以选择miss。
他可以在所有的块中都下注，此时他的数学期望是：1+(1/101)*(1-1/k)。k极大时为接近1.01。这也是目前结构的理论上最佳结果。即使DPOS完全取消轮值洗牌模式，每个块的出块者都是在上一个块出完后才能知道自己才是下一个块的出块者的情况下，作恶受托人仍然具备的最小优势。对于下一个块完全随机指定出块者的方式，我们已有一些策略，暂不在本文中描述。
游戏实际运行时，我们应确保不能有玩家的数学期望大于1，数学期望大于1意味着可以稳定盈利，长期来看游戏必然不可持续，由此我们可以引入摩擦a。a的定义是对于一般玩家你投入本金是1+a，回报是1。而1/(1+a)即为返奖率。此时作恶者的数学期望要乘以返奖率，从而降到1以下，将会极大的降低作恶动机，但他相比其他玩家仍然具备优势。
要更好的解决最后一个受托人问题，另一种思路是尽可能确保信息发布，即使有受托人故意miss，随机数信息仍然可以在将来发布出去（将导致延迟开奖，但可以抑制作恶动机，因此可能是很实用的）。相关策略暂时不在本文中描述。
下面说说另外的一些攻击方式，包括DPOS机制导致的攻击方式和受托人合谋的攻击。
在DPOS机制中采用了每轮轮值洗牌的模式，每一轮中顺序固定且已知。当有人控制了多个受托人时，如果他确定他控制的受托人在未来存在如下顺序：AXXXXXA，在这样一个序列里，作恶者可以在第一个A块时就构造第二个A块的随机数，由此构造以第二个A块为最终信息的游戏的结果。其结果不再是逃过一次输的机会，而是直接可以指定该轮游戏的结果。该问题由BTSdac在https://bitsharestalk.org/index.php/topic,15545.0.html提出，并预计在将来的DPOS轮值洗牌算法中修正，算法悬赏见https://bitsharestalk.org/index.php/topic,15547.0.html。修正后相同受托人的间隔将大于50，这意味着必须51个受托人联合才能作恶，但此时系统的安全性都不再能保证，此类作恶就不再是考虑范畴。
另一种攻击，是在B0和Bf之间（含两端）的所有受托人都被同一人控制的情况下，在B0可下注阶段，此人就已经知道了本局游戏的结果，从而直接在B0块下注并必胜。对此的策略是N至少要50才能保证绝对安全，N等于50时，如果还有人可以作恶意味着他已经控制了至少51个受托人，此时此种作恶就不再是考虑范畴。(但此时游戏的开奖时间将延迟到500秒)
当网络延迟时，一个受托人签出的块可能没有被其他人收到而被认定为miss，但是此时收到的人却可以保存下这个数据并提前获知了其中的S，当这个S作为下一轮某游戏的最终信息时（即这个miss的受托人下一轮成为了某局游戏的Bf），那么提前获取这个S的人就获得了一些优势。但是在N>>1的情况下，这个问题并不是很容易被利用。
其他攻击方式陆续添加。
