陷阱
一个哈希是三十二字节。而游戏需要一个介于0和1之间的数字。得到这个数字最直接的方法,是把部分字节当作整数读取,再除以可能的最大值,几乎所有可验证公平的说明文章,包括我们自己的,都是这样描述的。但这个看似直接的方法,存在一个只有在两个不同程序各自实现时才会暴露的问题。
服务器和浏览器都以IEEE 754双精度浮点数存储普通数字:64位,其中53位携带精度。哈希的七个字节是56位,八个字节是64位,两者都放不下。因此转换过程必然会丢失一些位,问题不在于是否会舍入,而在于会舍入多少次。一个逐字节累加的循环,每次把累计值乘以256再加上下一个字节,一旦总值超过2⁵³,就会在每一步都发生一次舍入。而Kotlin将64位整数转换为双精度数时,只舍入一次。同一个值经过两次舍入,未必会落在与一次舍入相同的双精度数上。
大多数时候没人会注意到,因为差异只出现在一个有十六位有效数字的数字的最后一位。但当游戏把这个数字乘以37、或52、或1,000,000,再向下取整时,最后一位恰恰就是决定36.9999999999999变成36还是37的那一位。一个按“显而易见”的方式构建的验证器,会拒绝一小部分完全诚实的回合,而看到这种拒绝的玩家,根本无法分辨这是诚实的舍入误差,还是服务器在作弊。
引擎是如何避开这个问题的
解决办法是让浏览器的舍入次数与服务器完全一致——也就是一次。引擎读取前四个字节作为一个整数,这个整数可以精确地放入双精度数中,再读取接下来的三或四个字节作为另一个整数,同样可以精确放入。每个数分别除以2的幂,这一操作对双精度数来说是精确的。然后把两者相加。这一次加法,是唯一会损失精度的地方,而它损失精度的方式,与Kotlin的单次转换完全相同。
ENGINE-VERIFIED_shared/rng.ts u56:“前7个字节→均匀分布于[0,1),与服务器的Long→Double舍入逐比特匹配:hi/2^32和lo/2^56都是精确的二进制小数双精度数,因此那一次IEEE加法只会将56位的值精确舍入一次——与Kotlin的toDouble()执行的那次单一舍入完全相同。(若在双精度数中朴素地累加56位,一旦超过2^53就会反复舍入,在取整边界处可能产生差异。)” u64使用相同的构造方式处理八个字节,“与服务器LimboService.outcome100中的ULong→Double转换相匹配”,是每一个种子对原始验证都会引入的函数。
| 函数 | 读取的字节 | 构造方式 | 匹配对象 |
|---|---|---|---|
| u56 | 前7个 | hi ÷ 2³² + lo ÷ 2⁵⁶,一次加法 | 服务器的Long → Double转换 |
| u64 | 前8个 | hi ÷ 2³² + lo ÷ 2⁶⁴,一次加法 | 服务器的ULong → Double转换(Limbo) |
| h52 / bust100 | 前6.5位(13个十六进制数字) | 精确的BigInt整数运算,完全不使用double | 服务器的CrashDerivation.crashPoint100 |
每个种子对原型(bingo、blackjack、hold'em、koban、omikuji、sic bo、video poker、hanabi、fukubukuro、roulette)都从rng.ts导入u64;生成器和验证器使用同一个导入。
Crash把这个论点推向了极致。它的爆点遵循bustabit公式,floor((100 × 2⁵² − h) ÷ (2⁵² − h)),其中h是哈希的前52位,而这个除法恰好落在double可能会出现一位偏差的那种边界上。所以引擎不使用double。它用任意精度整数在浏览器中计算这个公式,和服务器的方式一样,源代码中的注释一句话说明了原因:浮点近似会在floor边界处与整数除法产生分歧,导致验证器拒绝本应通过的合法回合。
引擎已验证_shared/rng.ts bust100: h = h52(digest),即前13个十六进制字符转为BigInt;p = (100·2⁵² − h) ÷ (2⁵² − h),使用BigInt除法,限制在[100, 1,000,000]范围内;注释写道:“精确的BigInt数学运算,以逐位匹配服务器(NewWhiteBack CrashDerivation.crashPoint100)——浮点近似会在floor边界处与整数除法产生分歧,导致验证器拒绝本应通过的合法回合。”这些BigInt值是通过BigInt()调用构建的,而不是字面量,以便文件能在项目的es5目标下编译。
一份实现,两项职责
同一个文件里还有一个更不起眼的决定。把哈希转换为数字的函数并没有写两遍,一遍给游戏用一遍给检查器用。它们只写了一次,放在头部注释描述为生成器和验证器共享的模块中,而在你的浏览器里进行未登录演示回合的引擎,正是通过调用公平性面板用来检查结果的同一组函数来产生结果的。
引擎已验证_shared/rng.ts 头部注释:“加密原语,由可证明公平的生成器(demoLocal.ts,各游戏的derive模块)和验证器(fairness.tsx)共享。从fairness.tsx中提取出来,以便游戏的推导可以被双方导入而不产生循环导入。”hmacSha256Utf8被描述为消费key和message“与服务器上RandomUtils.generateHash消费它们的方式完全一致……一份实现,因此演示永远不会与验证器接受的结果产生偏差。”
这种设计有一个容易说清楚、也值得说清楚的后果。当验证器说某个回合验证通过时,它并不是在说自己对服务器的近似值在某个容差范围内与服务器一致。它是在说,同一个函数,给定相同的输入,产生了相同的输出,而这里没有容差可言,因为根本没有什么需要容忍的。当它说某个回合验证不通过时,那不是噪音。这意味着输入不同,而这正是验证器存在的意义所在。
一个舍入方式与服务器不同的验证器,是一个偶尔会“狼来了”的验证器。第一次误报之后,就没人会相信真正的警报了。为什么舍入很重要
从中应汲取什么
- “可证明公平”是一个关于算术的主张,而算术是有边界的。承诺方案是标题,而逐位推导才是让这个标题真正可执行的东西。
- 不匹配的情况应该罕见到足以令人警觉。在这个引擎上,一个诚实的回合不会因为舍入问题而验证失败,所以失败是信息,而不是伪影。
- 你可以阅读这个函数。这个构造只有几行代码,验证走查展示了每一行在实际回合中的用法。
这篇文章描述了客户端推导模块,并引用了它对所镜像服务器的注释;服务器本身不在公开代码库中,庄家服务才是支付方的权威。这是一篇工程笔记,而非认证。
常见问题
如果使用相同的哈希,验证器和服务器为什么会不一致?
因为把哈希转换为0到1之间的数字需要舍入到53位精度,而一次性舍入并不总是与多次舍入得到相同的结果。一个在循环中累加字节的验证器,可能会在最后一位与一次性转换的服务器产生差异。
一个比特真的重要吗？
当这个数字乘以37、52或一百万并向下取整时，最后一位可以决定得出哪个整数。那可能就是不同的口袋、卡牌或物品。
引擎是如何避免这种情况的？
它由两个可精确表示的部分构建数字，前四个字节基于2³²，后面的字节基于2⁵⁶或2⁶⁴，然后一次性相加，与服务器整数到双精度浮点数转换时的单次舍入相匹配。Crash使用精确的整数运算，完全不涉及双精度浮点数。
验证器和游戏是各自独立的程序吗？
不是。哈希和数字函数存在于一个共享模块中，演示引擎和公平性面板都从这个模块导入，因此生成器不会与验证器产生偏差。
在这里验证失败意味着什么？
意味着输入与服务器实际使用的不同，因为在这个引擎上，舍入不可能导致误报的失败。这正是验证器存在的意义所在——发出这个信号。
来源与参考资料
- Betkyo引擎源代码：_shared/rng.ts（u56、u64、h52、bust100、hmacSha256Utf8及其注释）
- IEEE 754-2019 — 浮点运算标准（binary64：53位有效数字精度）
- Bustabit可证明公平的Crash点公式，bust100的构建正是对此的模仿
本文提到的游戏