译者按:原文作者Emin Gün Sirer是康奈尔大学计算机科学副教授,IC3密码货币和合约倡议的联合主任,在这篇文章当中,他通过具体的实例分析了为什么从区块链中导出公平的、不可操纵的随机数是困难的,因而像福利彩票这样的彩票并不适合用区块链来实现。
(图片来自:MyRichFuture.com)
在今天的文章当中,我会通过一个警示性的故事,来解释为什么在区块链上运行彩票是一个糟糕的主意[1]。
场景是这样的:Bitcoin Core开发者 Eric Lombrozo昨天秉着圣诞节的精神,决定赠送1个BTC,他将其分成了10份,每份为0.1BTC,规则是:转发他的推文,就有机会得到这笔奖金。每份礼物的价值大约为1500美元[2](译者注:文章创作时间为2017年12月25日)
为了证明这次赠送活动是公平的,他在推文中描述了自己提出的算法。我不会去讨论其具体的技术细节,你只需要明白,本质上,他想要选择一个随机数,比如说17,然后他会把这10份奖励分发给每一位得到随机数17的人。为此,他组合了其预先确定的区块高度的两个区块哈希,并导出与转发数量相互质的16位(bit)数字(H),所谓的互质数,仅仅意味着中奖彩票号码H和转推文的数量没有除1之外的公因数。然后,他索引操作了转发列表10次,然后奖励每一个得到 (H)结果的推文转发者。
现在,这个计划是非常华丽和复杂的。但是,下面发生的关键操作很简单:他从两个区块哈希中导出了一个随机数。我至少看到过十几个以太坊Dapp使用了这种模式,如果你觉得自己已经理解了这个问题,你可能会选择停止阅读。但请继续,因为这里面存在着多个问题,并且实际的漏洞并不是显而易见的,即使一开始看起来是这样的。
让我们深入研究这个方案,并记录下有趣的观察和思考:
关于矿工攻击的担忧
这个计划,表明上需要相当担心矿工对彩票操纵的可能。
每一个从区块哈希导出随机数的人,都应该担心矿工攻击的问题。假想一下,一名矿工希望让这个彩票变得不公平,他可以通过计算一个区块并查看其哈希是否会给矿工带来好的结果。如果不是好结果,这名矿工可以丢弃掉区块,选择不去公开。
但实际上,矿工攻击并不是问题
但在这种情况下,对矿工的担忧完全被夸大了,假设一名矿工为了这个特别的彩票,他必须放弃一个完好的比特币区块,因此他要失去超过20BTC (约合30万美元)的奖励,而得到的彩头却只有0.1BTC(1500美元)。
无论如何,有些人会过于偏执于那些不会发生的事情。我们听到过不少关于”中国矿工”[3]的消息,还有专门诋毁他们的红迪子版块。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次转发的不幸数字可能差别很大。
在这一点上,我们可以做一些理论分析,而现在是平安夜,要计算和检验数字要容易得多。我们所能做的,就是对转发的可能数量进行迭代,看看是否有任何有利的位置和不利的数字,然后我们可以看出有多少占据优势的人,以及多少不幸的人。
我写了一个小模拟器,检查每一次转发的结果,我把它放到了github上,任何人都可以查看,如果我错过了什么的话。
这里是图形结果,用于模拟1000-4000范围的推文转发数。
我们可以看到,在已转发 Eric推文的1000人中,10号的转发者中奖率极高!他有641486种不同的获胜方式。第二个有利位置是970号,他有632404种获胜的方式。而2号, 8号和9号推文转发也在前25之列。
Winners Losers
------- ------
10 641486 143 475215
970 632404 336 473269
890 632321 672 472628
830 631763 756 470375
790 631226 528 468487
730 630904 840 464022
710 630818 780 461876
670 630004 660 455016
610 629438 420 454108
590 628902 924 440952
将高概率数字和尾部的低概率数字进行比较,例如,第924次转发,它只有440952种获胜的方式! 而第10次转发的获胜概率是第924次转发的1.5倍!其它较低概率的数字,分别为420, 660, 780、840以及528。
更大的错误
这一切看起来都很聪明。起初看这个机制是可以由矿工操纵的,但后来发现它们完全是不相关的,并且这个方案本身也有缺陷。其分布并不均匀,某些人获胜的概率会大于其他人。
但是,这里还有一个更大,更明显的错误。我会给你一段时间思考。
这种彩票实际上更有利于运行社交媒体操纵服务的人,如果你有一堆Twitter 马甲账号,你就可以比诚实的参与者拥有更多的机会。如果你有1000个马甲账号,并且实际转发数只有1000条,那么上面这些花哨的数学和模拟实际上并不重要,你获胜的几率就是50% 。
更好的方法
那有什么更好的办法吗?均匀分布实际上是很难实现的。通常情况下,最简单的解决方案是最好的:获取转发列表,并基于区块哈希导出的随机数种子进行洗牌操作(使用Knuth shuffle工具[4])然后你再把奖颁给前10的人。洗牌算法必须事先公布,那样人们才不会认为你从中作弊。当然,即使你使用了这个计划,你仍然可能会遭受女巫攻击( Sybil attack)。
可Eric已经宣布了这个特别的彩票计划,他能够立即改变规则吗?如果这是一个智能合约,那就意味着一次硬分叉!
那么,我们能从这个案例中学到了什么?
- 从区块链中导出公平的、不可操纵的的随机数是困难的;
- 组合多个区块哈希值无法免疫矿工攻击,最后一名矿工可以完全控制结果;
- 如果你专注于不太可能的结果,你可能会错过更多可能的问题;
- 事实上,这个方案表现出了令人难以置信的不公平性,如果你能选择好转发的时机,你可以拥有比其他人更大的优势。
- 这个游戏,仍然掌握在社交媒体巨魔(拥有大量马甲账号)的手中。
- 事实上,就像现在每一个和比特币相关的故事一样,这次讨论,也涉及到了区块大小的争论;↵
- 具体来说,在撰写本文的时候,价值是1340美元,接受这笔资金要减去40美元的交易费,如果要使用的话,还需要花费40美元的比特币。↵
- “中国矿工”几乎总是被拿来和他们的国籍联系在一起,彷佛他们都是来自同一个模子。是的,这并不合适。↵
- 非常感谢Nick Johnson所指出的,之前使用数百万次交换的建议是低效的,并且只能渐进地实现均匀分布。Knuth在这个主题上花费了相当多的时间,并提出了一个有效的解决方案。↵