基于区块链中的HASH算法解析

区块链技术是一系列技术的结合，建立一种新的技术架构，hash算法是其中尤为重要的一块，这里简单对hash算法做一个说明。如果有理解不当的地方请及时指正。

讲hash算法之前先明确一个基础的计算机知识，计算机在底层机器码是采用二进制的模式，所谓二进制简单来说就是底层以0/1来标识，所有数据传输记录都以010101的模式来存储记录，两种状态也可认为就是一个日常生活中的开关，1标识开，0标识关。那么计算机中最小的数据单位也就是这里说的0或者1，这里我们称为bit（比特或者位），8个bit组成一个字节。当然计算机中也有八进制、十六进制的表示，这里暂时不展开讨论。只明确底层一个二进制的概念。

Hash算法将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。一般用于快速查找和加密算法。

再引入一个hash表概念，计算机数据结构中，给定一个表M，关键字key，存在函数H（key），对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为hash表。

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

解释到这里，可能会联想到，hash算法中key在计算后如果出现了同一位置，冲突的产生，这里简单说下几种冲突处理，如有兴趣可以查看hash算法论文。

1.拉链法：这种方法可以完全避免冲突，将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组t［0..m-1］。凡是散列地址为i的结点，均插入到以t为头指针的单链表中。t中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于1，但一般均取α≤1。

2.多哈希法：设计两种以上的hash函数，避免冲突，这个感觉比较不靠谱，但是从概率上来说多种hash函数还是降低了冲突的出现。

3.开放地址法：开放地址法有一个公式：Hi=（H（key）+di） MOD m i=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取值可能为伪随机数列。称伪随机探测再散列。

Hash算法函数根据分类：加法hash、位运算hash、乘法hash、除法hash、查表hash等。

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

结合区块链，在区块链中很多地方都用到了hash函数：

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

2.merkle tree：是数据结构中的一种树结构，可以是二叉树，也可以是多叉树，他和数据结构中树的特点几乎一致，和普通树不同的是：merkle tree上的叶节点存放hash计算后的hash值，非叶节点是其对应的子节点串联的字符串的hash值。用于区块头和SPV认证中。

3.比特币中的挖矿，工作量证明（pow），计算的其实就是一个nonce，当这个随机数和其他散列过的数据合并时，产生一个比规定目标小（target）值。挖矿也可以理解一种快速不可逆的计算。SHA256（SHA256（version + prev_hash + merkle_root + ntime + nbits + x ）） 《 TARGET。

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

简单介绍了HASH算法，和区块链中用到的HASH算法，区块链是多个技术的结合，结合各自特点出现的一种新的技术架构，HASH算法和加密技术为区块链的自证信任化及安全控制提供了基础，算法的碰撞和现在量子计算的发展，之前在区块链的安全性的文章中笔者有过说明，技术不断发展，肯定会有更适合的技术保障应用的实现。