We propose definitions and implementations of "S-money" - virtual tokens designed for high value fast transactions on networks with relativistic or other trusted signalling constraints, defined by inputs that in general are made at many network points, some or all of which may be space-like separated. We argue that one significant way of characterising types of money in space-time is via the "summoning" tasks they can solve: that is, how flexibly the money can be propagated to a desired space-time point in response to relevant information received at various space-time points. We show that S-money is more flexible than standard quantum or classical money in the sense that it can solve deterministic summoning tasks that they cannot. It requires the issuer and user to have networks of agents with classical data storage and communication, but no long term quantum state storage, and is feasible with current technology. User privacy can be incorporated by secure bit commitment and zero knowledge proof protocols. The level of privacy feasible in given scenarios depends on efficiency and composable security questions that remain to be systematically addressed.
Message digest algorithms are one of the underlying building blocks of\nblockchain platforms such as Ethereum. This paper analyses situations in which\nthe message digest collision resistance property can be exploited by attackers.\nTwo mitigations for possible attacks are described: longer message digest sizes\nmake attacks more difficult; and, including timeliness properties limits the\namount of time an attacker has to determine a hash collision.\n
We analyze the economic incentives generated by the proof-of-stake mechanism discussed in the Ethereum Casper upgrade proposal. Compared with proof-of-work, proof-of-stake has a different cost structure for attackers. In Budish (2018), three equations characterize the limits of Bitcoin, which has a proof-of-work mechanism. We investigate their counterparts and evaluate the risk of double-spending attack and sabotage attack. We argue that PoS is safer than PoW agaisnt double-spending attack because of the tractability of attackers, which implies a large "stock" cost for the attacker. Compared to a PoW system whose mining equipments are repurposable, PoS is also safer against a sabotage attack.
Distributed ledger technologies, such as blockchain systems, have in recent years emerged as promising platforms for machine-to-machine commerce and other forms of multi-stakeholder applications. However, despite the potential demonstrated by projects such as Bitcoin, Ethereum, and Hyperledger Fabric, the disk space typically required to host a copy of a ledger may be prohibitively large for many categories of devices. In this paper, we introduce an approach for reducing ledger size in blockchain systems, based on arbitrary pruning predicate functions, allowing each network participant to independently select and remove any already applied transactions. We also show that if only pruning certain ledger transactions, the ability to derive an unmodified state data structure from the remaining transactions is maintained. The approach is validated through a supply chain use case utilizing a modified version of Hyperledger Fabric, in which ledger size is reduced by about 84.49% via selective transaction pruning.
The rise in popularity of permissioned blockchain platforms in recent time is significant. Hyperledger Fabric is one such permissioned blockchain platform and one of the Hyperledger projects hosted by the Linux Foundation. The Fabric comprises various components such as smart-contracts, endorsers, committers, validators, and orderers. As the performance of blockchain platform is a major concern for enterprise applications, in this work, we perform a comprehensive empirical study to characterize the performance of Hyperledger Fabric and identify potential performance bottlenecks to gain a better understanding of the system. We follow a two-phased approach. In the first phase, our goal is to understand the impact of various configuration parameters such as block size, endorsement policy, channels, resource allocation, state database choice on the transaction throughput & latency to provide various guidelines on configuring these parameters. In addition, we also aim to identify performance bottlenecks and hotspots. We observed that (1) endorsement policy verification, (2) sequential policy validation of transactions in a block, and (3) state validation and commit (with CouchDB) were the three major bottlenecks. In the second phase, we focus on optimizing Hyperledger Fabric v1.0 based on our observations. We introduced and studied various simple optimizations such as aggressive caching for endorsement policy verification in the cryptography component (3x improvement in the performance) and parallelizing endorsement policy verification (7x improvement). Further, we enhanced and measured the effect of an existing bulk read/write optimization for CouchDB during state validation & commit phase (2.5x improvement). By combining all three optimizations1, we improved the overall throughput by 16x (i.e., from 140 tps to 2250 tps).
Xin Sun, Quanlong Wang, Piotr Kulicki, Mirek Sopek
This paper proposes a simple voting protocol based on Quantum Blockchain. Despite its simplicity, our protocol satisfies the most important properties of secure voting protocols: is anonymous, binding, non-reusable, verifiable, eligible, fair and self-tallying. The protocol could also be implemented using presently available technology.
Yandamuri, Sravya, Abraham, Ittai, Nayak, Kartik, Reiter, Michael K.
A smart contract on a blockchain cannot keep a secret because its data is replicated on all nodes in a network. To remedy this problem, it has been suggested to combine blockchains with trusted execution environments (TEEs), such as Intel SGX, for executing applications that demand privacy. Untrusted blockchain nodes cannot get access to the data and computations inside the TEE. This paper first explores some pitfalls that arise from the combination of TEEs with blockchains. Since TEEs are, in principle, stateless they are susceptible to rollback attacks, which should be prevented to maintain privacy for the application. However, in blockchains with non-final consensus protocols, such as the proof-of-work in Ethereum and others, the contract execution must handle rollbacks by design. This implies that TEEs for securing blockchain execution cannot be directly used for such blockchains; this approach works only when the consensus decisions are final. Second, this work introduces an architecture and a prototype for smart-contract execution within Intel SGX technology for Hyperledger Fabric, a prominent platform for enterprise blockchain applications. Our system resolves difficulties posed by the execute-order-validate architecture of Fabric and prevents rollback attacks on TEE-based execution as far as possible. For increasing security, our design encapsulates each application on the blockchain within its own enclave that shields it from the host system. An evaluation shows that the overhead moving execution into SGX is within 10%-20% for a sealed-bid auction application.
Yackolley Amoussou-Guenou, Antonella Del Pozzo, Maria Potop-Butucaru, Sara Tucci-Piergiovanni
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.
Blockchain-based consensus protocols present the opportunity to develop new protocols, due to their novel requirements of open participation and explicit incentivization of participants. To address the first requirement, it is necessary to consider the leader election inherent in consensus protocols, which can be difficult to scale to a large and untrusted set of participants. To address the second, it is important to consider ways to provide incentivization without relying on the resource-intensive proofs-of-work used in Bitcoin. In this paper, we propose a secure leader election protocol, Caucus; we next fit this protocol into a broader blockchain-based consensus protocol, Fantomette, that provides game-theoretic guarantees in addition to traditional blockchain security properties. Fantomette is the first proof-of-stake protocol to give formal game-theoretic proofs of security in the presence of non-rational players.
In this paper we discuss a design philosophy for interoperable blockchain systems, using the design philosophy of the Internet architecture as the basis to identify key design principles. Several interoperability challenges are discussed in the context of cross-domain transactions. We illustrate how these principles are informing the interoperability architecture of the MIT Tradecoin system.
Blockchain-based cryptocurrencies secure a decentralized consensus protocol by incentives. The protocol participants, called miners, generate (mine) a series of blocks, each containing monetary transactions created by system users. As incentive for participation, miners receive newly minted currency and transaction fees paid by transaction creators. Blockchain bandwidth limits lead users to pay increasing fees in order to prioritize their transactions. However, most prior work focused on models where fees are negligible. In a notable exception, Carlsten et al. postulated in CCS'16 that if incentives come only from fees then a mining gap would form~--- miners would avoid mining when the available fees are insufficient. In this work, we analyze cryptocurrency security in realistic settings, taking into account all elements of expenses and rewards. To study when gaps form, we analyze the system as a game we call \emph{the gap game}. We analyze the game with a combination of symbolic and numeric analysis tools in a wide range of scenarios. Our analysis confirms Carlsten et al.'s postulate; indeed, we show that gaps form well before fees are the only incentive, and analyze the implications on security. Perhaps surprisingly, we show that different miners choose different gap sizes to optimize their utility, even when their operating costs are identical. Alarmingly, we see that the system incentivizes large miner coalitions, reducing system decentralization. We describe the required conditions to avoid the incentive misalignment, providing guidelines for future cryptocurrency design.
As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how to achieve subquadratic BA under an {\it adaptive} adversary. Intriguingly, they all make a common relaxation about the adaptivity of the attacker, that is, if an honest node sends a message and then gets corrupted in some round, the adversary {\it cannot erase the message that was already sent} --- henceforth we say that such an adversary cannot perform "after-the-fact removal". By contrast, many (super-)quadratic BA protocols in the literature can tolerate after-the-fact removal. In this paper, we first prove that disallowing after-the-fact removal is necessary for achieving subquadratic-communication BA. Next, we show new subquadratic binary BA constructions (of course, assuming no after-the-fact removal) that achieves near-optimal resilience and expected constant rounds under standard cryptographic assumptions and a public-key infrastructure (PKI) in both synchronous and partially synchronous settings. In comparison, all known subquadratic protocols make additional strong assumptions such as random oracles or the ability of honest nodes to erase secrets from memory, and even with these strong assumptions, no prior work can achieve the above properties. Lastly, we show that some setup assumption is necessary for achieving subquadratic multicast-based BA.
Blockchain is a novel technology that is rising a lot of interest in the industrial and re- search sectors because its properties of decentralisation, immutability and data integrity. Initially, the underlying consensus mechanism has been designed for permissionless block- chain on trustless network model through the proof-of-work, i.e. a mathematical challenge which requires high computational power. This solution suffers of poor performances, hence alternative consensus algorithms as the proof-of-stake have been proposed. Conversely, for permissioned blockchain, where participants are known and authenti- cated, variants of distributed consensus algorithms have been employed. However, most of them comes out without formal expression of security analysis and trust assumptions because the absence of an established knowledge. Therefore the lack of adequate analysis on these algorithms hinders any cautious evaluation of their effectiveness in a real-world setting where systems are deployed over trustless networks, i.e. Internet ...
Eric Zhang, C Hendrik, Yang Liu, Archit Sharma · 5 authors
In this paper we present the initial design of Minerva consensus protocol for Truechain and other technical details. Currently, it is widely believed in the blockchain community that a public chain cannot simultaneously achieve high performance, decentralization and security. This is true in the case of a Nakamoto chain (low performance) or a delegated proof of stake chain (partially centralized), which are the most popular block chain solutions at time of writing. Our consensus design enjoys the same consistency, liveness, transaction finality and security guarantee, a de-facto with the Hybrid Consensus. We go on to propose the idea of a new virtual machine on top of Ethereum which adds permissioned-chain based transaction processing capabilities in a permissionless setting. We also use the idea of data sharding and speculative transactions, and evaluation of smart contracts in a sharding friendly virtual machine. Finally, we will briefly discuss our fundamentally ASIC resistant mining algorithm, Truehash.
Blockchain technology has the potential to decentralise many traditionally centralised systems. However, scalability remains a key challenge. A horizontally scalable solution, where performance increases by adding more nodes, would move blockchain systems one step closer to ubiquitous use. We design a novel blockchain system called CHECO. Each node in our system maintains a personal hash chain, which only stores transactions that the node is involved in. A consensus is reached on special blocks called checkpoint blocks rather than on all transactions. Checkpoint blocks are effectively a hash pointer to the personal hash chains; thus a single checkpoint block may represent an arbitrarily large set of transactions. We introduce a validation protocol so that any node can check the validity of any transaction. Since transaction and validation protocols are point-to-point, we achieve horizontal scalability. We analytically evaluate our system and show a number of highly desirable correctness properties such as consensus on the validity of transactions. Further, we give a free and open-source implementation of CHECO and evaluate it experimentally. Our results show a strong indication of horizontal scalability.
Nicholas Stifter, Aljosha Judmayer, Philipp Schindler, Alexei Zamyatin · 5 authors
The term Nakamoto consensus is generally used to refer to Bitcoin’s novel consensus mechanism, by which agreement on its underlying transaction ledger is reached. It is argued that this agreement protocol represents the core innovation behind Bitcoin, because it promises to facilitate the decentralization of trusted third parties. Specifically, Nakamoto consensus seeks to enable mutually distrusting entities with weak pseudonymous identities to reach eventual agreement while the set of participants may change over time. When the Bitcoin white paper was published in late 2008, it lacked a formal analysis of the protocol and the guarantees it claimed to provide. It would take the scientific community several years before first steps towards such a formalization of the Bitcoin protocol and Nakamoto consensus were presented. However, since then the number of works addressing this topic has grown substantially, providing many new and valuable insights. Herein, we present a coherent picture of advancements towards the formalization of Nakamoto consensus, as well as a contextualization in respect to previous research on the agreement problem and fault tolerant distributed computing. Thereby, we outline how Bitcoin’s consensus mechanism sets itself apart from previous approaches and where it can provide new impulses and directions to the scientific community. Understanding the core properties and characteristics of Nakamoto consensus is of key importance, not only for assessing the security and reliability of various blockchain systems that are based on the fundamentals of this scheme, but also for designing future systems that aim to fulfill comparable goals.
Cryptocurrencies have seen a massive surge in popularity and behind these new virtual currencies is an innovative technology called the blockchain: a distributed digital ledger in which cryptocurrency transactions are recorded after having been verified. The transactions within a ledger are verified by multiple clients or “validators,” within the cryptocurrency's peer-to-peer network using one of many varied consensus algorithms for resolving the problem of reliability in a network involving multiple unreliable nodes. The most widely used consensus algorithms are the Proof of Work (PoW) algorithm and the Proof of Stake (PoS) algorithm; however, there are also other consensus algorithms which utilize alternative implementations of PoW and PoS, as well as other hybrid implementations and some altogether new consensus strategies. In this paper, we perform a comparative analysis of typical consensus algorithms and some of their contemporaries that are currently in use in modern blockchains. Our analysis focuses on the algorithmic steps taken by each consensus algorithm, the scalability of the algorithm, the method the algorithm rewards validators for their time spent verifying blocks, and the security risks present within the algorithm. Finally, we present our conclusion and some possible future trends for consensus algorithms used in blockchains.
Nowadays, blockchain is becoming a synonym for distributed ledger technology. However, blockchain is only one of the specializations in the field and is currently well-covered in existing literature, but mostly from a cryptographic point of view. Besides blockchain technology, a new paradigm is gaining momentum: directed acyclic graphs. The contribution presented in this paper is twofold. Firstly, the paper analyzes distributed ledger technology with an emphasis on the features relevant to distributed systems. Secondly, the paper analyses the usage of directed acyclic graph paradigm in the context of distributed ledgers, and compares it with the blockchain-based solutions. The two paradigms are compared using representative implementations: Bitcoin, Ethereum and Nano. We examine representative solutions in terms of the applied data structures for maintaining the ledger, consensus mechanisms, transaction confirmation confidence, ledger size, and scalability.
Nowadays, blockchain is becoming a synonym for distributed ledger technology.\nHowever, blockchain is only one of the specializations in the field and is\ncurrently well-covered in existing literature, but mostly from a cryptographic\npoint of view. Besides blockchain technology, a new paradigm is gaining\nmomentum: directed acyclic graphs. The contribution presented in this paper is\ntwofold. Firstly, the paper analyzes distributed ledger technology with an\nemphasis on the features relevant to distributed systems. Secondly, the paper\nanalyses the usage of directed acyclic graph paradigm in the context of\ndistributed ledgers, and compares it with the blockchain-based solutions. The\ntwo paradigms are compared using representative implementations: Bitcoin,\nEthereum and Nano. We examine representative solutions in terms of the applied\ndata structures for maintaining the ledger, consensus mechanisms, transaction\nconfirmation confidence, ledger size, and scalability.\n
Blockchain has received much attention in recent years. This immense popularity has raised a number of concerns, scalability of blockchain systems being a common one. In this paper, we seek to understand how Ethereum, a well-established blockchain system, would respond to sharding. Sharding is a prevalent technique to increase the scalability of distributed systems. To understand how sharding would affect Ethereum, we model Ethereum blockchain as a graph and evaluate five methods to partition the graph. We analyze the results using three metrics: the balance among shards, the number of transactions that would involve multiple shards, and the amount of data that would be relocated across shards upon a repartitioning of the system.
Decentralized currencies and similar blockchain applications require consensus. Bitcoin achieves eventual consensus in a fully-decentralized setting, but provides very low throughput and high latency with excessive energy consumption. In this paper, we propose identity aging as a novel and more efficient consensus approach. Our main idea is to establish reliable, long-term identities and choose the oldest identity as the miner on each round. Based on this approach, we design two blockchain systems. Our first system, SCIFER, leverages Intel's SGX attestation for identity bootstrapping in a partially-decentralized setting, where blockchain is permissionless, but we trust Intel for attestation. Our second system, DIFER, creates new identities through a novel mining mechanism and provides consensus in a fully-decentralized setting, similar to Bitcoin. One of the main benefits of identity aging is that it does not require constant computation. Our analysis and experiments show that identity aging provides significant performance improvements over Bitcoin with strong security guarantees.
Proof-of-Stake systems randomly choose, on each round, one of the\nparticipants as a consensus leader that extends the chain with the next block\nsuch that the selection probability is proportional to the owned stake.\nHowever, distributed random number generation is notoriously difficult. Systems\nthat derive randomness from the previous blocks are completely insecure;\nsolutions that provide secure random selection are inefficient due to their\nhigh communication complexity; and approaches that balance security and\nperformance exhibit selection bias. When block creation is rewarded with new\nstake, even a minor bias can have a severe cumulative effect.\n In this paper, we propose Robust Round Robin, a new consensus scheme that\naddresses this selection problem. We create reliable long-term identities by\nbootstrapping from an existing infrastructure, such as Intel's SGX processors,\nor by mining them starting from an initial fair distribution. For leader\nselection we use a deterministic approach. On each round, we select a set of\nthe previously created identities as consensus leader candidates in round robin\nmanner. Because simple round-robin alone is vulnerable to attacks and offers\npoor liveness, we complement such deterministic selection policy with a\nlightweight endorsement mechanism that is an interactive protocol between the\nleader candidates and a small subset of other system participants. Our solution\nhas low good efficiency as it requires no expensive distributed randomness\ngeneration and it provides block creation fairness which is crucial in\ndeployments that reward it with new stake.\n
Elli Androulaki, Artem Barger, Vita Bortnikov, Christian Cachin · 21 authors
The success of public blockchains, such as Bitcoin and Ethereum, led to growing interest in Blockchain technology and its application as a distributed system in the most innovative business use cases.
We present SBFT: a scalable decentralized trust infrastructure for Blockchains. SBFT implements a new Byzantine fault tolerant algorithm that addresses the challenges of scalability and decentralization. Unlike many previous BFT systems that performed well only when centralized around less than 20 replicas, SBFT is optimized for decentralization and can easily handle more than 100 active replicas. SBFT provides a smart contract execution environment based on Ethereum's EVM byte-code.
We tested SBFT by running 1 million EVM smart contract transactions taken from a 4-month real-world Ethereum workload. In a geo-replicated deployment that has about 100 replicas and can withstand $f=32$ Byzantine faults our system shows speedups both in throughput and in latency. SBFT completed this execution at a rate of 50 transactions per second. This is a $10\times$ speedup compared to Ethereum current limit of $5$ transactions per second. SBFT latency to commit a smart contract execution and make it final is sub-second, this is more than $10\times$ speedup compared to Ethereum current $>15$ second block generation for registering a smart contract execution and several orders of magnitude speedup relative to Proof-of-Work best-practice finality latency of one-hour.