Hash 算法

散列表（Hash table，也叫哈希表），是依据关键码值(Key value)而直接进行訪问的数据结构。

也就是说，它通过把关键码值映射到表中一个位置来訪问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

基础概念

比方我们存储 70 个元素，但我们可能为这 70 个元素申请了 100 个元素的空间。

70/100=0.7，这个数字称为负载因子。

我们之所以这样做，也是为了“高速存取”的目的。

我们基于一种结果尽可能随机平均分布的固定函数H为每一个元素安排存储位置，这样就能够避免遍历性质的线性搜索，以达到高速存取。

可是因为此随机性，也必定导致一个问题就是冲突。

所谓冲突，即两个元素通过散列函数H得到的地址同样，那么这两个元素称为“同义词”。

这类似于 70 个人去一个有 100 个椅子的饭店吃饭。散列函数的计算结果是一个存储单位地址，每一个存储单位称为“桶”。

设一个散列表有 m 个桶，则散列函数的值域应为[0,m-1]。

冲突

解决冲突是一个复杂问题。冲突主要取决于：

（1）散列函数，一个好的散列函数的值应尽可能平均分布。

（2）处理冲突方法。

（3）负载因子的大小。太大不一定就好，并且浪费空间严重，负载因子和散列函数是联动的。

为此，有很多 hash 算法为解决这些问题而生。

hash 的介绍

  • 参考

The State of Hashing Algorithms — The Why, The How, and The Future

Why

在学习区块链时，新来者听到的关键字之一是哈希和哈希算法的概念，对于安全性来说，哈希算法似乎无处不在。运行一个分散的网络和共识机器，比如通过p2p连接数万个节点的比特币(Bitcoin)或Ethereum (Ethereum)网络，既需要“信任”，也需要验证效率。

也就是说，这些系统需要以一种紧凑的格式对信息进行编码，以便其参与者能够安全、快速地进行验证。

比特币和Ethereum所处理的主要原语是块的概念，这是一个包含交易、时间戳和其他重要元数据的数据结构。 它们安全性的一个关键部分是能够将有关网络全局状态的大量信息压缩为一个短消息标准，如果需要的话，可以有效地验证这个标准，称为哈希。

从密码存储到文件验证系统，密码哈希到处都在使用。

基本思想是使用确定性算法，它接受一个输入，每次生成一个固定长度的字符串。也就是说，使用相同的输入总是会得到相同的输出。

决定论不仅对哈希很重要，而且单个位在不同输入之间的变化也会产生完全不同的哈希。

哈希算法的一个问题是不可避免的冲突。也就是说，哈希是一个固定长度的字符串这一事实意味着，对于我们能想象到的每一个输入，都有可能产生相同的哈希值。碰撞是坏的。这意味着，如果攻击者能够根据需要创建冲突，则攻击者可以将恶意文件或数据传递为具有正确、适当的散列并伪装成合法的。

一个好的哈希函数的目标是使攻击者很难找到生成相同哈希值的输入的方法计算哈希的效率不应该太高，因为这使得人为计算冲突对攻击者来说更容易。

哈希算法需要抵抗“前图像攻击”。也就是说，给定一个hash，计算retrace所采取的确定步骤来重现创建hash的值(即pre-image)应该非常困难。

Given s= hash(x), finding x should be near impossible.

综上所述，“好的”散列算法具有以下3个特性:

  • 在输入中更改一个位应该会产生雪崩效应，并导致完全不同的散列

  • 碰撞的概率应该很低吗

  • 在某种程度上，不牺牲碰撞阻力的效率

Breaking Hashes

最初的散列算法标准之一是MD5散列，它广泛用于文件完整性验证(校验和)，并在web应用程序数据库中存储散列密码。

它的功能非常简单，因为它为每个输入输出一个固定的128位字符串，并且在几轮之间使用简单的单向操作来计算它的确定性输出。

它的短输出长度和操作的简单性使得MD5非常容易被破坏，并且容易受到所谓的生日攻击(birthday attack)。

birthday attack

你听说过这样一个事实吗?

如果你把23个人放在一个房间里，有50%的几率其中两个人同一天生日?把房间里的数字提高到70，你有99.9%的机会。

这源于我们所说的鸽子洞原理，这个原理大概是说，给100只鸽子和99个盒子把它们放进去，必须装满，一个盒子会共用2只鸽子。

也就是说，固定的输出约束意味着存在固定的排列程度，在此基础上可以找到碰撞。

实际上，MD5的抗碰撞能力非常弱，一个简单的2.4GHz奔腾处理器可以在几秒钟内计算出人工哈希碰撞。

此外，在当前web的早期，它的广泛使用已经在网上创建了大量泄漏的MD5预映像，只需对它们的散列进行简单的谷歌搜索就可以找到这些映像。

Diversity and Evolution of Hashing Algorithms

SHA1 & SHA2

NSA(是的，那个NSA)一直是哈希算法标准的先驱，他们最初提出的安全哈希算法(SHA1)创造了160位固定长度的输出。

不幸的是，SHA1仅仅通过增加输出长度、单向操作的数量和这些单向操作的复杂性改进了MD5，但是对于尝试不同攻击向量的更强大的机器，它没有提供任何基本的改进。

那么我们怎样才能做得更好呢?

SHA3

2006年，美国国家标准与技术研究院(NIST)发布了一项竞赛，希望找到一种可以替代SHA2的产品，这种产品在内部结构上与SHA2有本质区别，从而成为一种标准。

因此，SHA3诞生于一种名为KECCAK(发音为ketch-ak)的哈希算法。

尽管有了这个名字，SHA3内部还是有很大的不同，它采用了一种被称为海绵结构的机制，这种机制使用随机排列来吸收和输出数据， 同时作为随机性的来源，为哈希算法的未来输入提供数据。

SHA3维护一个内部状态，其中包含更多与输出相关的信息，这使得它能够克服以前算法的局限性。NIST在2015年成为标准。

Hashing and Proof of Work

当将哈希算法集成到区块链协议中时，更老的比特币都选择了SHA256，而Ethereum使用的是经过修改的SHA3 (KECCAK256)来证明其工作算法。 然而，使用工作证明为区块链选择哈希函数的一个重要质量是计算上述哈希的效率。

比特币SHA256的实现可以通过被称为应用专用集成电路(或asic)的专用硬件来特别高效地计算。

关于在挖掘池中使用asic以及它们如何使协议趋向于集中计算，已经写了很多。

也就是说，工作证明鼓励计算效率高的计算机组聚合到池中，并增加我们所表示的“哈希能力”，即机器每隔一段时间可以计算的哈希数的度量。

Ethereum，选择了一个被称为KECCAK256的改良SHA3。

此外，Ethereum的工作证明算法Dagger-Hashimoto在硬件上是难以计算的内存。

比特币为什么选择 double SHA256

比特币使用SHA256进行数据哈希的方式很有趣，因为它在协议中对算法进行了两次迭代。

注意，这不是针对生日攻击的对策，因为很明显，如果hash(x) = hash(y)，那么hash(x)) = hash(y)。

相反，双SHA256用于减轻长度扩展攻击。

从本质上讲，这种攻击涉及到恶意的参与者，他们知道哈希输入的长度，可以通过向哈希值附加一个秘密字符串来欺骗哈希函数，使其开始其内部状态的某个部分。 SHA256是SHA2算法家族中的一员，它受到了这个问题的困扰，比特币通过计算两次哈希来减轻这个问题。

Ethereum 2.0 and BLAKE

SHA3并不是NIST 2006年哈希竞赛的唯一突破。尽管SHA3赢了，一个被称为BLAKE的算法也紧随其后。 对于Ethereum 2.0的分片实现来说，更高效的哈希几乎是一个特性需求，也是研究团队非常重视的问题。 与KECCAK256相比，BLAKE2b哈希算法在保持高度安全性的同时，其出色的效率得到了广泛的探索。

在现代CPU上，计算BLAKE2b实际上比KECCAK快3倍。

Moving Forward: The Future of Hashing Algorithms

似乎无论我们做什么，我们要么

(1)增加了内部哈希操作的复杂性，要么

(2)增加了哈希输出的长度，希望攻击者的计算机不能足够快地有效地计算冲突。

为了保证网络的安全，我们依赖于单向操作的前图像的模糊性。

也就是说，哈希算法的安全目标是使任何人尽可能难以找到两个哈希到相同输出的值，尽管可能存在无数次的冲突。

量子计算的未来呢?哈希算法安全吗?

简而言之，目前的理解是，哈希算法将经得起时间和量子计算的考验。

量子计算能够打破的是那些由精确的技巧和RSA加密等理论建立起来的严格的、基本的数学结构的问题。另一方面，哈希算法的内部结构不那么正式。

量子计算机的确提高了非结构化问题(如哈希)的计算速度，但最终，它们还是会像今天的计算机一样，强行发起攻击。

不管我们为协议选择什么算法，很明显我们正走向一个计算效率更高的未来，我们必须用我们最好的判断力来选择适合这项工作的工具，以及那些有望经得起时间考验的工具。

优秀的 hash 算法

特点

一个好的哈希函数必须具备以下两点特性：

  • 一个好的哈希函数应该是可逆的。

对于哈希函数输入值 x 和输出值 y，如果存在 f(x) = y，就一定存在 g(y) = x。

说白了，就是哈希函数可以将某一个值x转换成一个key，也可以把这个key还原回成x。

具有可逆性的哈希函数可以从根本上消除哈希过程中的冲突(collisions)。

  • 一个好的哈希函数应该容易造成雪崩效应。

这里的雪崩效应是从比特位的角度出发的，它指的是，输入值1bit位的变化会造成输出值1/2的bit位发生变化。

哈希函数应只负责将输入值尽量均匀的分布在某一空间，而不管实际的物理内存是否可以容纳该空间。

我们可以将放置哈希结果的物理内存块的大小设置成2的n次方的形式。

这条特性的主要目的是使得哈希结果更为离散均匀。

可逆性

  • 简单例子

以下式子都是可逆的：

x + 常数 = y;
x - 常数 = y;
x ^ 常数 = y;
~x = y;
x * 常数 =y;
  • 个人理解

我觉得这部分应该是数学概念上的可逆性。

反函数-百度百科

一般地，设函数 y=f(x)(x∈A) 的值域是 C，若找得到一个函数 g(y) 在每一处 g(y) 都等于 x，这样的函数 x= g(y)(y∈C) 叫做函数 y=f(x)(x∈A) 的反函数， 记作 y=f^(-1)(x) 。

反函数 y=f^(-1)(x) 的定义域、值域分别是函数y=f(x)的值域、定义域。最具有代表性的反函数就是对数函数与指数函数。

一般地，如果 x 与 y 关于某种对应关系 f(x) 相对应，y=f(x)，则 y=f(x) 的反函数为 x=f(y)。

存在反函数(默认为单值函数）的条件是原函数必须是一一对应的（不一定是整个数域内的）。

雪崩效应

雪崩效应之前也讲过，说白了，就是输入数据1bit位的变化会导致输出数据N bit位的变化，这个N是大于等于1/2输出数据长度的。我们还是从简单的运算说起。

备注：b 代表二进制

  • 加减运算

加减运算很容易引起雪崩响应，这很容易理解，例如

1111b + 1b = 10000b

or

1000b - 1b = 111b
  • 位移运算

取反运算也很容易产生雪崩效应，例如(00001111)2 « 2 = (00111100)2。

00001111b << 2 = 00111100b
  • 乘除运算

乘除运算的本质就是位移与加减法的组合，所以也是可以一起雪崩效应的。

  • 取反、异或运算

取反和异或运算也很容易产生雪崩效应，如

~1111b =0000b

and

1101b ^ 1010b = 0111b

哈希函数的设计

一个好的哈希函数应满足假设：每个关键字都等可能地被哈希到 m 个槽位的任何一个之中，并且与其他的关键字已被哈希到哪一个槽位中无关。

不幸的是，通常情况下不太可能检查这一条件是否成立，因为人们很少能知道关键字所符合的概率分布，而各关键字可能并不是完全互相独立的。

在实践中，常常运用启发式技术来构造好的哈希函数。

比如在设计中，可以利用有关关键字分布的限制性信息等。

除法哈希法和乘法哈希法属于启发式的方法，而全域哈希法则采用了随机化技术来获取良好的性能。

除法哈希法（The Division Method）

一种好的哈希做法是以独立于数据中可能存在的任何模式的方式导出哈希值。例如，除法哈希法用一个特定的质数来除所给的关键字，所得的余数即为该关键字的哈希值。

除法哈希函数可表示为：

hash(key) = key mod m

其中 key 表示被哈希的关键字，m 表示哈希表的大小，mod 为取余操作。假定所选择的质数与关键字分布中的任何模式都是无关的，这种方法常常可以给出很好的结果。

乘法哈希法（The Multiplication Method）

乘法哈希函数可表示为：

hash(key) = floor( m * ( A * key mod 1) )

其中 floor 表示对表达式进行下取整，常数 A 取值范围为（0<A<1），m 表示哈希表的大小，mod 为取余操作。

[A * key mod 1] 表示将 key 乘上某个在 0~1 之间的数并取乘积的小数部分，该表达式等价于 [A*key - floor(A * key)]。

乘法哈希法的一个优点是对 m 的选择没有什么特别的要求，一般选择它为 2 的某个幂次，这是因为我们可以在大多数计算机上更方便的实现该哈希函数。

虽然这个方法对任何的 A 值都适用，但对某些值效果更好，最佳的选择与待哈希的数据的特征有关。

Don Knuth 认为 A ≈ (√5-1)/2 = 0.618 033 988… 比较好，可称为黄金分割点。

全域哈希法（Universal Hashing）

在向哈希表中插入元素时，如果所有的元素全部被哈希到同一个桶中，此时数据的存储实际上就是一个链表，那么平均的查找时间为 Θ(n) 。

而实际上，任何一个特定的哈希函数都有可能出现这种最坏情况，唯一有效的改进方法就是随机地选择哈希函数，使之独立于要存储的元素。

这种方法称作全域哈希（Universal Hashing）。

全域哈希的基本思想是在执行开始时，从一组哈希函数中，随机地抽取一个作为要使用的哈希函数。

就像在快速排序中一样，随机化保证了没有哪一种输入会始终导致最坏情况的发生。

同时，随机化也使得即使是对同一个输入，算法在每一次执行时的情况也都不一样。

这样就确保了对于任何输入，算法都具有较好的平均运行情况。

hasha,b(key) = ((a*key + b) mod p) mod m

其中，p 为一个足够大的质数，使得每一个可能的关键字 key 都落在 0 到 p - 1 的范围内。m 为哈希表中槽位数。

任意 a∈{1,2,3,…,p-1}，b∈{0,1,2,…,p-1}。

拓展阅读

一致性 hash 算法

java hash 实现

hash 冲突处理

bloom filter

参考资料

  • hash 算法

http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm

https://segmentfault.com/a/1190000010990136

https://blog.csdn.net/jasper_xulei/article/details/18364313

https://www.cnblogs.com/hzorac/p/5399042.html

https://www.jianshu.com/p/32faad2d711f

http://blog.jobbole.com/106733/

https://blog.csdn.net/tanggao1314/article/details/51457585

  • 反函数

反函数定理

https://blog.csdn.net/u010182633/article/details/64501915

  • 感知 Hash 算法

https://blog.csdn.net/whuhan2013/article/details/50993146