SHA-1，SHA-2和SHA-3的标准化版本都是顺序的。对于散列分布在计算机上的非常大的文件，这是不切实际的。可以使用Merkle树将任何顺序的哈希直接转换为高效并行的哈希，但是这样我就失去了标准化，如果将哈希用于长期的经过身份验证的存储，则这是不可取的。

问题：是否存在正式标准化的基于树的（可并行化的）哈希？

对我而言，基于树的哈希最重要的属性是对于输入字符串的任何分区，可以减少每一部分并行到$ O（\ log n）$中间空间，以便可以将中间值组合到最终哈希中，而在顺序哈希中最多具有恒定的因子开销。

评论

blake2b可能与您要查找的内容相似。
我认为NIST正在SHA-3程序的一部分上进行某些工作，但是他们还没有草稿
csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/documents / ...
老虎树哈希可能是最接近标准树哈希的事物。
@GeoffreyIrving我认为SHA-3的某些候选设计中包含了树形哈希，因为树形哈希没有标准。如果有的话，不需要将树的哈希值包含到算法中。

#1 楼

使用SHA-3派生函数（SP 800-185，pdf），现在有了一个基于SHA-3的标准化并行哈希，称为ParallelHash。

但是，它不是树哈希，而是更多基于哈希列表的模式。要散列的字符串被分成相等大小的块，这些块先进行散列，连接然后再次进行散列。

虽然它不是树形散列，但它应涵盖对整个大文件进行散列的用例许多机器。如果将阻塞大小设置为适当的输入大小函数，则任意小的阻塞大小都可以达到$ O（\ log n）$的要求。

评论

$ \ begingroup $
谢谢，似乎尚未敲定，但还是接受。令人遗憾的是，块大小是一个无法理解的参数。
$ \ endgroup $
–杰弗里·欧文（Geoffrey Irving）
17 Mar 4 '17 at 14:57
$ \ begingroup $
@GeoffreyIrving，它在几个月前完成。我认为如果块大小恒定不变，它几乎没有用。
$ \ endgroup $
–otus
17 Mar 4 '17 at 15:42
$ \ begingroup $
这是真的，因为它不是树哈希。
$ \ endgroup $
–杰弗里·欧文（Geoffrey Irving）
17 Mar 4 '17 at 17:51
$ \ begingroup $
@GeoffreyIrving，足够真实。
$ \ endgroup $
–otus
17 Mar 5 '17 at 7:56
$ \ begingroup $
KangarooTwelve是ParallelHash的改进版本，具有固定的块大小，减少的回合计数和较短的消息开销。
$ \ endgroup $
–杰克·奥康纳（Jack O'Connor）
20年7月12日在22:53

#2 楼

BLAKE3哈希函数刚刚在今天宣布。内部是一棵Merkle树。

#3 楼

我正在基于BLAKE2进行树哈希处理，这绝对不是官方的方法，但这恰恰是您描述的那种设计。一旦经过适当的检查和稳定，这可能会很有用：https://github.com/oconnor663/bao

Bao的一个可能对身份验证存储有用的功能是，它可以根据根哈希验证文件的任何部分，而无需先检索整个文件。因此，例如，如果经过身份验证的文件是一个大视频，并且您想要流式传输它并在手机上寻找它，则可以这样做。

编辑：随着BLAKE3的发布，最新版本的Bao不再拥有自己的哈希函数。相反，它基于BLAKE3，实现了规范中经过验证的流传输部分。