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