鏈化未來公眾號將分三篇文章來闡述鏈化未來的共識協(xié)議的理論設計展运，后續(xù)還會推出一系列文章來詳細說明鏈化未來共識協(xié)議的工程實現(xiàn)癣蟋，本文為鏈化未來共識協(xié)議理論設計的第一篇（1-3章）酒朵。

目錄

1露该、前言

2、貢獻

3乍惊、名詞解釋

? 3.1 驗證算法?

? 3.2 摘要函數(shù)?

? 3.3 后量子算法?

? 3.4 BLS 算法?

? 3.5 區(qū)塊?

? 3.6 節(jié)點身份?

? 3.7 消息類型?

? 3.8 可驗證延時函數(shù)算法?

4粪般、架構

? 4.1 隨機數(shù)層?

? 4.2 身份層?

? 4.3 共識層?

? 4.4 新節(jié)點加入 ?

5、安全性證明

? 5.1 定理?

? 5.2 安全假設?

? 5.3 推論?

1污桦、前言

對于區(qū)塊鏈應用場景亩歹，需要共識算法具有如下特性

Throughput：transaction per second 意味著區(qū)塊鏈系統(tǒng)每秒能處理的交易筆數(shù)，為了能夠滿足全球用戶凡橱，交易處理速度必須足夠大小作，否則會造成交易積壓，回復時間長稼钩。比如 bitcoin 的交易擁堵和以太坊因為 crytokitties 造成的網(wǎng)絡擁堵顾稀。

Latency：交易從提交到回復成功與否的時間。在 PoW 網(wǎng)絡中坝撑，因為有分叉可能静秆，一般要等待幾個塊后確定。在 BFT 共識系統(tǒng)中巡李，因為正確節(jié)點都在共識結束后就確定性有相同結果抚笔，所以在交易不擁堵的情況下，響應速度與共識時間相同侨拦。?

Scalability：一般默認區(qū)塊鏈系統(tǒng)參與的節(jié)點數(shù)越多殊橙，系統(tǒng)安全度越高。對于基于 PoW 共識的系統(tǒng)狱从，安全度與參與的誠實算力相關膨蛮。對于基于 BFT 共識的系統(tǒng)，參與節(jié)點數(shù)越多季研，能容納的惡意節(jié)點越多敞葛，惡意節(jié)點少于 1/3。但是對于 BFT 系統(tǒng)与涡，節(jié)點越多惹谐，通信和計算開銷越大。Algorand 提出利用 Verifiable Random Function 隨機選出一部分節(jié)點形成 committee參與共識递沪，保證了無論總節(jié)點數(shù)多大豺鼻，最后的 committee 數(shù)目一定综液，共識速度就不變款慨。

Security：對于 BFT 共識，安全度包含 consistence谬莹，liveness 和 fairness檩奠。Consistence 是系統(tǒng)內所有誠實節(jié)點要最終達到相同的狀態(tài)桩了。Liveness 需要系統(tǒng)在任意情況下都能收斂到確定狀態(tài)，并且能持續(xù)接受交易埠戳，產生正確的共識結果井誉。Fairness 在于對于系統(tǒng)的用戶，任意合法的交易都不會被拒絕整胃。

對于傳統(tǒng)的 PBFT[1, 2] 系統(tǒng)颗圣，需要假設網(wǎng)絡處于弱同步狀態(tài)，通過超時和換主來保證 liveness屁使。但是因為換主是確定性地換到預先設定的下一個節(jié)點在岂，而且每次換主導致的節(jié)點消息同步耗時長，主節(jié)點會被連續(xù)不斷的網(wǎng)絡攻擊導致癱瘓蛮寂，最終系統(tǒng)持續(xù)換主蔽午，永遠無法共識交易，相當于停滯狀態(tài)酬蹋。

對此及老，Tendermint[3] 提出每一輪共識完成后確定性由下一個節(jié)點提出共識請求，從而避免了一直由主節(jié)點提交請求范抓，避免了攻擊的薄弱點骄恶。但是這依然無法避免提交請求節(jié)點的可預測性，導致被依次攻擊匕垫，系統(tǒng)每輪共識都為空叠蝇。

Honey Badger[4] 提出了基于 RBC（Reliable Broadcast）和 BA（Binary Agreement）的協(xié)議。核心在于任意節(jié)點都可以提出共識消息年缎，通過 RBC 可靠傳播到所有節(jié)點悔捶，并且為了減小廣播帶寬，通過 erasure code 分割消息為多份单芜。同時所有節(jié)點都通過 BA 協(xié)議共識所有消息蜕该，BA 協(xié)議的執(zhí)行會在任意情況下快速收斂到 1 或者 0，表示對共識消息的接受與否洲鸠。該協(xié)議相當于每一輪堂淡，所有節(jié)點并行地提出交易、共識扒腕，最終得到交易的子集作為共識結果绢淀。所以對任意一個節(jié)點的攻擊，都不會造成整個網(wǎng)絡的崩潰瘾腰，只是會影響網(wǎng)絡部分性能皆的。而且能充分利用帶寬，適合全球部署蹋盆。該協(xié)議的缺點在于交易響應延時比較高费薄，因為每輪要共識多個節(jié)點的交易硝全。同時協(xié)議需要預先確定節(jié)點的集合，不能動態(tài)添加節(jié)點楞抡，不能支持大規(guī)模節(jié)點伟众。

為了解決節(jié)點添加和擴充節(jié)點的問題，Algorand[5] 提出將 VRF（Verifiable Random Function）[6]和 BA 結合起來召廷。無論節(jié)點數(shù)目多少凳厢，通過 VRF 和持有的代幣數(shù)隨機選出特定數(shù)目節(jié)點，然后節(jié)點通過 BA 相互發(fā)送交易竞慢，并對優(yōu)先級最高（VRF 隨機數(shù)最惺酢）的節(jié)點發(fā)出的交易共識。為了提高安全性梗顺，共識的每一步都通過 VRF 選出新一輪共識節(jié)點泡孩，從而讓攻擊者無法預測下一個攻擊目標。該協(xié)議的主要有點在響應時間短寺谤，缺點在于無法做到高吞吐率和小帶寬仑鸥。

Dfinity[7] 主要是通過 threshold 簽名來保證 VRF 的每一輪都能確定性地收到 signature。結合Random Beacon 和 Notaries 來使每一輪的成員都隨機選擇变屁，并且提交的塊按照本輪隨機數(shù)進行排名眼俊。但是一個潛在的經(jīng)濟學博弈問題是，threshold 簽名可以通過多個成員的合謀的方法來預測粟关，合謀的成員可以協(xié)同計算出群私鑰疮胖，快速預測出下一輪的隨機數(shù)。通過作惡 Dos 攻擊下一輪的成員的目的闷板，合謀者可以破壞網(wǎng)絡的公平性澎灸。因為這種攻擊是不容易被發(fā)現(xiàn)的，所以可以做到零成本收益遮晚，因而在現(xiàn)實世界必然會出現(xiàn)性昭。

2、貢獻

鏈化未來共識具備如下特性

基于 VDF 的隨機數(shù)生成器县遣，解決了拒絕提交和隨機數(shù)提前預測的問題糜颠，并且允許所有人公平地參與，隨時可以離開萧求。?

基于 VDF 的改進 PoS 機制其兴，解決了長程攻擊問題，同時對新節(jié)點加入的驗證問題也進行了解決夸政。?

引入硬件獨特的計算能力評分和歷史記錄評分元旬，生成無法篡改的硬件指紋，保證參與共識的節(jié)點都是高性能和良好信譽的。通過可驗證隨機函數(shù)和硬件指紋法绵、持有代幣隨機選出共識節(jié)點（側重硬件性能）和驗證節(jié)點（側重代幣數(shù)和信譽評分），提高了系統(tǒng)的安全性和擴展性酪碘。

通過利用拜占庭共識過程中的并行性朋譬，提高了共識的效率，同時保證在少數(shù)共識提交者被攻擊的時候兴垦，網(wǎng)絡依然保持活性徙赢。

通過優(yōu)化密碼學簽名驗簽模塊，在共識過程采用輕量級的密碼學模塊 [8, 9]探越，同時持久化高安全度的密碼學結果狡赐，提高了節(jié)點響應速度。?

通過冗余編碼 [10] 將消息劃分為多份傳遞钦幔，而不是一份消息廣播枕屉，保證了節(jié)點能在同一時間窗口并行廣播最大的消息數(shù)量，并且同一份消息通過多個路徑傳播鲤氢，增加了安全到達概率搀擂。每一份消息附帶默克爾樹證明，可以提前得到存在性驗證卷玉。

3哨颂、名詞解釋

3.1 簽名驗證算法

鏈化未來選擇 ED25519[11] 作為對消息的簽名，主要是基于如下考慮：

ED25519 是開源的密碼學算法相种，由 Daniel Bernstein 提出威恼，經(jīng)過眾多密碼學專家論證，最后入選 RFC7748 標準寝并。曾經(jīng)參與過同微軟 FourQ[12] 共同競爭下一代更高效更抗側信道攻擊的橢圓曲線算法標準箫措，后因 NIST 直接進入后量子算法的遴選而取消。

ED25519 有比較高效的開源算法實現(xiàn)衬潦，并且匯編實現(xiàn)支持 Intel AVX 指令集蒂破。?

ED25519 相對基于 Weistrass 曲線的 NIST P-256 曲線，性能有比較大的提升别渔。在接下來的數(shù)學表達中附迷，

簽名標記為：SIGsk(m) =?ED25519sig(sk, m)

驗證標記為：V ERpk(SIGsk(m), m) =?ED25519ver(pk, SIGsk(m), m)?

其中(sk, pk)?為一對私鑰、公鑰哎媚。

3.2 摘要函數(shù)

鏈化未來采取 SHA256 作為摘要函數(shù)喇伯，基于如下考慮：

雖然 SHA3 標準已經(jīng)提出，但是目前尚沒有明顯針對 SHA256 的攻擊拨与。?

SHA256 性能相對 SHA3 比較高稻据，而且有眾多比較成熟的開源實現(xiàn)。

SHA256 相對 SHA3 或者其他摘要算法，有更多市場可用的實現(xiàn)捻悯。

? ?在接下來的數(shù)學表達中匆赃，摘要函數(shù)標記為：SHA(m) :?hash?=?SHA256(m)

3.3 后量子算法

量子計算機主要對密碼學中的非對稱算法和密鑰交換影響較大，比如 RSA 基于的大數(shù)分解困難問題可用 Schor 算法高效解出今缚，同理離散對數(shù)問題也可以解決（如 GEECM ）算柳。然而對于對稱算法和單向函數(shù)影響不大，只需要為了增加安全性到兩倍即可即可姓言。目前 鏈化未來 不以后量子算法為主瞬项，基于如下考慮：

量子計算機的發(fā)展仍然有相當?shù)臅r間長度 [15]，一些關鍵性的問題如多個量子的疊加何荚、量子糾錯囱淋。

目前抗量子算法如密鑰交換和非對稱算法標準尚不成熟，NIST 第一輪的篩選剛剛完成餐塘。

抗量子算法目前有基于 LWE[16] 和 code[17] 的算法妥衣，效率普遍比較低，而且安全性的量化評估目前尚無定論（如 LWE 基于的 CVP 和 SVP 問題一直有效率更高的算法被提出 [18]）戒傻。

傳統(tǒng)算法基于的困難問題称鳞，如基于 pairing 的 ABE[19]/IBE[20]、零知識證明 [21]稠鼻，在抗量子的困難問題基礎上構造比較困難冈止，或者比較難做到高性能。

區(qū)塊鏈上的數(shù)據(jù)到后量子的遷移并沒有很大難度候齿。主要是因為有足夠多的時間熙暴，從非抗量子的公鑰錢包遷移到抗量子的錢包。

Merkle tree慌盯、存證等基于的 SHA 算法即使安全度降低周霉，被碰撞的難度依然比較大。?

鏈化未來的抗量子錢包亚皂，通過結合最新的 NIST 征集的抗量子加密算法俱箱，并通過多重簽名技術達到足夠的安全性。并且針對抗量子算法的缺點又以下解決方案

針對目前抗量子算法是否真正抗量子的問題灭必，即使 NIST 尚無定論狞谱，所以我們采用多個算法（Crystals-dilithium[22], Spincs+[23], Rainbow[24]）+ 多重簽名的方式。這樣即使其中一個算法被攻破禁漓，不至于影響錢包的安全性跟衅。

針對公鑰長度太大的問題，目前消息傳遞采用賬戶名的方式播歼，所以只是多占用用戶的存儲資源伶跷，不會帶來交易的帶寬消耗。

針對簽名長度太大的問題，會造成交易大小的增大叭莫，影響系統(tǒng)的 tps蹈集，消耗用戶的帶寬資源。所以目前只能依賴密碼學的進一步發(fā)展雇初，同時建議用戶只是用在抵押賬戶或者不經(jīng)常使用的存儲賬戶上拢肆。

針對多密鑰的管理問題，我們提供安全的密鑰派生錢包抵皱，用戶只需要存儲一個密鑰善榛，即可管理所有抗量子的錢包辩蛋，并且不會因為一個賬戶被破解而影響其他任何一個賬戶的安全性呻畸，用戶體驗不會受到任何影響。

3.4 BLS 算法

采用 BLS 算法悼院，可以對簽名結果進行聚合 [25]伤为，從而減小傳遞的消息大小。鏈化未來 目前將此算法此算法應用在 Vote 消息中据途，減小 Vote 的消息大小绞愚，并相應地減小每個塊證書的大小，減小側鏈向主鏈傳遞的跨鏈消息大小颖医。同時小的塊證書大小位衩，也對輕客戶端的驗證帶寬和計算負載比較小。

3.5 區(qū)塊

區(qū)塊由如下結構構成

塊高度熔萧，簡寫為bh

上一個塊的hash糖驴，定義為hprevbh。

塊包含的交易的merkle根hrootbh佛致。

交易執(zhí)行結果的merkle狀態(tài)樹根贮缕，即hstatebh。

交易的Proposers的merkle樹根俺榆，即hP roposerbh感昼。

VDF結果和證明，即resV DF和proofV DF?罐脊。

總的區(qū)塊格式為

(bh, hprevbh, hrootbh, hstatebh, hP roposerbh, resV DF?, proofV DF?)? ? ? ? ?(1)? ? ?

考慮到創(chuàng)世區(qū)塊比較特殊定嗓，我們定義為

??(0,?0, hroot0, hstate0,?0,?0,?0)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (2)

其中hroot0包含一個創(chuàng)世合約，其中約束了鏈化未來的規(guī)則萍桌。hstate0包含創(chuàng)世成員的身份和代幣分布蜕乡。

3.6 節(jié)點身份

在區(qū)塊鏈系統(tǒng)運行過程中，任意一個節(jié)點屬于如下一種身份：

Proposer: 共識每輪提起交易批

Voter: 對交易進行確認梗夸，發(fā)出投票同意打包請求

Listener：對消息進行傳遞层玲，收到足夠票數(shù)后執(zhí)行

3.7 消息類型

區(qū)塊鏈系統(tǒng)運行過程中，主要包含如下兩種消息：

PROPOSE 消息：提議共識中需要包含的交易，由Proposer（對應密鑰對為 (skp, pkp)）生成, 格式為? ? ?

?(P ROP OSE, txs, bh, round, txshash, SIGskp, pkp)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (3)

其中txs為交易批辛块，txshash?=?SHA(txs)畔派，SIGskp?=?SIGskp(bh, round, txshash)。

ECHO 消息：投票消息, 由 Voter（對應密鑰對為 (skv, pkv)）生成润绵，格式為

?(ECHO, bh, round, txshash, SIGskv, pkp, SIGskv, pkv)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (4)

其中?SIGskv?=?SIGskv(bh, round, txshash)线椰，其余同上。

3.8 可驗證延時函數(shù)算法

可驗證隨機函數(shù)尘盼，又被成為 VDF憨愉，是一種延時函數(shù)，具有不可被并行的特征卿捎，并且可以被高效驗證配紫。為了表示該函數(shù)，我們定義如下：

? ? ? ? ? ? ? y?=?V DF(x, ts)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5)

? ? ?result?=?V DFverif y(y)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(6)