HASH算法原理_推理方法未来_蓝狐笔记

前言：哈希算法对于保证区块链网络的安全非常重要。为了降低哈希碰撞的可能性，要么增加哈希内部运算的复杂度，要么增加哈希输出的长度，希望攻击者的计算速度不够快。本文分析了哈希算法的历史、原理和未来，对我们理解区块链的安全问题很有帮助。这篇文章的作者是劳尔乔丹。文章来自medium.com，由蓝狐笔记社区“李希和”翻译。

新手在学习区块链时，经常会接触到哈希、哈希算法等概念，在安全性方面可以说是无所不在。通过 P2P 运行具有许多节点（如比特币和以太坊）的去中心化网络需要无需信任的机制和有效的验证。

也就是说，这些系统需要找到以高效简洁的方式对信息进行编码的方法，并允许其参与者安全快速地进行身份验证。

比特币和以太坊涉及的主要概念是“块”，一种包含交易记录、时间戳和其他元数据的数据结构。这种数据结构安全性的关键在于，它可以将大量关于全球网络状态的信息压缩成一小段信息标准，而这一小段信息可以得到高效的验证。这一小段信息称为哈希。

即使改变输入消息的一个字符也会导致完全不同的哈希值！

从密码存储到文档验证系统，各种行业都使用加密哈希。基本思想是使用确定性算法交易区块哈希值如何生成，每次都接受输入并生成固定长度的字符串。也就是说，相同的输入总是会得到相同的输出。

除了这种确定性之外，散列算法还有另一个属性：输入的任何微小变化都可能导致输出完全不同。

哈希算法的一个问题是冲突的不可避免性。意思是由于哈希函数输出的字符串有一定的长度，不同的输入可能产生相同的哈希值。碰撞是不好的交易区块哈希值如何生成，如果攻击者可以故意产生碰撞，他可以将恶意文件或数据伪装成正确的哈希并传递它们。一个好的散列函数的目标是让冲突几乎不可能发生。

计算哈希值不应该太高效，因为它会使冲突太容易实现。散列算法应该能够抵抗“原像攻击”。也就是说，根据已知的哈希值找到输入值应该是非常困难的（输入值称为原像，例如 s = hash(x)，根据 s 找到 x 应该几乎是不可能的） .

总结起来，一个好的哈希算法应该具备以下特点：

攻击哈希

原始哈希算法标准之一是 MD5 哈希，它广泛用于文件完整性验证（校验和），并用于将哈希密码存储在 Web 应用程序的数据库中。当时它相当简单，因为无论输入如何，输出都是一个固定的 128 位字符串，并且它在几轮中使用低效的单向运算来计算确定性输出。

由于输出字符串短，操作简单，MD5容易破解，容易受到生日攻击。

什么是“生日攻击”？

你可能听说过：如果一个房间里有 23 个人，那么有 50% 的机会两个生日会重叠，如果增加到一个房间里有 70 个人，那么这个概率就会发生变化。它变成了 99.9%。这就是鸽巢原理，如果有 100 只鸽子只有 99 个洞，那么一个洞一定有两只鸽子。

在哈希算法的情况下，固定长度的字符串意味着固定数量的排列，所以当输入值达到一定数量时，必然会发生冲突。

鸽子太多了！至少有一只鸽子会与另一只鸽子共用一个洞。

MD5 对碰撞的抵抗力非常弱，以至于 2.4GHz Pentium 可以在几秒钟内制造出一个哈哈希腊冲突。事实上，由于早些年 MD5 的广泛使用，网上已经有大量原图被泄露，你甚至可以通过简单的谷歌搜索找到它们。

多样性和哈希算法演进

开始：SHA1 和 SHA2

美国国家安全局一直是哈希算法标准的先驱，他们首先提出了一种安全的哈希算法，也称为SHA1，它输出一个160位的固定长度字符串。

但是SHA1相对于MD5只是增加了输出的长度、单向运算的数量、单向运算的复杂度，并没有做任何根本性的改进来使其能够抵抗更强大的机器，这些机器尝试不同的攻击向量。

那么我们该如何改进呢？

SHA3

2006 年，美国国家标准与技术研究院 (NIST) 开始寻找一种完全不同的 SHA2 替代方案，使其成为新的算法标准。因此，SHA3的诞生是散列算法伟大机制的一部分，称为KECCAK。

虽然名称看起来很相似，但 SHA3 在内部与之前的算法完全不同，因为它具有 Sponge Construct 机制。这种结构使用随机排列来吸收和输出数据，同时也为未来的输入值提供随机性来源。

KECCAK256海绵结构作用于输入值

SHA3 维护一个内部状态，使输出消息比字符串长度更长（仍然能够压缩信息），这使它能够克服以前算法的限制。它也在 2015 年成为 NIST 的标准算法。

哈希和 PoW

当哈希算法被集成到区块链协议中时，旧的比特币选择了SHA256算法，而以太坊选择了改进后的SHA3版本（KECCAK256）用作PoW算法。

在区块链PoW协议中选择哈希函数的一个重要标准是计算哈希值的效率。

比特币的SHA256算法的执行效率可以通过制作ASIC等专用硬件来进一步提高。这体现在矿池中 ASIC 的使用上，而且协议往往是计算中心化的。

也就是说，PoW 鼓励高效的计算组聚合成更大的组（矿池），以增加我们所说的哈希算力（即一台机器在固定时间间隔内可以计算的哈希数）。

以太坊选择了改进的 SHA3，也称为 KECCAK256。另外，以太坊的PoW算法（Dagger-Hashimoto）被设计成在硬件内存中难以计算，这在一定程度上避免了ASICs对矿工的使用。

为什么比特币使用双 SHA256？

比特币使用 SHA256 转换数据的方式很有趣，它在协议中连续两次执行该算法注意，这不是为了防御生日攻击，显然如果 hash(x) = hash(y) then also hash (hash(x)) = hash(hash(y))，但为了缓解长度扩展 ) 攻击。

本质上，这种攻击需要恶意攻击者知道散列输入值的长度，在这个已知长度上添加一个秘密字符串，并在散列函数内部启动散列函数的一部分，从而扰乱散列函数。由于 SHA256 是 SHA2 算法家族中的一员，它有这样的缺点，而比特币通过连续运行两次哈希函数来缓解这个缺陷。

以太坊2.0 和布莱克

SHA3 并不是 NIST 在 2006 年发起的竞赛中的唯一突破。虽然 SHA3 最终获胜，但紧随其后的是一种名为 BLAKE 的算法，它排名第二。对于以太坊2.0 shards的执行，更高效的哈希算法可以说是必不可少的。

BLAKE2b 哈希算法是一场竞赛 此后，高度升级和优化的版本因其高效率（与 KECCAK256 相比）在保持高度安全性的同时得到了彻底的测试。

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

哈希算法的未来

看来无论我们做什么都是（1）增加哈希函数内部操作的复杂度，或者（2）增加哈希输出的长度，希望攻击者的计算机速度不够快，无法有效地产生计算冲突。

我们网络的安全性目前依赖于单向操作原像的模糊性。也就是说，散列算法的安全目标是让任何人尽可能难以找到两个相同输出的值，从而使散列冲突的概率尽可能小，尽管仍然有无穷多个可能的冲突。

量子计算呢？面对量子计算，哈希算法是否足够安全？

按照目前的理解，简单的答案是：安全。哈希算法将能够承受量子计算的挑战。量子计算能够破解诸如 RSA 之类的加密问题，这些问题具有由巧妙的技巧和理论构建的严格的底层数学结构。哈希算法的内部结构中没有这种形式的结构。

量子计算机确实可以加速计算非结构化问题（如哈希），但归根结底，量子计算机发起攻击的方式仍然是蛮力，与传统计算机没有什么不同。

无论我们选择何种算法，很明显我们正朝着计算效率更高的未来迈进，我们必须尽最大努力挑选最好的工具并经受住时间的考验。