The scalability problem has been one of the most significant barriers limiting the adoption of blockchains. Blockchain sharding is a promising approach to this problem. However, the sharding mechanism introduces a significant number of cross-shard transactions, which are expensive to process. This paper focuses on the transaction allocation problem to reduce the number of cross-shard transactions for better scalability. In particular, we systematically formulate the transaction allocation problem and convert it to the community detection problem on a graph. A deterministic and fast allocation scheme TxAllo is proposed to dynamically infer the allocation of accounts and their associated transactions. It directly optimizes the system throughput, considering both the number of cross-shard transactions and the workload balance among shards. We evaluate the performance of TxAllo on an Ethereum dataset containing over 91 million transactions. Our evaluation results show that for a blockchain with 60 shards, TxAllo reduces the cross-shard transaction ratio from 98% (by using traditional hash-based allocation) to about 12%. In the meantime, the workload balance is well maintained. Compared with other methods, the execution time of TxAllo is almost negligible. For example, when updating the allocation every hour, the execution of TxAllo only takes 0.5 seconds on average, whereas other concurrent works, such as BrokerChain (INFOCOM'22) leveraging the classic METIS method, require 422 seconds.
At present, academics have researched the directions that may become performance bottlenecks in blockchain systems, such as consensus protocols, encryption algorithms and contract execution. For example, in recent years, many improvements to consensus protocols have greatly improved the throughput of blockchain systems. However, the bottleneck of blockchain smart contract execution has not been well solved. Currently, the miner-validator architecture based on serial contract execution limits the throughput of smart contract execution to a great extent. This paper proposes a new smart contract parallel execution architecture, which migrates the concurrency control methods used in mature databases to the blockchain. The test of Ethereum data and a benchmark specifically for blockchain show that its throughput is greatly improved compared with the traditional serial execution mode.
Sharding has been considered as a prominent approach to enhance the limited performance of blockchain. However, most sharding systems leverage a non-cooperative design, which lowers the fault tolerance resilience due to the decreased mining power as the consensus execution is limited to each separated shard. To this end, we present Benzene, a novel sharding system that enhances the performance by cooperation-based sharding while defending the per-shard security. First, we establish a double-chain architecture for function decoupling. This architecture separates transaction-recording functions from consensus-execution functions, thereby enabling the cross-shard cooperation during consensus execution while preserving the concurrency nature of sharding. Second, we design a cross-shard block verification mechanism leveraging Trusted Execution Environment (TEE), via which miners can verify blocks from other shards during the cooperation process with the minimized overheads. Finally, we design a voting-based consensus protocol for cross-shard cooperation. Transactions in each shard are confirmed by all shards that simultaneously cast votes, consequently achieving an enhanced fault tolerance and lowering the confirmation latency. We implement Benzene and conduct both prototype experiments and large-scale simulations to evaluate the performance of Benzene. Results show that Benzene achieves superior performance than existing sharding/non-sharding blockchain protocols. In particular, Benzene achieves a linearly-improved throughput with the increased number of shards (e.g., 32,370 transactions per second with 50 shards) and maintains a lower confirmation latency than Bitcoin (with more than 50 shards). Meanwhile, Benzene maintains a fixed fault tolerance at 1/3 even with the increased number of shards.
Peter Eklund, Jonas Sveistrup Søgaard, Lasse Herskind, jason Spasovski
This paper examines the feasibility of blockchain solutions for national and transnational business-to-business and business-to-government (B2B/B2G) compliance frameworks, namely a trust-less, de-centralised, self-regulating distributed ledger. In particular, the paper examines whether blockchain platforms scale to support national and transnational e-business trading.
An optimistic rollup (ORU) scales a blockchain's throughput by delegating computation to an untrusted remote chain (L2), refereeing any state claim disagreements between mutually distrusting L2 operators via an interactive dispute resolution protocol. State-of-the-art ORUs employ a monolithic dispute resolution protocol that tightly couples an L1 referee with a specific L2 client binary--oblivious to the system's higher-level semantics. We argue that this approach (1) magnifies monoculture failure risk, by precluding trust-minimized and permissionless participation using operator-chosen client software; (2) leads to an unnecessarily large and difficult-to-audit TCB; and, (3) suffers from a frequently-triggered, yet opaque upgrade process--both further increasing auditing overhead, and broadening the governance attack surface. To address these concerns, we outline a methodology for designing a secure and resilient ORU with a minimal TCB, by facilitating opportunistic 1-of-N-version programming. Due to its unique challenges and opportunities, we ground this work concretely in the context of the Ethereum ecosystem--where ORUs have gained significant traction. Specifically, we design a semantically-aware proof system, natively targeting the EVM and its instruction set. We present an implementation in a new ORU, Specular, that opportunistically leverages Ethereum's existing client diversity with minimal source modification, demonstrating our approach's feasibility.
Because of the characteristics of decentralization, immutability, and transparency, blockchain has gradually become a new and revolutionary technology, which has far-reaching significance for the development of modern technology. However, the traditional Bitcoin blockchain that supports synchronous consensus suffers from the fatal flaw of low throughput. To improve throughput, a number of DAG distributed ledgers have been proposed that support asynchronous consensus, all of which allow multiple nodes to process concurrent transactions asynchronously. However, most DAG distributed ledgers do not implement consistent sorting of transactions, making it difficult to deploy smart contracts. To overcome this problem, in this paper, an epoch-based transaction consistency sorting protocol for DAG distributed ledger is proposed, which not only provides the possibility for the deployment of smart contracts but also can be used to resolve conflicting transactions in the ledger. Transaction consistency sorting protocol provides a more reasonably ordered list of all transactions by taking scalars, such as the set of their own past and future, parent block, and timestamp. In addition, through theoretical analysis, the stability and rationality of the transaction consistency sorting protocol are proved, and there is no Condorcet cycle. Finally, the simulation results demonstrate the protocol is efficient and achieve a throughput of at least 2000 transactions per second.
Efficient data storage and query processing systems play a vital role in many different research areas. Blockchain technology and distributed ledgers attract massive attention and trigger multiple projects in various industries. Nevertheless, blockchain still lacks the features of a Database Management System (DBMS or simply databases), such as high throughput, low latency, and high capacity. For that purpose, there have been many proposed approaches for handling data storage and query processing solutions in the blockchain. This paper presents a complete overview of many different DBMS types and how these systems can be used to implement, enhance, and further improve blockchain technology. More concretely, we give an overview of 10 transactional, an extensive overview of 14 analytical, 9 hybrids, i.e., translytical, and 13 blockchain DBMSs. We explain how database technology has influenced the development of blockchain technology by unlocking different features, such as Atomicity, Consistency, Isolation, and Durability (ACID), transaction consistency, rich queries, real-time analysis, and low latency. Using a relaxation approach analogous to the one used to prove the Consistency, Availability, Partition tolerance (CAP)-theorem, we postulate a “Decentralization, Consistency, and Scalability (DCS)-satisfiability conjecture” and give concrete strategies for achieving the relaxed DCS conditions. We also provide an overview of the different DBMSs, emphasizing their architecture, storage manager, query processing, and implementation.
As smart cities become more decentralized, the need for reliable and secure cyber-physical systems (CPS) that guarantee safe interactions and secure data storage without loss of privacy is continuously increasing. Blockchain is a rapidly emerging technology in this domain. It demonstrated effectiveness thanks to the cryptographic mechanisms it utilizes and to its immutability. Private blockchains are the most suited to applications that require privacy and confidentiality when data is very sensitive. In this case, the most commonly used consensus protocol is Practical Byzantine Fault Tolerance (PBFT). However, PBFT requires the participation of all nodes in the consensus process, which increases bandwidth consumption and consensus delay significantly. In this paper, we propose an adaptive PBFT protocol called APBFT that optimizes the number of nodes participating in the consensus based on their response time and credibility. Therefore, we reduce the amount of communication and the response delays. We maintain the asynchrony of the algorithm so that it remains resilient to DoS attacks. The simulation results show that our algorithm outperforms the original PBFT in terms of delays and message traffic.
In this work we combine Delegated Proof of Stake (DPoS) consensus technique with multiple entry Practical Byzantine Fault Tolerant voting in a permissioned blockchain network. Voting is organized in rounds that contain a number of PBFT consensus cycles. Nodes with low stake are forced to leave at the end of current round and may return to a new round when they repurchase the stake tokens, while nodes with sufficient stake may leave the network temporarily at the completion of current round due to mobility. We consider multiple DPoS classes based on node's initial stake and probability of truthful voting, and model their behavior using embedded Markov Chain which corresponds to a Semi Markov Process (SMP). We show that probability of reaching consensus is higher when rounds are shorter and/or there are more nodes in the network. In addition, we find that nodes from higher priority classes are mostly excluded from voting due to their mobility, while those from lower priority classes are excluded more often on account of low stake.
Valerio Mandarino, Giuseppe Pappalardo, Emiliano Tramontana
Ethereum network has introduced an important innovation to blockchain technology that has deeply changed the world of blockchains and cryptocurrencies: Turing-complete smart contracts. Thanks to smart contracts it is possible to mint fungible and non-fungible tokens, manage decentralized organizations and offer services such as digital identity, advertisement, time commitments, decentralized exchanges, etc. However, smart contract development is not free from challenges. This paper analyses a set of design patterns that have been documented and groups them according to related smart contracts' weaknesses. Moreover, two novel solutions are presented in the form of design patterns. The first is a micro architecture that deals with a treasure reserve and aims at reducing gas consumption when having to update the code of a smart contract. The second presents a solution for packing bits each representing a Boolean value.
Dec 1, 2022·2022 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom)
Minghao Fu, Haoran Zhu, Jelena Mišić, Vojislav B. Mišić · 6 authors
Eclipse-based Stake-Bleeding (ESB) attack is a kind of long-range attacks in a Proof-of-Stake (PoS) blockchain system, which can shorten the attack completion time. Researchers have quantitatively analyzed ESB attack but ignoring checkpointing defense technique, which solidifies the history of blockchain and then prevents an adversary to change the blockchain. This paper aims to investigate the capability of the checkpoint-based defense scheme in resisting ESB attack. We develop a Monte Carlo simulator to capture the dynamics of a PoS blockchain system, which is subject to ESB attack and deploys checkpoint-base defense scheme. We also develop the methods for calculating the probability of successful attack and attack profit. This simulator can be applied to evaluate the influence of ESB attack and the checkpointing capability from the perspective of honest verifiers, adversaries and victims. Our experiment results can help enhance PoS blockchain security.
Nov 29, 2022·Companion Proceedings of the 2022 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity
It is possible to download a piece of software over the internet and then verify its correctness locally using an appropriate trusted proof system. However, on a blockchain like Ethereum, smart contracts cannot be altered once deployed. This guarantee of immutability makes it possible for end users to interact collectively with a 'networked' piece of software, with the same opportunity to verify its correctness. Formal verification of smart contracts on a blockchain therefore offers an unprecedented opportunity for end users to collectively interact with a deployed instance of software that they can verify while not relying on a central authority. All that is required to be trusted beyond the blockchain itself is an appropriate proof system, a component which always needs to be in the trusted computing base, and whose rules and definitions can be public knowledge. DeepSEA (Deep Simulation of Executable Abstractions) could serve as such a proof system.
To create trustworthy programs, the 'gold standard' is specifications at a high-enough level to clearly correspond to the informal specifications, and also a refinement proof linking these high-level specifications down to, in our case, executable bytecode. The DeepSEA system demonstrates how this can be done, in the context of smart contracts on the Ethereum blockchain. A key component of this is the model of the blockchain on which the smart contracts reside. When doing proofs in DeepSEA, it is critical to have such a model, which allows for the writing of specifications at a high-level clearly corresponding to informal specifications. A candidate model for doing so and its usefulness for carrying out proofs is discussed in this paper.
Private blockchain as a replicated transactional system shares many commonalities with distributed database. However, the intimacy between private blockchain and deterministic database has never been studied. In essence, private blockchain and deterministic database both ensure replica consistency by determinism. In this paper, we present a comprehensive analysis to uncover the connections between private blockchain and deterministic database. While private blockchains have started to pursue deterministic transaction executions recently, deterministic databases have already studied deterministic concurrency control protocols for almost a decade. This motivates us to propose Harmony, a novel deterministic concurrency control protocol designed for blockchain use. We use Harmony to build a new relational blockchain, namely HarmonyBC, which features low abort rates, hotspot resiliency, and inter-block parallelism, all of which are especially important to disk-oriented blockchain. Empirical results on Smallbank, YCSB, and TPC-C show that HarmonyBC offers 2.0x to 3.5x throughput better than the state-of-the-art private blockchains.
Lydia Negka, Angeliki Katsika, Γεώργιος Σπαθούλας, Vassilis P. Plagianakos
One of the major concerns regarding currently proposed public blockchain systems relates to the feasible transaction processing rate. It is common for such systems to limit this rate to maintain the required levels of security and decentralisation. State channels are an approach to overcome this limitation, as they aim to decrease the required on-chain transactions for a given application and thus indirectly increase the capacity (in terms of applications) of public blockchain systems. In the present paper, we propose a state channel design that, through the use of RSA accumulators, operates on a compact state structure. This scheme is optimal for applications whose state includes large sets of elements. The novel state channel design is presented by analysing all state channel operations and how they have to be revised. The security of the design is discussed, while a practical use case scenario regarding the use of the design for an on-chain asset (e.g., non-fungible tokens) exchange application is also analysed.
Sarah Azouvi, Christian Cachin, Le, Duc V., Marko Vukolić · 5 authors
Blockchain protocols implement total-order broadcast in a permissionless setting, where processes can freely join and leave. In such a setting, to safeguard against Sybil attacks, correct processes rely on cryptographic proofs tied to a particular type of resource to make them eligible to order transactions. For example, in the case of Proof-of-Work (PoW), this resource is computation, and the proof is a solution to a computationally hard puzzle. Conversely, in Proof-of-Stake (PoS), the resource corresponds to the number of coins that every process in the system owns, and a secure lottery selects a process for participation proportionally to its coin holdings. Although many resource-based blockchain protocols are formally proven secure in the literature, the existing security proofs fail to demonstrate why particular types of resources cause the blockchain protocols to be vulnerable to distinct classes of attacks. For instance, PoS systems are more vulnerable to long-range attacks, where an adversary corrupts past processes to re-write the history, than Proof-of-Work and Proof-of-Storage systems. Proof-of-Storage-based and Proof-of-Stake-based protocols are both more susceptible to private double-spending attacks than Proof-of-Work-based protocols; in this case, an adversary mines its chain in secret without sharing its blocks with the rest of the processes until the end of the attack. In this paper, we formally characterize the properties of resources through an abstraction called resource allocator and give a framework for understanding longest-chain consensus protocols based on different underlying resources. In addition, we use this resource allocator to demonstrate security trade-offs between various resources focusing on well-known attacks (e.g., the long-range attack and nothing-at-stake attacks).
Data timeliness, privacy, and security are key enablers for data-sharing systems to support time-sensitive and mission-critical systems and applications. While blockchain-enabled data sharing frameworks can offer reliable security and privacy when properly implemented, the timeliness of data and the related latency are important issues that can limit the adoption of blockchain in large-scale mission-critical applications. This paper thus carried out a performance analysis of the blockchain-enabled data-sharing framework from latency and data age perspectives to investigate the suitability of blockchain technology in data sharing systems. To achieve this, the uniqueness of such systems such as transactions validation latency, transaction generation rate, waiting time, blockchain-appending rate, and overall communication latency were jointly studied. The communication latency was characterized following the spatiotemporal modeling approach. We further adopted the practical Byzantine fault tolerance (PBFT) consensus protocol due to its well discussed suitability in large-scale data sharing applications and captured the validation stages of such a PBFT scheme using the Erlang distribution of order$k$. Simulations results show that various influential system parameters must be carefully considered when adopting blockchain technology in time-sensitive data sharing applications. This will guide the adoption of blockchain technology in various data sharing applications and systems.
Blockchain consensus algorithms are generally used to ensure data consistency in the blockchain. The current blockchain consensus algorithm has some problems, such as high computing resource consumption, slow block generation speed and difficulty in dealing with malicious node and failure node, which lead to the uncertainty of authenticity of new blocks and trading transaction delay. In view of these problems, we firstly turn the question into solving the problems of electing the one node to keep ledger while ensuring the correctness of ledger information and then synchronize the distributed ledger among most nodes. we propose a consensus algorithm named ENET (Evil Node Elimination Tree) using single chain blockchain structure, with integrating Boyer-Moore majority vote algorithm ensuring the correctness of all new generated blocks. A bottom-up promotion approach to election was adopted to gradually eliminate evil nodes, meanwhile the structure of elimination tree of evil nodes is being constructed. In addition, the distributed synchronization mechanism of top-down update is adopted to recursively update the distributed ledger of all nodes. Theoretical derivation and computer multithreading simulation results show that the communication complexity of this algorithm is at a linear level, and the fault tolerance ratio is 1/4 at the lowest and 3/4 at the highest. The transaction duration is significantly shortened while the double payment problem is eliminated in the system.
Letterio Galletta, Cosimo Laneve, Ivan Mercanti, Adele Veschetti
Hybrid Casper is the new Ethereum blockchain protocol that uses both Proof of Work and Proof of Stake to reach a consensus between nodes. Here, we analyze the protocol using PRISM+ , an extension of the probabilistic model checker PRISM with primitives for expressing blockchain data types. First, we extend PRISM+ to include data types and operations for modeling and analyzing Proof of Stake based consensus protocols. Then, we model Hybrid Casper in PRISM+ as a parallel composition of stochastic processes, thus precisely describing the behavior of the protocol and highlighting its corner cases. PRISM+ is therefore used to rapidly and automatically analyze the resilience of Hybrid Casper when tuning, up or down, several basic parameters of the protocol, such as the rates of creating blocks, and the strategies for determining penalties. Finally, we study the robustness of Hybrid Casper to two well-known attacks: the Eclipse attack and the majority attack.
Despite the success in various scenarios, blockchain systems, especially EVM-compatible ones that serially execute transactions, still face the significant challenge of limited throughput. Concurrent transaction execution is a promising technique to accelerate transaction processing and increase the overall throughput. Existing concurrency control algorithms, however, fail to obtain enough speedups in real-world blockchains due to the high-contention workloads. In this paper, we propose a novel operation-level concurrency control algorithm designed for blockchains. The core idea behind our algorithm is that only operations depending on conflicts should be executed serially, while all other conflict-free operations can be executed concurrently. Therefore, in contrast to the traditional approaches, which block or abort the entire transaction when encountering conflicts, our algorithm introduces a redo phase to resolve conflicts at the operation level by re-executing conflicting operations only. We also develop a set of data dependency tracking mechanisms to achieve precise identification and speedy re-execution for conflicting operations. We implement an open-source prototype based on Go Ethereum and evaluate it using real-world Ethereum blocks. The evaluation results show that our algorithm achieves an average speedup of 4.28$\times$. If combined with state prefetching techniques, our approach can further accelerate the transaction execution by 7.11$\times$.
Scientific and commercial endeavors could benefit from cross-organizational, decentralized collaboration, which becomes the key to innovation. This work addresses one of its challenges, namely efficient access control to assets for distributed data processing among autonomous data centers. We propose a group membership management framework dedicated for realizing access control in decentralized environments. Its novelty lies in a synergy of two concepts: a decentralized knowledge base and an incremental indexing scheme, both assuming a P2P architecture, where each peer retains autonomy and has full control over the choice of peers it cooperates with. The extent of exchanged information is reduced to the minimum required for user collaboration and assumes limited trust between peers. The indexing scheme is optimized for read-intensive scenarios by offering fast queries -- look-ups in precomputed indices. The index precomputation increases the complexity of update operations, but their performance is arguably sufficient for large organizations, as shown by conducted tests. We believe that our framework is a major contribution towards decentralized, cross-organizational collaboration.
Nakamoto proof-of-work ledger consensus currently underlies the majority of deployed cryptocurrencies and smart-contract blockchains. While a long and fruitful line of work has succeeded to identify its exact security region---that is, the set of parametrizations under which it possesses asymptotic security---the existing theory does not provide concrete settlement time guarantees that are tight enough to inform practice.
Tim Ruffing, Viktoria Ronge, Elliott Jin, Jonas Schneider-Bensch · 5 authors
Bitcoin and other cryptocurrencies have recently introduced support for Schnorr signatures whose cleaner algebraic structure, as compared to ECDSA, allows for simpler and more practical constructions of highly demanded ''t-of-n'' threshold signatures. However, existing Schnorr threshold signature schemes still fall short of the needs of real-world applications due to their assumption that the network is synchronous and due to their lack of robustness, i.e., the guarantee that t honest signers are able to obtain a valid signature even in the presence of other malicious signers who try to disrupt the protocol. This hinders the adoption of threshold signatures in the cryptocurrency ecosystem, e.g., in second-layer protocols built on top of cryptocurrencies.
Recently, Byzantine fault-tolerant (BFT) state machine replication (SMR) experiences renewed research interest with the rise of novel BFT SMR-based distributed ledger technologies (DLTs). In DLTs, BFT SMR is used as a core primitive for maintaining a consistent append-only log by committing blocks of transactions in all replicas. In comparison with Proof-of-Work, BFT can typically improve performance and energy efficiency and comes with proven system properties.