2017.W26 - 雜湊函數 以數位貨幣為例
> 供給來自於需求
## 前言 ##
最近數位(虛擬)貨幣正夯 根據 Bitcoin[0] 的論文中提到
BTC 的若干要求中提到的 PoW (Proof-of-Word)
正是例計算一個 SHA 256 得到的 Hash 中 開頭若干為 0 所需要花費的勞力
但是有辦法不(那麼)勞而獲嗎？
## 內容 ##
雜湊函數 (Hash Function) 是一種數學函數 用來將一個大群集對應到小群集的方式
通常 Hash Function 會將輸入對應到一個固定長度的雜湊值 (Hash)
例如廣為人知的 MD5 就是將任意值雜湊為一個固定 128-bit 的 Hash
一個好的 Hash Function 需要滿足以下條件：
1. 防止碰撞 (collision)
2. 均勻 (uniformity)
3. 不可逆轉
4. 雪崩效應 (avalanche effect)[1]
這分別代表著給予一個 Hash 值 你很困難的找到他的原始輸入值
稍微改變輸入值也會得到差異很大的結果
舉一個不好的 Hash Function - H(x) = (x + 3) % 13 當做例子
假設給予一個 Hash 值 - 5 可以很快的反推出來原始的輸入值為 2 (違反 3.)
或者是輸入 4、5 會得到相似的結果 7、8 (違反 4.)
在 BTC 的例子中[2] 可以看到利用區塊[3]的開頭當作是 SHA 256 輸入值的一部分 (nonce)
接著從 0 到 MAX_NONCE 開始暴力嘗試 直到找到滿足的條件 (condition hash)
我們已經知道 MD5 可以有效的找到一個碰撞[4]
因此如果有一個虛擬貨幣 使用 MD5 來當作是主要的雜湊演算法
這樣忠厚老實的礦工就會用暴力搜尋的方式找到下一個區塊
而讀過演算法奸巧礦工 就可以用各種優化的演算法來找到下一個區塊
因此目前的虛擬貨幣 都選用沒有已知問題的雜湊演算法
另一種現代遇到的 Hash 問題就是不希望算出 hash 算得太快
在一開始 hash 設計的初衷 只需要逆轉很困難即可
但是在虛擬貨幣或資訊安全的情境下 算 hash 算得太快反而不是一個優點
原因在於如果暴力計算 hash 成本低廉 (運算速度快) 那暴力破解就不會是問題了
假設使用 RC4-40 當作例子 - 在暴力破解的狀況下需要嘗試 2 的 40 次方 ~= 10^12
如果用
一秒算出 1 個 hash 值 則需要花費 34865 年
一秒算出 1G 個 hash 值 則需要花費 17 分鐘
但如果用硬體的方式加速運算的 可能就會有更加顯著的成長
像這邊文章提到用硬體實作的 SHA 256 會有 4200% 的加速 [6]
[0]: https://bitcoin.org/bitcoin.pdf
[1]: https://en.wikipedia.org/wiki/Avalanche_effect
[2]: https://github.com/jgarzik/pyminer/blob/master/pyminer.py
[3]: https://en.wikipedia.org/wiki/Blockchain
[4]: http://www.mscs.dal.ca/~selinger/md5collision/
[5]: https://github.com/secworks/sha256
[6]: http://www.electronicsfaq.com/2014/01/sha256-on-tiva-c-series-of-cotex-m4.html