Bitcoin-NG: A Scalable Blockchain Protocol 進階計算機系統協會 Ittay Eyal, Adem Efe Gencer, Emin Gun Sirer, Robbert van Renesse Cornell University 13th USENIX Symposium on Networked Systems Design and Implementation(NSDI’16)

Outline Introduction Bitcoin-NG Metrics Evaluation Conclusion

The Blockchain Promise Byzantine fault-tolerant, decentralized Bank-to-bank settlements Cheap remittance Device-to-device payments (IoT) 今日的跨行結算仍是以一共識銀行作結算而不是BANK TO BANK 便宜的匯率

The Blockchain Promise Byzantine fault-tolerant, decentralized Bank-to-bank settlements Cheap remittance Device-to-device payments (IoT) Requires a bigger and faster boat 目前中本聰設計的blockchain是受限於一秒7個交易, 因為blockchain設計每個block只有1MB大且平均10分鐘才會驗證完一個block 平均，Visa 每秒處理 2000 個交易，而且 Visa 網絡的能力是每秒處理 5 萬 6 千個交易。 也就是要提升每秒交易量

Requires a bigger and faster boat Two ways: 1. Increasing block size improves throughput Result: Bigger blocks take longer to propagate in the network. 2. Reducing the block interval reduces latency Result: leads to instability where the system is in disagreement and the blockchain is subject to reorganization 如何提升每秒交易量呢 Take longer to propagate:  if it takes miners 1 minute on average to learn about new blocks Disagreement: 沒辦法好好驗證或驗證完全部 Reorganization: 因為交易速度太快會有forks要處理

Requires a bigger and faster boat Two ways: 1. Increasing block size improves throughput Result: Bigger blocks take longer to propagate in the network. 2. Reducing the block interval reduces latency Result: leads to instability where the system is in disagreement and the blockchain is subject to reorganization Don’t Work! 如何提升每秒交易量呢 Take longer to propagate:  if it takes miners 1 minute on average to learn about new blocks Disagreement: 沒辦法好好驗證或驗證完全部 Reorganization: 因為交易速度太快會有forks要處理

Requires a bigger and faster boat Two ways: 1. Increasing block size improves throughput Result: Bigger blocks take longer to propagate in the network. 2. Reducing the block interval reduces latency Result: leads to instability where the system is in disagreement and the blockchain is subject to reorganization Don’t Work! 如何提升每秒交易量呢 Take longer to propagate:  if it takes miners 1 minute on average to learn about new blocks Disagreement: 沒辦法好好驗證或驗證完全部 Reorganization: 因為交易速度太快會有forks要處理 Bitcoin-NG

Byzantine fault-tolerant Total Node: N Byzantine: B N >= 3B + 1 (strictly say: B < ¼ N) Make a consensus anyway Blockchain: PoW 拜占庭是東羅馬帝國首都, 地域寬廣, 守衛邊境的多個將軍(系統中的節點)需要通過信使來傳遞消息, 達成某些一致的決定, 但由於各個將軍中可能存在叛徒(系統中節點出錯), 這些叛徒會努力向不同將軍發送不同的消息, 試圖干擾一致性的達成, 解決這個問題的算法就叫做Byzantine fault-tolerant, 結論來說節點總數若為N , 叛變將軍數為F則當 N>=3F+1, 將軍們無論如何仍可達到一致性 Blockchain便是透過proof of work達成

Outline Introduction Bitcoin-NG Metrics Evaluation Conclusion

Bitcoin-NG : Model and Goal Total nodes: Byzantine nodes: Time: Mining power (compute power) of each node: Goal: Make Byzantine nodes be less than ¼ of the total compute power at any give time. 基本上是採用原本忠本聰的bitcoin blockchain model 以proof of work, 也就是hash出特定直後才能製造出新block 從Byzatine fault tolerance中得知作弊節點應該要小於所有節點數的1/4 否則系統會被attackers攻擊癱瘓 故此為其目標

Bitcoin-NG: Nakamoto Consensus (1) 作者對之前中本聰的論文實作的更加詳細 我們先看到這張圖 因為其實blockchain就是一個分散式系統, 所以他認為blockchain就是該系統中的一種複製狀態機, 而輸入該複製狀態機的東西就是右側的log, 也就是會複製到每個節點的blockchain , 而node輸入此狀態機後, 會得到新的blockchain if node加入了新的交易 也可能沒有變, 即沒有交易被納入

Bitcoin-NG: Nakamoto Consensus (2) Input = blockchain = log

Bitcoin-NG: Nakamoto Consensus (3) 而這裡是他定義的machine state

Bitcoin-NG: Nakamoto Consensus (4) 而這裡是他定義的machine state

Bitcoin-NG: Nakamoto Consensus (5) 而這裡是他定義的machine state

Bitcoin-NG: Nakamoto Consensus (6) 而這裡是他定義的machine state

Bitcoin-NG: Nakamoto Consensus (7) 若惡意節點的mining power和全部節點的比率<f 則最後造成blockchain更動中是惡意節點造成的的比率也應該要是<f 若是, 則blockchain是合法有效的

Bitcoin-NG: Nakamoto Consensus (8) FORK 忠本聰的blockchain系統會有fork的狀況發生 在第18篇中提到, 因為bitcoin平均10分鐘產生一個block, 而block的傳遞廣播給其他node會需要幾秒鐘, 故平均每60個block會有一個意外分叉 [18] DECKER, C., AND WATTENHOFER, R. Information propagation in the Bitcoin network. In IEEE P2P (Trento, Italy, 2013).

Bitcoin-NG: Nakamoto Consensus (9) FORK [18] DECKER, C., AND WATTENHOFER, R. Information propagation in the Bitcoin network. In IEEE P2P (Trento, Italy, 2013).

Bitcoin-NG: Nakamoto Consensus (10) Resolve forks: the protocol prescribes on which chain the miners should mine. Criterion: winning chain is the heaviest one that is, the one that required the most mining power to generate. All miners add blocks to the heaviest chain Branches and blocks outside the main chain are called pruned Transactions in pruned blocks are ignored, They can be placed in the main chain at any later time. the most mining power

Bitcoin-NG (1) • NG: New Generation • Latency is limited only by the propagation delay of the network • Maintaining the Bitcoin trust assumptions 也就是原本的10分鐘才產生一個blockchain不再構成long latency的因素

Bitcoin-NG (2) divides time into epochs introduces two types of blocks: key blocks for leader election microblocks that contain the ledger entries.

Bitcoin-NG (3) 在第18篇中提到, 因為bitcoin平均10分鐘產生一個block, 統計下來每60個block會有一個分叉

Bitcoin-NG (4) 拆到中間, 但是交易資訊沒有序列化

Bitcoin-NG (5) 所以就建立一個序列block來整合transacitons

Bitcoin-NG (6)

Bitcoin-NG (7) Key Blocks: (similar to Bitcoin’s normal Block) - No content - Leader election by PoW and in charge of mircoblock generating - Public key K - Fork, just as in Bitcoin, pick the branch with the most work 就像原本的normal block解出數學問題的人可以成為leader

Bitcoin-NG (8) Microblocks: - Only content (transaction) - Signed with k - generated by leader - microblocks do not affect the weight of the chain, as they do not contain proof of work

Bitcoin-NG (9)

Bitcoin-NG (10) Remuneration: - First, each key block entitles its generator a set amount (new mint) - Second, each ledger entry carries a fee.

Bitcoin-NG (11)

Bitcoin-NG (12) When a miner generates a key block, he may not have heard of all microblocks generated by the previous leader. Reason: - Propagation of Key block needs time - Microblocks can be generated cheaply and quickly by the leader cuz microblocks do not require mining. Result: Microblock forks

Bitcoin-NG (13) It is resolved once the key block propagates to that node. 即被加回新增出來的key block後面

Bitcoin-NG (13) It is resolved once the key block propagates to that node. Leader有可能趁著fork的時候將許多double spending的交易納入(即在原本的blcok中花該金幣, 分叉出來的block中又使用同一個金幣), 進而在下一個leader的時候併入之後的key block之後的microblock中 故當之後若有node發現這種狀況時, 便可以執行poison transaction 可以讓cheater得到的錢追溯性的被取消, 而下毒的node可以拿到報酬

Outline Introduction Bitcoin-NG Metrics Evaluation Conclusion

Metrics (1) Consensus Delay: defining how long back nodes have to look to find a point where they agree on the state. 介紹了幾個metrics來評斷blockchain的好壞 也就是達成同意的時間 他定義為後面的節點, 也就是不知道已達成同意的節點, 要過多久才會收到已達成同意而需要更新blockchain了

Metrics (2) Fairness: two ratios: (1) the ratio of transitions not coming from the largest miner with respect to all transitions (2) the ratio of mining power not owned by the largest miner with respect to all mining power. Fairness = (1) / (2) Optimally the fairness is 1.0 也就是最大miner造成的blockchain更動相對於所有miner造成blockchain更動的比例 應該要和她的mining power與所有power的比例一樣 也就是說有多少power應該就只能對blockchain造成多少影響, 這樣才是公平

Metrics (3) Mining Power Utilization: The mining power utilization is the ratio between the mining power that secures the system and the total mining power. the mining power an attacker has to outrun to obtain disproportionate control 介紹了幾個metrics來評斷blockchain的好壞 也就是達成同意的時間 他定義為後面的節點, 也就是不知道已達成同意的節點, 要過多久才會收到已達成同意而需要更新blockchain了

Metrics (4) Time to Prune Time to win 0.1234 是他們產生的時間 Time to Prune從一個node創出的Block到他發現main chain的時間稱之, 這段時間可以反映user要等多久才可以確信block已經轉移到另一個branch了 Time to win從創造出block直到對方創出最後一個衝突block, 代表隊方已經察覺他是即將被prune掉的節點了, 所以就win

Outline Introduction Bitcoin-NG Metrics Evaluation Conclusion

Evaluation (1) We evaluate Bitcoin-NG and compare it with Bitcoin in two sets of experiments - Varying block frequency - Block size

Varying block frequency (1) 對bitcoin來說就是透過調整難度來改變block的frequency 而對NG來說則是調整microblcok的產生速度(key block則固定在1個100秒) 而block size則都依照bitcoin的大小, 也就是1MB, every 10 mins, 也因為這個設定 我們可以看到tansaction frequency如實際運作上一樣接近3.5個transaction一秒鐘 而我們可以看到在1秒只產生0.01個blcok時 NG明顯比BITCOIN好

Evaluation (3) Varying block frequency (2) 而不論產生速度如何, NG的公平行總是在1附近, 而bitcoin可卻因為產生速度增加, 而導致mining power和其所影響的blockchain更動不成正比, 也就是可能有很多power的會造成比其該能造成的影響更多 在看mining power utilization , 我們可以看到bitcoin在產生速度越快時, 壞節點能夠破壞平衡, 掌控blockchain需要擁有的mining power門檻越來越低

Varying block frequency (3) Evaluation (4) We evaluate Bitcoin-NG and compare it with Bitcoin in two sets of experiments - Varying block frequency - Block size 最後看到意識到自己走的chain是即將被prune掉的chain的情況下 NG也是相當快就能反映 而bitcoin則稍慢

Block Size (1) 再來是固定block frequency調整block size的測試 作者把Bitcoin設定在1/10sec一個block NG則是1/10sec一個microblcok and keyblock 1/100sec 而因為此設定(microblcok and normal block的速率依樣) 所以交易速率是一樣的 另外我們可以看到如果blocksize越大, NG的agreement延遲表現比NORMAL好很多

Block Size (2) 再來看到Fairness block越大, NG並沒有顯著的下降 而Normal卻下降很多, 這顯示了size變大時, 會讓node花更多時間去驗證還有傳送廣播導致有強大power的人更有利 再來是mining power utilization, 一樣越大size, 惡意節點要掌控系統所需的mining power就越低

Block Size (3) 最後看到意識到自己走的chain是即將被prune掉的chain的情況下 NG也是相當快就能反映 而bitcoin則稍慢 (後面往上升是因為blocksize增大導致Agree時間增加, 因為驗證時間和傳送廣播時間增加)

Outline Introduction Bitcoin-NG Metrics Evaluation Conclusion

Conclusion Consensus latency is limited solely by the network diameter Throughput bottleneck lies only in node processing power. Such scaling is key in allowing for blockchain technology to fulfill its promise of implementing trustless consensus for a variety of demanding applications at global scale.