星期五 , 3月 29 2024
首页 / 区块之心 / 什么是哈希函数

什么是哈希函数

今天我们来看看比特币的一个重要概念:哈希函数。本文首先介绍了什么是哈希函数以及哈希函数的抗碰撞性、隐秘性和谜题友好三大特性。再结合区块链的特性,分享了哈希函数在区块链挖矿工作量证明中的具体应用,并简单讲解了哈希函数与防篡改性的关系。

全文约2600字,大概需要阅读8分钟。

01

     什么是哈希函数

 

哈希函数(Hash Function)是加密算法哈希算法中广泛应用的一种函数,也称为散列函数或杂凑函数。哈希函数作为公开函数,可以将任意长度的消息M映射成为一个长度较短且长度固定的值H(M),称H(M)为哈希值或者消息摘要(Message Digest)。哈希运算是一种单向密码体制,即一个从明文到密文的不可逆映射,只有加密过程,没有解密过程。它的函数表达式为:

y = H(x)

安全哈希算法(Secure Hash Algorithm 256,SHA-256)是比特币经常使用的一种哈希函数,本文主要以 SHA-256算法为例。无论输入是什么数字格式、文件有多大,哈希运算输出的都是固定长度的比特串,比如在二进制下有256bit,即256 个0或者1组成的串,用16进制数字表示的话是64位,例如:

我们常用的16进制:

0xd7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592

转为2进制:

1101011110101000111110111011001100000111110101111000000010010100011010011100101010011010101111001011000000001000001011100100111110001101010101100101000111100100011011010011110011011011011101100010110100000010110100001011111100110111110010011110010110010010

 

02

哈希函数的三大特性

 

要使哈希函数达到密码安全,需要附加以下三个特性:碰撞阻力、隐秘性、谜题友好。

特性1:碰撞阻力

Hash 函数 H 将可变长度的数据块 M 作为输入,产生固定长度的 Hash 值 h =  H(M)。称 M 是 H 的原像。因为 H 是多对一的映射,所以对于任意给定的 Hash 值 H,对应有多个原像。如果满足 x ≠ y 且 H(x) = H(y),即两个不同的输入 x 和 y 产生相同的输出 H(x) = H(y),则称为碰撞。如果对于哈希函数 H(x),没有人能够找到碰撞,则称该函数具有碰撞阻力。

对于给定的数据 X ,很容易算出哈希值 H = H(M);但根据 H 很难反算出 X;很难找到 X 和 Y 使得 H(X) = H(Y)。事实上,把大空间的消息压缩到小空间上,碰撞肯定是存在的。

假设哈希值长度固定为256位,如果顺序取1,2,…2^256+1,这2^256+1个输入值,逐一计算其哈希值,肯定能找到两个输入值使得其哈希值相同。但不要高兴的太早,因为你得有时间把它算出来,才是你的。

对于哈希值长度为256位的哈希函数,平均需要完成2^128次哈希计算,才能找到碰撞对。如果计算机每秒进行10000次哈希计算,需要约10^27年才能完成2^128次哈希计算。

 

特性2:隐秘性

隐秘性指的是当输入 r 选自一个高阶最小墒的概率分布,在给定 H(r||x) 条件下确定 x 是不可能的。简单的说,就是无法从输出得到输入。设 y=H(x) ,如果我们知道 y,很难迅速找到满足符合条件的 x,则称哈希函数 H(x) 具有隐蔽性。隐蔽性意味着几乎不可能找到其反函数 x’=H'(y),实际上满足条件的 x 应该多个,这里隐蔽性要求哪怕1个也找不出来。这是因为上面提到的哈希函数单向性,对于给定的Hash值,在 2^128次哈希计算量下是不可行的。

隐秘性的一个应用是“承诺”,将信息(message)和一个随机数(nounce)作为输入,所得的输出即为承诺。这里的承诺包含两方面的意思:通过承诺,其他人无法知道你的输入;而你一旦公开了承诺,你无法欺骗别人该承诺是另外一个信息。所以,这里应用到了隐秘性。此外,每次的承诺都需要一个新的的随机数,这对承诺的安全性很重要。

 

特性3:谜题友好

如果对于任意 n 位输出值 y,假定 k 选自高阶最小熵分布,如果无法找到一个可行的方法,在比2的 n 次方小很多的时间内找到 x,保证 H(k||x) = y 成立,那么我们称哈希函数 H 为谜题友好。在搜索谜题这个应用中,我们将建立一个搜索谜题,该谜题是一个需要对庞大空间进行搜索,才能找到解决办法的数学问题。简单来说,就是要求具有随机性,任意输入可以得到固定位数的输出,很难找到输入和输出之间的任何关联性,哪怕是稍微调整输入,得到的输出都具有随机性,除了通过调整输入内容进行“暴力试算”,没有其他更好的办法。

碰撞阻力,隐秘性,谜题友好,各有侧重,而又相互贯通。特别是隐秘性和谜题友好,十分相似,对于想深度理解的读者,需要指明的是隐秘性说的是确定x,谜题友好说的是找到k。对于哈希函数 H(x),我们做出如下总结:

  • 对于 y = H(x),知道 x 计算其哈希值 y 很简单;
  • 碰撞阻力:很难找出不同的x,y,使得 H(x) = H(y);
  • 隐秘性/谜题友好(近似理解):对于 y = H(x),知道哈希值 y ,很难反求出x。

 

03

哈希函数的意义所在

 

哈希函数与工作量证明

先回忆一下区块结构。比特币的区块由区块头及该区块所包含的交易列表组成,区块头的大小为80字节,由4字节的版本号、32字节的上一个区块的散列值、32字节的 Merkle Root Hash、4字节的时间缀(当前时间)、4字节的当前难度值、4字节的随机数组成。区块包含的交易列表则附加在区块头后面,其中的第一笔交易是 coinbase 交易,这是一笔为了让矿工获得奖励及手续费的特殊交易。

区块的大致结构如图所示:

 

 

其中:

  • Version 是当前区块的版本号
  • 该区块所包含的多个交易的 Hash 值构成区块的 Merkel 数据结构
  • nbits 是当前比特币协议设定的计算复杂度
  • ntime 是区块的时间戳
  • pre_hash 是前一个区块的 Hash 值

Hash(L,x) = SHA256(SHA256(block_header))

block_header = version + Merkel + nbits + ntime + pre_hash

拥有80字节固定长度的区块头,就是用于比特币工作量证明的输入字符串。不停的变更区块头中的随机数即 nonce 的数值,并对每次变更后的的区块头做双重 SHA256运算(即 SHA256(SHA256(Block_Header))),将结果值与当前网络的目标值做对比,如果小于目标值,则解题成功,工作量证明完成。

小结:可以简单理解成,比特币工作量证明的过程,就是通过不停地变换区块头(即尝试不同的随机值)作为输入进行 SHA256哈希运算,找出一个特定格式哈希值的过程,即要求有一定数量的前导0,而要求的前导0的个数越多,代表难度越大。

 

哈希函数与防篡改性

当 x 只变化一个字节,y 是不是也会只变化一个字节,这种微小的差异是否能篡改事实?

不能!

如果输入 x 有1bit 的变化,散列结果即哈希值中将有一半以上的 bit 改变,这又叫做“雪崩效应(avalanche effect)”。

区块链之所以称为链,是因为每一个区块都保存了前一区块的目标 Hash值(创世块没有前一 Hash 值)。某一个区块的某一笔交易发生篡改,因为默克尔树算法的作用这个区块的目标 Hash 值就会被改变,并导致连锁反应。以这个区块为基础,后续所有区块的 Hash 值都会发生变化,任一记账节点都可以轻易的发现账本被篡改,这样就保证了区块链上的所有区块都具备了防篡改功能。

哈希函数的抗碰撞性用来做区块和交易的完整性验证,一有篡改就能被识别出来。

 

最后我们对本文进行归纳总结:

 

1、哈希函数输入任意长度的信息 x ,输出的哈希值 H(x)的 长度都是固定的 256bit;

2、哈希函数具有碰撞阻力、隐秘性、谜题友好三重重要特性,具体来说:

  • 对于 y=H(x),知道 x 计算其哈希值 y 很简单;
  • 碰撞阻力:很难找出不同的 x,y,使得 H(x) = H(y);
  • 隐秘性/谜题友好(近似理解):对于 y = H(x),知道哈希值 y,很难反求出 x;

3、对每次变更后的的区块头做双重 SHA256 运算(即SHA256(SHA256(Block_Header))),结果值小于目标值(有足够多的前导0),工作量证明完成;

4、哈希函数下的防篡改性意味着,输入 x 哪怕 1bit 的变化都将改变一切,所以不可篡改。

关于 冯先生失眠中

冯先生失眠中
卷而怀之

检查

区块链,只是金融发展的延续吗?

区块链诞生于 2008 年的那 …

发表评论

邮箱地址不会被公开。 必填项已用*标注