Blockchain protocols typically aspire to run in the permissionless setting, in which nodes are owned and operated by a large number of diverse and unknown entities, with each node free to start or stop running the protocol at any time. This setting is more challenging than the traditional permissioned setting, in which the set of nodes that will be running the protocol is fixed and known at the time of protocol deployment. The goal of this paper is to provide a framework for reasoning about the rich design space of blockchain protocols and their capabilities and limitations in the permissionless setting. We propose a hierarchy of settings with different "degrees of permissionlessness", specified by the amount of knowledge that a protocol has about the current participants: These are the fully permissionless, dynamically available and quasi-permissionless settings. The paper also proves several results illustrating the utility of our analysis framework for reasoning about blockchain protocols in these settings. For example: (1) In the fully permissionless setting, even with synchronous communication and with severe restrictions on the total size of the Byzantine players, every deterministic protocol for Byzantine agreement has a non-terminating execution. (2) In the dynamically available and partially synchronous setting, no protocol can solve the Byzantine agreement problem with high probability, even if there are no Byzantine players at all. (3) In the quasi-permissionless and partially synchronous setting, by contrast, assuming a bound on the total size of the Byzantine players, there is a deterministic protocol solving state machine replication. (4) In the quasi-permissionless and synchronous setting, every proof-of-stake state machine replication protocol that uses only time-malleable cryptographic primitives is vulnerable to long-range attacks.
Blockchain explorers are important tools for quick look-ups of on-chain activities. However, as centralized data providers, their reliability remains under-studied. As a case study, we investigate Beaconcha.in , a leading explorer serving Ethereum’s proof-of-stake (PoS) update. According to the explorer, we find that more than 75% of slashable Byzantine actions were not slashed. Since Ethereum relies on the “stake-and-slash" mechanism to align incentives, this finding would at its face value cause concern over Ethereum’s security. However, further investigation reveals that all the apparent unslashed incidents were erroneously recorded due to the explorer’s mishandling of consensus edge cases. Besides the usual message of using caution with centralized information providers, our findings also call for attention to improving the monitoring of blockchain systems that support high-value applications.
Ahmad J. Alkhodair, Saraju P. Mohanty, Elias Kougianos
Distributed Ledger Technology (DLT) has been introduced using the most common consensus algorithm either for an electronic cash system or a decentralized programmable assets platform which provides general services. Most established reliable networks are unsuitable for all applications such as smart cities applications, and, in particular, Internet of Things (IoT) and Cyber Physical Systems (CPS) applications. The purpose of this paper is to provide a suitable DLT for IoT and CPS that could satisfy their requirements. The proposed work has been designed based on the requirements of Cyber Physical Systems. FlexiChain is proposed as a layer zero network that could be formed from independent blockchains. Also, NodeChain has been introduced to be a distributed (Unique ID) UID aggregation vault to secure all nodes' UIDs. Moreover, NodeChain is proposed to serve mainly FlexiChain for all node security requirements. NodeChain targets the security and integrity of each node. Also, the linked UIDs create a chain of narration that keeps track not merely for assets but also for who authenticated the assets. The security results present a higher resistance against four types of attacks. Furthermore, the strength of the network is presented from the early stages compared to blockchain and central authority. FlexiChain technology has been introduced to be a layer zero network for all CPS decentralized applications taking into accounts their requirements. FlexiChain relies on lightweight processing mechanisms and creates other methods to increase security.
Data synchronization in decentralized storage systems is essential to guarantee sufficient redundancy to prevent data loss. We present SNIPS, the first succinct proof of storage algorithm for synchronizing storage peers. A peer constructs a proof for its stored chunks and sends it to verifier peers. A verifier queries the proof to identify and subsequently requests missing chunks. The proof is succinct, supports membership queries, and requires only a few bits per chunk. We evaluated our SNIPS algorithm on a cluster of 1000 peers running Ethereum Swarm. Our results show that SNIPS reduces the amount of synchronization data by three orders of magnitude compared to the state-of-the-art. Additionally, creating and verifying a proof is linear with the number of chunks and typically requires only tens of microseconds per chunk. These qualities are vital for our use case, as we envision running SNIPS frequently to maintain sufficient redundancy consistently.
Kun Hao, Junchang Xin, Zhiqiong Wang, Zhongming Yao · 5 authors
Interoperable Blockchain Database (IBD) can enable users to execute transactions for sharing data stored in various blockchains maintained by different organizations or communities in a transparent manner. However, compared to traditional distributed databases, IBD can hardly provide high-level security and scalability, which are caused by many factors, such as system architecture, consensus protocol, and interactive pattern. Among them, the consensus protocol is the most critical factor, since the credibility of consensus nodes inside the corresponding blockchains are difficult to be guaranteed. Additionally, the consensus protocol directly affects the verification efficiency for given transactions in IBD. In this paper, we formally concern the problem of secure data sharing in IBD. We present a scheme namedHybridchainto execute transactions for sharing data securely and efficiently. We first propose a novel concept namedInteroperable Consensus Group(ICG) which organizes a set of basic consensus nodes into a group, each of which is responsible for managing at least one local blockchain. Then, we present an interoperable cross-chains consensus protocol to achieve eventual consistency of blockchain transactions. We conduct extensive experiments, and the evaluation results show that our proposed approach achieves superior performance.
Blockchain is a distributed ledger technology where all nodes in a blockchain maintain the same ledger. The key to a blockchain is to ensure the uniqueness of the ledger. Therefore, different consensus protocols have been designed to cater for different applications. Consensus protocols such as pow and pos allow nodes to enter and leave at any time but still ensure convergence, while PBFT and Raft protocols can speed up convergence in licensed blockchains but are relatively less secure. We analyse consensus protocols from a database perspective and can think of consensus protocols as consistency. We analyze the characteristics of consistency and propose CChain blockchain system, which integrates the eventual consistency method (CRDT) into Fabric for the first time. Compared with the native Fabric, the throughput is improved by more than 16X.
Permissioned blockchains are being widely applied to solve the trust problem in enterprise collaboration. However, most of these systems suffer from low throughput and flexibility lacking issues. In this paper, we present a blockchain system SChain with scalable concurrent execution based on a flexible architecture. SChain separates the functionality of a complete "node" into three sub-functions and assigns them to different peers within every organization. Then each organization can scale each sub-function flexibly with no need for negotiation between organizations. Based on this architecture, SChain explores scalable concurrent execution from two levels. First, SChain takes the advantage of multiple peers to execute transactions collectively, while promising they make the same results as one peer does serially. Second, SChain enables concurrent transaction execution across blocks to utilize the resources of peers fully, breaking up the block-by-block process manner, based on a pipelined workflow. The extensive evaluation results demonstrate that SChain significantly outperforms the serial execution and other competing systems-level approaches.
The problem of data synchronization arises in networked applications that require some measure of consistency. Indeed data synchronization approaches have demonstrated a significant potential for improving performance in various applications ranging from distributed ledgers to fog-enabled storage offloading for IoT. Although several protocols for data sets synchronization have been proposed over the years, there is currently no widespread utility implementing them, unlike the popular Rsync utility available for file synchronization. To that end, we describe a new middleware called GenSync that abstracts the subtleties of the state-of-the-art data synchronization protocols, allows users to choose protocols based on a comparative evaluation under realistic system conditions, and seamlessly integrate protocols in existing applications through a public API. We showcase GenSync through a case study, in which we integrate it into one of the world's largest wireless emulators and compare the performance of its included protocols.
In the context of consortium blockchain, consensus protocols set permission mechanisms to maintain a relatively fixed group of participants. They can easily use distributed consistent algorithms for achieving deterministic and efficient consensus and generate incessant blocks as the ledger. However, most of the existing consensus protocols do not sufficiently leverage the chain structure of blocks, and therefore leaving room for performance improvement. In this paper, we first propose a Hashchain-based Consensus Acceleration (HCA) protocol. The HCA protocol enables a leader to generate blocks that contain a quorum of votes on the previous block, and allow voters to re-vote for accelerating the block generation to Byzantine Fault Tolerance (BFT) consensus protocols. Then, we present a rolling-based leader selection (RLS) scheme to further optimize the HCA protocol. In the RLS scheme, the leader is changed in a round-robin fashion. Finally, theoretical analysis proves the safety, liveness and responsiveness of the optimized HCA protocol, while experimental evaluation shows that the optimized HCA protocol outperforms the existing BFT consensus protocols, from the viewpoint of efficiency.
Stefano Bistarelli, Andrea Bracciali, Rick Klomp, Ivan Mercanti
The Bitcoin language SCRIPT has undergone several technically non-trivial updates, still striving from security and minimal risk exposure. Up-to-date, formal verification is of strong interest for script programs that validate the correctness of the Bitcoin decentralised ledger, and allow more and more sophisticated protocols and decentralised applications to be implemented on top of Bitcoin transactions. We propose ScriFy, a comprehensive framework for the verification of the current SCRIPT language: a symbolic semantics and execution model, a model checker, and a modular (dockered), open-source verifier. Given the SCRIPT code that locks a Bitcoin transaction, ScriFy returns the minimal information needed to successfully execute it and authorise the transaction. Distinguishably, ScriFy features both recently added SCRIPT operators and an enhanced analysis, which considers prior information in the ledger. The framework is proved correct and validated through significant examples.
Blockchain technology has gained momentum due to its immutability and transparency. Several blockchain platforms, each with different consensus protocols, have been proposed. However, choosing and configuring such a platform is a non-trivial task. Numerous benchmarking tools have been introduced to test the performance of blockchain solutions. Yet, these tools are often limited to specific blockchain platforms or require complex configurations. Moreover, they tend to focus on one-off batch evaluation models, which may not be ideal for longer-running instances under continuous workloads. In this work, we presentBlockCompass, an all-inclusive blockchain benchmarking tool that can be easily configured and extended. We demonstrate howBlockCompasscan evaluate the performance of various blockchain platforms and configurations, including Ethereum Proof-of-Authority, Ethereum Proof-of-Work, Hyperledger Fabric Raft, Hyperledger Sawtooth with Proof-of-Elapsed-Time, Practical Byzantine Fault Tolerance, and Raft consensus algorithms, against workloads that continuously fluctuate over time. We show how continuous transactional workloads may be more appropriate than batch workloads in capturing certain stressful events for the system. Finally, we present the results of a usability study about the convenience and effectiveness offered byBlockCompassin blockchain benchmarking.
Christian Berger, Signe Schwarz-Rüsch, Arne Vogel, Kai Bleeke · 7 authors
With the advancement of blockchain systems, many recent research works have proposed distributed ledger technology~(DLT) that employs Byzantine fault-tolerant~(BFT) consensus protocols to decide which block to append next to the ledger. Notably, BFT consensus can offer high performance, energy efficiency, and provable correctness properties, and it is thus considered a promising building block for creating highly resilient and performant blockchain infrastructures. Yet, a major ongoing challenge is to make BFT consensus applicable to large-scale environments. A large body of recent work addresses this challenge by developing novel ideas to improve the scalability of BFT consensus, thus opening the path for a new generation of BFT protocols tailored to the needs of blockchain. In this survey, we create a systematization of knowledge about the novel scalability-enhancing techniques that state-of-the-art BFT consensus protocols use. For our comparison, we closely analyze the efforts, assumptions, and trade-offs these protocols make.
Abstract We introduce semitopology, a generalization of point-set topology that removes the restriction that intersections of open sets need necessarily be open. The intuition is that points represent participants in a decentralized system, and open sets represent collections of participants that collectively have the authority to collaborate to update their local state; we call this an actionable coalition. Examples of actionable coalition include: majority stakes in proof-of-stake blockchains; communicating peers in peer-to-peer networks; and even pedestrians working together to not bump into one another in the street. Where actionable coalitions exist, they have in common that collaborations are local (updating the states of the participants in the coalition, but not immediately those of the whole system); collaborations are voluntary (up to and including breaking rules); participants may be heterogeneous in their computing power or in their goals (not all pedestrians want to go to the same place); participants can choose with whom to collaborate; and they are not assumed subject to permission or synchronization by a central authority. We develop a topology-flavoured mathematics that goes some way to explaining how and why these complex decentralized systems can exhibit order, and gives us new ways to understand existing practical implementations. Semitopology is also interesting in and of itself, having a rich and interesting theory that quickly deviates from standard accounts on topological spaces. It soon becomes clear that the most interesting semitopologies are rather ill-behaved from the usual viewpoint, as they are never Hausdorff. A notion of ‘transitive open sets’ (topens) becomes central to the story, as topens define subsets of participants who should decide the same value in a distributed system that tries to achieve consensus, and points are called ‘regular’ when they have a topen neighbourhood. The theory is then further developed by introducing intertwined points, closures, closed sets and two interesting characterizations of regularity.
For Nakamoto's longest-chain consensus protocol, whose proof-of-work (PoW) and proof-of-stake (PoS) variants power major blockchains such as Bitcoin and Cardano, we revisit the classic problem of the security--performance tradeoff: Given a network of nodes with finite communication- and computation-resources, against what fraction of adversary power is Nakamoto consensus (NC) secure for a given block production rate? State-of-the-art analyses of NC fail to answer this question, because their bounded-delay model does not capture the rate limits to nodes' processing of blocks, which cause congestion when blocks are released in quick succession. We develop a new analysis technique to prove a refined security--performance tradeoff for PoW NC in a bounded-capacity model. In this model, we show that, in contrast to the classic bounded-delay model, Nakamoto's private attack is no longer the worst attack, and a new attack we call the teasing strategy, that exploits congestion, is strictly worse. In PoS, equivocating blocks can exacerbate congestion, making traditional PoS NC insecure except at very low block production rates. To counter such equivocation spamming, we present a variant of PoS NC we call Blanking NC (BlaNC), which achieves the same resilience as PoW NC.
Welcome to the fifteenth Jubilee International Symposium on Autonomous Decentralized Systems (ISADS).As Lifetime Honorary Chair, I would like to thank you for coming to ISADS 2023. ISADS was founded in 1993 atKawasaki, Japan.Since then, ISADSs have been held world-wide every two years except in 2021 due to pandemic.They were successful in their high quality and broad international participation from academia, government and industry.At the first ISADS, the concept of autonomous decentralized systems (ADS) was well recognized.During the last 30 years, fields of ADS have been substantially advanced to provide solutions for control, communication, computing, service systems and further to organization and finance management, such as FinTech along with rapid development of other related technologies and management.ISADS 2023 reflects not only such maturity but also innovation in ADS concept, technology and application as well as further integration with other heterogeneous fields.Now, structures of Society, Value, Business and Technology have been unpredictably and rapidly transformed under climate change, pandemic and economic turmoil.ADS, which behaves as a living system comprised of largely autonomous and decentralized subsystems, has been successfully contributing to fulfill adaptive, reliable and expandable properties under changing and transforming environment as consistent concept.The continuous growth of ISADS in size and diversity is reflected by the sponsoring society, the Computer Society of the Institute of Electrical and Electric Engineers (IEEE) together with the cooperating societies including the International Federation for Information Processing (IFIP), the International Federation of Automatic Control (IFAC), the Institute of Electronics, Information and Communication Engineers (IEICE), Japan and Object Management Group (OMG), as well as the strong supporting organization of Universidad Panamericana, Mexico.I hope that you will find the program stimulating and that you will take the opportunity to meet with your colleagues from around the world to engage in social as well as technical discussions.In addition, technical sessions and workshops on the hot topics of technologies and their advanced applications are jointly arranged.The success of the symposium depends on the dedication and contributions of many volunteers, committee members, authors, reviewers, speakers, workshop chairs, session chairs and supporting personnel, and the strong organizations.I would like to thank Honorary Chairs, Bojan Cukic and General Chair, Carlos Perez for their direction.
Modern public and private infrastructure is increasingly large and complex regardless of the industry within which it is deployed - communications, power, transportation, manufacturing, finance, etc. Autonomous Decentralized Systems (ADSs) analogous to living systems with autonomous and decentralized subsystems have been developed to support the requirements of modern infrastructure. Large-scale infrastructure is increasingly a significant source of data on both its own operations as well as the society dependent on it. Big data from infrastructure can thus supply a variety of artificial and augmented intelligence systems. Large complex infrastructures typically require large complex organizations to operate and maintain. Such organizations though are typically centralized and constrained by bureaucratic policies and procedures. Decentralized Autonomous Organizations (DAOs) are emerging that may provide better transparency, autonomy and decentralization for the manner in which these large-scale infrastructures are operated. The paper contrasts DAOs and ADSs before identifying the requirements for DAO administration of an ADS.
Luca Olivieri, Thomas Wiben Jensen, Luca Negrini, Fausto Spoto
Smart contracts are immutable code deployed in a blockchain, whose execution modifies its global state. Code im-mutability leads to immutable bugs. To prevent such bugs, static program analysis infers information about the behavior of the code, statically, before code execution and deployment. This paper introduces MichelsonLiSA, a static analyzer based on abstract interpretation for the verification of smart contracts written in the Michelson low-level language of the Tezos blockchain. It applies MichelsonLiSA to the identification of security issues arising from cross-contract invocations.
Cezara Drăgoi, Constantin Enea, Srinidhi Nagendra, Mandayam Srivas
Large-scale, fault-tolerant, distributed systems are the backbone for many critical software services. Since they must execute correctly in a possibly adversarial environment with arbitrary communication delays and failures, the underlying algorithms are intricate. In particular, achieving consistency and data retention relies on intricate consensus (state machine replication) protocols. Ensuring the reliability of implementations of such protocols remains a significant challenge because of the enormous number of exceptional conditions that may arise in production. We propose a methodology and a tool called Netrix for testing such implementations that aims to exploit programmer's knowledge to improve coverage, enables robust bug reproduction, and can be used in regression testing across different versions of an implementation. As evaluation, we apply our tool to a popular proof of stake blockchain protocol, Tendermint, which relies on a Byzantine consensus algorithm, a benign consensus algorithm, Raft, and BFT-Smart. We were able to identify 4 deviations of the Tendermint implementation from the protocol specification and check their absence on an updated implementation. Additionally, we were able to reproduce 4 previously known bugs in Raft.
Countless endeavors have been undertaken to address the Byzantine Generals Problem, a generalization of the Two Generals Problem. The emergence of proof of work (PoW) for Bitcoin has led to various consensus algorithms diverging, and comparable existing consensus algorithms are being gradually utilized interchangeably, or only developed for each specific application domain. Our approach employs an evolutionary phylogeny method to classify blockchain consensus algorithms based on their historical development and current usage. To demonstrate the relatedness and lineage of distinct algorithms, as well as to support the recapitulation theory, which posits that the evolutionary history of its mainnets is mirrored in the development of an individual consensus algorithm, we present a taxonomy. We have created a comprehensive classification of past and present consensus algorithms that serves to organize this swift consensus algorithm evolution period. By recognizing similarities, we have compiled a list of different verified consensus algorithms and performed clustering on over 38 of these. Our new taxonomic tree presents five taxonomic ranks, including the evolutionary process and decision-making method, as a technique for analyzing correlation. Through the examination of the evolution and utilization of these algorithms, we have developed a systematic and hierarchical taxonomy that enables the grouping of consensus algorithms into distinct categories. The proposed method classifies various consensus algorithms according to taxonomic ranks and aims to reveal the direction of research on the application of blockchain consensus algorithms for each domain.
Summary The idea of hash time‐lock contracts (HTLCs) has been around from 2013. Nowadays these contracts power the majority of atomic swaps making decentralized exchange of tokens possible. On the other hand, HTLCs also have some flaws. For example they can only be instantiated between two parties. This is highly inefficient when many participants want to exchange tokens between the same pair of blockchains at the same time, because the number of transactions increases linearly in the number of participants. To solve this problem, in this article, we present MP‐HTLC. MP‐HTLC lets multiple users exchange tokens on different blockchains in a single instantiation of the protocol without any leader election. We prove that in case of a UTXO‐based blockchain the number of transactions remains constant regardless the number of participants. We are able to maintain the security assumptions of HTLCs using multiparty computation in the creation of the secret preimage and threshold signatures to manage transaction signing. We also present an implementation for each of the aspects of the protocol.
Blockchain databases have attracted widespread attention but suffer from poor scalability due to underlying non-scalable blockchains. While blockchain sharding is necessary for a scalable blockchain database, it poses a new challenge named on-chain cross-shard database services. Each cross-shard database service (e.g., cross-shard queries or inter-shard load balancing) involves massive cross-shard data exchanges, while the existing cross-shard mechanisms need to process each cross-shard data exchange via the consensus of all nodes in the related shards (i.e., on-chain) to resist a Byzantine environment of blockchain, which eliminates sharding benefits. To tackle the challenge, this paper presents GriDB, the first scalable blockchain database, by designing a novel off-chain cross-shard mechanism for efficient cross-shard database services. Borrowing the idea of off-chain payments, GriDB delegates massive cross-shard data exchange to a few nodes, each of which is randomly picked from a different shard. Considering the Byzantine environment, the untrusted delegates cooperate to generate succinct proof for cross-shard data exchanges, while the consensus is only responsible for the low-cost proof verification. However, different from payments, the database services' verification has more requirements (e.g., completeness, correctness, freshness, and availability); thus, we introduce several new authenticated data structures (ADS). Particularly, we utilize consensus to extend the threat model and reduce the complexity of traditional accumulator-based ADS for verifiable cross-shard queries with a rich set of relational operators. Moreover, we study the necessity of inter-shard load balancing for a scalable blockchain database and design an off-chain and live approach for both efficiency and availability during balancing. An evaluation of our prototype shows the performance of GriDB in terms of scalability in workloads with queries and updates.
A consensus mechanism determines how partici-pants agree on a transaction or a state change in the distributed ledger technology (DLT) such as blockchain by receiving consent from majority of network participants before inclusion of a block to blockchain. The consensus mechanism is required in almost every blockchain application. Most contemporary blockchain consensus systems need massive processing capabilities, signif-icant energy consumption, and reliance on monetary stake. Because of these limitations, mainstream consensus approaches are unsuitable for low-resource applications such as IoT. As a result, this paper introduces a new consensus protocol known as “Delegated Proof of Accessibility” (DPoAC). The DPoAC protocol minimized the computational resource needs and energy usage demands of the existing proof-based consensus mechanisms, making it appropriate to use in applications with limited resources, such the Internet of Things. In addition, the lack of a financial stake in DPoAC makes it ideal for blockchain-IoT convergence.
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.
Founded in 2017, Algorand is one of the world's first carbon-negative, public blockchains inspired by proof of stake. Algorand uses a Byzantine agreement protocol to add new blocks to the blockchain. The protocol can tolerate malicious users as long as a supermajority of the stake is controlled by non-malicious users. The protocol achieves about 100x more throughput compared to Bitcoin and can be easily scaled to millions of nodes. Despite its impressive features, Algorand lacks a reward-distribution scheme that can effectively incentivize nodes to participate in the protocol. In this work, we study the incentive issue in Algorand through the lens of game theory. We model the Algorand protocol as a Bayesian game and propose a novel reward scheme to address the incentive issue in Algorand. We derive necessary conditions to ensure that participation in the protocol is a Bayesian Nash equilibrium under our proposed reward scheme even in the presence of a malicious adversary. We also present quantitative analysis of our proposed reward scheme by applying it to two real-world deployment scenarios. We estimate the costs of running an Algorand node and simulate the protocol to measure the overheads in terms of computation, storage, and networking.