问题:是否存在正式标准化的基于树的(可并行化的)哈希?
对我而言,基于树的哈希最重要的属性是对于输入字符串的任何分区,可以减少每一部分并行到$ O(\ log n)$中间空间,以便可以将中间值组合到最终哈希中,而在顺序哈希中最多具有恒定的因子开销。
#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/baoBao的一个可能对身份验证存储有用的功能是,它可以根据根哈希验证文件的任何部分,而无需先检索整个文件。因此,例如,如果经过身份验证的文件是一个大视频,并且您想要流式传输它并在手机上寻找它,则可以这样做。
编辑:随着BLAKE3的发布,最新版本的Bao不再拥有自己的哈希函数。相反,它基于BLAKE3,实现了规范中经过验证的流传输部分。
评论
blake2b可能与您要查找的内容相似。我认为NIST正在SHA-3程序的一部分上进行某些工作,但是他们还没有草稿
csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/documents / ...
老虎树哈希可能是最接近标准树哈希的事物。
@GeoffreyIrving我认为SHA-3的某些候选设计中包含了树形哈希,因为树形哈希没有标准。如果有的话,不需要将树的哈希值包含到算法中。