以太坊工作量證明演算法是什麼？對於沒有把數學學會的同學來說，如果希望從演算法層瞭解以太坊的工作量證明是非常困難的。一本黃皮書會難倒一大批吃瓜群眾。因此，本文將試圖使用圖文和儘量簡單的數學來解釋以太坊挖礦工作量證明，包括以太坊是如何對抗ASIC1、如何動態調整挖礦難度、如何校驗挖礦正確性的。
認識工作量證明PoW
工作量證明(Proof-of-Work，PoW)是一種對應服務與資源濫用、或是拒絕服務攻擊的經濟對策。一般是要求使用者進行一些耗時適當的複雜運算，並且答案能被服務方快速驗算，以此耗用的時間、裝置與能源做為擔保成本，以確保服務與資源是被真正的需求所使用。
摘自維基百科
這種經濟性應對政策概念，是在1993年提，直到1999年才使用 Proof-of-Work一詞。
Proof of Work ，直接翻譯過來是工作量證明。這個詞的中文直接聽起來有點不知所云。實際上如果我跟你說結婚證明，離職證明，那你是不是首先想到的是一張上面印著一些東西的紙呢?別人看到這張紙就知道你的確結婚了，或者你的確從某單位離職了。工作量證明從語法上也是一個邏輯，也可以理解成一張紙，透過這張紙就可以證明你的確完成了一定量的工作。這就是工作量證明的字面意思。
那工作量證明有什麼特點呢?我們拋開計算機，用現實世界的例子來說明。例如我上課不認真，老師罰我把《桃花源記》抄寫十遍，我用了兩個小時的勞動，最後給老師的就是一張紙，而老師要確認我的確付出了大量勞動，其實只需要看一眼就可以了。
這個例子道出了 POW 機制的一大特點，那就是生成需要花費大量勞動，但是驗證只需一瞬間。另外一個工作量證明的例子可以是，老師給我出一道題，我給老師的運算結果，或者說就是最後的那個數字，就是我的工作量證明。回到計算機情形下，紙當然是不存在的，所以所謂的工作量證明就是花費了很多勞動而得到的一個數了。
再說說 POW 最早的用途。人們在使用電子郵件的時候會收到垃圾郵件的騷擾。如果沒有成本，那麼傳送一百萬封郵件的確是很輕鬆的事情了。所以，聰明的人就會想，如果讓每一封郵件傳送時候，都有一個微小的成本，那麼垃圾郵件就會被很大程度的遏制了。
而 POW 就是為了服務這個目的產生的。基本過程就是郵件接收方會先廣播一道題出去，郵件傳送方發郵件的時候必須附帶上這道題的答案，這樣郵件才會被接受，否則就會被認為是垃圾郵件。
摘自：https://zhuanlan.zhihu.com/p/42694998
挖礦
挖礦就是在求解一道數學方程。方程的多個可能的解被稱為解的空間。挖礦就是從中尋找一個解。不同於幾何方程，這個挖礦方程有如下特點：
1.沒有比窮舉法更有效的求解方法;
2.解在空間中均勻分佈，每一次窮舉查詢到解的概率基本一致;
3.解的空間足夠大，保證一定能夠找到解;
假設挖礦方程是：n=random(1.10)，求 n< D。
當 D為10時，我們只需要運算一次就可以找到任意的n都滿足 n<10.可當 D =5.則平均需要兩次運算才能找到 n<5.隨著D的減小，需要運算的次數就會增大。
這裡的D就是通常說的挖礦難度，透過調整解空間中的符合要求的解的數量來控制求解所需要嘗試的次數，間接的控制產生一個區塊所需要的時間。使得可以調控和穩定區塊間隔時間。
當挖礦的人很多，單位時間內嘗試次數增多時，求解的速度也就更快，區塊挖出用時更短。此時則增大挖礦難度，增大平均嘗試次數，使得挖礦耗時上升。反之依然。
以太坊新區塊挖礦流程
透過父區塊可計算新區塊的挖礦難度，再求解挖礦方程。
挖礦工作量證明透過一個密碼學安全的nonce來證明“為了獲得挖礦方程解n，已經付出了一定量的計算”。工作量證明函式可以用PoW表示：
其中
是新的區塊頭，但nonce和mixHash均為空值;2.
是區塊 difficulty 值。; 3.
是區塊mixHash值;挖礦方程演算法返還的第一個引數值; 4.
是區塊nonce值; 挖礦方程演算法返還的第二個引數值; 5.d 是一個計算mixHash所需要的大型資料集dataset;6.PoW是工作量證明函式，可以得到兩個值，其中第一個是mixHash，第二個是密碼學依賴於 H和d的偽隨機數。
這個基礎演算法就是挖礦方程Ethash。透過可以信任的挖礦方程求解，來確保區塊鏈的安全性。同時，挖出新塊還伴有區塊獎勵，所以工作量證明不僅提供安全保障，還是一個利益分配機制。
下面是挖礦工作量證明的計算過程：
大致流程如下：
1.根據父區塊頭和新區塊頭計算出
;2.在PoW開始時選擇一個隨機數作為Nonce的初始化值;3.將Nonce和作為挖礦方程Ethash的入參;4.執行Ethash將得到兩個返回值：mixHash和 result;5.判斷 result 是否高於
。如果是則 nonce加1.繼續窮舉查詢;否則，如果是則說明求解成功。返回 mixHash和Nonce;6.兩個值記錄到區塊頭中，完成挖礦。
區塊難度 difficulty
以太坊的挖礦難度記錄在區塊頭difficulty上 ，那麼在它是如何動態調整的呢?
調整演算法在以太坊主網有多次修改，即使以太坊黃皮書中的定義也和實際實現程式碼也不一致，這裡我以程式實現程式碼來講解區塊難度調整演算法。
其中有：
是創世區塊的難度值。難度值引數
被用來影響出塊時間的動態平衡。使用了變數而非直接使用兩個區塊間的時間間隔，是用於保持演算法的粗顆粒度，防止當區塊時間間隔為1秒時只有稍微高難度情況。也可以確保該情況下容易導致到軟分叉。
-99 的上限只是用來防止客戶端安全錯誤或者其他黑天鵝問題導致兩個區塊間在時間上相距太遠，難度值也不會下降得太多。在數學理論是兩個區塊的時間間隔不會超過24秒。
難度增量 ∈ 會越來越快地使難度值緩慢增長(每10萬個區塊)，從而增加區塊時間差別，為以太坊2.0的權益證明(proof-of-stake)切換增加了時間壓力。這個效果就是所謂的“難度炸彈”(“difcultybomb”)或“冰河時期”(“iceage”)。
以太坊的設想是最終從PoW過度到PoS，為了給過度施加時間壓力，所以在區塊難度中預埋了一個難度炸彈 ∈ ，他是以2的指數級增長的。如果聽過“棋牌擺米”的數學故事，就應該清楚指數級增長是非常恐怖的。
最終，在拜占庭版本中，伴隨EIP-649.透過偽造一個區塊號
來延遲冰河時期的來臨。這是透過用實際區塊號減去300萬來獲得的。換句話說，就是減少 ∈ 和區塊間的時間間隔，來為權益證明的開發爭取更多的時間並防止網路被“凍結”。
在君士坦丁堡版本升級中，以太坊開發者在影片會議中表示，如果直接執行難度炸彈，那麼難保以太坊能順利切換到PoS就有大量礦工離開，這很有可能極大的影響以太坊的安全性。因此，伴隨EIP-1234.再一次修改
到500萬來延遲冰河時期。
這個挖礦難度調整機制保證了區塊時間的動態平衡;如果最近的兩個區塊間隔較短，則會導致難度值增加，因此需要額外的計算量，大概率會延長下個區塊的出塊時間。相反，如果最近的兩個區塊間隔過長，難度值和下一個區塊的預期出塊時間也會變短。
挖礦方程Ethash
區塊鏈鼻祖比特幣，是PoW共識，已經穩定執行10年。但在2011年開始，因為比特幣有利可圖，市場上出現了專業礦機專門針對雜湊演算法、散熱、耗能進行最佳化，這脫離了比特幣網路節點執行在成千上萬的普通計算機中並公平參與挖礦的初衷。這容易造成節點中心化，面臨51%攻擊風險。因此，以太坊需要預防和改進PoW。因此在以太坊設計共識演算法時，期望達到兩個目的：
1.抗ASIC1性：為演算法建立專用硬體的優勢應儘可能小，理想情況是即使開發出專有的積體電路，加速能力也足夠小。以便普通計算機上的使用者仍然可以獲得微不足道的利潤。2.輕客戶端可驗證性: 一個區塊應能被輕客戶端快速有效校驗。
在以太坊早期起草的共識演算法是 Dagger-Hashimoto，由 Buterin和 Dryja提出。但被證明很容易受到 Sergio Lerner 共享記憶體硬體加速的影響。所以最終拋棄了 Dagger-Hashimoto，改變研究方向。在對 Dagger-Hashimoto 進行大量修改，終於形成了明顯不同於 Dagger-Hashimoto 的新演算法：Ethash。Ethash 就是以太坊1.0 的挖礦方程。
介紹
這個演算法的大致流程如下：
1.透過掃描區塊頭直到某點，來為每個區塊計算得到一個種子 Seed。2.根據種子可以計算一個初始大小為 16MB的偽隨機快取cache。輕客戶端儲存這個 cache,用於輔助校驗區塊和生成資料集。3.根據 cache， 可以生成一個初始大小為 1GB的DAG資料集。資料集中的每個條目(64位元組)僅依賴於 cache 中的一小部分條目。資料集會隨時間線性增長，每30000個區塊間隔更新一次。資料集僅僅儲存在完整客戶端和礦工節點，但大多數時間礦工的工作是讀取這個資料集，而不是改變它。4.挖礦則是在資料集中選取隨機的部分並將他們一起雜湊。可以根據 cache 僅生成驗證所需的部分，這樣就可以使用少量記憶體完整驗證，所以對於驗證來講，僅需要儲存 cache 即可。
這裡cache選擇16 MB 快取是因為較小的快取記憶體允許使用光評估(light-evaluation)方法,太容易用於 ASIC。16 MB 快取仍然需要非常高的快取讀取頻寬，而較小的快取記憶體可以更容易地被最佳化。較大的快取會導致演算法太難而使得輕客戶端無法進行區塊校驗。
選擇初始大小為 1GB 的DAG資料集是為了要求記憶體級別超過大多數專用記憶體和快取的大小，但普通計算機能夠也還能使用它。資料集選擇 30000 個塊更新一次，是因為間隔太大使得更容易建立被設計為非常不頻繁地更新並且僅經常讀取的記憶體。而間隔太短，會增加進入壁壘，因為弱機器需要花費大量時間在更新資料集的固定成本上。
同時，快取和資料集大小隨時間線性增長，且為了降低迴圈行為時的偶然規律性風險，資料大小是一個不超過上限的素數。每年約以0.73倍的速度增長，這個增長速率大致同摩爾定律持平。這仍有越過摩爾定律的風險，將導致挖礦需要非常大量的記憶體，使得普通的GPU不再能用於挖礦。因為可透過使用快取重新生成所需資料集的特定部分，少量記憶體進行PoW驗證，因此你只需要儲存快取，而不需要儲存資料集。
快取和資料集大小
快取c和資料集d的大小依賴用區塊的視窗週期Eepoch。
每過一個視窗週期後，資料集固定增長8MB(223 位元組)，快取固定增長 128kb(217 位元組)。為了降低迴圈行為時的偶然規律性風險，資料大小必須是一個素數。計算快取大小公式：
計算資料大小公式：
其中，求素數公式如下：
這個素數計算是從不高於上限值中向下依次遞減2*64位元組遞迴查詢，直到 x/64是一個素數。
生成種子雜湊值
種子seed實際是一個雜湊值，每個視窗週期(30000個區塊)更新一次。它是經過多次疊加Keccak256計算得到的。
第一個視窗週期內的種子雜湊值s 是一個空的32位元組陣列，而後續每個週期中的種子雜湊值，則對上一個週期的種子雜湊值再次進行Keccak256雜湊得到。
生成快取cache
快取cache 生成過程中，是將cache切割成64位元組長的若干行陣列操作的。
先將種子雜湊值的Keccak512結果作為初始化值寫入第一行中;隨後，每行的資料用上行資料的Keccak512雜湊值填充;最後，執行了3次 RandMemoHash演算法(在嚴格記憶體硬雜湊函式 Strict Memory Hard Hashing Functions (2014)中定義的記憶體難題演算法)。該生成演算法的目的是為了證明這一刻確實使用了指定量的記憶體進行計算。
RandMemoHash 演算法可以理解為將若干行進行首尾連線的環鏈，其中n為行數。
每次RandMemoHash 計算是依次對每行進行重新填充。先求第 i 行的前後兩行值得或運算結果，再對結果進行Keccak512雜湊後填充到第i行中。
最後，如果作業系統是 Big-Endian(非little-endian)的位元組序，那麼意味著低位位元組排放在記憶體的高階，高位位元組排放在記憶體的低端。此時，將快取內容進行倒排，以便調整記憶體存放順序。最終使得快取資料在記憶體中排序順序和機器位元組順序一致。
生成資料集
利用快取cache來生成資料集，首先將快取切割成n個16 bytes大小的單元。在生成過程中時將資料集切割為若干個64bytes大小的資料項，可對每項資料mix併發生成。最終將所有資料項拼接成資料集。
1.在生成index行的資料時，先從快取中獲取第 index % n 個單元的值u;
2.資料項mix長度64bytes，分割為4bytes的16個uint32.第一個uint32等於 u^index，其他第i個uint32等於u+i;
3.用資料項mix的Keccak512雜湊值覆蓋mix;
4.對mix進行FNV雜湊。在FNV雜湊時，是要從快取中獲取256個父項進行運算。
1)確定第p個父項位置: FNV(index^p ， mix[p%16]) % n;2)再將FNV( mix[p%16], cache[p] )的值填充到 mix[p%16]中;其中，FNV(x,y)= x*0x01000193 ^ y ;這裡的256次計算，相當於mix的16個uint32迴圈執行了16次。
5.再一次用資料項mix的Keccak512雜湊值覆蓋mix;
6.如果機器位元組序是Big-Endian的，則還需要交換高低位;
7.最後將mix填充到資料集中，即 dataset[index]=mix;
注意，在FNV雜湊計算中，初始大小1 GB資料集累積需要約42億次(16777216 * 256) 次計算。即使併發計算，也需要一定的時間才能完成一次資料集生成。這也就是為什麼在啟動一個geth挖礦節點時，剛開始時會看到一段“Generating DAG in progress” 的日誌，直到生成資料集完成後，才可以開始挖礦。
Ethash挖礦方程求解
準備好資料集dataset就可以用於工作量證明計算。依賴nonce、h、dataset可計算出的一個偽隨機數N，工作量證明就是校驗N是否符合難度要求。工作量計算由挖礦方程Ethash定義。
上圖是Ethash的計算流程圖。說明如下：
1.首先將傳入的新區塊頭雜湊值和隨機數nonce拼接後進行KEC512雜湊，得到64位元組的種子seed;
2.然後初始化一個128位元組長的mix，初始化時分割成32個4位元組的單元;使用128位元組的順序訪問，以便每次Ethash計算都始終從RAM提取整頁，從而最小化頁表快取未命中情況。理論上，ASIC是可以避免的;
3.mix陣列的每個元素值來自於seed; mix[i]= s[i%16*4];是seed的第0、4、8...60位的值;
4.緊接著完成64次迴圈記憶體隨機讀寫。每次迴圈需要從 dataset 中取指定位置p(fnv(i^s[:32]，i%32) % rows)和p+1上的兩個16位元組拼接成32位元組的m;然後，使用fnv(mix[i],m[i])去覆蓋mix[i]; 其中，i是迴圈索引、s[:32]是種子seed的前32位元組、rows是表示資料集dataset可分成rows個128位元組。
5.然後壓縮mix。壓縮是將mix以每16位元組分別壓縮得到8個壓縮項。每16位元組又是4小份的fnv疊加雜湊值fnv(fnv(fnv(m[0],m[1]),m[2]),m[3]);
6.拼接這8個壓縮項就得到mix的雜湊值mixHash;
7.最後將seed和mixHash進行KEC256雜湊得到偽隨機數N;8.最終，返回這兩個引數：mixHash和N;
