Tayyaba Noreen, Qiufen Xia, Muhammad Zeeshan Haider
In the past decade, blockchain has emerged as a promising solution for building secure distributed ledgers and has attracted significant attention. However, current blockchain systems suffer from limited throughput, poor scalability, and high latency. Due to limitations in consensus mechanisms, especially in managing node identities, blockchain is often considered unsuitable for applications such as the Internet of Things (IoT). This paper proposes the Advanced DAG-based Ranking (ADR) protocol to enhance blockchain scalability and throughput. ADR employs a directed acyclic graph (DAG) structure where nodes are positioned based on their rankings. Unlike traditional chains, ADR allows honest nodes to write blocks and verify transactions using a DAG-based topology. The protocol follows a three-step approach to secure the network against double-spending and enhance performance. First, it verifies nodes using their public and private keys before granting entry. Second, it builds an advanced DAG ledger enabling block production and transaction validation. Third, a ranking algorithm filters out malicious nodes, ranks the remaining nodes based on performance, and arranges them topologically. This process increases throughput and ensures robust scalability. We evaluated ADR on Amazon EC2 clusters with over 100 nodes, including scenarios with injected malicious nodes. Simulation results demonstrate that ADR significantly improves transaction throughput and network liveness compared to existing DAG-based blockchains such as IOTA and ByteBall, making it well-suited for IoT applications.
Blockchain and other decentralized databases, known as distributed ledgers, are designed to store information online where all trusted network members can update the data with transparency. The dynamics of ledger's development can be mathematically represented by a directed acyclic graph (DAG). In the first part of the thesis, we propose a random DAG model with sequential stochastic arrivals that mimic attachment rules from the IOTA cryptocurrency and study its asymptotic behavior as time goes to infinity. Our analysis establishes that the DAG is almost surely one-ended which is a crucial indicator of security of a decentralized database. In the second part of the paper, we study a modified DAG model and analyze its property as the arrival rate goes to infinity and the inter arrival time goes to zero. We establish that the number of leaves in the DAG and various random variables characterizing the vertices in the DAG can be approximated by its fluid limit, represented as delayed partial differential equations. Furthermore, we establish the stable state of this fluid limit and validate our findings through simulations.--Author's abstract
Chryssis Georgiou, Michel Raynal, Elad M. Schiller
Numerous distributed applications, such as cloud computing and distributed ledgers, necessitate the system to invoke asynchronous consensus objects an unbounded number of times, where the completion of one consensus instance is followed by the invocation of another. With only a constant number of objects available, object reuse becomes vital. We investigate the challenge of object recycling in the presence of Byzantine processes, which can deviate from the algorithm code in any manner. Our solution must also be self-stabilizing, as it is a powerful notion of fault tolerance. Self-stabilizing systems can recover automatically after the occurrence of arbitrary transient faults, in addition to tolerating communication and (Byzantine or crash) process failures, provided the algorithm code remains intact. We provide a recycling mechanism for asynchronous objects that enables their reuse once their task has ended, and all non-faulty processes have retrieved the decided values. This mechanism relies on synchrony assumptions and builds on a new self-stabilizing Byzantine-tolerant synchronous multivalued consensus algorithm, along with a novel composition of existing techniques.
A Single Secret Leader Election (SSLE) enables a group of parties to randomly choose exactly one leader from the group with the restriction that the identity of the leader will be known to the chosen leader and nobody else. At a later time, the elected leader should be able to publicly reveal her identity and prove that she is the elected leader. The election process itself should work properly even if many registered users are passive and do not send any messages. SSLE is used to strengthen the security of proof-of-stake consensus protocols by ensuring that the identity of the block proposer remains unknown until the proposer publishes a block. Boneh, Eskandarian, Hanzlik, and Greco (AFT'20) defined the concept of an SSLE and gave several constructions. Their most efficient construction is based on the difficulty of the Decision Diffie-Hellman problem in a cyclic group. In this work we construct the first efficient SSLE protocols based on the standard Learning With Errors (LWE) problem on integer lattices, as well as the Ring-LWE problem. Both are believed to be post-quantum secure. Our constructions generalize the paradigm of Boneh et al. by introducing the concept of a re-randomizable commitment (RRC). We then construct several post-quantum RRC schemes from lattice assumptions and prove the security of the derived SSLE protocols. Constructing a lattice-based RRC scheme is non-trivial, and may be of independent interest.
We examine which decentralized finance architectures enable meaningful regulation by combining financial and computational theory. We show via deduction that a decentralized and permissionless Turing-complete system cannot provably comply with regulations concerning anti-money laundering, know-your-client obligations, some securities restrictions and forms of exchange control. Any system that claims to follow regulations must choose either a form of permission or a less-than-Turing-complete update facility. Compliant decentralized systems can be constructed only by compromising on the richness of permissible changes. Regulatory authorities must accept new tradeoffs that limit their enforcement powers if they want to approve permissionless platforms formally. Our analysis demonstrates that the fundamental constraints of computation theory have direct implications for financial regulation. By mapping regulatory requirements onto computational models, we characterize which types of automated compliance are achievable and which are provably impossible. This framework allows us to move beyond traditional debates about regulatory effectiveness to establish concrete boundaries for automated enforcement.
We propose a novel model for teaching and learning called Decentralized Autonomous Education (DAE for short). DAE exploits the dual principles of freedom and responsibility, meritocracy and inclusivity, privacy and transparency in the educational process. It also fits well the philosophy of blockchain technology, and more generally of Web3 – the third iteration of the World Wide Web – specifically the tenets of decentralization, disintermediation, incentive and sovereignty of the individual. In this paper, we fully illustrate the DAE model, highlighting the theoretical and practical links between DAE and Web3, dissecting the pros and cons of the proposed learning method and reviewing related pedagogical approaches. Finally, we describe the front-end and back-end design of the DAE app, a decentralized application that implements the DAE learning model.
Abstract Efficiency is a fundamental property of any type of program, but it is even more so in the context of the programs executing on the blockchain (known as smart contracts ). This is because optimizing smart contracts has direct consequences on reducing the costs of deploying and executing the contracts, as there are fees to pay related to their bytes-size and to their resource consumption (called gas ). Optimizing memory usage is considered a challenging problem that, among other things, requires a precise inference of the memory locations being accessed. This is also the case for the Ethereum Virtual Machine (EVM) bytecode generated by the most-widely used compiler, , whose rather unconventional and low-level memory usage challenges automated reasoning. This paper presents a static analysis, developed at the level of the EVM bytecode generated by , that infers write memory accesses that are needless and thus can be safely removed. The application of our implementation on more than 19,000 real smart contracts has detected about 6,200 needless write accesses in less than 4 hours. Interestingly, many of these writes were involved in memory usage patterns generated by that can be greatly optimized by removing entire blocks of bytecodes. To the best of our knowledge, existing optimization tools cannot infer such needless write accesses, and hence cannot detect these inefficiencies that affect both the deployment and the execution costs of Ethereum smart contracts.
Jan 1, 2023·Proceedings of the ... Annual Hawaii International Conference on System Sciences/Proceedings of the Annual Hawaii International Conference on System Sciences
Nickolas Carter, Duane Davis, Cynthia E. Irvine, Peter Pommer
Autonomous multi-vehicle systems are becoming increasingly relevant in military operations and have demonstrated potential applicability in civilian environments as well. A problem emerges, however, when logging data within these systems. In particular, potential loss of individual vehicles and inherently lossy and noisy communications environments can result in the loss of important mission data. This paper describes a novel distributed ledger protocol that can be used to ensure that the data in such a system survives and documents verification of the behavioral correctness of this protocol using informal verification methods and tools provided by the Monterey Phoenix project.
Since the Merge update upon which Ethereum transitioned to Proof of Stake, it has been touted that it resulted in lower power consumption and increased security. However, even if that is the case, can this state be sustained? In this paper, we focus on the potential impact of competition with other smart contract platforms on the price of Ethereum's native currency, Ether (ETH), thereby raising questions about the safety and sustainability purportedly brought about by the design of Proof of Stake.
Franck Cassez, Joanne Fuller, Milad K. Ghale, David J. Pearce · 5 authors
The Ethereum protocol implements a replicated state machine. The network participants keep track of the system state by: 1) agreeing on the sequence of transactions to be processed and 2) computing the state transitions that correspond to the sequence of transactions. Ethereum transactions are programs, called smart contracts, and computing a state transition requires executing some code. The Ethereum Virtual Machine (EVM) provides this capability and can execute programs written in EVM bytecode. We present a formal and executable semantics of the EVM written in the verification-friendly language Dafny: it provides (i) a readable, formal and verified specification of the semantics of the EVM; (ii) a framework to formally reason about bytecode.
Fernando Bereta dos Reis, Mark Borkum, Monish Mukherjee, D. Jonathan Sebastian-Cardenas
This paper explores the potential of distributed ledger technology (DLT) to improve fault-tolerant grid operations by leveraging its core features as an immutable, decentralized ledger, a distributed, consensus-based agreement process, and a distributed state-replication engine. Distribution power systems deliver electricity to millions of customers; however, they are susceptible to various threats that can result in customer interruptions. These include faults caused by adverse weather conditions, natural disasters, vegetation growth, equipment failure, and malicious attacks. To minimize the effects of these faults, fault-handling approaches rely on network knowledge to isolate affected areas and reconnect unaffected areas, reducing the number of affected customers while maintaining safety. Here, we present a trusted data-sharing architecture that enables independent, distributed actors to reconstruct the pre-fault system state by enabling distributed resources to make appropriate decisions with limited network/system information. Although the process requires some data sharing between switch-delimited areas, the approach limits the amount of private information shared, preserving customers’ privacy and business-sensitive information. We include three use cases that form a foundation for third parties to develop functional solutions that can eventually be deployed in the field. The gross error detection method used within switch-delimited areas can identify sensor errors and accurately detect circuit breaker states. The evaluation of possible reconnection while preserving data ownership resulted in a voltage magnitude difference smaller than 0.01% from the OpenDSS power flow solution that has full system knowledge, which is below the expected power flow tolerance. The approach offers a promising opportunity for improving fault-tolerant distribution grid operations.
Ethereum is a permissionless blockchain ecosystem that supports execution of smart contracts, the key enablers of decentralized finance (DeFi) and non-fungible tokens (NFT). However, the expressiveness of Ethereum smart contracts is a double-edged sword: while it enables blockchain programmability, it also introduces security vulnerabilities, i.e., the exploitable discrepancies between expected and actual behaviors of the contract code. To address these discrepancies and increase the vulnerability coverage, we propose a new smart contract security testing approach called transaction encapsulation. The core idea lies in the local execution of transactions on a fully-synchronized yet isolated Ethereum node, which creates a preview of outcomes of transaction sequences on the current state of blockchain. This approach poses a critical technical challenge — the well-known time-of-check/time-of-use (TOCTOU) problem, i.e., the assurance that the final transactions will exhibit the same execution paths as the encapsulated test transactions. In this work, we determine the exact conditions for guaranteed execution path replicability of the tested transactions. To demonstrate the transaction encapsulation, we implement a transaction testing tool, TxT, which reveals the actual outcomes (either benign or malicious) of Ethereum transactions. To ensure the correctness of testing, TxT deterministically verifies whether a given sequence of transactions ensues an identical execution path on the current state of blockchain. We analyze over 1.3 billion Ethereum transactions and determine that 96.5% of them can be verified by TxT. We further show that TxT successfully reveals the suspicious behaviors associated with 31 out of 37 vulnerabilities (83.8% coverage) in the smart contract weakness classification (SWC) registry. In comparison, the vulnerability coverage of all the existing defense approaches combined only reaches 40.5%.
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.
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.
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.