Search

We consider the problem of supporting payment transactions in an asynchronous system in which up to $f$ validators are subject to Byzantine failures under the control of an adaptive adversary. It was shown that, in the case of a single owner, this problem can be solved without consensus by using byzantine quorum systems (requiring a quorum of $2f+1$ validations per transaction). Nonetheless, the process of validating transactions remains sequential. For example, if one has a balance of ten coins and intends to make separate payments of two coins each to two distinct recipients, both transactions must undergo processing by a common correct validator. On the other hand, these two transactions are non-conflicting as they do not lead to double spending, allowing in principle for parallel validation. In this paper, we show that it is possible to validate payment transactions in parallel with less than $f$ validations per transaction in an asynchronous system, provided that each transaction spends only a small fraction of a balance. Our solution relies on a novel class of probabilistic quorum systems that we introduce in this paper, termed \textit{$(k_1,k_2)$-quorum systems}. In the absence of an adaptive adversary, \textit{$(k_1,k_2)$-quorum systems} can be used to enable concurrent and asynchronous validation of up to $k_1$ transactions while preventing validation of more than $k_2$ transactions. Employing a $(k_1, k_2)$-quorum system, we introduce protocols enabling a payer to validate multiple \textit{fractional spending} transactions in parallel with less than $f+1$ validations per transaction. Subsequently, the payer reclaims any remaining funds through a fully validated transaction, referred to as a \textit{settlement} transaction., Comment: arXiv admin note: substantial text overlap with arXiv:2301.10149

In May 2023, the Ethereum blockchain experienced its first inactivity leak, a mechanism designed to reinstate chain finalization amid persistent network disruptions. This mechanism aims to reduce the voting power of validators who are unreachable within the network, reallocating this power to active validators. This paper investigates the implications of the inactivity leak on safety within the Ethereum blockchain. Our theoretical analysis reveals scenarios where actions by Byzantine validators expedite the finalization of two conflicting branches, and instances where Byzantine validators reach a voting power exceeding the critical safety threshold of one-third. Additionally, we revisit the probabilistic bouncing attack, illustrating how the inactivity leak can result in a probabilistic breach of safety, potentially allowing Byzantine validators to exceed the one-third safety threshold. Our findings uncover how penalizing inactive nodes can compromise blockchain properties, particularly in the presence of Byzantine validators capable of coordinating actions.

Failure Mode, Effects and Criticality Analysis (FMECA) is one of the safety analysis methods recommended by most of the international standards. The classical FMECA is made in a form of a table filled in either manually or by using safety analysis tools. In both cases, the design engineers have to choose the trade-offs between safety and other development constraints. In the case of complex cyber-physical systems (CPS) with thousands of specified constraints, this may lead to severe problems and significantly impact the overall criticality of CPS. In this paper, we propose to adopt optimization techniques to automate the decision making process conducted after FMECA of CPS. We describe a multi-agent based optimization method which extends classical FMECA for offering optimal solutions in terms of criticality and development constraints of CPS., Comment: 13 pages, 2 figures, 1 table, "2nd International Workshop on Emerging Ideas and Trends in Engineering of Cyber-Physical Systems, part of Cyber-Physical Systems Week, April 2015, Seattle, USA"

Distributed immutable ledgers, or blockchains, allow the secure digitization of evidential transactions without relying on a trusted third-party. Evidential transactions involve the exchange of any form of physical evidence, such as money, birth certificate, visas, tickets, etc. Most of the time, evidential transactions occur in the context of complex procedures, called evidential protocols, among physical agents. The blockchain provides the mechanisms to transfer evidence, while smart contracts - programs executing within the blockchain in a decentralized and replicated fashion - allow encoding evidential protocols on top of a blockchain. As a smart contract foregoes trusted third-parties and runs on several machines anonymously, it constitutes a highly critical program that has to be secure and trusted-by-design. While most of the current smart contract languages focus on easy programmability, they do not directly address the need of guaranteeing trust and accountability, which becomes a significant issue when evidential protocols are encoded as smart contracts., Comment: 17 pages, 1 algorithm, The 29th Francophone Days of Application Languages - JFLA 2018

This paper presents a novel adversary model specifically tailored to distributed systems, aiming to assess the security of blockchain networks. Building upon concepts such as adversarial assumptions, goals, and capabilities, our proposed adversary model classifies and constrains the use of adversarial actions based on classical distributed system models, defined by both failure and communication models. The objective is to study the effects of these allowed actions on the properties of distributed protocols under various system models. A significant aspect of our research involves integrating this adversary model into the Multi-Agent eXperimenter (MAX) framework. This integration enables fine-grained simulations of adversarial attacks on blockchain networks. In this paper, we particularly study four distinct fairness properties on Hyperledger Fabric with the Byzantine Fault Tolerant Tendermint consensus algorithm being selected for its ordering service. We define novel attacks that combine adversarial actions on both protocols, with the aim of violating a specific client-fairness property. Simulations confirm our ability to violate this property and allow us to evaluate the impact of these attacks on several order-fairness properties that relate orders of transaction reception and delivery., Comment: 10 pages, 8 figures

Blockchain applications are witnessing rapid evolution, necessitating the integration of upgradeable smart contracts. Software patterns have been proposed to summarize upgradeable smart contract best practices. However, research is missing on the comparison of these upgradeable smart contract patterns, especially regarding gas costs related to deployment and execution. This study aims to provide an in-depth analysis of gas costs associated with two prevalent upgradeable smart contract patterns: the Proxy and diamond patterns. The Proxy pattern utilizes a Proxy pointing to a logic contract, while the diamond pattern enables a Proxy to point to multiple logic contracts. We conduct a comparative analysis of gas costs for both patterns in contrast to a traditional non-upgradeable smart contract. We derive from this analysis a theoretical contribution in the form of two consolidated blockchain patterns and a corresponding decision model. By so doing we hope to contribute to the broader understanding of upgradeable smart contract patterns.

We consider the problem of supporting payment transactions in an asynchronous system in which up to $f$ validators are subject to Byzantine failures under the control of an adaptive adversary. It was shown that this problem can be solved without consensus by using byzantine quorum systems (requiring at least $2f+1$ validations per transaction in asynchronous systems). We show that it is possible to validate transactions in parallel with less than $f$ validations per transaction if each transaction spends no more that a small fraction of a balance. Our solution relies on a novel quorum system that we introduce in this paper and that we call $(k_1,k_2)$-quorum systems. In the presence of a non-adaptive adversary, these systems can be used to allow up to $k_1$ transactions to be validated concurrently and asynchronously but prevent more than $k_2$ transactions from being validated. If the adversary is adaptive, these systems can be used to allow $k_1$ transaction to be validated and prevent more than $k'_2 > k_2$ transactions from being validated, the difference $k'_2-k_2$ being dependent on the quorum system's {\em validation slack}, which we define in this paper. Using $(k_1,k_2)$-quorum systems, a payer can execute multiple partial spending transactions to spend a portion of its initial balance with less than full quorum validation (less than $f$ validations per transaction) then reclaim any remaining funds using one fully validated transaction, which we call a {\em settlement} transaction., Comment: 26 pages, 2 figures

Ethereum has undergone a recent change called \textit{the Merge}, which made Ethereum a Proof-of-Stake blockchain, shifting closer to BFT consensus. Ethereum, which wished to keep the best of the two protocol designs (BFT and Nakomoto-style), now has a convoluted consensus protocol as its core. The result is a blockchain being possibly produced in a tree-like form while participants try to finalize blocks. We categorize different attacks jeopardizing the liveness of the protocol. The Ethereum community has responded by creating patches against some of them. We discovered a new attack on the patched protocol. To support our analysis, we propose a new high-level formalization of the properties of liveness and availability of the Ethereum blockchain, and we provide a pseudo-code. We believe this formalization to be helpful for other analyses as well. Our results yield that the Ethereum Proof-of-Stake has safety but only probabilistic liveness. The probability of the liveness is influenced by the parameter describing the time frame allowed for validators to change their mind about the current main chain.

In a single secret leader election protocol (SSLE), one of the system participants is chosen and, unless it decides to reveal itself, no other participant can identify it. SSLE has a great potential in protecting blockchain consensus protocols against denial of service (DoS) attacks. However, all existing solutions either make strong synchrony assumptions or have expiring registration, meaning that they require elected processes to re-register themselves before they can be re-elected again. This, in turn, prohibits the use of these SSLE protocols to elect leaders in partially-synchronous consensus protocols as there may be long periods of network instability when no new blocks are decided and, thus, no new registrations (or re-registrations) are possible. In this paper, we propose Homomorphic Sortition -- the first asynchronous SSLE protocol with non-expiring registration, making it the first solution compatible with partially-synchronous leader-based consensus protocols. Homomorphic Sortition relies on Threshold Fully Homomorphic Encryption (ThFHE) and is tailored to proof-of-stake (PoS) blockchains, with several important optimizations with respect to prior proposals. In particular, unlike most existing SSLE protocols, it works with arbitrary stake distributions and does not require a user with multiple coins to be registered multiple times. Our protocol is highly parallelizable and can be run completely off-chain after setup. Some blockchains require a sequence of rounds to have non-repeating leaders. We define a generalization of SSLE, called Secret Leader Permutation (SLP) in which the application can choose how many non-repeating leaders should be output in a sequence of rounds and we show how Homomorphic Sortition also solves this problem.

In the industry, blockchains are increasingly used as the backbone of product and process traceability. Blockchain-based traceability participates in the demonstration of product and/or process compliance with existing safety standards or quality criteria. In this perspective, services and applications built on top of blockchains are business-critical applications, because an intended failure or corruption of the system can lead to an important reputation loss regarding the products or the processes involved. The development of a blockchain-based business-critical application must be then conducted carefully, requiring a thorough justification of its dependability and security. To this end, this paper encourages an engineering perspective rooted in well-understood tools and concepts borrowed from the engineering of safety-critical systems. Concretely, we use a justification framework, called CAE (Claim, Argument, Evidence), by following an approach based on assurance cases, in order to provide convincing arguments that a business-critical blockchain-based application is dependable and secure. The application of this approach is sketched with a case study based on the blockchain HYPERLEDGER FABRIC., Comment: 8 pages, 6 figures, The Third IEEE International Conference on Blockchain Computing and Applications (BCCA 2021)

Multi-party random number generation is a key building-block in many practical protocols. While straightforward to solve when all parties are trusted to behave correctly, the problem becomes much more difficult in the presence of faults. In this context, this paper presents RandSolomon, a protocol that allows a network of N processes to produce an unpredictable common random number among the non-faulty of them. We provide optimal resilience for partially-synchronous systems where less than a third of the participants might behave arbitrarily and, contrary to many solutions, we do not require at any point faulty-processes to be responsive.

This paper revisits the ubiquitous problem of achieving state machine replication in blockchains based on repeated consensus, like Tendermint. To achieve state machine replication in blockchains built on top of consensus, one needs to guarantee fairness of user transactions. A huge body of work has been carried out on the relation between state machine replication and consensus in the past years, in a variety of system models and with respect to varied problem specifications. We systematize this work by proposing novel and rigorous abstractions for state machine replication and repeated consensus in a system model that accounts for realistic blockchains in which blocks may contain several transactions issued by one or more users, and where validity and order of transactions within a block is determined by an external application-dependent function that can capture various approaches for order-fairness in the literature. Based on these abstractions, we propose a reduction from state machine replication to repeated consensus, such that user fairness is achieved using the consensus module as a black box. This approach allows to achieve fairness as an add-on on top of preexisting consensus modules in blockchains based on repeated consensus., Comment: 11 pages, 2 figures, 5 algorithms

An accountable distributed system provides means to detect deviations of system components from their expected behavior. It is natural to complement fault detection with a reconfiguration mechanism, so that the system could heal itself, by replacing malfunctioning parts with new ones. In this paper, we describe a framework that can be used to implement a large class of accountable and reconfigurable replicated services. We build atop the fundamental lattice agreement abstraction lying at the core of storage systems and cryptocurrencies. Our asynchronous implementation of accountable lattice agreement ensures that every violation of consistency is followed by an undeniable evidence of misbehavior of a faulty replica. The system can then be seamlessly reconfigured by evicting faulty replicas, adding new ones and merging inconsistent states. We believe that this paper opens a direction towards asynchronous "self-healing" systems that combine accountability and reconfiguration.

There exist many forms of Blockchain finality conditions, from deterministic to probabilistic terminations. To favor availability against consistency in the face of partitions, most blockchains only offer probabilistic eventual finality: blocks may be revoked after being appended to the blockchain, yet with decreasing probability as they sink deeper into the chain. Other blockchains favor consistency by leveraging the immediate finality of Consensus-a block appended is never revoked-at the cost of additional synchronization. In this paper, we focus on necessary and sufficient conditions to implement a blockchain with deterministic eventual finality, which ensures that selected main chains at different processes share a common increasing prefix. This is a much weaker form of finality that allows us to provide a solution in an asynchronous system subject to unlimited number of byzantine failures. We study stronger forms of eventual finality as well and show that it is unfortunately impossible to provide a bounded displacement. By bounded displacement we mean that the (unknown) number of blocks that can be revoked from the current blockchain is bounded. This problem reduces to consensus or eventual consensus depending on whether the bound is known or not. We also show that the classical selection mechanism, such as in Bitcoin, that appends blocks at the longest chain is not compliant with a solution to eventual finality.

Committee-based blockchains are among the most popular alternatives of proof-of-work based blockchains, such as Bitcoin. They provide strong consistency (no fork) under classical assumptions, and avoid using energy-consuming mechanisms to add new blocks in the blockchain. For each block, these blockchains use a committee that executes Byzantine-fault tolerant distributed consensus to decide the next block they will add in the blockchain. Unlike Bitcoin, where there is only one creator per block with high probability, in committee-based blockchain any block is cooperatively created. In order to incentivize committee members to participate to the creation of new blocks rewarding schemes have to be designed. In this paper, we study the fairness of rewarding in committee-based blockchains and we provide necessary and sufficient conditions on the system communication under which it is possible to have a fair reward mechanism.

Reconfiguration is one of the central mechanisms in distributed systems. Due to failures and connectivity disruptions, the very set of service replicas (or servers) and their roles in the computation may have to be reconfigured over time. To provide the desired level of consistency and availability to applications running on top of these servers, the clients of the service should be able to reach some form of agreement on the system configuration. We observe that this agreement is naturally captured via a lattice partial order on the system states. We propose an asynchronous implementation of reconfigurable lattice agreement that implies elegant reconfigurable versions of a large class of lattice abstract data types, such as max-registers and conflict detectors, as well as popular distributed programming abstractions, such as atomic snapshot and commit-adopt.

In this paper we analyze from the game theory point of view Byzantine Fault Tolerant blockchains when processes exhibit rational or Byzantine behavior. Our work is the first to model the Byzantine-consensus based blockchains as a committee coordination game. Our first contribution is to offer a game-theoretical methodology to analyse equilibrium interactions between Byzantine and rational committee members in Byzantine Fault Tolerant blockchains. Byzantine processes seek to inflict maximum damage to the system, while rational processes best-respond to maximise their expected net gains. Our second contribution is to derive conditions under which consensus properties are satisfied or not in equilibrium. When the majority threshold is lower than the proportion of Byzantine processes, invalid blocks are accepted in equilibrium. When the majority threshold is large, equilibrium can involve coordination failures , in which no block is ever accepted. However, when the cost of accepting invalid blocks is large, there exists an equilibrium in which blocks are accepted iff they are valid.

The paper presents Pluralize a formal logical framework able to extend the execution of blockchain transactions to events coming from external oracles, like external time, sensor data, human-made declarations, etc. These events are by essence non-reliable, since transaction execution can be triggered by information whose veracity cannot be established by the blockchain. To overcome this problem, the language features a first-order logic and an authority algebra to allow formal reasoning and establish accountability of agents for blockchain-enabled transactions. We provide an accountability model that allows to formally prove the accountability of agents by a formal proof locally executable by each agent of the blockchain.

In this paper we analyze Tendermint proposed in [7], one of the most popular blockchains based on PBFT Consensus. The current paper dissects Tendermint under various system communication models and Byzantine adversaries. Our methodology consists in identifying the algorithmic principles of Tendermint necessary for a specific combination of communication model-adversary. This methodology allowed to identify bugs [3] in preliminary versions of the protocol ([19], [7]) and to prove its correctness under the most adversarial conditions: an eventually synchronous communication model and asymmetric Byzantine faults.

Tendermint-core blockchains (e.g. Cosmos) are considered today one of the most viable alternatives for the highly energy consuming proof-of-work blockchains such as Bitcoin and Ethereum. Their particularity is that they aim at offering strong consistency (no forks) in an open system combining two ingredients (i) a set of validators that generate blocks via a variant of Practical Byzantine Fault Tolerant (PBFT) consensus protocol and (ii) a selection strategy that dynamically selects nodes to be validators for the next block via a proof-of-stake mechanism. However,the exact assumptions on the system model under which Tendermint underlying algorithms are correct and the exact properties Tendermint verifies have never been formally analyzed. The contribution of this paper is two-fold. First, while formalizing Tendermint algorithms we precisely characterize the system model and the exact problem solved by Tendermint. We prove that in eventual synchronous systems a modified version of Tendermint solves (i) under additional assumptions, a variant of one-shot consensus for the validation of one single block and (ii) a variant of the repeated consensus problem for multiple blocks. These results hold even if the set of validators is hit by Byzantine failures, provided that for each one-shot consensus instance less than one third of the validators is Byzantine. Our second contribution relates to the fairness of the rewarding mechanism. It is common knowledge that in permisionless blockchain systems the main threat is the tragedy of commons that may yield the system to collapse if the rewarding mechanism is not adequate. Ad minimum the rewarding mechanism must be fair, i.e.distributing the rewards in proportion to the merit of participants. We prove, for the first time in blockchain systems, that in repeated-consensus based blockchains there exists an (eventual) fair rewarding mechanism if and only if the system is (eventual) synchronous. We also show that the original Tendermint rewarding is not fair, however, a modification of the original protocol makes it eventually fair.

The presented work continues the line of recent distributed computing communityefforts dedicated to the theoretical aspects of blockchains. This paper is the rst tospecify blockchains as a composition of abstract data types all together with a hierarchyof consistency criteria that formally characterizes the histories admissible for distributedprograms that use them. Our work is based on an original oracle-based constructionthat, along with new consistency deffnitions, captures the eventual convergence processin blockchain systems. The paper presents as well some results on implementability ofthe presented abstractions and a mapping of representative existing blockchains fromboth academia and industry in our framework.