漫談 Bitcoin (BTC) 和 Litecoin (LTC)

很久沒有寫文章，最近因為媒體開始炒熱 BitCoin，又開始拿來看一下。之前大概有 Survey 過 BitCoin 的制度和原理，不過那時候大概是只有少數或理論上的交易，也沒像現在的天價美金匯率一樣，所以幾乎沒什麼人聞問。

最近 BitCoin 開始紅起來，最主要大概是有實際交易紀錄和媒體的報導。再來就是，可以靠挖礦賺錢而不是勞力，現實生活上，除了那些有錢人靠資本利得賺錢外，所有的人不管是教師、公務員、科技業，都是靠勞力換取金錢。而 BitCoin 只要靠著適當的硬體，就可以產出金錢。當然現在的 Difficulty 已經是天文數字，也就是靠 CPU/GPU 已經無法在能源效率情況下，賺取相當的回報。而 ASIC 適當的挖礦機，也幾乎是天價的價格，甚至都已經排隊排到不知道多久了，等你拿到機器，可能 Difficulty 已經成長到你的機器無法負擔的情況。

來說說 BitCoin 的真實價格，其實這種虛擬的東西，沒有一個實體讓你估價。但是就像硬幣鈔票一樣，他的金屬或是紙的價格是遠低於面額，而這個貨幣的價格則是由發行單位和銀行所承認。萬一他們不承認，你所擁有的東西不就是金屬跟一張紙而已嗎? 這時跟你心目中虛擬的貨幣其實大概是一樣的感覺，唯一不同的是金屬跟紙你還可以拿去回收換等值物品。

接著來說一下這種網路虛擬硬幣，為什麼要動用一堆網路上的電腦資源來運算? 以BitCoin來說，他需要做兩次SHA的運算。而計算的內容就是把版本、前次交易的hash value、merkle、時間、困難度、以及一個任意限制的 32-bit 數字去做兩次 SHA-256。然後限定要小於某個 target value。請參考 Block hashing algorithm。因此，電腦就必須要列舉 2^32 次方那麼多的數字，組成完整的 block 然後去計算兩次 SHA-256 後的 hash value。然後再跟 target value 比較，小於的話就是找出 nonce，該次 SHA-256 後兩次的 256-bit 就是該 block 的 hash value。電腦本身列舉 2^32 之外，還要計算 SHA-256 兩次，如果在 2^32 找不到小於 target value 的值，那麼該 block 的 merkle 就會被累加，然後 nonce 再次重來。

那麼 CPU 做這樣的計算，到底速度怎樣? 以 Mining hardware comparison 的表來說，i3-i7 的數據大概是個位數到兩位數而已。單位是 MH/s，全名是 Mega Hashrate per Second。也就是每秒可以計算百萬次的 Hash。而 2^32 是 4G，因此如果 CPU 是 4MH/s，也就是 4G/4M = 1024 也就是要花上 1024 秒，或是18分鐘才能列舉完全部的 nonce，但是運氣好的話可能很快就遇到某一小的 nonce 可以符合最後 hash value < target value。而網路上挖礦的礦池，就是把這些 block chain 的每個 block 分給大家去做，然後每個計算執行序只計算某個範圍的 nonce，如果算出一個合法的，告訴礦池之後她會 accept 或 reject (可能是亂算或是計算錯誤)。因此就是 divide & conquer 集合大家來平行運算。

而為什麼用 CPU 算會這麼慢也不推薦，因為 CPU 的速度並不快，核心數也不多，CPU通常要動用一堆指令，才能完成 SHA256 的運算。舉個簡單的例子 SHA-256 有很多移位的動作，如果是用專門電路或是 FPGA/ASIC，那其實根本不用運算，因為硬體線路就是如此連接給下一階的計算，例如本來是 {a,b,c,d,e,f,g,h} 每個代表 1bit，那麼移位只是硬體線路的連接而已，例如給下一個輸入端連線是 {b,c,d,e,f,g,h,a}。但是 CPU 要做一個指令才能完成移位運算，況且又不只有一個要做移位運算，而且又不是只做一次。而 SHA 本身運算除移位外，還有加法、XOR 等等。除了一些前後置的運算，本身核心要做 64 次。因此在電路設計上，FPGA 或是 ASIC 可以透過 pipeline 方式，提高平行運算的 throughput。所以，在速度上，比 generic CPU 還快上幾千幾百萬倍。

另外一種新的虛擬貨幣稱為 Litecoin。基本上本身也是參考 BitCoin，幾乎也是類似的機制，差別主要在於演算法改為 scrypt，貨幣發行量是 BitCoin 四倍。選用 scrypt 的目的，是想要避免使用不同硬體產生速度上的巨大 hashrate 差異，例如現在 BitCoin 就幾乎是 ASIC 天下，用 CPU/GPU/FPGA 基本上已經無利可圖，且 ASIC 的價格也很可觀。scrypt 基本上存在 Time-Memory trade-off，也就是計算 hash 值會需要 bitstream 所產生的 pseudo random number 來做 random memory access。因此基本上需要較大的記憶體空間，就不像 SHA-256 只要做些移位、加法、XOR 等運算，再餵給下一級迴圈即可。因此，scrypt 運算需要有 control logic 和 memory element。所以 Hashrate 上來說，LiteCoin 會比 BitCoin 慢上千倍以上。
這演算法在 FPGA 或是 ASIC 上並不太可行，因為 on-chip SRAM 非常貴，也沒有 FPGA 配備有這麼大量記憶體，若是 SDRAM，那就得透過 memory controller 去存取外部速度較慢的記憶體。這樣使得 FPGA 或是 ASIC 的成本不是要增加，就是要靠類似 MCU/CPU 和記憶體來做運算。要是 FPGA/ASIC 上有太多平行運算核心，相對應記憶體量也要等比增加，這使得要生產這樣的 ASIC 成本不低。要是做成 controller + SDRAM，這就不是現在的 CPU + SDRAM? 因此產生特定硬體來達到超快的 hash rate 幾乎是不可能。但是這個假設還有個錯誤的地方，也就是如果我用大量平行的架構，類似 GPU，那還是可以達到非常高的 hash rate。現在 GPU 上基本上就有大量的運算單元，再加上非常高速幾乎是核心頻率 1/2 或相等的記憶體時脈。所以，透過 CUDA 或是 OpenCL，即便每個核心速度並不高，也許只有 5KH/s，但是假設上面有上百個運算單元，那平行去計算就相當於 500KH/s，再加上 GPU 可以透過 PCI-e 串接，因此就好像有一大堆小電腦在做平行運算，而 CPU 功能就是下載，分工，驗證和回覆計算資料。