作者：Steven Li（胡飛瞳）
來源：IPFS原力區
散列（hash）函數是區塊鏈所利用的技術中的最為基礎的部分了，也是非常重要的部分之一。一個好的散列函數在一個密碼體系中的地位也十分重要。Filecoin作為新一代的區塊鏈，在散列函數的採用上也十分大膽。其中Posaidon就是比較新的散列算法。
散列的基本概念
IT人士對於散列（Hash）再熟悉不過了。Hash表是一種基本的數據結構，而這種數據結構是依靠hash函數來進行索引和訪問的。由於Hash函數在尋址上具有很高的效率上的優勢，算法複雜度基本上是O(1)。因此，Hash函數被廣泛應用與資料庫和其他數據處理系統中。
簡單來說，散列函數就是把任意長度的輸入，通過散列算法，變換成固定長度的輸出，該輸出就是散列值。通常輸入的數據長度要大於運算得出的散列值，同時因為這個散列值一定程度上可以代表原數據，因此也被成為摘要。工程師比較熟悉的 md5 就是使用最為廣泛的 hash 函數，一般用來驗證數據的完整性。
因為散列值是一個固定長度，比如說md5sum的輸出是128位，也就是16位元組，那麼這個散列值的所有可能性就是 2^128。這個範圍和IPv6的地址範圍差不多。
一個 hash 函數可以由以下特性來進行評估：
- 均勻度（Uniformity）：前面提到了一個散列值的空間，那麼一個hash函數對於一個輸入的運算結果落到這個散列值空間中的機率最好是均等的。這樣可以降低碰撞率（不同的輸入得出相同結果的比率）
- 效率（Efficiency）：hash函數本身的計算複雜度也是一個考量因素。在很多場合，要求快速響應，因此最好計算簡單。但是太簡單的hash函數在均勻性上可能不理想，因此這裡需要考慮一些權衡
- 確定性（Deterministic）：對於固定的輸入，輸出固定。這也是一般函數的特徵
用於密碼學的散列函數
對於區塊鏈從業者而言，很多時候使用hash函數的場合併不是用於索引或檢索數據（儘管這種情況也很普遍），通常可以看見的是用來進行單向計算和驗證。比如說在比特幣中採用 SHA256 來進行選舉運算獲得出塊權，以及採用SHA256 和 RIPEMD-160 來從私鑰計算公鑰和地址。除了hash函數的一般性特性只要，用於密碼學的 hash 函數有更嚴格的要求：
- 單向性：從數據求散列值很容易，但不能倒推。或者倒推十分困難，理論上不可行
- 無相關性：要求在輸入有一點點改變的情況下，要產生完全不同的輸出。這樣，從散列值完全不能看出數據之間的相關性
- 唯一性：不能通過不同的數據產生相同的hash值。這裡說的不能是基本上不能人為實現，也就是說機率極小；此特性也可以成為碰撞安全性。
前面提到的 md5 散列函數，在區塊鏈系統中完全沒有被採用，其主要原因就是在碰撞安全性不能滿足要求，密碼學界在2007年就發現了其碰撞破解的辦法，而最新的發現其雙塊攻擊在普通計算機上就可以很快實現。而廣泛使用的SHA256函數的碰撞安全性是 md5 的 2^64 倍，
IPFS 中使用的散列函數
IPFS 與傳統存儲系統的一個重要區別在於採用內容尋址。所謂內容尋址就是對內容做hash運算，把散列值作為內容的索引。由於hash函數的確定性和唯一性，可以用散列值來代表數據。IPFS的CID（內容標識，也就是散列之）在數據格式的定義上採用MultiHash，也就是說，是一個可擴展的數據格式和方案。用戶可以根據需要隨時支持新的協議。其格式大致如下：
大家常見的以 Qm 打頭的CID是採用SHA256算法的，Qm是SHA256的base58編碼後的結果。當前，IPFS支持的常見hash算法包括：
- SHA-1：160bits，
- SHA-2-256， SHA-2-512
- SHA-3-256
- blake2b-256
注1： SHA家族的算法，由美國國家安全局（NSA）所設計，並由美國國家標準與技術研究院（NIST）發布，是美國的政府標準。SHA-x表示第x代。
注2: BLAKE2的改進版本於2012年12月21日宣布推出。它由Jean-Philippe Aumasson、Samuel Neves、Zooko Wilcox-O'Hearn和Christian Winnerlein設計，用於取代廣泛使用但已被攻破的MD5和SHA-1算法。Blake2的特點是計算更快，安全性高。
由於 Filecoin 的代碼基於IPFS之上，因此IPFS中使用的hash算法，也就自然在Filecoin中被採用，包括使用於libp2p, IPLD, 以及存儲市場和檢索市場。
Filecoin採用的其他散列算法
除了IPFS中的散列算法之外，Filecoin作為區塊鏈，在散列算法的應用上考慮更多。其中最為重要的兩個方面需要考慮的就是：1）計算的高效性；2）安全性這一點可以從Filecoin在選擇 Blake-2b 和 SHA-3 上可以看出來，Blake算法曾被其發明人Jean-Philippe Aumasson, Luca Henzen, Willi Meier, and Raphael C.-W. Phan 提交到NIST去競爭 SHA-3，但最終敗給了 Keccak（以太坊目前使用，將來也可能替換）。但 Blake2 效率更高，在實踐中安全性不輸SHA-3。因此，blake2在Filecoin中被廣泛採用。
在Filecoin中 blake2b 使用在以下一些地方：
- blake2b-256 ：IPLD，用於區塊和消息
- blake2b-4 ：用於校驗
- black2b-160：用於取代RIPEMD-160來生成 secp256k1 地址，也就是現在的 t1 地址，通常是客戶端採用的地址
Filecoin區別於現有區塊鏈的一個顯著特點是它的證明系統，也就是其複製證明和時空證明機制。在這一套機制中，hash算法也被廣泛用到。
Feistel算法
Feistel 算法本來是一個對稱密碼算法，採用數據塊鏈式加密的方式。沒有太高的複雜度。為什麼會用來作為hash函數呢？在2005年，有人就發現採用Feistel算法可以實現一個完全散列均勻的分布，而且滿足隨機性。因此，這個剛好切合 SDR 中exp parents node的選取規則。基於Feistel算法的hash函數，又成為F-Hash。Filecoin採用F-Hash來為SDR過程中的每一個節點計算找尋父節點，這些父節點隨機分布，沒有規律，同時，這些父節點又完全均勻地分布在整個sector的空間中。這簡直就是使用F-Hash的最佳場合。
PedersenHash
區塊鏈業界對零知識證明進行孜孜不倦的探索者就是令人尊敬的ZCash團隊。ZCash團隊一直在追尋如何更快更安全地進行零知識證明，在ZCash中，PedersenHash 是為 PedersenCommitment服務，這在ZCash的交易中起到舉足輕重的作用。Filecoin的複製證明和時空證明採用與ZCash類似的零知識證明，所以順理成章地採用PedersenHash。
PoseidonHash
但是，技術在不斷進步。隨著ZCash的研究，2019年5月，一篇論文橫空出世：Starkad and Poseidon: New Hash Functions for Zero-Knowledge Proof Systems。此論文號稱，採用Poseidon，其約束複雜度相對Pedersen而言，減少8倍。因此電路複雜度大大減小。證明和驗證也就更快了。在這種情況下，Filecoin團隊毅然決定，在Filecoin的證明系統中，與零知識證明相關的hash算法採用 Pedersen Poseidon。
用得最多的還是 SHA256
儘管前面提到多種不同的Hash算法，但是，在Filecoin中，SHA256還是使用的最多的一種。特別是在SDR的第一個階段，進行每一層的計算之中，所有的node計算全部採用SHA256。這帶來一個問題，那就是對SHA又特殊支持的晶片效率要高很多。這也就是為什麼Filecoin團隊最近一直在暗示AMD CPU效率更高的原因，因為AMD的多數晶片都支持 SHA-NI，而Intel目前並不支持。這個問題是的Intel設備非常尷尬，也使得市場處於一個不平衡的狀態。
既然如此，為什麼Filecoin團隊不換一個Hash算法，來達成某種平衡，不同的設備都可以進入網絡進行競爭對Filecoin網絡來說不是更好嗎？但是，我的判斷是，並不會。因為這裡又充分的理由採用SHA-256。具體原因是什麼，留給讀者自己思考。