区块链数字货币各类哈希算法分析与差异比较

区块链数字货币各类哈希算法分析与差异比较

谁能想到,我们之前用作校验文件,核验数据的一种算法,现在却奠定了区块链数字货币帝国大厦,这个算法有很多名字,比如一般叫做哈希算法(HASH的英文而来),有的也称在杂凑算法(很形象~~)或者散列算法等(以下我们统称哈希)。那么现在我们就来解开这种算法的层层面纱,在本文中,我们将解析加密货币中最常用的四种加密哈希函数的特性和差异。但在此之前,还是需要了解哈希的含义。

什么是HASH(哈希)

简单来说,哈希意味着输入任意长度的字符串通过密码运算来实现固定长度的输出。在像比特币这样的加密货币的情况下,交易被视为输入并通过哈希算法(比特币使用SHA-256)运行(该算法提供固定长度的输出)。

先了解下哈希算法是如何工作的。我们以SHA-256(256位安全哈希算法)为例。

在SHA-256的情况下,无论你的输入有多大或多小,输出总是有一个固定的256位长度。这对于处理大量的数据和事务校验时非常关键,这里先看看哈希函数的各种特性以及它们在区块链中的实现方式。

加密哈希算法特性

哈希算法其特俗的特性使得非常适合密码应用,加密哈希算法具有以下几个特性:

特性 1:确定性

这意味着无论 你通过哈希函数解析特定输入多少次, 你都会得到相同的结果。这是至关重要的,因为如果每次都得到不同的哈希值,就不可能跟踪输入。

特性2:快速计算

哈希函数应该能够快速返回输入的哈希。

性质3:单向性

单向性指的是:假设A是输入数据并且H(A)是输出哈希结果,假设给定H(A)来倒推出A是“不可行”的(注意使用“不可行”一词而不是“不可能”)。

因为我们已经知道从它的哈希值中确定原始输入并不是“不可能”的。举个例子吧。

假设你掷骰子,输出是骰子出现的数字的哈希。我们将如何确定原始号码是什么?很简单,所要做的就是从1-6中找出所有数字的哈希值并进行比较。由于哈希函数是确定性的,所以特定输入的哈希总是相同的,因此 我们可以简单地比较哈希并找出原始输入。

但是,只有在给定的数据量非常少的情况下,这才有效。当你有大量的数据时会发生什么?假设你正在处理128位哈希。唯一必须找到原始输入的方法是使用“暴力群举”。暴力群举基本上意味着你必须选取一个随机输入,对其进行哈希,然后将输出与目标哈希进行比较并重复,直到找到匹配。

如果你使用这种暴力方法后:

最好的结果: 你可能在第一次尝试时获得答案,不过这只是理论上的可能,因为他的概率是2的128次方分之1(自己去算算)。

最坏的情况:你在2 ^ 128 - 1次之后得到答案。基本上,这意味着你会在所有数据的末尾找到你的答案。

平均情景:在2 ^ 128/2 = 2 ^ 127次之后, 你会在中间的某处找到它。从这个角度来看,2 ^ 127 = 1.7 *10 ^ 38。换句话说,这是一个巨大的数字。

所以,虽然可以通过暴力方法来打破单向性,但同时也要有巨大的算力投入。

特性4:雪崩效应。

即使 你对原始输入数据进行了小改动,哈希的结果差异也非常大。让我们使用SHA-256对其进行测试:

即使你只是改变了输入的第一个字母表的大小写,看看它对输出哈希值有多大影响。

这个特性也被称为雪崩效应。

区块链数字货币各类哈希算法分析与差异比较

雪崩效应

性质5:防碰撞

给定两个不同的输入A和B,其中H(A)和H(B)是它们各自的哈希,H(A)等于H(B)是不可行的。这意味着大多数情况下,每个输入都会有自己独特的哈希。为什么我们说“大部分”?为了理解这一点,我们需要知道什么是“生日悖论”。

什么是生日悖论?

如果你在街上碰到任何陌生人,那么你们两个都有相同的生日的可能性非常低。事实上,假设一年中的所有日子都有生日的可能性,另一个人分享你的生日的机会是1/365,这是0.27%:概率非常低。

不过,如果你在一个房间里聚集20-30人,那么两个分享完全相同生日的人的几率会大幅度上升。

区块链数字货币各类哈希算法分析与差异比较

生日悖论

这是基于一个简单的概率原理:

假设你有一个事件发生N种不同的可能性,那么你需要N个随机项的平方根,以使它们有50%的碰撞几率。

因此,将这个理论应用于生日时, 你有365种不同的生日可能性,所以 你只需要Sqrt(365),即约23%,随机选择两个人分享生日的可能性为50%。

假设你有一个128位哈希,有2 ^ 128种不同的可能性。通过使用生日悖论,你有50%的几率在sqrt(2 ^ 128)= 2 ^ 64的情况下打破防碰撞机制。

正如你所看到的,打破防碰撞要比打破单向性容易得多。所以,如果你使用的是SHA-256这样的函数,假设如果H(A)= H(B),那么A = B是可以认为成立。

那么,你如何创建一个抗碰撞的哈希函数?为此,我们使用一种称为Merkle-Damgard的结构。

什么是Merkle-Damgard结构?

该结构非常简单,并且遵循以下原则:给定短消息的防碰撞哈希函数,我们可以为长消息构造防碰撞哈希函数。

区块链数字货币各类哈希算法分析与差异比较

Merkle-Damgard

记住上面的图表,注意以下几点:

较大的消息M被分解为m [i]的较小块。

哈希函数H由许多较小的哈希函数“h”组成。

“h”是一个较小的哈希函数,又称压缩函数,它接收一小块消息并返回一个哈希。

第一个哈希函数“h”(在上图中圈出)接收第一个消息块(m [0]),并添加一个固定值IV并返回哈希值。

哈希现在被添加到第二个消息块并通过另一个哈希

函数h,并且这一直持续到最后的消息块,其中填充块PB也被添加到消息中。

每个压缩函数h的输出被称为链接变量。

填充块是一系列1和0。在SHA-256算法中,PB长64位。

哈希压缩函数h的输出是大消息M的输出。

几种加密哈希函数的举例与比较

既然已经了解了哈希方法以及加密哈希函数的特性,让我们熟悉一些加密货币中最常用的加密哈希函数。

先把几种加密哈希算法列出来:

MD 5:它产生一个128位哈希。在~2 ^ 21哈希后,防碰撞机制被打破。

SHA 1:生成一个160位哈希。经过2 ^ 61次哈希后,防碰撞机制被打破。

SHA 256:产生一个256位哈希。这是目前比特币正在使用的。

Keccak-256:产生256位哈希,目前由Ethereum使用。

RIPEMD-160:产生160个输出,由比特币脚本(和SHA-256)使用。

CryptoNight:Monero使用的哈希函数。

安全哈希算法(SHA)

安全哈希算法是由美国国家标准与技术研究院(NIST)发布的美国联邦信息处理标准(FIPS)的一系列加密哈希函数。SHA由以下算法组成:

SHA-0:指1993年发布的名为“SHA”的原始160位哈希函数。由于未公开的“重大缺陷”,并在稍后修订的版本SHA-1中取而代之,它在出版后不久被撤回。

SHA-1:当SHA-0传送失败时被引入。这是一个160位哈希函数,类似于早期的MD5算法。这是由国家安全局(NSA)设计的数字签名算法的一部分。然而,人们注意到加密图形的弱点之后不久就被抛弃了。

SHA-2:现在我们来看一下哈希函数中最受欢迎的类别之一。它是由NSA使用Merkle-Damgard范例设计的。它们是具有不同字长的两种哈希函数族:SHA-256和SHA-512。比特币使用SHA-256

SHA-3:之前被称为keccak,它在2012年被非NSA设计师的公开竞争之后选中。它支持与SHA-2相同的哈希长度,其内部结构与SHA系列的其他部分有很大不同。以太坊使用这个哈希函数。

区块链数字货币各类哈希算法分析与差异比较

各类哈希比较

让我们仔细看看SHA-256和SHA-3。

SHA-256

SHA-256是一个SHA-2函数,它使用32个单词,而不是使用64位单词的SHA-512。比特币在以下两种情况下使用SHA-256:

采矿。

创建地址。

采矿:

比特币采矿涉及矿工解决复杂的计算难题,以找到一个块,然后将其附加到比特币区块链。就是我们经常称的工作量证明(proof-of-work),它涉及SHA-256哈希函数的计算。

创建比特币地址、;

SHA-256哈希函数用于哈希比特币公钥以生成公共地址。哈希密钥为身份认证增加了一层额外的保护。此外,哈希地址的长度仅比存储更好的比特币公钥更短。

SHA-256运行实例:

输入:Hi

输出:98EA6E4F216F2FB4B69FFF9B3A44842C38686CA685F3F55DC48C5D3FB1107BE4

SHA-3

如上所述,这种算法以前被称为keccak,并被以太坊使用。它是在non-NSA设计师的公开竞赛之后创建的。SHA-3使用“海绵(sponge)机制”。

什么是海绵机制?

海绵功能是具有有限内部状态的一类算法,其获取任意长度的输入比特流并产生预定长度的输出比特流。

在继续之前,我们需要定义一些术语:

我们知道,在海绵功能中,数据被“ 吸收 ”到海绵中,然后将结果“ 挤出 ”。

所以有一个“ 吸收 ”阶段和一个“ 挤压 ”阶段。

区块链数字货币各类哈希算法分析与差异比较

海绵机制

SHA-3举例:

输入:Hi

输出:154013cb8140c753f0ac358da6110fe237481b26c75c3ddc1b59eaf9dd7b46a0a3aeb2cef164b3c82d65b38a4e26ea9930b7b2cb3c01da4ba331c95e62ccb9c3

RIPEMD-160哈希函数

RIPEMD是由比利时鲁汶的Hans Dobbertin,Antoon Bosselaers和Bart Preneel在鲁汶Katholieke大学的COSIC研究小组开发的一系列加密哈希函数,并于1996年首次发布。

虽然RIPEMD基于MD4的设计原则,但其性能与SHA-1非常相似。RIPEMD-160是这种哈希函数的160位版本,通常用于生成比特币地址。

比特币公钥首先通过SHA-256哈希函数运行,然后通过RIPEMD-160运行。这样做的原因是因为160位的输出比256位小很多,这有助于节省空间。

除此之外,RIPEMD-160是唯一性哈希函数,可以产生最短哈希,其唯一性仍然得到充分保证。

区块链数字货币各类哈希算法分析与差异比较

RIPEMD-160

上面的图像显示了RIPEMD-160哈希算法压缩函数的子块快照。

RIPEMD -160实例:

输入:Hi

输出:242485ab6bfd3502bcb3442ea2e211687b8e4d89

CryptoNight哈希函数

现在我们拥有由Monero使用的CryptoNight哈希函数。与比特币不同,Monero希望他们的采矿尽可能地不利于GPU。他们可以做到这一点的唯一方法是让他们的哈希算法难以记忆。

输入CryptoNight

CryptoNight是一种内存硬件哈希函数。它被设计为在GPU,FPGA和ASIC体系结构上无法有效计算。CryptoNight的工作原理如下:

该算法首先用伪随机数据初始化一个大暂存器。

之后,大量的读/写操作发生在伪随机地址上

包含在便签簿中。

最后,整个暂存器被哈希以产生最终值。

区块链数字货币各类哈希算法分析与差异比较

CryptoNight

下图显示了CryptoNight哈希算法的示意图。

CryptoNight实例:

输入:This is a test

输出:a084f01d1437a09c6985401b60d43554ae105802c5f5d8a9b3253649c0be6605

结论

加密货币中最常用的四种哈希算法基本都在这里了。对他们的工作方式有一个基本的认知将让我们更好的理解各类数字货币的区别(比如采矿)。

本文链接:

http://ulian.io/post/1560


TAGS