投標承諾
愛麗絲和鮑勃正坐在一張線上賭場的桌子上，該桌子展示了以下游戲：桌子隨機生成一個數字 R 並記錄這個數字。在 0 和 R 之間“出價”最高數字的玩家獲勝。如果兩個玩家出價相同的號碼，他們都將被排除在遊戲之外（只有唯一的出價才能獲勝）。玩家必須確保牌桌沒有作弊，允許串通的玩家出價，而其他玩家透露他們的出價。
遊戲的結構是這樣的： 1. 所有玩家單獨選擇一個號碼並對該號碼發布不可延展的承諾，任何玩家都可以看到。2. 一段時間後，桌子停止接受投標。3. 每個玩家都顯示他們的出價以及承諾證明。4. 表宣布獲勝者。
“收盤”信號不一定同時到達所有玩家，但可能會有幾秒鐘的延遲。
玩家如何確保該桌沒有在揭露過程中接受出價而作弊？還是要弄清楚在所有其他人之後已經出價了？有沒有辦法在不信任任何第三方的情況下為投標“加蓋時間戳”？
讓我重述一下你的遊戲，以確保我正確理解了你：
- 有 $ n $ 球員
- 賭場禮物號碼 $ R $
- 每個玩家向某個數字發送承諾 $ 0 $ 和 $ R $
- 之後，賭場向所有玩家發送“投注關閉”信號
- 每個玩家發送他選擇的號碼+承諾證明
- 擁有最高唯一編號的玩家獲勝
您的問題是：如何證明賭場在某些玩家發送他們的號碼後不會接受任何投注。
解決方案：使用一些簽名方案。賭場在“投注關閉”信號期間發送它在關閉前收到的所有承諾列表，並使用其公鑰簽名。只有在收到此列表後，玩家才會發送他的號碼+證明。然後，如果賭場宣布不在列表中的獲勝者，玩家可以出示作弊證據。
說我認為這個遊戲存在更根本的問題：即使賭場非常誠實，一群勾結的玩家也可以將賠率轉向有利於他們：
- 如果 $ n=2k, k>0 $ 然後至少一組 $ k $ 玩家可以確保沒有其他人可以獲勝
- 如果 $ n=2k-1, k>1 $ 然後至少一組 $ k $ 玩家可以保證他們會贏
在這兩種情況下，策略是相同的：小組投注 $ k $ 價值觀： $ R,R-1,R-2,…,R-k+1 $ . 對於組外的任何玩家要獲勝，必須匹配所有組投注+再下注（之間 $ 0 $ 和 $ R-k $ ).
但在情況 1 中只有 $ k $ 組外的玩家，因此您不能在組外下注（如果任何兩名玩家下注相同的數字，組仍然可以獲勝）。
情況2只有 $ k-1 $ 組外的玩家，因此至少有一個 $ R,R-1,R-2,…,R-k+1 $ 在所有賭注中都是獨一無二的，而且肯定是最高賭注，因此小組每次都會獲勝。