<p>Recent technological advancements have led to the development of new methods for managing organ donation systems, which aim to overcome the limitations of traditional centralized systems. To achieve increased transparency, security, and efficiency in the organ donation process, blockchain technology is being proposed as a replacement for these centralized systems. However, most previous works on organ donation systems have focused on using Ethereum-based blockchain solutions, which offer limited control, a fixed set of consensus protocols, and no support for concurrent executions. In contrast, our work has utilized the Hyperledger Fabric framework to develop a network model of the organ donation system. We have designed and deployed a prototype system with smart contracts using Amazon Managed Blockchain Service. Additionally, we have built a client application that uses the Fabric SDK to interact with the network and perform various actions. To evaluate the performance of our system, we conducted extensive testing using the Hyperledger Caliper benchmarking tool. In our test bench, the system achieved a peak actual send rate of 389.1 transactions per second (TPS) for creating new records and 508.4 TPS for reading records. At a send rate of 800 TPS, the system took an average of 12.16 seconds to serve a request for creating a record and an average of 3.71 seconds to serve a request for reading a record. Future work is required to extend the functionalities of the system and identify potential endorsers and managers for this type of controlled blockchain network.</p>
A smart contract is a translation of a standard paper-based contract that can be enforced and executed by a contract management system. At a high level of abstraction, a contract is only a document that describes how the signing parties are to behave in different scenarios; nevertheless, the translation of a typical paper-based contract to its electronic counterpart has proved to be both time-consuming and difficult. The requirement for a language capable of capturing the core of a contract in simple phrases and definitions has been a focus of study for many years. EROP (Events, Rights, Obligations, Prohibitions) is a contract specification language that breaks a contract down into sets of events, rights, obligations, and prohibitions.
We consider a project (model) owner that would like to train a model by utilizing the local private data and compute power of interested data owners, i.e., trainers. Our goal is to design a data marketplace for such decentralized collaborative/federated learning applications that simultaneously provides i) proof-of-contribution based reward allocation so that the trainers are compensated based on their contributions to the trained model; ii) privacy-preserving decentralized model training by avoiding any data movement from data owners; iii) robustness against malicious parties (e.g., trainers aiming to poison the model); iv) verifiability in the sense that the integrity, i.e., correctness, of all computations in the data market protocol including contribution assessment and outlier detection are verifiable through zero-knowledge proofs; and v) efficient and universal design. We propose a blockchain-based marketplace design to achieve all five objectives mentioned above. In our design, we utilize a distributed storage infrastructure and an aggregator aside from the project owner and the trainers. The aggregator is a processing node that performs certain computations, including assessing trainer contributions, removing outliers, and updating hyper-parameters. We execute the proposed data market through a blockchain smart contract. The deployed smart contract ensures that the project owner cannot evade payment, and honest trainers are rewarded based on their contributions at the end of training. Finally, we implement the building blocks of the proposed data market and demonstrate their applicability in practical scenarios through extensive experiments.
Rongxin Xu, Shiva Raj Pokhrel, Qiujun Lan, Gang Li
Mobile Edge Computing (MEC) has been a promising paradigm for communicating and edge processing of data on the move. We aim to employ Federated Learning (FL) and prominent features of blockchain into MEC architecture such as connected autonomous vehicles to enable complete decentralization, immutability, and rewarding mechanisms simultaneously. FL is advantageous for mobile devices with constrained connectivity since it requires model updates to be delivered to a central point instead of substantial amounts of data communication. For instance, FL in autonomous, connected vehicles can increase data diversity and allow model customization, and predictions are possible even when the vehicles are not connected (by exploiting their local models) for short times. However, existing synchronous FL and Blockchain incur extremely high communication costs due to mobility-induced impairments and do not apply directly to MEC networks. We propose a fully asynchronous Blockchained Federated Learning (BFL) framework referred to as BFL-MEC, in which the mobile clients and their models evolve independently yet guarantee stability in the global learning process. More importantly, we employ post-quantum secure features over BFL-MEC to verify the client's identity and defend against malicious attacks. All of our design assumptions and results are evaluated with extensive simulations.
Currently, Gasper, the implemented consensus protocol of Ethereum, takes between 64 and 95 slots to finalize blocks. Because of that, a significant portion of the chain is susceptible to reorgs. The possibility to capture MEV (Maximum Extractable Value) through such reorgs can then disincentivize honestly following the protocol, breaking the desired correspondence of honest and rational behavior. Moreover, the relatively long time to finality forces users to choose between economic security and faster transaction confirmation. This motivates the study of the so-called single slot finality protocols: consensus protocols that finalize a block in each slot and, more importantly, that finalize the block proposed at a given slot within such slot. In this work we propose a simple, non-blackbox protocol that combines a synchronous dynamically available protocol with a partially synchronous finality gadget, resulting in a consensus protocol that can finalize one block per slot, paving the way to single slot finality within Ethereum. Importantly, the protocol we present can finalize the block proposed in a slot, within such slot.
Dynamic participation has recently become a crucial requirement for devising permissionless consensus protocols. This notion, originally formalized by Pass and Shi (ASIACRYPT 2017) through their "sleepy model", captures the essence of a system's ability to handle participants joining or leaving during a protocol execution. A dynamically available consensus protocol preserves safety and liveness while allowing dynamic participation. Blockchain protocols, such as Bitcoin's consensus protocol, have implicitly adopted this concept. In the context of Ethereum's consensus protocol, Gasper, Neu, Tas, and Tse (S&P 2021) presented an attack against LMD-GHOST -- the component of Gasper designed to ensure dynamic availability. Consequently, LMD-GHOST results unable to fulfill its intended function of providing dynamic availability for the protocol. Despite attempts to mitigate this issue, the modified protocol still does not achieve dynamic availability, highlighting the need for more secure dynamically available protocols. In this work, we present RLMD-GHOST, a synchronous consensus protocol that not only ensures dynamic availability but also maintains safety during bounded periods of asynchrony. This protocol is particularly appealing for practical systems where strict synchrony assumptions may not always hold, contrary to general assumptions in standard synchronous protocols. Additionally, we present the "generalized sleepy model", within which our results are proven. Building upon the original sleepy model proposed by Pass and Shi, our model extends it with more generalized and stronger constraints on the corruption and sleepiness power of the adversary. This approach allows us to explore a wide range of dynamic participation regimes, spanning from complete dynamic participation to no dynamic participation, i.e., with every participant online.
In the traditional mobile edge computing (MEC) system, the availability of MEC services is greatly limited for the edge users of the cell due to serious signal attenuation and inter-cell interference. User-centric MEC (UC-MEC) can be seen as a promising solution to address this issue. In UC-MEC, each user is served by a dedicated access point (AP) cluster enabled with MEC capability instead of a single MEC server, however, at the expense of more energy consumption and greater privacy risks. To achieve efficient and reliable resource utilization with user-centric services, we propose an energy-efficient blockchain-enabled UC-MEC system where blockchain operations and resource optimization are jointly performed. Firstly, we design a resource-aware, reliable, replicated, redundant, and fault-tolerant (R-RAFT) consensus mechanism to implement secure and reliable resource trading. Then, an optimization framework based on alternating direction method of multipliers (ADMM) is proposed to minimize the total energy consumed by wireless transmission, consensus, and task computing, where AP clustering, computing resource allocation, and bandwidth allocation are jointly considered. Simulation results show the superiority of the proposed UC-MEC system over reference schemes, with at most 33.96% reduction in the total delay and 48.77% reduction in the total energy consumption.
Biometric recognition as an efficient and hard-to-forge way of identification and verification has become an indispensable part of the current digital world. The fast evolution of this technology has been a strong incentive for integration into many applications. Meanwhile, blockchain, the decentralized ledger technology, has been widely received by both research and industry in the past few years, and it is being increasingly deployed today in many different applications, such as money transfer, IoT, healthcare, or logistics. Recently, researchers have started to speculate on the pros and cons and what the best applications would be when these two technologies cross paths. This paper provides a survey of the research literature on the combination of blockchain and biometrics and includes a first legal analysis of this integration based on GDPR to shed light on challenges and potentials. Although the integration of blockchain technology into the biometric sector is still in its infancy, with a growing body of literature discussing specific applications and advanced technological setups, this paper aims to provide a holistic understanding of blockchain applicability in biometrics. Based on published studies, this article discusses, among others, practical examples combining blockchain and biometrics for novel applications in PKI systems, distributed trusted services, and identity management. Challenges and limitations when combining blockchain and biometrics that motivate future work will also be discussed; e.g., blockchain networks at their current stage may not be efficient or economical for some real-time biometric applications. Finally, we also discuss key legal aspects of the EU General Data Protection Regulation (GDPR) related to this combination of technologies (blockchain and biometrics); for example, accountability, immutability, anonymity, and data protection elements.
In blockchain systems, the scarcity of a resource is used as a Sybil protection mechanism. In Proof-of-Work blockchains, that resource is computing power. In the event of a fork, the scarcity of this resource theoretically prevents miners from producing blocks on both branches of a fork. In Proof-of-Stake blockchains, because that resource is token stake, the computational cost of creating a block is negligible. In the event of a fork, and if no specific measures have been taken, rational block producers should extend both branches of the fork. In blockchains with sequential block production, a punishment mechanism known as slashing is often cited as a protection against the nothing-at-stake problem. However, in the context of a blockchain with parallel block production, it seems that slashing is not sufficient against the numerous divergence opportunities. In this paper, we propose a novel protection against the nothing-at-stake problem that takes the most out of BFT and Nakamoto-based consensus. By combining those approaches, we wish to scale up blockchains by allowing parallel block production without reconciliation.
Manaswini Piduguralla, Saheli Chakraborty, Parwat Singh Anjana, Sathya Peri
Blockchain technology is a distributed, decentralized, and immutable ledger system. It is the platform of choice for managing smart contract transactions (SCTs). Smart contracts are self-executing codes of agreement between interested parties commonly implemented using blockchains. A block contains a set of transactions representing changes to the system and a hash of the previous block. The SCTs are executed multiple times during the block production and validation phases across the network. The execution is sequential in most blockchain technologies. In this work, we incorporate a direct acyclic graph (DAG) based parallel scheduler framework for concurrent execution of SCTs. The dependencies among a block's transactions are represented through a concurrent DAG data structure that assists in throughput optimization. We have created a DAG scheduler module that can be incorporated into blockchain platforms for concurrent execution with ease. We have also formally established the safety and liveness properties of the DAG scheduler. For evaluation, our framework is implemented in Hyperledger Sawtooth V1.2.6. The performance across multiple smart contract applications is measured for various scheduler types. Experimental analysis shows that the proposed framework achieves notable performance improvements over the parallel SCT execution frameworks.
Ali Nikhalat-Jahromi, Ali Mohammad Saghiri, Mohammad Reza Meybodi
Learning Automaton (LA) is an adaptive self-organized model that improves its action-selection through interaction with an unknown environment. LA with finite action set can be classified into two main categories: fixed and variable structure. Furthermore, variable action-set learning automaton (VASLA) is one of the main subsets of variable structure learning automaton. In this paper, we propose VDHLA, a novel hybrid learning automaton model, which is a combination of fixed structure and variable action set learning automaton. In the proposed model, variable action set learning automaton can increase, decrease, or leave unchanged the depth of fixed structure learning automaton during the action switching phase. In addition, the depth of the proposed model can change in a symmetric (SVDHLA) or asymmetric (AVDHLA) manner. To the best of our knowledge, it is the first hybrid model that intelligently changes the depth of fixed structure learning automaton. Several computer simulations are conducted to study the performance of the proposed model with respect to the total number of rewards and action switching in stationary and non-stationary environments. The proposed model is compared with FSLA and VSLA. In order to determine the performance of the proposed model in a practical application, the selfish mining attack which threatens the incentive-compatibility of a proof-of-work based blockchain environment is considered. The proposed model is applied to defend against the selfish mining attack in Bitcoin and compared with the tie-breaking mechanism, which is a well-known defense. Simulation results in all environments have shown the superiority of the proposed model.
Nikolay Ivanov, Chenning Li, Qiben Yan, Zhiyuan Sun · 6 authors
The blockchain technology, initially created for cryptocurrency, has been re-purposed for recording state transitions of smart contracts—decentralized applications that can be invoked through external transactions. Smart contracts gained popularity and accrued hundreds of billions of dollars in market capitalization in recent years. Unfortunately, like all other computer programs, smart contracts are prone to security vulnerabilities that have incurred multibillion-dollar damages over the past decade. As a result, many automated threat mitigation solutions have been proposed to counter the security issues of smart contracts. These threat mitigation solutions include various tools and methods that are challenging to compare. This survey develops a comprehensive classification taxonomy of smart contract threat mitigation solutions within five orthogonal dimensions: defense modality, core method, targeted contracts, input-output data mapping, and threat model. We classify 133 existing threat mitigation solutions using our taxonomy and confirm that the proposed five dimensions allow us to concisely and accurately describe any smart contract threat mitigation solution. In addition to learning what the threat mitigation solutions do, we also show how these solutions work by synthesizing their actual designs into a set of uniform workflows corresponding to the eight existing defense core methods. We further create an integrated coverage map for the known smart contract vulnerabilities by the existing threat mitigation solutions. Finally, we perform the evidence-based evolutionary analysis, in which we identify trends and future perspectives of threat mitigation in smart contracts and pinpoint major weaknesses of the existing methodologies. For the convenience of smart contract security developers, auditors, users, and researchers, we deploy and maintain a regularly updated comprehensive open-source online registry of threat mitigation solutions, called Security Threat Mitigation (STM) Registry at https://seit.egr.msu.edu/research/stmregistry/ .
Security analysis of blockchain technology is an active domain of research. There has been both cryptographic and game-theoretic security analysis of Proof-of-Work (PoW) blockchains. Prominent work includes the cryptographic security analysis under the Universal Composable framework and Game-theoretic security analysis using Rational Protocol Design. These security analysis models rely on stricter assumptions that might not hold. In this paper, we analyze the security of PoW blockchain protocols. We first show how assumptions made by previous models need not be valid in reality, which attackers can exploit to launch attacks that these models fail to capture. These include Difficulty Alternating Attack, under which forking is possible for an adversary with less than 0.5 mining power, Quick-Fork Attack, a general bound on selfish mining attack and transaction withholding attack. Following this, we argue why previous models for security analysis fail to capture these attacks and propose a more practical framework for security analysis pRPD. We then propose a framework to build PoW blockchains PRAGTHOS, which is secure from the attacks mentioned above. Finally, we argue that PoW blockchains complying with the PRAGTHOS framework are secure against a computationally bounded adversary under certain conditions on the reward scheme.
Lioba Heimbach, Quentin Kniep, Yann Vonlanthen, Roger Wattenhofer
Many classical blockchains are known to have an embarrassingly low transaction throughput, down to Bitcoin's notorious seven transactions per second limit.Various proposals and implementations for increasing throughput emerged in the first decade of blockchain research. But how much concurrency is possible? In their early days, blockchains were mostly used for simple transfers from user to user. More recently, however, decentralized finance (DeFi) and NFT marketplaces have completely changed what is happening on blockchains. Both are built using smart contracts and have gained significant popularity. Transactions on DeFi and NFT marketplaces often interact with the same smart contracts. We believe this development has transformed blockchain usage. In our work, we perform a historical analysis of Ethereum's transaction graph. We study how much interaction between transactions there was historically and how much there is now. We find that the rise of DeFi and NFT marketplaces has led to an increase in "centralization" in the transaction graph. More transactions are now interconnected: currently there are around 200 transactions per block with 4000 interdependencies between them. We further find that the parallelizability of Ethereum's current interconnected transaction workload is limited. A speedup exceeding a factor of five is currently unrealistic.
Rastislav Budinský, Ivan Homoliak, Ivana Stančíková
In this paper, we review the undercutting attacks in the transaction-fee-based regime of proof-of-work (PoW) blockchains with the longest chain fork-choice rule. Next, we focus on the problem of fluctuations in mining revenue and the mining gap - i.e., a situation, in which the immediate reward from transaction fees does not cover miners' expenditures. To mitigate these issues, we propose a solution that splits transaction fees from a mined block into two parts - (1) an instant reward for the miner of a block and (2) a deposit sent to one or more fee-redistribution smart contracts ($\mathcal{FRSC}$s) that are part of the consensus protocol. At the same time, these redistribution smart contracts reward the miner of a block with a certain fraction of the accumulated funds of the incoming fees over a predefined time. This setting enables us to achieve several interesting properties that are beneficial for the incentive stability and security of the protocol. With our solution, the fraction of Default-Compliant miners who strictly do not execute undercutting attacks is lowered from the state-of-the-art result of 66% to 30%.
Margarita Capretto, Martín Ceresa, Antonio Fernández Anta, Antonio Russo · 5 authors
Blockchain technologies are facing a scalability challenge, which must be overcome to guarantee a wider adoption of the technology. This scalability issue is due to the use of consensus algorithms to guarantee the total order of the chain of blocks (and of the transactions within each block). However, total order is often not fully necessary, since important advanced applications of smart-contracts do not require a total order among all operations. A much higher scalability can potentially be achieved if a more relaxed order (instead of a total order) can be exploited. In this article, we propose a novel distributed concurrent data type, Setchain , which significantly improves scalability. A Setchain implements a grow-only set whose elements are not ordered, unlike conventional blockchain operations. When convenient, the Setchain allows forcing a synchronization barrier that assigns permanently an epoch number to a subset of the latest elements added, agreed by consensus. Therefore, two operations in the same epoch are not ordered, while two operations in different epochs are ordered by their respective epoch number. We present different Byzantine-tolerant implementations of Setchain, prove their correctness, and report on an empirical evaluation of a prototype implementation. Our results show that Setchain is orders of magnitude faster than consensus-based ledgers, since it implements grow-only sets with epoch synchronization instead of total order. Since the Setchain barriers can be synchronized with the underlying blockchain, Setchain objects can be used as a sidechain to implement many decentralized solutions with much faster operations than direct implementations on top of blockchains. Finally, we also present an algorithm that encompasses into a single process the combined behavior of the Byzantine servers, which simplifies correctness proofs by encoding the general attacker in a concrete implementation.
Decentralized systems built around blockchain technology promise clients an immutable ledger. They add a transaction to the ledger after it undergoes consensus among the replicas that run a Proof-of-Stake (PoS) or Byzantine Fault-Tolerant (BFT) consensus protocol. Unfortunately, these protocols face a long-range attack where an adversary having access to the private keys of the replicas can rewrite the ledger. An existing solution to this problem forces each committed block from these protocols to undergo another consensus, Proof-of-Work (PoW) consensus; POW protocol wastes computational resources as miners compete to solve complex puzzles. In this paper, we present the design of our Power-of-Collaboration (POC) protocol, which guards existing POS/BFT blockchains against long-range attacks and requires miners to collaborate rather than compete. POC guarantees fairness and accountability and only marginally degrades the throughput of the underlying system.
While blockchain and distributed ledger technology offer immense potential for applications in transparency, security, efficiency, censorship resistance, and more, they have been criticized due to the energy-intensive nature of the proof of work consensus algorithm, particularly in the context of Bitcoin mining. We systematically explore the state-of-the-art regarding the relationship between Bitcoin mining and grid decarbonization. We specifically focus on the role of flexible load response through proof of work mining as a potential contributor to renewable energy penetration and net decarbonization of the energy grid. The existing literature has not comprehensively examined this area, leading to conflicting views. We address the gap, analyzing the capabilities and limitations of Bitcoin mining in providing flexible load response services. Our findings show that renewable-based mining could potentially drive a net-decarbonizing effect on energy grids, although key adaptations in mining practices are needed to fully realize this potential. Overall, the paper suggests a re-evaluation of the environmental impact of Bitcoin mining, highlighting its potential role as a facilitator for renewable energy expansion, and decarbonization more broadly.
Sebastian Müller, Isabel Amigo, Alexandre Reiffers-Masson, Santiago Ruano-Rincón
In directed acyclic graph (DAG)-based distributed ledgers, unreferenced blocks (tips) form the backlog of a distributed queueing system. Each new block creates one tip and attempts to remove up to $k$ existing tips by referencing them. With heterogeneous propagation delays, these service decisions are made from delayed local information, so nodes may disagree on the backlog and some reference attempts are wasted. We study a continuous-time Poisson model with bounded heterogeneous delays and uniform tip selection. We prove that the embedded tip-configuration chain is irreducible, aperiodic, and positive Harris recurrent, and hence admits a unique stationary regime. The observer and local tip-pool sizes have stationary exponential moments, converge to their stationary limits, and satisfy almost-sure ergodic averages. We also derive a Little-type identity relating the stationary mean observer tip count to the mean time until a typical block is first referenced. Simulations are included as qualitative illustrations of the effects of delay variability and issuance heterogeneity.
Open access
2 source records
math.PR
cs.DC
Mathematical and Theoretical Epidemiology and Ecology Models
I study a repeated auction in which payments are made with a blockchain token created and initially owned by the auction designer. Unlike the ``virtual money'' previously examined in mechanism design, such tokens can be saved and traded outside the mechanism. I show that the present-discounted value of expected revenues equals that of a conventional dollar auction, but revenues accrue earlier and are less volatile. The optimal monetary policy burns the tokens used for payment, a practice common in blockchain-based protocols. I also show that the same outcome can be reproduced in a dollar auction if the auctioneer issues a suitable dollar-denominated security. This equivalence breaks down with moral hazard and contracting frictions: with severe contracting frictions the token auction dominates, whereas with mild contracting frictions the dollar auction combined with a dollar-denominated financial instrument is preferred.
We develop a model of coordination and allocation of decentralized multi-sided markets, in which our theoretical analysis is promisingly optimizing the decentralized transaction packaging process at high-throughput blockchains or Web 3.0 platforms. In contrast to the stylized centralized platform, the decentralized platform is powered by blockchain technology, which allows for secure and transparent Peer-to-Peer transactions among users. Traditional single-chain-based blockchains suffer from the well-known blockchain trilemma. Beyond the single-chain-based scheme, decentralized high-throughput blockchains adopt parallel protocols to reconcile the blockchain trilemma, implementing any tasking and desired allocation. However, unneglectable network latency may induce partial observability, resulting in incoordination and misallocation issues for the decentralized transaction packaging process at the current high-throughput blockchain protocols. To address this problem, we consider a strategic coordination mechanism for the decentralized transaction packaging process by using a game-theoretic approach. Under a tractable two-period model, we find a Bayesian Nash equilibrium of the miner's strategic transaction packaging under partial observability. Along with novel algorithms for computing equilibrium payoffs, we show that the decentralized platform can achieve an efficient and stable market outcome. The model also highlights that the proposed mechanism can endogenously offer a base fee per gas without any restructuration of the initial blockchain transaction fee mechanism. The theoretical results that underlie the algorithms also imply bounds on the computational complexity of equilibrium payoffs.
Ali Nikhalat Jahromi, Ali Mohammad Saghiri, Mohammad Reza Meybodi
The Bitcoin cryptocurrency has received much attention recently. In the network of Bitcoin, transactions are recorded in a ledger. In this network, the process of recording transactions depends on some nodes called miners that execute a protocol known as mining protocol. One of the significant aspects of mining protocol is incentive compatibility. However, literature has shown that Bitcoin mining's protocol is not incentive-compatible. Some nodes with high computational power can obtain more revenue than their fair share by adopting a type of attack called the selfish mining attack. In this paper, we propose an artificial intelligence-based defense against selfish mining attacks by applying the theory of learning automata. The proposed defense mechanism ignores private blocks by assigning weight based on block discovery time and changes current Bitcoin's fork resolving policy by evaluating branches' height difference in a self-adaptive manner utilizing learning automata. To the best of our knowledge, the proposed protocol is the literature's first learning-based defense mechanism. Simulation results have shown the superiority of the proposed mechanism against tie-breaking mechanism, which is a well-known defense. The simulation results have shown that the suggested defense mechanism increases the profit threshold up to 40\% and decreases the revenue of selfish attackers.
Monte Carlo simulations play a crucial role in all stages of particle collider experiments. There has been a long-term trend in HEP of both increasing collision energies and the luminosity. As a result, the requirements for MC simulations have become more rigorous: Their computational complexity has increased due to higher accuracy requirements. Additionally, more simulation data is required to allow data analysts to spot Standard Model deviations in observations of real data and enable the filtering of rare events. In order to keep up with the computational complexity of simulations and analysis of real data, distributed computing approaches are commonly employed. For instance, CERN relies on the Worldwide LHC Computing Grid (WLCG) in order to be able to store, process, distribute and analyze collision data. Since not every HEP experiment has access to these resources and the addition of new Grid servers is a complex process, this publication explores a novel distributed computing approach for HEP which is based on blockchain technology. It features the description of a novel Proof-of-Useful-Work consensus algorithm which aims to both support real-world HEP experiments with the production of required MC data and to secure the underlying blockchain infrastructure at the same time. Instead of being an alternative to WLCG or BOINC projects that rely on volunteer computing, it aims to be a complementary source of additional computing power. This publication also features a brief introduction into blockchain fundamentals and comparisons to existing distributed computing approaches.
Berk Cirisci, Constantin Enea, Suha Orhun Mutluergil
Distributed algorithms solving agreement problems like consensus or state machine replication are essential components of modern fault-tolerant distributed services. They are also notoriously hard to understand and reason about. Their complexity stems from the different assumptions on the environment they operate with, i.e., process or network link failures, Byzantine failures etc. In this paper, we propose a novel abstract representation of the dynamics of such protocols which focuses on quorums of responses (votes) to a request (proposal) that form during a run of the protocol. We show that focusing on such quorums, a run of a protocol can be viewed as working over a tree structure where different branches represent different possible outcomes of the protocol, the goal being to stabilize on the choice of a fixed branch. This abstraction resembles the description of recent protocols used in Blockchain infrastructures, e.g., the protocol supporting Bitcoin or HotStuff. We show that this abstraction supports reasoning about the safety of various algorithms, e.g., Paxos, PBFT, Raft, and HotStuff, in a uniform way. In general, it provides a novel induction based argument for proving that such protocols are safe.