區塊鏈技術六大核心算法，你知道幾個？

隨著比特幣、萊特幣礦機相繼出現，大家已經認識到沒有不能開發礦機的算法，想通過改進算法來徹底阻止礦機和礦池的出現是不可能的。

區塊鏈核心算法一：拜占庭協定

拜占庭的故事大概是這麼說的：拜占庭帝國擁有巨大的財富，周圍10個鄰邦垂誕已久，但拜占庭高牆聳立，固若金湯，沒有一個單獨的鄰邦能夠成功入侵。任何單個鄰邦入侵的都會失敗，同時也有可能自身被其他9個鄰邦入侵。拜占庭帝國防禦能力如此之強，至少要有十個鄰邦中的一半以上同時進攻，才有可能攻破。然而，如果其中的一個或者幾個鄰邦本身答應好一起進攻，但實際過程出現背叛，那麼入侵者可能都會被殲滅。於是每一方都小心行事，不敢輕易相信鄰國。這就是拜占庭將軍問題。

在這個分佈式網絡裡：每個將軍都有一份實時與其他將軍同步的消息賬本。賬本里有每個將軍的簽名都是可以驗證身份的。如果有哪些消息不一致，可以知道消息不一致的是哪些將軍。儘管有消息不一致的，只要超過半數同意進攻，少數服從多數，共識達成。

由此，在一個分佈式的系統中，儘管有壞人，壞人可以做任意事情（不受protocol限制），比如不響應、發送錯誤信息、對不同節點發送不同決定、不同錯誤節點聯合起來幹壞事等等。但是，只要大多數人是好人，就完全有可能去中心化地實現共識。

區塊鏈核心算法二：非對稱加密技術

在上述拜占庭協定中，如果10個將軍中的幾個同時發起消息，勢必會造成系統的混亂，造成各說各的攻擊時間方案，行動難以一致。誰都可以發起進攻的信息，但由誰來發出呢？其實這只要加入一個成本就可以了，即：一段時間內只有一個節點可以傳播信息。當某個節點發出統一進攻的消息後，各個節點收到發起者的消息必須簽名蓋章，確認各自的身份。

在如今看來，非對稱加密技術完全可以解決這個簽名問題。非對稱加密算法的加密和解密使用不同的兩個密鑰.這兩個密鑰就是我們經常聽到的”公鑰”和”私鑰”。公鑰和私鑰一般成對出現, 如果消息使用公鑰加密,那麼需要該公鑰對應的私鑰才能解密; 同樣，如果消息使用私鑰加密,那麼需要該私鑰對應的公鑰才能解密。

區塊鏈核心算法三：容錯問題

我們假設在此網絡中，消息可能會丟失、損壞、延遲、重複發送，並且接受的順序與發送的順序不一致。此外，節點的行為可以是任意的：可以隨時加入、退出網絡，可以丟棄消息、偽造消息、停止工作等，還可能發生各種人為或非人為的故障。我們的算法對由共識節點組成的共識系統，提供的容錯能力，這種容錯能力同時包含安全性和可用性，並適用於任何網絡環境。

區塊鏈核心算法四：Paxos 算法（一致性算法）

Paxos算法解決的問題是一個分佈式系統如何就某個值(決議)達成一致。一個典型的場景是，在一個分佈式數據庫系統中，如果各節點的初始狀態一致，每個節點都執行相同的操作序列，那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列，需要在每一條指令上執行一個“一致性算法”以保證每個節點看到的指令一致。一個通用的一致性算法可以應用在許多場景中，是分佈式計算中的重要問題。節點通信存在兩種模型：共享內存和消息傳遞。Paxos算法就是一種基於消息傳遞模型的一致性算法。706878

區塊鏈核心算法五：共識機制

區塊鏈共識算法主要是工作量證明和權益證明。拿比特幣來說，其實從技術角度來看可以把PoW看做重複使用的Hashcash，生成工作量證明在概率上來說是一個隨機的過程。開採新的機密貨幣，生成區塊時，必須得到所有參與者的同意，那礦工必須得到區塊中所有數據的PoW工作證明。與此同時礦工還要時時觀察調整這項工作的難度，因為對網絡要求是平均每10分鐘生成一個區塊。

區塊鏈核心算法六：分佈式存儲

分佈式存儲是一種數據存儲技術，通過網絡使用每台機器上的磁盤空間，並將這些分散的存儲資源構成一個虛擬的存儲設備，數據分散的存儲在網絡中的各個角落。所以，分佈式存儲技術並不是每台電腦都存放完整的數據，而是把數據切割後存放在不同的電腦裡。就像存放100個雞蛋，不是放在同一個籃子裡，而是分開放在不同的地方，加起來的總和是100個。

算法演進之路

算法演進

關於“算法”一詞，目前國內用戶使用的比較模糊，有時指共識機制，比如POW算法，POS算法；有時指具體的Hash算法，比如SHA256，SCRYPT。應該說這是由於早期從外文資料翻譯過來概念模糊導致的錯誤，後來人云亦云。共識機制（以前一般叫Proof，現在經常使用Consensus）和算法（Algorithm）在英文資料里語義清晰，不能混為一談，兩者都是區塊鏈技術體系裡的重要支柱。

因此當我們說“X幣使用Y算法”的時候，其實具體指的是採用何種Hash算法，而且隱含的前提條件是這個幣使用POW證明方式。只有在POW下討論選取何種算法才有意義，算法的各種複雜設計才能體現其用處。為什麼呢，中本聰在設計比特幣的時候其實有很多地方用到Hash函數，比如計算區塊ID，計算交易ID，構造代幣地址等。我們說的算法具體是指用何種Hash函數計算區塊ID，所謂算法創新也就是在這個地方下功夫。此外其他任何用到Hash函數的地方，對計算難度沒有要求，而且應該選用可以快速運算的算法，尤其在計算交易ID時候，不然影響區塊鏈同步速度。因此如果選用POS方式，計算區塊ID也應該使用容易運算的算法。

Hash函數

如上所言，我們經常說的POW算法本質是一個Hash函數。Hash函數是一個無比神奇的東西，說他替中本聰打下了半壁江山一點不為過，學習比特幣應該從學習Hash函數入手，理解了Hash函數再去學比特幣原理將事半功倍，不然將處處感覺混沌，難以開竅。而中本聰也將Hash函數的所有特性使用得淋漓盡致：

已經有很多Hash函數被設計出來並廣泛應用，不過Hash函數一般安全壽命都不長，被認為安全的算法往往沒能使用多久就被成功攻擊，新的更安全的算法相繼被設計出來，而每一個被公認為安全可靠的算法都有及其嚴格的審計過程。在幣圈中我們經常說某某幣發明了某種算法，其實主要都是使用那些被認證過的安全算法，或是單獨使用，或是排列組合使用。

SHA256

SHA (Secure Hash Algorithm，譯作安全散列算法) 是美國國家安全局(NSA) 設計，美國國家標準與技術研究院(NIST) 發布的一系列密碼散列函數，經歷了SHA-0，SHA-1 ，SHA-2，SHA-3系列發展。NSA於2007年正式宣佈在全球範圍內徵集新新一代（SHA-3）算法設計，2012年公佈評選結果， Keccak算法最終獲勝成為唯一官方標準SHA-3算法，但還有四種算法同時進入了第三輪評選，分別是：BLAKE, GrøSTL, JH和SKEIN，這些算法其實也非常安全，而且經受審查，被各種競爭幣頻繁使用。

比特幣採用SHA256算法，該算法屬於SHA-2系列，在中本聰發明比特幣時（2008）被公認為最安全最先進的算法之一。除了生成地址中有一個環節使用了REPID-160算法，比特幣系統中但凡有需要做Hash運算的地方都是用SHA256。隨著比特幣被更多人了解，大家開始好奇中本聰為何選擇了SHA256，同時對SHA256的安全性發表各種意見，SHA256妥妥經受了質疑，到目前為止，沒有公開的證據表明SHA256有漏洞，SHA256依然牢牢抗住保衛比特幣安全的大旗。當然大家心裡都明白，沒有永遠安全的算法，SHA256被替代是早晚的事，中本聰自己也說明了算法升級的必要和過程。

SCRYPT

後來隨著顯卡挖礦以及礦池的出現，社區開始擔心礦池會導致算力集中，違背中本聰“一CPU一票”的最初設計理念。在那段時間，中心化的焦慮非常嚴重，討論很激烈，比特幣一次又一次“被死亡”，直到現在，針對礦池是否違背去中心化原則的爭論仍在繼續。

無論如何，有人將矛頭指向SHA256，認為是算法太容易導致礦機和礦池出現，並試圖尋找更難的算法。

恰逢其時，使用SCRYPT算法的萊特幣（Litecoin）橫空出世。據說SCRYPT是由一位著名的黑客開發，由於沒有得到諸如SHA系列的嚴格的安全審查和全面論證，一直沒被廣泛推廣使用。與SHA256算法相比，SCRYPT佔用的內存更多，計算時間更長，並行計算異常困難，對硬件要求很高。很顯然，SCRYPT算法具有更強的抵禦礦機性，萊特幣還將區塊時間改為2.5分鐘，在那個山寨幣還鳳毛麟角年代，萊特幣依靠這兩點創新大獲成功，長期穩坐山寨幣第一寶座位置。

後來有人在SCRYPT的基礎上稍作修改形成Scrypt –N算法，改進思路都一樣，都是追求更大的內存消耗和計算時間，以有效阻止ASIC專用礦機。

很快，萊特幣的成功催生了各種各樣的算法創新，2012至2014年間，算法創新一直都是社區討論的熱門話題，每一個使用創新算法的幣種出現，都能刮起一陣波瀾。

串聯算法

重新排列組合是人類一貫以來最常用的創新發明方法。很快，有人不滿足於使用單一Hash函數，2013年7月，夸克幣（Quark）發布，首創使用多輪Hash算法，看似高大上，其實很簡單，就是對輸入數據運算了9次hash函數，前一輪運算結果作為後一輪運算的輸入。這9輪Hash共使用6種加密算法，分別為BLAKE, BMW, GROESTL, JH, KECCAK和SKEIN，這些都是公認的安全Hash算法，並且早已存在現成的實現代碼。

這種多輪Hash一出現就給人造成直觀上很安全很強大的感覺，追捧者無數。現今價格依然堅挺的達世幣（DASH，前身是暗黑幣，Darkcoin，）接過下一棒，率先使用11種加密算法（BLAKE, BMW, GROESTL, JH, KECCAK, SKEIN, LUFFA, CUBEHASH, SHAVITE, SIMD, ECHO），美其名曰X11，緊接著X13，X15這一系列就有人開發出來了。

S系列算法實際是一種串聯思路，只要其中一種算法被破解，整個算法就被破解了，好比一根鏈條，環環相扣，只要其中一環斷裂，整個鏈條就一分為二。

並聯算法

有人串聯，就有人並聯，Heavycoin（HVC）率先做了嘗試。HVC如今在國內名不見經傳，當時還是名噪一時，首次實現鏈上游戲，作者是俄羅斯人，後來不幸英年早逝，在幣圈引起一陣惋惜。

HVC算法細節：

1. 對輸入數據首先運行一次HEFTY1（一種Hash算法）運算，得到結果d1
2. 以d1為輸入，依次進行SHA256、KECCAK512、GROESTL512、BLAKE512運算，分別獲得輸出d2,d3,d4和d5
3. 分別提取d2-d5前64位，混淆後形成最終的256位Hash結果，作為區塊ID。

之所以首先進行一輪HEFTY1 哈希，是因為HEFTY1 運算起來極其困難，其抵禦礦機性能遠超於SCRYPT。但與SCRYPT一樣，安全性沒有得到某個官方機構論證，於是加入後面的四種安全性已經得到公認的算法增強安全。

對比串聯和並聯的方法，Quark、X11，X13等雖使用了多種HASH函數，但這些算法都是簡單的將多種HASH函數串聯在一起，仔細思考，其實沒有提高整體的抗碰撞性，其安全性更是因木桶效應而由其中安全最弱的算法支撐，其中任何一種Hash函數遭遇碰撞性攻擊，都會危及貨幣系統的安全性。

HVC從以上每種算法提取64位，經過融合成為最後的結果，實際上是將四種算法並聯在一起，其中一種算法被破解只會危及其中64位，四中算法同時被破解才會危及貨幣系統的安全性。

比特幣只使用了一種Hash算法，假如未來某日SHA256被證明不再安全時，雖然可以更該算法，但考慮到如今“硬分叉猛於虎”的局面，屆時引發動盪不可避免，但如果使用並聯算法，就可以爭取平靜的硬分叉過渡時間。

PRIMECOIN

正當一部分人在算法探索之路上進行的如火如荼之時，另一部分人的聲音也非常刺耳，那就是指責POW浪費能源（彼時POS機制已經實現）。POW黨雖極力維護，但也承認耗費能源這一事實。這一指責打開了另一條探索之路，即如果能找到一種算法，既能維護區塊鏈安全，這些Hash運算又能在其他方面產生價值，那簡直更完美。

在這條探索之路上最讓人振奮人心的成果來自於Sunny King（這大神之前已經開發了Peercoin，點點幣）發明的素數幣（Primecoin）。素數幣算法的核心理念是：在做Hash運算的同時尋找大素數。素數如今已被廣泛應用於各個領域，但人類對他的認識還是有限。素數在數軸上不但稀有（相對於偶數而言），而且分佈不規律，在數軸上尋找素數只能盲目搜索探測，這正是POW的特徵。

POW還有另一個要求是容易驗證，這方面人類經過幾百年探索已經獲得一些成果。素數幣使用兩種方法測試，首先進行費馬測試（Fermat Test），通過則再進行歐拉-拉格朗日-立夫習茲測試（Euler-Lagrange-Lifchitz Test），還通過測試則被視為是素數。需要指出的是，這種方法並不能保證通過測試的數百分百是素數，不過這並不影響系統運行，即便測試結果錯誤，只要每個節點都認為是素數就行。

素數幣其實找的是素數鏈-坎氏鏈，存在三個特定類型的坎氏素數鏈：第一類坎氏鏈，第二類坎氏鍊和雙坎氏鏈。

舉第一類來說明，規則是：素數鏈中每個數都是前一個數的兩倍減一，比如：
1531，3061，6121，12241，24481

數列的下一個數48961(24481*2-1)不是素數，因而這個坎氏鏈的長度是5，素數幣的目標就是探索更長的坎氏鏈（以上三類都可以）。

那麼現在最重要的問題來了，如何用坎氏鏈來驗證一個區塊是否合格呢？素數幣實現的細節是這樣的：

1. 計算中本聰區塊頭Hash，hashBlockHeader = SHA256(BlockHeader)
2. 通過變換獲得坎氏鏈的第一個數：originNum = hashBlockHeader * Multiplier

獲取originNum之後就可以測試併計算素數鍊長度的整數部分，小數部分的計算與坎氏鏈最後一個非素數的跨度相關。

每個區塊的乘積因子Multiplier各不相同，計算過程和hashBlockHeader相關，素數幣為此對區塊頭進行修改，專門增加一個字段（bnPrimeChainMultiplier）來存放這個乘積因子。但是以上第一步計算hashBlockHeader時輸入數據並不包含這個乘積因子，這也是為啥特別指出中本聰區塊頭。

由於素數在數軸上分佈不均勻，且根據目前掌握的知識來看，數越大，素數越稀有，尋找難度並不是線性遞增，耗時也就不可預估，但是區塊鏈要求穩定出塊。正因為這點，素數幣算法沒有得到熱捧，但這種探索並非沒有意義，利用POW工作量的“幻想”並沒有停止，探索還在繼續。

ETHASH

以太坊（Ethereum）一開始就打算使用POS方式，但由於POS設計存在一些問題，開發團隊決定在以太坊1.0階段使用POW方式，預計在Serenity階段轉入POS。

以太坊POW算法叫Ethash，雖只是一個過渡算法，但開發團隊一點也不含糊，一如既往發揚其“簡單問題複雜化，繁瑣細節秀智商”的設計風格。Ethash 是最新版本的 Dagger-Hashimoto改良算法，是Hashimoto算法結合Dagger算法產成的一個新變種。Ethash設計時就明確兩大目標：

抵禦礦機性能（ASIC-resistance），團隊希望CPU也能參與挖礦獲得收益。

輕客戶端可快速驗證（Light client verifiability）。

基於以上兩個目標，開發團隊最後倒騰出來的Ethash挖礦時基本與CPU性能無關，卻和內存大小和內存帶寬成正相關。不過在實現上還是藉鑑了SHA3的設計思路，​​但是使用的”SHA3_256” ,”SHA3_512”與標準實現很不同。

Ethash基本流程是這樣的：對於每一個塊，首先計算一個種子（seed），該種子只和當前塊的信息有關；然後根據種子生成一個32M的隨機數據集（Cache）；緊接著根據Cache生成一個1GB大小的數據集合（DAG），DAG可以理解為一個完整的搜索空間，挖礦的過程就是從DAG中隨機選擇元素（類似於比特幣挖礦中查找合適Nonce）再進行哈希運算。可以從Cache快速計算DAG指定位置的元素，進而哈希驗證。此外還要求對Cache和DAG進行週期性更新，每1000個塊更新一次，並且規定DAG的大小隨著時間推移線性增長，從1G開始，每年大約增長7G左右。

EQUIHASH

最近在國內發展勢頭最猛的莫過於Zcash，該幣種最大的特點是使用零知識證明實現隱私交易。距離發布還有幾天，但從社區討論來看，各方礦工都已在磨刀霍霍。Zcash對於算法的選擇非常慎重，在先後考量了SHA256D，SCRYPT，CUCKOO HASH以及LYRA2等算法後，最終選擇Equihash。

Equihash算法由Alex Biryukov 和Dmitry Khovratovich聯合發明，其理論依據是一個著名的計算法科學及密碼學問題——廣義生日悖論問題。Equihash是一個內存（ARM）依賴型算法，機器算力大小主要取決於擁有多少內存，根據兩位發明者的論文描述，該算法執行至少需要700M內存，1.8 GHz CPU計算30秒，經Zcash項目優化後，目前每個挖礦線程需要1G內存，因此Zcash官方認為該算法在短時間內很難出現礦機（ASIC）。此外，Zcash官方還相信該算法比較公平，他們認為很難有人或者機構能夠對算法偷偷進行優化，因為廣義生日悖論是一個已經被廣泛研究的問題。此外，Equihash算法非常容易驗證，這對於未來在受限設備上實現Zcash輕客戶端非常重要。

Zcash官方團隊選擇Equihash完全出於抵禦礦機性能的需求，他們在官方博客中也承認並不敢確保Equihash一定是安全的，並表示如果發現Equihash存在問題，或者發現更優算法，Zcash會改變POW算法。

總結

隨著比特幣、萊特幣礦機相繼出現，大家已經認識到沒有不能開發礦機的算法，想通過改進算法來徹底阻止礦機和礦池的出現是不可能的。另外，從近幾年的發展來看，礦池也沒有之前想的那麼可怕，甚至已經有人論證了礦池並沒有破壞去中心化。但除了安全性，POW往往伴隨分發代幣功能，從這個角度來說，CPU算法更具公平性，用戶門檻更低，這也是算法創新的驅動，從Ethash以及Equihash設計來看，目前的算法創新仍然是以追求內存高消耗為主。以此同時，社區在共識機制的探索之路上也取得很多成果。縱觀當前區塊鏈核心技術發展全局，算法創新熱潮已經有所消退，但也未停止，於比特幣，於區塊鏈，於算法探索而言，都還在路上。