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結構產生了一個哈希值。

整個哈希算法計算速度是非?？斓模胀ǖ腜C端，一個哈希算法每秒可達到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個特點也解釋了為什么在區塊鏈中會采用哈希算法，具體思想我們將在下一篇文章中進行詳細分析。