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

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

本篇專門講解哈希碰撞原理，這對于哈希算法的理解是非常重要的。如果把這個理解透了，那么哈希算法里面的很多特點(diǎn)，包括區(qū)塊鏈當(dāng)中為什么使用哈希算法，那么基本上就完全通透了。

定義

摘要函數(shù)（哈希函數(shù)），其實(shí)是一個安全性定義。

抗原像碰撞

什么是原像？函數(shù)有定義域，有詞語，有對應(yīng)關(guān)系。那么類比到這里，原像是指定義域里面的一些未知數(shù)。

引用哈希算法應(yīng)用中挖礦的例子來說，X是定義域，里面的部分就是原像，Y就是一個值域。

我們來看其定義，幾乎所有消息摘要，都難以用ppn算法計(jì)算出一個原像。

這句話的意思是，假如確定了一個對應(yīng)關(guān)系，或者確定了一個哈希函數(shù)，這時(shí)對定義域里面某一個元素，比如X1，進(jìn)行哈希之后，產(chǎn)生了一個哈希值，比如Y1。

假設(shè)這個時(shí)候產(chǎn)生了Y1，但是并沒有告訴任何人。那么這里就有一個問題：這個Y1的原像是誰呢？

這是很難找出來的，也就是提供一個像：Y1，很難找出其對應(yīng)的原像：X1，這也就是抗原像碰撞的意思。

抗第二原像碰撞

通過字面意思來解釋是，存在兩個原像，這兩個原像是很難找到碰撞的。

給定一個摘要函數(shù)h，消息m1，任何ppn算法都難以計(jì)算出一個m2使得m1≠m2并且h（m1）=h（m2）。

意思是，給定一個哈希函數(shù)，通過任何ppn算法，很難找出一個m2，但這個m2和m1不相同，然后使得原像m2和m1，里面的像也相同，這是很難做到的。

抗碰撞

給定一個摘要函數(shù)，任意ppn算法，難以找到m1，m2，使得h（m1）=h（m2）。

意思是，給定一個哈希函數(shù)，使用任意ppn算法，難以找到兩個消息（原像），使得它們的像相同。

強(qiáng)抗碰撞的意思是，給定一個哈希函數(shù)，從定義域（原像）里面隨便找兩個數(shù)，并且這兩個數(shù)的像是相同的，這樣的數(shù)是很難找到的。

抗第二原像碰撞和抗碰撞之間的區(qū)別是：

抗第二原像碰撞是抗碰撞里面的一個特殊問題。抗碰撞的條件更加強(qiáng)一些，因?yàn)槭侨我馊〉膬蓚€原像，想得到的像是相同的。而抗第二原像碰撞是給定了一個固定的原像，讓再找一個原像，使得這兩個原像里面的像相同。所以說抗第二原像碰撞是弱抗碰撞。

在區(qū)塊鏈中，如果一個哈希函數(shù)滿足上述三個安全性定義，即：抗原相碰撞、抗第二原像碰撞、抗碰撞，那么這個函數(shù)就可以使用，比如SHA-256就滿足這三點(diǎn)。

應(yīng)用

通過安全性定義，其實(shí)我們能發(fā)現(xiàn)一個特點(diǎn)：這種函數(shù)能進(jìn)行一個數(shù)據(jù)的完整性認(rèn)證。

為什么這么說呢？

舉個例子，特工A發(fā)了一段消息，內(nèi)容是：使用任意函數(shù)H。并用SHA-256對這段話進(jìn)行哈希，假設(shè)其哈希值全部是0，那么就產(chǎn)生了256個0。

特工A把這段消息發(fā)給特工B，特工B收到之后，也對其內(nèi)容“使用任意函數(shù)H”進(jìn)行哈希，假如產(chǎn)生的值是256個0的話，那么就說明這個消息在傳播的過程當(dāng)中沒有被篡改。

發(fā)送方將完整的傳輸傳輸給了接收方，完成了發(fā)送方的目的，同時(shí)接受方也可以對數(shù)據(jù)的完整性進(jìn)行驗(yàn)證。

這里有的朋友就有疑問了，那么對于消息：使用任意函數(shù)X，經(jīng)過哈希之后，會不會也產(chǎn)生256個0呢？

我可以負(fù)責(zé)的告訴你，如果對消息進(jìn)行哈希使用的函數(shù)，滿足上述三個安全性定義的話，那么是不會產(chǎn)生這種情況的。所以，在進(jìn)行區(qū)塊鏈開發(fā)選用函數(shù)的時(shí)候，可以不必須用SHA-256，但是一定要滿足這三個安全條件。

其實(shí)講到這里，有很多朋友會產(chǎn)生一個問題：假如我采用的是SHA-256算法，其原像是任意的字符串，像是固定的，那么這個像的空間有多大呢？

答案是：2的256次方的像，也就是總共可以容納這么多像。

安全級別

還有一個問題是：一個任意多的原像和一個固定空間大的像，那么肯定會通過一定的概率找到兩個原像一樣的像，也就是產(chǎn)生了碰撞，那么這個碰撞的概率是多大呢？

這個問題很好理解，像是固定的，但是原線有很多，在一個固定的空間內(nèi)肯定會有碰撞的概率，就比如之前講過的粒子對撞機(jī)一樣的原理。

很多朋友都會對這個問題困擾很久。

其實(shí)在密碼學(xué)里面專門有個悖論來解釋這個問題，我們一起來用“生日悖論”來解釋一下這個問題。

生日悖論

上述的成功概率與下述的問題相關(guān)。

問題：要使得教室里的學(xué)生中有兩個人的生日相同的概率大于0.5（也就是50%），那么教室里至少需要有多少學(xué)生？

從直觀上來看，可能至少需要2/365≈183個人才行。但是大家仔細(xì)分析一下，回顧一下之前學(xué)過的概率論的一些知識，會發(fā)現(xiàn)這個問題其實(shí)并不容易回答。

我們另外一個角度，從反面來解決這個問題，可能會更好一點(diǎn)。

這個問題的反面事件可以理解為：教室里的學(xué)生，任意兩個人的生日，不相同的概率大于50%。

如果我們能把反面事件的概率求出來，那么用1減去求得概率就是原題目的答案。

所以這個問題我們轉(zhuǎn)換成：求這個教室里面任意兩個人的生日，不相同的概率大于50%的人數(shù)。

那么到底有多少個人不相同，概率才大于50%呢？

我們做兩個假設(shè)：

假設(shè)1，每個學(xué)生的生日在某個特定一天的概率是1/365；

假設(shè)2，n個學(xué)生的生日都互不相同的概率大于50%。

這里就轉(zhuǎn)換成了求n是什么。

我們首先來來分析一下，n 個人里面，2個人生日不相同的概率是多大？也就是從教室里面任意選出2個人，那他們生日不相同的概率是多少？

答案是：364/365。

也就是把兩個人標(biāo)記為A和B，A的生日是365天中的某一天，那么B的生日和A不同，就有364種可能。

我們繼續(xù)，如果3個人不相同的概率是多大呢？那么就是：364/365 * 363/365 。

……

那么n個人不相同的概率應(yīng)該是：363/365 * 364/365 * ……*（365-n+1）/365

這個時(shí)候呢，n個人生日不相同的概率，我們已經(jīng)求出來了。如果要求這個概率大于50%，則可以寫成：pro[363/365 * 364/365 * ……*（365-n+1）/365] >

0.5，這就是反面事件的解。

那正面事件就可以寫成：1-{ pro[363/365

* 364/365 * ……*（365-n+1）/365] > 0.5} > 0.5

算式列出來之后，對n求解，得出n≥23，也就是說，只要不少于23個人，就至少有兩人生日相同的概率大于50%。

這看起來很不可思議，但通過計(jì)算卻是：一個 30 人的班級中，存在兩人生日相同的概率為 70%；對于 60 人的班級中，這種概率要大于 99%。

從引起邏輯矛盾的角度來說，生日悖論并不是一種“悖論”。但這個數(shù)學(xué)事實(shí)十分反直覺，故稱之為一個悖論。

通過這個問題，我們回來看哈希函數(shù)的碰撞問題：假如使用的哈希函數(shù)是SHA-256，那么它的安全級別是多少呢？

或者說，假如使用的哈希函數(shù)是SHA-256，任意找兩個原像，要使這兩個原像產(chǎn)生碰撞的概率大于50%，需要做多少次計(jì)算呢？

通過生日悖論，我們可以理解到，SHA-256的安全級別不是2^256（2的256次方），而是：2^（256/2），也就是2的256/2次方。

引申一下，其實(shí)在密碼學(xué)里面，對哈希函數(shù)有一個專門的安全性界定，它是跟哈希函數(shù)的尾綴有關(guān)系的，所以假如使用的是SHA-n，那么其安全級別就是：2^（n/2）。