Comunion 是一個去中心化的(DAO) 組織協(xié)作網(wǎng)絡(luò)，提供面向數(shù)字時代的全新商業(yè)基礎(chǔ)設(shè)施和價值轉(zhuǎn)化機(jī)制，致力于讓勞動價值 像 資本一樣自由流通、交易和積累。

本系列內(nèi)容包含：基本概念及原理、密碼學(xué)、共識算法、錢包及節(jié)點(diǎn)原理、挖礦原理及實(shí)現(xiàn)。

Merkle-Damg?rd結(jié)構(gòu)

Merkle-Damg?rd結(jié)構(gòu)是以一位名叫Damg?rd的科學(xué)家命名的，很多哈希函數(shù)是基于這個結(jié)構(gòu)構(gòu)造的哈希函數(shù)，比如我們熟悉的SHA-256。

了解這個結(jié)構(gòu)，對我們學(xué)習(xí)哈希函數(shù)是很有用的，因?yàn)榈胶竺婢幊虒?shí)現(xiàn)希算法的時候，我們會發(fā)現(xiàn)通過了解這個結(jié)構(gòu)，在實(shí)現(xiàn)哈希算法的過程當(dāng)中是有章可循的。

通過上圖我們來看一下這個結(jié)構(gòu)，第一層一共有6個塊，假如要對消息進(jìn)行哈希，這里分成6個塊的意思是，在哈希消息的時候先對消息進(jìn)行處理，將消息分成相同的塊。

上圖中每個塊里面有3個字符，分到最后剛好合適，假如最后一個塊不夠均分的話，需要將其補(bǔ)齊。

第二層最左邊IHV表示哈希向量，是一個初始值，中間很多C是壓縮函數(shù)（Compress function），整個結(jié)構(gòu)中的壓縮函數(shù)都是一樣的。壓縮函數(shù)的特點(diǎn)是，m加t個指數(shù)的{0,1}比特串，經(jīng)過壓縮之后會變成一個m指數(shù)的{0,1}比特串。

如上圖所示，整個開始計(jì)算的時候，首先將“Thi”和“IHV”一起放進(jìn)壓縮函數(shù)進(jìn)行計(jì)算，經(jīng)過壓縮之后，會給出一個字符串，這個字符串和“the”再傳遞給第二個壓縮函數(shù)……以此類推。

直到最后一個消息塊壓縮完之后，會給出一個哈希值，此時就可以說一個消息通過Merkle-Damg?rd結(jié)構(gòu)產(chǎn)生了一個哈希值。

整個哈希算法計(jì)算速度是非?？斓模胀ǖ腜C端，一個哈希算法每秒可達(dá)到100多萬次計(jì)算，慢的話也可以達(dá)到幾十萬次。如果使用專門的芯片去計(jì)算的話，速度還會成倍地增加。

Merkle-Damg?rd結(jié)構(gòu)還有一個特點(diǎn)是我們之前講過的，假如6個塊中前5個塊的消息一模一樣，但是最后一個塊改變了一個字符，比如“021”，那么最后出來的哈希結(jié)果是和之前的哈希結(jié)果完全不一樣的。

這個其實(shí)也可以用我們之前學(xué)過的安全性定義來，就是即使兩個原像非常的相似，但是不相同，那么計(jì)算出來的兩個像也是不相同的，如果相同，就變成了一個碰撞。

keccak結(jié)構(gòu)

keccak結(jié)構(gòu)常用于SHA-3，也是以太坊所用哈希函數(shù)采用的結(jié)構(gòu)。

這個結(jié)構(gòu)和前面的Merkle-Damg?rd結(jié)構(gòu)結(jié)構(gòu)是非常類似的。第一層是P0、P1、Pn-1，和上文一樣，是將消息進(jìn)行分塊，這里將消息分成了n塊。

最左面有r和c，里面的方框里面有0，意思是開始時上面一層有r個0，下面一層有c個0，初始向量由r加c個比特串構(gòu)成。

函數(shù)向前計(jì)算的話會經(jīng)過一個f，f是一個海綿函數(shù)（sponge function），為什么叫海綿函數(shù)呢？是因?yàn)檫@個函數(shù)的特點(diǎn)和海綿非常相似。

比如上圖中間有一個虛線，虛線的左邊是一個吸收的過程，虛線的右邊是一個壓縮的過程。也就是左邊是指函數(shù)將初始向量和需要哈希的字符串吸收進(jìn)來，右邊用函數(shù)進(jìn)行壓縮。

海綿函數(shù)的作用是，它會將放進(jìn)函數(shù)的數(shù)據(jù)進(jìn)行置換，也可以理解成把所有的數(shù)據(jù)打亂。

比如上圖中，我們先看虛線左邊。

第一個數(shù)據(jù)塊P0做完置換之后，會將第二個數(shù)據(jù)塊P1吸收進(jìn)來；P1吸收之前，會將第一個海綿函數(shù)置換后，長度為“r+c”的比特串中，“r”長的比特串，和P1字符串進(jìn)行易換。

這樣一來，P1字符串的長度就變成了“r”長，以此完成壓縮的過程。

易換之后，將所有的數(shù)據(jù)再次進(jìn)行置換-壓縮，這里的置換會有很多層……直到把最后一個數(shù)據(jù)塊吸收進(jìn)來，然后完成壓縮。

置換-壓縮完之后，來到虛線右邊，右邊的Z0、Z1……是最后輸出的哈希值，其長度是“r”長。

哈希函數(shù)的特點(diǎn)

結(jié)合上篇文章，我們可以總結(jié)哈希函數(shù)總共有4個特點(diǎn)：

特點(diǎn)1，哈希算法能將任意長的輸入數(shù)據(jù)，通過壓縮算法壓縮成固定長且短的數(shù)據(jù)。

特點(diǎn)2，速度快?？梢酝ㄟ^壓縮函數(shù)或者海綿函數(shù)結(jié)構(gòu)化的對數(shù)據(jù)進(jìn)行壓縮，最終輸出哈希值。

特點(diǎn)3，輸入數(shù)據(jù)之間細(xì)微的差距，經(jīng)過哈希算法后，輸出數(shù)據(jù)有巨大的差異。另外，也是最重要的，一個puzzle需要具備公平、不可預(yù)測、難度可調(diào)、每次出現(xiàn)的問題都不一樣等特點(diǎn)。

特點(diǎn)4，數(shù)據(jù)的完整性（認(rèn)證）。

特點(diǎn)3、4是利用了抗碰撞的安全性定義， 因?yàn)楹茈y找到碰撞，所以傳輸?shù)臄?shù)據(jù)能進(jìn)行一個完整性驗(yàn)證。也可以這樣理解，給入一個數(shù)據(jù)段，如果用SHA-256進(jìn)行哈希的話，它能產(chǎn)生一個唯一的數(shù)據(jù)指紋（這里的唯一是有極小的概率性的）。

這4個特點(diǎn)也解釋了為什么在區(qū)塊鏈中會采用哈希算法，具體思想我們將在下一篇文章中進(jìn)行詳細(xì)分析。