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

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

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

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

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

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

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

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

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

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

整個(gè)哈希算法計(jì)算速度是非常快的，普通的PC端，一個(gè)哈希算法每秒可達(dá)到100多萬(wàn)次計(jì)算，慢的話也可以達(dá)到幾十萬(wàn)次。如果使用專(zhuān)門(mén)的芯片去計(jì)算的話，速度還會(huì)成倍地增加。

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

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

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

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

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

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

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

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

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

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

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

這樣一來(lái)，P1字符串的長(zhǎng)度就變成了“r”長(zhǎng)，以此完成壓縮的過(guò)程。

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

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

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

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

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

特點(diǎn)2，速度快。可以通過(guò)壓縮函數(shù)或者海綿函數(shù)結(jié)構(gòu)化的對(duì)數(shù)據(jù)進(jìn)行壓縮，最終輸出哈希值。

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

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

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

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