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,实现了规范中经过验证的流传输部分。