Comunion 区块链深度学习系列｜哈希结构及特点

Comunion 是一个去中心化的(DAO) 组织协作网络，提供面向数字时代的全新商业基础设施和价值转化机制，致力于让劳动价值 像 资本一样自由流通、交易和积累。

本系列内容包含：基本概念及原理、密码学、共识算法、钱包及节点原理、挖矿原理及实现。

Merkle-Damgård结构

Merkle-Damgård结构是以一位名叫Damgård的科学家命名的，很多哈希函数是基于这个结构构造的哈希函数，比如我们熟悉的SHA-256。

了解这个结构，对我们学习哈希函数是很有用的，因为到后面编程实现希算法的时候，我们会发现通过了解这个结构，在实现哈希算法的过程当中是有章可循的。

通过上图我们来看一下这个结构，第一层一共有6个块，假如要对消息进行哈希，这里分成6个块的意思是，在哈希消息的时候先对消息进行处理，将消息分成相同的块。

上图中每个块里面有3个字符，分到最后刚好合适，假如最后一个块不够均分的话，需要将其补齐。

第二层最左边IHV表示哈希向量，是一个初始值，中间很多C是压缩函数（Compress function），整个结构中的压缩函数都是一样的。压缩函数的特点是，m加t个指数的{0,1}比特串，经过压缩之后会变成一个m指数的{0,1}比特串。

如上图所示，整个开始计算的时候，首先将“Thi”和“IHV”一起放进压缩函数进行计算，经过压缩之后，会给出一个字符串，这个字符串和“the”再传递给第二个压缩函数……以此类推。

直到最后一个消息块压缩完之后，会给出一个哈希值，此时就可以说一个消息通过Merkle-Damgård结构产生了一个哈希值。

整个哈希算法计算速度是非常快的，普通的PC端，一个哈希算法每秒可达到100多万次计算，慢的话也可以达到几十万次。如果使用专门的芯片去计算的话，速度还会成倍地增加。

Merkle-Damgård结构还有一个特点是我们之前讲过的，假如6个块中前5个块的消息一模一样，但是最后一个块改变了一个字符，比如“021”，那么最后出来的哈希结果是和之前的哈希结果完全不一样的。

这个其实也可以用我们之前学过的安全性定义来，就是即使两个原像非常的相似，但是不相同，那么计算出来的两个像也是不相同的，如果相同，就变成了一个碰撞。

keccak结构

keccak结构常用于SHA-3，也是以太坊所用哈希函数采用的结构。

这个结构和前面的Merkle-Damgård结构结构是非常类似的。第一层是P0、P1、Pn-1，和上文一样，是将消息进行分块，这里将消息分成了n块。

最左面有r和c，里面的方框里面有0，意思是开始时上面一层有r个0，下面一层有c个0，初始向量由r加c个比特串构成。

函数向前计算的话会经过一个f，f是一个海绵函数（sponge function），为什么叫海绵函数呢？是因为这个函数的特点和海绵非常相似。

比如上图中间有一个虚线，虚线的左边是一个吸收的过程，虚线的右边是一个压缩的过程。也就是左边是指函数将初始向量和需要哈希的字符串吸收进来，右边用函数进行压缩。

海绵函数的作用是，它会将放进函数的数据进行置换，也可以理解成把所有的数据打乱。

比如上图中，我们先看虚线左边。

第一个数据块P0做完置换之后，会将第二个数据块P1吸收进来；P1吸收之前，会将第一个海绵函数置换后，长度为“r+c”的比特串中，“r”长的比特串，和P1字符串进行易换。

这样一来，P1字符串的长度就变成了“r”长，以此完成压缩的过程。

易换之后，将所有的数据再次进行置换-压缩，这里的置换会有很多层……直到把最后一个数据块吸收进来，然后完成压缩。

置换-压缩完之后，来到虚线右边，右边的Z0、Z1……是最后输出的哈希值，其长度是“r”长。

哈希函数的特点

结合上篇文章，我们可以总结哈希函数总共有4个特点：

特点1，哈希算法能将任意长的输入数据，通过压缩算法压缩成固定长且短的数据。

特点2，速度快。可以通过压缩函数或者海绵函数结构化的对数据进行压缩，最终输出哈希值。

特点3，输入数据之间细微的差距，经过哈希算法后，输出数据有巨大的差异。另外，也是最重要的，一个puzzle需要具备公平、不可预测、难度可调、每次出现的问题都不一样等特点。

特点4，数据的完整性（认证）。

特点3、4是利用了抗碰撞的安全性定义， 因为很难找到碰撞，所以传输的数据能进行一个完整性验证。也可以这样理解，给入一个数据段，如果用SHA-256进行哈希的话，它能产生一个唯一的数据指纹（这里的唯一是有极小的概率性的）。

这4个特点也解释了为什么在区块链中会采用哈希算法，具体思想我们将在下一篇文章中进行详细分析。