巴比特专栏

　　一、菠菜类应用成了黑客的提款机
　　自去年EOS主网上线以来，菠菜类应用成了EOS平台的＂主流＂应用。但是，因为EOS内在机制的缺陷，让菠菜类应用纷纷沦为黑客的刀下肉，成了黑客的提款机。一个较为知名的案例是EOSDice两度被黑客攻破。
　　黑客的攻击手法暴露了一个非常底层而本质的问题：区块链随机数的安全性问题。
　　以EOSDice为例[1]。第一版本它是实时开奖，用户在当前区块下注时，它通过智能合约代码把上一个区块的信息以及帐户名、id、开奖时间、合约余额信息作为随机数函数的种子，计算出随机数生成结果作为中奖依据。
　　黑客发现：开奖代码所用的随机数函数其实生成的是确定性序列，随机性的来源是种子。而区块链上一切数据都是公开透明的，代码也是开源的。因此，掌握了种子信息和计算逻辑不就可以直接推算出来押注哪里必赢了吗？
　　黑客必赢手法：根据全部已知信息进行模拟运算，推算出必赢押注。
　　EOSDice团队迅速修改了代码，把实时开奖改成了延时开奖。也就是说，顺延一个区块，到下下个区块再执行开奖代码，这样就可以让随机数函数种子使用下个区块的信息——这个在当前下注时还不存在的信息。看似无懈可击了吗？
　　黑客又一次发现：既然现在无法拿到信息，但是可以现在写个一模一样的算法代码，到未来信息出现的时候再运行不就可以了吗？
　　黑客必赢手法：提前写一个和开奖代码一样的伴娘代码，但是让它和开奖代码一样延时到下个区块运行，这样就可以算出来必赢的押注了，然后让这个伴娘代码按照必赢押注进行注资。
　　EOSDice这次只好把余额从种子计算的输入中去掉，以免黑客随意改变押注金额操纵种子，进而操纵看似＂随机＂的开奖结果。
　　于是有安全研究人员大声疾呼：＂区块链的世界没有真正的随机数＂，甚至更进一步的，＂计算机的世界没有真随机数＂。
　　在笔者（公众号：刘教链）看来，上述命题的外延并不清晰，需要刨根问底、一探究竟：
　　1、仅仅是因为EOS的伪随机函数被黑客攻击，就可以扩大化到区块链甚至计算机没有真随机吗？
　　2、仅仅是因为伪随机函数不能产生真随机数，就可以如此轻易得出不含任何前提条件的＂绝对命题＂（categorical judgement）吗？这意味着上述两个命题应该在时空任意之处都绝对正确，也意味着只要找到一个反例就足以推翻。
　　同时，命题的内涵也具有相当的模糊性，这会导致不同读者产生不同的概念联想并被误导：
　　1、存在性：怎么定义一个东西在＂区块链世界＂和＂计算机世界＂有或者无？＂没有＂的意思是指无论通过任何方法也不能有吗？如果不是，那＂没有＂的具体内涵又是什么？
　　2、真实性：怎么定义＂真随机数＂？什么才是真随机？真随机可以被确证吗？
　　下面我们就来看一看这些问题。
　　二、随机数的定义和及其密码学安全性
　　快速了解现代冯诺伊曼架构计算机中随机数问题，可以翻阅美国计算机科学家、1974年图灵奖获得者高德纳（Donald E. Knuth, 1938-）的堪称计算机科学理论与技术的经典巨著《计算机程序设计艺术》（TheArt of Computer Programming，缩写TAOCP）的第二卷＂不完全数值计算算法＂之第三章＂随机数＂。
　　仅仅这一章就有着长达170页的篇幅[2]。其中综述了计算机随机数问题的研究历史和成果。笔者（公众号：刘教链）给各位读者简要概述一下，很有趣味：
　　首先，高老先生回顾了一下随机数研究历史，然后说，究竟什么是随机数，这其实是一个哲学问题，也就是得先搞清楚＂我是谁＂（怎么定义）这个问题。
　　然后，高老先生就引述一个前人给出的定义，接着说，嗯，按照这个定义的话，我想，整个宇宙中可能就不存在真正的随机数了！好吧，我们还是换个更＂宽松＂的定义吧！
　　再然后，高老先生换了一个＂宽松＂一些的定义，写了一个算法说，大家看我构造的这个随机数算法，其实根本就不能称之为＂算法＂！为什么？因为这个＂算法＂根本就不能保证输出结果（计算机术语称之为＂停机问题＂）！只好再弱化要求。
　　接下来，就是洋洋洒洒，给大家讲解各种弱弱的＂随机数＂算法，这个好一点儿，那个差一点儿，等等。总之，高老先生就是不断地在暗示同学们，这些算法嘛，各有各的坑，大家小心点儿用。
　　最后，布置习题。完。^_^
　　高老先生已经开门见山地告诉我们了，一个确定性的算法所生成的＂随机数＂是什么随机数？伪随机数！也就是说，计算机那个叫做＂random＂（随机）的函数其实所生成的是一种大大弱化了的、看起来像随机数的＂随机数＂。
　　这些随机数函数所产生的的结果的随机性将取决于外部给它的随机性，比如通过所谓的＂种子＂参数。一旦知道了种子，它所计算出来的随机数序列就是确定性的。
　　是不是就可以下结论说，计算机就没有办法产生真随机数了呢？如果这句话的意思是限定计算机的方法为伪随机数算法的话，那么这就不啻为一个＂分析命题＂（analytical judgement）：
　　伪随机数算法没有办法产生真随机数。
　　上面这个分析命题的正确性和下面这个分析命题是一样的：
　　黑天鹅不是白的。
　　众所周知，分析命题先验为真[3]。并没有讨论的必要。
　　我们需要讨论的，永远是怎么解决问题。就像中本聪克服＂FLP不可能＂解决拜占庭问题一样。
　　在密码学上，随机性是非常重要的，无论是资产控制私钥的安全性，还是椭圆曲线数字签名算法的签名过程安全性，都需要良好的随机数。当然，文初提到的菠菜，可能也需要良好的随机数。
　　密码学安全的随机数，比用于统计模拟的随机数，对随机性的要求就要更高、更严格。考虑起来，其分布需要均匀，且不可被操纵导致出现分布偏差，其发生不可预测，每次发生之间保证良好的独立性。
　　在密码学里，我们把这种随机数（的来源）叫做＂高阶最小熵＂（highmin-entropy）。其要求统计学上＂均匀分布＂的＂独立同分布＂（Independentand identically distributed, i.i.d.）。
　　比如扔一个两面均匀的硬币的最小熵是-log2(1/2)= 1比特，扔一个八面均匀骰子的最小熵是-log2(8)= 3比特，而大家知道的比特币私钥的长度是256比特，足够强壮的私钥其最小熵应该可以高达256比特，也就是黑客随便猜一下只有2的256次方分之一的概率能猜中，这么高的最小熵就叫做高阶最小熵，意思就是非常非常不容易被猜中。
　　计算机随机数函数的伪随机数算法是确定性算法（受停机问题约束），因而并不能为结果增加最小熵，也就是说，其输出结果的最小熵等于输入的最小熵。
　　如果输入被人为控制或猜中，那么输入的熵就减小到0，结果也就完全在黑客的预料之中了。
　　分析至此，我们就知道了，＂区块链的世界＂或者＂计算机的世界＂里可不可以有真随机？当然可以有。怎么有？给这个世界输入熵。
　　怎么给区块链系统输入熵？我们可能会考虑如下一些方法：
　　1、让节点加装特殊的随机数硬件。这个方法是有问题的：（1）不是所有的节点都有这个硬件，轮到没有这种硬件的节点出块怎么办？（2）区块链是开放的，如果节点故意作弊，使用假冒的、受控的硬件怎么办？（3）最大的问题是，出块节点声称的真随机数其他节点和用户完全无法验证，在这里，＂真随机＂和＂可验证＂互相矛盾！如果不可验证，就意味着其他节点和用户需要无条件信任（trust）出块节点的随机数是真的，这又和区块链非信任模型相矛盾！
　　2、使用外部的随机数提供接口，也就是所谓的OracleAPI。这个方法同样有一些无法忽视的问题：（1）依赖外部Oracle就是给区块链系统带来了＂中心化＂和＂信任依赖＂，外部Oracle可以被摧毁，也就是中本聪邮件里说的＂cutoff the head（斩首）＂。（2）同上，最大问题也是，其他人只能无条件相信出块节点没有伪造这个结果，即使Oracle提供的是真随机数，因为＂真随机＂和＂可验证＂矛盾。增加Oracle其实不仅没有缓解＂信任依赖＂问题，反而把这个问题进一步扩大化了！
　　3、从用户输入中获取熵。问题：区块链是完全透明的，这意味着，系统知道的所有的用户输入的信息，黑客也同样可以知道，而且可以在同一个时间知道！理论上讲，黑客完全可以利用同样的信息、同样的算法模拟出同样的结果。
　　4、不公开程序代码，也就是隐藏随机数生成逻辑。问题：封闭代码只会让真实用户怀疑其中是否有猫腻。没有了＂公开＂，公平公正性就会受到质疑！正如中本聪在帖子里写的，比特币这种系统必须开源，大家才能相信这些规则是按照声称的来实现的。而闭源这东西反而对真正的黑客高手没什么大用，各种分析技术轻而易举就搞定了。
　　5、试图发明＂真随机数＂计算函数。问题：发明这种＂算法＂的难度和解决＂停机问题＂应该是差不多的吧？哈哈哈哈。
　　6、给区块链系统引入一个＂中心的＂随机数发生器，要求大家都信任它。问题：如果这种中心化也能接受，那么其实就可以不用区块链了，直接全面改成中心化多节点数据库技术一定更好。
　　看起来，道路千万条，条条走不通呀！
　　真的没有路了吗？当然不是。如果真的是这样，就不会有中本聪发明的比特币了。
　　三、比特币是如何实现内生的去中心化随机性的
　　好了，让我们仔细考察一下比特币的全球一万多个出块节点的随机选择问题吧。我们会惊奇地发现：
　　1、比特币系统没有办法禁止节点操纵任何它能够操纵的输入，包括但不限于时间戳恶意改写、交易集刻意选择、nonce是不是特意选择的，等等。
　　2、比特币系统不要求节点安装特别的随机数硬件。
　　3、比特币系统不需要依赖外部的随机数提供接口。
　　4、比特币系统不需要一个中心的、权威的随机数发生节点。
　　5、比特币系统的代码和数据完全公开，人人可见。
　　然后比特币系统实现了对于出块节点的公平公正公开的随机选择：
　　也就是说，如果我们把整个比特币系统看作一个函数：B(区块高度) = 出块节点，那么这个函数B有一个很奇妙的特点，那就是，在没有被＂看见＂的时候，它的结果是真随机的，而一旦被＂看见＂，随机性就会迅速＂坍缩＂成为一个确定的结果，而且这个结果可以被其他节点验证。了解过量子力学的朋友此刻脑海中可能会浮现出＂薛定谔的猫＂的场景哈？那么这里的＂看见＂，则是后续出块节点通过新区块不断加持和见证的过程。
　　亲爱的读者朋友请回想一下前面说到的，＂随机性＂和＂可验证＂相矛盾的问题吧。这个矛盾怎么化解？答案只能是，未产生时具有充分随机性从而无人可以预测，一旦产生则可以公开记录下来被任何人反复确证，这种＂薛定谔随机性＂才是最适合区块链的随机性。
　　并且这个随机性是足够＂真＂的。因为如果它可以被＂拉偏＂，那么操纵者就可以获得出块的极大优势，进而赚取超额的比特币奖励！显然，比特币已经如此值钱的情况下，这一情况并未发生。非不愿也，实不能也。
　　比特币是无许可的（permissionless），也就是恶意节点可自由加入网络并操纵输入。在这种情况下，比特币又是如何实现内生的、去中心化的真随机性的呢？
　　这个随机性的来源是工作量证明（Proof-of-work, PoW）吗？PoW是两层SHA-256哈希运算，而输入是黑客随意操纵的，哈希运算对于给定的输入必然给出确定性的结果，不会增加任何随机性。
　　那么随机性的来源到底在哪儿呢？
　　比特币是这样一种非常特别的系统，它对外消耗能量，形成内在的自发秩序（有序的区块链账本）。诺奖得主普利高津发明了一个术语来描述这种系统，称之为＂耗散结构＂或者＂耗散系统＂[4]。生命有机体、公司组织、城市、国家，这些都是耗散系统。
　　一个耗散系统能够形成自发秩序，有三个条件：
　　1、开放性。系统要保持开放。比特币的无准入许可极大增加了其开放程度。
　　2、非平衡性。系统要有持续的内部竞争，以系统远离平衡态。比特币的记账权竞争，也就是挖矿竞争，乃是比特币区块链账本的有序之源。
　　3、涨落。系统中微小的扰动会通过系统的非线性回路雪崩式放大，就像所谓的＂蝴蝶效应＂。比特币的区块链无时无刻不在分叉，又无时无刻不在选择最长链作为主链，从而形成一个分形结构。
　　工作量证明把算力涨落引入系统，作为竞争依据，这种竞争，为系统带来了随机性。
　　接下来我们考察一下比特币区块链中的随机性应用及其操纵可行性。
　　四、比特币系统随机性应用和作弊可行性分析
　　我们大家都知道，比特币区块链中的区块头哈希是符合工作量证明要求的哈希值。
　　毋庸置疑，根据密码学安全哈希算法的要求，哈希值的分布是均匀的，而且，无论输入是否有规律性，输出值之间都是没有规律可循的。这些是防碰撞攻击、防第一原像攻击和第二原像攻击的基本要求。
　　密码学安全意味着，作弊者只有一种方法来尝试欺诈，就是不断改变输入，直到找到符合自己利益需要的哈希值。
　　比如以猜大小为例。两人打赌某个尚未生成的区块的头哈希值的最后一位比特是0还是1。如果没有操纵的情况，这是一个公平的均匀分布。
　　现在让我们假设有一个人试图作弊。那么他的方法是什么呢？方法就是使用自己的算力去抢夺打赌的对象区块的创建权，并按照按自己下注的结果去操纵哈希值。
　　一个明显的事实是，无论两人打赌的区块高度是下一个，还是若干个之后，作弊者都只能从所赌区块的前一个区块产生出来的时候开始计算，因为计算需要有赖于这前一个区块的头哈希值作为输入之一。
　　另外一个值得注意的是，这个问题和中本聪在白皮书里计算通过隐藏区块来实现双花欺诈不同，打赌操纵的问题是一个抢跑问题。
　　具体的，作弊者和平常一样计算符合工作量证明要求的哈希，也即是开头有若干个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个比特币的超额收益（这还没扣掉区块奖励的机会损失）。这对他而言不是一个非常理性的选择。
　　而如果他掌握了超过一半的算力，理论上他就不需要靠操纵开大小取胜了。完全可以对比特币网络发动双花攻击，谋取更大的利益。
　　五、弱化PoW乃至放弃PoW共识机制就是弱化和放弃安全随机性
　　根据上面的分析，比特币采用的PoW共识机制，实现了去中心化的安全随机性。
　　任何对这一共识机制的弱化和放弃，都将减少熵的导入，进而弱化安全随机性，以及因此而带来的中心化依赖程度的增加又会增加系统脆弱性。
　　这一必然性由计算机的停机问题所限定，并在数学上，最终由哥德尔不完备定理所约束。
　　任何试图减少PoW对能量消耗的设计，都会给系统增加确定性，并节省黑客尝试攻破随机数的代价，从而给予黑客更多的时间和空间来完成破解。
　　PoW本质上是一个映射函数，把物理世界的热力学过程映射成数字世界的比特过程，是一个连接两个世界的＂虫洞＂。
　　黑客无法逆转物理世界的热力学第二定律，也就无法逆转数字世界的比特过程。只能重演，不能反演。这也正是时间之矢的单向性。
　　去中心化的随机性，以及去中心化的时间之矢，这两点正是比特币系统中深藏不露的秘密武器。
　　因此，中本聪在比特币白皮书第2页第3节开头第一句就这样写道[5]：
　　我们提出的解决方案从一个时间戳服务器开始。
　　（全文完）
　　参考文献：
　　[2] Donald Knuth. The Art of Computer Programming. Volume 2.Chapter 3.
　　[3] Immanuel Kant. Critique of Pure Reason.
　　[4] Ilya Prigogine. Time, Structure and Fluctuations.
　　[5] Satoshi Nakamoto. Bitcoin: A Peer-to-Peer ElectronicCash System.
　　本文作者：刘教链（公众号：刘教链）