(HotOS'03 Note)An Analysis of Compare-by-hash

An Analysis of Compare-by-hash
Val Henson
HotOS 2003

作者就研究中越来越广泛的使用hash函数作为快速比较方法的倾向进行了分析。很多的研究工作，都使用SHA-1等Hash函数作为比较的唯一标准，例如一些网络文件系统的块cache命中算法。有人认为密码学hash函数的冲突概率要比硬件出错的概率还要低，所以支持直接使用hash函数作为比较标准，而不再对hash冲突进行检查。

作者对这种将密码学hash函数应用推广到通用应用倾向提出了质疑，认为compare-by-hash方法有以下一些问题需要认真分析。
1．输入的随机性。实际使用compare-by-hash的应用的输入并不像期望的那样真正具有随即性。
2．密码学hash函数有一些特点：short-lived（一般只有有限的时间窗口）；Obsolescence can occur overnight（一旦攻破，立即过时）；Obsolescence is inevitable；Upgrade strategy required。而通用的软件可能会使用10年以上的时间。
3．Hash冲突可能导致silent，deterministic， hard-to-fix errors。这种错误可能是相当危险的。
4．Comparing probabilities。可以构造出一些例子证明会改变hash函数本身的冲突概率。
5．Software and reliability。作者认为软件不应对硬件错误概率听之任之，而应该增加软件手段去改进。所以，hash冲突概率低于硬件错误概率的论据是站不住脚的。

作者也提出其它可选的方案，总结其特点就是keep some state。另外，结合具体应用的特点进行评估也很重要。作者反对的是不加区分的使用compare-by-hash，实际上hash方法确实有很多好处，有巨大的吸引力。

作者文中提到fingerprints（指纹）方法作为一种替代方法，让我想起了B. O. Christiansen的博士论文Data Compression for Thin Client Computing中Fast block motion detection的核心思想之一就是利用图像元素的“指纹”（特征）。

关于Compare-by-hash，对于thin client研究中也许有一些启发……