区块链中的哈希函数（应用、MD5\SHA\Keccak算法等算法等）

哈希函数

一、概念

哈希函数是一公开函数。用于将任意长的消息M映射为较短的、固定长度的值H（M），又称为散列函数、杂凑函数。我们称函数值H（M）为哈希值、杂凑值、杂凑码、信息摘要。

杂凑值是信息中所有比特的函数，因此提供了一种错误检测能力，即改变信息中任何一个比特或几个比特都会使杂凑值改变。

 

二、性质

实用性要求（本身特性，用于消息认证的基本要求）：

①输入任意性：函数的输入可以是任意大小的数据

（实际上不是任意的，如SHA-1要求不超过2^64）

②输出固定性：函数的输出是一个固定大小的数据；

（如SHA-1的输出是160比特，SHA-256的输出是256比特）

③对任意给定的x，H（x）计算相对容易，无论是软件还是硬件实现。

 

安全性要求：对于区块链技术以及加密数字货币而言，要使得哈希函数达到密码安全：

①collision resistance抗碰撞；对任意x≠y，使H(x)=H(y)是不可能的。

作用：检测信息是否被篡改

注意：哈希碰撞不可避免，因为输入空间大于输出空间。

②hiding单向不可逆；知道H(x)无法推导x。

前提：输入的空间要足够大，使得暴力破解的方法不可行，而且输入的分布要比较均匀，各种取值的可能性都差不多。

③puzzle friendly；哈希值的计算是不可预测的，只根据输入很难预测出输出。

如果需要找出一个哈希值存在某个范围内，只能通过一个一个运算才能找出。

一个好的“Puzzle friendly”算法不会显式输入x和输出H(x)之间的任何可预先确定的相关性。

该性质保证了比特币系统中，只能通过挖矿获得比特币。

 

三、哈希函数的一般结构

四、哈希的实际用途

Hash能把一个大范围映射到一个小范围，能对输入数据或文件进行校验，还可用于查找等。具体的：

①唯一标识或数据检验：

能够对输入数据或文件进行校验，判断是否相同或是否被修改。 如图片识别，可针对图像二进制流进行摘要后MD5，得到的哈希值作为图片唯一标识； 如文件识别，服务器在接受文件上传时，对比两次传送文件的哈希值，若相同则无须再次上传（传统的奇偶校验和CRC校验一定程度上能检测并纠正数据传输中的信道误码，但没有抗数据篡改的能力）。

②安全加密：

最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和SHA（Secure Hash Algorithm，安全散列算法）。对于敏感数据进行MD5或SHA加密传输。哈希算法还可以检验信息的拥有者是否真实。如，用保存密码的哈希值代替保存密码，基本可以杜绝泄密风险。

③数字签名：对Hash值，又称“数字摘要”进行数字签名。

④散列函数：是构造散列表的关键。它直接决定了散列冲突的概率和散列表的性质。

⑤*负载均衡：

负载均衡算法有很多，比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞（session sticky）的负载均衡算法呢？也就是说，需要在同一个客户端上，将一次会话中的所有请求都路由到同一个服务器上。

直接的方法就是，维护一张映射关系表，这张表的内容是客户端IP地址或者会话ID与 服务器编号的映射关系。客户端发出的每次请求，都要先在映射表中查找应该路由到的服务器编号，然后再请求编号对应的服务器。这种方法简单直观，但也有几个弊端：

A.如果客户端很多，映射表可能会很大，比较浪费内存空间；

B.客户端下线、上线，服务器扩容、缩容都会导致映射失效，维护映射表的成本就会很大；

还可以通过哈希算法，对客户端IP地址或者会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。

A.哈希算法可以保证每个客户端的哈希值不同，达到负载均衡效果

B.取模可以把同一个 IP 过来的所有请求，都路由到同一个后端服务器上

⑥*数据分片：

比如图库中有大量图片，可以使用分片思想，准备n台机器，每台机器负责散列表的一部分数据。每次从图库取一个图片，计算唯一标识，然后与机器个数n求余取模，得到的值就是被分配到的机器编号，然后将这个唯一标识和图片路径发往对应机器构建散列表。 当进行图片查找时，使用相同的哈希函数对图片摘要信息取唯一标识并对n求余取模操作后，得到的值k，就是当前图片所存储的机器编号，在该机器的散列表中查找该图片即可。海量数据的处理问题，都可以借助这种数据分片思想，突破单机内存、CPU等资源限制。

⑦*分布式存储：

一致性哈希：对于K个关键字和n个槽位（分布式系统中的节点）的哈希表，增减槽位后，平均只需对K/n个关键字重新映射。

解决缓存等分布式系统的扩容、缩容导致大量数据搬移难题。

 

问题：在分布式缓存的情景下，若其中一台服务器宕机，或者整体要缩容扩容。虽然hash值不变，但取模的服务器数改变了，因此计算出的对应服务器已经错误了。导致所有的数据请求都会穿透缓存，直接去请求数据库。很可能发生雪崩效应，压垮数据库。

 

假设有k个机器，数据的哈希值的范围是[0, MAX]：

==》将整个范围划分成m个小区间（m 远大于k）去直接管理每个客户端

==》每个机器负责 m/k个小区间

==》若集群变动只用迁移少量区间即可

 

服务器定位：确定每个管理哪些区间，原来的分片算法并无此步。注：这里的2^32是因为IPV4，32位的IP断，相当于根据IP断进行分区管理。

客户端定位：定位不依赖于服务器数量，而是看其处于哪个小区间。

区间迁移：若有新机器加入，就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。

1.硬哈希

分布式系统中，假设有n个节点，传统方案使用mod(key, n)映射数据和节点。当扩容或缩容时(哪怕增减1个节点)，映射关系变为 mod(key, n+1) / mod(key, n-1)，绝大多数数据的映射关系都会失效。

2.特性

均衡性(Balance)：将关键字的哈希地址均匀地分布在地址空间中，使地址空间充分利用。

 

单调性(Monotonicity)：当地址空间增大（减少）时，通过哈希函数所得到的关键字的哈希地址也能映射的新的地址空间，而不是仅限于原先的地址空间。简单的哈希函数往往不能满足此性质。

 

分散性(Spread)：哈希经常用在分布式环境中，终端用户通过哈希函数将自己的内容存到不同的缓冲区。此时，终端有可能看不到所有的缓冲，只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中，降低了系统存储的效率。好的哈希算法应能够尽量避免不一致的情况发生，尽量降低分散性。

 

负载(Load)：对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

 

3.映射思想描述

把数据用hash函数（如MD5），映射到一个很大的空间里，如图所示。数据的存储时，先得到一个hash值，对应到这个环中的每个位置，如k1对应到了图中所示的位置，然后沿顺时针找到一个机器节点B，将k1存储到B这个节点中。

如果B节点宕机了，则B上的数据就会落到C节点上：

只会影响C节点，对其他的节点A，D的数据不会造成影响。然而，这又会造成一个“雪崩”的情况，即C节点由于承担了B节点的数据，C节点的负载会变高，很容易也宕机，依次下去，造成整个集群都挂了。

为此，引入了“虚拟节点”的概念：想象在这个环上有很多“虚拟节点”，数据的存储是沿着环的顺时针方向找一个虚拟节点，每个虚拟节点都会关联到一个真实节点：

图中的A1、A2、B1、B2、C1、C2、D1、D2都是虚拟节点，机器A负载存储A1、A2的数据，机器B负载存储B1、B2的数据，机器C负载存储C1、C2的数据。由于这些虚拟节点数量很多，均匀分布，因此不会造成“雪崩”现象。

 

 

密码学Hash函数的应用

1.消息认证：

1.是确保数据正确，2是确保发送方的身份真实

当提供消息认证功能时，Hash值通常称为信息摘要

操作过程：发送者先将信息M进行Hash，然后将【M+Hash】一起发送给B，B再做一次Hash运算将结果与Hash值比较，相同则没有篡改。

注意：此种情况下必须保证Hash的安全传输，因为中间人攻击完全可以改完信息之后再算一个新的Hash值，接收者并不会发现。

 

使用不同方法提供消息认证服务：

①使用对称密码一起加密M和Hash：认证功能+保密性

②使用对称密码只加密Hash：认证功能

③不使用加密算法，使用一个双方都知道的秘密值S和M一起计算Hash值：认证功能

④在③的基础上再将整个消息和Hash一起加密：认证功能+保密性

 

人们不希望使用加密函数的理由：

①加密软件速度慢

②加密硬件成本不容忽视

③硬件的优化通常是针对大数据块

④加密算法可能受专利保护，会增加成本

更一般的，消息认证通过使用消息认证码（MAC）实现，即带密钥的哈希函数。同③不使用加密算法，此时的秘密值就是密钥

 

2.数字签名

过程：

使用发送方的私钥，利用公钥算法对Hash进行加密。

如果希望保密整个信息，则发送方可以先使用私钥对Hash进行加密，再使用对称密码加密消息和公钥算法结果，这是比较常用的做法。

 

五、常用哈希函数及其生命周期

常见Hash算法有：

MD5（MD5 Message-Digest Algorithm，MD5消息摘要算法）

SHA（Secure Hash Algorithm，安全散列算法）

DES（Data Encryption Standard，数据加密标准）

AES（Advanced Encryption Standard，高级加密标准）

目前MD5和SHA1已经被破解，一般推荐至少使用SHA2-256算法。

 

（一）MD5：Message-Digest Algorithm消息摘要算法

MD5输入任意长度的信息，在处理过程中以512位输入数据块为单位，输出为128位的信息（数字指纹）。

 

常用场景：

1、一致性验证，防篡改：如发送一个电子文档，发送前，得到MD5的输出结果a。对方接收后，也得到一个MD5的输出结果b。如果a与b一样就代表中途未被篡改。

2、安全访问认证，增强密码保存的安全性：例如网站将用户密码的MD5值保存，而不是存储用户密码。当用户登录的时候，系统把用户输入的密码进行MD5 Hash运算，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。

3、防抵赖，数字签名：这需要一个第三方认证机构。例如A写了一个文件，认证机构对此文件用MD5算法产生摘要信息并做好记录。若以后A说这文件不是他写的，权威机构只需对此文件重新产生摘要信息，然后跟记录在册的摘要信息进行比对，相同的话，就证明是A写的了。这就是所谓的“数字签名”。

 

算法实现过程：

①消息填充，补长到512的倍数。最后64位为消息长度（填充前的长度）的低64位，在消息后面进行填充，填充第一位为1，其余为0。直到使其字节长度对512求余数的结果等于448，即（n*512) + 448。

为什么余数为448呢，因为剩下的512-448 等于64位，是用于表示填充前的信息长度。信息长度就变为N*512 + 448 + 64 = (N+1)*512，刚好是512的整数倍数。

 

②分割：把输入消息分割为512位的分组，每一块又被划分为16个32位子分组。

 

③计算：每一个分组（512位）进行64次计算后（4轮F\G\H\I，每轮16个子块M0~M15），将A，B，C，D分别加上计算得到的a，b，c，d。当做新的A，B，C，D，并将这4个变量赋值给a，b，c，d再进行下一分组的运算。

由于填充后的消息长度为(N+1)*512，则共需计算N+1个分组。计算所有数据分组后，这4个变量为最后的结果，即MD5值。每次一个输入128位（A\B\C\D），另一个输入512位，结果输出128位，用于下一轮输入。

 

首先需要用到4个常数：

四个32位变量初始化(经过研究所得，为固定值)，称为链接变量（chaining variable）

A = 0×01234567 ；B = 0×89ABCDEF ；C = 0xFEDCBA98 ；D = 0×76543210  

以上为标准的幻数的（物理顺序），在程序中(小端模式)定义是：

A = 0x67452301 ；B = 0xEFCDAB89 ；C = 0x98BADCFE ；D = 0x10325476

 

4个非线性函数：

F(X,Y,Z)=(X & Y) | ((~X) & Z);

G(X,Y,Z)=(X & Z) | (Y & (~Z));

H(X,Y,Z)=X ^ Y ^ Z;

I(X,Y,Z)=Y ^ (X | (~Z));

(&是与, |是或, ~是非, ^是异或)

4种操作：

FF(a,b,c,d,Mi,s,tj)  表示a=b+((a+(F(b,c,d)+Mi+tj)<<< s)

GG(a,b,c,d,Mi,s,tj) 表示 a=b+((a+(G(b,c,d)+Mi+tj)<<< s)

HH(a,b,c,d,Mi,s,tj) 表示 a=b+((a+(H(b,c,d)+Mi+tj)<<< s)

II(a,b,c,d,Mi,s,tj)   表示a=b+((a+(I(b,c,d)+Mi+tj)<<< s)

 

Mi表示消息的第i个子分组（从0到15，共16个）

<<< s表示循环左移s位

常数tj：在第j步中，tj是4294967296*abs(sin(j))的整数部分，i的单位是弧度。

(4294967296是2的32次方)，亦可用 0x100000000UL * abs(sin((double)j)) 计算。

x循环左移s位:( s << x ) | ( s >> (32 - x) )

④输出：输出由4个32位分组组成，级联后将生成一个128位散列值。

 

MD5性质：

①压缩性：任意长度的数据，算出的MD5值长度都是固定的(相当于超损压缩)。

②容易计算

③抗修改性：哪怕只修改1个字节，所得到的MD5值都有很大区别。

④弱抗碰撞：已知原数据和其MD5值，想找到一个具有相同MD5值的数据（即伪造数据）是非常困难的。

⑤强抗碰撞：想找到两个不同的数据，使它们具有相同的MD5值，是非常困难的。

 

MD5不是加密算法：

使用加密算法加密后的消息是完整的，并且基于解密算法后，可以恢复原始数据。

而MD5算法得到的消息是不完整的，并且无法通过摘要的数据也无法得到原始数据。

MD5算法对比加密算法缺少了解密过程，因此，MD5算法不是加密算法。

MD5已经较老，散列长度通常为128位，随着计算机运算能力提高，找到“碰撞”是可能的。因此，在安全要求高的场合不使用MD5。

 

MD2、MD4和MD5：

MD2、MD4和MD5是Rivest开发的信息摘要算法。它们是针对数字签名应用而言的，在一个大的消息被用私钥签名之前，必须以安全的方式‘压缩’。这三种算法都接收任意长度的消息，并生成128位消息摘要。虽然这些算法的结构有些相似，但MD2的设计与MD4和MD5完全不同，MD2是为8位机器做过设计优化的，而MD4和MD5却是面向32位的电脑。

MD2由Rivest于1989年开发。信息首先被填充(数据部位)，使其字节长度是16的倍数。然后在信息末尾追加一个16字节的校验和，并在这个新产生的信息上计算哈希值。Rogier和Chauvaud发现，如果省略校验和的计算，MD2的碰撞可以被构造出来。这是MD2已知的唯一的密码分析结果。

MD4是Rivest于1990年开发的。对信息进行填充，保证信息在加上448后的长度可以被512整除。然后将信息原始长度的64位二进制表示添加到信息中。该消息以512位块进行处理，每个块以三个不同的步骤进行处理。Den Boer和Bosselaers等人非常迅速地开发了对MD4版本的攻击，其中第一轮或最后一轮丢失。Dobbertin 已经在一个典型的PC机上显示了如何在一分钟内就能发现MD4全版本的碰撞。显然，现在MD4被认为是被打破了。

MD5由Rivest于1991年开发。它在md4的基础上增加了"安全-带子"（safety-belts）的概念，虽然比MD4稍慢，但更安全。该算法由4个截然不同的步骤组成，其设计与MD4略有不同。信息摘要大小以及填充要求保持不变。Den Boer和Bosselaers 发现了MD5的伪碰撞，但没有其他已知的密码分析结果。

Van Oorschot 和 Wiener在哈希函数中考虑了对碰撞的粗暴力搜索，他们估计专门为MD5设计的碰撞搜索机(1994年耗资 1000万美元)可以在平均每24天内找到一个MD5的碰撞。一般的技术可以应用于其他哈希函数。

 （二）SHA-1：Secure Hash Algorithm安全哈希算法

主要适用于数字签名标准（Digital Signature Standard DSS）里面定义的数字签名算法（Digital Signature Algorithm DSA）。对于长度小于2^64b的消息，SHA-1将输入流按照每块512b（64B）进行分块，并产生20B或160b的信息摘要。

每个明文分组的摘要生成过程如下：

1、将512位的明文分组划分为16个子明文分组（32位）。

2、申请5个32位的链接变量，记为A、B、C、D、E。

3、16份子明文分组扩展为80份（32位）。

4、80份子明文分组进行4轮运算。

5、链接变量与初始链接变量进行求和运算。

6、链接变量作为下一个明文分组的输入重复进行以上操作。

7、最后，5个链接变量里面的数据就是SHA1摘要。

 

具体算法实现过程：

①补位：（同MD5）消息补位使其长度在对512取模以后的余数是448。先补一个1，然后再补0，直到长度满足对512取模后余数是448。补位是至少补一位，最多补512位。即使长度已经满足对512取模后余数是448，补位也必须要进行。

原始信息：  011000010110001001100011

补位第一步：0110000101100010011000111，首先补一个“1”

补位第二步：01100001011000100110001110…..0，然后补423个“0”

可以把最后补位完成后的数据用16进制写成下面的样子，确保是448b：

61626380000000000000000000000000

00000000000000000000000000000000

00000000000000000000000000000000

0000000000000000

 

②补长度：将原始数据的长度补到已经进行了补位操作的消息后面。通常用一个64位的数据来表示原始消息的长度。如果消息长度不大于2^64，那么第一个字就是0。

在进行了补长度的操作以后，整个消息就变成下面这样了（16进制格式）：

61626380000000000000000000000000

00000000000000000000000000000000

00000000000000000000000000000000

00000000000000000000000000000018（16进制，一个数4位）

如果原始的消息长度超过了512，我们需要将它补成512的倍数。然后我们把整个消息分成一个个512位的数据块。分别处理每一个数据块，从而得到消息摘要。

 

③压缩函数处理：每个消息块都将进行四轮操作，每轮操作又将进行20步运算。

链接变量：函数的初始链接变量值、中间链接变量值和最终的输出值都保存在5个32比特的寄存器A，B，C，D，E中，其中初始链接变量的值为：

A=H0=0x67452301

B=H1=0xEFCDAB89

C=H2=0x98BADCFE

D=H3=0x10325476

E=H4=0xC3D2E1F0

 

常量字K(0),K(1),...,K(79)，如果以16进制给出：

Kt=0x5A827999(0<=t<=19) ；

Kt=0x6ED9EBA1(20<=t<=39) ；

Kt=0x8F1BBCDC(40<=t<=59) ；

Kt=0xCA62C1D6(60<=t<=79)

 

函数：每个函数ft(0<=t<=79)都操作32位的字B，C，D并且产生32位的字作为输出。ft(B,C,D)可以如下定义：

ft(B,C,D)=(B AND C)or( (NOT B)AND D )      (0<=t<=19)

ft(B,C,D)=B XOR C XOR D                  (20<=t<=39)

ft(B,C,D)=(B AND C)or(B AND D)or(C AND D)  (40<=t<=59)

ft(B,C,D)=B XOR C XOR D                  (60<=t<=79)

计算消息摘要：计算需要

A. 两个缓冲区，每个由5个32位的字组成（A，B，C，D，E；H0，H1，H2，H3，H4）；

B. 一个“80个32位”的缓冲区（W0，W1，...，W79）；

C. 一个一个字的TEMP缓冲区。

开始处理Mi。（每个Mi包含80个步骤）

Mi：512b（64B），512位（512比特，64字）

在每一次步函数运算中，A、B、C、D中的值将依次赋值给B、C、D、E寄存器。同时，将A、B、C、D、E的当前的输入值与加法常数和由消息块生成的消息字的值通过步函数运算，将得出的值赋值给寄存器A，其表达式为：

每一个消息块经过运算后，将得到的值赋值给寄存器A、B、C、D、E，当前寄存器中的值与此次运算的输入值进行模加运算，则得到当前的中间链接变量值。当依次计算出最后一个消息块的值时，所得到的值即为最终的消息摘要。

处理完所有Mi后，消息摘要是一个160位的字符串，以下面的顺序标识H0H1H2H3H4。

 

 

（三）SHA-2系列

SHA-2是六个不同算法的合称，包括：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。除了生成摘要的长度、循环运行的次数等一些微小差异外，这些算法的基本结构是一致的。对于任意长度的消息，SHA256都会产生一个256bit长的消息摘要。

 

SHA-256算法

SHA-256算法的输入是最大长度小于2^64位的消息，输出是256位的消息摘要，输入消息以512位的分组为单位进行处理。

 

①消息充填：（同MD5）添加一个“1”或者N个“0”，使其长度模512与448同余。在消息后附加64位的长度块，其值为充填前消息的长度。从而产生长度为512整数倍的消息分组，充填后消息的长度最多为2^64位。

 

②初始化链接变量：链接变量的中间结果和最终结果存储于256位的缓冲区中，缓冲区用8个32位的寄存器可用A-H，h0-h7表示，输出仍然放在缓冲区以代替旧的8个寄存器。

h0 := 0x6a09e667

h1 := 0xbb67ae85

h2 := 0x3c6ef372

h3 := 0xa54ff53a

h4 := 0x510e527f

h5 := 0x9b05688c

h6 := 0x1f83d9ab

h7 := 0x5be0cd19

初始链接变量是取自前8个素数（2、3、5、7、11、13、17、19）的平方根的小数部分其二进制表示的前32位。

 

③初始化Kt（第t个密钥）：Kt是取前64个素数(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59, 61,67,71,73,79,83,89,97…)的立方根的小数部分二进制的前64位。提供了64位随机串集合以消除输入数据里的任何规则性。

④处理主循环模块：消息块是以512位分组为单位进行处理的，需要进行64步循环操作。每一轮的输入均为当前处理的消息分组和上一轮输出的256位缓冲区A-H的值。每一步中均采用了不同的消息字和常数。

 ⑤消息拓展：

对一个消息分组M(t)迭代压缩之前，首先进行消息扩展：

①将16个字的消息分组Mt扩展生成如下的64个字，供压缩函数使用 W0，…，W63；

  ②消息扩展把原消息位打乱，隐蔽原消息位之间的关联，增强了安全性；

SHA256算法中的最小运算单元称为“字”（Word），一个字是32位。

 ⑥压缩：初始化变量A,B,C,E,F,G分别等于前面设置的哈希值 h0, h1, h2, h3, h4,h5, h6, h7。每一步都会生成两个临时的变量，T1、T2：根据T1、T2的值，对寄存器A、E进行更新。ABCEFG的输入值则一次赋值给BCDFGH。

 

 

 ⑦得出最终的Hash值：

在压缩循环之后，在每一个块循环内，通过加上相应的变量a-h来改变哈希值。加法都对2^23取模。

级联最终的哈希值。

 

SHA-256工作全过程：

至今尚未出现对SHA-2有效的攻击，SHA-2和SHA-1并没有接受公众密码社区的详细检验，所以它们的密码安全性还不被广泛信任。

总体上，HAS-256与MD4、MD5以及HSA-1等哈希函数的操作流程类似，在哈希计算之前首先要进行以下两个步骤：

①对消息进行补位处理，最终的长度是512位的倍数；

②以512位为单位对消息进行分块为M1,M2,…,Mn

③处理消息块：从一个初始哈希H0开始，迭代计算：Hi = Hi-1 + CMi(Hi-1)

其中C是SHA256的压缩函数，+是mod 2^32加法，Hn是消息区块的哈希值。

 

 

 

（四）Keccak算法

SHA-3成为NIST的新哈希函数标准算法(FIPS PUB 180--5)。SHA-3的结构仍属于Merkle提出的迭代型哈希函数结构。最大的创新点是采用了一种被称为海绵结构的新的迭代结构。海绵结构又称为海绵函数。

在海绵函数中，输入数据被分为固定长度的数据分组。每个分组逐次作为迭代的输入，同时，上轮迭代的输出也反馈至下轮的迭代中，最终产生输出哈希值。海绵函数允许输入长度和输出长度都可变，具有灵活的性。海绵函数能够用于设计哈希函数（固定输出长度）、伪随机数发生器，以及其他密码函数。

 

以太坊使用的是一种名为Keccak的哈希算法。

可以说Keccak是SHA3正式批准前的名字，但正式批准的SHA3还是和Keccak有许多不一样的地方，我们并不能认为SHA3和Keccak是完全对等的。

在以太坊中，常见的区块哈希、交易哈希、状态哈希等等都使用的Keccak256哈希算法。 256表示创建的信息指纹长度是256位，即32字节。当然以太坊也在慢慢向标准的SHA3算法靠拢，不管你是在开发DAPP还是做其他与要计算哈希值得工作，也建议你使用SHA3，除非你不得不做一些兼容性工作。在 Ether.js中同时提供了Keccak256和SHA256的哈希算法。同样在Solidity中也内置提供了Keccak256和SHA256，同大家灵活使用。

 

Keccak算法描述：

输入数据没有长度限制；

输出哈希值的比特长度分为：224，256，384，512.

Keccak是一种被选定为SHA-3标准的单向散列函数算法。

Keccak可以生成任意长度的散列值，但为了配合SHA-2的散列值长度，SHA-3标准中规定了SHA3-224、SHA3-256、SHA3-384、SHA3-512这4种版本。在输入数据的长度上限方面，SHA-1为2的64次方-1比特，SHA-2为2的128次方-1比特，而SHA-3则没有长度限制。

 

（1）符号与函数 Keccak算法使用以下符号与函数：

①符号

r：比特率 (比特rate)，其值为每个输入块的长度.

c：容量(capacity)，其长度为输出长度的两倍.

b：向量的长度， b = r + c，而 b的值依赖于指数 I，即 b=25 * 2^l

②Keccak算法用到了5个函数： θ(theta)、ρ(rho)、π(pi)、χ(chi)、ι(iota)

（2）算法描述

Keccak算法对数据进行填充，然后迭代压缩生成哈希值。

①填充

使填充后的数据长度为r的整数倍。因为迭代压缩是对r位数据块进行的，如果数据的长度不是r的整数倍，最后一块数据将是短块，这将无法处理。

设消息m长度为l比特。首先将比特“1”添加到m的末尾，再添加k个“0”，k是满足下式的最小非负整数： l +1+ k = r-1 mod r ；然后再添加比特“1”添加到末尾。

 

②整体描述

Keccak算法采用海绵结构(Sponge Construction)，在预处理（padding并分成大小相同的块）后，海绵结构主要分成两部分：

吸入阶段(Absorbing Phase)：将块 xi传入算法并处理。

挤出阶段(Squeezing Phase)：产生一个固定长度的输出。

 

Keccak算法的整体运算结构如下图

 

 ③吸入与挤出阶段

海绵结构：输入的数据进行填充之后，要经过吸收阶段和挤出阶段，最终生成输出的散列值。

①吸收阶段

经过填充的输入消息按照每r比特为一组分割成若干个输入分组；

将“内部状态的r比特”与“输入分组1”进行XOR，将其结果作为“函数f的输入值”；

反复执行上述步骤，直到达到最后一个输入分组。

函数f的作用是将输入的数据进行复杂的搅拌操作并输出结果，内部状态的初始值为0。

内部状态中有c个比特是不受输入分组内容直接影响的（但会通过函数f受到间接影响）。

②挤出阶段

将“函数f的输出值中的r个比特”保存为“输出分组1”，并将整个输出值（r+c个比特）       再次输入到函数f中，

反复执行上面的步骤，直到获得所需长度的输出数据。

两个阶段的函数f的逻辑本身是完全一样的，每执行一次，内部状态都会被搅拌一次。

容量c的意义在于防止将输入消息中的一些特征泄露出去。

 

 

给定输入串x，对x做padding，使其长度能被r整除，将padding后分割成长度为r的块， 即x =x 0|| x1|| x2||...|| xt-1。然后执行以下吸入阶段和挤出阶段：

①初始化一个长度为 r + c 比特的全零向量。

②输入块xi，将xi和向量的前r个比特做异或运算，然后输入到f函数中处理。

③重复上一步，直至处理完x中的每个块。

④输出长为r的块作为y0，并将向量输入到f函数中处理，输出y1，以此类推。得到的哈希序列，即为y = y 0 || y1|| y2 ||...|| yu 。在Keccak-224/256/384/512中，只需要在y0中取出前224/ 256/ 384/ 512位即可。

“||”符号表示比特串串联。

 ④压缩函数

压缩函数f是Keccak算法的核心，它包含n_r轮。

n_r的取值与计算b时用到的指数I ( b=25 * 25^l，向量长度b=r+c)有关，n_r =12+2* I。

Keccak-224/256/384/512中，取I=6， 因此n_r =24。

在每一轮中，要以此执行五步，即 θ(theta)、ρ(rho)、π(pi)、 χ(chi)、ι(iota).

在处理过程中，把b=1600个比特排列成一个5*5* w的三维数组，w=2^I=64比特。

 

 （3）安全性与性能

安全性：可以抵御对哈希函数的所有现有攻击；目前为止，没有发现它有严重的安全弱点。灵活性：可选参数配置，能够适应哈希函数的各种应用。

高效性：设计简单，软硬件实现方便，是高效的。

尚未广泛应用，需要经过实践检验

 

 

（五）SM3算法

SM3是我国商用密码管理局颁布的商用密码哈希函数

用途广泛：

商用密码应用中的辅助数字签名和验证；

消息认证码的生成与验证；

随机数的生成；

SM3在结构上属于基本压缩函数迭代型的哈希函数.

 

SM3算法描述：

输入数据长度为l比特，1≤ l ≤264-1；

输出哈希值的长度为256比特。

 

（1）常量与函数：SHA-256算法使用以下常数与函数：

①常量：

初始值IV=7380166f 4914b2b9 172442d7 da8a0600 a96f30bc 163138aa e38dee4d b0fb0e4e。

 

②函数：

布尔函数：

置换函数：

 ∧表示按位“与”；∨表示按位“或”；¬表示按位“补”；

⊕表示按位“异或”；<<<表示循环左移；

 

（2）算法描述

①填充

设消息m长度为l比特。添加比特“1”，再添加k个“0”，k是满足下式的最小非负整数。l +1+ k = 448 mod 512。然后再添加一个64位比特串，该比特串是长度l的二进制表示。

 ②消息扩展

③迭代压缩处理

将填充后的消息m′按512比特分组： m′= B^(0) B^(1) … B^(n−1)，其中：n = ( l+ k+65)/512。

对m′按下列方式迭代压缩：//外层迭代

FOR i = 0 TO n-1

V ^(i+1)= CF^( V(i) ，B^(i) )

ENDFOR

CF是压缩函数，V ^(0)为256比特初始值IV，B^(i)为填充后的消息分组，迭代压缩的结果为V^(n)，它为消息m的哈希值。

 ④压缩函数

令A, B, C, D, E, F, G, H为字寄存器，SS1, SS2, TT1, TT2为中间变量。

压缩函数： V^( i+1) = CF( V^(i)，B^(i)), 0 ≤i ≤ n -1。压缩函数CF的压缩处理：//内层迭代

FOR j=0 TO 63

CF= F(SS1, SS2, TT1, TT2，A, B, C, D, E, F, G, H，Wj，W′ j ) //基本压缩函数

ENDFOR

⑤基本压缩函数F

⑥SM3工作全过程

⑦压缩函数的作用

1.数据压缩。

SM3的压缩函数CF把每一个512位的消息分组B(i)压缩成256位。经过各数据分组之间的迭代处理后把l位的消息压缩成256位的哈希值。

2.提供安全性。

在SM3的压缩函数CF中，布尔函数FFj (X,Y,Z) 和GGj (X,Y,Z)是非线性函数，经过循环迭代后提供混淆作用。置换函数P0(X)和P1(X)是线性函数，经过循环迭代后提供扩散作用。加上压缩函数CF中的其它运算的共同作用，压缩函数CF具有很高的安全性，从而确保SM3具有很高的安全性

 

（3）安全性

专业机构设计，经过充分测试和论证；

安全性可满足上述应用的安全需求；

学者已开展对SM3的安全分析（如缩减轮的分析），尚未发现本质的缺陷。

 

 

六、哈希函数构造方法

构造哈希函数原则：

（1）函数本身便于计算

（2）计算出来的地址分布均匀，以尽可能减少冲突。

在实际应用中，构造哈希函数要考虑以下五个因素：

（1）计算哈希函数所需要的时间。

（2）关键字的长度。关键字过长，我们可以考虑取关键的某几位来建立哈希函数。

（3）哈希表的大小。哈希表过短，或者过长都会使哈希法性能降低。

（4）关键字分布情况。使key值和哈希函数计算出来的地址分布均匀。

（5）记录查找的频率。

 

1.直接定址法（极少用）

以数据元素关键字k本身或其线性函数作为哈希地址：H（k）=a*k+b；(a，b为常数)。

仅适合于：地址集合的大小==关键字集合的大小，浪费空间太大。

 

2.数字分析法

数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。

只适合于所有关键字值已知的情况（能预先估计出全体关键字的每一位上各种数字出现的频度）。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。

第①②位都是8，1，第③位只可能取3、4，第⑧位只可能取2、5、7，因此这4位都不可取。由于中间的4位可看成是近乎随机的，因此可取其中任意两位，或取其中两位与另外两位的叠加求和后舍去进位作为哈希地址。

 

3.折叠法

折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）。两种叠加处理的方法：

①移位叠加：将分割后的几部分低位对齐相加；

②边界叠加：从一端沿分割界来回折叠，然后对齐相加。

适用于关键字位数较多，而且关键字中每一位上数字分布大致均匀的情况。

例如：采用折叠法构造一个四位数的哈希函数，对关键字1234 5678进行存储：

移位叠加：H(key) = 1234 + 5678 = 6912 ；边界叠加： H(key) = 1234 + 8765 = 9999

 

4.平方取中法（常用）

先取关键字的平方，然后根据可使用空间的大小，选取平方数是中间几位为哈希地址。哈希函数H(key)=“key²的中间几位”。取的位数由表长决定。

原理：通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。

适于：关键字中的每一位都有某些数字重复出现频度很高的现象。

 

5.减去法

减去法是数据的键值减去一个特定的数值以求得数据存储的位置。

 

6.基数转换法

将十进制数X看作其他进制，比如十三进制，再按照十三进制数转换成十进制数，提取其中若干位作为X的哈希值。一般取大于原来基数的数作为转换的基数，并且两个基数应该是互素的。

 

7.除留余数法（常用）

假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为h（k）=k mod p。p取≤m且最接近m的素数时，效果最好，且p最好取1.1n～1.7n之间的一个素数（n为存在的数据元素个数）。

若p选的不好，容易产生同义词。一般情况下可以选择p为质数或者不包含小于20的质因数的合数。

这是最常用的构造哈希函数的方法，不仅可以对关键字直接取模，还可以对折叠、平方区中等运算之后取模。

 

 8.随机数法

设定哈希函数为：H(key)=Random(key)其中，Random为伪随机函数。

适于：对长度不等的关键字构造哈希函数。

 

9．随机乘数法（乘余取整法）

随机乘数法使用一个随机实数f，0≤f<1，乘积f*k的分数部分在0～1之间，用这个分数部分的值与n（哈希表的长度）相乘，乘积的整数部分就是对应的哈希值，显然这个哈希值落在0～n-1之间。其表达公式为：Hash(k)=「n*(f*k%1)」，其中f*k%1表示f*k的小数部分，即f*k%1 = f*k-「f*k」。

优点是对n的选择不很关键。通常若地址空间为p位就是选n=2p。Knuth对常数f的取法做了仔细的研究，他认为f取任何值都可以，但某些值效果更好。如f=（-1）/2=0.6180329...比较理想。

 

10．字符串数值哈希法

把字符串的前10个字符的ASCII值之和对N取摸作为Hash地址，只要N较小，Hash地址将较均匀分布[0，N]区间内。

对于N很大的情形，可使用ELFHash（ExecutableandLinkingFormat，ELF，可执行链接格式）函数，它把一个字符串的绝对长度作为输入，并通过一种方式把字符的十进制值结合起来，对长字符串和短字符串都有效，这种方式产生的位置可能不均匀分布。

 

11.旋转法

旋转法是将数据的键值中进行旋转。旋转法通常并不直接使用在哈希函数上，而是搭配其他哈希函数使用。

 

七、哈希冲突的解决方法

常用的主要有两种方法解决冲突：

1.链接法（拉链法）

将所有关键字为同义词的结点链接在同一个单链表中。

若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组 T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。

T中各分量的初值均应为空指针。

在拉链法中，装填因子α可以大于 1，但一般均取α ≤ 1。

2.开放定址法（再散列法）

当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。

按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。

 

a.线性探查法

hi=(h(key)+ i )％m ，0 ≤ i ≤ m-1

探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到有空余地址或者到T[d-1]为止。

 

b.二次探查法

hi=(h(key)+ i*i ) ％ m，0 ≤ i ≤ m-1

探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1^2]，T[d+2^2]，T[d+3^2]…，直到探查到有空余地址或者到T[d-1]为止。

缺点：无法探查到整个散列空间。

 

c.双重散列法（最好的方法之一）

hi=(h(key)+ i*h1(key) ) ％ m，0 ≤ i ≤ m-1

探查时从地址d开始，首先探查T[d]，然后依次探查T[d+h1(d)]，T[d + 2*h1(d)]，…。

该方法使用了两个散列函数 h(key) 和 h1(key)，故也称为双散列函数探查法。

 

定义 h1(key) 的方法较多，但无论采用什么方法定义，都必须使h1(key)的值和m互素，才能使发生冲突的同义词地址均匀地分布在整个表中，否则可能造成同义词地址的循环计算。

 

3.再哈希法

同时构造多个不同的哈希函数：Hi = RHi(key)
哈希地址H1 = RH1(key)差生冲突时，再计算H2 = RH2(key)…直到冲突不再产生。

 

4.建立公共溢出区

哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素一律填入溢出表。

 

八、哈希结构的缺点：

Hash索引结构的特殊性，检索效率非常高，可以一次定位，不像B-Tree 索引需要从根节点到枝节点，才能访问到叶子节点，所以Hash索引的查询效率要远高于B-Tree索引。

那为什么不用Hash 索引而还要使用B-Tree索引呢？

 

由于Hash索引中存放的是经过Hash计算之后的Hash值，而且Hash值的大小关系并不一定和Hash运算前的键值完全一样，所以

（1）Hash索引仅仅能满足“=”，“IN”和“<=>”查询，不能使用范围查询。

（2）Hash索引无法被用来避免数据的排序操作。

（3）MySQL Hash索引不能利用部分索引键查询。

Hash索引在计算Hash值的时候是组合索引键合并后再一起计算Hash值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash索引也无法被利用。

 

（4）MySQL Hash索引在任何时候都不能避免表扫描。

Hash索引是将索引键通过Hash运算之后，将Hash运算结果的Hash值和所对应的行指针信息存放于一个Hash表中，由于不同索引键存在相同Hash值，所以即使取满足某个Hash键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。

 

（5）MySQL Hash索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。

 

对于选择性比较低的索引键，如果创建Hash索引，那么将会存在大量记录指针信息存于同一个Hash值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。

 

①哈希是以 key-value的形式存储数据的，数据之间没有顺序，无法通过下标访问数据。

②占的空间大，牺牲空间换取了效率

③当哈希表接近装满的状态时，性能下降得非常严重；因为当哈希表空间不足时需要执行扩容操作且扩容操作非常耗时。例如哈希表的长度是100，现在有第101个数要插入，这时，不仅哈希表的长度可能要扩展到150，且扩展之后所有的数都需要重新rehash。因此在设计哈希表时最好能够提前预知数据量的大小。

 

 

九、常见攻击方法：

1.穷举攻击

（a）原像攻击和第二原像攻击（Preimage or Second Preimage attack）

对于给定的哈希值h，试图找到满足H（x）=h的x

对于m位的哈希值，穷举规模大约是2^m

（b）碰撞攻击（Collision Resistance）

找到两个信息x不等于y，满足H(x) = H(y)

对于m位的哈希值，平均预计在2^(m/2)次尝试后就找到两个具有相同哈希值的数据。

（c）因此对于m位的哈希值，抗穷举攻击的强度为2^m/2：

目前128比特已经不够，需要160比特甚至更多

 

2.生日悖论birthday attack：

birthday attack是用来指一类暴力攻击的名称。即23人一组中的两个或两个以上的人共享同一个生日的概率大于1/2。 

如果某种函数，当供给一个随机输入时，返回k 个古典概型值中的一个，那么通过对不同输入的函数反复评估，我们期望在约1.2 k^(1/2)。 获得相同的输出。对于上述生日悖论，用365替换k。

birthday attack常被用来发现哈希函数的碰撞。

 

 关于在提供数字签名时使用哈希函数，Yuval 基于生日悖论提出了以下策略，其中n为消息摘要的长度：

1.攻击者选择Alice很可能要签名的无害目标消息。

2.攻击者生成2^(n/2)个无害消息（做一些小的编辑修改）的变体，所有变体都传达相同的含义和对应的信息摘要。。

3.根据生日悖论，无害消息的变化之一与目标消息的变化之一匹配的概率大于1/2。 

4.攻击者然后在无害消息的变化上获得Alice的签名。

5.从无害消息中取出签名，并附加到产生相同消息摘要的目标消息的变体中。

被攻击者在没有运用加密密钥的情况下成功伪造了消息。

6.为了避免依赖于蛮力方法的攻击，哈希函数的输出必须足够长。

 

3.字典攻击：

如果用户信息被“脱库”，黑客虽然拿到是加密之后的密文，但可通过“猜”破解密码，因为有些用户密码太简单。就需维护一个常用密码的字典表，把字典中的每个密码用哈希算法计算哈希值，然后拿哈希值跟脱库后的密文比对。如果相同，基本上就可以认为，这个加密之后的密码对应的明文就是字典中的这个密码。（哈希算法存在散列冲突，也可能密文一样，但明文不一样）

可引入一个盐（salt），跟用户的密码组合在一起，增加密码的复杂度。拿组合后的字符串做哈希算法加密，存储到数据库，进一步增加破解的难度。

 

4.中间相遇攻击：

攻击者构造一种消息从两端向中间传播的方式。在某些情况下主要的部分是通过猜测而得到的。如果某些消息值在中间不匹配，那么这个猜测的值是错误的并将会被丢弃。

中间相遇攻击比较的是中间链接变量的值。攻击者首先将伪造的消息分成两部分处理。先把前一部分消息按照原来的算法进行计算，从而得到一个中间变量值，然后根据原先函数的哈希值向前计算，直到退回到消息中间分开处理的部分，这样也会产生一个中间变量值。

中间相遇攻击这种分析方法常常用来攻击像IDEA ，AES等分组密码算法。

 

 

 

十、哈希的应用

常用应用：哈希表、分布式缓存

1.哈希表（散列表）

哈希表是实现关联数组（associative array）的一种数据结构，广泛应用于实现数据的快速查找。

用哈希函数计算关键字的哈希值（hash value），通过哈希值这个索引就可以找到关键字的存储位置，即桶（bucket）。哈希表不同于二叉树、栈、序列的数据结构一般情况下，在哈希表上的插入、查找、删除等操作的时间复杂度是 O(1)。

查找过程中，关键字的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。

影响产生冲突多少有以下三个因素：

①哈希函数是否均匀；

②处理冲突的方法；

③哈希表的加载因子。

哈希表的加载因子和容量决定了在什么时候桶数（存储位置）不够，需要重新哈希。

 

加载因子太大的话桶太多，遍历时效率变低；太大的话频繁rehash，导致性能降低。所以加载因子的大小需要结合时间和空间效率考虑。

在 HashMap 中的加载因子为 0.75，即四分之三。

 

2.分布式缓存

网络环境下的分布式缓存系统一般基于一致性哈希（Consistent hashing）。简单的说，一致性哈希将哈希值取值空间组织成一个虚拟的环，各个服务器与数据关键字K使用相同的哈希函数映射到这个环上，数据会存储在它顺时针“游走”遇到的第一个服务器。可以使每个服务器节点的负载相对均衡，很大程度上避免资源的浪费。

在动态分布式缓存系统中，哈希算法的设计是关键点。使用分布更合理的算法可以使得多个服务节点间的负载相对均衡，可以很大程度上避免资源的浪费以及部分服务器过载。 使用带虚拟节点的一致性哈希算法，可以有效地降低服务硬件环境变化带来的数据迁移代价和风险，从而使分布式缓存系统更加高效稳定。

 

十一、BTC中哪些地方用到了哈希函数

1.BTC的数据结构：

哈希指针：存储地址和哈希值。

哈希指针的内容是把整个区块的内容取哈希。

区块链用哈希指针代替了普通的指针。一个哈希指针改变会影响其他哈希指针。

BTC根据这个性质，只保存最近的几个区块哈希。如果需要找之前的区块，可以用哈希指针找到正确的区块。

Merkle tree的好处：只要记住根哈希就可以检测出对树中任何部位的修改。

 

2.挖矿难度的设置

比特币区块链系统采用的哈希算法是SHA256，故搜索空间的大小为2^256。

比特币难度是对挖矿困难程度的度量，即指：计算符合给定目标的一个哈希值的困难程度。difficulty = difficulty_1_target / current_target difficulty_1_target的长度为256比特，前32位为0，后面全部为1，一般显示为哈希值，

0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF difficulty_1_target表示BTC网络最初的目标哈希。current_target是当前块的目标哈希，先经 过压缩然后存储在区块中，区块的哈希值必须小于给定的目标哈希值，表示挖矿成功。

 

3.数字签名

比特币需要利用公钥进行加锁，利用私钥签名进行解锁，从而实现数字货币的交易。解锁过程实际上是利用ECDSA算法的产生数字签名。给定交易信息m，签名过程如下：

①选择一个随机数k；

②计算点R = k*G= (xR, yR )，计算r = xR mod n；

③利用私钥d计算s＝k-1 * (( H( m) - d * r)) mod n；

④输入签名( r, s)

 

十二、ETH中哪些地方用到了哈希函数

1.以太坊的数据结构

block header中的数据结构：

 parentHash：父区块的哈希值，区块链中前一个区块的哈希值（前一个区块块头的哈希值）

uncleHash：叔父区块的哈希值

三棵树的根哈希。Root是状态树的根哈希值，TxHash是交易树的根哈希值（类似比特币系统的根哈希值），ReceipHash是收据树的根哈希值。

2.以太坊用户地址的生成

第一步：生成私钥 (private key)

产生的256比特随机数做为私钥(256比特=16进制32字节)： 18e14a7b 6a307f42 6a94f811 4701e7c8 e774e7f9 a47e2c20 35db29a2 06321725

第二步：生成公钥 (public key)

①将私钥(32字节)和椭圆曲线ECDSA-secp256k1计算公钥(65字节)(前缀04||X公钥||Y公钥)：

04 ||50863ad6 4a87ae8a 2fe83c1a f1a8403c b53f53e4 86d8511d ad8a0488 7e5b2352 || 2cd47024 3453a299 fa9e7723 7716103a bc11a1df 38855ed6 f2ee187e 9c582ba6

 

②利用Keccak-256算法计算公钥的哈希值(32bytes)：

fc12ad81 4631ba68 9f7abe67 1016f75c 54c607f0 82ae6b08 81fac0ab eda21781

③取上一步结果取后20bytes即以太坊地址：

1016f75c54c607f082ae6b0881fac0abeda21781

 

第三步：输地址 (address)：0x1016f75c54c607f082ae6b0881fac0abeda21781

 

3.以太坊的三棵树：状态树、交易树、收据树

在以太坊的block header中，存在有三个根哈希值。

举例：状态树，账户状态组织成一个Merkle Tree。

 

以太坊区块链系统使用了压缩前缀Merkle树(Merkle Patricia Tree,MPT)的结构来存储账户的状态。因为以太坊区块链账户的地址长度是固定的，且长度为160位二进制数，即40位16进制数。如果采用前缀树的方式来存储以太坊区块链的账户，构成的状态树的节点最多只有17个分支（16位十六进制的编码 + 一个结束标志位）。以太坊区块链账户的查找效率只与状态树的高度有关。

当以太坊区块链网络中产生新的交易时，即使不同的矿工打包交易的顺序不同，但是每个交易可按照其地址编码去寻找对应分支的叶子节点，所以当打包交易顺序不同时，形成的前缀树的根节点还是一样的。

压缩前缀Merkle树使树的高度变小，提高了查找账户的时间效率，并且从叶子节点向根节点去验证压缩前缀Merkle树，便可以得到账户的状态以及账户的余额。

 

根哈希值的用处：

1.防止篡改，只要根哈希值不变，整个树的任何部分都没办法被篡改。

2.提供Merkle proof，可以证明账户余额，轻节点可以进行验证。如何证明呢，你账户所在的分支，整个分支自己向上，作为Merkle proof发给轻节点，轻节点就可以验证一下，你账户上有多少钱。

3.证明MPT中某个健值是不存在的，将它所在的分支作为merkle proof 发出去就可以证明它是否存在。

 

4.布隆过滤器(Bloom Filter)

以太坊区块链系统提供了一个布隆过滤器(Bloom Filter)的数据结构，它可以在一个大的集合中计算出一个非常紧凑的摘要信息，通过该摘要信息可以快速定位和验证某一交易信息是否存在。

在该集合中，一开始先对所有元素的初值都赋值为0，当某一交易信息进行消息摘要后映射到该集合中的某一位置时，将该位置的信息赋值为1 ，表示交易存在。

弊端是存在哈希碰撞的可能。该位置的元素为1时，并不能说明某一交易一定存在，还需要进一步去检查交易树的信息，但是该数据结构一定可以确定某一交易不存在，所以通过该性质可以快速过滤一些无关的区块。

因为存在哈希碰撞的可能,在删除时可能把另一个交易的交易信息一起删除，所以为了系统的稳定，该数据结构并不支持删除操作。

在以太坊区块链系统中每个收据都保存了一个布隆过滤器记录用于交易类型、地址等信息。并且会在块头形成一个总的布隆过滤器的并集。

 

5.挖矿算法

在以太坊区块链系统中有两种不同大小的数组，较小的数组大概在16×10^6左右，称之为缓存数组，主要的作用是用于轻节点去验证交易的合法性以及生成矿工挖矿时需要保存的大的数组。

缓存数组的生成方式为：

①计算一个随机种子的哈希值，得到缓存数组的第一个元素；

②通过数组的第一个元素计算哈希值得到该缓存数组的第二个元素；

③以此类推，直到整个数组的元素填充完成；

④数组每隔3000个区块会进行一次更新操作。

工作量证明数组的生成方式为：

①计算一个伪随机数的哈希值，得到对应缓存数组中的元素的位置；

②按照伪随机的顺序，在缓存数组中进行256次查找得到256位的一个数；

③利用该数去计算哈希值，便可以得到工作量证明数组的第一个元素；

④后面的元素按照同样的方式依次生成。

 

 

十三、超级账本Fabric中哪些地方用到了哈希函数

1.私有数据机制

私有数据机制基于策略创建私有数据集合，从而定义同通道中具有权限的组织才可以访问私有数据，而通道内的其余组织只知道发生了这样一笔交易，并不具备查看和操作私有数据的权限，因此并不知道此交易的具体内容。

私有数据集合包括两个部分。

A.私有数据实体：在具有权限的节点之间通过Gossip协议传输数据，并且存储在这些节点的私有状态数据库中，可通过链码API进行访问。

B.私有数据的哈希值：这部分数据用于背书和排序时调用，最后存储到通道内每一个peer节点的账本数据库中，哈希值用于验证私有数据的正确性和完整性。

 

私有数据在通道内的传输流程可分为七步。