区块链技术中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经过计算出现在同一个位置，就会发生冲突。 这里有一些冲突需要处理。 有兴趣的可以查看哈希算法论文。

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<=m-1)，其中m是哈希表的长度。 di 是发生冲突时的增量序列。 如果di值可能是1,2,3,。 ..m-1比特币中使用的哈希算法是什么，称为线性检测和散列。 如果di为1，则每次冲突后，向后移动1个位置。 如果di的值可能是1,-1,4,-4,9,-9,16,-16,。 ..k*k, -k*k (k<=m/2)，称为二次检测和哈希。 如果di的值可能是一个伪随机序列。 它被称为伪随机检测和重新散列。

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

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

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

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

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

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

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

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