首页 > 世链号 > 币信小课堂 05 | 什么是哈希函数
韭菜盒子  

币信小课堂 05 | 什么是哈希函数

摘要:趣说行业热点,深研技术应用,解读区块链动向, 服务钱包用户

趣说行业热点,深研技术应用,解读区块链动向, 服务钱包用户

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

全文约 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 的变化都将改变一切,所以不可篡改。

今天就先到这里,江湖路远,下期再见。

- END-

来源链接:mp.weixin.qq.com

免责声明
世链财经作为开放的信息发布平台,所有资讯仅代表作者个人观点,与世链财经无关。如文章、图片、音频或视频出现侵权、违规及其他不当言论,请提供相关材料,发送到:2785592653@qq.com。
风险提示:本站所提供的资讯不代表任何投资暗示。投资有风险,入市须谨慎。
世链粉丝群:提供最新热点新闻,空投糖果、红包等福利,微信:juu3644。