验证成本低，计算哈希算法成本高

Question

我正在寻找一个哈希算法有点类似bcrypt，但我希望验证是非常便宜的。

作为一项反垃圾邮件的措施，我想要求我的客户在提交信息之前花费半秒钟的计算时间。我想分配他们的信息哈希，然后在我的一端快速检查信息是正确的哈希。使用像bcrypt这样的东西来保护自己不受DoS的侵害是不可行的。

因为这是一个反垃圾邮件的措施，我不是在寻找完美，散列算法可能会很弱。

这样的算法有名字吗？我能用什么？

Answer 1

它被称为“工作证明”算法。基本思想是，在创建哈希之后，强制调用方做一些额外的工作。您可以使用任何哈希算法。这里有一个简单的表单：

1. 客户端计算数据的哈希。(比方说，它是160位。)
2. 客户端创建一个包含散列和其余数据(全部为零)的块。(假设块是512位。)
3. 客户端计算此块的散列。
4. 如果最后一个散列低于目标，则客户端提交它刚才散列的整个块并完成。
5. 客户端增加除哈希之外的块中的数据，并跳转到步骤3。

当服务器获得该块时，它将计算该块的散列。如果哈希值低于目标，则服务器接受该块，并从块的开头读取哈希。如果哈希位于目标之上，服务器将拒绝该哈希。

所以如果目标是..。客户端通常必须执行步骤3(哈希操作) 16次，才能获得目标以下的最终哈希。(在十六进制中，给定散列的概率为1/ 16，从零开始。)如果太简单的话，把目标设为00fff.客户端通常需要执行256个块散列。

平均而言，您可以强制客户端执行任意数量的散列。客户端需要执行的实际哈希数遵循泊松分布。缺点是，客户总是有可能运气不好，不得不做大量的工作。

如果您需要防止客户端‘重用’工作，您可以让客户端要求您提供序列号。然后，块包含散列，然后是序列号，然后是现在(客户端递增的部分)。然后，您可以验证序列号，这样客户端就不能重用它以前做过的块，也不能预先计算块。

如果你不喜欢这个，你也可以选择两个随机素数并发送这些素数的乘积。强制客户端计算该数字。接受每个数字的一个哈希因子。当然，您可以使素数大或小，以控制客户需要完成的工作量。