Big data applications put significant latency and throughput demands on distributed storage systems. Meeting these demands requires storage systems to use a significant amount of infrastructure resources, such as network capacity and storage devices. Resource demands largely depend on the workloads and can vary significantly over time. Moreover, demand hotspots can move rapidly between different infrastructure locations. \n \nExisting storage systems are largely infrastructure-oblivious as they are designed to support a broad range of hardware and deployment scenarios. Most only use basic configuration information about the infrastructure to make important placement and routing decisions. In the case of cloud-based storage systems, cloud services have their own infrastructure-specific limitations, such as minimum request sizes and maximum number of concurrent requests. By ignoring infrastructure-specific details, these storage systems are unable to react to resource demand changes and may have additional inefficiencies from performing redundant network operations. As a result, provisioning enough resources for these systems to address all possible workloads and scenarios would be cost prohibitive. \n \nThis thesis studies the performance problems in commonly used distributed storage systems and introduces novel infrastructure-aware design methods to improve their performance. First, it addresses the problem of slow reads due to network congestion that is induced by disjoint replica and path selection. Selecting a read replica separately from the network path can perform poorly if all paths to the pre-selected endpoints are congested. Second, this thesis looks at scalability limitations of consensus protocols that are commonly used in geo-distributed key value stores and distributed ledgers. Due to their network-oblivious designs, existing protocols redundantly communicate over highly oversubscribed WAN links, which poorly utilize network resources and limits consistent replication at large scale. Finally, this thesis addresses the need for a cloud-specific realtime storage system for capital market use cases. Public cloud infrastructures provide feature-rich and cost-effective storage services. However, existing realtime timeseries databases are not built to take advantage of cloud storage services. Therefore, they do not effectively utilize cloud services to provide high performance while minimizing deployment cost. \n \nThis thesis presents three systems that address these problems by using infrastructure-aware design methods. Our performance evaluation of these systems shows that infrastructure-aware design is highly effective in improving the performance of large scale distributed storage systems.
Daniel M. Kane, Andreas Fackler, Adam Gągol, Damian Straszak
There has been recently a lot of progress in designing efficient partially synchronous BFT consensus protocols that are meant to serve as core consensus engines for Proof of Stake blockchain systems. While the state-of-the-art solutions attain virtually optimal performance under this theoretical model, there is still room for improvement, as several practical aspects of such systems are not captured by this model. Most notably, during regular execution, due to financial incentives in such systems, one expects an overwhelming fraction of nodes to honestly follow the protocol rules and only few of them to be faulty, most likely due to temporary network issues. Intuitively, the fact that almost all nodes behave honestly should result in stronger confidence in blocks finalized in such periods, however it is not the case under the classical model, where finality is binary. We propose Highway, a new consensus protocol that is safe and live in the classical partially synchronous BFT model, while at the same time offering practical improvements over existing solutions. Specifically, block finality in Highway is not binary but is expressed by fraction of nodes that would need to break the protocol rules in order for a block to be reverted. During periods of honest participation finality of blocks might reach well beyond 1/3 (as what would be the maximum for classical protocols), up to even 1 (complete certainty). Having finality defined this way, Highway offers flexibility with respect to the configuration of security thresholds among nodes running the protocol, allowing nodes with lower thresholds to reach finality faster than the ones requiring higher levels of confidence.
The conventional architecture of vehicular ad hoc networks (VANETs) with a centralized approach has difficulty overcoming the increasing complexity of intelligent transportation system (ITS) applications as well as challenges in providing large amounts of data storage, trust management, and information security. Therefore, vehicular edge computing networks (VECNets) have emerged to provide massive storage resources with powerful computing on network edges. However, a centralized server in VECNets is insufficient due to potential data leakage and security risks as it can still allow a single point of failure (SPoF). We propose consortium blockchain and smart contracts to ensure a trustworthy environment for secure data storage and sharing in the system to address these challenges. Practical byzantine fault tolerance (PBFT) is utilized because it is suitable for consortium blockchain to audit publicly, store data sharing, and records the whole consensus process. It can defend against system failures with or without symptoms to reach an agreement among consensus participants. Furthermore, we use an incentive mechanism to motivate the vehicle to contribute and honestly share their data. The simulation results satisfy the proposed model’s design goals by increasing vehicular networks’ performance in general.
Carlos Santiago, Shuyang Ren, Choonhwa Lee, Minsoo Ryu
In this paper, we present a novel Byzantine fault-tolerant consensus protocol for sharded blockchain networks that does not rely on expensive leader-driven communication. The proposed protocol selects a single block proposer at a time and uses threshold signatures as a voting mechanism to confirm the validity of the proposed block. By using a gossip-like communication scheme, each node can collect and recover the group signature within$\mathrm {O(log}N)$steps. With only one block proposer per consensus round, there is no possibility of conflicting blocks and resultant forks. Therefore, our consensus protocol requires only one round of one-way communication to achieve finality for each block. Our protocol guarantees safety and liveness while tolerating up to$f$faulty participants among$2f+1$nodes. Our performance study shows that the proposed protocol enables hundreds of nodes to participate in the agreement process, and can finalize large blocks in approximately 10 seconds.
The problem of transaction reordering in blockchains, also known as the blockchain anomaly [Christopher Natoli and Vincent Gramoli, 2016], can lead to fairness limitations [Kelkar et al., 2020] and front-running activities [Philip Daian et al., 2020] in cryptocurrency. To cope with this problem despite f < n/3 byzantine processes, Zhang et al. [Zhang et al., 2020] have introduced the ordering linearizability property ensuring that if two transactions or commands are perceived by all correct processes in the same order, then they are executed in this order. They proposed a generic distributed protocol that first orders commands and then runs a leader-based consensus protocol to agree on these orders, hence requiring at least 11 message delays. In this paper, we parallelize the ordering with the execution of the consensus to require only 6 message delays. For the ordering, we introduce the ordered reliable broadcast primitive suitable for broadcast-based cryptocurrencies (e.g., [Daniel Collins et al., 2020]). For the agreement, we build upon the DBFT leaderless consensus protocol [Tyler Crain et al., 2018] that was recently formally verified [Bertrand et al., 2021]. The combination is thus suitable to ensure ordering linearizability in consensus-based cryptocurrencies (e.g., [Tyler Crain et al., 2021]).
Vladimir Kukharenko, Kirill Ziborov, Rafael Faritovich Sadykov, Ruslan Rezin
The extent of formal verification methods applied in industrial projects has always been limited. The proliferation of distributed ledger systems (DLS), also known as blockchain , is rapidly changing the situation. Since the main area of DLSs’ application is the automation of financial transactions, the properties of predictability and reliability are critical for implementing such systems. The actual behavior of the DLS is largely determined by the chosen consensus protocol, which properties require strict specification and formal verification. Formal specification and verification of the consensus protocol is necessary but not sufficient. It is also required to ensure that the software implementation of the DLS nodes complies with this protocol. Finally, the verified software implementation of the protocol must run on a fairly reliable operating system. The financial focus of DLS application has also led to the emergence of the so-called smart contracts , which are an important part of the applied implementations of specific business processes based on DLSs. Therefore, the verifiability of smart contracts is also a critical requirement for industrial DLSs. In this paper, we describe an ongoing industrial project between a large Russian airline and three universities – Innopolis University (IU), Moscow Institute of Physics and Technology (MIPT) and Lomonosov Moscow State University (MSU). The main expected project result is a DLS for more flexible refueling of aircrafts, verified at least at the four technological levels described above. After brief project overview, we focus on our experience with the formal specification and verification of HotStuff, a leader-based fault-tolerant protocol that ensures reaching distributed consensus in the presence of Byzantine processes. The formal specification of the protocol is performed in the TLA+ language and then verified with a specialized TLC tool to verify models based on TLA+ specifications.
Florian Jacob, Carolin Beer, Norbert Henze, Hannes Hartenstein
Matrix is a new kind of decentralized, topic-based publish-subscribe middleware for communication and data storage that is getting particularly popular as a basis for secure instant messaging. By comparison with traditional decentralized communication systems, Matrix replaces pure message passing with a replicated data structure. This data structure, which we extract and call the Matrix Event Graph (MEG), depicts the causal history of messages. We show that this MEG represents an interesting and important replicated data type for decentralized applications that are based on causal histories of publish-subscribe events: First, we prove that the MEG is a Conflict-Free Replicated Data Type for causal histories and, thus, provides Strong Eventual Consistency (SEC). With SEC being among the best known achievable trade-offs in the scope of the well-known CAP theorem, the MEG provides a powerful consistency guarantee while being available during network partition. Second, we discuss the implications of byzantine attackers on the data type's properties. We note that the MEG, as it does not strive for consensus or strong consistency, can cope with n > f environments with n participants, of which f are byzantine. Furthermore, we analyze scalability: Using Markov chains, we study the number of forward extremities of the MEG over time and observe an almost optimal evolution. We conjecture that this property is inherent to the underlying spatially inhomogeneous random walk. With the properties shown, a MEG represents a promising element in the set of data structures for decentralized applications, but with distinct trade-offs compared to traditional blockchains and distributed ledger technologies.
In the high-stakes race to develop more scalable blockchains, some platforms (Binance, Cosmos, EOS, TRON, etc.) have adopted committee-based consensus (CBC) protocols, whereby the blockchain's record-keeping rights are entrusted to a committee of elected block producers. In theory, the smaller the committee, the faster the blockchain can reach consensus and the more it can scale. What's less clear, is whether such protocols ensure that honest committees can be consistently elected, given blockchain users typically have limited information on who to vote for. We show that the approval voting mechanism underlying most CBC protocols is complex and can lead to intractable optimal voting strategies. We empirically characterize some simpler intuitive voting strategies that users tend to resort to in practice and prove that these nonetheless converge to optimality exponentially quickly in the number of voters. Exponential convergence ensures that despite its complexity, CBC exhibits robustness and has some efficiency advantages over more popular staked-weighted lottery protocols currently underlying many prominent blockchains such as Ethereum.
The Deposit Smart Contract (DSC) is an instrumental component of the Ethereum 2.0 Phase 0 infrastructure. We have developed the first machine-checkable version of the incremental Merkle tree algorithm used in the DSC. We present our new and original correctness proof of the algorithm along with the Dafny machine-checkable version. The main results are: 1) a new proof of total correctness; 2) a software artefact with the proof in the form of the complete Dafny code base and 3) new provably correct optimisations of the algorithm.
Ignacio Amores-Sesar, Christian Cachin, Anna Parker
Despite the tremendous interest in cryptocurrencies like Bitcoin and Ethereum today, many aspects of the underlying consensus protocols are poorly understood. Therefore, the search for protocols that improve either throughput or security (or both) continues. Bitcoin always selects the longest chain (i.e., the one with most work). Forks may occur when two miners extend the same block simultaneously, and the frequency of forks depends on how fast blocks are propagated in the network. In the GHOST protocol, used by Ethereum, all blocks involved in the fork contribute to the security. However, the greedy chain selection rule of GHOST does not consider the full information available in the block tree, which has led to some concerns about its security. This paper introduces a new family of protocols, called Medium, which takes the structure of the whole block tree into account, by weighting blocks differently according to their depths. Bitcoin and GHOST result as special cases. This protocol leads to new insights about the security of Bitcoin and GHOST and paves the way for developing network- and application-specific protocols, in which the influence of forks on the chain-selection process can be controlled. It is shown that almost all protocols in this family achieve strictly greater throughput than Bitcoin (at the same security level) and resist attacks that can be mounted against GHOST.
Our contributions with this paper are twofold. First, we elucidate the methodological requirements for a risk framework of custodial operations and argue for the value of this type of risk model as complementary with cryptographic and blockchain security models. Second, we present a risk model in the form of a library of attack-trees for Revault -- an open-source custody protocol. The model can be used by organisations as a risk quantification framework for a thorough security analysis in their specific deployment context. Our work exemplifies an approach that can be used independent of which custody protocol is being considered, including complex protocols with multiple stakeholders and active defence infrastructure.
Petr Kuznetsov, Yvonne-Anne Pignolet, Pavel Ponomarev, Andrei Tonkikh
Most modern asset transfer systems use consensus to maintain a totally ordered chain of transactions. It was recently shown that consensus is not always necessary for implementing asset transfer. More efficient, asynchronous solutions can be built using reliable broadcast instead of consensus. This approach has been originally used in the closed (permissioned) setting. In this paper, we extend it to the open (permissionless) environment. We present {Pastro}, a permissionless and asynchronous asset-transfer implementation, in which quorum systems, traditionally used in reliable broadcast, are replaced with a weighted Proof-of-Stake mechanism. {Pastro} tolerates a dynamic adversary that is able to adaptively corrupt participants based on the assets owned by them.
Blockchain consensus, which enables nodes on a peer-to-peer network to agree on the same ledger history, is the core element of blockchain systems. In many blockchain systems, a node chosen as a block proposer, in accordance with the consensus protocol, generates a block, and each node chooses a chain to extend by a fork-choice rule. This study introduces saving attacks, a new kind of attack that prevents nodes from reaching a consensus. In saving attacks, the adversary “saves” its rights to propose blocks during a temporal consensus failure and utilizes them later to cause another consensus failure. As a result, the blockchain suffers from poor performance and high latency to block finalization. We study the effect of saving attacks on various fork-choice rules, including those that Ethereum 2.0 plans to employ.We simulate saving attacks on the longest-chain rule, Greedy Heaviest-Observed Sub-Tree (GHOST), latest-message-driven (LMD) GHOST, and fresh-message-driven (FMD) GHOST.We show that the saving attack has a very large negative impact on the consensus. For example, we observe that under a certain condition, an adversary with 30% of the total stake that has saved its blocks for 32 minutes succeeds in preventing a consensus against LMD GHOST for 83 minutes in the context of Ethereum 2.0. We also show that FMD GHOST decreases the attack duration to approximately 6.4 minutes under the same conditions. Our results are applicable to all slot-based proof-of-stake blockchains, not just Ethereum 2.0.
Abstract A smart contract is a program executed on a blockchain, based on which many cryptocurrencies are implemented, and is being used for automating transactions. Due to the large amount of money that smart contracts deal with, there is a surging demand for a method that can statically and formally verify them. This tool paper describes our type-based static verification tool Helmholtz for Michelson, which is a statically typed stack-based language for writing smart contracts that are executed on the blockchain platform Tezos. Helmholtz is designed on top of our extension of Michelson’s type system with refinement types. Helmholtz takes a Michelson program annotated with a user-defined specification written in the form of a refinement type as input; it then typechecks the program against the specification based on the refinement type system, discharging the generated verification conditions with the SMT solver Z3. We briefly introduce our refinement type system for the core calculus Mini-Michelson of Michelson, which incorporates the characteristic features such as compound datatypes (e.g., lists and pairs), higher-order functions, and invocation of another contract. Helmholtz successfully verifies several practical Michelson programs, including one that transfers money to an account and that checks a digital signature.
With the emergence of Bitcoin and recently proposed stablecoins from BigTechs, such as Diem (formerly Libra), central banks face growing competition from private actors offering their own digital alternative to physical cash. We do not address the normative question whether a central bank should issue a central bank digital currency (CBDC) or not. Instead, we contribute to the current research debate by showing how a central bank could do so, if desired. We propose a token-based system without distributed ledger technology and show how earlier-deployed, software-only electronic cash can be improved upon to preserve transaction privacy, meet regulatory requirements in a compelling way, and offer a level of quantum-resistant protection against systemic privacy risk. Neither monetary policy nor financial stability would be materially affected because a CBDC with this design would replicate physical cash rather than bank deposits.
Decentralized finance (DeFi) has become one of the most successful applications of blockchain and smart contracts. The DeFi ecosystem enables a wide range of crypto-financial activities, while the underlying smart contracts often contain bugs, with many vulnerabilities arising from the unforeseen consequences of composing DeFi protocols together. In this paper, we propose a formal process-algebraic technique that models DeFi protocols in a compositional manner to allow for efficient property verification. We also conduct a case study to demonstrate the proposed approach in analyzing the composition of two interacting DeFi protocols, namely, Curve and Compound. Finally, we discuss how the proposed modeling and verification approach can be used to analyze financial and security properties of interest.
Aiming at the problems of the existing DPoS(Delegated Proof of Stake) consensus algorithm, such as low enthusiasm of voting nodes and difficulties in dealing with malicious nodes, we improve the traditional DPoS consensus algorithm and propose a reputation-based delegated proof of stake consensus algorithm, called Reputation-DPoS. In our Reputation-DPoS, the reputation model is introduced. By evaluating the behavior of nodes, nodes are divided into different trusted states, and high-quality nodes in the network are selected as consensus nodes to reduce security risks and improve efficiency. Besides, incentive methods of reputation and token are used to improve the enthusiasm of nodes to participate in voting. Simulation results show that our Reputation-DPoS can reduce the probability of malicious nodes being selected and optimize the state of nodes in DPoS. Nodes with good behavior will get more votes and rewards, which will motivate nodes and improve the security of the system. Insert here your abstract text.
Hyoungsung Kim, Jaehyuk Jang, Sangjun Park, Heung-No Lee
The error-correction code proof-of-work (ECCPoW) algorithm is based on a low-density parity-check (LDPC) code. ECCPoW can impede the advent of mining application-specific integrated circuits (ASICs) with its time-varying puzzle generation capability. Previous research studies on the ECCPoW algorithm have presented its theory and implementation on Bitcoin. In this study, we have not only designed ECCPoW for Ethereum, called ETH-ECC, but have also implemented, simulated, and validated it. In the implementation, we have explained how the ECCPoW algorithm has been integrated into Ethereum 1.0 as a new consensus algorithm. Furthermore, we have devised and implemented a new method for controlling the difficulty level in ETH-ECC. In the simulation, we have tested the performance of ETH-ECC using a large number of node tests and demonstrated that the ECCPoW Ethereum works well with automatic difficulty-level change capability in real-world experimental settings. In addition, we discuss how stable the block generation time (BGT) of ETH-ECC is. Specifically, one key issue we intend to investigate is the finiteness of the mean of ETH-ECC BGT. Owing to a time-varying cryptographic puzzle generation system in the ECCPoW algorithm, the BGT in the algorithm may lead to a long-tailed distribution. Thus, simulation tests have been performed to determine whether the BGT distribution is heavy-tailed and has a finite mean. If the distribution is heavy-tailed, transaction confirmation cannot be guaranteed. In the validation, we have presented statistical analysis results based on the two-sample Anderson–Darling test and discussed how the BGT distribution satisfies the necessary to be considered an exponential distribution. Our implementation is available for download at https://github.com/cryptoecc/ETH-ECC.
Bartosz Kuśmierz, Sebastian Müller, Angelo Capossele
In this paper, we propose several solutions to the committee selection problem among participants of a DAG distributed ledger. Our methods are based on a ledger intrinsic reputation model that serves as a selection criterion. The main difficulty arises from the fact that the DAG ledger is a priori not totally ordered and that the participants need to reach a consensus on participants' reputation. Furthermore, we outline applications of the proposed protocols, including: (i) self-contained decentralized random number beacon; (ii) selection of oracles in smart contracts; (iii) applications in consensus protocols and sharding solutions. We conclude with a discussion on the security and liveness of the proposed protocols by modeling reputation with a Zipf law.
Distributed ledgers (DLs) provide many advantages over centralized solutions in Internet of Things projects, including but not limited to improved security, transparency, and fault tolerance. To leverage DLs at scale, their well-known limitation (i.e., performance) should be adequately analyzed and addressed. Directed acyclic graph-based DLs have been proposed to tackle the performance and scalability issues by design. The first among them, IOTA, has shown promising signs in addressing the preceding issues. IOTA is an open source DL designed for the Internet of Things. It uses a directed acyclic graph to store transactions on its ledger, to achieve a potentially higher scalability over blockchain-based DLs. However, due to the uncertainty and centralization of the deployed consensus, the current IOTA implementation exposes some performance issues, making it less performant than the initial design. In this article, we first extend an existing simulator to support realistic IOTA simulations and investigate the impact of different design parameters on IOTA’s performance. Then, we propose a layered model to help the users of IOTA determine the optimal waiting time to resend the previously submitted but not yet confirmed transaction. Our findings reveal the impact of the transaction arrival rate, tip selection algorithms, weighted tip selection algorithm randomness, and network delay on the throughput. Using the proposed layered model, we shed some light on the distribution of the confirmed transactions. The distribution is leveraged to calculate the optimal time for resending an unconfirmed transaction to the DL. The performance analysis results can be used by both system designers and users to support their decision making.
Naipeng Dong, Babu Pillai, Guangdong Bai, Mark Utting
Abstract Distributed ledger technology (DLT) emerged as a disruptive force towards decentralization and has expanded beyond its origins in cryptocurrencies like Bitcoin. At the heart of DLT is an infrastructure that replicates data across multiple network nodes, enabling new opportunities for data integrity, transparency, and trust in distributed business environments. In recent years, technological advances have improved the performance, energy efficiency, and functionality of DLT, expanding its application to various sectors such as finance, healthcare, trade and media, logistics, and the public sector. Despite these advances, adoption remained limited, with notable successes primarily in areas such as decentralized finance and non-fungible tokens. By placing DLT within the historical development of ledgers and distributed databases, this Fundamental provides a business-oriented foundation for structuring and assessing DLT-based solutions. It presents, a unified definition covering blockchain technologies, describes the key characteristics of DLT, and offers a structured analysis of its potential and challenges using a multi-dimensional interaction framework. Ultimately, it serves to carve out where and under which conditions DLT infrastructures add value for interorganizational relationships.