今天我們來學(xué)習(xí)一下一個(gè)新的共識(shí)算法歹河，他較以往有非常大的改變摩窃。雪崩算法如果在數(shù)學(xué)上可以給出更好地安全性證明以及活性證明卤恳，它可能在接下來一段時(shí)間大放異彩鳞滨。
在 2018 年 5 月紐約舉行的 Token Summit III 上洞焙，康奈爾教授埃米·岡·瑟勒（Emin Gun Sirer）發(fā)布了一個(gè)新型的區(qū)塊鏈共識(shí)協(xié)議，它是由一組算法組成的家族拯啦，聲稱它是公式算法的重大突破和創(chuàng)新澡匪，這個(gè)算法家族集成了經(jīng)典的 Non-Byzanting 共識(shí)算法和 Nakamoto 共識(shí)算法（即 POW） 兩者的特點(diǎn)。用他們的話來說就是褒链，簡(jiǎn)單而又強(qiáng)大無比唁情。
亞穩(wěn)態(tài)機(jī)制：
算法提出了一種基于亞穩(wěn)態(tài)機(jī)制（metastable）的共識(shí)協(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)槔绻帽容^小的力推小球恍箭，則會(huì)停留在位置1這個(gè)亞穩(wěn)態(tài)上刻恭，而如果用比較大的力推，則會(huì)進(jìn)入位置3這個(gè)真正的穩(wěn)態(tài)上季惯。
那么這個(gè)新的共識(shí)協(xié)議族有什么特點(diǎn)呢吠各？
綠色（Green）：消耗很少能源
安靜（Quiescent）：沒有交易時(shí)不需要工作（出塊）
高效（Efficient）：節(jié)點(diǎn)交互復(fù)雜度O(knlogn) ~ O(kn)
如何實(shí)現(xiàn)以上目標(biāo)？主要依賴以下幾種措施：
并行共識(shí)模型：不使用單一復(fù)制狀態(tài)機(jī)（RSM）模型勉抓，每個(gè)節(jié)點(diǎn)維護(hù)自己的RSM（可以互相轉(zhuǎn)移所有權(quán)）贾漏，系統(tǒng)對(duì)有關(guān)聯(lián)的交易只維護(hù)偏序（partial order）
反復(fù)隨機(jī)采樣：引導(dǎo)誠(chéng)實(shí)節(jié)點(diǎn)產(chǎn)生相同輸出
亞穩(wěn)態(tài)決策：亞穩(wěn)態(tài)決策可以使得一個(gè)大網(wǎng)絡(luò)快速推進(jìn)到一個(gè)不可逆的狀態(tài)（雖然不能100%保證）
既然是共識(shí)協(xié)議，必然繞不過安全性和活性的證明藕筋。我們先看一下這兩個(gè)特性的定義：
安全性（Safety)：nothing bad happens
活性（Liveness）：something good eventually happens
該論文證明纵散，文中提出的算法可以提供強(qiáng)概率安全性保證，并且保證誠(chéng)實(shí)節(jié)點(diǎn)的活性。所謂“強(qiáng)概率安全保證”伍掀，是指共識(shí)被逆轉(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的增長(zhǎng)鳍置，m呈對(duì)數(shù)級(jí)增長(zhǎng)，因此可以有效控制通信量送淆。
Slush算法是一種非拜占庭容錯(cuò)（BFT）算法税产，但卻是后面三種BFT算法的基石。
下面總結(jié)一下這個(gè)協(xié)議的特點(diǎn)：
（1）簡(jiǎn)單狀態(tài)（simple state）
節(jié)點(diǎn)是 memoryless 的偷崩，在每一輪 query 之間辟拷，除了 color，不保存其他任何狀態(tài)阐斜。
**（2）小樣本（small sample） **
不像其他共識(shí)算法衫冻，每輪必須向所有節(jié)點(diǎn)發(fā)出請(qǐng)求。Slush 只需要向一個(gè)很汹顺觥（常量 k）的隨機(jī)樣本集發(fā)出 query隅俘。
（3）反復(fù)抽樣（repeated sampling）
通過反復(fù)抽樣邻奠，可以放大隨機(jī)擾動(dòng)。比如为居，即使初始狀態(tài)是一個(gè) 50/50 的對(duì)等分裂狀態(tài)（收到了兩種沖突的 color 響應(yīng) 碌宴，且他們數(shù)量相同），抽樣過程中的隨機(jī)擾動(dòng)（perturbation) 也會(huì)導(dǎo)致一種 color 會(huì)獲得輕微的優(yōu)勢(shì)蒙畴，然而協(xié)議通過反復(fù)的抽樣可以不斷放大這種優(yōu)勢(shì)贰镣。
（4）抽樣輪數(shù)或時(shí)間期限（用 m 表示）
如果 m 足夠大，Slush 算法可以保證所有節(jié)點(diǎn)都有同等的機(jī)會(huì)被染色（colorized）膳凝，每個(gè)節(jié)點(diǎn)每輪通信都會(huì)有一個(gè)常量的八孝，可以預(yù)測(cè)的通信消耗。m 會(huì)隨著 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)對(duì)當(dāng)前顏色的信任度讲坎。如果連續(xù)β輪都選擇該顏色，則接受該顏色愧薛。
具體修改的部分：
每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)計(jì)數(shù)器
每次顏色發(fā)生變化時(shí)晨炕，將該計(jì)數(shù)器清零
每次查詢成功（收到αk個(gè)回復(fù)），并且顏色不變時(shí)毫炉，計(jì)數(shù)器加一
Snowflake 對(duì) Slush 的改進(jìn)非常簡(jiǎn)單瓮栗，下面也做個(gè)總結(jié)：
（1）每個(gè)節(jié)點(diǎn)維護(hù)一個(gè) counter 變量 。
（2）每當(dāng) color 進(jìn)行改變瞄勾，節(jié)點(diǎn)都會(huì)把 counter 值重置為 0费奸。
（3）一旦 query 得到的響應(yīng)結(jié)果中包含同一 color 的數(shù)量 ≥ αk，那么該節(jié)點(diǎn)就會(huì)把 counter 加 1进陡。
當(dāng) Snowflake 選擇了一個(gè)合適的 β 參數(shù)愿阐，和一個(gè)理想的 ε 安全系數(shù)，就可以同時(shí)保證 Safty 和 Liveness四濒。
論文在后面還介紹了一個(gè) phase-shift 點(diǎn)换况，correct node 更傾向與做出一個(gè)決定而不是維持在一個(gè) bivalent 狀態(tài)职辨。 并且，還會(huì)有一個(gè)叫做 point-of-no-return 的時(shí)間點(diǎn)戈二，Byzantine node 在 phase-shift 之后失去控制舒裤，而 Correct node 則在 point-of-no-return 點(diǎn)之后開始 commit color。
（要出差觉吭，回來繼續(xù)）
