哈希算法的前世，今生和未来

转载

2329 天前

13283

巴比特资讯

火讯财经注：区块链初学者都听说过哈希算法，那么哈希算法究竟是什么？

文章来源：巴比特作者：Raul Jordan

当新人在学区块链技术的时候，都会听到哈希和哈希算法，这似乎是无处不在的安全性保证。例如比特币或者以太坊这种运行去中心化网络和共识的机器，都会有上万个节点通过P2P连接，并且需要“无需可信”和可验证的效率。这些系统需要将信息写入紧凑的格式，从而通过参与者进行保证安全和快速验证。

比特币和以太坊主要的primitive是区块的notion，这是包含转账信息，时间戳和其他重要数据的数据结构。他们安全性的重要部件，就是能够压缩网络全部的状态信息，变成很短，并且标准的信息，在需要的时候可以进行有效验证，这就被称之为哈希。

到处都会使用加密哈希，从密码存储到文件验证系统。使用确定性算法的基本原理，就是使用一个输入，并且每次都产生一个固定长度的字符串。也就是说，使用同样的输入总是会导致同样的输出。

确定性不仅对哈希很重要，而且可以改变输入的单个字符会产生完全不同的哈希。

哈希算法的问题是碰撞（collisions）的必然性。哈希是固定的字符串，意味着对于每个输入，不同的输入都会产生同样的输出。碰撞（collisions）是不好的。这意味着如果有攻击者能够根据需求创建这种collisions，那么他就可以让欺诈文件或者数据看起来像正确的，合适的哈希，并且冒充合法。优质哈希功能的目标是让攻击者很难找到，获得输入数据的方法。

计算哈希不应该太简单，因为这会让对于攻击者来说，计算collisions也变得很容易。哈希算法需要对“预攻击”有抵抗性。也就是说，给定哈希，应该很难计算追溯确定性的步骤来重新产生由哈希创建的数值。

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

概括来看，“好的”哈希算法会有以下3种特性：

-在输入中改变一个字符，应该会创建雪崩效应，从而导致完全不同的哈希

-很低的概率会产生collisions

-提高效率，但是不会牺牲collision的对抗性

破散哈希

其中一个初始哈希算法标准是MD5哈希，这是被广泛用来进行文件整合验证，而且存储哈希密码在网页应用数据库。这个功能非常简单，因为输出是固定的，128个字符串对于每个输入，并且使用几轮微不足道的单向运算来计算其确定性输出。它的输出长度短，操作简单，使得MD5彻底易碎，被称为生日攻击。

“生日攻击”是什么？

我们曾经听过，如果你把23个人放在一个房间，就会有50%的概率，其中的2人会有同样的生日？将这个数字提升到70人在一个房间，就会有99.9%的概率。这就是我们所说的鸽巢原理，也就说如果把100个各自放到99个箱子，你就必须在1个盒子里面放2个鸽子。换句话说，固定的输出意味着collisions 可能会找到固定的排序。

其实，MD5对于collision的抵抗是很脆弱的，家庭使用的2.4GHz处理器就可以在几秒钟算出哈希collision。而且，对于现在网页的早期使用，还可以在网络上创建很多MD5的预图形，如果搜索哈希，就可以在谷歌上很容易找到。

哈希算法的多样化和革新

开始：SHA1 &SHA2

NAS被称为哈希算法标准的先驱，最初的想法是安全哈希算法或者SHA1，创建了160固定长度的输出。不幸地是，SHA1通过增加了输出长度，单向操作的数量，还有单向操作的复杂性，从而形成了MD5算法，但是这不会提供任何基础的提升，来对抗更有力量的机器来尝试不同的攻击。

我们怎么才能做得更好呢？

进入SHA3时代

在2006年，国家标准和技术研究院提出了一个比赛，来找到SHA2的替代，这在本质上九不同，从而形成了标准。因此，SHA3作为现在所知的KECCAK哈希算法一部分，就这样诞生了。

尽管表面看起来是相同的，SHA3通过一个被称为海绵结构的机制，让内部变得非常不同，这使用了随机的排列来输入和输出数据，同时也为未来的输入提供了随机的来源，这会进入到哈希算法中。

HA3维持了内部的状态并且有和输出相关的更多信息，这可以防止之前算法的限制。在2015年，通过NIST成为了标准。

哈希算法和工作量证明

当考虑到整合哈希算法到区块链协议中的时候，比特币使用了比较旧的SHA256算法，但是以太坊使用了修改后的SHA3算法，作为工作量证明的算法。选择工作量证明区块链的哈希功能是很重要的部分，但是计算的效率称为哈希。

比特币SHA256算法通过特定的硬件ASIC，进行有效计算。在矿池中，很多都是在ASIC上写入的算法，但是这也会使得整个协议往中心化计算发展。也就是说，工作量证明激励了有效计算机器来聚集成矿池，同时也增加了哈希力。或者一种机器可以计算每个时间间隔的哈希数量。

以太坊，使用的是被称为KECCAK256的改进SHA3。而且，以太坊的工作量证明算法，Dagger-Hashimoto意味着意味着内存难以计算硬件。

为什么比特币使用双重SHA256算法？

比特币通过SHA256算法，会有很有趣的方式来获得哈希数据，因为它会在协议中运行算法的2次迭代。需要注意地是，这并不是生日攻击的对策，因为很明显如果hash(x) = hash(y)，那么hash(hash(x)) = hash(hash(y))。但是，双重SHA256算法是被使用来减轻长度扩展攻击。

本质上来说，这类攻击包括，恶意欺诈的人知道哈希输入的长度，可以用来欺骗哈希来开始内部状态的某个部分，通过附加一个私密字符串到哈希值。SHA256，是SHA2算法大家庭中的一个，逃离这个陷阱，比特币通过计算哈希两次来减轻它。

以太坊2.0和BLAKE算法

SHA3并不是来自2006年NIST哈希比赛的唯一突破。尽管SHA3获得胜利，称为BLAKE的算法获得第二。对于以太坊2.0分片技术的部署，更有效的哈希几乎是个特性要求，研究团队非常重视。BLAKE2b哈希算法，这是BLAKE的更新版本，在和KECCAK256算法相比的时候，它由于效率很高正在被广泛使用，同时也保证了很高的安全性。

BLAKE2b的计算速率实际上是比KECCAK在现代CPU上要快3倍。

哈希算法的未来

不论我们怎么做，我们只能（1）提高内部哈希操作的复杂性，或者（2）提高哈希输出的长度，希望攻击者的计算机不会足够快到能够有效地计算collision。

我们依赖于网络安全单向操作前图像的模糊性。也就是说，哈希算法的安全目标是让所有人尽可能困难地找到能够获得同样哈希输出的数值，尽管对于可能的collision，其数值是有限的。

未来有量子计算机了？哈希算法还安全吗?

根据现在的理解，答案是肯定的。哈希算法将经受量子计算机的考验。量子计算能够打破的东西，是严密的，用巧妙的技巧和理论建立的底层数学架构，例如RSA加密。另个方面来看，哈希算法在内部的框架中，有更少的形式结构。

量子计算机确实加快了计算的速度，例如哈希算法，但是最后，它们也会被利用来进行如同现在计算机的攻击。

不论我们为协议选择了什么算法，很清楚地是我们都处于有效计算的未来，而且我们必须要使用最好的方式来获得正确的工具，以及那些希望能经受时间考验的人。