投标承诺

Question

Alice和Bob坐在一张在线赌场桌子上，这张桌子公开了以下游戏:该表随机生成一个数字R，并将这个数字与这个数字相比较。在0和R之间“出价”最高的球员获胜。如果两个球员出价相同，他们都被排除在游戏之外(只有独特的出价才能获胜)。玩家必须得到保证，该表没有欺骗，允许一个串通的球员出价，而其他球员是透露他们的出价。

游戏的结构是这样的: 1.所有玩家，个别地，选择一个数字，并发布一个对这个数字的不可延展性的承诺，任何玩家都可以看到。2.一段时间后，表格不再接受投标。3.每个球员都会透露他们的出价和承诺证明。4.表中宣布胜利者。

“结束出价”信号不一定同时到达所有玩家，但可能会有几秒钟的延迟。

球员们怎么能确定在揭发过程中接受出价，而不是作弊呢？还是想弄清楚到底是谁出价了？有没有办法“时间戳”的出价，而不信任任何第三方？

Answer 1

让我重申一下你的游戏，以确保我正确地理解了你：

• 有$n$播放器
• 赌场显示编号$R$
• 每个玩家都会把承诺发送给某个数字0$和$R$
• 在赌场向所有玩家发出“关闭博彩”信号后
• 每个玩家都会发送自己选择的号码+证据作为承诺。
• 拥有最高独特号码的玩家获胜

你的问题是:如何证明赌场不会采取任何赌注后，一些玩家发送他们的号码。

解决方案:使用一些签名方案。赌场期间，“博彩关闭”信号发送清单，它已经收到的所有承诺，关闭前与其公钥签署。只有在收到这个列表后，玩家才会发送他的号码+证明。如果赌场宣布胜利者不在名单上，玩家可以出示作弊的证据。

他说，我认为这场游戏还有更根本的问题:即使赌场是完全诚实的，一群合谋的玩家也会向他们有利：

1. 如果$n=2k，k>0$，那么至少有一群$k$玩家可以保证没有其他人能赢
2. 如果$n=2k-1，k>1$那么至少有一组$k$玩家可以保证他们会赢。

在这两种情况下，策略是相同的:组投注$k$值：$R，R-1，R-2，.，R+1$。对于小组以外的任何玩家来说，要想赢，就必须匹配所有的团体投注+多赌一次($0到$R-k$)。

但是在第一种情况下，只有小组之外的$k$玩家，所以你不能在小组之外进行赢注(如果任何两位玩家打赌的号码相同的话，组仍然可以赢)。

在第二种情况下，团队之外只有$k-1的玩家，所以至少有一个$R，R-1，R-2，.，R+1$将是唯一的，它肯定是最高的赌注，所以小组每次都会赢。