[SIGMOD 2021] SharPer: Sharding Permissioned Blockchains Over Network Clusters

1. 作者簡介

論文發表在SIGMOD 2021，第一作者Mohammad Javad Amiri來自賓夕法尼亞大學，第二作者和第三作者都來自加州大學圣塔芭芭拉分校（Divyakant Agrawal和Amr El Abbadi都是ACM/IEEE Fellow，資料管理方面大佬），

2. 背景介紹

可拓展性是區塊鏈的一個重要性能指標，是指隨著區塊鏈網路中節點數目增加，系統對交易的處理性能也隨之增長，分片技術是分布式資料庫中常用來提升性能的技術方案，例如Google的Spanner，目前，分片技術也被運用在區塊鏈來提升單鏈性能，Elastico，OmniLedger和Rapidchain用在公鏈的分片中，分片由節點隨機組合產生，以通過概率來保障所有惡意節點均勻的分配到不同分片中，聯盟鏈中的分片作業有Fabric，Cosmos，RSCoin，AHL，AHL是本文所對比的一個方法，其首先依靠可信硬體降低片內允許的節點數目下限，使惡意節點占比低于1/3，同時，片間共識需要依賴片以外的其他節點，共識的網路通信開銷大，單片處理跨片交易不支持多片并行，

當前分片作業對于片內安全性假設有兩種，預先定義錯誤節點數目或者概率性的錯誤假設，例如Spanner，基于真實世界中的物理情況約束，假設資料中心的大部分節點都是安全的（Paxos情況下惡意節點數目不會超過1/2，PBFT共識演算法下惡意節點資料不超過1/3），即一種確定性的片內安全保證，其他例子還有ResilientDB和Blockplane，本文提出的Sharper也是基于這種確定性的安全保證假設，節點部署在資料中心，云服務或者本地服務器，Elastico，OmniLedger和Rapidchain都旨在更加廣泛的對等網路中提供分片服務，通過隨機分配節點形成分片，獲得概率性的片內安全保障，

3. 貢獻點

文章作業致力于提高當前聯盟鏈在分片架構下的交易吞吐率，貢獻點如下：

• 將區塊鏈節點和資料進行分片，支持并行處理多個跨片交易，
• 支持片間共識（純CFT或BFT節點錯誤），解決了片間并發時候共識出現的交易沖突、死鎖、主節點故障問題，

4. Sharper 架構

假設前提：

1. 網路中的所有節點存在于異步環境網路環境，（根據FLP定理，異步網路下只能保證一致性協議的安全性，若要同時滿足活性異步網路是不夠的，需要弱同步網路），

2. 網路中的所有節點分成P個分片P={p1, p2,…, pN}，每個分片維護區塊鏈的部分視圖資料D={d1, d2,…, dP}，片中所有節點存盤一個視圖中的所有資料，如圖1所示，對于運行Paxos或者PBFT共識協議時，每個分片中節點數目都滿足2f+1或者3f+1安全條件，f為故障階段或拜占庭階段數目，并且同一個片中的節點是由地理上距離比較相近的一批節點組成，互相通信延遲較低，

3. 網路中的訊息經過簽名認證，惡意節點無法鍛造誠實節點的訊息，
   
   Sharper架構示例如圖1所示，整條鏈被分成4個分片，t10,t11是片1的第一個和第二個執行的交易，它們都是片內交易，t12,22是片1和片2需要共同執行的跨片交易，并且都是片內的第三個執行的交易，跨片交易需要確定在相關片中執行的序號確保結果的正確性，對于那些所涉及的分片不存在交集的跨片交易，Shaper支持并行處理這些交易，例如交易t12,22和交易t32,42，

4. 跨片共識
   區塊鏈中的共識機制負責讓所有節點對請求按照某個相同的處理順序達成共識，需協議要滿足以下四個性質：

   約同性（ Agreement ） , 所有誠實節點對相同的請求達成commit意見，
   有效性（ Validity ） ，好節點達成commit意見的值，必須是一個好節點的輸入值，
   一致性（ Consistency ） ，所有好節點按照相同的順序commit相同的值，
   可終止性（ Termination ） ，最終所有節點都會commit一個值，

   其中，前三個總結為協議安全性（safety），最后一個總結為活性（liveness），

對單個分片而言，讓片中所有節點對一筆交易保持一致的技術已經很成熟，然而對于跨片交易而言，它需要在多個排序實體的節點之間保持保持一致，本文分別研究了CFT和BFT網路節點錯誤環境下的跨片共識機制，值得一提的是，雖然現在區塊鏈中大家都在研究BFT共識下的問題，對于研究CFT下的跨片共識的重要性作者給予了解釋，認為在存在準入機制的聯盟鏈場景中，CFT共識可能就已經足夠了，例如有名的Hyperledger Fabric專案中也只支持CFT下的共識，

5. CFT 網路

5.1.1 片內 CFT 共識

對于只涉及到一個分片的交易只要走片內共識（Intra-shard consensus）就可以了，Sharper在CFT網路中的片內共識采用multi-paxos演算法，該演算法由Lamport 1998年提出，選擇一個穩定的節點長期作為主節點，協議相比原始paxos具有更低的延時，

流程如下（因為網路中只有故障停節點，因此不需要對訊息進行簽名，只有主節點廣播commit訊息以及回復客戶端的時候需要簽名，用于其他節點和客戶端作為交易提交的證明）：

1. 客戶端向主節點發送一個交易請求，主節點分配一個訊息序號回傳給客戶端
2. 主節點向所有從節點廣播此訊息并且帶上accept資訊
3. 從節點收到主節點發來的訊息后回傳主節點accept資訊
4. 主節點收齊f個accept訊息后（加上自己的一共f+1個），向所有從節點廣播commit訊息，回傳客戶端處理結果（交易哈希，commit資訊，簽名），
5. 從節點收到主節點commit資訊后，將交易打包區塊，并帶上主節點簽名的commit請求提交給各自的節點驗簽、執行，（ 論文假設交易在所有節點上都是確定性執行 , 最后所有節點狀態一定一致 ）

5.1.2 跨片 CFT 共識


跨片共識演算法流程如下：

1. 客戶端c向跨片交易所涉及的其中一個分片主節點π(pi)發送交易m=<REQUEST, OP, tc, c>δc，tc是交易時間戳，用于抵抗重放攻擊，op是交易操作內容，δc表示客戶端簽名，
2. 主節點π(pi)給訊息m分配編號hi，并向交易所涉及分片的所有節點廣播propose訊息<PROPOSE, hi,d, m>，m是客戶端給主節點發送的交易，d是交易哈希，
3. 分片的從節點接受到主節點π(pi)的訊息后，驗證序號hi和訊息內容，若當前節點在等待前一筆跨片交易m’的commit訊息（m和m’涉及相同分片或者有重合），為了保證片間commit順序一致，節點將交易m存入快取，等m’交易commit之后再處理m，否則，從節點直接向主節點π(pi)回傳accept訊息<ACCEPT, hi, hj, d, r>，其中hj表示片內一個從節點r給訊息m分配的訊息編號，
4. 當主節點π(pi)收齊來自每個分片的f+1個ACCEPT訊息后，驗證hj、hi和d，收集所有分片的從節點分配的訊息編號(h1, h2, …, hk)，隨后向所有涉及交易的分片廣播COMMIT訊息<COMMIT, [h1, h2, …, hk], d>δπ(pi)，δπ(pi)表示主節點簽名，用于向區塊鏈證明區塊交易的正確性，主節點向客戶端回傳結果，如果客戶端沒收到回復，向所有相關分片節點廣播，如果分片節點判斷該請求已經被處理，則向客戶端回傳結果，否則，從節點將訊息轉發給主節點廣播，如果主節點不廣播訊息，判斷主已經故障，
5. 分片的從節點接受到COMMIT訊息后確認編號hj之前的所有交易都已經COMMIT（即使之前沒有ACCEPT，因為之前可能宕機了沒收到），然后向區塊鏈提交交易，執行，改變狀態，

協議可能出現問題：

若某個時刻兩個分片（p1和p3）的主節點同時向某個分片（p2）中的節點廣播propose訊息，如下圖，由于網路延遲，p2中不同節點收到來自p1和p2的順序可能不同，導致不同節點賦予相同訊息的編號不同，造成p1或者p3收到的交易編號沖突，無法收齊f+1個編號一致的accept訊息，造成此輪無法commit，另外，這也會進一步造成死鎖情況，例如兩個分片p1和p2同時收到p3的跨片共識請求，p1收到訊息的順序是m、m’; ，p2收到訊息順序是m’、m，p1只有收到m的commit訊息后才會提交m’， p2只有收到m’的commit訊息后才會提交m，系統陷入死鎖，作者隨后通過非常Na?ve的方法解決這幾個問題，最后還處理了主節點故障問題，

BFT場景中演算法也非常類似，協議概要圖如下：

同樣，作者也針對這個場景下會發生的編號沖突、死鎖、主節點故障進行了討論，解法非常相似，這里不再贅述，

6. 實驗

1測驗CFT和BFT環境中不同workload下的吞吐，發現在跨片事務較小的時候性能最好，

2分片中節點數目增加，系統整體吞吐變化，意料之中，主要是共識開銷，

轉載請注明來自我的CSDN博客：https://blog.csdn.net/BOBOyspa/article/details/119119827