首先我們從討論設計一個可以反ASIC解謎(ASIC-resistant puzzles)的挑戰開始，這個挑戰也是最被廣泛討論和追求的可替代目前比特幣挖礦解謎的一種。我們在第5章中討論過，比特幣挖礦最初是用普通電腦，然後再升級到GPU和定制化的FPGA設備，到現在基本上由非常強大的優化過的ASIC芯片所壟斷。現在的ASIC的挖礦運算能力比一般電腦甚至早期的ASIC都要高太多。一般的電腦即使硬件本身是免費的，也會因為電費價格等因素而變得不可行。
這個轉變意味著，在比特幣生態系統裡的大部分個體（例如使用比特幣交易的客戶和商家）已經無法參與到挖礦過程中了。有些人認為這是一個危險的勢頭，一小部分職業礦工控制了整個挖礦的過程。在中本聰最初有關比特幣的論文裡，用到過「一個CPU一票」的說法，這個說法時不時被有些人用來說明比特幣應該是一個被全部用戶所擁有的民主系統。
其他人覺得ASIC的崛起是不可避免的，而且這也不會傷害到比特幣，這種希望實現反ASIC的願望也只是有些人希望回到「過去的好時光」。對於反ASIC是否可取，我們保持中立的態度，因為只有這樣，我們才可以深入討論一些技術上的挑戰和提議的方案，來實現反ASIC的目標。
反ASIC到底是什麼意思
大致上說，我們想抑制為了挖礦而特別定制的設備的優勢。這也可以理解為，設計一個解謎程序，讓現有的普通電腦成為最廉價和最有效率的解謎運算設備。但這在現實中不可能，畢竟所有的通用電腦的中央處理器裡已經針對一些特殊目的進行了優化。並不是所有的電腦都有相同的優化配置，並且它們隨著時代而改變。比如，過去的10年中，英特爾（Intel）和AMD在芯片裡加入特殊指令（通常叫作「增加硬件支持」）來更加有效地計算高級加密標準（Advanced Encryption Standard，簡稱AES）的區塊密碼。所以有些電腦在挖礦這個事情上總是會比其他電腦更加低效。另外，很難想像設計一個挖礦解密程序，而這些程序是依賴普通個人電腦諸如音響或顯示器這些特性的，所以去除了那些通用特性的具有特殊目的的設備，很可能會更有效率，並且成本更低。
更加實際地說，我們有一個適中的目標：設計一個解謎程序，盡可能地減少最有效率的定制運算設備與通用電腦之間的效率差距。ASIC還是會不可避免地成為更加有效的挖礦機，但我們至少可以將其運算效能限制在一定範圍內，從而讓個人用戶使用他們已有的通用電腦來挖礦仍具備一定的經濟效應。
剛性內存解謎
大多數被設計成反ASIC的解謎程序中，最普遍被應用的叫作剛性內存解謎（memory-hard puzzles）——解謎需要大量的內存來計算，而不是靠大量的CPU時間。一個類似但又不一樣的概念是內存限制解謎（memory-bound puzzles），花在讀取內存上的時間，佔據了這種程序大部分的計算時間。一個解謎可以是剛性內存類而不是內存限制類，或是內存限制類而不是剛性內存類，或是二者兼而有之。一個微妙但重要的區別在於，雖然CPU的速度是計算時間的瓶頸，但平行運算大量解謎的成本，還是被內存的成本所左右，或者反之亦然。通常對於運算類的解謎程序，我們要做到剛性內存和內存限制，就需要保證在運算過程中大量的內存被要求使用，使之成為一個限制性因素。
為什麼剛性內存解謎或內存限制解謎可以反ASIC？因為用來計算哈希函數的邏輯運算只佔了CPU裡的一小部分，意思是在比特幣的解謎計算裡，ASIC不需要執行一些不必要的功能，而只需要執行計算哈希函數的相關功能，所以佔了很大優勢。另外一個相關因素是，不同的內存性能上的差異（和單位性能的成本）比不同處理器之間運算速度上的差異要小很多，所以，如果我們設計了一個剛性內存類的解謎，計算時需要相對簡單的算力但需要大量的內存，這就意味著，解密成本的上升速率將會像內存成本提升速率那樣，在一個相對低一些的水平。[1]
SHA-256已經被認定為不是剛性內存解謎算法。它只需要一個小小的256位模塊，可以很容易地被放進CPU的註冊機裡。但設計一個剛性內存類的工作量證明解謎不是一件太難的事。
Scrypt
現在最受歡迎的剛性內存解謎叫作Scrypt[2]，被第二大加密數字貨幣萊特幣以及其他加密數字貨幣所用。
Scrypt是一個剛性內存的哈希函數，最早是為了加密密碼而不容易被暴力破解（比如，反覆試錯破解），所以挖礦解謎與比特幣用的「不完全哈希函數原像解謎」是一樣的，只不過用Scrypt取代了SHA-256。
Scrypt在比特幣被發明出來之前就已經存在，而且它是用來加密個人密碼，這一點讓我們對它的安全性有一定的信心。密碼的哈希函數化其實與反ASIC有著相似的目的。出於安全性考慮，我們期望，一個有著定制化設備的攻擊者不能夠比使用一般電腦或者服務器的用戶更快地計算密碼的函數值。
Scrypt基本上有兩個步驟：第一個步驟是在用隨機數據填充隨機存取存儲器（Random Acess Memory，簡稱RAM）裡面的緩存空間；第二步是從這塊內存區域裡虛擬隨機地讀取（或者更新）數據，同時要求整個緩存都存儲在RAM裡面。
圖8.1 Scrypt虛擬代碼
圖8.1展示了一段Scrypt的偽代碼(pseudocode)來體現核心的計算原則，但我們也省略了一些細節——在實際中，Scrypt使用更大一點的數據塊，然後用來充滿緩存區的算法略微複雜一點。
為了理解為什麼Scrypt是剛性內存類的，我們先想像一下如果我們要計算同樣的值，但不用緩存區V( 參見圖8.1)。這當然也是可行的——但在第9行代碼裡，我們需要重新動態地計算值V[j]，這需要進行j次的SHA-256的迭代運算。因為j的值在每次迭代循環裡會從0和N-1中虛擬隨機地選擇，因此這平均需要N/2次SHA-256計算。這意味著計算整個函數需要N×N/2=N2/2個SHA-256計算，但是如果使用一個緩存的話，只需要進行2N次運算。因此，緩存的使用將Scrypt的時間複雜度從O(N2)轉換成O(n)。這樣一來，只要簡單地選一個足夠大的N值使得O(N2)的計算變得足夠慢，以此確保使用內存是更快的選擇。
在時間與內存之間的權衡
如果沒有一個較大的內存緩存，計算Scrypt會變得很慢，但是用較少的內存來增加相對較少的計算還是可能的。假設我們使用一個大小約N/2的緩存（而不是N的大小），現在，我們只在j是偶數的情況儲存V[j]的值，丟掉那些j是奇數的值。而在第二次循環裡，一半的情況下j為奇數的值將會被選到，但這種情況還是很容易被計算的。我們只需要簡單地計算SHA-256(V[j-1])，因為V[j-1]在我們的緩存裡。[3]在一半的時間內會產生這種情況，所以它增加了N/2個額外的SHA-256計算。
因此，對內存要求量的減半隻會增加1/4的SHA-256計算量（從2N到5N/2）。總體來說，我們可以儲存緩存區域V裡的每個k排數據，即使用N/k的內存和計算（k+3）N/2次的SHA-256迭代計算。在這個限制下，如果我們設定k=N，我們就回到先前運算時間為O(N2)的計算。這些數字不一定非常精確地適用於Scrypt算法本身，但是漸近預測的方式確實是適用的。
除此之外，還有其他的設計可以弱化用時間來換取內存的能力。舉例來說，如果一個緩存持續地在第二次循環中被更新，它可以讓時間與內存之間的互換不是那麼有效，因為這些更新必須被儲存在內存中。
校驗成本
Scrypt的另一個局限性是，它需要用與計算所用的同樣大小的內存來做校驗。為了讓內存剛性有意義，N需要變得比較大。這意味著一個Scrypt的計算要比一個SHA-256的迭代計算（在比特幣裡只需要一個SHA-256計算就可以校驗）昂貴許多倍。
這會產生負面的結果，因為在網絡裡的每個用戶必須重複這個計算來檢查每一個新發現的區塊是否有效。這會減緩新區塊傳播和被認可的速度，從而增加了分叉攻擊[4]的風險。它還要求每個客戶端（即使是輕量級的SPV客戶端）擁有足夠的內存來有效地進行函數計算。這樣一來，實際上在加密數字貨幣中能夠被Scrypt用到的內存N是有限的。
一直到最近我們都不明確，是否有可能設計一個挖礦解謎程序在計算上是剛性內存類的，又可以很快地（不需要大量內存）進行校驗。這個特性對密碼進行哈希運算沒有多大作用，在用於加密數字貨幣之前，這是Scrypt算法的主要用途。
在2014年，一個叫作杜鵑鳥週期的新解謎算法被約翰·特龍普（John Tromp）所提出（起這個名字是因為這個算法的特性與杜鵑鳥的特性類似，杜占雀巢）。杜鵑鳥週期算法，是從杜鵑鳥哈希表所衍生的一張圖中尋找週期的難度而設定的，杜鵑鳥哈希表這種數據結構在2001年才被首次提出。除了建立起一個很大的哈希表之外，沒有其他已知的方法來計算這個週期，結果卻可以通過發現一個週期（相對小的）來簡單地驗證。
這個算法可能會讓剛性內存或是內存限制類的證明工作在比特幣共識裡變得更加實用。可惜的是，這個函數無法在數學上證明，如果它不用內存的話就不能被有效地計算。通常，一個新的密碼學算法看起來都是安全的，但是社區會對它持有保留意見，直到它存在了多年而沒有被破解過。因為這個緣故，並且因為它也是最近才被發明的，當前杜鵑鳥週期算法還沒有被任何加密數字貨幣所採用。
實際應用中的Scrypt
Scrypt被許多種加密數字貨幣所使用，包括萊特幣在內的幾種熱門幣，結果好壞參半。針對萊特幣Scrypt算法參數的ASIC已經存在（然後被其他幾種另類幣所複製）。令人驚訝的是，相較於大眾電腦，這些ASIC在算力上的提高比起SHA-256相對普通電腦的提高，至少旗鼓相當甚至要更大！所以，Scrypt最終還是無法反ASIC，至少在萊特幣上是如此。萊特幣的設計者起初宣稱反ASIC是萊特幣的一大優勢。但現在他們已經收回了這個說法。
這可能是萊特幣所用的數值N（內存使用參數）比較低所造成的，它只要求128KB就可以進行計算（如果使用時間內存互換的模式，可能所需要的內存更低，這也被普遍用於GPU以獲得更快的緩存）。低數值N使設計一個不需要複雜的內存存儲總線的輕量級挖礦ASIC變得很容易，通常這種複雜的總線是讀取十億字節（Gigabytes）級別的隨機存取存儲器所需要的，而這些通用電腦都具備。萊特幣的開發者沒有選擇一個比較高的內存參數（這會使ASIC更加難以設計），因為他們認為高內存參數所導致的高成本的校驗過程是不太現實的。
其他抵抗ASIC的方法
請回憶一下，我們的初衷是想讓可以大幅度提升計算性能的ASIC的開發變得困難。剛性內存解謎只是其中一個方法，還有其他方法。
遺憾的是，其他的方法都不是很科學，並且沒有作為剛性內存函數而被設計過或者攻擊過。最有名的一個叫作X11，其實就是把11個不同的哈希函數結合在一起，被一個叫作「黑暗幣」(Dark Coin)的另類幣所用（後面這個另類幣改名叫DASH），在DASH之後也被其他一些另類幣所使用。X11的目的是使設計一個有效的ASIC變得十分複雜，因為所有的11個函數的計算模塊都要在芯片上被實施。但這其實對硬件設計者來說，也不過是一個小小的不方便而已。如果有一個針對X11的ASIC誕生，那麼馬上會廢棄掉X11的CPU和GPU挖礦。
X11的哈希函數出自何處？
從2007年至2012年，美國國家標準委員會組織了一個競賽，這個競賽選取新的哈希函數家族來作為SHA-3的標準，大量包含了設計文檔和源代碼的哈希函數作為候選方案被提交。雖然有很多候選方案在競賽中被證實並不符合密碼學安全規範，但其中有24個哈希函數經受住了所有已知的密碼學攻擊，X11選擇了其中的11種，包括獲得最終勝利的Keccak[5]
另外被提出但還沒有被實施的一個方法是使用一個移動的目標值來作為挖礦解謎。也就是說，解謎算法本身就會變化，就像比特幣裡的難度會週期性地改變一樣。在理想的狀態下，為上一個解謎算法而被優化過的挖礦硬件，對下一個解謎算法不再適用。我們不是很清楚要多久改變一次解謎算法，才能達到我們需要的安全要求。如果這是由另類幣的開發者所決定的，這可能就變成了一種不可接受的中心化來源。比如，開發者可以根據他們已經開發出來的一種硬件（或者只是優化過的FPGA），去設計一個相對應新的解謎算法，他們自然就有了針對這個新算法的早期優勢。
或許這些解密算法的順序能夠被自動生成，但這看上去也很難。一個想法是選擇一大堆哈希函數（比如24個沒有被攻破的基於SHA-3的算法），然後每個用上6個月到一年，在這麼短的週期裡很難開發新的硬件。當然如果這個順序安排被事先知道，相應的硬件設計就可以按照函數使用的時間表來進行。
ASIC的蜜月
目前市面上還沒有針對X11的ASIC面世，即便都清楚這種芯片的生產是可能的，這種現象顯示了可能很有用的規律。因為適用X11算法的另類幣的市值都不高，簡單來說，還沒有足夠的市場價值吸引人去設計和生產針對X11的ASIC。一般來說，設計ASIC的前期投入都很高（不管是時間還是資金），同時生產單個硬件的利潤相對來說比較低。因此，對於新的還沒有被證實的加密數字貨幣，是不值得去投資研發針對性的ASIC，因為在新的硬件設備可用之前這個貨幣就可能失敗了。即使有一個明顯的市場需求，也會有硬件研發生產到出貨的延遲。第一批比特幣的ASIC從最初設計到最終出貨花了近一年時間，這在硬件行業裡已經算是很快了。
正因為如此，任何使用新的挖礦解謎算法的另類幣都會經歷一個ASIC蜜月期，在這段時間內，用GPU和FGPA挖礦(或許CPU挖掘)的利潤會比較高。對於永久阻止ASIC的浪潮不太可能，但是吸引個人參與挖礦（並且因此而獲得新幣）的做法，在新幣還處於步步為營的階段，還是有價值的。
對於抵抗ASIC的爭論
我們已經可以看到，從長遠來講做到反ASIC是不太可能的。但是也有一些其他意見，覺得從已經被證明的SHA-256解謎算法轉變為一個密碼學角度偏弱的新解謎算法，會存在一定的風險。甚者，SHA-256的挖礦ASIC已經接近當今硬件效能的極限了。這意味著，ASIC所帶來的指數型增長可能結束了，之後SHA-256挖礦也會因此給網絡帶來最大的穩定性。
最後，還有一種意見認為，在短期內反ASIC也不好。在第3章中，我們曾探討過即使一個擁有全網51%算力的礦工，他如若嘗試做出很多類型的攻擊，也並不理性。因為這樣一來會使幣值匯率崩潰，使得礦工在挖礦設備上的巨額投資大幅減值，他通過挖掘賺來的比特幣的價值也會大幅下降。
對於一個高度反ASIC的解謎算法，這個安全性的說辭可能會站不住腳。舉例來說，一個攻擊者可能會暫時租用巨大算力〔比如像亞馬遜（Amazon）的EC2服務〕，用它來攻擊，然後不會承受任何財務上的損失，因為他們不需要在攻擊後繼續租用這個服務。相比較而言，對於一個「對ASIC友好」的解謎算法，攻擊者就不得不控制一大堆只可以用作加密貨幣挖礦的ASIC。這樣的一個攻擊者其實應該是看好比特幣未來的發展，做了一個最大限度的投資。按照這個邏輯進行推理的話，為了最大限度地保護安全，或許挖礦解謎算法應該被設計成不僅僅要讓有效的挖礦ASIC被設計生產出來，更應該讓那些ASIC除了用於加密貨幣的解謎運算之外，沒有任何其他用途！
[1] 也就是花費更多去提高內存的效能，並不能以相同比例去提高解謎的效能。——譯者注
[2] Scrypt是由著名的FreeBSD黑客Colin Percival為他的備份服務Tarsnap開發的。Scrypt不僅計算所需時間長，而且佔用內存也多，使得並行計算多個摘要異常困難，因此利用rainbow table進行暴力攻擊更加困難。Scrypt沒有在生產環境中大規模應用，並且缺乏仔細的審察和廣泛的函數庫支持。——譯者注
[3] j是奇數時，減1為偶數，我們存的是有偶數的值的。——譯者注
[4] 有關分叉攻擊的內容，可以參見本書第5章。——譯者注
[5] Keccak算法為SHA-3的一種加密標準。——譯者注。