薛定谔的猫：区块链随机数和赌博操纵技术的分析

标题图片：薛定谔的猫。 图片来自网络。

1. 赌博应用程序已成为黑客的提款机

自去年EOS主网上线以来，博彩类应用已经成为EOS平台上的“主流”应用。 但由于EOS内部机制的缺陷，博彩类应用沦为黑客的肉食和ATM机。 一个众所周知的案例是 EOSDice 被黑了两次。

黑客的攻击方式暴露了一个很底层但很本质的问题：区块链中随机数的安全性。

以 EOSDice 为例 [1]。 第一个版本是实时彩票。 用户在当前区块下注时，通过智能合约代码使用上一个区块的信息、账户名、id、开奖时间、合约余额信息作为随机数函数的种子，计算出结果随机数生成用作获胜的基础。

黑客发现，彩票代码中使用的随机数函数实际上生成了一个确定性序列，而随机性的来源就是种子。 区块链上的所有数据都是公开透明的，代码也是开源的。 所以，如果你有种子信息和计算逻辑，是不是可以直接算出赌注赢在哪呢？

黑客必胜法：根据所有已知信息进行模拟计算，计算出必胜赌注。

EOSDice团队迅速修改代码，将实时开奖改为延迟开奖。 也就是说延后一个区块，在下一个区块执行开奖代码，这样随机数函数seed就可以使用下一个区块的信息——当前下注时不存在的信息. 似乎刀枪不入？

黑客又发现了：既然现在获取不到信息，但是现在可以写出一模一样的算法代码，等以后出现信息的时候再运行一遍，这不就可以了吗？

黑客必胜法：提前写一个和彩票代码一样的伴娘代码，但是让它像彩票代码一样延迟到下一个区块运行，这样就可以计算出必须赢的赌注，然后让伴娘代码遵循 必须赢得赌注才能获得资金。

EOSDice这次不得不从种子计算的输入中去掉余额，以防止黑客随意改变投注金额来操纵种子，进而操纵看似“随机”的开奖结果。

于是有安全研究人员高呼：“区块链世界不存在真正的随机数”，更进一步，“计算机世界不存在真正的随机数”。

在笔者（公众号：刘教莲）看来，上述命题的外延并不明确，有必要深究一下：

1、仅仅因为EOS的伪随机函数被hack了，是否可以扩展到区块链甚至计算机不是真的随机？

2. 就因为伪随机函数不能产生真随机数，那么没有任何前置条件的“分类判断”（categorical judgement）就这么容易得到吗？ 这意味着以上两个命题在任何时间和空间的任何地方都应该是绝对正确的，也意味着只要找到一个反例就足以推翻它。

同时，命题的内涵比较模糊，会导致不同读者产生不同的概念联想而被误导：

1. 存在：在“区块链世界”和“计算机世界”中如何定义某物是否存在？ “无”是否意味着无论如何都不可能存在？ 如果不是，“不”的具体内涵是什么？

2.真实性：如何定义“真随机数”？ 什么是真正的随机？ 真正的随机性可以被证明吗？

下面我们就来看看这些问题。

2. 随机数的定义及其密码安全性

快速理解现代冯·诺依曼体系结构计算机中的随机数问题，可以阅读美国计算机科学家、图灵奖获得者唐纳德·克努斯（Donald E. Knuth，1938-）的计算机科学理论与技术经典巨著1974 年，计算机程序设计艺术 (TAOCP) 第 2 卷“不完全数值计算的算法”第 3 章“随机数”。

仅这一章就有 170 页 [2]。 总结了计算机随机数问题的研究历史和成果。 作者（公众号：刘娇莲）给读者做一个简单的概述，很有意思：

首先，高老师回顾了随机数研究的历史，然后说，什么是随机数，其实是一个哲学问题，也就是说，你首先要搞清楚“我是谁”（如何定义它）。

然后，高老师引用了一个前辈给的定义，然后说，嗯，按照这个定义，我觉得整个宇宙可能没有真正的随机数！ 好吧，让我们换一个更“宽松”的定义吧！

然后，高老师改了一个“宽松”的定义，写了一个算法说，大家看我构造的随机数算法，其实根本称不上是“算法”！ 为什么？ 因为这个“算法”根本不能保证输出（计算机术语叫“停机问题”）！ 不得不弱化要求。

接下来就是滔滔不绝，给大家讲解各种弱“随机数”算法，这个比较好，那个差点，等等。 总之，高老师在不断地给同学们提示，这些算法各有各的隐患，大家在使用的时候一定要小心。

最后，布置练习。 结束。 ^_^

高老师已经开门见山地告诉我们了，确定性算法产生的“随机数”是什么随机数？ 伪随机数！ 也就是说，计算机中那个叫做“random()”（随机）的函数，实际上是生成了一个大大弱化了的、看起来像随机数的“随机数”。

这些随机数函数产生的结果的随机性将取决于外部赋予它的随机性，例如通过所谓的“种子”参数。 一旦种子已知比特币放一万个地址碰撞私钥，它计算的随机数序列就是确定性的。

是否可以断定计算机没有办法产生真正的随机数？ 如果这句话的意思是将计算机的方法限定为伪随机数算法，那么这无非是一种“分析判断”：

伪随机数算法无法生成真正的随机数。

上述分析命题的正确性与下面的分析命题相同：

黑天鹅不是白的。

众所周知，分析命题是先验的 [3]。 无需讨论。

我们需要讨论的永远是如何解决问题。 就像中本聪克服了“FLP impossible”，解决了拜占庭问题。

在密码学中，随机性非常重要。 无论是资产控制私钥的安全性，还是椭圆曲线数字签名算法签名过程的安全性，都需要良好的随机数。 当然，文章开头提到的菠菜可能也需要很好的随机数。

密码学上安全的随机数比统计模拟中使用的随机数对随机性有更高更严格的要求。 考虑到它的分布需要均匀，不能被人为操纵造成分布偏差，它的发生是不可预测的，保证了每次发生之间的良好独立性。

在密码学中，我们称这种随机数（来源）为“高最小熵”。 它在统计上要求“均匀分布”的“独立同分布”（iid）。

例如，掷偶数面硬币的最小熵为-log2(1/2) = 1 位，掷八面骰子的最小熵为-log2(8) = 3 位，而已知的比特币private key 长度为256位，足够强的私钥的最小熵应该高达256位，即黑客只能以1/256的2次方的概率猜测。这么高最小熵称为高阶最小值。 熵意味着它非常非常难以猜测。

计算机随机数函数的伪随机数算法是一种确定性算法（受停机问题约束），所以不能在结果上加上最小熵，即输出结果的最小熵等于最小值输入的熵。

如果输入是人为控制或猜测的，那么输入的熵就降为0，结果完全在黑客的预料之中。

从目前的分析，我们知道，“区块链世界”或“计算机世界”中是否存在真正的随机性？ 当然可以。 如何？ 将熵输入世界。

如何向区块链系统输入熵？ 我们可能会考虑以下一些方法：

1.让节点安装特殊的随机数硬件。 这种方法存在的问题是：（1）不是所有的节点都有这个硬件。 如果轮到没有这种硬件的节点出块怎么办？ (2) 区块链是开放的，如果节点故意作弊，使用假的、受控的硬件怎么办？ (3) 最大的问题是出块人所宣称的真随机数根本无法被其他节点和用户验证。 在这里，“真随机”和“可验证”是相互矛盾的！ 如果不可验证，则意味着其他节点和用户需要无条件信任（信任）出块节点的随机数为真，这与区块链非信任模型相矛盾！

2、使用外部随机数提供接口，也就是所谓的Oracle API。 这种方式也存在一些不容忽视的问题：（1）依赖外部预言机给区块链系统带来“中心化”和“信任依赖”。 外部 Oracles 是可以销毁的，也就是中本聪在邮件中所说的“砍头”。 (2)同上，最大的问题是其他人只能无条件地相信出块节点没有伪造结果，即使Oracle提供了真随机数，因为“真随机”和“可验证”是矛盾的. 事实上，加入Oracle不仅没有缓解“信任依赖”问题，反而进一步扩大了问题！

3. 从用户输入中获取熵。 问题：区块链是完全透明的，也就是说系统知道的用户输入的所有信息，黑客也可以知道，而且可以同时知道！ 从理论上讲，黑客可以使用相同的信息和相同的算法来模拟相同的结果。

4、不公开程序代码，即隐藏随机数生成逻辑。 问题：关闭代码只会让真正的用户怀疑是否有什么棘手的事情。 没有“公开”，公平正义就会受到质疑！ 正如中本聪在帖子中所写，像比特币这样的系统必须是开源的，这样每个人都可以相信这些规则是按照声称的那样实施的。 不过闭源对于真正的黑客高手用处不大，各种分析技术都可以轻松搞定。

5、尝试发明“真随机数”计算功能。 提问：发明这个“算法”的难度应该和解决“停止问题”差不多吧？ 哈哈哈哈。

6. 在区块链系统中引入一个“中央”随机数生成器，并要求每个人都信任它。 问：如果这种中心化也可以，那么其实区块链是可以取消的，直接改成中心化的多节点数据库技术肯定更好。

道路仿佛有千万条，一条条走不通！

真的没有办法吗？ 当然不是。 如果真是这样，就不会有中本聪发明的比特币。

3. 比特币如何实现内生去中心化随机性

好吧，让我们仔细看看比特币全球一万多个区块节点的随机选择。 我们会惊奇地发现：

1、比特币系统没有办法禁止节点操纵任何它可以操纵的输入，包括但不限于恶意改写时间戳、故意选择交易集、是否故意选择nonce等。

2、比特币系统不需要节点安装特殊的随机数硬件。

3、比特币系统不需要依赖外部随机数提供接口。

4、比特币系统不需要中央权威的随机数生成节点。

5、比特币系统的代码和数据完全公开，所有人都可以看到。

然后比特币系统实现了公平、公正、公开的区块生产者的随机选择。

也就是说，如果我们把整个比特币系统看成一个函数：B（区块高度）=区块节点，那么这个函数B有一个非常奇妙的特性，就是当它没有被“看到”时，它的结果是真正随机的，而一旦被“看到”，随机性就会迅速“坍缩”成一个确定的结果，而这个结果可以被其他节点验证。 了解过量子力学的朋友，此刻脑海中可能浮现出“薛定谔的猫”的场景吧？ 那么这里的“看见”就是后续的出块节点通过新的区块不断支持和见证的过程。

各位读者，请回想一下前面提到的“随机性”和“可验证性”的矛盾问题。 如何解决这个矛盾？ 答案只能是，当它没有产生时，它的随机性足够大，没有人可以预测。 一旦生成，它可以被公开记录并被任何人反复确认。 这种“薛定谔随机性”是最适合区块链的随机性。

而这种随机性就足够“真实”了。 因为如果能被“拉偏”，那么操盘手就可以在出块上获得很大的优势，进而赚取超额的比特币奖励！ 显然，当比特币已经如此有价值时，这并没有发生。 如果你不想，你不能。

比特币是无需许可的，这意味着恶意节点可以自由加入网络并操纵输入。 在这种情况下，比特币如何实现内生的、去中心化的真随机性？

这种随机性的来源是工作量证明（PoW）吗？ PoW 是两层 SHA-256 哈希运算，输入被黑客随意操纵。 散列运算必须在不添加任何随机性的情况下为给定输入提供确定性结果。

那么随机性的来源到底在哪里呢？

比特币就是这样一个非常特殊的系统，外部消耗能量形成内部自发秩序（有序的区块链账本）。 诺贝尔奖获得者普里高津发明了一个术语来描述这种系统，称之为“耗散结构”或“耗散系统”[4]。 生物体、企业组织、城市、国家，这些都是耗散系统。

一个耗散系统能够形成自发有序，需要满足三个条件：

1. 开放性。 系统应该保持开放。 比特币的无许可访问大大增加了它的开放性。

2. 不平衡。 系统必然存在持续的内部竞争，使系统远离均衡状态。 比特币的记账权竞争，即挖矿竞争，是比特币区块链账本的有序来源。

3.波动。 系统中的微小扰动都会通过系统的非线性回路雪崩式放大，就像所谓的“蝴蝶效应”一样。 比特币的区块链一直在分叉，一直选择最长的链作为主链，从而形成分形结构。

工作量证明将计算能力的波动引入系统作为竞争的基础。 这种竞争给系统带来了随机性。

接下来我们研究随机性的应用及其在比特币区块链中的操纵可行性。

4.随机性在比特币系统中的应用及作弊可行性分析

我们都知道比特币区块链中的区块头哈希是工作量证明哈希。

毫无疑问，根据密码学安全哈希算法的要求，哈希值的分布是均匀的，无论输入是否规则，输出值之间没有规律可循。 这些是防碰撞攻击、防第一原像攻击和防第二原像攻击的基本要求。

密码安全意味着作弊者只有一种尝试作弊的方法，那就是不断更改输入，直到他们找到适合他们兴趣的哈希值。

以猜测大小为例。 两个人打赌尚未生成的块的头哈希的最后一位是 0 还是 1。如果没有被操纵的情况，这是一个公平的均匀分布。

现在让我们假设一个人试图作弊。 那么他的方法是什么呢？ 其方法是利用自己的算力抢夺创建投注对象区块的权利，根据自己投注的结果来操纵哈希值。

一个显而易见的事实是，无论他们押注的区块高度是下一个还是后面几个，作弊者只能从押注区块的前一个区块生成的时间开始计算，因为计算需要依赖on 前一个块的头哈希被用作输入之一。

另外值得注意的是，这个问题与白皮书中中本聪通过隐藏区块实现双花欺诈的计算不同。 投注操纵问题是一个抢先交易问题。

具体来说，作弊者照常计算满足工作量证明要求的哈希值，即开头有几个0。 找到一个后，再看一下哈希的最后一位数字。 假设作弊者下注 0，那么如果 PoW 哈希的最后一位正好是 0，他就广播该区块； 否则，如果 PoW 哈希的最后一位是 1，他将丢弃该块。

换句话说，一旦作弊者挖出一个让他获胜的区块，他就会立即释放。 一旦他带头，他就可以吸引其他中立的算力来见证他操纵的区块进入主链。

制作：

p = 诚实节点找到有效区块的概率

q = 1 - p = 作弊节点找到有效区块的概率

诚实节点只要找到符合要求的合格区块，就会出块

作弊节点找到合格的区块后，根据是否满足自己的赌注，选择生产还是丢弃该区块（不满足的概率为r）

q_r = 作弊节点先于诚实节点出块的概率

找到 q_r = ?

利用概率论的一些知识，我们可以计算出答案如下：

对于两个人使用区块头哈希的最后一位进行赌注大小r=0.5的情况，那么作弊节点跑在前面的概率为q_r=0.5*q/(1-0.5*q ). 那么它的操纵胜率就是win=q_r * 1.0 + (1 - q_r) * 0.5。

一旦操纵成功，好处就是对手下注 bet_honest。 一旦失败，它的损失就是自己的bet_cheat加上区块奖励block_reward。 收入预期：

E_cheat = win * bet_honest - (1 - win) * (bet_cheat +block_reward)

而如果作弊者老老实实玩，那么他的输赢率就是0.5，0.5。 收入预期：

E_nocheat = 0.5 * bet_honest - 0.5 * bet_cheat + q *block_reward

由于操纵而导致的超额预期收益为：

作弊者的预期超额回报率为E_extra/bet_cheat，等于：

为使预期超额收益率大于0，需满足：

bet_honest + bet_cheat > 2 * (1 + q + 1/q) * block_reward

令 miu = 2* (1 + q + 1/q) 为“超额投注因素”。

并且假设双方下注金额相等比特币放一万个地址碰撞私钥，且远大于miu*block_reward，可以忽略区块奖励，则ROR_max=0.5*q/(1-0.5*q)。 这恰好等于 q_r。

试算作弊节点掌握的算力比例q、抢跑成功概率q_r、操纵胜率win、超赌系数miu、预期超额收益率ROR_max比较如下：

q=0.001 q_r=0.0005003 win=0.5002501 miu=2002.0020000 ROR_max=0.0005003

q=0.01q_r=0.0050251 win=0.5025126 miu=202.0200000 ROR_max=0.0050251

q=0.1 q_r=0.0526316 win=0.5263158 miu=22.2000000 ROR_max=0.0526316

q=0.3 q_r=0.1764706 win=0.5882353 miu=9.2666667 ROR_max=0.1764706

q=0.5 q_r=0.3333333 win=0.6666667 miu=7.0000000 ROR_max=0.3333333

q=0.8 q_r=0.6666667 win=0.8333333 miu=6.1000000 ROR_max=0.6666667

q=0.9 q_r=0.8181818 win=0.9090909 miu=6.0222222 ROR_max=0.8181818

可以看出，如果你的对手拥有比特币全球10%的算力，那么你的总投注额需要大于22个区块奖励，也就是今天的275个比特币以上。 假设你们每人下注 200 个比特币。 此时，他冒着 47% 的概率失去自己的 200 个比特币的风险，赚取 5% 或 10 个比特币的超额收益（这还没有扣除区块奖励的机会损失）。 这对他来说不是一个非常理性的选择。

而如果他掌握了一半以上的算力，理论上就不需要靠操纵取胜了。 完全有可能对比特币网络发起双花攻击，谋取更大利益。

5.弱化PoW甚至放弃PoW共识机制意味着弱化和放弃安全随机性

根据以上分析，比特币采用的PoW共识机制实现了去中心化的安全随机性。

任何弱化和放弃这种共识机制都会减少熵的引入，从而削弱安全随机性，由此带来的中心化依赖增加会增加系统脆弱性。

这种必然性受到计算机停机问题的限制，并且在数学上最终受到哥德尔不完备性定理的限制。

任何试图降低 PoW 能量消耗的设计，都会增加系统的确定性，节省黑客试图破解随机数的成本，从而给黑客更多的时间和空间来完成破解。

PoW本质上是一种映射函数，将物理世界的热力学过程映射到数字世界的比特过程，是连接两个世界的“虫洞”。

黑客无法在物理世界中逆转热力学第二定律，也无法在数字世界中逆转比特过程。 只能重复，不能逆转。 这也是时间之箭的单向性。

去中心化的随机性和去中心化的时间之箭是比特币系统中暗藏的秘密武器。

因此，中本聪在比特币白皮书第2页第3节开头的第一句话中写道[5]：

我们提出的解决方案从时间戳服务器开始。

（全文）

参考：

[1]

[2] 唐纳德·克努特。 计算机编程艺术。 第 2 卷第 3 章。

[3] 伊曼纽尔·康德。 纯粹理性批判。

[4] 伊利亚·普里高津。 时间、结构和波动。

[5] 中本聪。 比特币：一种点对点电子现金系统。