Applied Science, Faculty of
Engineering, School of (Okanagan)
DSpace
UBCO
Yazdinejad, Saeid
Master of Applied Science - MASc
University of British Columbia
This thesis proposes two novel solutions, Aurora and Phoenix, to address the file downloading problem in distributed networks vulnerable to Byzantine faults—scenarios where network components may fail or behave maliciously. Both solutions employ advanced erasure coding and cryptographic schemes to ensure reliable data transfer and integrity verification. Aurora utilizes Maximum Distance Separable (MDS) codes paired with vector commitments like KZG, optimizing for robust data redundancy and secure verification processes. Phoenix, conversely, leverages rateless codes alongside homomorphic commitments, offering greater flexibility and efficiency in data recovery under varying network conditions. Implemented within the HotStuff protocol—a Byzantine Fault Tolerant (BFT) consensus algorithm—Aurora demonstrates enhanced synchronization efficiencies, significantly reducing the overhead in networks with up to 10% faulty nodes. This work contributes to robust and efficient data dissemination protocols that optimize bandwidth and storage utilization, essential for maintaining integrity and performance in critical network infrastructures.
Byzantine-Tolerant Erasure Coding forBlockchainsbySaeid YazdinejadA THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinThe College of Graduate Studies(Electrical Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)October 2024© Saeid Yazdinejad, 2024The following individuals certify that they have read and recommend tothe College of Graduate Studies for acceptance a thesis entitled:Byzantine-Tolerant Erasure Coding for Blockchainssubmitted by Saeid Yazdinejad in partial fulfilment of the requirementsof the degree of Master of Applied ScienceChen Feng, School of EngineeringSupervisorAnas Chaaban, School of EngineeringSupervisory Committee MemberZehua Wang, University of British Columbia - VancouverSupervisory Committee MemberFatemeh Hendijani Fard, Irving K. Barber Faculty of ScienceUniversity ExamineriiAbstractThis thesis proposes two novel solutions, Aurora and Phoenix, to ad-dress the file downloading problem in distributed networks vulnerable toByzantine faults—scenarios where network components may fail or behavemaliciously. Both solutions employ advanced erasure coding and crypto-graphic schemes to ensure reliable data transfer and integrity verification.Aurora utilizes Maximum Distance Separable (MDS) codes paired with vec-tor commitments like KZG, optimizing for robust data redundancy and se-cure verification processes. Phoenix, conversely, leverages rateless codesalongside homomorphic commitments, offering greater flexibility and effi-ciency in data recovery under varying network conditions. Implementedwithin the HotStuff protocol—a Byzantine Fault Tolerant (BFT) consensusalgorithm—Aurora demonstrates enhanced synchronization efficiencies, sig-nificantly reducing the overhead in networks with up to 10% faulty nodes.This work contributes to robust and efficient data dissemination protocolsthat optimize bandwidth and storage utilization, essential for maintainingintegrity and performance in critical network infrastructures.iiiLay SummaryThis thesis presents two solutions, Aurora and Phoenix, aimed at im-proving how files are downloaded in networks that may encounter disrup-tions or malfunctions, commonly referred to as Byzantine faults. Auroraensures that data is consistently reliable and secure, preventing loss evenwhen parts of the network fail. However, Phoenix adapts more dynami-cally, and efficiently recovering data that gets corrupted due to changingnetwork conditions. Aurora was applied to the HotStuff protocol, a sys-tem designed to secure data across networks where faults are likely. Auroraoutperformed, improving data synchronization ten times compared to theexisting solutions like Diem (a blockchain system developed by former Metaemployees). This research is relevant for technologies like blockchain, wheresafeguarding data integrity and maintaining efficient operations are critical,ensuring that networks operate smoothly even under challenging conditions.ivPrefaceSome sections of this thesis are based on joint work with Dr. MohammadJalalzai and Prof. Chen Feng. Portions of this work were presented at theCanadian Workshop on Information Theory (CWIT) 2024, Vancouver, BC,and a full version is scheduled for submission in a top-tier journal. Genera-tive artificial intelligence was used for typo and grammatical correction.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Our Contribution . . . . . . . . . . . . . . . . . . . . . . . . . 5Chapter 2: Preliminaries . . . . . . . . . . . . . . . . . . . . . . 62.1 What is a blockchain? . . . . . . . . . . . . . . . . . . . . . . 62.2 BFT-Based Algorithms . . . . . . . . . . . . . . . . . . . . . 72.2.1 HotStuff . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3 Erasure codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3.1 [n, k] Optimal Erasure Codes . . . . . . . . . . . . . . 122.3.2 Rateless Codes . . . . . . . . . . . . . . . . . . . . . . 122.4 Cryptographic Primitives . . . . . . . . . . . . . . . . . . . . 182.4.1 Vector Commitment . . . . . . . . . . . . . . . . . . . 182.4.2 Merkle Proof . . . . . . . . . . . . . . . . . . . . . . . 192.4.3 KZG Commitment . . . . . . . . . . . . . . . . . . . . 202.4.4 Homomorphic Commitments . . . . . . . . . . . . . . 222.4.5 Pedersen Commitment . . . . . . . . . . . . . . . . . . 22viTABLE OF CONTENTSChapter 3: Byzantine-Tolerant Erasure Coding Protocols . . 243.1 Aurora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.1.1 Setup Phase . . . . . . . . . . . . . . . . . . . . . . . . 243.1.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 253.1.3 Time Complexity Analysis . . . . . . . . . . . . . . . . 293.1.4 Proof of Correctness . . . . . . . . . . . . . . . . . . . 323.1.5 KZG Commitment . . . . . . . . . . . . . . . . . . . . 343.1.6 Merkle Proof in Aurora Protocol . . . . . . . . . . . . 343.2 Phoenix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.2.1 Setup Phase . . . . . . . . . . . . . . . . . . . . . . . . 353.2.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 353.2.3 Time Complexity Analysis . . . . . . . . . . . . . . . . 403.2.4 Proof of Correctness . . . . . . . . . . . . . . . . . . . 42Chapter 4: Application in Data Synchronization Problem . . 444.1 What is the Data Synchronization Problem in HotStuff? . . . 444.2 Applying Aurora or Phoenix for Faster Node Recovery . . . . 45Chapter 5: Evaluation of the Aurora Protocol . . . . . . . . . 505.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . 505.1.1 Network Configuration . . . . . . . . . . . . . . . . . . 505.1.2 Coding and Commitment Schemes . . . . . . . . . . . 515.2 Adversary Model . . . . . . . . . . . . . . . . . . . . . . . . . 515.3 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . 525.3.1 Experiment 1: Performance Evaluation of Aurora . . . 525.3.2 Experiment 2: Impact of Faulty Nodes on System Per-formance . . . . . . . . . . . . . . . . . . . . . . . . . 535.3.3 Discussion on Performance Fluctuations . . . . . . . . 545.4 Experiment 3: Handling Fewer Available Nodes . . . . . . . . 555.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55Chapter 6: Evaluation of the Phoenix Protocol . . . . . . . . . 576.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . 576.1.1 Data Preparation . . . . . . . . . . . . . . . . . . . . . 576.1.2 Encoding Process . . . . . . . . . . . . . . . . . . . . . 576.1.3 Commitment Generation . . . . . . . . . . . . . . . . 586.1.4 Verification and Decoding . . . . . . . . . . . . . . . . 596.1.5 Performance Measurement . . . . . . . . . . . . . . . . 596.2 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . 606.2.1 Encoding and Decoding Performance . . . . . . . . . . 60viiTABLE OF CONTENTS6.2.2 Commitment Generation and Verification Performance 606.2.3 Scalability Analysis . . . . . . . . . . . . . . . . . . . 616.2.4 Implications for Practical Deployment . . . . . . . . . 62Chapter 7: Discussion . . . . . . . . . . . . . . . . . . . . . . . . 637.1 Translating Performance Improvements into TPS and La-tency Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . 637.1.1 Impact on TPS . . . . . . . . . . . . . . . . . . . . . . 637.1.2 Reduction in Transaction and Network Latency . . . . 647.2 Comparison of Merkle Proofs and KZG Commitments in Aurora 647.3 Why is coding necessary? . . . . . . . . . . . . . . . . . . . . 647.4 Lack of Resources for Simulating Phoenix . . . . . . . . . . . 667.5 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667.5.1 Computational Intensity . . . . . . . . . . . . . . . . . 667.5.2 Implementation Complexity . . . . . . . . . . . . . . . 667.5.3 Computationally Bounded Adversary . . . . . . . . . 67Chapter 8: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 688.1 Key Findings . . . . . . . . . . . . . . . . . . . . . . . . . . . 688.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 68Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70viiiList of TablesTable 4.1 Definition of Parameters in the Data SynchronizationProblem in HotStuff . . . . . . . . . . . . . . . . . . . 45Table 4.2 Parameters in Example 1 of Data Synchronization Prob-lem in HotStuff . . . . . . . . . . . . . . . . . . . . . . 47Table 4.3 Parameters definition Example 2 of Data Synchroniza-tion Problem in HotStuff . . . . . . . . . . . . . . . . . 48Table 4.4 Parameters in Example 2 of Data Synchronization Prob-lem in HotStuff . . . . . . . . . . . . . . . . . . . . . . 48Table 5.1 Time metrics for computing coded chunks and vectorcommitments for 1,000,000 Ethereum transactions us-ing the Aurora protocol . . . . . . . . . . . . . . . . . 55Table 7.1 Comparison of Merkle Proofs and KZG Commitmentsin Aurora . . . . . . . . . . . . . . . . . . . . . . . . . 65ixList of FiguresFigure 1.1 The Byzantine Generals Problem Diagram, Source:[Mak18] . . . . . . . . . . . . . . . . . . . . . . . . . . 2Figure 1.2 Asynchronous Verifiable Information Dispersal Dia-gram . . . . . . . . . . . . . . . . . . . . . . . . . . . 3Figure 2.1 Practical Byzantine Fault Tolerance CommunicationDiagram . . . . . . . . . . . . . . . . . . . . . . . . . 8Figure 2.2 HotStuff Communication Diagram . . . . . . . . . . . 10Figure 2.3 Peeling Decoding phase 0 . . . . . . . . . . . . . . . . 15Figure 2.4 Peeling Decoding phase 1 . . . . . . . . . . . . . . . . 16Figure 2.5 Peeling Decoding final phase . . . . . . . . . . . . . . 17Figure 3.1 Aurora - [n, k] MDS codes . . . . . . . . . . . . . . . 25Figure 3.2 Phoenix - Rateless codes . . . . . . . . . . . . . . . . 36Figure 4.1 Applying Aurora or Phoenix to HotStuff for increas-ing the efficiency of data synchronization . . . . . . . 45Figure 5.1 Synchronization times for the Aurora protocol undervarious network conditions. Aurora maintains lowsynchronization times even in the presence of faultynodes, demonstrating its scalability and robustness. . 52Figure 5.2 Scalability of Aurora under varying numbers of faultynodes. Aurora maintains robust performance, withonly moderate increases in retrieval time as the num-ber of faulty nodes increases. . . . . . . . . . . . . . . 54Figure 6.1 Performance evaluation of the Phoenix Protocol fordifferent values of k. . . . . . . . . . . . . . . . . . . . 61xAcknowledgementsI would like to express my deepest gratitude to my wife for her un-wavering support and encouragement throughout this journey. I am alsoimmensely grateful to my parents for their constant love and belief in me.A special thanks to my supervisor, Prof. Chen Feng, whose guidance andmentorship have been invaluable in shaping this work.xiChapter 1IntroductionDistributed systems have been one of the main players in modern com-puting for many years, supporting various applications like peer-to-peer net-works and cloud computing. These systems work by having multiple com-puters, often located in different places, share tasks and resources. However,because these systems are spread out, they face challenges in maintainingdata consistency and reliability during failures.One of the oldest and most important problems in this area is known asthe Byzantine Generals Problem. This problem, introduced in 1982 by LeslieLamport and others [LSP82], describes a situation where several actors (ornodes) need to agree on a common plan, even when some of them might actunpredictably or dishonestly (Figure 1.1). They call these actors Byzantine.Solving this problem is crucial for ensuring that a distributed system canfunction correctly, even when some parts of it are unreliable or malicious.Over the years, many algorithms have been developed to tackle thisproblem, with Byzantine Fault Tolerance (BFT) being a key concept. In1999, Miguel Castro and Barbara Liskov introduced the Practical ByzantineFault Tolerance (PBFT) algorithm [CL99], which was one of the first to beusable in real-world systems. However, while PBFT was a big step forward,it had some limitations, particularly in terms of how well it could scale asthe system grew larger.The arrival of blockchain technology in 2008, with the introduction ofBitcoin by the mysterious Satoshi Nakamoto [Nak09], brought new attentionto BFT algorithms. Blockchain networks, by design, are decentralized andrequire strong fault tolerance to ensure they can operate securely, even whensome nodes in the network behave badly. This has led to renewed interestand significant research in improving BFT algorithms to meet the demandsof blockchain systems.This breakthrough inspired scientists to try one more time to solve theefficiency problem of BFT consensus algorithms. One of the more recentadvancements in this area is the HotStuff algorithm [YMR+18], which ad-dresses some of the scalability and efficiency problems found in earlier BFTprotocols like PBFT. HotStuff reduces the complexity of communication be-1Figure 1.1: The Byzantine Generals Problem Diagram, Source: [Mak18]tween nodes, making it more suitable for large-scale blockchain networks.This algorithm has set the stage for further innovations in making BFT sys-tems more efficient and capable of handling the needs of modern distributednetworks.Now, imagine a client who wants to download a file in a Byzantine en-vironment. The most naive solution is downloading the file from 2/3 of thenodes (because, at most, 1/3 of nodes can be malicious in a BFT system).It shows the importance of achieving sufficient tolerance against Byzantineactors is crucial to ensure data availability. Although simple data replica-tion, which involves storing multiple copies of the same data across differ-ent nodes, provides some level of fault tolerance, it comes with significantdrawbacks. Replication can lead to high bandwidth and storage demands,making it impractical in resource-constrained environments. To overcomethese limitations, researchers have developed more efficient solutions, suchas erasure coding, which offers robust fault tolerance with lower resourcerequirements.In a nutshell, erasure coding algorithms and error-correcting codes workby breaking data into smaller pieces and creating additional pieces that canbe used to reconstruct the original data if some of the pieces are lost ordamaged. This method is more efficient than simply making multiple copiesof the data, which would require much more storage and bandwidth.With this inspiration in mind, one of the notable applications of erasurecoding in BFT systems is seen in the development of Asynchronous Verifi-able Information Dispersal (AVID) protocols [CT05]. AVID protocols aredesigned to securely distribute and verify data across a network, even in thepresence of faulty or malicious nodes. As illustrated in Figure 1.2, they work21.1. RELATED WORKFigure 1.2: Asynchronous Verifiable Information Dispersal Diagramby dispersing data in a way that each piece can be independently verifiedby the receiving nodes.By observing these developments in addressing the file downloadingproblem in distributed networks, the Secure Fountain (SeF) paper [KCR19]presented an architecture that aimed to reduce storage and bandwidth costsby leveraging rateless erasure coding techniques during the bootstrappingprocess of blockchain networks. The SeF architecture showed promise inmitigating the initial synchronization costs, but it faced limitations. Forexample, SeF could not effectively distinguish between valid and maliciousrequests, leading to resource wastage when dealing with malicious actors.Furthermore, SeF’s decode-and-then-verify approach was found to be ineffi-cient, as it allowed invalid data to be processed before errors were detected.In this thesis, we build on these developments by proposing two newprotocols, Aurora and Phoenix. These protocols are designed to improve theefficiency and security of downloading a file in the Byzantine environmentby providing an application for data synchronization in the static HotStuffconsensus algorithm.1.1 Related WorkThe synchronization of data in Byzantine Fault Tolerant (BFT) consen-sus protocols remains a critical challenge in blockchain systems. Kadhe etal. proposed Secure Fountain Codes (SeF) to mitigate storage and band-width costs during blockchain bootstrapping [KCR19]. Although SeF codes31.1. RELATED WORKreduce initial costs, they face significant limitations: they cannot distinguishbetween valid and malicious requests, are vulnerable to opaque droplet at-tacks, and can only detect murky droplets post-decoding, leading to resourcewastage. This decode-and-then-verify approach is inefficient. Our modularapproach allows clients to detect invalid responses and opaque and murkydroplets beforehand, reducing bandwidth consumption and enhancing reli-ability and efficiency.Recent work by Das et al. explores asynchronous data disseminationusing Reed-Solomon codes [DXR21, RS60]. While Reed-Solomon codes areknown for their robustness, they can be computationally expensive1 andthe solution does not consider Byzantine attacks, which can severely impactperformance. Another study introduces Proof of Availability and Retrieval(PoA&R) protocols to address data synchronization in blockchain networks,focusing on a probabilistic retrieval mechanism to minimize communicationcosts [GKS+22]. These approaches, while innovative, still leave room forimprovement in terms of efficiency and robustness.In contrast, our method leverages MDS codes, rateless codes, or a combi-nation of both, along with vector and homomorphic commitments, providinggreater flexibility, robustness, and enhanced Byzantine fault tolerance.The Diem protocol2 employs sequential streaming and replication meth-ods for data synchronization, which can lead to significant delays and band-width inefficiencies, particularly in large-scale networks [Ass21]. Our solu-tions, Aurora and Phoenix utilize advanced erasure coding techniques toenable parallel data requests and efficient verification, resulting in fastersynchronization and reduced bandwidth usage. This approach offers betterscalability and robustness compared to Diem’s method.Nazirkhanova et al. presented a communication- and storage-efficientprotocol using linear erasure-correcting codes and homomorphic vector com-mitments, focusing on the application requirements for rollups [NNT23].This protocol, Semi-AVID-PR, improves data retrieval guarantees with-out requiring comprehensive termination properties, thereby avoiding fallingback to empty blocks in adverse conditions. However, while this solutionaddresses many aspects of data availability and integrity, it does not fullyexplore the use of rateless codes for data dissemination. Our design is mod-ular, allowing for the incorporation of both MDS and rateless codes, thereby1Although they are computationally expensive, they are highly optimized over the pastdecade and adopted by the industry2The Diem protocol is a blockchain-based payment system designed by Facebook toenable fast, low-cost, and secure financial transactions globally, originally intended for usewith the Diem (formerly Libra) digital currency.41.2. OUR CONTRIBUTIONproviding enhanced flexibility and robustness in data synchronization pro-cesses for BFT consensus protocols.Another recent work by Alhaddad et al. introduced an erasure codingproof (ECP) system that provides succinct and non-interactive proofs forerasure-coded fragments [ADVZ21]. Their design focuses specifically on theuse of [n, k] MDS codes that it is providing a robust and efficient methodfor verifying erasure-coded data in distributed systems. However, their ap-proach is not modular, as it does not accommodate other types of erasurecodes, such as rateless codes. In contrast, our design offers greater flexibil-ity by supporting both MDS and rateless codes, which makes it adaptableto a wider range of applications and network conditions. This modularityensures that our protocol can maintain efficiency and robustness even indynamic environments where the optimal type of erasure code may vary.1.2 Our ContributionThis thesis presents two innovative solutions, Aurora and Phoenix, toaddress the challenges of file downloading problems with a focus on datasynchronization in static HotStuff consensus protocols within blockchainsystems. Aurora employs Maximum Distance Separable (MDS) codes andvector commitments to ensure robust data redundancy and integrity verifi-cation. This approach enables clients to identify invalid responses and datachunks before decoding, a method we refer to as verify-and-then-decode.On the other hand, Phoenix complements Aurora by utilizing ratelesscodes and homomorphic commitments, offering flexible and efficient datarecovery under varying network conditions while maintaining data integrity.The integration of Aurora and Phoenix into the HotStuff BFT consensusprotocol facilitates parallel data requests and efficient verification, resultingin faster synchronization times and reduced bandwidth usage. Comparedto existing methods like the Diem protocol, our approach provides superiorscalability and robustness, particularly in large-scale networks.By combining MDS and rateless codes with advanced cryptographicschemes such as vector, polynomial, and homomorphic commitments, oursolutions offer enhanced flexibility, robustness, and Byzantine fault toler-ance. This comprehensive approach surpasses current methods that relysolely on any off-the-shelf coding algorithms and cryptographic techniques.5Chapter 2PreliminariesThis chapter provides the foundational concepts and background infor-mation necessary to understand the proposed solutions presented in this the-sis. It covers essential topics such as blockchain technology, erasure codes,and relevant cryptographic techniques, which will be elaborated upon insubsequent sections. Those who are familiar with these concepts can skipthis chapter.2.1 What is a blockchain?Blockchain is a decentralized, distributed ledger technology that recordstransactions across multiple computers to ensure security and transparencywithout the need for a central authority. Each block in a blockchain containsa list of transactions and a cryptographic hash of the previous block, linkingeach block together in a chain. This structure ensures that once data isrecorded in a block, it is difficult to alter without altering all subsequentblocks, providing data integrity and immutability.Blockchains are used in various applications, such as cryptocurrency,supply chain management, and digital identity verification. The most well-known application of blockchain technology is Bitcoin, introduced by ananonymous entity known as Satoshi Nakamoto in 2008 [Nak09]. Since then,numerous blockchain platforms have been developed, each with unique fea-tures and capabilities. Ethereum, for example, extends the basic blockchainconcept by incorporating smart contracts, which are self-executing contractswith the terms directly written into code.The decentralized nature of blockchain ensures that no single entity hascontrol over the entire network, enhancing security and reducing the riskof centralized points of failure. Consensus mechanisms are used to agreeon transaction validity and add new blocks to the chain, ensuring that allparticipants in the network maintain a consistent view of the ledger.Consensus algorithms are fundamental to the functioning of blockchainnetworks, ensuring that all nodes in the network agree on the state of the62.2. BFT-BASED ALGORITHMSledger. These algorithms are designed to achieve agreement among dis-tributed nodes, even in the presence of faults or malicious actors. Differentblockchain platforms use different consensus mechanisms, each with its ad-vantages and trade-offs. There are different consensus algorithms, and BFTis one of them. In the next section, we provide an overview of the mechanismbehind BFT-based consensus algorithms.2.2 BFT-Based AlgorithmsAs previously mentioned, BFT consensus algorithms are designed toensure that distributed systems can continue to function correctly even whensome nodes behave arbitrarily or maliciously. These algorithms solve theByzantine Generals Problem. BFT algorithms are categorized into threemain types based on their synchronization model: synchronous, semi-synchronous, and asynchronous.Synchronous BFT algorithms assume that there is a known upperbound on the time it takes for messages to be delivered across the network.This model simplifies consensus because nodes can be certain that messageswill arrive within a specific time frame. However, this assumption is oftenunrealistic in real-world systems where network delays can be unpredictable.An example of a synchronous BFT algorithm is the Dolev-Strong protocol[DFF+82], which operates under the assumption that message delivery timesare bounded and known to all participants.Semi-synchronous BFT algorithms relax the strict timing assump-tion by allowing messages to be delivered within some unspecified but boundedtime frame. This model is more practical for real-world applications, asit balances between the idealized synchronous and the fully asynchronousmodels. An example of a semi-synchronous BFT algorithm is PracticalByzantine Fault Tolerance (PBFT) [CL99], proposed by Castro and Liskovin 1999. PBFT operates under a semi-synchronous model where messagesare assumed to be eventually delivered but without a strict upper boundon delivery time. As shown in Figure 2.1, PBFT uses a primary-backupreplication model, where the leader (or primary) proposes a block, and thebackups (other nodes) participate in multiple rounds of voting to reach aconsensus. Although PBFT provides strong fault tolerance, it does so at thecost of high communication overhead, which can limit its scalability in largernetworks. Another example of these BFT algorithms is HotStuff [YMR+18],which we will discuss in the next section.Asynchronous BFT algorithms operate under the assumption that72.2. BFT-BASED ALGORITHMSFigure 2.1: Practical Byzantine Fault Tolerance Communication Diagramthere are no guarantees regarding the timing of message delivery, makingthem highly robust in environments where network conditions are unpre-dictable or where delays are indefinite. In a fully asynchronous model, mes-sages may be delayed indefinitely, yet the algorithm must still ensure thatconsensus can eventually be reached despite these uncertainties.However, achieving consensus in a fully asynchronous system is subjectto a fundamental limitation known as the FLP impossibility, named afterFischer, Lynch, and Paterson, who proved in 1985 that no deterministic con-sensus algorithm can guarantee reaching consensus in a fully asynchronousnetwork if even a single node may fail [FLP85]. The FLP result implies thatin such a system, it’s impossible to simultaneously achieve all three of thefollowing properties:− Safety: all non-faulty nodes must agree on the same value− Liveness: the system must eventually make progress− Fault Tolerance: the system must continue to operate even if somenodes failDue to the FLP impossibility, fully asynchronous BFT algorithms musteither make compromises, such as accepting probabilistic guarantees or relyon randomization to break ties and make progress. An example of such analgorithm is the Randomized Byzantine Agreement (RBA) [Tou84]. RBA82.2. BFT-BASED ALGORITHMSuses randomization techniques to achieve consensus without relying on anytiming assumptions, thereby circumventing the deterministic limits imposedby FLP. While asynchronous algorithms like RBA are theoretically appeal-ing due to their robustness and ability to function without timing guarantees,they are often more complex and less efficient in practice compared to semi-synchronous or synchronous algorithms. This complexity arises from theneed to account for all possible delays and to ensure that the randomizationtechniques lead to eventual consensus within a reasonable timeframe.A key concept in BFT algorithms is the view. A view represents aspecific period during which a designated leader is responsible for proposingnew blocks. The leader is selected through a process that ensures fairnessand resilience to faults. If the leader fails to perform their duties—due toa fault or malicious behavior—nodes can trigger a view change to selecta new leader. This mechanism allows the system to maintain progress andconsensus, even when some nodes are unreliable.Another important component in BFT algorithms, particularly in semi-synchronous and asynchronous models, is the pacemaker. The pacemakeris responsible for coordinating the timing of view changes and ensuring thatthe system can smoothly transition from one view to another. By managingthese transitions, the pacemaker helps to maintain the liveness of the system,ensuring that consensus can be reached without unnecessary delays.BFT algorithms can also be classified as static or dynamic.Static BFT algorithms assume a fixed set of nodes that participatein the consensus process. This model is simpler but less flexible, as it doesnot easily accommodate changes in the network, such as nodes joining orleaving. An example of a static BFT algorithm is the original PBFT, whichoperates with a predetermined set of nodes.Dynamic BFT algorithms, on the other hand, allow the set of partici-pating nodes to change over time. This flexibility makes dynamic algorithmsmore suitable for environments like blockchain networks, where nodes mayfrequently enter or exit the network. An example of a dynamic BFT algo-rithm is Algorand [GHM+17], which allows for the dynamic participationof nodes in its consensus process. There are also recent research papers onthis topic, such as [DZ22] and [MMR22], but they are still not quite readyto be adopted by the industry.Each type of BFT algorithm has its own set of advantages and limita-tions. Synchronous algorithms are straightforward but impractical for mostreal-world applications, while semi-synchronous algorithms like PBFT offera balance between robustness and practicality, with increased complexityand communication costs compared to synchronous models. The choice be-92.2. BFT-BASED ALGORITHMSFigure 2.2: HotStuff Communication Diagramtween static and dynamic models depends on the specific requirements ofthe system, such as the need for flexibility or the importance of minimizingoverhead.In the next section, we will explain the HotStuff algorithm in detail.We need this information to grasp how to apply the Aurora or Phoenixprotocol to HotStuff to solve the data synchronization problem. Those whoare familiar with the system can skip the next section.2.2.1 HotStuffHotStuff [YMR+18] is a more recent advancement in BFT consensusalgorithms designed to address the scalability and efficiency limitations ofearlier protocols like PBFT. HotStuff reduces communication complexity byintroducing a linear communication pattern and supporting pipelining andconcurrent execution of consensus rounds.As illustrated in Figure 2.2, HotStuff operates in four steps: Prepare,Pre-commit, commit, and decide. HotStuff’s design makes it highly suitablefor large-scale blockchain networks, as it can handle a high number of nodeswith reduced overhead. In the next section, we delve into the HotStuff’salgorithm.102.2. BFT-BASED ALGORITHMSAlgorithmHotStuff improves upon other BFT-based algorithms by reducing com-munication complexity to linear, enhancing scalability and efficiency. Itsupports pipelining and concurrent execution, which increases throughputand lowers latency. The use of Quorum Certificates (QC) with BLS aggre-gate signatures3 simplifies agreement processes, and the efficient view changemechanism ensures robust performance even during leader transitions.As previously mentioned, the HotStuff algorithm operates through aseries of steps to achieve consensus in a BFT environment. These steps are:prepare, pre-commit, commit, and decide. The consensus process begins withthe Proposal phase, initiated by the chosen leader in the current view, topropose a new block. This new block contains transactions and the previousblock’s hash.Prepare In the prepare phase, the leader sends the block to all repli-cas. Each node, upon receiving the new block, starts to verify it and thenresponds with a prepare message as a vote for the block. Next, the leadercollects prepare messages from replicas to form a QC with BLS aggregatesignatures. The leader also creates a bitmap to track which nodes havesigned, with the length of the bitmap equal to the total number of nodes.This QC represents the proof of consensus of the majority of replicas.Pre-commit In the pre-commit phase, the leader broadcasts the QCalong with the bitmap to all replicas. The leader then aggregates enoughvotes on the QC to form another QC and broadcasts the new block alongwith the new QC. Each replica, upon receiving the new QC, starts to verifyit.Commit If the QC is valid, the replicas respond with a commit message.The leader collects the majority of commit votes to finalize the block.Decide After the leader collects the majority of votes, the process movesto the decide phase, where the block is finalized. If the leader fails to gatherthe necessary votes, a View Change protocol is triggered to select a newleader for the current view.In the application chapter, we will explain which part of this algorithmmust change to apply the proposed protocol. However, before understandingthe method, we need to be familiar with erasure coding algorithms. The nextsection is devoted to this subject.3BLS aggregate signatures simplify the agreement process. One can also use thresholdsignatures [Sha79], although the design would be a bit different.112.3. ERASURE CODES2.3 Erasure codesErasure codes are a method of data protection in storage and transmis-sion systems. They work by breaking data into chunks of data and thencreating additional redundant pieces so that the original data can be recon-structed even if some fragments are lost or corrupted. This section discussestwo types of erasure codes: [n, k] optimal erasure codes and rateless codes.2.3.1 [n, k] Optimal Erasure Codes[n, k] Optimal erasure codes, also known as Maximum Distance Sepa-rable (MDS) codes, are designed to provide the best possible redundancy.Here, n is the total number of data and parity blocks, and k is the numberof original data blocks. An example of these codes is Reed-Solomon codes[RS60], which are widely used in various applications such as data storage,CDs, and DVDs.In Reed-Solomon codes, the data is divided into k blocks, and n − kparity blocks are generated. The key feature of these codes is that any kout of n blocks are sufficient to reconstruct the original data. This makesthem very robust against data loss. However, the encoding and decodingprocesses are computationally intensive, which can be a drawback in systemswith limited resources.The encoding process involves creating a polynomial that fits the datapoints and then evaluating this polynomial at different points to generatethe parity blocks. The decoding process uses algorithms like the Berlekamp-Massey algorithm to reconstruct the original data from a subset of theblocks.2.3.2 Rateless CodesUnlike traditional erasure codes, rateless codes do not have a fixed redun-dancy ratio. They can generate an unlimited number of encoded blocks fromthe original data. This makes them highly flexible and efficient, especiallyin environments with unpredictable network conditions.A well-known example of rateless codes is Luby Transform (LT) codes[Lub02]. LT codes generate encoded blocks by XORing random subsetsof the original data blocks. The decoding process uses a technique calledbelief propagation to recover the original data. If enough encoded blocksare received, the original data can be reconstructed with high probability.Another example is Raptor codes, which build on LT codes by adding a122.3. ERASURE CODESpre-coding step. This step uses a traditional erasure code like a low-densityparity-check (LDPC) [FLMY03] code to preprocess the data before applyingthe LT encoding. This enhances the robustness and reduces the decodingcomplexity compared to LT codes alone.Rateless codes are particularly useful in applications like video streamingand file distribution, where the network conditions can vary widely. Theyallow the sender to keep transmitting encoded blocks until the receiver hasenough to reconstruct the original data, ensuring high reliability and effi-ciency.In the rest of this section, we will explain the encoding algorithm andpeeling decoding as the decoding algorithm.Example 2.1. Encoding with Luby Transform (LT) CodesThe encoding process for LT codes involves generating encoded blocksby XORing random subsets of the original data blocks. An essential aspectof LT codes is the degree distribution, which determines the likelihood ofselecting a particular number of data blocks to combine.A commonly used degree distribution for LT codes is the Robust SolitonDistribution [CCZ+12]. This distribution ensures that most encoded blockshave a low degree (involving fewer data blocks), which facilitates efficientdecoding, while a few blocks have higher degrees to ensure robustness againstdata loss.Consider an example where we have n original data chunksD1, D2, . . . , Dn.The encoding process for generating a single encoded block is as follows:1. Select a Degree: Randomly select a degree d from the degree distri-bution, which is the number of data blocks that will be combined tocreate the encoded block.2. Select Data Blocks: Using a random seed, choose d distinct datablocks from the set {D1, D2, . . . , Dn}. The use of a random seed en-sures that if the same seed is used again, the same subset of datablocks will be selected, leading to the generation of the same set ofencoded chunks.3. Generate Encoded Block: XOR the selected data blocks to createthe encoded block. For example, if the selected blocks areDi1 , Di2 , . . . , Did ,the encoded block C is given by:C = Di1 ⊕Di2 ⊕ · · · ⊕Did132.3. ERASURE CODES4. Repeat: Repeat the process to generate additional encoded blocksuntil a sufficient number has been created.The random seed plays a crucial role in ensuring that the encoding pro-cess is reproducible. If the same seed is used, the exact same set of encodedchunks will be generated, which is particularly useful for scenarios wheredeterministic encoding is required.Example 2.2. Encoding in Finite Field ZpWhen encoding data using rateless codes over a finite field Zp, the arith-metic operations are performed modulo p, where p is a prime number. Thisextends the XOR operation used in typical LT codes to addition and multi-plication modulo p.Consider the same data chunks D1, D2, . . . , Dn as before, but now weperform encoding over the finite field Zp.The encoding process to generate a single encoded block is as follows:1. Select a Degree: Randomly select a degree d from the degree distri-bution, which is the number of data blocks that will be combined tocreate the encoded block.2. Select Data Blocks: Using a random seed, choose d distinct datablocks from the set {D1, D2, . . . , Dn}. The use of a random seed en-sures that if the same seed is used again, the same subset of datablocks will be selected, leading to the generation of the same set ofencoded chunks.3. Generate Encoded Block: Add the selected data blocks modulo pto create the encoded block. For example, if the selected blocks areDi1 , Di2 , . . . , Did , the encoded block C is given by:C = (Di1 +Di2 + · · ·+Did) mod p4. Repeat: Repeat the process to generate additional encoded blocks asneeded.Just as in the standard LT encoding process, the random seed ensuresthat the encoding process is reproducible. Using the same seed will generatethe same set of encoded chunks, even when operating within the finite fieldZp.142.3. ERASURE CODESFigure 2.3: Peeling Decoding phase 0Example 2.3. Peeling DecodingPeeling decoding is a fundamental algorithm for decoding rateless codes,such as LT codes. It is known for its simplicity and efficiency in recoveringthe original data chunks from the encoded data. The algorithm proceedsiteratively, focusing on singleton droplets—coded chunks that depend ona single data chunk—and progressively simplifying the problem until theoriginal data is fully recovered.To illustrate, consider a scenario where we have n original data chunksD1, D2, . . . , Dn. These chunks are encoded into several coded chunks, eachrepresenting a linear combination of the original chunks using the XORoperation as illustrated in Figure 2.3. Let the received coded chunks berepresented as follows:C1 = D1 ⊕D3C2 = D2 ⊕D4C3 = D3 ⊕D5C4 = D1 ⊕D2 ⊕D3C5 = D4 ⊕D5C6 = D3The peeling decoding process begins by identifying singleton droplets.C6 is a singleton droplet, directly revealing D3, which can now be peeled offfrom other coded chunks (Figure 2.4). The process iterates as follows:First, we decode D3 from C6. Next, we substitute D3 in the remainingcoded chunks:152.3. ERASURE CODESFigure 2.4: Peeling Decoding phase 1C ′1 = D1 ⊕D3 ⊕D3 = D1C ′2 = D2 ⊕D4C ′3 = D3 ⊕D5 ⊕D3 = D5C ′4 = D1 ⊕D2 ⊕D3 ⊕D3 = D1 ⊕D2C ′5 = D4 ⊕D5We then decode the next singleton droplets D1 and D5 from C′1 and C′3.After that, we substitute D1 and D5 in the remaining coded chunks:C ′′2 = D2 ⊕D4C ′′4 = D1 ⊕D2 ⊕D1 = D2C ′′5 = D4 ⊕D5 ⊕D5 = D4Finally, as illustrated in Figure 2.5, we decode the remaining singletondroplets D2 and D4 from C′′4 and C′′5 . By the end of this iterative process,all original data chunks D1, D2, D3, D4, and D5 are successfully recovered.Example 2.4. Peeling Decoding over Finite Field ZpWhen implementing peeling decoding over a finite field Zp, the decodingprocess remains conceptually similar, but it operates within the arithmeticconstraints of the finite field. This means we have more options than XOR.Consider the same example as above, but now each arithmetic operationis performed in the finite field Zp. Hence, all additions and multiplicationsare modulo p.Suppose the received coded chunks are:162.3. ERASURE CODESFigure 2.5: Peeling Decoding final phaseC1 = D1 +D3C2 = D2 +D4C3 = D3 +D5C4 = D1 +D2 +D3C5 = D4 +D5C6 = D3First, we decode D3 from C6. Next, we substitute D3 in the remainingcoded chunks:C ′1 = D1 +D3 −D3 = D1C ′2 = D2 +D4C ′3 = D5C ′4 = D1 +D2 +D3 −D3 = D1 +D2C ′5 = D4 +D5We then decode the next singleton droplets D1 and D5 from C′1 and C′3:D1 = C′1D5 = C′3After that, we substitute D1 and D5 in the remaining coded chunks:C ′′2 = D2 +D4C ′′4 = D1 +D2 −D1 = D2C ′′5 = D4 +D5 −D5 = D4172.4. CRYPTOGRAPHIC PRIMITIVESFinally, we decode the remaining singleton droplets D2 and D4 from C′′4and C ′′5 :D2 = C′′4D4 = C′′5By the conclusion of this iterative process, we successfully recover alloriginal data chunks D1, D2, D3, D4, and D5 within the finite field Zp.2.4 Cryptographic PrimitivesCryptography is essential for ensuring the security, integrity, and au-thenticity of data in distributed systems. This section covers several cryp-tographic techniques relevant to our work: vector commitments [CF13],Merkle proofs [Mer80], KZG commitments [KZG10], and homomorphic com-mitments [Gen09]. Those who are familiar with the mentioned concepts canskip this chapter.2.4.1 Vector CommitmentA vector commitment is a cryptographic primitive that allows one tocommit to a vector of values in such a way that any individual value withinthe vector can be efficiently and securely verified. This is particularly use-ful in systems where data integrity is important, as it enables verificationwithout revealing the entire data set.Commitment and OpeningThe vector commitment process consists of two main phases: commit-ment and opening.− Commitment: In the commitment phase, the committer generatesa commitment C to a vector v = (v1, v2, . . . , vn). This commitmentis a compact, fixed-size acting on behalf of the entire vector. Thecommitment C ensures that the committer is bound to the vectorv and cannot change any of its values without altering the originalvector.− Opening: To prove the value of a specific element vi within the vector,the committer generates an opening or proof πi. This proof allowsa verifier to check that vi is indeed part of the committed vector v182.4. CRYPTOGRAPHIC PRIMITIVESwithout having access to the original vector. The opening processinvolves generating a short, computationally friendly proof that canbe quickly verified by the verifier.PropertiesVector commitments are designed to be binding and hiding.− Binding: Once a commitment C is made to a vector v, it is compu-tationally infeasible for the committer to change the vector withoutaltering the commitment. This ensures that the committer cannotmodify the values in v after the commitment has been made.− Hiding: The commitment C does not reveal any information aboutthe individual elements of the vector. This property is particularly im-portant in privacy-preserving applications where the committer wantsto prove the properties of the vector without revealing its contents.2.4.2 Merkle ProofMerkle proofs [Mer80] are used to verify the integrity and consistency ofdata in a Merkle tree, a binary tree where each leaf node represents a hash ofa data block, and each non-leaf node represents the hash of its child nodes.The root of the tree, known as the Merkle root, serves as a cryptographicfingerprint of the entire dataset.To verify that a particular data block is part of the dataset, a verifierneeds a Merkle proof. This proof consists of the hashes along the path fromthe leaf node to the root. The verifier can recompute the hashes along thispath and compare the result to the Merkle root. If they match, the integrityof the data block is confirmed. Merkle proofs are widely used in blockchainsystems to ensure data integrity and efficient verification.To better understand how Merkle proofs work, let’s consider a concreteexample:Example 2.5. Merkle Proof ExampleConsider a Merkle tree built from four data blocks D1, D2, D3, and D4.Each data block is hashed to create the leaf nodes of the tree:h1 = Hash(D1)h2 = Hash(D2)h3 = Hash(D3)h4 = Hash(D4)192.4. CRYPTOGRAPHIC PRIMITIVESThe non-leaf nodes are then created by hashing pairs of leaf nodes:h12 = Hash(h1∥h2)h34 = Hash(h3∥h4)Finally, the Merkle root is generated by hashing the top-level non-leafnodes:hroot = Hash(h12∥h34)Now, suppose a verifier wants to confirm that D3 is part of this dataset.To do this, the committer provides a Merkle proof consisting of the followingelements:− The hash h3 of the data block D3.− The hash h4 of the sibling leaf node D4.− The hash h12 of the sibling non-leaf node, which is the parent of h1and h2.The verifier can then perform the following steps:1. Compute h34 = Hash(h3∥h4).2. Compute the Merkle root candidate h′root = Hash(h12∥h34).3. Compare the computed h′root with the provided Merkle root hroot.If h′root matches hroot, the verifier can confidently conclude that D3 isindeed part of the original dataset, verifying its integrity through the Merkleproof.This example illustrates how Merkle proofs enable efficient and secureverification of individual data blocks within a larger dataset without requir-ing access to the entire data structure.2.4.3 KZG CommitmentKZG (Kate-Zaverucha-Goldberg) [KZG10] commitments are a type ofcryptographic commitment scheme that leverages polynomial commitmentsto provide efficient and secure ways to commit to polynomials. The coreidea behind KZG commitments is that one can commit to a polynomialP (x) and later reveal the value of the polynomial at any given point, alongwith a proof that this value is correct. These commitments are widely used202.4. CRYPTOGRAPHIC PRIMITIVESin cryptographic protocols due to their efficiency in terms of proof size andverification time.KZG commitments are particularly useful in scenarios where one needsto prove statements about polynomials, such as in zero-knowledge proofs,polynomial identity testing, and vector commitments. The commitment toa polynomial P (x) is typically represented as C(P ), which serves as a com-pact representation of the entire polynomial. To prove that the polynomialevaluates to a specific value at a particular point, the committer provides anevaluation proof. The verifier can then use this proof, in conjunction withthe original commitment, to confirm the correctness of the polynomial’sevaluation without requiring access to the full polynomial.Using Polynomial Commitments as Vector Commitments. Poly-nomial commitments can also be employed as vector commitments by en-coding the elements of a vector as the coefficients of a polynomial. Specif-ically, to commit to a vector v = (v1, v2, . . . , vn), the committer constructsa polynomial P (x) where the coefficients vi correspond to the elements ofthe vector. The commitment C(P ) generated for this polynomial is then acompact, secure representation of the entire vector.When a verifier wants to check the value of a specific element vi withinthe vector, the committer generates an evaluation proof πi, which provesthat evaluating P (x) at the point x = i yields vi. The verifier can thenuse the proof πi and the commitment C(P ) to efficiently verify the cor-rectness of vi without needing to access the entire vector or polynomial.This makes polynomial commitments, particularly KZG commitments, apowerful tool in applications that require efficient proof generation and ver-ification, such as in blockchain systems, large-scale distributed systems, andprivacy-preserving protocols.The efficiency of KZG commitments in both proof size and verificationtime, combined with their flexibility in being used as vector commitments,makes them well-suited for modern cryptographic protocols. Their applica-tion in zero-knowledge proofs, where the ability to prove knowledge of certaininformation without revealing the information itself is crucial, demonstratesthe robustness and practicality of KZG’s commitments to securing data in-tegrity and confidentiality.44For more information about the setup behind the KZG, you can read this article:https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html212.4. CRYPTOGRAPHIC PRIMITIVES2.4.4 Homomorphic CommitmentsHomomorphic commitments are cryptographic schemes that enable com-putations to be performed directly on committed values without revealingthe underlying data. In such schemes, if c(a) and c(b) are commitmentsto values a and b, respectively, it is possible to compute a new commit-ment c(a ⋆ b) using c(a) and c(b), where ⋆ represents an operation (such asaddition or multiplication) supported by the homomorphic property of thecommitment scheme.This property is invaluable in various cryptographic applications, par-ticularly in secure multi-party computation, privacy-preserving protocols,and blockchain technologies. Homomorphic commitments allow parties toperform complex computations on encrypted or committed data while en-suring that the privacy and integrity of the original values are preserved.The operations supported depend on the specific homomorphic commitmentscheme employed; some schemes support additive homomorphism, allowingoperations like addition and scalar multiplication, while others support mul-tiplicative homomorphism.For instance, in an additive homomorphic commitment scheme, givencommitments c(a) and c(b), one can compute c(a + b) without knowledgeof a or b. This enables the aggregation of committed values and supportsprotocols that require the summation of private inputs, such as privacy-preserving statistical analysis.Homomorphic commitments are thus a versatile tool in modern cryp-tographic systems, facilitating secure computations and enabling protocolsthat require both confidentiality and integrity assurances without sacrificingcomputational efficiency.2.4.5 Pedersen CommitmentPedersen commitments [Ped91] are a widely used cryptographic primi-tive that provides a way to commit to a value while keeping it hidden andretaining the ability to reveal it later. The scheme offers two fundamentalproperties:− Hiding: The commitment does not reveal any information about thecommitted value, ensuring confidentiality.− Binding: Once a value is committed, it cannot be changed withoutdetection; the committer cannot open the commitment to a differentvalue, ensuring integrity.222.4. CRYPTOGRAPHIC PRIMITIVESThe Pedersen commitment scheme is constructed over a cyclic group Gof large prime order q, in which the discrete logarithm problem is compu-tationally hard. Let g and h be two generators of G such that the discretelogarithm of h with respect to g is unknown (i.e., no one knows an x suchthat h = gx). This assumption is critical to the security of the scheme.Given a value x ∈ Zq and a random blinding factor r ∈ Zq, the commit-ment to x is computed as:C(x, r) = gxhr mod p,where p is the prime modulus defining the group G.The commitment C(x, r) is information-theoretically hiding because theblinding factor r randomizes the commitment, making it statistically inde-pendent of x. It is computationally binding under the discrete logarithmassumption, as the committer cannot find another pair (x′, r′) ̸= (x, r) suchthat C(x′, r′) = C(x, r) without solving the discrete logarithm problem.A key feature of the Pedersen commitment is its homomorphic property,specifically additive homomorphism. Given two commitments C(x1, r1) andC(x2, r2), one can compute the commitment to the sum x1 + x2 as:C(x1, r1) · C(x2, r2) = gx1hr1 · gx2hr2 mod p= gx1+x2hr1+r2 mod p= C(x1 + x2, r1 + r2).This homomorphic property allows for operations on committed values,enabling protocols that require computations over private data. For ex-ample, in zero-knowledge proofs, participants can prove statements aboutcommitted values without revealing the values themselves.The security of the Pedersen commitment scheme relies on the hardnessof the discrete logarithm problem in the chosen group G. Additionally,the use of two independent generators g and h ensures that the hiding andbinding properties hold simultaneously.Pedersen commitments are computationally efficient, requiring only ex-ponentiation operations, and are compatible with various cryptographic pro-tocols. Their homomorphic nature makes them particularly suitable for ap-plications in privacy-preserving protocols, secure multi-party computation,and blockchain technologies, where they can be used to ensure data integrityand confidentiality while supporting necessary computations on the data.In summary, the Pedersen commitment scheme provides a robust mech-anism for committing to values with strong security guarantees, facilitatingcomplex cryptographic protocols that require both privacy and verifiability.23Chapter 3Byzantine-Tolerant ErasureCoding ProtocolsIn this chapter, we present two solutions to achieve modularity in thesystem. The first solution, Aurora, is designed for compatibility with MDScodes and can operate with any type of vector or polynomial commitment.We will detail the application of Merkle Proofs and the KZG commitmentscheme to the coded chunks.Furthermore, Phoenix is specifically tailored for compatibility with rate-less codes such as Luby Transform [Lub02] or Raptor codes [Sho06]. Thissolution employs a homomorphic vector commitment scheme. we will dis-cuss the necessity of defining rateless codes over a finite field Zp.3.1 AuroraIn this section, we discuss our first solution, Aurora, and its algorithm.This approach is based on MDS codes and by leveraging vector commitment,we can make the system robust and safe against malicious servers.3.1.1 Setup PhaseThe design is illustrated in Fig 3.1. As shown, each server generatesn coded chunks using the same setup. This ensures uniformity across allservers, with each server producing an identical set of coded chunks in-dexed from 1 to n. Second, each server computes the hash of each codedchunk using a Collision Resistant Hash Function (CRHF) [DH76]. Theythen form a vector of these hashes, resulting in [h1, h2, h3, ..., hn], wherehi = CRHF (coded chunki).At the final stage, each server computes a commitment to the computedvector using a vector commitment scheme, referred to as COM . Addition-ally, each server computes the proof for each element in the vector as proofi.We assume the commitment, COM , is public information accessible to allnodes (clients and servers) within the network.243.1. AURORAFigure 3.1: Aurora - [n, k] MDS codes3.1.2 AlgorithmThe algorithm starts when a client sends a request to download n codedchunks and their respective proofs from the n servers. Each server, sayserver i, sends back the coded chunk i and its respective proof.Upon receiving a coded chunk, the client computes the hash of the re-ceived coded chunk. The client then verifies the computed hash and its proofagainst the commitment. If they match, the client stores the coded chunk.Otherwise, the chunk is treated as an erasure, and the client blacklists thecorresponding server.Once the client verifies and stores k coded chunks, the client starts todecode the coded chunks to reconstruct the original file.Proposition 3.1. Aurora’s verify-and-then-decode approach can identifythe invalid coded chunks before they are used under computation-boundedadversary.Pseudocode for Aurora ProtocolIn this section, we present pseudocode for both the server and clientoperations in the Aurora protocol. The algorithms are designed to be clearand comprehensive, detailing each step of the process and ensuring that allvariables and functions are well-defined. This will facilitate understandingand implementation of the protocol.253.1. AURORAAlgorithm 1: Aurora Protocol Server-Side Operations1 Initialization:2 K ← Number of original data chunks;3 N ← Number of parity chunks (total coded chunks n = K +N);4 File← Input data file to be encoded;5 H ← ∅ ; // Vector of hashes of coded chunks6 COM ← ∅ ; // Vector commitment to the hashes7 {proofi} ← ∅ ; // Set of proofs for each hash8 Function GenerateCodedChunks(File, K, N):Data: Input data file, number of original and parity chunksResult: Set of coded chunks CodedChunks9 Divide File into K original chunks of equal size;10 Use an [n,K] MDS code (e.g., Reed-Solomon) to generate N paritychunks;11 CodedChunks← Combine K original chunks and N parity chunksinto a sequence;12 return CodedChunks13 Function ComputeHashesAndCommitments(CodedChunks):Data: Set of coded chunksResult: Hash vector H, vector commitment COM , proofs {proofi}14 foreach chunk ci in CodedChunks, where i = 1 to n do15 hi ← CRHF(ci) ; // Compute hash of chunk16 H[i]← hi;17 end18 COM ← VectorCommit(H) ; // Compute vector commitment to H19 foreach index i from 1 to n do20 proofi ← GenerateProof(i,H,COM) ; // Generate proof forelement hi21 Store proofi;22 end23 return H, COM , {proofi}24 Main Server Execution:25 CodedChunks← GenerateCodedChunks(File, K, N , Seed);26 H, COM , {proofi} ←ComputeHashesAndCommitments(CodedChunks);27 Publish COM ; // Make commitment publicly accessible28 Upon receiving a request from a client for chunk index i:29 Function SendChunkAndProof(ClientID, ChunkIndex i):Data: Request from client identified by ClientID for chunk at index iResult: Send coded chunk ci and its proof proofi to client30 ci ← CodedChunks[i];31 proofi ← Stored proof corresponding to hi;32 Send ci and proofi to client ClientID;263.1. AURORAAlgorithm 2: Aurora Protocol Client-Side Operations1 Initialization:2 k ← Number of original data chunks needed for decoding;3 VerifiedChunks← ∅ ; // Dictionary mapping indices toverified chunks4 COM ← Retrieve public vector commitment;5 NeededChunks← {1, 2, . . . , n} ; // Set of chunk indices torequest6 Blacklist← ∅ ; // Set of untrusted servers7 ServerList← List of available servers;8 Function VerifyChunk(i, ci, proofi, COM):Data: Index i, coded chunk ci, proof proofi, commitment COMResult: Boolean indicating verification success9 hi ← CRHF(ci) ; // Compute hash of chunk10 if VerifyProof(i, hi, proofi, COM) is True then11 return True12 end13 else14 return False15 end16 Function BlacklistServer(ServerID):17 Add ServerID to Blacklist;18 Remove ServerID from ServerList;273.1. AURORAAlgorithm 2: Aurora Protocol Client-Side Operations (Contin-ued)1 Main Client Execution:2 while size of VerifiedChunks < k and NeededChunks not empty do3 foreach Server in ServerList do4 if Server is not in Blacklist then5 i← Next chunk index from NeededChunks;6 RequestChunk(Server, i);7 Receive ci and proofi from Server;8 if VerifyChunk(i, ci, proofi, COM) is True then9 VerifiedChunks[i]← ci;10 Remove i from NeededChunks;11 end12 else13 BlacklistServer(Server);// Optionally, may retry i from another server14 end15 if size of VerifiedChunks ≥ k then16 break;17 end18 end19 end20 end21 if size of VerifiedChunks ≥ k then22 OriginalData← ReconstructData(VerifiedChunks);// Decode using MDS code decoding algorithm (e.g.,Reed-Solomon decoding)23 return OriginalData;24 end25 else// Insufficient verified chunks to reconstruct data26 return Error indicating failure to reconstruct data;27 endExplanation of the AlgorithmsServer Operations The server-side algorithm consists of the followingkey functions:− Initialization: Sets up the necessary parameters, including the num-ber of original and parity chunks, the seed for consistent chunk gener-ation, and initializes empty structures for hashes, commitments, andproofs.283.1. AURORA− GenerateCodedChunks: Generates the coded chunks by dividing theinput file into K original chunks and creating N parity chunks usingan MDS code like Reed-Solomon. The use of a common seed ensuresthat all servers generate identical coded chunks.− ComputeHashesAndCommitments: Computes the hash of each codedchunk using a Collision Resistant Hash Function (CRHF) and storesthem in the vector H. It then computes a vector commitment COMto the hash vector H using a suitable vector commitment scheme (e.g.,KZG or Merkle tree). Proofs for each element in H are generated andstored for later verification.− SendChunkAndProof: Responds to client requests by sending the re-quested coded chunk and its corresponding proof. This function en-sures that clients receive the necessary information to verify the in-tegrity of the chunks.Client Operations The client-side algorithm includes the following keyfunctions:− Initialization: Retrieves the public commitment COM and initial-izes the required data structures for tracking verified chunks, neededchunks, blacklisted servers, and the list of available servers.− VerifyChunk: Verifies a received coded chunk using its proof and thepublic commitment. It computes the hash of the chunk and uses theproof to verify that this hash is correctly committed in COM . Ifverification succeeds, the chunk is accepted; otherwise, the server isblacklisted.− BlacklistServer: Updates the blacklist and server list by marking aserver as untrusted and removing it from future communication.− Main Execution Loop: Continues to request and verify chunks fromservers until at least k verified chunks are collected or there are no moreservers or chunks to request. If sufficient verified chunks are obtained,it reconstructs the original data using the decoding algorithm of theemployed MDS code.3.1.3 Time Complexity AnalysisIn this section, we analyze the time complexity of the Aurora protocol,focusing on both the server-side and client-side operations. The analysis293.1. AURORAconsiders the primary computational steps involved in the setup phase, thegeneration and verification of commitments, and the decoding process.Server-Side ComplexityThe server operations can be divided into the following steps:1. Coded Chunk Generation: Each server generates n coded chunksfrom the original data using an [n, k] Maximum Distance Separable(MDS) code. The time complexity for encoding data with MDS codes(such as Reed-Solomon codes) is O(k log k) per server for efficient im-plementations, assuming k is the number of original data chunks.2. Hash Computation: The server computes the hash of each codedchunk using a Collision Resistant Hash Function (CRHF), typicallywith a time complexity of O(n), as hashing each chunk is a constant-time operation with respect to the chunk size.3. Vector Commitment Generation: The server generates a vectorcommitment COM to the vector of hashes [h1, h2, . . . , hn]. The timecomplexity depends on the commitment scheme used:− KZG Commitment: Generating a KZG commitment over nelements requires O(n) time due to the need for polynomial in-terpolation or evaluation at a single point.− Merkle Tree Commitment: Constructing a Merkle tree overn elements requires O(n) time, as it involves hashing each levelof the tree up to the root.4. Proof Generation: For each coded chunk, the server generates aproof proofi associated with the commitment. The time complexityis:− KZG Commitment: Proof generation requires O(log n) timedue to operations over polynomials of degree n− 1.− Merkle Tree Commitment: Generating a Merkle proof for asingle element requires O(log n) time, corresponding to the heightof the tree.Overall Server Time Complexity: The total time complexity perserver is dominated by the coded chunk generation and vector commitmentsteps, yielding an overall complexity of O(k log k + n).303.1. AURORAClient-Side ComplexityThe client operations include:1. Data Retrieval: The client requests and receives n coded chunksand their corresponding proofs from n servers. The communicationcomplexity is O(n), but since we focus on computational complexity,this step involves minimal computation.2. Hash Computation: For each received coded chunk, the client com-putes its hash. This operation has a time complexity of O(n).3. Proof Verification: The client verifies each coded chunk and itsproof against the public commitment COM :− KZG Commitment: Each proof verification requires O(log n)time, involving polynomial evaluations.− Merkle Tree Commitment: Each Merkle proof verificationrequires O(log n) time due to the need to hash up the Merklepath.The total time complexity for verifying all n chunks is O(n log n).4. Decoding: After successfully verifying at least k coded chunks, theclient proceeds to decode the original data using the inverse of theencoding operation. For MDS codes like Reed-Solomon, decoding hasa time complexity of O(k log2 k) due to polynomial interpolation.Overall Client Time Complexity: The client’s total time complexityis O(n log n+ k log2 k).Summary of Time Complexities− Server-Side Complexity: O(k log k + n) per server.− Client-Side Complexity: O(n log n+ k log2 k).These complexities highlight that the Aurora protocol scales efficientlywith the number of servers and data size, making it suitable for large-scaledistributed storage systems.313.1. AURORA3.1.4 Proof of CorrectnessWe provide a proof sketch to demonstrate that the Aurora protocol cor-rectly allows the client to reconstruct the original data only if at least kvalid coded chunks are received and verified.Correctness of VerificationProposition 3.2. In the presence of a computationally bounded adversary,the Aurora protocol ensures that any invalid coded chunk provided by a ma-licious server will be detected by the client during the verification phase.Proof. Assuming the collision resistance of the hash function and the secu-rity properties of the vector commitment scheme (whether KZG or Merkletree), any attempt by a malicious server to provide an incorrect coded chunkor an invalid proof will fail verification.For each received coded chunk ci and its proof proofi, the client computesthe hash hi = CRHF(ci). The client then verifies hi against the publiccommitment COM using proofi.− If the server alters ci: The computed hash hi will not correspondto the hash committed in COM , and the proof verification will faildue to the binding property of the commitment scheme.− If the server provides an incorrect proof: The proof verificationwill fail since the proof does not correspond to the committed hash.− Collision Resistance: Given the collision resistance of the hash func-tion, it is computationally infeasible for the server to find a differentchunk c′i such that CRHF(c′i) = hi.− Commitment Security: The vector commitment scheme ensuresthat the server cannot alter the committed values without detectiondue to its binding property.Therefore, any deviation by the server will be detected during the veri-fication process, ensuring that only valid coded chunks are accepted by theclient.Correctness of DecodingProposition 3.3. If the client successfully verifies and collects at least kvalid coded chunks, the client can reconstruct the original data correctly usingthe decoding algorithm of the employed MDS code.323.1. AURORAProof. MDS codes have the property that any subset of k out of n codedchunks suffices to reconstruct the original data. Since the client verifies theintegrity of each coded chunk before accepting it, all collected chunks arevalid and consistent with the encoding performed by the servers.Given that the client has at least k valid coded chunks, the decodingalgorithm (e.g., Reed-Solomon decoding) can be applied to recover the orig-inal data. The correctness of the decoding algorithm is well-established incoding theory; it relies on solving a system of linear equations correspondingto the encoding operations.Therefore, the client will reconstruct the original data accurately, pro-vided that the collected coded chunks are valid and the decoding algorithmis correctly implemented.Resilience Against Malicious ServersProposition 3.4. Aurora can tolerate up to n−k malicious servers withoutcompromising data integrity or the ability of the client to reconstruct theoriginal data.Proof. Since the client requires only k valid coded chunks to reconstructthe original data, the system can tolerate up to n − k failures or maliciousbehaviors. Malicious servers that provide invalid chunks will have their datarejected during the verification phase, and their contributions will not affectthe decoding process.As long as there are at least k honest servers providing valid codedchunks, the client can perform the decoding successfully. The verificationmechanism ensures that only valid data is used, preventing malicious serversfrom disrupting the reconstruction process.Conclusion of CorrectnessThe Aurora protocol ensures correctness through:− Robust Verification: Leveraging cryptographic commitments andproofs to authenticate coded chunks.− Reliable Decoding: Utilizing the properties of MDS codes to guar-antee data reconstruction from any k valid coded chunks.− Fault Tolerance: Resilience against a certain number of maliciousor failed servers without impacting the client’s ability to recover theoriginal data.333.1. AURORAThis combination of cryptographic verification and coding theory prin-ciples underpins the correctness and reliability of the Aurora protocol indistributed storage environments.In the next two sections, we will discuss two candidates for the cryp-tographic primitive in the Aurora approach: KZG and Merkle Proof. Inthe discussion chapter, we will explain which of these is more suitable fordifferent situations.3.1.5 KZG CommitmentIn this section, we discuss how the KZG commitment scheme is appliedas a vector commitment within the Aurora protocol. For this application,each hash of a coded chunk is treated as a field element. Using SHA-256 asthe hash function requires an elliptic curve that accommodates its 256-bitoutput size. The BLS12-381 curve is chosen for its large field size, which iswell-suited for SHA-256 outputs.Following the trusted setup phase, Aurora employs the KZG commit-ment scheme to compute commitments over vectors of these field elements.A key advantage of the KZG commitments is their consistent size—eachcommitment is precisely 48 bytes, regardless of the vector’s length. Thesecommitments serve as compact cryptographic proofs that enable the verifi-cation of data chunk integrity without exposing the underlying data.This approach integrates cryptographic efficiency with data verificationprocesses in Aurora, ensuring that data integrity is maintained across thesystem without excessive computational overhead.3.1.6 Merkle Proof in Aurora ProtocolMerkle proofs can be used as another candidate for vector commitment.The protocol constructs a Merkle tree where each leaf node represents thehash of a coded chunk, and each non-leaf node is derived from the hash ofits children. This tree structure allows for secure and quick validation ofdata.To verify a data chunk, a user only needs the corresponding Merkleproof, which is a path from the chunk’s leaf node up to the tree’s root.The verification process involves hashing each step of the path alongside thesibling hashes provided in the proof. If the computed root hash matches thepublicly known Merkle root, the integrity of the data chunk is confirmed.This approach significantly reduces the data transmission required forverification. For a tree with n chunks, the proof size is approximately log(n)343.2. PHOENIXhashes, making Merkle proofs particularly efficient for verifying large datasets.In the discussion chapter, we will consider the advantages and disadvan-tages of using Merkle Proof or KZG commitment.3.2 PhoenixIn the previous section, we explained how the system works using MDScodes. However, unlike Aurora, Phoenix is designed around rateless codes,specifically LT codes [Lub02]. This code is particularly effective in environ-ments with high noise levels and unpredictable data loss because it does notdepend on a fixed number of encoded outputs. In other words, LT codes cangenerate encoded chunks continuously until sufficient data has been receivedto reconstruct the original data.In the Phoenix system, the design leverages homomorphic commitmentsover the data chunks, not the hashes of encoded chunks. Given the character-istic of an unlimited number of encoded chunks, committing to each encodedchunk would be impractical. By applying homomorphic commitments to thedata chunks instead, we ensure that the integrity and verification processesare consistent and feasible. The decision to define rateless codes over a finitefield Zp (where p is a prime number) instead of a binary field is driven bythe necessity for essential algebraic operations for effectively implementinghomomorphic commitments.In the following sections, we explain the peeling decoding algorithm andhow we can apply this algorithm over Zp.3.2.1 Setup PhaseAs illustrated in Figure 3.2, each server divides the original file intok data chunks using a deterministic algorithm. These chunks are pro-cessed to compute k homomorphic commitments, which are formulated as[C1, C2, . . . , Ck]. This array of commitments is then made publicly accessi-ble to all network nodes. In the next section, we explain the workflow andhow servers utilize Luby Transform (LT) codes over the finite field Zp.3.2.2 AlgorithmThe operational phase of the Phoenix protocol starts when a client re-quests a coded chunk from a server. By using LT codes, the server calculates353.2. PHOENIXFigure 3.2: Phoenix - Rateless codesthis coded chunk as a linear combination of the predefined data chunks us-ing a deterministic algorithm. Because each server uses the same seed, it isguaranteed that each of them will generate an identical set of coded chunks.Upon receiving a coded chunk, the client employs the homomorphicproperty of commitments to authenticate the chunk’s validity. This in-volves computing the commitment of the coded chunk using the coefficientsprovided in the chunk’s header and verifying it against the expected com-mitment derived from the publicly accessible homomorphic commitments.If the commitments match, the chunk is stored; otherwise, it is discarded ascompromised, and the server providing it is blacklisted.The client repeats this verification process until it has collected enoughvalid coded chunks (typically slightly more than k) necessary for recon-structing the original file. This threshold k is well-known and accessible toall network participants.Proposition 3.5. Phoenix can achieve efficient data recovery in environ-ments with up to 33% Byzantine faults, with a linear increase in coded chunkgeneration as network conditions worsen.363.2. PHOENIXPseudocode for Phoenix ProtocolAlgorithm 3: Phoenix Protocol Server-Side Operations1 Initialization:2 k ← Number of data chunks;3 File← Input data file to be divided;4 Seed← Agreed-upon seed for consistency;5 p← Large prime number defining Zp;6 g, h← Generators for the homomorphic commitment scheme;7 DataChunks← ∅;8 Commitments← ∅;9 Function GenerateDataChunks(File, k):Data: Input data file, number of data chunksResult: List of data chunks10 Divide File into k equal-sized data chunks;11 return DataChunks12 Function ComputeCommitments(DataChunks):Data: List of data chunksResult: List of commitments {Ci}13 foreach chunk mi in DataChunks do14 Choose random ri ∈ Zp;15 Ci ← gmihri mod p;16 Store Ci and ri;17 end18 Publish {Ci} as public commitments;19 return {Ci}20 Function GenerateCodedChunk(DataChunks, Seed):Data: List of data chunks, seed for randomnessResult: Coded chunk ccoded, coefficients {ai}, combined randomnessrcoded21 Initialize random number generator with Seed;22 Sample degree d from robust soliton distribution;23 Select d unique indices {i1, i2, . . . , id};24 Generate coefficients aij ∈ Zp;25 ccoded ←∑dj=1 aijmij mod p;26 rcoded ←∑dj=1 aijrij mod p;27 Provide {aij} and rcoded to client;28 return ccoded, {aij}, rcoded29 Main Server Execution:30 DataChunks← GenerateDataChunks(File, k);31 {Ci} ← ComputeCommitments(DataChunks);32 Upon receiving a request from a client:33 ccoded, {aij}, rcoded ← GenerateCodedChunk(DataChunks, Seed);34 Send ccoded, {aij}, rcoded to client;373.2. PHOENIXAlgorithm 4: Phoenix Protocol Client-Side Operations (Part 1)1 Initialization:2 k ← Number of data chunks;3 p← Large prime number defining Zp;4 g, h← Generators for the homomorphic commitment scheme;5 PublicCommitments← Retrieve {Ci};6 VerifiedChunks← ∅;7 Blacklist← ∅;8 Function RequestCodedChunk(Server):Data: Server to request chunk fromResult: Coded chunk and associated data9 Send request to Server;10 Receive ccoded, {aij}, rcoded from Server;11 return ccoded, {aij}, rcoded12 Function VerifyCodedChunk(ccoded, {aij}, rcoded):Data: Coded chunk, coefficients, combined randomnessResult: Boolean indicating verification success13 Compute Cexpected ←∏dj=1 Caijijmod p;14 Compute Ccoded ← gccodedhrcoded mod p;15 if Ccoded = Cexpected then16 Store ccoded and {aij} in VerifiedChunks;17 return True18 end19 else20 BlacklistServer(Server);21 return False22 end383.2. PHOENIXAlgorithm 4: Phoenix Protocol Client-Side Operations (Contin-ued)1 Function BlacklistServer(Server):2 Add Server to Blacklist;3 Remove Server from ServerList;4 Function PeelingDecoder(VerifiedChunks):Data: Set of verified coded chunks and coefficientsResult: Recovered data chunks5 Apply peeling decoding algorithm over Zp;6 return Recovered data chunks7 Main Client Execution:8 while Not enough data to decode do9 foreach Server in ServerList do10 if Server not in Blacklist then11 ccoded, {aij}, rcoded ← RequestCodedChunk(Server);12 if VerifyCodedChunk(ccoded, {aij}, rcoded) then// Proceed to collect more chunks13 end14 else15 BlacklistServer(Server);16 end17 if Decoding is possible with collected chunks then18 break;19 end20 end21 end22 end23 RecoveredData← PeelingDecoder(VerifiedChunks);Explanation of the AlgorithmsServer Operations The server-side algorithm includes:− Initialization: Sets up necessary parameters, including data chunks,commitments, and cryptographic parameters.− GenerateDataChunks: Divides the input file into k data chunks.− ComputeCommitments: Computes homomorphic commitments for eachdata chunk and publishes them.− GenerateCodedChunk: Generates coded chunks using LT encodingover Zp, including coefficients and combined randomness.393.2. PHOENIX− Main Execution and Client Response: Prepares data chunks andcommitments, and responds to client requests with coded chunks andassociated data.Client Operations The client-side algorithm includes:− Initialization: Retrieves public commitments and sets up necessarydata structures.− RequestCodedChunk: Requests coded chunks from servers and receivesnecessary data for verification.− VerifyCodedChunk: Verifies the correctness of the received codedchunk using homomorphic commitments.− BlacklistServer: Manages a list of untrusted servers.− PeelingDecoder: Applies the peeling decoding algorithm to recoverthe original data chunks.− Main Execution Loop: Continues to request and verify chunks untilenough data is collected to perform decoding.3.2.3 Time Complexity AnalysisWe analyze the time complexity of the Phoenix protocol, focusing onboth server-side and client-side operations. The analysis considers the pri-mary computational steps involved in the setup phase, the generation andverification of coded chunks, and the decoding process.Server-Side ComplexityThe server operations include:1. Data Chunk Generation: The server divides the original file intok data chunks using a deterministic algorithm. Assuming the file sizeis proportional to k, this operation has a time complexity of O(k).2. Homomorphic Commitment Computation: The server computeshomomorphic commitments for each of the k data chunks. Each com-mitment involves exponentiation operations over Zp. The time com-plexity for computing one commitment is O(log p). Therefore, thetotal time complexity is O(k log p).403.2. PHOENIX3. Coded Chunk Generation: When a client requests a coded chunk,the server generates it using the LT encoding process over Zp. Thesteps involved are:− Degree Selection: Sampling the degree d from the robust soli-ton distribution has a time complexity of O(1).− Chunk Selection: Selecting d data chunks can be done in O(d)time.− Linear Combination: Computing the linear combination in-volves d additions and multiplications in Zp, each with a timecomplexity of O(log p), resulting in O(d log p) time.The expected degree d¯ is typically constant or logarithmic in k. There-fore, the average time complexity per coded chunk generation isO(d¯ log p).Overall Server Time Complexity: The total time complexity perserver includes the initial setup of O(k log p) and O(d¯ log p) per coded chunkgeneration.Client-Side ComplexityThe client operations include:1. Coded Chunk Request and Reception: The client requests codedchunks from servers. This step involves negligible computational com-plexity on the client side.2. Verification of Coded Chunks: For each received coded chunk, theclient verifies its validity using homomorphic commitments:− Commitment Computation: The client computes the expectedcommitment using the coefficients and public commitments, whichinvolves d exponentiations and d − 1 multiplications, each withO(log p) time, resulting in O(d log p) time.− Verification: Comparing the computed commitment with thereceived commitment takes O(1) time.3. Decoding: Once the client has collected enough coded chunks, theyperform decoding using the peeling decoder for LT codes. The timecomplexity of the peeling decoder is O(k log k) on average.Overall Client Time Complexity: The total time complexity isO(nd¯ log p+ k log k), where n is the number of coded chunks received.413.2. PHOENIXSummary of Time Complexities− Server-Side Complexity: O(k log p) for initial setup, O(d¯ log p) percoded chunk.− Client-Side Complexity: O(nd¯ log p+ k log k).These complexities indicate that the Phoenix protocol scales efficientlywith the number of data chunks k and is suitable for large-scale distributedstorage systems.3.2.4 Proof of CorrectnessWe provide a proof sketch to demonstrate that the Phoenix protocolcorrectly allows the client to reconstruct the original data only if sufficientvalid coded chunks are received and verified.Correctness of VerificationProposition 3.6. Under the assumption of the hardness of the discretelogarithm problem in Zp and the computational binding property of the ho-momorphic commitment scheme, any invalid coded chunk provided by a ma-licious server will be detected by the client during the verification phase.Proof. For each coded chunk received, the client uses the homomorphic prop-erty of the commitments to verify the chunk. Given the coded chunk ccodedand coefficients {ai}, the client computes:Cexpected =∏iCaii mod p,where Ci are the public commitments of the data chunks. The serverprovides ccoded and the combined randomness rcoded. The client computes:Ccoded = gccodedhrcoded mod p.If Ccoded = Cexpected, the coded chunk is accepted; otherwise, it is re-jected. Due to the binding property of the commitment scheme, a maliciousserver cannot produce a ccoded that passes verification unless it is correctlycomputed from the original data chunks.423.2. PHOENIXCorrectness of DecodingProposition 3.7. If the client successfully verifies and collects sufficientcoded chunks, the client can reconstruct the original data correctly using thepeeling decoding algorithm of LT codes over Zp.Proof. LT codes are designed such that, with high probability, the originalk data chunks can be recovered from any set of slightly more than k codedchunks. The peeling decoder operates by iteratively recovering data chunksfrom coded chunks of degree one and simplifying other coded chunks.Since all coded chunks have been verified for correctness using homo-morphic commitments, the data chunks recovered during decoding will beconsistent with the original data.Therefore, the client can reconstruct the original data accurately, pro-vided that enough valid coded chunks are collected.Resilience Against Malicious ServersProposition 3.8. Phoenix can tolerate a certain fraction of malicious serversproviding invalid coded chunks, as long as the client can collect enough validcoded chunks to decode the original data.Proof. Since the client verifies each coded chunk before accepting it, anyinvalid chunks provided by malicious servers will be detected and discarded.As long as the client can collect enough valid coded chunks (slightly morethan k), they can successfully decode the original data.Therefore, the protocol is resilient to malicious servers up to the pointwhere the client cannot obtain enough valid chunks.Conclusion of CorrectnessThe Phoenix protocol ensures correctness through:− Robust Verification: Utilizing homomorphic commitments to au-thenticate coded chunks.− Reliable Decoding: Leveraging the properties of LT codes and thepeeling decoder to recover original data from verified coded chunks.− Fault Tolerance: The ability to tolerate a fraction of maliciousservers without impacting the client’s ability to reconstruct the origi-nal data.43Chapter 4Application in DataSynchronization ProblemWith a comprehensive understanding of the Aurora and Phoenix solu-tions, we can now delve into their application in enhancing the efficiency androbustness of HotStuff [YMR+18]. In this chapter, we will explain in detailand give examples of the modifications required in each stage to integrate thesolutions. In the next chapter, We will evaluate how incorporating Auroracan improve data synchronization, integrity verification, and overall systemperformance, ensuring compatibility and optimal functionality within theHotStuff protocol.4.1 What is the Data Synchronization Problemin HotStuff?As mentioned before, a BFT consensus algorithm contains multiple roundsof communication to reach a consensus. Specifically, data synchronizationis the process by which a node acquires the necessary data to participate ina consensus round. This process is crucial for BFT-based consensus algo-rithms, and HotStuff is no exception. During a view change, it is essential toensure that the majority of nodes have the current state data to verify theleader’s proposed block. If nodes are behind the current state, they mustupdate their data by downloading and verifying the missing blocks fromother peers. This critical procedure is known as the data synchronizationphase.Traditional methods for data synchronization involve requesting anddownloading entire missing blocks from other nodes. Each node must thenverify the received blocks using public information, such as block headers.Although straightforward, this method can be inefficient, as the laggingnode may end up downloading redundant data from multiple nodes. Thiscan lead to increased bandwidth usage and higher latency. Consequently,this process can become a bottleneck in large-scale networks.444.2. APPLYING AURORA OR PHOENIX FOR FASTER NODE RECOVERYFigure 4.1: Applying Aurora or Phoenix to HotStuff for increasing the effi-ciency of data synchronizationAurora and Phoenix can be applied to optimize data synchronizationby leveraging erasure coding and vector commitment schemes. By sendingonly coded chunks and their respective succinct proofs, bandwidth usage isoptimized, latency is decreased, and nodes can reliably synchronize with thecurrent state during view changes.4.2 Applying Aurora or Phoenix for Faster NodeRecoveryTable 4.1: Definition of Parameters in the Data Synchronization Problemin HotStuffParameter DescriptionFile A Blockn Number of Nodesk Number of Chunks needed for a successful decodingclient Lagging nodeBuilding on our understanding of BFT algorithms and the HotStuffprotocol, we explore how the Aurora and Phoenix protocols can be ap-plied to expedite node recovery in a static HotStuff environment. In thiscontext, each block is treated as a file, and each chunk contains multipletransactions. Referring to the parameter definitions in Table 4.1, we out-line the specific modifications required at each stage to implement thesesolutions and compute the system parameter k in the following sections.Integrating the Aurora protocol into HotStuff significantly accelerates thedata synchronization phase, achieving a speed-up proportional to k, wherek = File SizeNumber of Coded Chunks .Prepare The prepare phase is simple, in which the chosen leader sends454.2. APPLYING AURORA OR PHOENIX FOR FASTER NODE RECOVERYthe tuple ⟨body, header, seed⟩5. Upon receiving the proposal, each nodebegins verifying the message. If the majority of nodes agree on the message,they send a prepare vote back to the leader. Once the leader receives themajority of prepare votes, the number of valid received votes will be assumedas k. This parameter k indicates the minimum number of needed codedchunks for decoding. The leader then starts computing the coded chunksand the commitment based on the derived parameters.Pre-commit Next, the leader attaches the computed commitment tothe prepare QC and broadcasts the tuple ⟨prepare QC, commitment,bitmap⟩to all nodes. Upon receiving the tuple, each node starts computing the com-mitment using the parameter k (size of the bitmap) and the seed. If a node’scomputed commitment matches the one received from the leader, it sends apre-commit vote. Honest replicas avoid voting if there is any discrepancy inthe commitment.Commit In the commit phase, the leader aggregates the majority votesfrom the pre-commit phase to form the pre-commit QC. The leader thenbroadcasts the tuple ⟨pre-commit QC⟩ to all replicas. Each replica verifiesthe pre-commit QC and, if valid, sends a commit message. Once the leadercollects the majority of commit votes, the process moves to the decide phase,where the block is finalized. As illustrated in Fig 4.1, COM , k, and bitmapwill be eventually added to the block header.Decide In the decide phase, after the leader collects the majority ofcommit votes, the block is finalized and accepted by the network. In practice,when a node finds some blocks missing, it uses the bitmap to identify whichnodes have the necessary chunks and sends a request to those replicas todownload the corresponding coded chunk. Needless to say, this solution isalso applicable to Fast-HotStuff [JNFG24].To enhance clarity, we provide detailed, step-by-step examples:Example 4.1. We begin with a straightforward and intuitive example ofan ideal environment. Imagine a network with 100 nodes, where 20 nodesare faulty, and the remaining 80 nodes are honest. Node A is selected asthe leader for the next view v. Node A creates a new block and sendsout her proposal. Upon receiving the proposal in the second round, thehonest nodes will send their pre− commit votes. However, the faulty nodesmay behave arbitrarily, meaning they could submit either valid or invalidresponses. For simplicity, let’s assume they do not provide their signatures.In the next example, we will demonstrate the system behavior with more5seed will be used for encoding algorithm, ensure each server will compute a same setof coded chunks464.2. APPLYING AURORA OR PHOENIX FOR FASTER NODE RECOVERYcomplex malicious actions. The values for our parameters in this exampleare summarized in Table 4.1.Table 4.2: Parameters in Example 1 of Data Synchronization Problem inHotStuffParameter DescriptionFile new blockn 100k 80client Lagging nodeIn the third step, the leader computes the commitment, COM , andsends a tuple consisting of the aggregated signature, COM , and the bitmap.Each node then verifies the received commitment against its own computedcommitment. Since peers are known to each node, they can easily check theaggregated signature. If both constraints are satisfied, they proceed to vote.The rest of the steps will remain as HotStuff algorithm until the block, alongwith its metadata like block header, is finalized.Recovery Stage: Recall that the lagging node can access the publicinformation such as block headers (see Section 3.1.1). From the block header,they can obtain the bitmap, which shows the list of nodes that providedtheir signatures. Using this list, the lagging node begins to communicatewith the respective nodes and requests the coded chunks. After aggregatinga sufficient number of coded chunks, k, and verifying them, the node startsdecoding.However, the real-world scenario is not ideal. This leads to some naturalquestions. For example, we previously assumed that a malicious node wouldnot provide its signature. However, what if they sign the message but avoidproviding the coded chunk(s)? Another important question is what if somehonest nodes are offline when the lagging node sends the chunk request? Inthe next example, we explain the system behavior in these situations.Example 4.2. The two questions are equivalent in some ways. A Byzantinenode is defined as one that might behave arbitrarily, not necessarily mali-ciously. Thus, an honest node that is offline at the time of its duty can alsobe considered Byzantine. To explain the system behavior, imagine we havea network with 100 nodes, of which 20 are Byzantine. Node A is selected asthe leader for the next view v. Node A creates a new block and sends outher proposal.474.2. APPLYING AURORA OR PHOENIX FOR FASTER NODE RECOVERYTable 4.3: Parameters definition Example 2 of Data Synchronization Prob-lem in HotStuffParameter DescriptionFile new blockn 100k ≥ 80 and ≤ 100client Lagging nodeUpon receiving the proposal in the second round, the honest nodes willsend their pre − commit votes. However, the faulty nodes may behavearbitrarily, meaning they could submit either valid or invalid responses.From the theoretical perspective, in this situation, k will be bounded by atleast 23n and at most n. However, for our setup, it would be like Table 4.3.At first, it might seem odd to have a dynamic value for k. However, we willexplain in later paragraphs that the range is an overhead, and honest nodescan handle it.To begin with, let’s imagine 10 out of these 20 byzantine nodes willnot provide their signature, and the rest of them are honest, but they willbe offline at the moment of duty. In this way, the leader, Node A, willreceive 90 votes and use the k = 90 (Table 4.4). In the third step, similarto the previous example, the leader calculates the commitment, COM , andsends a tuple with the aggregated signature, COM , and the bitmap. Eachnode compares this with its own commitment and verifies the aggregatedsignature. If both are correct, they vote.Table 4.4: Parameters in Example 2 of Data Synchronization Problem inHotStuffParameter DescriptionFile new blockn 100k 90client Lagging nodeRecovery Stage: Until now, there were no differences between thisscenario and the previous example. However, retrieving coded chunks canbe challenging without knowing which nodes are offline. This creates anoverhead for both the nodes and the lagging node. The lagging node mustwait a few seconds to see if a node responds. If not, it must contact another484.2. APPLYING AURORA OR PHOENIX FOR FASTER NODE RECOVERYnode that has already sent a valid coded chunk. Consequently, some nodesmay need to send more than one chunk, which we refer to as an overhead.This event might affect the liveness but not the security.49Chapter 5Evaluation of the AuroraProtocol5.1 Experimental SetupThis chapter evaluates the performance and robustness of the Auroraprotocol under various network conditions. The evaluation aims to answerkey research questions regarding the efficiency, scalability, and fault toler-ance of Aurora compared to existing protocols like Diem. The experimentswere implemented in the Go programming language and executed in a sim-ulated network environment. The source code is publicly available6.5.1.1 Network ConfigurationThe simulated network environment was configured with varying param-eters:− Total Number of Nodes (n): The number of participating nodeswas varied to assess scalability.− Data Chunks (k): The minimum number of data chunks requiredto accurately reconstruct the original data.− Faulty Nodes (f): Nodes that are either malicious or offline, withthe assumption that f ≤ n3 .− Bandwidth Constraints: Each node was assigned an average uploadbandwidth of 10 Mbps and a download bandwidth of 100 Mbps.− File Size: The file size corresponded to 1,000,000 Ethereum transac-tions.6https://github.com/Xm0onh/thesis_simulation505.2. ADVERSARY MODELThe nodes in the experiment ran concurrently on the same machine—aMacBook Pro M1 Pro with 16 GB RAM. Network bandwidth and latencywere simulated to create a realistic environment. Communication betweennodes was facilitated through TCP sockets. Reed-Solomon coding was im-plemented using a highly optimized library7 widely adopted in the industry.5.1.2 Coding and Commitment SchemesIn the experimental design, we used Merkle proofs [Mer80] as the vectorcommitment scheme. Additionally, we experimented with the KZG com-mitment scheme [KZG10] to compare their performance in proof generationand verification. The parameter k was set such that k ≤ n − f , ensuringthat the system could tolerate up to f faulty nodes.5.2 Adversary ModelFaulty nodes were selected uniformly at random from the set of all nodes.These nodes were designed to disrupt the data synchronization process byeither ignoring requests or sending incorrect data. When a lagging nodesends a request to a faulty node, it may receive no response or receive invaliddata.To handle such disruptions, the lagging node employs a strategy of time-out and blacklisting:− Timeout Mechanism: The lagging node waits up to 10 seconds fora response after sending a request.− Verification of Data: Upon receiving a response, the lagging nodeverifies the integrity of the data using the vector commitment scheme.− Blacklisting: If the response is invalid or no response is receivedwithin the timeout period, the lagging node identifies the peer asfaulty, adds it to a blacklist, and drops the connection.This mechanism ensures that the lagging node can effectively avoid faultynodes and continue the synchronization process with honest peers.7https://github.com/klauspost/reedsolomon515.3. RESULTS AND ANALYSIS5.3 Results and Analysis5.3.1 Experiment 1: Performance Evaluation of AuroraFigure 5.1: Synchronization times for the Aurora protocol under variousnetwork conditions. Aurora maintains low synchronization times even inthe presence of faulty nodes, demonstrating its scalability and robustness.In the first experiment, we evaluated the performance and efficiency ofthe Aurora protocol under various network conditions. While the Diemprotocol relies on a sequential streaming approach for data synchroniza-tion—which can introduce significant delays, especially when interactingwith slow or unreliable peers—Aurora leverages advanced coding techniquesto request data in parallel from multiple nodes, thereby reducing synchro-nization times.In the Diem protocol, a lagging node:525.3. RESULTS AND ANALYSIS1. Identifies and connects to a full node.2. Exchanges bandwidth capacity information with the full node.3. Receives missing blocks streamed sequentially from the full node.4. Verifies the integrity of the received blocks against publicly availableblock headers.This sequential approach can lead to substantial synchronization delays,particularly if the full node is slow or if there are network issues.In contrast, Aurora’s parallel data retrieval mechanism significantly im-proves synchronization times. Figure 5.1 illustrates the synchronizationtimes for Aurora under various network sizes and faulty node conditions.As shown in the figure, Aurora maintains synchronization times below 40seconds across different network configurations, demonstrating its scalabilityand robustness.While the figure focuses on Aurora’s performance, it is important tonote that the Diem protocol exhibits significantly higher synchronizationtimes based on existing benchmarks. Under ideal conditions where the firstfull node is honest, Diem’s average total duration is approximately 166seconds. Compared to Aurora, this represents a substantial increase insynchronization time. In scenarios with faulty nodes, Diem’s performancedegrades further, whereas Aurora continues to perform efficiently.In realistic scenarios with 10% faulty nodes and 100 total nodes, Au-rora achieves nearly ten times better efficiency than Diem. This significantimprovement demonstrates Aurora’s ability to handle network unreliabilityand malicious behavior effectively.5.3.2 Experiment 2: Impact of Faulty Nodes on SystemPerformanceThe second experiment examined the impact of faulty nodes (f) on theoverall system performance. Figure 5.2 shows the scalability of Aurora undervarying network conditions. The analysis focused on the time required forsuccessful retrieval and validation of data chunks as the number of nodes(n) and faulty nodes (f) increased.Aurora maintained low synchronization times even as the number ofnodes grew, demonstrating its scalability. As the number of faulty nodesincreased, there was a noticeable rise in retrieval time. Specifically, theretrieval time increased by approximately 42% for n = 50 and 43% forn = 80 as f approached the threshold of f ≤ n3 .535.3. RESULTS AND ANALYSISFigure 5.2: Scalability of Aurora under varying numbers of faulty nodes.Aurora maintains robust performance, with only moderate increases in re-trieval time as the number of faulty nodes increases.5.3.3 Discussion on Performance FluctuationsAn interesting observation from the experiments is the fluctuation in syn-chronization times as the number of nodes increases. Intuitively, one mightexpect that adding more nodes would decrease the total synchronizationtime due to parallelization. However, this is not always the case.In some scenarios, a slightly smaller number of nodes leads to better per-formance. This phenomenon occurs because nodes with idle bandwidth cancontribute more effectively to the data transfer. When the network includesmore nodes, the overhead associated with network delays and cryptographiccomputations can offset the benefits of parallelization. Each additional nodeintroduces potential latency and requires additional computational resourcesfor tasks like verifying proofs and managing connections.By reducing the number of nodes slightly, the system can minimize theseoverheads. The remaining nodes can utilize their available bandwidth moreefficiently to support the transfer of data chunks. This balance results in amore optimal use of network resources, leading to improved synchronizationtimes in certain configurations.545.4. EXPERIMENT 3: HANDLING FEWER AVAILABLE NODES5.4 Experiment 3: Handling Fewer AvailableNodesIn the third experiment, we investigated how the system handles datarecovery when the number of available nodes is less than the parameter k. Inpractical scenarios, nodes may go offline or become temporarily unavailable,resulting in fewer nodes than required.To address this issue, we considered two approaches:1. New Nodes Computing Coded Chunks: New nodes that possessthe data can compute the coded chunks and proofs to compensate forthe unavailable nodes.2. Nodes Sending Multiple Chunks: Some nodes can send more thanone coded chunk to the client.Our experiment demonstrated that the first solution, though it mightseem less feasible due to computational overhead, proved effective in prac-tice. Even for large files, the time required to compute all coded chunksusing Reed-Solomon codes was only 15.221 milliseconds.Table 5.1 summarizes the time metrics for computing coded chunksand generating proofs using different vector commitment schemes for 7,000Ethereum blocks.Table 5.1: Time metrics for computing coded chunks and vector commit-ments for 1,000,000 Ethereum transactions using the Aurora protocolMetric TimeComputing coded chunks with Reed-Solomon 15.221 msComputing vector commitments and proofsMerkle proof generation 88.984 msKZG vector commitment 393.791 µsThese results indicate that even with fewer available nodes, the systemcan efficiently recover the data without significant performance degradation.5.5 ConclusionThe experiments demonstrate that Aurora significantly outperforms tra-ditional protocols like Diem in terms of synchronization times and scalability.555.5. CONCLUSIONAurora’s ability to handle faulty nodes and fluctuating network conditionsmakes it a robust solution for distributed systems. The observed perfor-mance fluctuations with varying numbers of nodes highlight the importanceof balancing network size and resource utilization to achieve optimal perfor-mance.56Chapter 6Evaluation of the PhoenixProtocol6.1 Experimental SetupThe evaluation of the Phoenix Protocol aimed to assess the performance,scalability, and efficiency of its core cryptographic operations—encoding,decoding, commitment generation, and verification—using LT codes over afinite field Zp. The experiments were meticulously implemented in the Goprogramming language and executed in a controlled local environment toeliminate network-induced variability. All tests were performed on the samemachine as the previous experiment.6.1.1 Data PreparationThe original data consisted of a JSON file containing Ethereum transac-tion objects, each comprising fields such as from, to, value, gas price, andnonce. To simulate a realistic and variable-sized dataset, the entire JSONfile was treated as a single continuous byte stream. This stream was thenpartitioned into k equal-sized chunks, with k varying from 100 to 60,000.Each chunk served as an input symbol for the LT coding process.To ensure uniformity, if the total data size was not perfectly divisibleby k, the last chunk was padded with zeros to match the size of the otherchunks. This preprocessing step was crucial for maintaining consistencyacross all experiments.6.1.2 Encoding ProcessFor each specified value of k, the following encoding steps were executed:1. Symbol Conversion: Each data chunk was converted into a big in-teger representation using the SetBytes method. This representationfacilitated mathematical operations within the finite field Zp.576.1. EXPERIMENTAL SETUP2. LT Code Parameterization: The robust soliton distribution pa-rameters were configured with c = 0.1 and δ = 0.5, which influencedthe degree distribution of the encoded symbols. These parameterswere chosen to balance the trade-off between encoding overhead anddecoding success probability.3. Overhead Calculation: An overhead percentage of 10% was applied,resulting in the total number of encoded symbols n = ⌈k × (1 + 0.1)⌉.This overhead ensures that enough encoded symbols are generated tofacilitate successful decoding with high probability.4. Symbol Encoding: Utilizing the robust soliton distribution, encodedsymbols were generated by performing a linear combination (modulop) of randomly selected original chunks. For each encoded symbol:(a) A degree d was sampled according to the distribution.(b) d unique original chunk indices were randomly selected.(c) The encoded symbol value was computed as mencoded =∑di=1mimod p, where mi are the selected original chunks.6.1.3 Commitment GenerationTo ensure data integrity and enable verification without exposing theoriginal data, the Pedersen commitment scheme was employed, leveragingits homomorphic linear properties:1. Parameter Generation: Secure Pedersen parameters were gener-ated, including:− A large prime p defining the finite field Zp.− A prime q such that q divides p−1, establishing a cyclic subgroupof order q within Z∗p.− Generators g and h of the subgroup, carefully selected to ensurethey are independent (i.e., logg h is unknown).2. Commitment Computation for Original Chunks: For each orig-inal chunk mi:(a) A random value ri was selected uniformly from Zq.(b) The commitment was calculated as Ci = gmihri mod p.586.1. EXPERIMENTAL SETUP3. Homomorphic Commitment Computation for Encoded Sym-bols: Exploiting the linear homomorphic property of Pedersen com-mitments, the commitment for each encoded symbol was computedwithout revealing the underlying data:(a) For an encoded symbol composed of original chunks at posi-tions S, the combined commitment was calculated as Cencoded =∏i∈S Ci mod p.(b) The combined randomness was rencoded =∑i∈S ri mod q.(c) The encoded symbol commitment satisfies Cencoded = gmencodedhrencodedmod p.6.1.4 Verification and DecodingThe verification and decoding processes were as follows:1. Verification of Encoded Symbols: The client verified the integrityof each encoded symbol using its commitment:(a) The server provided the encoded symbol mencoded and the com-bined randomness rencoded.(b) The client computed C ′ = gmencodedhrencoded mod p.(c) Verification succeeded if C ′ = Cencoded, confirming that the en-coded symbol was correctly formed from the original chunks.2. Decoding Process: The LT decoding algorithm was applied to re-cover the original chunks:(a) Decoding commenced with encoded symbols of degree one, di-rectly recovering corresponding original chunks.(b) Recovered chunks were iteratively used to simplify other encodedsymbols by subtracting known values (modulo p).(c) The process continued until all original chunks were recovered ordecoding stalled due to insufficient information.6.1.5 Performance MeasurementFor each value of k, the time taken for critical operations was meticu-lously measured using Go’s high-resolution timers:596.2. RESULTS AND ANALYSIS− Encoding Time: Duration to generate all n encoded symbols fromthe original chunks.− Decoding Time: Duration to recover all original chunks from theencoded symbols.− Commitment Generation Time: Duration to compute Pedersencommitments for all original chunks.− Verification Time: Duration to verify all encoded symbols’ commit-ments.Each experiment was repeated five times to calculate average timings,thereby mitigating the effects of transient system performance fluctuations.6.2 Results and AnalysisThe performance evaluation of the Phoenix Protocol revealed insightsinto its scalability and efficiency across varying values of k. Figure 6.1presents the relationship between the number of chunks and the time takenfor each core operation.6.2.1 Encoding and Decoding PerformanceThe encoding and decoding operations demonstrated a linear to sub-linear increase in execution time as k increased:− Encoding: The encoding time rose from approximately 0.83 millisec-onds at k = 100 to 53.8 seconds at k = 60,000. This escalation isattributed to the increased computational load of generating moreencoded symbols and performing modular arithmetic operations overlarge integers.− Decoding: Decoding times increased from 0.17 milliseconds at k =100 to 72.8 seconds at k = 60,000. The decoding process, inherentlyiterative and dependent on the structure of the encoded symbols, re-quires more time as the number of symbols grows.6.2.2 Commitment Generation and VerificationPerformanceCommitment-related operations scaled more efficiently:606.2. RESULTS AND ANALYSISFigure 6.1: Performance evaluation of the Phoenix Protocol for differentvalues of k.− Commitment Generation: Times increased from 7.13 millisecondsto 13.6 seconds as k grew from 100 to 60,000. The linear relationshipis due to the need to compute one exponentiation per original chunk.− Verification: Verification times were notably efficient, rising from4.26 milliseconds at k = 100 to just 2 seconds at k = 60,000. This effi-ciency is a direct result of the homomorphic properties of the Pedersencommitments, allowing the verification of encoded symbols without in-dividual inspection of each original chunk.6.2.3 Scalability AnalysisThe experimental results indicate that:− Encoding and Decoding: While the time increases with k, thegrowth rate remains manageable for moderate values of k. The use of616.2. RESULTS AND ANALYSISefficient data structures and algorithms in the implementation helpsmitigate performance degradation.− Commitment Operations: Both generation and verification oper-ations exhibit favorable scalability due to their linear complexity andthe utilization of the homomorphic linear property of Pedersen com-mitments, which reduces computational overhead during verification.6.2.4 Implications for Practical DeploymentThe Phoenix Protocol demonstrates practical viability for applicationsrequiring data integrity and confidentiality over unreliable channels. How-ever, for large-scale deployments with very high k values, optimization strate-gies such as parallel processing, optimized arithmetic libraries, or alternativecoding schemes may be necessary to maintain acceptable performance levels.62Chapter 7DiscussionThis chapter discusses the practical implications and challenges of inte-grating the Aurora and Phoenix protocols into BFT systems, particularlyin terms of performance improvements, cryptographic commitments, andthe necessity of coding techniques. The analysis focuses on how both pro-tocols address key performance metrics, such as Transactions Per Second(TPS) and latency, and how their design choices influence their robustnessand scalability. We compare the cryptographic commitments used in Au-rora, exploring the trade-offs between Merkle proofs and KZG commitments,and highlight the necessity of coding beyond parallel downloading for fault-tolerant data synchronization. Furthermore, we mention the limitations ofthe protocols.7.1 Translating Performance Improvements intoTPS and Latency MetricsThe integration of the Aurora and Phoenix protocols into existing sys-tems leads to significant enhancements in key performance metrics such asTPS and latency. This section examines how reductions in synchronizationtimes and improved fault tolerance directly translate into measurable gainsin TPS and decreases in transaction latency. Additionally, we explore howthese protocols align with responsive BFT algorithms and the concept ofsemi-synchrony to further reduce latency in the presence of network uncer-tainties.7.1.1 Impact on TPSTPS reflects the throughput capacity of a blockchain or distributedledger system, quantifying the number of transactions that can be processedand confirmed within one second. The integration of the Aurora protocolenhances TPS by significantly reducing the time required for nodes to syn-chronize data. By minimizing the downtime experienced by lagging nodes,637.2. COMPARISON OF MERKLE PROOFS AND KZG COMMITMENTS IN AURORAAurora ensures that nodes can quickly rejoin the consensus process, therebycontributing to higher overall system throughput.7.1.2 Reduction in Transaction and Network LatencyLatency refers to the time it takes for a transaction to be confirmedand become immutable in the ledger. Lower latency improves the system’sresponsiveness, enhancing user experience and enabling time-sensitive appli-cations. The Aurora and Phoenix protocols contribute to latency reductionthrough faster node recovery, efficient handling of network delays, and align-ment with responsive BFT algorithms.By accelerating the synchronization of lagging nodes, these protocolsreduce the time during which a node is unable to participate in consen-sus, ensuring that the consensus process can proceed without delays causedby missing nodes. Designed to be resilient to network latency, the proto-cols operate effectively even when some nodes experience delays, prevent-ing high latency in parts of the network from disproportionately affectingoverall transaction latency. Furthermore, integrating these protocols withresponsive BFT algorithms allows the system to adjust its behavior based onnetwork conditions. In periods of synchrony, the system can make progressfaster, thus reducing the latency experienced by transactions.7.2 Comparison of Merkle Proofs and KZGCommitments in AuroraIn the Aurora protocol, ensuring data integrity and efficient verificationis crucial. Aurora can utilize either Merkle proofs or KZG commitments asoptions for cryptographic commitments, each offering distinct advantagesbased on the system’s requirements. The table 7.1 summarizes the keydifferences between Merkle proofs and KZG commitments.In summary, both Merkle proofs and KZG commitments are viable op-tions within Aurora. The choice between them allows the protocol to op-timize for performance, scalability, or security based on the application’sspecific requirements.7.3 Why is coding necessary?While parallel downloading significantly reduces the time required fordata synchronization by allowing a lagging node to retrieve data from mul-647.3. WHY IS CODING NECESSARY?Table 7.1: Comparison of Merkle Proofs and KZG Commitments in AuroraFeature Merkle Proofs KZG CommitmentsProof Size Increases logarithmicallywith data sizeConstant-size proofs re-gardless of data sizeVerification Time Logarithmic time relativeto data sizeEfficient verification evenfor large data setsComputationalComplexityUses simple hash func-tions; low computationaloverheadRequires advanced cryp-tographic operations;higher overheadTrusted Setup Not required Required (introducestrust assumptions)Update Overhead Modifying data requiresupdating hashes up to therootSupports efficient updateswith minimal overheadBandwidth Usage Proof size grows with datasizeSmall, fixed-size proofs re-duce bandwidth usageSecurity Assump-tionsRelies on collision resis-tance of hash functionsBased on hardness of dis-crete logarithm problemsBest Suited For Simplicity; small tomedium data setsLarge data sets; whenproof size is criticaltiple peers simultaneously, it is not robust enough. Parallel downloadingmitigates delays caused by slow or unreliable nodes by not relying on a sin-gle source for data. However, it does not address data integrity and faulttolerance issues. On the other hand, coding techniques provide additionalbenefits by enabling the reconstruction of the original data from a subset ofreceived coded chunks.For example, consider a network with ten nodes where data is dividedinto ten blocks, each stored on a different node. Without coding, if nodes3 and 7 are faulty, the lagging node would need to request the missingblocks from the remaining honest nodes, which can introduce delays andincrease the complexity of the synchronization process. In contrast, withReed-Solomon coding, the data can be split into seven original chunks withthree parity chunks. The lagging node only needs to retrieve any 7 out of 10chunks to reconstruct the data. Even if nodes 3 and 7 are faulty, the laggingnode can still obtain the necessary chunks from the remaining nodes.657.4. LACK OF RESOURCES FOR SIMULATING PHOENIX7.4 Lack of Resources for Simulating PhoenixOne of the primary limitations encountered during this research wasthe lack of sufficient resources to fully simulate/implement the Phoenix ap-proach. While Aurora was extensively tested and demonstrated significantimprovements in synchronization times and fault tolerance, Phoenix’s po-tential remains largely theoretical at this stage. The primary challenge wasthe absence of optimized coding libraries that support rateless codes andhomomorphic commitments over finite fields Zp. This gap hindered a com-prehensive comparative analysis between Aurora and Phoenix, limiting ourability to fully validate Phoenix’s efficiency and robustness in practical sce-narios.7.5 LimitationsWhile both the Aurora and Phoenix protocols offer robust solutions forimproving data synchronization and integrity in Byzantine Fault Tolerantsystems, they are not without limitations. Below, we discuss three keychallenges inherent to these protocols.7.5.1 Computational IntensityThe computational complexity of the operations scales with the size ofthe data and the number of chunks, k. For large datasets, the encoding anddecoding phases, as well as the generation and verification of cryptographiccommitments, can become prohibitively expensive. This is particularly truein resource-constrained environments where processing power and memoryare limited. During large-scale deployments, such computational intensitycan create bottlenecks, affecting the protocol’s ability to perform in real-timescenarios.7.5.2 Implementation ComplexityThe implementation of both Aurora and Phoenix is inherently complexdue to the integration of advanced cryptographic and coding techniques.Aurora employs MDS codes alongside vector commitments, while Phoenixutilizes rateless codes combined with the homomorphic properties of Peder-sen commitments to validate coded chunks.One significant challenge associated with KZG commitments is the re-quirement for a trusted setup phase. This phase is critical for generating667.5. LIMITATIONSthe initial parameters used in the commitment scheme, and any compromiseduring this phase can undermine the security of the entire system. Ensuringthe correctness and security of these cryptographic operations, as well astheir integration with the coding techniques, demands meticulous attentionto detail.Even minor errors in implementation, whether in the coding algorithmsor cryptographic constructs, can introduce vulnerabilities, making these pro-tocols difficult to deploy and maintain securely. The complexity is furthercompounded by the need to manage cryptographic keys and parameters cor-rectly, particularly in the context of the trusted setup for KZG. This makesthe deployment of Aurora and Phoenix protocols challenging, requiring spe-cialized knowledge and rigorous validation to ensure their reliability andsecurity.7.5.3 Computationally Bounded AdversaryThe security assumptions of both protocols are based on the computa-tional limitations of potential adversaries. They rely on cryptographic prim-itives that are secure under classical computing assumptions. However, therise of quantum computing poses a significant threat. Quantum algorithms,such as Shor’s algorithm [Sho97], could break the discrete logarithm problemthat underpins Pedersen commitments, as well as other cryptographic con-structs used in these protocols. This means that in a post-quantum world,the security guarantees of Aurora and Phoenix would be compromised. Ad-dressing this limitation would require transitioning to quantum-resistantcryptographic primitives, which is an active area of research but not yetfully realized.67Chapter 8ConclusionThe research presented in this thesis explores advanced techniques to ad-dress the challenges of file downloading problems in Byzantine environmentswith the application of data synchronization in BFT consensus protocols,particularly within blockchain systems. We proposed two novel solutions,Aurora and Phoenix, each leveraging coding and cryptographic methods toenhance data integrity, efficiency, and fault tolerance.8.1 Key Findings− Performance and Efficiency: Aurora significantly reduces synchro-nization times compared to the Diem protocol. By enabling paralleldata requests and employing advanced coding techniques, Aurora en-sures faster and more reliable data synchronization.− Scalability: Aurora maintains low synchronization times even as thenetwork size increases. This scalability is crucial for modern blockchainsystems, which often operate in large and dynamic environments.− Fault Tolerance: Aurora demonstrates robust performance in thepresence of faulty nodes. The use of MDS codes and vector commit-ments enhances its ability to detect and recover from data corruptionand loss.− Coding Necessity: The research emphasizes the importance of era-sure coding in distributed systems. Coding techniques like those usedin Aurora provide significant advantages in terms of data integrity andfault tolerance, which are not achievable through parallel downloadingalone.8.2 Future WorkWhile Aurora has shown significant promise, the lack of optimized re-sources for simulating Phoenix remains a major limitation. Future research688.2. FUTURE WORKshould focus on developing and optimizing coding libraries that can supportrateless codes and homomorphic commitments efficiently. Additionally, ex-ploring hybrid approaches that combine the strengths of MDS and ratelesscodes could offer new insights and further enhance the robustness and effi-ciency of BFT consensus protocols.An important direction for future work is to extend the design of Au-rora and Phoenix to be fully compatible with Dynamic Byzantine FaultTolerance (Dynamic BFT) protocols. While the current design is tailoredto static networks, adapting it to dynamic environments where nodes canjoin or leave the network without compromising security or performancewould significantly broaden the applicability of these protocols. This wouldinvolve integrating dynamic membership changes into the commitment andverification processes, ensuring that the system maintains its efficiency andfault tolerance as the network evolves.Advanced fault detection and correction mechanisms, potentially lever-aging machine learning and artificial intelligence, could further improve thefault tolerance of these protocols. Real-world implementations and testingin diverse blockchain networks would provide valuable practical insights andhelp refine these solutions.69Bibliography[ADVZ21] Nicolas Alhaddad, Sisi Duan, Mayank Varia, and Haibin Zhang.Succinct erasure coding proof systems. Cryptology ePrintArchive, Paper 2021/1500, 2021. https://eprint.iacr.org/2021/1500. → pages 5[Ass21] The Diem Association. The diem blockchain, 2021. → pages 4[CCZ+12] Guo Tai Chen, Lei Cao, Feilong Zhao, Hai-feng Zheng, andMeiying Pan. Analysis of robust soliton distribution for lt code.In 2012 IEEE 11th International Conference on Signal Process-ing, volume 2, pages 1546–1549, 2012. → pages 13[CF13] Dario Catalano and Dario Fiore. Vector commitments and theirapplications. In Kaoru Kurosawa and Goichiro Hanaoka, editors,Public-Key Cryptography – PKC 2013, pages 55–72, Berlin, Hei-delberg, 2013. Springer Berlin Heidelberg. → pages 18[CL99] Miguel Castro and Barbara Liskov. Practical byzantine faulttolerance. In Proceedings of the Third Symposium on OperatingSystems Design and Implementation, OSDI ’99, page 173–186,USA, 1999. USENIX Association. → pages 1, 7[CT05] C. Cachin and S. Tessaro. Asynchronous verifiable informationdispersal. In 24th IEEE Symposium on Reliable Distributed Sys-tems (SRDS’05), pages 191–201, 2005. → pages 2[DFF+82] Danny Dolev, Michael J. Fischer, Rob Fowler, Nancy A. Lynch,and H. Raymond Strong. An efficient algorithm for byzantineagreement without authentication. Information and Control,52(3):257–274, 1982. → pages 7[DH76] W. Diffie and M. Hellman. New directions in cryptogra-phy. IEEE Transactions on Information Theory, 22(6):644–654,1976. → pages 2470Bibliography[DXR21] Sourav Das, Zhuolun Xiang, and Ling Ren. Asynchronous datadissemination and its applications. In Proceedings of the 2021ACM SIGSAC Conference on Computer and CommunicationsSecurity, CCS ’21, page 2705–2721, New York, NY, USA, 2021.Association for Computing Machinery. → pages 4[DZ22] Sisi Duan and Haibin Zhang. Foundations of dynamic bft. In2022 IEEE Symposium on Security and Privacy (SP), pages1317–1334, 2022. → pages 9[FLMY03] Wai Fong, Shu Lin, Gary Maki, and Pen-Shu Yeh. Low densityparity check codes: Bandwidth efficient channel coding. 02 2003.→ pages 13[FLP85] Michael J Fischer, Nancy A Lynch, and Michael S Paterson.Impossibility of distributed consensus with one faulty process.Journal of the ACM (JACM), 32(2):374–382, 1985. → pages 8[Gen09] Craig Gentry. A fully homomorphic encryption scheme. PhDthesis, Stanford, CA, USA, 2009. AAI3382729. → pages 18[GHM+17] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, andNickolai Zeldovich. Algorand: Scaling byzantine agreements forcryptocurrencies. In Proceedings of the 26th Symposium on Op-erating Systems Principles, SOSP ’17, page 51–68, New York,NY, USA, 2017. Association for Computing Machinery. → pages9[GKS+22] Guy Goren, Lefteris Kokoris-Kogias, Alberto Sonnino, Shir Co-hen, and Alexander Spiegelman. Proof of availability & retrievalin a modular blockchain architecture. IACR Cryptol. ePrintArch., page 455, 2022. → pages 4[JNFG24] Mohammad M. Jalalzai, Jianyu Niu, Chen Feng, and FangyuGai. Fast-hotstuff: A fast and robust bft protocol forblockchains. IEEE Transactions on Dependable and SecureComputing, 21(4):2478–2493, 2024. → pages 46[KCR19] Swanand Kadhe, Jichan Chung, and Kannan Ramchandran.Sef: A secure fountain architecture for slashing storage costsin blockchains. CoRR, abs/1906.12140, 2019. → pages 371Bibliography[KZG10] Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg.Constant-size commitments to polynomials and their applica-tions. In Advances in Cryptology - ASIACRYPT 2010, pages177–194, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.→ pages 18, 20, 51[LSP82] Leslie Lamport, Robert Shostak, and Marshall Pease. Thebyzantine generals problem. ACM Trans. Program. Lang. Syst.,4(3):382–401, jul 1982. → pages 1[Lub02] Michael Luby. Lt codes. The 43rd Annual IEEE Symposiumon Foundations of Computer Science, 2002. Proceedings., pages271–280, 2002. → pages 12, 24, 35[Mak18] Georgios Michail Makrakis. Evaluating the performance of Dis-tributed Ledger - Blockchain technologies in IoT environment.PhD thesis, 10 2018. → pages x, 2[Mer80] Ralph C. Merkle. Protocols for public key cryptosystems. In1980 IEEE Symposium on Security and Privacy, pages 122–122,1980. → pages 18, 19, 51[MMR22] Dahlia Malkhi, Atsuki Momose, and Ling Ren. Towards prac-tical sleepy BFT. Cryptology ePrint Archive, Paper 2022/1448,2022. https://eprint.iacr.org/2022/1448. → pages 9[Nak09] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash sys-tem. May 2009. → pages 1, 6[NNT23] Kamilla Nazirkhanova, Joachim Neu, and David Tse. Informa-tion dispersal with provable retrievability for rollups. In Pro-ceedings of the 4th ACM Conference on Advances in FinancialTechnologies, AFT ’22, page 180–197, New York, NY, USA,2023. Association for Computing Machinery. → pages 4[Ped91] Torben P. Pedersen. Non-interactive and information-theoreticsecure verifiable secret sharing. In Proceedings of the 11th An-nual International Cryptology Conference on Advances in Cryp-tology, CRYPTO ’91, page 129–140, Berlin, Heidelberg, 1991.Springer-Verlag. → pages 22[RS60] Irving S. Reed and Gustave Solomon. Polynomial codes overcertain finite fields. Journal of The Society for Industrial andApplied Mathematics, 8:300–304, 1960. → pages 4, 1272Bibliography[Sha79] Adi Shamir. How to share a secret. Commun. ACM,22(11):612–613, nov 1979. → pages 11[Sho97] Peter W. Shor. Polynomial-time algorithms for prime factor-ization and discrete logarithms on a quantum computer. SIAMJournal on Computing, 26(5):1484–1509, 1997. → pages 67[Sho06] A. Shokrollahi. Raptor codes. IEEE Transactions on Informa-tion Theory, 52(6):2551–2567, 2006. → pages 24[Tou84] Sam Toueg. Randomized byzantine agreements. In Proceed-ings of the Third Annual ACM Symposium on Principles of Dis-tributed Computing, PODC ’84, page 163–178, New York, NY,USA, 1984. Association for Computing Machinery. → pages 8[YMR+18] Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy GolanGueta, and Ittai Abraham. Hotstuff: Bft consensus in the lensof blockchain. arXiv preprint arXiv:1803.05069, 2018. → pages1, 7, 10, 4473
Thesis/Dissertation
eng
Electrical Engineering
Vancouver : University of British Columbia Library
Attribution-NoDerivatives 4.0 International
Graduate
Feng, Chen
Byzantine-tolerant erasure coding for blockchains
Text