快速(XOR-?)组合SHA1哈希以生成新哈希

Question

我有一个（可能很大的）唯一文本行（字符串化JSON数据）列表，我需要为整个文本文档计算一个唯一哈希值。通常，新行将附加到文档中，偶尔某些行会从中删除，导致文档完全重新生成哈希值。

最终目标是只使用哈希来识别相同的文档。

当然，在每次修改后为整个文档计算SHA1哈希将给我所需的唯一哈希，但这也是计算密集型的，特别是在仅向5兆字节的文档追加了约40字节并且所有数据都必须再次通过SHA1计算的情况下。

因此，我正在寻找一种解决方案，可以使我减少计算新哈希所需的时间。

问题属性/要求的摘要：

- 每行都保证是唯一的 - 行的顺序不一定重要（最好是如此） - 单行的长度通常很小，但整个文档可能很大 - 该算法可以针对添加的数据进行优化（即，如果要删除数据，则在这种情况下甚至可能需要重新开始）

我的当前想法是单独为每个单独行计算SHA1（或任何其他）哈希值，然后将哈希值异或在一起。这应该满足所有要求。对于新行，我只需计算该行的SHA1并将其与已知总和异或。

但是，我有疑虑，因为...

- 我不确定XOR哈希是否仍然足够强大，以确切地识别文档（即，是否存在意外冲突的可能性显着更高？） - 计算大量短行的SHA1哈希本身可能是计算密集型的（至少在初始化期间）

有人能为这些问题提供一些帮助吗？

另外，也许通常可以使用SHA1（或类似的哈希）快速生成附加数据的新哈希（旧哈希+添加数据=新哈希）吗？

- Udo G

---

你使用的是哪个 sha1 的 JavaScript 实现？ - vp_arth

实现对于这个问题并不重要，因为只要哈希足够强大以“唯一”地标识文档即可，甚至不需要是SHA1。然而，为了回答你的问题，我通常使用rusha库。 - Udo G

Answer 1

单独对每个文件进行哈希存在问题。

如果添加了两行相同的内容，组合后的异或值不会改变。

更好的方法是对所有单独的行哈希进行哈希。

可以考虑使用Merkle Tree。

- zaph

---

不可能添加两行相同的内容（它们是唯一的，请参见问题）。感谢Merkle Tree提示，看起来很有趣 - 尽管通常我发现哈希大量短行非常昂贵，因此最终流式sha1哈希（其他答案）可能更好。 - Udo G

我可用的计算机可以每秒哈希400 MB的SHA256。 - zaph

...还有手机吗？ ;) - Udo G

iPhone 6s：400MB/s，iPhone4s（4年前的）：40MB/s。 - zaph

用JavaScript？使用哪种实现方式？ - Udo G

我没有 JavaScript 的任何数字。如果实际实现在 JavaScript 中，即使在编译为其他语言的情况下，我也可以看到 200:1 的速度降低，而使用原生的 iOS 实现则更好。与硬件支持加密跨模型/版本相比，Android 更具问题。 - zaph

Answer 2

你可以执行增量更新来计算点赞流：

var crypto = require('crypto');

var shasum = crypto.createHash('sha1');
shasum.update("Hello, ");
shasum.update("World!");
console.log(shasum.digest('hex'));

shasum = crypto.createHash('sha1');
shasum.update("Hello, World!")
console.log(shasum.digest('hex'));

- vp_arth

---

好的，谢谢！也许你能告诉我一些关于上面描述的异或方法的信息吗？ - Udo G

你的 xor 方法有些问题。a xor b xor b == a。我认为，你永远不可能得到 sha1('abcd') == foo(sha1('abc'), 'd') 的相等性。看起来几乎不可能。 - vp_arth

请注意，“a xor b xor a”永远不可能发生，因为所有行都是唯一的。 - Udo G

我本来想建议这个。我认为浏览器WebCrypto API没有提供这种灵活性（而且Safari目前也不支持），但是任何SHA-1 Merkle-Damgard构造的实现都应该很容易修改为可流式处理，并且通过逐步执行此操作所获得的效率收益应该超过JITting JavaScript加密时略微低效的部分。关于这种方法的安全性，您最好在Crypto.SE上询问，但据我了解，对于大多数实际威胁来说，这应该是安全的（假设行是唯一的）。 - Jeremy