是否可以做到这一点，从而使每个玩家都有能力合理地确定随机数是公平选择的，而不必信任任何其他人？ />
这个问题源于对我对比特币SE的回答的评论讨论。我提出了一个协议，但是其他人发现了一个缺陷。该网站似乎更合适。
请随时使用我对这个问题的回答。
#1 楼
您发布的答案实际上是正确的（或多或少，请参见下文）：让每个参与者通过在第一轮发布$ \ mathcal {H}（r_i）$来承诺其随机数$ r_i $。然后在第二轮中，每个参与者通过发布$ r_i $来打开承诺，每个人都通过对承诺值进行哈希处理来检查其是否与承诺值匹配。最终的随机数是每个$ r_i $的XOR。那里的评论者建议如果发生碰撞则发动袭击。但是，安全哈希函数的定义是其抗冲突性。对于像SHA256这样的现代哈希函数来说，就是这种情况。
有两个微妙之处。
第一个是，您的方案仅适用于较大的随机数，足够大，攻击者无法尝试$ r_i $的所有可能值，对其进行哈希处理，然后查看其是否匹配。为了提交较小的值，您需要一个随机的提交函数。好的随机承诺基于离散对数，但是您可以使用哈希函数构造一个（具有合理的安全性），方法是生成一个较大的随机值$ a_i $，然后将您的承诺计算为$ \ mathcal {H}（r_i || a_i）$ 。要打开，请同时显示$ r_i $和$ a_i $。要更改$ r_i $，您必须找到一个不同的$ a_i $，以使散列相同：基于抗碰撞性很难做到这一点。 $ r_i $和$ a_i $的位长必须预先确定，以便从$ r_i || a_i $清楚地知道将值分为$ r_i $和$ a_i $的位置（否则您可以通过简单地将其拆分为不同的值）在另一个位置）。
第二个微妙之处是，最后一个展示自己价值的参与者在展示自己的数字之前将学习累积的随机数（他可以看到其他人的数字并且他知道自己的数字）。如果他不喜欢这个结果，这可能导致他中止。您可以做一些更复杂的事情来提供公平性，但是通常，如果任何参与者拒绝履行其承诺，则应从头开始重新启动协议，并排除该参与者。
也请从@ D.W阅读此答案。在另一个问题上，他解释了相同的协议。
#2 楼
JGWeissman在Bitcoin.SE上指出的问题仅在哈希函数缺乏抗冲突性时才是一个问题。诚然，抗冲突性是哈希函数通常需要的最强属性之一，并且已经发现了对过去常用的某些哈希函数（例如MD5）的冲突攻击，但仍然，任何安全的密码哈希函数都应具有冲突性。 br />实际上，一个更简单的方案应该起作用：
每个玩家$ i $选择一个随机数$ x_i \ in \ {0，\ dotsc，n- 1 \} $和一个随机的$ k $位字符串$ s_i $，用于一些相当大的$ k $（例如，$ k = 128 $）。
每个玩家都宣布$ h_i = H（i \，| | \，s_i \，|| \，x_i）$，其中$ H $是抗碰撞的哈希函数，而$ || $则表示串联。
所有玩家都宣布了$ h_i $之后，他们的$ s_i $和$ x_i $。每个玩家检查步骤2中其他玩家$ j $宣布的$ h_j $值是否与该玩家的$ s_j $和$ x_j $相匹配。
最终的随机数$ x $计算为所有$ x_i $值以$ n $为模。
步骤2中宣布的$ h_i $值称为承诺。通过发布$ h_i $，玩家$ i $提交了一个特定的$ x_i $，而没有实际揭示$ x_i $本身。这样，每个玩家$ i $可以确保其他玩家在不知道$ x_i $的情况下选择了他们的随机数。
盐$ s_i $的目的仅仅是为了防止暴力破解。 $ h_i $，依次尝试$ x_i $的每个可能值。玩家标识符$ i $包含在散列中，以防止作弊玩家复制其他玩家的承诺。我假设标识符是唯一的，并且至少在步骤3之前至少为所有玩家所知。（另一种防止此类重播攻击的方法是，如果任何两个承诺相同，则在步骤3中终止协议。几乎不应该偶然地包含盐。）
实际上，如果$ h_i $的长度实质上大于$ k \; \ log_2（n ^ 2- n）$，即使$ H $不具有抗冲突性，该协议也可能是安全的，这仅仅是因为可能没有发现可利用的冲突。特别是，假设$ H $的输出均匀地分布在$ m $位字符串的集合中，其中$ 2 ^ m \ gg 2 ^ k $（和$ 2 ^ m \ gg n ^ 2 $），则概率为至少有一个可利用的冲突大约是
$$ 1- \ left（1- \ frac {1} {2 ^ m} \ right）^ {2 ^ k \ tfrac {n ^ 2 -n} {2}} \ approx 1- \ exp \ left（-2 ^ {km} \ frac {n ^ 2-n} {2} \ right）\ approx 2 ^ {km} \ frac {n ^ 2 -n} {2}。$$
但是，请记住，您也不想使$ k $太小，因为那样盐就无效了。不过，增加$ m $应该总是安全的。
评论
$ \ begingroup $
实际上，这里有一个微妙之处。使用$ r_i $ s的总和是不安全的。使用我在@PulpSpy的协议中描述的攻击的一种变体，恶意参与者Bob可以强制总和为偶数，这意味着最终的“随机”数实际上并不是随机的。该修复方法与我在Pulpspy答案中的评论中所述的相同：您应该哈希所有$ x_i $值（而不是求和）。
$ \ endgroup $
– D.W.
2011年9月26日下午4:23
$ \ begingroup $
@ D.W .：很好。不过，我应该指出，还有至少两种其他方法可以修复协议：如果$ h_i = h_j $对于任何$ i \ ne j $，则中止/重启协议（如果没有人作弊，从天文学角度来看这不太可能），或在$ H $的输入中包含某种玩家标识符（这样，任何重放其他玩家承诺的人都会在步骤3中被捕获）。我将编辑答案以实现后一个选项，因为无论如何都是好的做法。
$ \ endgroup $
–伊尔马里·卡洛宁（Ilmari Karonen）
2011-09-26 17:39
$ \ begingroup $
（我是密码学领域的n00b）这确实是一个问题：每个人的算法为什么都涉及两步？为什么人们首先需要揭示H（xi）？为什么不让每个人都直接提交他们选择的号码？这种承诺似乎是参与的信号？而不是会影响结果的安全性或随机性的东西吗？人们在观察其他人提交自己的号码之前会观察到他们的等待时间是b / c吗？谢谢！
$ \ endgroup $
–避免
17年12月3日在8:18
$ \ begingroup $
@reedvoid：是的。没有承诺阶段，最后一个宣布其人数的人可以根据其他人宣布的内容对其进行更改，因此他们基本上可以选择最终的金额作为他们想要的任何金额。如果您能以某种方式强迫所有人在同一时间即时宣布他们的电话号码，以使他们无法根据其他人的选择更改电话号码，那也可以解决问题。但是在实践中，您永远不能保证不同方的两个操作完全同时发生，尤其是不能在像Internet这样的分布式网络上发生。
$ \ endgroup $
–伊尔马里·卡洛宁（Ilmari Karonen）
17年12月3日，9：05
#3 楼
假设$ m $个人见面，并想画一个小于$ n $的正整数$ x $。每个人$ j $都秘密选择一个小于$ n $的正整数$ x_j $，将其记录在一张纸上，然后折叠以隐藏她的选择。折成美元的纸片放在一起，然后公开展开，露出$ x_j $。该协议的结果为$ x =（\ sum x_j）\ mod n $。为了说明$ n = 10 $，添加了$ m $位$ x_j $，总和的最右边位是$ x $。 $是随机的，那么$ x $是随机的。因此，没有参与者可以抱怨$ x $不是随机的。
可以用电子信息交换来代替论文：除了$ x_j $，每个人都随机抽取一个$ r_j $，并将$ H_j = Hash（x_j \ | r_j）$发送给其他所有对象，这构成了她对选择$ x_j $的承诺。当每个人都有所有承诺时，每个人都会透露她的$ x_j $和$ r_j $。如上计算结果，并且$ x_j $和$ r_j $中的任何人都可以验证$ H_j $。如果消息交换可靠，没有人可以抱怨。
评论
$ \ begingroup $
用纸做的协议是安全的，但是用电子方式交换消息的协议不是安全的。这里有一个微妙的攻击，我在对PulpSpy和Ilmari的回答的评论中对此进行了描述：攻击者可以复制其他人的承诺，从而影响/偏向最终的随机数。如果要使用电子消息，则需要散列每个人的$ x_j $值，而不是对它们求和。
$ \ endgroup $
– D.W.
2011-09-26 4:25
$ \ begingroup $
@ D.W .：您当然是对的！如其他答案所指出的，可以通过定义$ H_j = Hash（x_j∥r_j∥j）$来解决此问题。
$ \ endgroup $
–fgrieu♦
2011-09-27 6:15
#4 楼
有两种变体。如果其中一个“玩家”要生成供其他人猜猜的数字（彩票），那么您可以这样操作：
从每个参与者中收集令牌（随机数，随机数，喜欢的颜色等）。
生成或选择机密号。
将生成的号码与令牌混合。哈希和令牌。
让其他玩家猜猜。猜测完成并发布后，您将发布秘密号码。
每个人都可以通过重复哈希来验证它是真实号码。然后猜猜就这样：
从每个玩家那里收集令牌（随机数，随机数，喜欢的颜色等）
将令牌发布给所有人玩家。
哈希令牌。
使用哈希查看PRNG或RNG生成随机数。
每个人都可以重复此过程以生成相同的随机数。当然，一旦发布令牌，就会知道所有将来的随机数。
评论
$ \ begingroup $
实际上，这里有一个微妙之处。使用$ r_i $ s的XOR是不安全的。攻击：假设有两个参与者，爱丽丝和鲍勃。爱丽丝很诚实，会随机选择$ r_1 $，然后发布$ h_1 = H（r_1）$。鲍勃（Bob）是恶意的，而不是选择自己的随机数并对其进行哈希处理，只是复制了爱丽丝（Alice）的哈希值：即，鲍勃（Bob）发布$ h_1 $。在第二轮中，爱丽丝展示$ r_1 $。鲍勃揭示了同样的事情。现在，最终的随机数将为全零。这允许恶意的Bob强制将最终的“随机”数设为全零，因此它毕竟不是随机的。
$ \ endgroup $
– D.W.
2011年9月26日下午4:20
$ \ begingroup $
附言解决方法是，您可以对它们进行哈希运算，而不是对$ r_i $ s进行XOR。例如，最终的随机数是$ H（r_1 || r_2 || ...）$，而不是$ r_1 \ oplus r_2 \ oplus ... $。
$ \ endgroup $
– D.W.
2011年9月26日下午4:21
$ \ begingroup $
好点！如果您使用不可更改的承诺方案（我曾建议Pedersen承诺；现在已编辑），则攻击最严重，因为这样您就可以掩盖复制另一个承诺（或形成相关承诺）的事实。
$ \ endgroup $
–PulpSpy
2011年9月26日下午14:07
$ \ begingroup $
另一个解决方法是要求随机位的数量大于（例如）256，并且不允许重复的摘要。或者更好的是，迫使重复摘要的第二发布者首先揭示（更好，因为它可以最终确定作弊者）。
$ \ endgroup $
–固定
2011年9月27日，1：18
$ \ begingroup $
对$ \ mathcal {H}（r_i || a_1）$的中间段落进行一次较小的更正：您只需要具有固定大小的部分之一，即可对二进制数进行唯一的解释。通常，您只需要任何完全绑定的承诺方案（或没有陷阱门的计算绑定方案，例如哈希函数）
$ \ endgroup $
– tylo
2014年3月21日在8:26