第一次在知乎上寫文章，沒想到是關於論文的讀書筆記== 本來只想快速讀完這篇文章，奈何第一次讀這篇論文時確實看得很累，所以我打算專門為它寫一篇讀書筆記，權當留作紀念。
這篇文章是關於下面這篇2015年論文的讀書筆記：
J。 A。 Garay， A。 Kiayias and N。 Leonardos， “The bitcoin backbone protocol： Analysis and applications”，
Eurocrypt
， 2015。
不過我實際上閱讀的是2020年8月更新的更完整的版本：
先從摘要這兒簡單說明一下這篇論文吧：
正如文章標題可見，這篇論文研究比特幣這個最早以及當前最受大家關注的分散式數字貨幣系統。它將比特幣協議的核心部分提取出來（文中叫做Bitcoin backbone，後文將統一用Backbone來簡稱）進行分析，並提出了對於一條鏈來說兩條重要的安全性質：common prefix（共同字首） 和 chain quality （鏈質量），證明了在滿足hashing power和網路同步的假設下，backbone協議大機率滿足這兩條性質。 這一部分是關於這篇論文最重要的理論成果，接下來論文基於backbone底層協議來設計對應的上層協議來解決兩個具體應用：拜占庭將軍問題和公開交易賬本問題。最後論文針對網路同步問題增加了網路延遲設定，在新的網路同步場景下分別證明了backbone協議在對應的假設下可以滿足上述兩條重要的安全性質。
簡單來說，只要弄明白這篇論文的理論部分，後面的上層應用部分就只是添加了一些場景業務最後規約到理論模型當中。
1. 關於模型和一些基本定義
這篇文章採納了這篇論文中的經典multiparty模型設定：
Ran Canetti。 Universally composable security： A new paradigm for cryptographic protocols。 Cryptology ePrint Archive， Report 2000/067， 2000。
我覺得可以這樣來解釋：
首先拋開真實的網路環境，假設我們在玩一局沙盒遊戲。這局遊戲主要由如下成分構成：
上帝系統
Z
：
Z
的功能主要是建立遊戲玩家（論文中稱作party）、啟用玩家的回合行動、標記叛變玩家、向所有玩家提供輸入、查詢每個玩家的輸出
控制程式
C
：負責約束
Z
的行動，比如限制最多有n個玩家，最多有t個玩家可以叛變
玩家 Parties：遊戲中總共有n個玩家，我們簡稱為
， 在區塊鏈設定下，我們可以認為每個玩家都是一個礦工，他們負責執行對應的區塊鏈協議。玩家分為誠實玩家和叛變玩家。誠實玩家會遵從協議，不斷挖塊並在塊中寫入合適的內容，而叛變玩家則會根據 Adversary的策略來攻擊和阻礙誠實玩家
敵人 Adversary：簡稱
A
，這是一個全域性唯一的角色。它可以向上帝系統提出申請來使得若干誠實玩家叛變（上限為t），同時它可以操控叛變的玩家來執行它的攻擊策略
OK 接下來繼續說明遊戲怎麼玩：
首先這是一個回合制遊戲，在每個回合內每個玩家輪流行動（即所謂“round-robin”），所有玩家在本回合行動完畢之後即進入下一個回合。首先呢 上帝系統
Z
會建立
A
和 n 個誠實玩家。接著
A
可以告訴上帝系統 它打算使哪些誠實玩家叛變（最多t個），然後
Z
就會標記這些玩家已經叛變（誠實玩家不知道）。接著就開始了初始回合（round 1），
Z
依次啟用n個玩家的行動。假設當前激活了玩家
的行動，如果
是誠實的玩家，那麼下一個被啟用行動的玩家就是
， 否則下一個行動的玩家就是
A
，
A
在每個回合做的事情都是告訴
Z
它打算使哪些玩家叛變。（簡單來說就是當前叛變玩家越多，敵人
A
的操作就更多）
那麼，在每個回合內，玩傢俱體可以幹什麼事情呢？
挖礦（POW）：簡單來說就是去算雜湊，算到一個符合條件的雜湊就算成功挖了一個塊
接收來自其它玩家和上帝系統
Z
傳送的訊息
廣播自己想要發出的訊息 （即自己當前的區塊鏈）
最後我們還得說明遊戲中關於算力的基本假設：
所有玩家算力
相同
，每個玩家每個回合 最多可以計算 q 次雜湊（敵人
A
控制了t個叛變玩家就意味著敵方每回合最多可以計算t·q次雜湊），論文中把這個基本假設叫作 q-bouned setting
2. Backbone協議以及其安全分析
先說一些基本定義：
定義一個塊 Block（簡稱B）：
，其中 s 就是大家熟悉的前一個塊的hash值，x是塊的內容，而 ctr 則是POW裡hash函式的輸入引數中的隨機數（通常在區塊鏈中叫做nonce）
如何驗證一個塊的POW合法性：
，其中H和G是兩個雜湊函式，就是說算出來的塊hash值要小於等於T並且ctr的值不能超過q（因為基本假設中假設每個玩家每回合最多算q次hash，所以這裡的條件是合理的）
不同區塊鏈的字首（prefix）關係：考慮兩條鏈
，如果
是
的字首，那麼
截去一條鏈的最新一部分塊：考慮一條鏈
，如果我們截去掉這條鏈最新的k個塊，那麼剩下的這條鏈我們用
來表示
那麼有了上面的基本定義之後，接下來我們可以進一步說明玩家如何處理鏈：
關於如何驗證一條鏈的合法性：從第一個塊開始，先驗證塊的POW合法性，再驗證塊的內容和之前的塊是否有衝突，依次驗證直到最新的一塊都是合法的即可認為這條鏈是合法的
兩條鏈之間的比較：在比特幣中在考慮選擇哪條鏈作為主鏈時我們選擇比較鏈的累積工作量，而在論文中因為不考慮塊的難度變化因此比較兩條鏈只需要比較他們的長度即可
多條鏈之間的選擇：論文中選擇了保守的方式，如果多條鏈長度相等，我們選擇最先到達的鏈作為主鏈
接著我們便可以說明Backbone協議的具體內容，即玩家在每個回合裡應該如何行動（按順序）：
接收來自上一輪其它玩家傳送的他們的最新的鏈用於和自己的比較，選擇最長的一條鏈作為自己的主鏈
如果來自上帝系統
Z
有查詢指令，則返回對應的鏈的資訊
根據 I（·） 函式（後文會提到）來獲取想要放進塊中的內容，接著開始挖礦
如果在挖成功了（計算雜湊q次以內算出合適的值），則把最新的鏈廣播發送給其他玩家，否則就傳送一個空的內容
當前回合行動結束，進入下一回合
以上便是Backbone協議的主要內容。
講完了協議的內容，接著我們來說這個協議想要實現的3個主要安全目標：
Common Prefix Property(公共字首性質)
：給定引數k，對於任意兩個誠實玩家
和
，他們分別擁有各自的鏈
和
，並且他們分別在
和
回合，且滿足
，那麼一定有
Chain Quality Property(鏈質量性質)：
給定引數u和L，對於任何一位誠實玩家來說，他擁有的鏈中的任意連續L個塊裡誠實玩家挖的塊至少佔了u的比例
Chain Growth Property(鏈增長性質)：
給定引數t和s，對於任意一個誠實玩家來說，在經過連續s個回合之後，他的鏈至少增長了t·s個塊
關於對Backbone協議的分析，則主要證明協議大機率(指數級)滿足上述3個核心安全目標。具體的證明其實比較冗長繁瑣，但其實不難，主要是定義的變數比較多，數學上主要用到的工具就是常用的Concentration 不等式(Chernoff bound)。這裡就說一下基本思路：
針對某一回合 i 定義對應的Bernoulli變數 X ：回合i 中有誠實玩家挖到了塊，Y：回合i中有且僅有一個誠實玩家挖到了塊（注意X和Y的區別）。以及一個Binomial變數Z：在回合i中挖到塊的叛變玩家總數
根據X，Y和Z的定義我們假設單獨一次計算POW成功的機率是f，然後我們便可以很容易的計算出這些隨機變數對應的期望值，接著利用Concentration不等式我們可以透過引數
來控制機率來使得這些隨機變數以指數級機率落在其置信區間
![((1-\epsilon)E[X],(1+\epsilon)E[X])](https://img.bearask.com/upload/website_attach/GAdgf0NlFaFj1_b_Imj=Z0pvbjL-LyZw1nSgdXBTXhIx2xHTHj_TLQekGowhQyZU0NjTe3_kA+TWunkVZCkyQNpzTewcOTC=N6HwywYkmPWFHy8_7T6iQTp2TkhwN6-=Nb6Ua.jpeg)
中（這裡僅以X為例）
接著我們便可以僅僅考慮發生好事件（即隨機變數落在置信區間中，敵人挖的塊沒有誠實玩家多）的情況，在這樣的情況下討論會使得問題變得簡單很多，因為這些重要的隨機變數都有了各自的bound，因此可以利用這些bound來一個個證明性質。
在這裡我不妨貼一小段原文的圖便於說明上述內容：
對應我們上面說的思路，這裡的好事件即是圖中的Typical execution，這個好事件發生的機率是指數級機率，機率大小由
來控制。當好事件發生的時候，我們可以有如下的一些重要的bound：
在有了這些bound後，對上述的3條性質的證明就變得相對簡單許多（但還是比較冗長繁雜==） ，這裡就不展開一一贅述了。
3。 基於Backbone協議的兩個上層應用
針對不同的應用，每個玩家擁有3個通用的功能函式來處理不同的業務：
I(·)：
這是input函式，即基於當前玩家的狀態、所擁有的鏈資訊、接受的來自上帝系統
Z
以及來自其它玩家傳送的資訊來生成的該玩家即將寫入新塊中的內容
R(·)：
即Read函式，讀取該玩家所擁有的鏈中的資訊
V(·)
：即驗證函式，用於驗證一條鏈中的內容是否合法（比如可以驗證比特幣的鏈中是否有“雙花”交易）
因此，我們只需要定義不同的I，R，V函式，Backbone協議即可以用於解決不同的具體應用。
舉個例子，關於論文中提出來如何解決拜占庭將軍問題：
在這樣的定義下，論文證明了當叛變玩家佔總人數比重不超過1/3時，誠實玩家透過Backbone協議可以在拜占庭問題中達成共識。而原先的Nakamoto協議卻無法滿足拜占庭將軍問題中的chain quality性質。
而對於公開賬本問題（終於接近比特幣的場景了）：
從圖中可以看到這裡的定義就已經比較接近比特幣對應的功能函數了。論文證明了當叛變玩家少於總人數的一半時誠實玩家可以達成共識。
在這一節最後貼上一張論文的應用成果圖吧，重點關注圖中的數字，它代表了叛變玩家可以佔據的總人數最大比例， #FormatImgID_32# 表示一個接近0的數，可以看到在拜占庭將軍問題和公開賬本問題中Backbone幾乎都實現了叛變者少於一半誠實玩家可以達成共識的目標。
4。 增加網路延遲設定
最後論文討論了有網路延遲的情況（之前的無延遲情況其實與真實場景差距非常大），在這個場景下需要對應地修改一些假設：
之前每個玩家在每回合可以最多計算q次hash，現在修改為1次
每個玩家傳送的資訊有
回合的延遲
簡單來說就是在有網路延遲的場景下，我們需要
把時間劃分得更細以方便定義延遲
（因此每回合只能算最多1次hash）
而增加網路延遲，最主要的影響就是大大增加了挖塊分叉的機率，因此我們需要重新定義X，Y：
當第i個回合的前
個回合以及後
個回合中都沒有誠實玩家挖出新塊，且第i個回合有且只有一個誠實玩家挖出了塊時，
當第i個回合有誠實玩家挖出了塊且第i回合的前
個回合都沒有誠實玩家挖出新塊時，
在新的定義下，我們同樣地需要重新定義好的事件：
當我們僅考慮好事件發生的情況時，我們得到了相似但是更為複雜的bound：
雖然內容變複雜多了，不過使用的方法和第2節中使用的方法是類似的。而在延遲場景下證明Backbone滿足安全性質的方法也是類似的，只是需要的假設有了對應的改動，所以這裡也不用再多贅述了。
5。 總結
這篇論文從3條重要的安全性質出發來論述比特幣核心協議的安全性，同時說明了網路同步速度和算力對誠實玩家達成共識的影響。這篇論文假設遊戲中的玩家數是固定的，而且挖礦難度也是固定的，這並不符合真實的場景，作者們在下一篇論文中討論了可變難度的場景：
Juan A。 Garay， Aggelos Kiayias， and Nikos Leonardos。 The Bitcoin Backbone Protocol with Chains of Variable Difficulty。 IACR Cryptology ePrint Archive， 2016：1048， 2016。
（如果你看了這篇文章的reference部分的話請直呼好傢伙，人家直接承包了一大片魚塘）
總體來說，雖然文章證明冗長繁雜，但是這篇首發自2015年的論文確實從理論上幫助我們更清晰地認識了比特幣的共識機制，具有很不錯的參考價值。
