译者按:原文作者Emin Gün Sirer是康奈尔大學计算机科学副教授IC3密码货币和合约倡议的联合主任,在这篇文章当中他通过具体的实例分析了为什么从区块链中导出公平的、不可操纵的随机数是困难的,因而像福利彩票这样的彩票并不适合用区块链来实现
在今天的文章当中,我会通过一个警示性的故事来解释為什么在区块链上运行彩票是一个糟糕的主意
场景是这样的:Bitcoin Core开发者 Eric Lombrozo昨天秉着圣诞节的精神,决定赠送1个BTC他将其分成了10份,每份为0.1BTC规則是:转发他的推文,就有机会得到这笔奖金每份礼物的价值大约为1500美元(译者注:文章创作时间为2017年12月25日)
为了证明这次赠送活动是公平的,他在推文中描述了自己提出的算法我不会去讨论其具体的技术细节,你只需要明白本质上,他想要选择一个随机数比如说17,然后他会把这10份奖励分发给每一位得到随机数17的人为此,他组合了其预先确定的区块高度的两个区块哈希并导出与转发数量相互质嘚16位(bit)数字(H),所谓的互质数仅仅意味着中奖彩票号码H和转推文的数量没有除1之外的公因数。然后他索引操作了转发列表10次,然后奖勵每一个得到
(H)结果的推文转发者
现在,这个计划是非常华丽和复杂的但是,下面发生的关键操作很简单:他从两个区块哈希中导出了┅个随机数我至少看到过十几个以太坊Dapp使用了这种模式,如果你觉得自己已经理解了这个问题你可能会选择停止阅读。但请继续因為这里面存在着多个问题,并且实际的漏洞并不是显而易见的即使一开始看起来是这样的。
让我们深入研究这个方案并记录下有趣的觀察和思考:
这个计划,表明上需要相当担心矿工对彩票操纵的可能
每一个从区块哈希导出随机数的人,都应该担心矿工攻击的问题假想一下,一名矿工希望让这个彩票变得不公平他可以通过计算一个区块并查看其哈希是否会给矿工带来好的结果。如果不是好结果這名矿工可以丢弃掉区块,选择不去公开
但实际上,矿工攻击并不是问题
但在这种情况下对矿工的担忧完全被夸大了,假设一名矿工為了这个特别的彩票他必须放弃一个完好的比特币区块,因此他要失去超过20BTC (约合30万美元)的奖励而得到的彩头却只有0.1BTC(1500美元)。
无論如何有些人会过于偏执于那些不会发生的事情。我们听到过不少关于"中国矿工"的消息还有专门诋毁他们的红迪子版块。Core开发者总是鈈断提醒我们要警惕中国矿工也许额外的偏执是被要求的。但至少中国矿工们可能是无害的。
当我们试图关注矿工的时候我们可能唍全错过了其他更大的问题,对吧
在这一点上,事情变得非常哲学所以我会放弃这一思路,我不认为矿工是邪恶的这里有一个充满信息和模因的subreddit。
那么这种方法能够很好地牵制住矿工吗?一点也不该方案从两个哈希的组合中导出随机数,分别在高度H和H + 5它无法确保这些区块来自两个独立的矿工。如果两个数字来自同一个矿工的话那么挑选它们有什么意义吗?
即使区块H和区块H+ 5来自不同的矿工我們怎么知道它们不是一伙的?这似乎是一个不可逾越的问题
好吧,无论如何它都是有问题的
但不管怎样这个方案都可以通过可预测的方式进行破坏。挖掘第二个区块的矿工会知道第一个区块是被谁挖到的,所以他完全控制了彩票的结果所以,两个矿工之间甚至不需偠串通因为第二个矿工已经控制了结果。如果挑选了N个区块的哈希那么挖到最后一个区块的矿工,依然可以控制结果
但是等等,在隨机性计算中的缺陷并不重要因为理性的矿工不会发动攻击,因为成本远远高于潜在的奖金可是,假设是把一个国家级的彩票(例如鍢彩)放到区块链上那就是另外一回事了,但这个案例显然不是所以让我们继续前进。
这就引出了一个更为根本的问题所在这个特殊的方案选择了一个随机获胜的数字,并给得到这个数字的人颁发奖励其选取的随机数仅受限于群体大小的互质。组合H的选择并通过H*j mod N嘚算法限制了赢家的集合。
因此一些数字较其它数字会更容易地被选为H。简单举个例子来说明原因想象一下, Eric的推文被转发了1000次那麼与1000 互质的潜在数字就有65534种。例如2, 4, 5、6, 8和10不是互质的,所以它们不是第一个被选取的数字它们的倍数也不会被选择。
现在被选择的数芓可能是较小的,比如1然后覆盖前10个数字,包括2、4、5、6、8和10
也可能会选中较大的数字,它环绕并覆盖那些不会被覆盖的数字
但是,佷可能有一些数字既没有被选中的数覆盖(即N的互质数)也没有被环绕的大数字所覆盖(即mod N 互质数的倍数)。让我们来看看这些不幸运嘚数字
有这么不幸的数字吗?是的事实证明,如果转发了1000次那么第20、25、40、50、60、75条转发绝不可能获胜!
我们不知道会发生多少转发,所以或许1000次转发的不幸数字和1001次转发的不幸数字可能差别很大。
在这一点上我们可以做一些理论分析,而现在是平安夜要计算和检驗数字要容易得多。我们所能做的就是对转发的可能数量进行迭代,看看是否有任何有利的位置和不利的数字然后我们可以看出有多尐占据优势的人,以及多少不幸的人
我写了一个小模拟器,检查每一次转发的结果我把它放到了,任何人都可以查看如果我错过了什么的话。
这里是图形结果用于模拟范围的推文转发数。
我们可以看到在已转发 Eric推文的1000人中,10号的转发者中奖率极高!他有641486种不同的獲胜方式第二个有利位置是970号,他有632404种获胜的方式而2号, 8号和9号推文转发也在前25之列。
将高概率数字和尾部的低概率数字进行比较例洳,第924次转发它只有440952种获胜的方式! 而第10次转发的获胜概率是第924次转发的1.5倍!其它较低概率的数字,分别为420, 660, 780、840以及528
这一切看起来都很聰明。起初看这个机制是可以由矿工操纵的但后来发现它们完全是不相关的,并且这个方案本身也有缺陷其分布并不均匀,某些人获勝的概率会大于其他人
但是,这里还有一个更大更明显的错误。我会给你一段时间思考
这种彩票实际上更有利于运行社交媒体操纵垺务的人,如果你有一堆Twitter 马甲账号你就可以比诚实的参与者拥有更多的机会。如果你有1000个马甲账号并且实际转发数只有1000条,那么上面這些花哨的数学和模拟实际上并不重要你获胜的几率就是50% 。
那有什么更好的办法吗均匀分布实际上是很难实现的。通常情况下最簡单的解决方案是最好的:获取转发列表,并基于区块哈希导出的随机数种子进行洗牌操作(使用Knuth shuffle工具)然后你再把奖颁给前10的人洗牌算法必须事先公布,那样人们才不会认为你从中作弊当然,即使你使用了这个计划你仍然可能会遭受女巫攻击( Sybil attack)。
可Eric已经宣布了这個特别的彩票计划他能够立即改变规则吗?如果这是一个智能合约那就意味着一次硬分叉!
那么,我们能从这个案例中学到了什么
- 從区块链中导出公平的、不可操纵的的随机数是困难的;
- 组合多个区块哈希值无法免疫矿工攻击,最后一名矿工可以完全控制结果;
- 如果伱专注于不太可能的结果你可能会错过更多可能的问题;
- 事实上,这个方案表现出了令人难以置信的不公平性如果你能选择好转发的時机,你可以拥有比其他人更大的优势
- 这个游戏,仍然掌握在社交媒体巨魔(拥有大量马甲账号)的手中