我正在开发一个"可证明公平"的网站,假设 X 名参与者进入抽奖,我们需要选出前 1 名总冠军,但理想情况下,我们也想从 X 个总数中挑选 N 个次级获胜者。
(对于好奇的人来说,SHA-256 哈希将在预先指定的时间成为比特币区块的默克尔树根)
那么,给定一个 SHA-256 哈希,我们如何生成 N 个随机数?
我想我知道如何生成 1 个随机数(在 ruby 的 Fixnum 范围内)。根据这篇文章: http://patshaughnessy.net/2014/1/9/how-big-is-a-bignum
最大 Fixnum 整数为:4611686018427387903
让我们采摘 SHA-256 哈希的第一个 Y 字符。我们可以生成一个,而不是依赖比特币默克尔根:
d = Digest::SHA256.hexdigest('hello')
> "2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824"
让我们取前 6 个字符,或:2cf24d
将其转换为基数 10:
'2cf24d'.to_i(16)
> 2945613
我们现在有一个基于我们的默克尔根的独特 Fixnum。
对于 X 名参与者,假设 17 名,我们通过以下方式决定获胜者:
2945613 % 17
> 6
因此,假设所有参赛者都知道他们的参赛顺序,第六名参赛者可以证明他们应该是获胜者。
现在 - 同样挑选N个次级赢家的最佳方法是什么?假设这些参赛者中的每一个都应该获得一个较小但仍然有些有价值的奖品。
为什么不直接使用哈希作为种子?
[*1..17].shuffle(random: Random.new(0x2cf24d))
# => [15, 5, 9, 7, 14, 3, 16, 12, 2, 1, 17, 4, 6, 13, 11, 10, 8]
[*1..17].shuffle(random: Random.new(0x2cf24d))
# => [15, 5, 9, 7, 14, 3, 16, 12, 2, 1, 17, 4, 6, 13, 11, 10, 8]
编辑:这取决于Ruby版本 - 我相信JRuby和MRI之间的shuffle
是不同的,即使Random
产生相同的序列。您可以通过自己实现shuffle
来规避这一点。有关更多详细信息,请参阅此问题。此解决方法在JRuby和MRI中始终适用于我:
r = Random.new(0x2cf24d)
[*1..17].sort_by { r.rand }
# => [14, 11, 4, 10, 1, 3, 9, 13, 16, 17, 12, 5, 8, 2, 6, 7, 15]
r = Random.new(0x2cf24d)
[*1..17].sort_by { r.rand }
# => [14, 11, 4, 10, 1, 3, 9, 13, 16, 17, 12, 5, 8, 2, 6, 7, 15]