Not a fair game, Dice2win 公平性分析

Dice2win 目前是以太坊上一款异常火爆的区块链博彩游戏。号称“可证明公平的”Dice2win 目前每日有近千以太 (一百五十万人民币) 的下注额,是总交易量仅次于 etheroll 的第二大以太坊博彩游戏。然而我们分析发现,dice2win 中的所有游戏都存在公平性漏洞,庄家可以利用这些漏洞操纵游戏结果。

Dice2win 游戏介绍

Dice2win 目前有包括“抛硬币”、“掷骰子”、“两个骰子”、“过山车”几款游戏。其介绍如图:

在这些游戏中,每个用户单独下注与庄家进行一对一对赌。游戏的本质,是用户和庄家在去中心化的以太坊智能合约平台上通过一系列协议来生成随机数。如果用户猜中随机数,则用户胜利,否则庄家胜利。

在进一步介绍 Dice2win 工作流程和公平性分析之前,我们先讨论一个历史悠久的密码学问题:Mental poker。 Mental poker 是由 Shamir, Rivest 和 Adleman 1978 年在文章“Is it possible to play a fair game of ‘Mental Poker”中首次提出的概念。(Shamir, Rivest 和 Adleman 有没有很眼熟?没错,就是你知道的 RSA) 其本质是想解决:在没有可信第三方的参与的情况下 (可信平台或软件),两个不诚实的参与方如何在网络上进行一场公平的棋牌游戏。在公平性的定义中,有非常重要的一点:如果任何一方收到了游戏结果,那么所有的诚实方都应该收到结果。

Dice2win 实际上是利用区块链实现 mental poker 的典型案例。但我们发现,Dice2win 并不满足 mental poker 的公平性安全。

选择性中止攻击

这里我们来看看 Dice2win 的工作原理。Dice2win 游戏的本质,是用户和庄家在去中心化的以太坊智能合约平台上通过一系列协议来生成随机数。如果用户猜中随机数,则用户胜利,否则庄家胜利。游戏总体工作流程如下:

  1. 【庄家承诺】庄家 (secretSigner) 随机生成某随机数 reveal,同时计算 commit = keccak256 (reveal)对该 reveal 进行承诺。然后根据目前区块高度,设置一个该承诺使用的最后区块高度 commitLastBlock。 对 commitLastBlock 和 commit 的组合体进行签名得到 sig,同时把 (commit, commitLastBlock,sig) 发送给玩家。
  2. 【玩家下注】玩家获得 (commit, commitLastBlock,sig) 后选择具体要玩的游戏,猜测一个随机数 r,发送下注交易 placeBet 到智能合约上进行下注。
  3. 【矿工打包】下注交易被以太坊矿工打包到区块 block1 中,并将玩家下注内容存储到合约存储空间中。
  4. 【庄家开奖】当庄家在区块 block1 中看到玩家的下注信息后。则发送 settleBet 交易公开承诺值 reveal 到区块链上。合约计算随机数 random_number=keccak256(reveal,block1.hash)。如果 random_number 满足用户下注条件,则用户胜,否则庄家胜。此外游戏还设有大奖机制,即如果某次 random_number 满足某个特殊值 (如 88888),则用户可赢得奖金池中的大奖。

Dice2win 在其官网和白皮书宣称自己的游戏具有数学上可证明的公平性,其随机数是随机数生成过程由矿工和庄家共同决定,矿工或者庄家无法左右游戏结果,所以玩家可以放心下注。此外,在一些介绍以太坊智能合约安全的文章中,我们也看到一些作者将 Dice2win 的随机数生成过程称为极佳实践。

然而我们分析发现,dice2win 中的所有游戏都会受到庄家选择性中止攻击,庄家可以选择性公布中将结果从而导致用户无法获胜或赢得彩票。我们考虑如下两个攻击场景:

场景 1:

用户下注额大,且赔率高的情况下。用户下下注产生 block1 后,block1.hash 实际上就已经固定了。此时庄家已经可以计算出 random_number,从而计算出用户的投注结果和盈亏。则庄家可以选择性中止交易。如果用户不中奖,则庄家公布正常开奖结果。如果用户中奖,则庄家可因为“网络用户和技术原因”从而导致用户该笔下注失效。

场景 2:

用户下注额不大,但是 block1 产生后庄家发现 random_number 导致用户中彩票。则庄家可以选择性中止交易,导致用户该笔下注失效。

在这两种攻击场景下,庄家都能够轻松控制交易结果。当然庄家并不会对每笔交易都发起这种攻击,而是可以选择用户获奖特别大的交易进行操控。Dice2win 官方实际上已经在智能合约代码得注释中声明了可能会发生“技术问题和以太坊拥堵”原因造成荷官无法开奖 (大约 1 个小时内),则用户可以提回下注款。

造成该漏洞的本质原因在于,该方案的随机数对于庄家而言并不是真正的随机。庄家可以提前知道下注的结果。想一想如果你去一个声称“绝对公平”的赌场赌骰子。在完成下注后,庄家是有一种方法先偷看一眼骰子结果,算一算盈亏之后再决定是否开奖 (重摇),这样的骰子,是真的随机的吗?

实际上选择性中止攻击 (selective abort attack) 是针对 mental poker 公平性一种最常见的攻击方式。要修复该问题实际也很简单,只要以惩罚机制强制要求庄家在限制时间内打开承诺便可解决该问题。其他的适用于 mental poker 或安全多方计算的随机数生成算法均可在此处适用。

选择性开奖攻击

选择性中止攻击的修复实际上非常简单,要求庄家在限定时间内打开承诺便可。但这并没有从机制上完全消除 Dice2win 庄家在游戏中的优势。是不是简单的直接引入其他 mental poker 或安全多方计算的随机数生成算法到区块链智能合约平台上,就可以解决该问题了呢?实际上也未必能真正保证游戏的公平性。这里我们称述一个我们有趣的发现: 区块链智能合约上玩家交互的通讯模型,与传统的互联网用户点对点通讯模型是有区别的。传统的点对点通讯模型下证明的安全协议,直接套用到智能合约平台上未必能保证其安全性。核心原因在于:传统的点对点通讯模型下,协议的执行是顺序的,不可逆的。而智能合约的通讯模型中,由于 POW 等共识算法存在分叉的可能性,协议的执行可能是非顺序的可逆的。在下图中,假设黑色区块为网络主链,白色区块是分叉区块。如果一个安全多方计算的协议步骤(某笔交易)在白色执行,那么该交易将不会生效。例如 Alice 和 Bob 在区块链上进行某种计算。Alice 在区块 B5 上执行某笔交易,Bob 随后在区块 B6 上公布某个秘密。随后因为网络发生分叉,B5、B6 上的交易都失效了。但是 Alice 却收到了秘密。

以太坊使用“幽灵协议 (GHOST protocol)”来选择区块成为主链。分叉块包括叔块和孤块。下图中我们可以看到,当前以太坊叔块的概率已经达到 10% 以上。所以直接简单的将 mental poker 和安全多方计算的一些协议移植到智能合约平台上时,发生不稳定事件的概率是不可忽略的。

解决该问题的最直接的方法是,智能合约中协议的每步执行之间等待足够长的时间。当我们有接近 100% 把握上一个一笔交易已经在区块中稳定了,再执行下一笔交易。但这样的方式,一次交互可能要等待多个区块(数分钟的时间)才能完成。对于博彩游戏而言,显然是不可接受的。

事实上在 Dice2win 在上个月已经意识到叔块所带来的问题了,并声称他们的提出的 MerkleProof 方法可以解决该问题,从而使得游戏变得公平。并在 commit 中提出了使 MerkleProof 的方法来对叔块中的下注进行开奖(https://github.com/dice2-win/contracts/commit/86217b39e7d069636b04429507c64dc061262d9c)。 现在我们看看 Dice2win 如何解决这个问题。在 Dice2win 的代码中(https://github.com/dice2-win/contracts/blob/b0a0412f0301623dc3af2743dcace8e86cc6036b/Dice2Win.sol),我们可以看到看到方法 settleBetUncleMerkleProof(uint reveal, uint40 canonicalBlockNumber):

Dice2win 官方提出的 MerkleProof 方法的核心逻辑在于:为了提高用户体验(开奖速度),当荷官收到一个下注交易 (Tx) 的时候(假设在 B5 区块),就立刻计算出该下注结果并对该交易进行开奖。然而由于 GHOST 算法原因,最终主网选择了 A5 区块作为主链上的块(与 B5 区块 hash 值不同,所以开奖结果不一样)。那么此时,按合约原本 SettleBet 的方法是无法对 B5 区块进行开奖的。针对这个问题,Dice2win 的解决办法是:直接对叔块进行开奖就好了。

如何对叔块进行开奖呢:因为叔块的 hash 是包含在主链上某个合法的区块上的。而以太坊的区块结构中又有非常多的哈希关联结构。具体我们可以看看以太坊区块头的定义:

所以我们能够从 B5 中交易 Tx 的交易执行结果 Receipthash,一直计算向上层计算哈希得到叔块 B5 的 ReciptsRoot。然后再与其他结构进行 Hash 得到叔块 B5 的区块 hash(我们称为 uncleHash)。假设 A6 区块中引用了叔块 B5 的 uncleHash, 那么我们最终以 A6 的 canonicalHash 作为根节点,构造一个非结构性 Merkle Tree。交易 Tx 为其中一个叶节点。其结构图如下:

Dice2win 提出的 Merkle proof 算法的思路在于:当分叉块产生时 (如同时产生 B5 与 A5),网络可能有两种开奖结果出现。但因为网络原因,荷官可能先收到其中一个块(假设为 B5)。从荷官的视角来看,它并不知道 B5 是否会称为主链上的块。即使荷官多等待一段时间,收到了(A5、A6、B6)后,它仍然无法确定哪条链会称为主链。为了提高开奖速度,当荷官收到某个交易块之后,就马上进行开奖。如果该交易块最后成为主链 (A5),则正常使用 SettleBet 方法开奖。如果该区块最后成为叔块 (B5),则提交由该交易执行结果为叶根节点、引用该叔块的主链块 canoinicalHash 为根节点的非结构性 Merkle tree(如上图)的一个存在性证明 (Merkle proof)。从而证明 B5 确实存在过,且交易 Tx 包含在 B5 中;荷官可以使用叔块进行开奖。

Dice2win 的 Merkle proof 算法看上去是一个解决以太坊上去中心化博彩游戏开奖速度的很好的思路。但实际上该做法并不公平,以太坊上接近 10% 的叔块率可以导致荷官以比较大的优势可以根据游戏结果进行选择性开奖。如果 A5 庄家赢就开 A5,如果 B5 庄家赢就开 B5。这样的方案显然不公平。

任意开奖攻击(Merkle proof 验证绕过漏洞)

在详细阅读 Dice2win 关于 Merkle proof 的实现后,我们发现目前该合约的非结构性 Merkle Proof 验证存在诸多绕过方法。即荷官可以伪造一个叔块 B5 的 Merkle proof,欺骗合约实现对任意结果进行开奖。

一次已经发生过的 Merkle proof 验证绕过攻击分析

同时,我们翻阅合约历史发现其实上个月就已经有攻击者实现了对该 Merkle proof 算法的绕过,将该版本的合约余额洗劫一空 (但该情况为引起社区重视,Dice2win 官方对该事件进行了冷处理)。在介绍我们的漏洞之前,我们可以先看看这个已发生对该 Merkle proof 验证算法的攻击方法。其中一笔攻击交易发生在: https://etherscan.io/tx/0xd3b1069b63c1393b160c65481bd48c77f1d6f2b9f4bde0fe74627e42a4fc8f81

攻击者通过创建攻击合约 0xc423379e42bb79167c110f4ac541c1e7c7f663d8,并在合约 0xc423379e42bb79167c110f4ac541c1e7c7f663d8 调用 placeBet 方法自动化进行下注(17 次下注,每次 2 以太)。然后伪造 Merkle proof, 调用 settleBetUncleMerkleProof 方法开奖,在赢取了 33 以太后将奖金转到账户 0x54b7eb670e091411f82f50fdee3743bd03384aff,最后合约自杀销毁。通过对该合约 bytecode 的逆向分析,我们可以得知该攻击利用了如下漏洞:

  1. Dice2win 不同版本的合约,存在 secretSigner 相同的情况。导致一个庄家的承诺可以在不同版本的合约中使用。【运维原因产生的安全漏洞】
  2. placeBet 方法中对 commit 的过期校验可被绕过。commitLastBlock 与当前 block.number 进行大小判断时是 uint256 类型的。然后再带入 keccak256 进行签名验证的时候却转换成了 uint40。那么攻击者将任意一个 secretSigner 签名的 commitLastBlock 的最高位 (256bit) 从 0 修改为 1,则可绕过时间验证。【漏洞在最新版本中仍未修复,详细见下图】

  1. Merkle proof 校验不严格。在该版本的 settleBetUncleMerkleProof 中,每次计算 hashSlot 偏移的边界检查不严格 (缺少 32byte),导致攻击者可以不需要将目标 commit 绑定到该 Merkle proof 的计算中,从而绕过验证。【该漏洞已修复,详见下图】

Merkle proof 验证绕过漏洞

经过我们分析,Dice2win 目前版本的 Merkle proof 仍然存在多种绕过方法。由于该方法目前只能由荷官调用,所以普通攻击者无法利用该漏洞。但该漏洞可以作为荷官后门实现任意开奖。 这里我们大致整理当前验证算法的验证逻辑:

  1. 先调用 requireCorrectReceipt 方法校验 Receipt 格式满足条件。
  2. Recipt trie entry 中包含的是一个成功的交易。
  3. 交易的目标地址是 Dice2win 合约。
  4. Merkle Proof 验证计算的起始叶节点包含目标 commit。
  5. 最后计算得到的 canonicalHash 是一个合法的主链块哈希。 条件 1、2、3 的满足并不是强绑定的,我们只要构造满足条件的数据格式就可以了。条件 4、5 的绕过,本质上是要迭代计算: hash_0=commit hash_{n+1}= SHA3(something_{n1},hash_n,something_{n2}) canonicalHash=hash_{lastone}

攻击方法 1:

一个执行成功的叔块交易中包含目标 commit 并不是什么难构造的事情。荷官可以在某个合约调用交易的 input 输入里面塞入该 commit 就能绕过。当然该绕过方法比较麻烦。

攻击方法 2:

由于 hash_{n+1}= SHA3(something_{n1},hash_n,something_{n2}) 的迭代计算未进行深度检查。所以荷官可以在本地生意一个新的 merkle tree, 该 merkle tree 的叶节点满足 1、2、3 条件且包含多个 commit_i。将该 merkle tree 的根 hash 嵌入到一个正常的区块中,就能生成一个合法的证明。在该攻击方法中,荷官可以一劳永逸,对所有的 commit 进行任意开奖。

这些绕过方法的核心问题在于:目前该非结构化的 Merkle tree 实际上并不满足我们常说的 Merkle hash tree 的结构。常规的 Merkle hash tree 在加强限制的条件下能够进行存在性证明,但 Dice2win 的非结构化 Merkle 证明算法难以实现该目的。

其他安全问题:

当用户下注未被开奖,用户可以调用 refundBet 来溢出 jackpotSize,造成 jackpotSize 变为一个巨大的整数 (由 Gaia 发现并指出)。

后记

  1. Dice2win 并不是一个公平的博彩游戏。
  2. 智能合约的安全问题非常严峻。(这实际上是我分析的第一个智能合约)
  3. 传统的安全多方计算的协议有时不能简单套用的到智能合约环境中,因为其通讯模型有区别。

本文链接:http://blogs.360.cn/post/Fairness_Analysis_of_Dice2win.html