基於FPGA上實現記憶體受限之Autolykos演算法

Abstract

本論文的重點在於深入探討Ergo虛擬貨幣的工作證明演算法Autolykos。其中工作證明(Proof of Work)是區塊鏈中廣為使用的一種共識機制，人們可透過解決複雜的數學難題來獲得加密貨幣的獎勵，目前普遍使用GPU、FPGA、ASIC來尋找更高的算力卻又更省能源的方法。 傳統的PoW演算法，例如比特幣的SHA-256，是compute hard的算法，這意味著它主要受到處理器速度的限制。這種設計使得那些有能力購買和運營能源消耗大且昂貴的特殊硬體的礦工（例如ASIC）具有顯著的優勢。這導致了大規模礦工和礦場的出現，並引發了中心化和公平性的問題，因為個人和小規模礦工很難與這些大型勢力競爭。 相比之下，記憶體束縛的PoW演算法是設計來限制這種優勢的。內存受限演算法的工作需求大部分基於記憶體，因此，它鼓勵礦工使用具有大量可用記憶體的硬體，而這種硬體通常比高速處理器更便宜、更容易獲得。 此次研究之Autolykos算法為memory bound演算法。其特性為會對內存進行大量讀取與寫入，故整體計算速度會受限於記憶體頻寬與記憶體容量大小。而與乙太坊所使用的Ethash算法相比，Autolykos提高了計算資源的使用量，使ASIC和FPGA所需面積大為增加，以此提高兩者的成本。並且提高記憶體讀取在整體計算的比例，因此相較於Ethash又更強調memory hard的特性，如何有效運用記憶體頻寬成為提高算力最大的討論點。 本論文將在Xilinx的VU35P FPGA晶片上做硬體實現，論文中將詳細描述軟體架構、舊版硬體架構及其瓶頸，再提出一種全新的架構以大幅超越同記憶體頻寬的GPU算力，並可透過調整HBM reference clock至130MHz以上，提升記憶體頻寬上限，最終算力達到266.4MHz/s，為高階GPU算力的1.5倍 。

This paper focuses on an in-depth exploration of the Proof of Work (PoW) algorithm, Autolykos, used in the Ergo cryptocurrency. PoW is a widely used consensus mechanism in blockchain, where individuals can earn rewards in cryptocurrency by solving complex mathematical problems. Currently, general-purpose computing devices like GPUs, specific hardware like FPGAs, and specialized ASICs are used to find more powerful yet energy-efficient mining methods. Traditional PoW algorithms, such as Bitcoin's SHA-256, are compute-bound, meaning they are mainly limited by the speed of the processor. This design gives miners who can afford to purchase and operate power-intensive and expensive specialized hardware (such as ASICs) a significant advantage. This has led to the emergence of large-scale miners and mining farms, raising issues of centralization and fairness, as individual and small-scale miners find it hard to compete with these large entities. In contrast, memory-bound PoW algorithms are designed to curb this advantage. The workload requirements of memory-bound algorithms are primarily based on memory, thus encouraging miners to use hardware with a large amount of available memory, which is generally cheaper and more accessible than high-speed processors. The Autolykos algorithm investigated in this study is memory-bound. Its characteristic feature is that it involves a large number of memory read and write operations, so the overall calculation speed is limited by memory bandwidth and memory size. Compared to Ethereum's Ethash algorithm, Autolykos increases the use of computing resources, making the area required by ASICs and FPGAs significantly larger, thus raising their cost. Furthermore, it increases the proportion of memory read operations in the overall calculation, emphasizing the memory-hard feature even more than Ethash. How to effectively utilize memory bandwidth becomes the key discussion point for enhancing the hash rate. This paper presents a hardware implementation on the Xilinx VU35P FPGA chip. It will detail the software architecture, the old hardware architecture, and its bottlenecks, and then propose a novel architecture to significantly surpass the hash rate of a GPU with the same memory bandwidth. By adjusting the HBM reference clock to above 130MHz, the upper limit of memory bandwidth can be improved, with the final computational power reaching 266.4MH/s, which is 1.5 times that of high-end GPUs.