今天我們來學(xué)習(xí)一下一個(gè)新的共識算法，他較以往有非常大的改變。雪崩算法如果在數(shù)學(xué)上可以給出更好地安全性證明以及活性證明，它可能在接下來一段時(shí)間大放異彩。
在 2018 年 5 月紐約舉行的 Token Summit III 上，康奈爾教授埃米·岡·瑟勒（Emin Gun Sirer）發(fā)布了一個(gè)新型的區(qū)塊鏈共識協(xié)議，它是由一組算法組成的家族，聲稱它是公式算法的重大突破和創(chuàng)新，這個(gè)算法家族集成了經(jīng)典的 Non-Byzanting 共識算法和 Nakamoto 共識算法（即 POW） 兩者的特點(diǎn)。用他們的話來說就是，簡單而又強(qiáng)大無比。
亞穩(wěn)態(tài)機(jī)制：
算法提出了一種基于亞穩(wěn)態(tài)機(jī)制（metastable）的共識協(xié)議族。所謂亞穩(wěn)態(tài)，是指系統(tǒng)在某段時(shí)間內(nèi)處于穩(wěn)定狀態(tài)，但在另外一段時(shí)間內(nèi)可能是不穩(wěn)定的。穩(wěn)態(tài)代表了系統(tǒng)的最低能量點(diǎn)，而亞穩(wěn)態(tài)則是一個(gè)局部的而非全局的最低能量點(diǎn)。以下圖中的小球?yàn)槔?，如果用比較小的力推小球，則會停留在位置1這個(gè)亞穩(wěn)態(tài)上，而如果用比較大的力推，則會進(jìn)入位置3這個(gè)真正的穩(wěn)態(tài)上。
那么這個(gè)新的共識協(xié)議族有什么特點(diǎn)呢？
綠色（Green）：消耗很少能源
安靜（Quiescent）：沒有交易時(shí)不需要工作（出塊）
高效（Efficient）：節(jié)點(diǎn)交互復(fù)雜度O(knlogn) ~ O(kn)
如何實(shí)現(xiàn)以上目標(biāo)？主要依賴以下幾種措施：
并行共識模型：不使用單一復(fù)制狀態(tài)機(jī)（RSM）模型，每個(gè)節(jié)點(diǎn)維護(hù)自己的RSM（可以互相轉(zhuǎn)移所有權(quán)），系統(tǒng)對有關(guān)聯(lián)的交易只維護(hù)偏序（partial order）
反復(fù)隨機(jī)采樣：引導(dǎo)誠實(shí)節(jié)點(diǎn)產(chǎn)生相同輸出
亞穩(wěn)態(tài)決策：亞穩(wěn)態(tài)決策可以使得一個(gè)大網(wǎng)絡(luò)快速推進(jìn)到一個(gè)不可逆的狀態(tài)（雖然不能100%保證）
既然是共識協(xié)議，必然繞不過安全性和活性的證明。我們先看一下這兩個(gè)特性的定義：
安全性（Safety)：nothing bad happens
活性（Liveness）：something good eventually happens
該論文證明，文中提出的算法可以提供強(qiáng)概率安全性保證，并且保證誠實(shí)節(jié)點(diǎn)的活性。所謂“強(qiáng)概率安全保證”，是指共識被逆轉(zhuǎn)的可能性小到可以被忽略（甚至小于哈希沖突的概率），實(shí)際上POW提供的也是強(qiáng)概率安全性保證。
另外，文中的理論分析是基于同步系統(tǒng)假設(shè)，而實(shí)驗(yàn)過程則是在部分同步系統(tǒng)中完成的，實(shí)驗(yàn)結(jié)果和理論分析基本吻合。
雪泥算法SLUSH：
為了算法的通用性，這里是以顏色沖突為例：R表示紅色，B表示藍(lán)色，⊥表示沒有顏色（初始狀態(tài)）。
初始狀態(tài)：沒有顏色（⊥）
收到交易：染成交易中指定的顏色，同時(shí)發(fā)起查詢
查詢：在網(wǎng)絡(luò)中隨機(jī)選取k個(gè)節(jié)點(diǎn)，如果規(guī)定時(shí)間內(nèi)沒有收到k個(gè)回復(fù)，再多選一些節(jié)點(diǎn)，直到收到k個(gè)回復(fù)為止
收到查詢：如果沒有染色，染成查詢中指定的顏色，并回復(fù)該顏色，同時(shí)自己也發(fā)起查詢。否則直接回復(fù)自己當(dāng)前的顏色
決策：收到k個(gè)回復(fù)后，如果某種顏色所占比例超過閾值α（0.5～1），則把自己染成那種顏色。然后繼續(xù)進(jìn)入下一輪查詢，一共查詢m輪，決定最終結(jié)果
可以證明，隨著節(jié)點(diǎn)數(shù)n的增長，m呈對數(shù)級增長，因此可以有效控制通信量。
Slush算法是一種非拜占庭容錯（BFT）算法，但卻是后面三種BFT算法的基石。
下面總結(jié)一下這個(gè)協(xié)議的特點(diǎn)：
（1）簡單狀態(tài)（simple state）
節(jié)點(diǎn)是 memoryless 的，在每一輪 query 之間，除了 color，不保存其他任何狀態(tài)。
**（2）小樣本（small sample） **
不像其他共識算法，每輪必須向所有節(jié)點(diǎn)發(fā)出請求。Slush 只需要向一個(gè)很?。ǔＡ?k）的隨機(jī)樣本集發(fā)出 query。
（3）反復(fù)抽樣（repeated sampling）
通過反復(fù)抽樣，可以放大隨機(jī)擾動。比如，即使初始狀態(tài)是一個(gè) 50/50 的對等分裂狀態(tài)（收到了兩種沖突的 color 響應(yīng) ，且他們數(shù)量相同），抽樣過程中的隨機(jī)擾動（perturbation) 也會導(dǎo)致一種 color 會獲得輕微的優(yōu)勢，然而協(xié)議通過反復(fù)的抽樣可以不斷放大這種優(yōu)勢。
（4）抽樣輪數(shù)或時(shí)間期限（用 m 表示）
如果 m 足夠大，Slush 算法可以保證所有節(jié)點(diǎn)都有同等的機(jī)會被染色（colorized），每個(gè)節(jié)點(diǎn)每輪通信都會有一個(gè)常量的，可以預(yù)測的通信消耗。m 會隨著 n 變大。 m 是指輪數(shù)或時(shí)間限制。 如果 Slush 被用在有 Byzantine 節(jié)點(diǎn)的網(wǎng)絡(luò)中，那么由于 adversary 節(jié)點(diǎn)可以故意把自己翻轉(zhuǎn)（flip）成一個(gè)與主流 color 不一樣的 color 來打亂平衡，使得整個(gè)網(wǎng)絡(luò)的安全性大大降低。 因此，我們把 Slush 協(xié)議作為 BFT 協(xié)議的原始狀態(tài)，它不能提供完整的 BFT 保證。
雪花算法Snowflake：
Slush算法是無狀態(tài)記憶的（memoryless），節(jié)點(diǎn)不保存和其他節(jié)點(diǎn)的交互歷史。
Snowflake算法在該基礎(chǔ)上，為每個(gè)節(jié)點(diǎn)增加了一個(gè)查詢計(jì)數(shù)器，用于累積該節(jié)點(diǎn)對當(dāng)前顏色的信任度。如果連續(xù)β輪都選擇該顏色，則接受該顏色。
具體修改的部分：
每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)計(jì)數(shù)器
每次顏色發(fā)生變化時(shí)，將該計(jì)數(shù)器清零
每次查詢成功（收到αk個(gè)回復(fù)），并且顏色不變時(shí)，計(jì)數(shù)器加一
Snowflake 對 Slush 的改進(jìn)非常簡單，下面也做個(gè)總結(jié)：
（1）每個(gè)節(jié)點(diǎn)維護(hù)一個(gè) counter 變量 。
（2）每當(dāng) color 進(jìn)行改變，節(jié)點(diǎn)都會把 counter 值重置為 0。
（3）一旦 query 得到的響應(yīng)結(jié)果中包含同一 color 的數(shù)量 ≥ αk，那么該節(jié)點(diǎn)就會把 counter 加 1。
當(dāng) Snowflake 選擇了一個(gè)合適的 β 參數(shù)，和一個(gè)理想的 ε 安全系數(shù)，就可以同時(shí)保證 Safty 和 Liveness。
論文在后面還介紹了一個(gè) phase-shift 點(diǎn)，correct node 更傾向與做出一個(gè)決定而不是維持在一個(gè) bivalent 狀態(tài)。 并且，還會有一個(gè)叫做 point-of-no-return 的時(shí)間點(diǎn)，Byzantine node 在 phase-shift 之后失去控制，而 Correct node 則在 point-of-no-return 點(diǎn)之后開始 commit color。
（要出差，回來繼續(xù)）
