工作量證明（PoW）

工作量證明（PoW） 是一種加密證明方式，其中一方（證明者）向其他方（驗證者）證明其已經付出了特定數量的計算努力。驗證者隨後可以以極少的努力確認這一支出。該概念最早在 1993 年由 Moni Naor 和 Cynthia Dwork 在 Hashcash 中實現，作為一種通過要求服務請求方進行一些工作（通常是計算機處理時間）來阻止拒絕服務攻擊和其他網絡服務濫用（如垃圾郵件）的方法。術語「工作量證明」首次出現在 1999 年 Markus Jakobsson 和 Ari Juels 的論文中，並被正式化。該概念在 2004 年被 Hal Finney 通過「可重複的工作量證明」思想應用到數字代幣上，使用的是 160 位安全哈希算法 1（SHA-1）。

工作量證明後來被比特幣作為去中心化、無需許可的網絡共識基礎所推廣，礦工通過競爭附加區塊和挖掘新貨幣來進行工作，每個礦工的成功概率與其所投入的計算努力成正比。PoW 和 PoS（權益證明）是目前最知名的 Sybil 攻擊防範機制，在加密貨幣的背景下，它們是最常見的機制。

工作量證明方案的一個關鍵特徵是其不對稱性：計算工作對於證明者或請求者而言必須適度困難（但可行），而對於驗證者或服務提供者而言檢查起來則非常容易。這一理念也被稱為 CPU 成本函數、客戶端難題、計算難題或 CPU 定價函數。另一個常見特徵是內建的激勵結構，通過將計算能力分配到網絡上，獎勵以加密貨幣的形式提供價值。

工作量證明算法的目的是通過設定較大的能量和硬體控制要求來防止數據被操縱，而不是證明某項工作已完成或某個計算難題已被「解決」。工作量證明系統因其能源消耗問題而受到環保人士的批評。

背景

工作量證明（PoW）的概念源於早期研究，旨在防止垃圾郵件和拒絕服務攻擊（DoS）。PoW 的最早實現之一是 Hashcash，由英國密碼學家 Adam Back 於 1997 年創建。它被設計為一種反垃圾郵件機制，要求電子郵件發送者執行一個小的計算任務，從而有效地證明他們在發送電子郵件之前已經消耗了資源（以 CPU 時間的形式）。對於合法用戶而言，這個任務是微不足道的，但對於試圖發送大量郵件的垃圾郵件發送者來說，執行該任務會產生顯著的成本。

Hashcash 的系統基於尋找滿足特定標準的哈希值這一概念，這一任務需要計算工作，因此充當了「工作量證明」。其思想是通過讓發送大量電子郵件的行為在計算上變得昂貴，從而減少垃圾郵件的數量。

在 Hashcash 中使用的一個流行系統是通過部分哈希反轉來證明已經進行過計算，作為發送電子郵件的善意標記。例如，以下標題表示要向 [email protected] 發送一封郵件，需要進行大約 252 次哈希計算：

X-Hashcash: 1:52:380119:[email protected]:::9B760005E92F0DAE

它通過單次計算進行驗證，方法是檢查戳記（去除 X-Hashcash: 標頭，包括冒號和任何空白字符，直到數字 '1'）的 SHA-1 哈希值是否以 52 個二進位零開頭，也就是 13 個十六進位零：

0000000000000756af69e2ffbdb930261873cd71

PoW 系統是否能夠真正解決像垃圾郵件問題這樣的拒絕服務問題尚有爭議；該系統必須使垃圾郵件發送者發送垃圾郵件的行為變得顯著不具生產力，但又不應阻止合法用戶發送電子郵件。換句話說，真正的用戶在發送電子郵件時不應遇到任何困難，但垃圾郵件發送者必須花費大量計算能力才能一次發送許多電子郵件。工作量證明系統已被更複雜的加密系統所使用，例如比特幣，它使用了類似於 Hashcash 的系統。

變種

工作量證明協議有兩類。

• 挑戰-響應協議 假設請求方（客戶端）和提供方（伺服器）之間有直接的互動連接。提供方選擇一個挑戰，例如選擇一個具有某種屬性的集合中的某個項，請求方在集合中找到相關的響應，並將其返回給提供方進行檢查。由於挑戰由提供方當場選擇，因此其難度可以根據提供方當前的負載進行調整。如果挑戰-響應協議具有已知解決方案（由提供方選擇），或者已知解決方案存在於有限的搜索空間內，則請求方一側的工作可能是有限的。

• 解決方案-驗證協議 則不假設有這樣的連接：因此，問題必須在請求方尋求解決方案之前自我設定，提供方必須檢查問題選擇和找到的解決方案。大多數這樣的方案是無界的概率迭代過程，例如 Hashcash。

已知解決方案協議通常比無界概率協議具有稍低的方差，因為矩形分布的方差低於泊松分布的方差（在均值相同的情況下）。減少方差的一種通用技術是使用多個獨立的子挑戰，因為多個樣本的平均值將具有更低的方差。

還有一些固定成本函數，例如時間鎖難題。

此外，這些方案所使用的底層函數可能是：

• CPU綁定：計算速度受處理器的限制，計算速度在時間上有很大的變化，也會在高端伺服器和低端便攜設備之間有所不同。
• 內存綁定：計算速度受主內存訪問（無論是延遲還是帶寬）的限制，其性能預計對硬體的演變不那麼敏感。
• 網絡綁定：如果客戶端必須執行很少的計算，但必須從遠程伺服器收集一些令牌，然後再查詢最終的服務提供方。在這種情況下，工作實際上並不是由請求方執行的，但由於獲取所需令牌的延遲，仍然會產生延遲。

最後，一些 PoW 系統提供捷徑計算，允許知道某個秘密（通常是私鑰）的參與者生成便宜的 PoW。其原理是，郵件列表持有者可以為每個收件人生成戳記，而不會產生高成本。是否需要此功能取決於使用場景。

工作量證明函數列表

以下是已知的工作量證明函數列表：

• 大素數模運算的整數平方根
• 弱化的 Fiat–Shamir 簽名
• Ong–Schnorr–Shamir 簽名，被 Pollard 破解
• 部分哈希反轉：本文形式化了工作量證明的概念，並引入了「麵包布丁協議」的相關思想，這是一個「可重用的工作量證明」 (RPoW) 系統。
• 哈希序列
• Puzzles
• 基於 Diffie-Hellman 的難題
• Moderate
• Mbound
• 北海道難題（Hokkaido）
• 雜樹（Cuckoo Cycle）
• 基於 Merkle 樹的
• 引導遊覽難題協議