欧奇云链研究院｜今日学习：哈希算法补充内容

对于hash比特币算法原理，可能理解的还不够透彻，下面补充一些内容

解释一：

URL A转换成数字1 URL B转换成数字2 一个网站X转换成数字N，根据数字N为下标，可以快速查到网站X的信息。 这个转换过程就是散列算法。 哈希算法不是具体的算法，只要能完成这种转换的算法就是哈希算法。 但是，评价一个算法是否是一个好的哈希算法，应该根据算法的分散程度和碰撞概率来评价。

解释二：

什么是哈希表和哈希算法？ 比如这里有10000首歌曲，给你一首新歌X，让你确认这首歌是否在10000首歌曲中。 毫无疑问，将10,000首歌曲一首一首地比较是非常缓慢的。 但是如果有办法把这10000首歌曲的每首数据都压缩成一个数字（称为哈希码），然后得到10000个数字，然后用同样的算法计算出新歌曲X的编码，看看是不是歌曲X的代码在前一万首号码中，可以知道歌曲X是否在前一万首歌曲中。 举个例子，如果要整理那10000首歌曲，一个简单的哈希算法就是用歌曲在硬盘上占用的字节数作为哈希码。 这样就可以把10000首歌曲“按大小排序”，然后遇到一首新歌，只要看新歌的字节数是否与现有10000首歌曲中的一首一样。 如果字节数相同，则可知新歌是否在10000首歌曲之内。 当然，这种简单的哈希算法容易出现两首大小相同的歌曲，这就是发送碰撞。 好的哈希算法发生冲突的可能性很小。

解释三：

这个HASH算法不是大学里数据结构课的HASH表的算法。 这里的HASH算法是密码学的基础。 比较常用的是MD5和SHA。 两个最重要的属性是不可逆性和非冲突性。 所谓不可逆性，就是当你知道x的HASH值时，你找不到x； 所谓不冲突，就是知道x的时候，找不到ay，这样x和y的HASH值 是一样的。 这两个属性在数学上都是无效的。 因为一个函数必须是可逆的，又因为HASH函数的取值范围是有限的，理论上会有无穷多个不同的原值，它们的哈希值都是一样的。 MD5 和 SHA 实现的是计算上不可能找到反转和冲突，即正向计算容易，但即使耗尽所有人力计算资源也无法进行反向计算。 我认为密码学的几种算法（HASH、对称加密、公私钥）是计算机科学领域最伟大的发明之一，它在权力面前赋予弱者信息安全（和绝对安全）。 例如，只要你一直使用https与国外网站通信，注意对方的公钥没有被篡改，G**W就可以断开你的连接，但它永远不知道你的是什么传输内容是。

解释四：

区块链解读，区块链中的HASH算法

区块链技术是一系列技术的组合，建立起一种新的技术架构，其中哈希算法是其中尤为重要的一个。 这里简单介绍一下哈希算法。 如有误会，请及时指正。

在讲哈希算法之前，我们先来澄清一个计算机基础知识。 计算机在底层机器代码中使用二进制模式。 所谓二进制简单的说就是底层用0/1标记，所有的数据传输记录都以010101的方式存储。这两种状态也可以看作是日常生活中的一个开关，1代表开，0代表开意味着关闭。 那么计算机中的最小数据单位就是这里说的0或者1。 这里我们称之为位（bit或bit），8位组成一个字节。 当然，计算机中也有八进制和十六进制的表示方式，这里暂不讨论。 仅阐明了基本的二进制概念。

Hash算法将一个任意长度的二进制值映射为一个较短的固定长度的二进制值，这个小的二进制值称为哈希值。 哈希值是一段数据的唯一且极其紧凑的数字表示。 如果您对一段明文进行哈希处理，甚至更改其中的一个字母，则后续哈希将产生不同的值。 在计算上不可能找到散列为相同值的两个不同输入，因此数据的散列可用于检查数据的完整性。 一般用于快速查找和加密算法。

然后引入哈希表的概念。 在计算机数据结构中，给定一个表M和一个关键字key，有一个函数H(key)。 对于任意给定的关键字值key，如果可以得到包含该关键字的函数 表中记录的地址，则表M称为哈希表。

哈希算法简单理解就是这种单向加密。 明文加密称为密文，密文是不可逆的。 只有加密过程，没有解密过程。 解释一下哈希函数和哈希表的概念，那么常用的哈希算法有MD5（已破解），SHA系列算法（比特币使用sha-256算法）。 这里稍微提一下SHA（secure hash algorithm）。 这不是算法，而是一组哈希函数。 现在有sha-224、sha-256、sha-384、sha-512等算法。 2009年中本聪设计比特币的时候，sha-256被认为是当时最安全的算法之一，所以选择了sha-256，至今没有被破解。

（解释到这里，大家可能会觉得，如果hash算法中的key经过计算出现在同一个位置，就会发生冲突，这里介绍几个冲突处理，有兴趣的可以去看看hash算法论文。

1、拉链法：这种方法可以完全避免冲突，将所有关键字为同义词的节点链接在同一个单链表中。 如果选择的哈希表的长度为m，则可以将哈希表定义为由m个头指针组成的指针数组t[0..m-1]。 将哈希地址为i的所有节点插入到以t为头指针的单向链表中。 t中每个组件的初始值应该是一个空指针。 在拉链法中，填充因子α可以大于1，但一般α≤1。

2. 多哈希法：设计两个或多个哈希函数来避免冲突。 这样感觉不太靠谱，但是从概率上来说，多个hash函数还是可以减少冲突的发生的。

3. 开地址法： 开地址法有一个公式： Hi=(H(key)+di) MOD mi=1,2,...,k(k

哈希算法函数按分类分为：加法哈希、位运算哈希、乘法哈希、除法哈希、查表哈希等。

参考百度百科说的比较抽象，有兴趣的可以多了解下。

结合区块链，哈希函数在区块链的很多地方都有用到：

1. 区块链节点地址、公钥、私钥的计算。 以地址为例：公钥经过SHA256计算，再进行RIPEMD160计算得到公钥哈希（20字节\160位），加上版本信息，经过两次SHA256运算得到前4字节. 放入hash公钥加上版本信息，再用base58编码比特币算法原理，最后得到地址。

2.默克尔树：是数据结构中的树型结构。 它可以是二叉树或多叉树。 它与数据结构中的树几乎具有相同的特性。 与普通树的区别在于：默克尔树上的叶子节点存储的是哈希计算后的哈希值，而非叶子节点是字符串与其对应的子节点拼接后的哈希值。 用于块头和 SPV 身份验证。

3、比特币挖矿，工作量证明（POW），其实是计算一个随机数。 当这个随机数与其他散列数据结合时，会生成一个小于指定目标（target）的值。 挖矿也可以理解为快速不可逆的计算。 SHA256(SHA256(版本 + prev_hash + merkle_root + ntime + nbits + x ))

4. Bloom filter 比特币中的布隆过滤器，布隆过滤器是基于哈希函数的快速查找。 它解决了客户端检索的问题。 其原理是Bloom filter可以快速判断某个检索值一定不存在于指定的集合中，从而过滤掉大量不相关的数据，减少客户端不必要的下载。

简单介绍一下HASH算法以及区块链中使用的HASH算法。 区块链是多种技术的结合，结合各自的特点出现了一种新的技术架构。 HASH算法和加密技术是区块链的天然特征。 算法的碰撞和现在量子计算的发展，笔者之前在区块链安全的文章中已经说明，技术在不断发展，肯定会有更合适的技术保障应用。 完成。