[Coin] Bitcoin Core 0.7ms 的代價

[GameDemon ()]

                       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

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.117.189
※ 文章網址: https://www.ptt.cc/bbs/DigiCurrency/M.1538195587.A.998.html
推 www10177: 寫的還滿清楚的，推
推 DarkerDuck: 所以我向來都認為Bitcoin的金流protocol應該簡單
→ DarkerDuck: 甚至能有多個不同的node implementation
→ DarkerDuck: 那就比較不會有單個implementation bug失效的問題
→ DarkerDuck: 像這次的bug就是被Bitcoin Umlimited的開發者抓到
推 kugwa: 推～
推 vvind: 認真推
推 zhiping8: 推
推 DarkerDuck: 真正的攻擊成本當然是高於八萬美金
→ DarkerDuck: 除了12.5枚BTC還加上了算出區塊的電費以及設備折舊
→ DarkerDuck: 恐怖點在於BTC的挖礦節點幾乎只有一種implmentation
→ DarkerDuck: 攻擊過後可能挖礦節點全死光，剩下自己爽爽挖51%攻擊
推 SecretAres: 好文章該推
推 kugwa: https://i.imgur.com/OVf51ow.png
→ kugwa: https://i.imgur.com/Ubf16HE.png
→ kugwa: 0.15.0之後 CheckTransaction()從validation.cpp被移到
→ kugwa: consensus/tx_verify.cpp
→ kugwa: 難怪剛剛找validation.cpp找無
推 kugwa: 是說 點進去bitcoin的github的release頁
→ kugwa: https://github.com/bitcoin/bitcoin/releases
→ kugwa: 最近幾個release 比較舊的反而在比較上面
→ kugwa: 是否跟這個bug有關？
→ tcn1john: 除了可以讓程式crash, 能夠憑空產生bitcoin才是重點吧
→ kugwa: 應該沒有允許多產生BTC UpdateCoins那裡有檢查 會擋下來
→ kugwa: 只不過擋下來=直接讓程式死掉
→ DarkerDuck: 流通量不會增加，頂多可以讓你double spend
→ DarkerDuck: 但鏈要長的時候就會被reject掉
→ DarkerDuck: 0.14x 的完整節點會直接死給你看，其他版本可能會拒絕
→ kugwa: 不過我認為 就算有攻擊者弄出一個區塊 裡面帶有這種引用重
→ kugwa: 複input的交易
→ kugwa: 而且一時之間也成功進到區塊鏈了
→ tcn1john: 我是看到相關新聞@@ 像是發現bug的開發者說可以造成 in
→ tcn1john: flation http://goo.gl/16eCng
→ kugwa: 但之後當大家發現這個bug的時候 都能發現鏈上這個出問題的
→ kugwa: 區塊
→ kugwa: 所以應該也能達成共識 一致把區塊鏈轉回那個區塊之前
→ DarkerDuck: 那篇文章只有說有這個可能，但實際上double spend的
→ DarkerDuck: 檢查依照節點實作的不同，會被檢查不只一次
→ DarkerDuck: 新加入的節點一定會檢查double spend，所以inflation
→ DarkerDuck: 不會產生，但是可能還是有少數的特定節點實作通過
→ DarkerDuck: 那這樣就會造成chain split
→ DarkerDuck: Awemany就是在批評，避免雙花這種核心的功能竟然可以
推 whyever: 好文推
→ DarkerDuck: 靜悄悄地被省略拿掉，開啟了inflation的可能性
→ DarkerDuck: 想要攻擊的人可以故意不公布，找到真正增加流通量方法
→ kugwa: 請問現在的Bitcoin Core是誰在帶頭呀？
推 tcn1john: 感謝解說@@
→ DarkerDuck: https://en.bitcoin.it/wiki/Wladimir_van_der_Laan
→ DarkerDuck: https://github.com/laanwj
→ kugwa: 原來就是發release的人
→ GameDemon: 謝謝各位強者的補充 還沒機會回答問題 大家都解答完了
推 john371911: 推。
推 leftc: 技術文推
推 aabb927: 推
推 justben: 推～
推 camellala: 推專業文
推 EthereumPTT: 以太好像沒被波及到
→ kugwa: 以太不是直接fork比特幣ㄅ
→ kugwa: 以太的客戶端 最大宗的好像是用go寫 而且也有不只一種實作
→ kugwa: 用各種不同語言寫
→ DarkerDuck: 以太幣自己重底層重刻的，金流只是EVM的一個功能罷了
推 DarkerDuck:           從
推 Binance: 推 謝謝分享
推 Ayahuasca: 推認真解釋
推 ko88201: 專業給推