最近arXiv上發(fā)現(xiàn)一篇論文（2018/8/2發(fā)表）欺嗤，作者來自清華大學唤衫，卡內(nèi)基梅隆大學，以及多倫多大學铐殃，提出了Conflux共識機制。姚期智是作者之一跨新。論文下載地址：https://arxiv.org/pdf/1805.03870富腊。
本篇文章大致介紹Conflux共識機制的算法思想以及實驗數(shù)據(jù)結(jié)果。感興趣的小伙伴可以查看論文以及相關引用域帐。
Conflux共識機制以及實驗數(shù)據(jù)是在比特幣（Bitcoin）源代碼框架下實現(xiàn)赘被。也就是說論文中區(qū)塊生成的算法沿用比特幣的POW（工作量證明）機制。當然論文中提到肖揣，Conflux的共識機制可以擴展到或者結(jié)合其他共識算法民假，比如PoS等等。Conflux共識機制的實驗數(shù)據(jù)說明：Conflux共識機制的吞吐量能達到5.78GB/s龙优，確認時間4.5-7.4分鐘羊异，交易速度6000TPS。論文中還提到彤断，Conflux共識機制的交易速度是GHOST或者Bitcoin的11.62倍野舶，Algorand的3.84倍。
1）Conflux框架
Conflux共識機制是在比特幣源代碼基礎上實現(xiàn)的宰衙。Conflux的框架和比特幣的礦機類似：GossipNetwork實現(xiàn)P2P網(wǎng)絡交互平道，節(jié)點維護TxPool，生成區(qū)塊（Block Generator）供炼，以及維護區(qū)塊狀態(tài)一屋。Conflux框架如下圖：
框架圖中的虛線部分是一個節(jié)點上的細節(jié)。比特幣的區(qū)塊鏈是一條鏈袋哼，也就是說冀墨，每個區(qū)塊只有一個父區(qū)塊。和比特幣不同涛贯，Conflux的區(qū)塊鏈是由“DAG State”實現(xiàn)轧苫，每個區(qū)塊除了一個“父區(qū)塊”外，可能還有多個“引用區(qū)塊”。
2）區(qū)塊DAG
Conflux中的區(qū)塊之間由多條邊（Edge含懊，連接）組成身冬，這些邊分成兩類：父連接，以及引用連接岔乔。在確定主鏈（Pivot）的基礎上酥筝，新生成的區(qū)塊必須使用父連接連接到主鏈的最后一個區(qū)塊上。除了主鏈外雏门，還存在其他一些非主鏈的路徑嘿歌，新生成的區(qū)塊必須使用“引用連接”連接這些非主鏈的最后一個區(qū)塊。也就是說茁影，Conflux中的區(qū)塊之間的連接關系組成DAG（有向無環(huán)圖）宙帝。Conflux中組成DAG的區(qū)塊會確定一條主鏈（Pivot Chain）。在主鏈確定的基礎上再確定所有區(qū)塊的先后順序募闲。區(qū)塊DAG的示意圖如下：
Genesis是“創(chuàng)世紀”塊步脓，也就是第一個塊。父連接用“實心”箭頭表示浩螺，引用連接用“虛線”箭頭表示靴患。區(qū)塊C使用“父連接”連接到A，使用“引用連接”連接到B要出。新生成的區(qū)塊（New Block）使用“父連接”連接到H鸳君，使用“引用連接”連接到K。
3）主鏈（Pivot Chain）確定算法
要確定區(qū)塊的順序關系（Block Total Order）患蹂，必須先確定主鏈或颊。主鏈的選擇使用“GHOST”規(guī)則〈冢“GHOST”規(guī)則是在2015年的一篇論文中介紹饭宾，具體請參考論文中的引用26「窳耍“GHOST”的基本思想是選擇子節(jié)點數(shù)多的節(jié)點看铆。Conflux的DAG結(jié)構(gòu)用如下的四元組表示：G = <B,g,P,E>，B代表DAG中的所有區(qū)塊盛末，g是創(chuàng)世紀塊弹惦，P是映射函數(shù)（每個區(qū)塊可以通過P函數(shù)獲取父區(qū)塊），E是所有區(qū)塊的“父連接”和“引用連接”的集合悄但。
GHOST規(guī)則的計算過程如下：
其中最核心棠隐，是第8行。確定下一個區(qū)塊是根據(jù)子區(qū)塊個數(shù)或者在子區(qū)塊個數(shù)相等的情況下根據(jù)區(qū)塊Hash檐嚣。子區(qū)塊個數(shù)多的助泽，或者子區(qū)塊個數(shù)相等區(qū)塊Hash小的區(qū)塊為主鏈的下一個區(qū)塊啰扛。注意，子區(qū)塊個數(shù)的計算不包括“引用連接”嗡贺。
還用第2部分介紹的DAG舉例：
主鏈由Genesis隐解，A，C诫睬，E煞茫，H以及New Block組成。
4）區(qū)塊順序
每個主鏈上的區(qū)塊組成一個時代（Epoch）摄凡。被該區(qū)塊“連接”到的區(qū)塊续徽，且沒有被之前區(qū)塊“連接”的區(qū)塊屬于這個區(qū)塊時代。區(qū)塊排序的算法如下：
Past（G亲澡，a）獲取DAG圖G中的主鏈中一個區(qū)塊a之前的所有區(qū)塊（包括區(qū)塊a）钦扭，也就是區(qū)塊a之前的區(qū)塊以及區(qū)塊a能連接到的區(qū)塊。很顯然床绪，偽代碼的第5行：Past（G客情，a）- Past（G，a'）計算的是區(qū)塊a所處時代中的所有區(qū)塊会涎，包括區(qū)塊a裹匙。區(qū)塊a時代的區(qū)塊單獨組成一個圖的話瑞凑，按照兩個規(guī)則進行排序：
1）有沒有連接關系 2）區(qū)塊Hash大小末秃。
同樣以第2部分介紹的DAG為例，每個時代包含的區(qū)塊用虛線分開籽御。區(qū)塊的排序為：Genesis练慕，（A），（B技掏，C）铃将，（D，F(xiàn)哑梳，E）劲阎，（G，J鸠真，I悯仙，H），（K吠卷，New Block）锡垄。區(qū)塊D只被區(qū)塊E連接，所以屬于區(qū)塊E的時代祭隔。
5）交易順序以及有效性
在區(qū)塊確定順序的前提下货岭，前一個區(qū)塊中的交易在后一個區(qū)塊中的交易前面。同一區(qū)塊的交易，按照區(qū)塊中交易順序排序千贯。特別注意的是屯仗，因為不同節(jié)點打包的交易加入DAG圖后，可能同一個交易被不同節(jié)點打入不同區(qū)塊中丈牢，也就是交易沖突祭钉。交易沖突包括兩種情況：1）交易兩方的地址有一個相同 2）同一交易。發(fā)生沖突的交易己沛，第一個交易有效慌核，后續(xù)沖突交易都無效。
比如在第2部分介紹的DAG中申尼，區(qū)塊B中的Tx3和區(qū)塊A中的Tx2沖突垮卓，地址X相同，保留區(qū)塊A中的Tx2师幕。區(qū)塊G中Tx4和區(qū)塊B中的Tx4重復粟按，保留區(qū)塊B中的Tx4。
6）安全性以及確認時間
簡單的說霹粥，攻擊者為了修改區(qū)塊的順序灭将，不得已要偽造足夠多的“子節(jié)點”。也就是需要有超過“誠實”節(jié)點的算力后控。GHOST規(guī)則的論文證明了只要作惡節(jié)點的算力不超過50%庙曙，要修改主鏈順序，隨著時間越長浩淘，概率越低捌朴，趨向0。論文提到张抄，用戶可以選擇自己能夠接受的確認時間砂蔽。論文同時給出了Conflux的安全性（Safety）以及可持續(xù)性（Liveness）的證明。感興趣的小伙伴可以自行參閱署惯。
7）實驗結(jié)果
Conflux在云服務器（Amazon EC2）上部署模擬節(jié)點左驾，得出如下結(jié)論：
a）區(qū)塊使用率，不論是區(qū)塊大小變化极谊，還是區(qū)塊生成時間變化诡右，都是100%。也就是只要生成的區(qū)塊怀酷，都能利用上稻爬，增加了區(qū)塊交易的吞吐量。比特幣同一時間蜕依，只有一個區(qū)塊勝出桅锄，其他區(qū)塊都會被浪費琉雳。
b）確認時間，不論是區(qū)塊變大友瘤，或者區(qū)塊生成時間變長翠肘，只有稍微變長。比特幣的話辫秧，在區(qū)塊變大束倍，或者區(qū)塊生成時間變長，分叉的可能性就變大盟戏，確認時間顯著增大绪妹。
c）Conflux具有很好的擴展性。帶寬變大柿究，區(qū)塊生成的速度變快邮旷。節(jié)點變多，生成區(qū)塊也會變多蝇摸。兩種方式都能帶來吞吐量的提升婶肩。
總結(jié)：Conflux共識機制，借鑒了2015年論文中的GHOST規(guī)則貌夕，使用DAG數(shù)據(jù)結(jié)構(gòu)組織區(qū)塊律歼。論文邏輯清晰，比較容易閱讀啡专。Conflux共識機制险毁，在DAG區(qū)塊中，先使用GHOST規(guī)則確定主鏈植旧，再確定區(qū)塊順序辱揭，交易順序离唐。發(fā)生沖突的交易病附，只保留第一個交易，其他沖突交易作廢亥鬓。論文論證了Conflux共識機制完沪，保證了區(qū)塊的安全性和可靠性，又能極大地提升交易吞吐量嵌戈。實驗數(shù)據(jù)表明：Conflux共識機制的吞吐量能達到5.78GB/s覆积，確認時間4.5-7.4分鐘，交易速度6000TPS熟呛。
題外：Conflux共識機制的設計宽档，結(jié)構(gòu)上和以太坊中的叔塊設計感覺有點相似。以太坊中的叔塊也是考慮到減少分叉庵朝，將在一定時間內(nèi)生成的合法區(qū)塊吗冤，“引用”連接到主鏈的區(qū)塊中又厉。
喜歡技術的小伙伴，歡迎關注公眾號：星想法椎瘟。
