Bitcoin Core 0.7ms 的代价
细说 CVE-2018–17144的来龙去脉
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
图文好读 Medium 版 : https://tinyurl.com/y7l8gf53
前言
Bitcoin Core 在 2018/09/18 时紧急发布了新版本 0.16.3，并在其中提到：
We highly recommend users of all affected versions
immediately upgrade to 0.16.3.(Ref#1)
区块链圈无不掀起一波讨论，当然各式媒体也相继报导；最耸动的莫过于这句话：
康奈尔大学教授 EminGünSirer 表示，估计只需不到 8 万美元的成本
（12.5 枚比特币）就能瘫痪整条比特币区块链。(Ref#2)
事情真有这么可怕？瘫痪整条链？只要八万美元？
秉持着工程师精神，追根究柢找了一些资料终于了解整件事情的前因后果，
就让我娓娓道来。
=============
前因
Bitcoin Core 身为元老级的 bitcoin 用户端
（Bitcoin 的其余分支也师承此 source code），算得上是 open source 界经典范例。
拥有五百个以上的全球贡献者时时都为 Bitcoin Core 上 pull request，
有的为了修正 bug，有的为了提升效能。
那现在我们就要回到 2016/11 的 pull request #9049 (Ref#3)：
Benchmark results indicate this saves about
0.5–0.7ms during CheckBlock.
这个 PR 提高了 CheckBlock 的效能，主要是做了以下的 change：
// Check for duplicate inputs — note that this check is slow
so we skip it in CheckBlock
https://i.imgur.com/T2e1MtP.png
(Code Snippet for PR#9049)
简单来说，矿工们会无所不用其极地节省各式计算的时间，
以期在挖矿时确保能挖的比别人快。所以这个 PR 的用意在于，
想要在 CheckBlock 时略过检查于 transaction 中是否有两个相同的 input，
以节省时间。
（检查的方式算是蛮暴力的，利用 std::set::count 与 std::set::insert 来检查
是否有重复，时间复杂度为 O(n log n)）
其实，有没有相同的 input 是一个非常重要的检查，
意义在于避免双花（double-spending）；当初此 PR 作者群认为，
每个 transaction 在上到 mempool 的时候，就应该做过检查了，
所以当 block 上链后，照理说事后应不需多花这个计算时间重复检验。
=============
后果
But，就是这个 but ，在将近两年后的 2018/09/17 ，
这段 comment 被一位 Bitcoin Cash/Bitcoin Unlimited 的开发者 Awemany
于开发时无意发现(Ref#4)，于是做了一些实验，
制造出具有相同的 input 的 transaction，
来测试 Bitcoin ABC (Bitcoin Cash 的 client)，居然遇到了 assert()，
程式直接 crash ，当他转而测试 Bitcoin Core 也得到相同结果
（这并不意外，Bitcoin 子子孙孙的原始程式大多都从 Bitcoin Core fork 出来），
这时候 Awemany 就知道不太妙了，开始做后续通报的动作。
https://i.imgur.com/SOoc2XI.jpg
(bitcoin/src/validation.cpp code snippet)
Assertion failure point 在CheckBlock()之后的链结区块ConnectBlock()。
而其中之 UpdateCoin() 会检查 input 是否有被重复 spend，若有则 assert()。
Bitcoin Core 团队迅速的于24小时内提出修正并释出新版本(Ref#5)。
Fix 非常简单，就是把原本于CheckBlock() 的duplicate inputs重新打开…(#Ref6)
=============
这件事情为什么是个区块链圈大新闻，这边归纳为以下几点：
1. 影响范围广大：许多区块链实作受到影响，尤其是从 Bitcoin 分叉出来的，
除了上述的 Bitcoin Cash、Bitcoin Unlimited 外，Litecoin 也受其影响。
2. 可能引发严重后果：普通程式异常关闭虽然是我们生活中的日常，
但在区块链的世界中却是一件大事。矿工利用程式挖矿，以建立共识并确认交易；
当程式异常关闭（而且是一直关闭），就不会有矿工可以帮交易做确认，
整条区块链可以算是瘫痪；
更严重的是，只要骇客成功算出一个包含有重复 input 的区块放到链上，
会成为一种阻断服务攻击（DoS），可以大大的降低整体算力，
使 51% 攻击更容易成功，进而修改区块链上的资料。
3. 修复是一个缓慢的过程：P2P 世界中，成千上万的节点需要被更新，
这不是像按一个按钮就可以完成的。截至 9/24 修正释出的一个礼拜后，
Bitcoin 全网仍有 87% 的节点受此CVE 影响(Ref#7)。（真的是87%….）
=============
反思
理解了来龙去脉，回到最前言的部分，
到现在为止我们已经知道了为什么大家认为这是一个（目前）史上最严重的
Bitcoin bug，会使整条链瘫痪。
但让我再次引用 INSIDE 文章的某一段文字：
康奈尔大学教授 EminGünSirer 表示，
估计只需不到 8 万美元的成本（12.5 枚比特币）就能瘫痪整条比特币区块链。(Ref#2)
那个 8 万美元的成本（12.5 枚比特币）到底是怎么算出来，
一直困扰着我。查阅了 Bitcoin Core 0.16.3 的 release note 后发现：
Such blocks are invalid, so they can only be created by a miner willing to
sacrifice their allowed income for creating a block of at least 12.5 BTC
(about $80,000 USD as of this writing)
原来国内外媒体一直引用的 8 万美元的成本（12.5 枚比特币）
就可以瘫痪 Bitcoin 的这句话是有一些误解的。
原意其实是指：攻击者先必须真正的算出合法的 hash，
才可将不合法的交易包入区块中，进而达成攻击。
反过来说，攻击者等于是放弃了这 12.5 枚比特币挖矿奖励
（时下汇率换算约八万美元），来达成攻击，
因为包含了不合法的交易之区块绝对不会被其他矿工承认。
所以真正要成功完成攻击，成本绝对是远高于所谓的 8 万美元。
（cryptoglobe 文章中提到，www.crypto51.app 已经成功预估出于
Bitcoin Private (BTCP) 网络上，只需 $122 美金即可达成 51% 攻击(Ref#8)，
不过目前还找不到相关佐证文件）
=============
另一个反思则是，区块链世界强调去中心化，但吸引众多使用者的交易所、
共用的智能合约与区块链全网使用的相同程式，再再的打破去中心化的概念，
只要任何一点被攻破，都是重大的损失，这样还算是真正的去中心化吗？
=============
Note : 若有错误，欢迎指正；也欢迎讨论与指教，谢谢。
References :
1. https://bitcoincore.org/en/2018/09/18/release-0.16.3/
2. https://tinyurl.com/ycg2cmlm
3. https://github.com/bitcoin/bitcoin/pull/9049
4. https://medium.com/@awemany/600-microseconds-b70f87b0b2a6
5. https://bitcoincore.org/en/2018/09/20/notice/
6. https://github.com/bitcoin/bitcoin/pull/14247
7. https://twitter.com/LukeDashjr/status/1044224230114627586
8. https://tinyurl.com/ycq5gzjb