比原链BBFT.pdf

BBFT a Hierarchical Byzantine FaultTolerant Consensus AlgorithmByStack Teamv1.01 IntroductionConsensus is the process applied by nodes to reach nal agreement on networkstates. Byzantine fault tolerant BFT consensuses are considered well suitedfor permission-ed blockchains where semi-trust exists among node. BFTconsensus can deliver high TPS transactions per second while guaranteessafety when at most bn 13 c out of total n nodes are simultaneously faulty.PBFT practical byzantine fault tolerant is one of the widely adoptedBFT consensuses[6]. However, it does not scale well because ofOn2 commu-nication complexity. In this report, we present a hierarchical BFT consensusalgorithm - BBFT. It utilizes network topology to e ectively distribute andaggregate messages among nodes and provides On communication com-plexity.2 System ModelWe de ne the system as an asynchronous distributed environment whereindividual nodes communicate via point-to-point network. The network mayfail to deliver message, delay them not inde nitely, or deliver them outof order. The network by itself is heterogeneous, meaning communicationquality between nodes is not equal and does not remain constant betweenthe same set of nodes.Message authentication is guaranteed by asymptotic security throughcryptographic signatures and hash functions[15, 17, 12].We call a node a consensus node if it participates in the consensus process.Consensus node replicates the current state of the system. Gateway node is aconsensus node that pers additional signature aggregation. Leader node1is a consensus node that proposes a block to be veri ed at the beginning ofthe consensus round. Every node possess a unique ID and is known by othernodes.We call a node byzantine node if it behaves arbitrarily. It may delay com-munication, modify messages, replay messages and forge signatures. Byzan-tine nodes can even collude. We assume that the faulty nodes are computa-tionally bound so that it is impossible to subvert the cryptographic techniquesused for message security.Nodes are organized as tree vertices with edges being communicationpaths as shown in gure 1. Non-leaf nodes are gateway nodes, and leaf nodesare consensus nodes. Top level gateway nodes are connected to each other.Leader node is always one of the top level gateway nodes.Figure 1 Example Nodes inter-connection TopologyThe system is Byzantine Fault Tolerant with minimal number of nodesn 3f 1 when up to f nodes are faulty. This number provides a lowerthreshold because in worst case of f faulty nodes, a node must be able toproceed with n f responses, despite that the f unresponsive nodes areactually non-faulty. This requires n 2f f. Therefore n 3f.In the following sections we describe the process of how nodes reach con-sensus. Then we discuss the two important components of the algorithmhow network is partitioned and how to aggregate signatures e ectively.23 Consensus ProcessThe consensus process resembles of a typical PBFT[6] with additional han-dling of signature aggregation at the gateway nodes. Under normal case,the algorithm consists of three stages distribute, aggregate, and nalize asshown in gure 2.Figure 2 Example Consensus Process of Single Level Five Nodes NetworkAt the beginning of consensus round, the nodes have the same view num-ber v 0, and block height h. Every node has its unique id i, which is knownby other nodes. A bitmap m is used during message passing to indicate whichnodes’ signatures are included in the aggregated signature.1. The leader node p selects transactions from its transaction pool andpackages them into the next proposed block b. The proposal is broad-casted to its peer gateway nodes at the same level as hDISTRIBUTE,h;v;m;b;b i.2. Its peer gateway nodes receive the proposal, and start to pass it downalong the topology tree edges. This concludes the distribute stage.3. At the leaf level, upon receipt of the proposal, consensus node i veri esthe block and signature, signs the block, and sends the result to itsparent gateway node as hAGGREGATE, h;v;m;b i.34. At every non-leaf level, gateway nodes verify the signatures receivedfrom its children and aggregate them together with its own incremen-tally, and pass it up along the topology tree edges.5. When top level nodes receive the aggregated signatures, they do a fullexchange of the message. This concludes the aggregate stage.6. The fully aggregated signature is then passed down along the topologytree edges to reach the leaf nodes as hFINALIZE, h;v;m;b i.7. Any consensus node, upon receipt of at least n f signatures, reachesconsensus and logs the block to its ledger. This concludes the nalizestage.A consensus node can initiate a VIEW-CHANGE proposal when it cannotreach consensus within t time interval, an invalid block has been proposed,or an invalid aggregated signature has been received. Here t is chosen to bethe maximum consensus process time, and depends on the number of nodesand network characteristics. When any node received at least n f VIEW-CHANGE messages with the same view number from other nodes, currentview number is updated and new consensus round starts.Let n be the number of consensus nodes, and m be the number of top levelgateway nodes, the total number of messages communicated in the consensusprocess is m2 2m 3n 2. When 1 m pn 4n 2pn 2,the communication complexity is On. Multi-level gateway nodes do notimpact overall complexity, because only the top level gateway nodes perfull message exchange. BBFT exhibits its exibility when m changes. As twospecial cases of BBFT, when m 1, BBFT becomes FBFT[16], and whenm n, BBFT becomes PBFT.4 Network ZoningWe de ne topology graph as the logical view of inter-connection among nodes.Nodes are vertices in the graph, and undirected edges are the communicationpaths between nodes, with its weight being communication latency. Wede ne topology tree as the minimal spanning tree MST that connects allthe nodes together, without any cycles and with the minimal possible totallatency. We consider the topology tree unique given the fact that it is highlyimpossible for the latency to be exact the same between any two pairs ofconnected nodes in real use case.Finding MST of an undirected graph is a well studied area[14, 7, 10].Highly optimal linear complexity algorithms exist[8, 13]. Linear complexity4distributed solutions also exist, where nodes are fully disconnected and onlycommunicate by message passing[9, 1]. To construct the MST in BBFT,we can either deploy a dedicated service that requests latency numbers fromnodes and returns the MST back to nodes, or distributed algorithm can beapplied. Note that even with the centralized approach, the service internalimplementation can be transparent to the nodes. The detail of the algorithmis out of the scope of this report.Once the MST is built, the tree is rotated such that the elected leadernode is at top level, and the number of the top level gateway nodes doesnot exceed pn. Given the dynamic of network inter-connection state, thetopology tree is re-generated periodically. Re-generation frequency dependson the use case and is coordinated with leader election.5 Signature AggregationWhen gateway node receives responses from it children consensus nodes, itpers signature aggregation before routing the message. A naive aggre-gation would simply concatenate all signatures together, which may lead tobig message size and requires recipient to verify all signatures. We call a keyaggregation e ective if1. The aggregated key size should remain relatively constant regardless ofnumber of participants.2. The veri cation time of the key should remain relatively constant re-gardless of number of participants.Here the term “key“ may refer to any types of primitives, such as secret keys,public keys, signatures, etc.In BBFT, we use BLS Boneh{Lynn{Shacham multi-signature scheme[4,5, 3] to e ectively aggregate signatures. With BLS, it’s possible to aggre-gate all types of primitives and the result is always another valid primitive.Primitives which were already aggregated can also be further aggregated in-crementally, independent from the order in which it happens. With thisproperty, the aggregated signature size remains constant regardless of num-ber of participating signatures. Another unique property of BLS is that itcan be done in single round, unlike Schnorr signature scheme[11], where apre-commitment setup is needed, which leads to multiple rounds of communi-cation. This feature makes it ideal for distributed and trust-less environment.Let n be the number of participants, m be the message communicatedamong them. The BLS signature aggregation scheme in BBFT works asfollows5Setup We choose an e ciently computable non-degenerate bilinearpairing e G0 G1 GT[3], where G0, G1, and GT are groups of primeorder q. Let g0 and g1 be the generators of G0 and G1 respectively. Wealso choose two hash functions H0 MG0, a mapping from messagespace to G0, and H1 Gn1 Zq.KeyGen Every participant picks a secret key sk2Zq, and shares itspublic key pk gsk H1gsk1 1 with each other. pk2G1.Signsk, m Participant with secret key sk signs m and outputs sig-nature H0msk H1gsk1 . 2G0.Aggregate 1, 2,., n Upon receipt of multiple signatures on mes-sage m, the aggregated signature Qni1 i is computed as the prod-uct of individual signatures i. 2G0.Verify , m Participant veri es an aggregated signature on m byrst computing aggregated public key Qni1pki, as the product ofindividual public key pki. 2 G1. Then veri cation is done by thetwo-pairing check e ;g1 eH0m; .Pairing operation is known to be expensive, it is order of magnitude slowerthan typical ECDSA, such as Schnorr signature[2, 11]. However, in the caseof same message, the number of pairing is limited to 2 for every aggregatedsignature veri ed regardless of number of signatures.6 ConclusionWe present BBFT, an e cient byzantine fault tolerant consensus algorithm.The model achieves On communication complexity with certain limit onnumber of gateway nodes. It is worth noting that as a highly exible and re-con gurable model, zoning and aggregation techniques proposed here are notnecessarily the only choices. Depending on the real use case, other techniquescan be easily integrated into the consensus model.6References[1] B. Awerbuch. \Optimal Distributed Algorithms for Minimum WeightSpanning Tree, Counting, Leader Election, and Related Problems“.In Proceedings of the Nineteenth Annual ACM Symposium on Theoryof Computing. STOC ’87. New York, New York, USA ACM, 1987,pp. 230{240. isbn 0-89791-221-7. doi 10.1145/28395.28421. urlhttp//doi.acm.org/10.1145/28395.28421.[2] Alexander Block. BLS Is it really that slow url https//blog.dash.org/bls-is-it-really-that-slow-4ca8c1fcd38e. accessed05.21.2019.[3] Dan Boneh, Manu Drijvers, and Gregory Neven. \Compact Multi-signatures for Smaller Blockchains“. In Advances in Cryptology { ASI-ACRYPT 2018. Ed. by Thomas Peyrin and Steven Galbraith. ChamSpringer International Publishing, 2018, pp. 435{464. isbn 978-3-030-03329-3.[4] Dan Boneh, Ben Lynn, and Hovav Shacham. \Short Signatures fromthe Weil Pairing“. In Proceedings of the 7th International Conferenceon the Theory and Application of Cryptology and Ination Secu-rity Advances in Cryptology. ASIACRYPT ’01. Berlin, HeidelbergSpringer-Verlag, 2001, pp. 514{532. isbn 3-540-42987-5. url http//dl.acm.org/citation.cfmid647097.717005.[5] Dan Boneh et al. \Aggregate and Veri ably Encrypted Signaturesfrom Bilinear Maps“. In Proceedings of the 22Nd International Con-ference on Theory and Applications of Cryptographic Techniques. EU-ROCRYPT’03. Warsaw, Poland Springer-Verlag, 2003, pp. 416{432.isbn 3-540-14039-5. url http//dl.acm.org/citation.cfmid1766171.1766207.[6] Miguel Castro and Barbara Liskov. \Practical Byzantine Fault Toler-ance“. In Proceedings of the Third Symposium on Operating SystemsDesign and Implementation. OSDI ’99. New Orleans, Louisiana, USAUSENIX Association, 1999, pp. 173{186. isbn 1-880446-39-1. urlhttp//dl.acm.org/citation.cfmid296806.296824.[7] E. W. Dijkstra. \A note on two problems in connexion with graphs“.In Numerische Mathematik 1.1 Dec. 1959, pp. 269{271. issn 0945-3245. doi 10.1007/BF01386390. url https//doi.org/10.1007/BF01386390.7[8] Michael L. Fredman and Robert Endre Tarjan. \Fibonacci Heaps andTheir Uses in Improved Network Optimization Algorithms“. In J.ACM 34.3 July 1987, pp. 596{615. issn 0004-5411. doi 10.1145/28869.28874. url http//doi.acm.org/10.1145/28869.28874.[9] R. G. Gallager, P. A. Humblet, and P. M. Spira. \A Distributed Al-gorithm for Minimum-Weight Spanning Trees“. In ACM Trans. Pro-gram. Lang. Syst. 5.1 Jan. 1983, pp. 66{77. issn 0164-0925. doi10.1145/357195.357200. url http//doi.acm.org/10.1145/357195.357200.[10] Joseph B. Kruskal. \On the Shortest Spanning Subtree of a Graphand the Traveling Salesman Problem“. In Proceedings of the AmericanMathematical Society 7.1 1956, pp. 48{50. issn 00029939, 10886826.url http//www.jstor.org/stable/2033241.[11] Gregory Maxwell et al. \Simple Schnorr multi-signatures with appli-cations to Bitcoin“. In Designs, Codes and Cryptography Feb. 2019.doi 10.1007/s10623-019-00608-x.[12] Alfred J. Menezes. Elliptic Curve Public Key Cryptosystems. Norwell,MA, USA Kluwer Academic Publishers, 1994. isbn 0792393686.[13] Seth Pettie and Vijaya Ramachandran. \An Optimal Minimum Span-ning Tree Algorithm“. In J. ACM 49.1 Jan. 2002, pp. 16{34. issn0004-5411. doi 10.1145/505241.505243. url http//doi.acm.org/10.1145/505241.505243.[14] R. C. Prim. \Shortest connection networks and some generalizations“.In The Bell System Technical Journal 36.6 Nov. 1957, pp. 1389{1401. issn 0005-8580. doi 10.1002/j.1538-7305.1957.tb01515.x.[15] R. L. Rivest, A. Shamir, and L. Adleman. \A for ObtainingDigital Signatures and Public-key Cryptosystems“. In Commun. ACM21.2 Feb. 1978, pp. 120{126. issn 0001-0782. doi 10.1145/359340.359342. url http//doi.acm.org/10.1145/359340.359342.[16] Harmony Team. Harmony Technical Whitepaper. url https//harmony.one/whitepaper.pdf. accessed 05.21.2019.[17] Gene Tsudik. \Message Authentication with One-way Hash Functions“.In SIGCOMM Comput. Commun. Rev. 22.5 Oct. 1992, pp. 29{38.issn 0146-4833. doi 10.1145/141809.141812. url http//doi.acm.org/10.1145/141809.141812.8