块链科学:散列函数算法

散列值和散列函数的概念是两个对区块链不熟悉的人经常听到的关键词，而且似乎对安全特别重要。(事实上，的确如此。对于像比特币和以太网这样通过P2P方式由成千上万个节点组成的分散网络来说，“无信任”和验证效率无疑是关键。也就是说，这些系统需要找到一种将信息编码成紧凑形式的方法，同时使参与者能够安全快速地验证信息。

比特币和以太网处理的主要内容称为“块”，即由交易、时间戳和其他重要元数据组成的数据结构。比特币和以太网网络安全的关键在于，它可以将表达网络全局状态的大量信息压缩成一条短消息。必要时，我们可以有效地验证此消息的真实性。这个过程由散列函数完成，结果(消息)是散列值。

即使输入中只有一个字符被更改，结果得到的哈希值也会完全不同

密码哈希广泛用于密码存储和文件验证系统。简而言之，加密散列函数是一种确定性算法，无论输入什么值，它都可以得到一个固定长度的字符串。也就是说，相同的输入值总是对应于相同的输出值。

对于散列函数，不仅对于确定性(而且对于结果的随机性)很重要：即使输入中只有一位被改变，最终的散列值也会完全不同。

哈希算法有一个不可避免的问题，叫做碰撞概率。因为哈希值是一个固定长度的字符串，所以相同的输出哈希值可能对应多个输入。碰撞会产生严重的后果。如果有人可以根据需要发起冲突攻击，他可以将恶意文件或数据伪装成合法的、经过验证的、具有适当哈希值的文件。一个好的散列函数的设计目标是使攻击者很难找到方法来找到对应于同一散列的不同输入。

哈希计算的效率不应太高，以免攻击者更容易人为计算冲突。哈希算法必须能够抵抗“预镜像攻击”。也就是说，对于特定的散列值，攻击者很难通过确定性计算步骤来推断输入值(即，原始图像)。

假设s=散列(x)，应该几乎不可能推回x。

一般来说，一个“好的”哈希算法需要具备以下三个特征：

改变输入中的一位会产生雪崩效应，导致完全不同的哈希值

哈希冲突的概率非常低

在不牺牲防碰撞性能的情况下，计算效率是可以接受的

破解哈希算法

哈希算法的初始标准之一是MD5哈希。MD5哈希广泛用于文件完整性验证(校验和)，以及在网络应用程序数据库中存储哈希帐户密码。MD5的功能非常简单，因为它将每个输入转换成一个固定的128位字符串输出，并通过几个简单的单向操作来计算确定性输出。由于输出值长度短，操作简单，MD5容易被破解。一种常见的攻击方法称为生日攻击。

什么是生日攻击？你听说过这样的事实吗？如果你把23个人放在一个房间里，两个人生日相同的概率是50%。如果把70个人放在一个房间里，两个人同一天生日的概率高达99.9%。这就是我们所说的鸽子笼原则，也就是说，如果把100只鸽子放进99个鸽子笼，两只鸽子必须共用一个鸽子笼。也就是说，固定长度的输出意味着在所有的输入输出组合中都必须有冲突。

当笼子不够的时候，鸽子会聚在一起

事实上，MD5的防冲突性能非常差，以至于2.4千兆赫奔腾处理器可以在几秒钟内计算出散列冲突。此外，由于MD5在互联网的早期已经被广泛使用，大量的MD5图片在互联网上被泄露，这可以通过谷歌搜索它们的哈希值来找到。

哈希算法的多样化发展

国家安全局(没错，国家安全局)是哈希算法标准的先驱。安全散列算法(SHA1)是最早提出的标准，它将输出值的长度固定在160位。不幸的是，SHA1只在MD5的基础上增加了输出值的长度、单向运算的数量和复杂性，却没有做出根本性的改进来抵御更强大的机器攻击。

我们如何做得更好？

2006年，国家标准与技术研究所(NIST)举办了一场竞赛，寻找一种与SHA2本质上不同的替代标准。因此，SHA3应运而生，它是KECCAK哈希算法的一种方案。

尽管SHA 3与SHA1和SHA2同名，但它在本质上有很大不同，因为它采用了一种称为海绵结构的机制。该机制使用随机排列来吸收和输出数据，同时为哈希算法中使用的未来输入值提供随机性。

KECCAK256海绵结构如何进行输入操作

与输出值相比，SHA3的内部状态信息更多，突破了以往算法的局限性。NIST于2015年正式批准了SHA3标准。

哈希计算和工作量证明

就集成到区块链协议中的哈希算法而言，早期的比特币选择了SHA256，而以太网采用了改进的SHA3 (KECCAK256)作为工作量证明算法。对于具有工作量证明的区块链来说，选择散列函数的一个重要标准是散列运算的效率。

使用一种称为专用集成电路的硬件，可以大大提高比特币SHA256算法的哈希运算效率。许多文章解释了挖掘池如何使用专用集成电路，以及专用集成电路如何使协议趋向于以计算为中心。也就是说，工作量证明了具有高计算效率的机器将被激励来收集成矿池，从而形成大的散列计算力(计算力的度量是采矿机器在每个时间间隔内能够完成多少散列操作)。

Ethereum选择了改进的SHA3算法(称为KECCAK256)。此外，以太网的工作负载证明了Dagger-Hashimoto算法是以内存密集型的方式设计的，计算硬件需要更多的内存来提高计算效率。

那么，为什么比特币使用双SHA256？有趣的是，比特币协议需要运行SHA256算法两次。请注意，这不是为了防御生日攻击。毕竟，当散列(x)=散列(y)时，散列(x)=散列(y))。双SHA256设计用于抵抗长度扩展攻击。

本质上，所谓的长度扩展攻击意味着，如果恶意攻击者知道散列输入的长度，他可以向散列值添加一个秘密字符串，并欺骗散列函数从其内部状态的特定部分进行计算。作为SHA2算法家族的一员，SHA256也有这个缺陷。因此，比特币采用两次哈希计算的方法来解决这一缺陷。

SHA3并不是哈希算法竞赛中的唯一突破。尽管SHA3最终赢得了比赛，但BLAKE算法紧随其后，排名第二。对于以太网2.0的实现，一个更有效的哈希算法可以说是一个功能性的需求，这是研究团队非常重视的。BLAKE2b哈希算法是BLAKE算法的高度升级版本。与KECCAK256相比，BLAKE2b哈希算法不仅保持了较高的安全性，而且在提高效率方面进行了深入的探索。

用一个现代的中央处理器来计算黑洞2b比计算黑洞2快三倍。

哈希算法展望

因此，无论我们做什么，它都是(1)增加内部哈希运算的复杂性，或者(2)增加哈希输出值的长度，这样攻击者的计算机就不能快速有效地计算冲突。

我们依靠单向操作的模糊性来保护网络的安全。也就是说，哈希算法的安全目标是当存在无限可能的冲突时，尽可能难以发现哈希冲突。

如果量子计算时代到来，哈希算法仍然安全吗？

目前，答案是肯定的。哈希算法将经得起时间的考验，并抵抗量子计算。量子计算可以解决那些严格遵循一些小技术或RSA加密理论来构建底层结构的数学问题。另一方面，哈希算法的内部结构不太正式。

量子计算机确实可以加速散列等非结构化问题的计算，但它们最终会像今天的计算机一样诉诸暴力。

无论我们为协议选择哪种算法，我们都在朝着计算效率的未来前进。因此，我们必须仔细选择最合适的工具，使它经得起时间的考验。