Idea: Verifiably non-riggable shuffle algorithm for online mahjong games

1. en.md

Idea: Verifiably non-riggable shuffle algorithm for online mahjong games

1. Server should save a random bytestring PS (regenerated after each full match) for each player. PS should be visible on game UI.
2. Server should publish a global 1024-bit (128 bytes) random bytestring GS (changed every X minutes). Current and next GS should be visible on game UI.
3. When a match starts, save timestamp T1.
4. When a round starts, save timestamp T2, and generate a random bytestring R. Then, generate random seed for this round by calculating SHA512 hash of concatenation of following elements (|| denotes concatenation):

• T1
• T2
• R
• HMAC-SHA512(GS, T1 || T2 || R)
• HMAC-SHA512(PS, T1 || T2 || R) for each player

5. Use RFC7539 ChaCha20 as random number generator. Key, nonce and block count are sliced from the hash generated in step #4. Generated bitstream should be XORed with GS to produce output.
6. Use Fisher–Yates algorithm to shuffle the tiles.

Notes

• All random bytestrings should be at least 32 bytes long, and preferably generated from /dev/urandom or RDRAND.
• All timestamps should be at least in millisecond precision
• All seed materials should be saved in game record for verification
• T1, T2 and R should be kept on server-side and NOT revealed to players until the match is completed

Rationale

• Random number generator with deterministic seed allows players to verify that tiles are shuffled using this algorithm
• GS and PS ensure that server can't use a pre-generated tile list for a specific game
• T1, T2 and R introduce randomness into the algorithm, and ensure player can't compute tile list for games in progress
• XORing with GS is for increasing number of possible permutions to 1024bit

2. ch.md

想法：在线麻将游戏的可验证非作弊洗牌算法

1. 服务器应为每个玩家保存一个随机字节串 PS（每场完整对局后重新生成）。在游戏界面上应显示 PS。
2. 服务器应发布一个 1024 位（128 字节）的全局随机字节串 GS（每隔 X 分钟重新生成）。当前和下一个 GS 应在游戏界面上可见。
3. 当对局开始时，保存时间戳 T1。
4. 当一局开始时，保存时间戳 T2，并生成一个随机字节串 R。然后，通过计算以下元素的串联的 SHA512 哈希值（|| 表示串联）来为这一局生成随机种子：
   • T1
   • T2
   • R
   • HMAC-SHA512(GS, T1 || T2 || R)
   • 对每个玩家：HMAC-SHA512(PS, T1 || T2 || R)
5. 使用 RFC7539 ChaCha20 作为随机数生成器。密钥、随机数和块计数从步骤＃4生成的哈希中截取。生成的比特流应与 GS 进行异或操作以产生输出。
6. 使用 Fisher–Yates算法 对牌山进行洗牌。

注意事项

• 所有随机字节串应至少为 32 字节长，并最好从 /dev/urandom 或 RDRAND 生成。
• 所有时间戳应至少精确到毫秒。
• 所有种子材料应保存在游戏记录中以供验证。
• T1、T2 和 R 应保留在服务器端，在比赛完成前不向玩家透露。

理论基础

• 具有确定性种子的随机数生成器允许玩家验证牌山是使用当前算法洗牌的。
• GS 和 PS 确保服务器无法为特定局使用预生成的牌山。
• T1、T2 和 R 引入随机性，并确保玩家无法计算进行中的游戏的牌山。
• 与 GS 进行异或操作使可能的排列数增加到 1024 位。

3. ja.md

アイデア: オンライン麻雀ゲームの改ざん不可能なシャッフルアルゴリズム

1. サーバーは各プレーヤーに対してランダムなバイトストリング PS（各対局後に再生成）を保存する必要があります。PS はゲームのUI上で表示されるべきです。
2. サーバーはグローバルな1024ビット（128バイト）のランダムバイトストリング GS（X分ごとに変更）を公開する必要があります。現在の GS と次の GS はゲームのUI上で表示されるべきです。
3. 対局が開始されると、タイムスタンプ T1 を保存します。
4. 局が開始されると、タイムスタンプ T2 を保存し、ランダムバイトストリング R を生成します。次に、以下の要素の連結のSHA512ハッシュを計算することで、この局のランダムシードを生成します（|| は連結を表します）：
   • T1
   • T2
   • R
   • HMAC-SHA512(GS, T1 || T2 || R)
   • 各プレーヤーごとに HMAC-SHA512(PS, T1 || T2 || R)
5. RFC7539 ChaCha20 をランダム数生成器として使用します。鍵、ノンス、およびブロック数はステップ＃4で生成されたハッシュからスライスされます。生成されたビットストリームは GS とXOR演算を行って出力を生成します。
6. Fisher-Yatesアルゴリズム を使用して牌山をシャッフルします。

ノート

• すべてのランダムバイトストリングは少なくとも32バイトの長さである必要があり、可能であれば /dev/urandom または RDRAND から生成されるべきです。
• すべてのタイムスタンプは少なくともミリ秒単位である必要があります。
• すべてのシード素材は検証のためにゲームの記録に保存されるべきです。
• T1、T2、および R はサーバーサイドに保持され、対局が完了するまでプレーヤーには公開されません。

理論的根拠

• 確定的シードを持つランダム数生成器により、プレーヤーはこのアルゴリズムを使用してタイルがシャッフルされたことを検証できます。
• GS と PS は、サーバーが特定のゲームのために事前生成された牌山を使用できないようにします。
• T1、T2、および R はアルゴリズムにランダム性を導入し、進行中のゲームの牌山をプレーヤーが計算できないようにします。
• GS とのXOR演算は1024ビットの可能な並べ替えの数を増やすために使用されます。