Andrew Miller, Iddo Bentov, Surya Bakshi, Ranjit Kumaresan · 5 authors
Bitcoin, Ethereum and other blockchain-based cryptocurrencies, as deployed today, cannot scale for wide-spread use. A leading approach for cryptocurrency scaling is a smart contract mechanism called a payment channel which enables two mutually distrustful parties to transact efficiently (and only requires a single transaction in the blockchain to set-up). Payment channels can be linked together to form a payment network, such that payments between any two parties can (usually) be routed through the network along a path that connects them. Crucially, both parties can transact without trusting hops along the route. In this paper, we propose a novel variant of payment channels, called Sprites, that reduces the worst-case "collateral cost" that each hop along the route may incur. The benefits of Sprites are two-fold. 1) In Lightning Network, a payment across a path of $\ell$ channels requires locking up collateral for $Θ(\ellΔ)$ time, where $Δ$ is the time to commit an on-chain transaction. Sprites reduces this cost to $O(\ell + Δ)$. 2) Unlike prior work, Sprites supports partial withdrawals and deposits, during which the channel can continue to operate without interruption. In evaluating Sprites we make several additional contributions. First, our simulation-based security model is the first formalism to model timing guarantees in payment channels. Our construction is also modular, making use of a generic abstraction from folklore, called the "state channel," which we are the first to formalize. We also provide a simulation framework for payment network protocols, which we use to confirm that the Sprites construction mitigates against throughput-reducing attacks.
Andrew Miller, Iddo Bentov, Ranjit Kumaresan, Christopher Cordi · 5 authors
Bitcoin, Ethereum and other blockchain-based cryptocurrencies, as deployed\ntoday, cannot scale for wide-spread use. A leading approach for cryptocurrency\nscaling is a smart contract mechanism called a payment channel which enables\ntwo mutually distrustful parties to transact efficiently (and only requires a\nsingle transaction in the blockchain to set-up). Payment channels can be linked\ntogether to form a payment network, such that payments between any two parties\ncan (usually) be routed through the network along a path that connects them.\nCrucially, both parties can transact without trusting hops along the route.\n In this paper, we propose a novel variant of payment channels, called\nSprites, that reduces the worst-case "collateral cost" that each hop along the\nroute may incur. The benefits of Sprites are two-fold. 1) In Lightning Network,\na payment across a path of $\\ell$ channels requires locking up collateral for\n$\\Theta(\\ell\\Delta)$ time, where $\\Delta$ is the time to commit an on-chain\ntransaction. Sprites reduces this cost to $O(\\ell + \\Delta)$. 2) Unlike prior\nwork, Sprites supports partial withdrawals and deposits, during which the\nchannel can continue to operate without interruption.\n In evaluating Sprites we make several additional contributions. First, our\nsimulation-based security model is the first formalism to model timing\nguarantees in payment channels. Our construction is also modular, making use of\na generic abstraction from folklore, called the "state channel," which we are\nthe first to formalize. We also provide a simulation framework for payment\nnetwork protocols, which we use to confirm that the Sprites construction\nmitigates against throughput-reducing attacks.\n
Thomas Dickerson, Paul Gazzillo, Maurice Herlihy, Eric Koskinen
Modern cryptocurrency systems, such as Ethereum, permit complex financial transactions through scripts called smart contracts. These smart contracts are executed many, many times, always without real concurrency. First, all smart contracts are serially executed by miners before appending them to the blockchain. Later, those contracts are serially re-executed by validators to verify that the smart contracts were executed correctly by miners. Serial execution limits system throughput and fails to exploit today's concurrent multicore and cluster architectures. Nevertheless, serial execution appears to be required: contracts share state, and contract programming languages have a serial semantics. This paper presents a novel way to permit miners and validators to execute smart contracts in parallel, based on techniques adapted from software transactional memory. Miners execute smart contracts speculatively in parallel, allowing non-conflicting contracts to proceed concurrently, and "discovering" a serializable concurrent schedule for a block's transactions, This schedule is captured and encoded as a deterministic fork-join program used by validators to re-execute the miner's parallel schedule deterministically but concurrently. Smart contract benchmarks run on a JVM with ScalaSTM show that a speedup of of 1.33x can be obtained for miners and 1.69x for validators with just three concurrent threads.
Tyler Crain, Vincent Gramoli, Mikel Larrea, Michel Raynal
This paper presents a new Byzantine consensus algorithm targeting consortium blockchains. To this end, it first revisits the consensus validity property by requiring that the decided value satisfies a predefined predicate, which does not systematically exclude a value proposed only by Byzantine processes, thereby generalizing the validity properties found in the literature. Then, the paper presents a simple and modular Byzantine consensus algorithm that relies neither on a leader, nor on signatures, nor on randomization. It features the fastest multivalued reduction to binary consensus we know of and a time optimal binary Byzantine consensus algorithm. The multivalued reduction runs multiple instances of binary consensus concurrently, which result in a bitmask that is then applied to a vector of multivalued proposals to filter out a valid proposed value that is decided. To ensure eventual decision deterministically, the underlying binary consensus algorithm assumes eventual synchrony.
Consensus, or state machine replication is a foundational building block of distributed systems and modern cryptography. Consensus in the classical, "permissioned" setting has been extensively studied in the 30 years of distributed systems literature. Recent developments in Bitcoin and other decentralized cryptocurrencies popularized a new form of consensus in a "permissionless" setting, where anyone can join and leave dynamically, and there is no a-priori knowledge of the number of consensus nodes. So far, however, all known permissionless consensus protocols assume network synchrony, i.e., the protocol must know an upper bound of the network's delay, and transactions confirm slower than this a-priori upper bound. We initiate the study of the feasibilities and infeasibilities of achieving responsiveness in permissionless consensus. In a responsive protocol, the transaction confirmation time depends only on the actual network delay, but not on any a-priori known upper bound such as a synchronous round. Classical protocols in the partial synchronous and asynchronous models naturally achieve responsiveness, since the protocol does not even know any delay upper bound. Unfortunately, we show that in the permissionless setting, consensus is impossible in the asynchronous or partially synchronous models. On the positive side, we construct a protocol called Hybrid Consensus by combining classical-style and blockchain-style consensus. Hybrid Consensus shows that responsiveness is nonetheless possible to achieve in permissionless consensus (assuming proof-of-work) when 1) the protocol knows an upper bound on the network delay; 2) we allow a non-responsive warmup period after which transaction confirmation can become responsive; 3) honesty has some stickiness, i.e., it takes a short while for an adversary to corrupt a node or put it to sleep; and 4) less than 1/3 of the nodes are corrupt. We show that all these conditions are in fact necessary - if only one of them is violated, responsiveness would have been impossible. Our work makes a step forward in our understanding of the permissionless model and its differences and relations to classical consensus.
In the last decades, we have witnessed an exploding growth of the Internet. The massive adoption of distributed systems on the Internet allows users to offload their computing intensive work to remote servers, e.g. cloud. In this context, distributed systems are pervasively used in a number of difference scenarios, such as web-based services that receive and process data, cloud nodes where company data and processes are executed, and softwarised networks that process packets. In these systems, all the computing entities need to trust each other and co-operate in order to work properly. While the communication channels can be well protected by protocols like TLS or IPsec, the problem lies in the expected behaviour of the remote computing platforms, because they are not under the direct control of end users and do not offer any guarantee that they will behave as agreed. For example, the remote party may use non-legitimate services for its own convenience (e.g. illegally storing received data and routed packets), or the remote system may misbehave due to an attack (e.g. changing deployed services). This is especially important because most of these computing entities need to expose interfaces towards the Internet, which makes them easier to be attacked. Hence, software-based security solutions alone are insufficient to deal with the current scenario of distributed systems. They must be coupled with stronger means such as hardware-assisted protection. In order to allow the nodes in distributed system to trust each other, their integrity must be presented and assessed to predict their behaviour. The remote attestation technique of trusted computing was proposed to specifically deal with the integrity issue of remote entities, e.g. whether the platform is compromised with bootkit attacks or cracked kernel and services. This technique relies on a hardware chip called Trusted Platform Module (TPM), which is available in most business class laptops, desktops and servers. The TPM plays as the hardware root of trust, which provides a special set of capabilities that allows a physical platform to present its integrity state. With a TPM equipped in the motherboard, the remote attestation is the procedure that a physical node provides hardware-based proof of the software components loaded in this platform, which can be evaluated by other entities to conclude its integrity state. Thanks to the hardware TPM, the remote attestation procedure is resistant to software attacks. However, even though the availability of this chip is high, its actual usage is low. The major reason is that trusted computing has very little flexibility, since its goal is to provide strong integrity guarantees. For instance, remote attestation result is positive if and only if the software components loaded in the platform are expected and loaded in a specific order, which limits its applicability in real-world scenarios. For such reasons, this technique is especially hard to be applied on software services running in application layer, that are loaded in random order and constantly updated. Because of this, current remote attestation techniques provide incomplete solution. They only focus on the boot phase of physical platforms but not on the services, not to mention the services running in virtual instances. This work first proposes a new remote attestation framework with the capability of presenting and evaluating the integrity state not only of the boot phase of physical platforms but also of software services at load time, e.g. whether the software is legitimate or not. The framework allows users to know and understand the integrity state of the whole life cycle of the services they are interacting with, thus the users can make informed decision whether to send their data or trust the received results. Second, based on the remote attestation framework this thesis proposes a method to bind the identity of secure channel endpoint to a specific physical platform and its integrity state. Secure channels are extensively adopted in distributed systems to protect data transmitted from one platform to another. However, they do not convey any information about the integrity state of the platform or the service that generates and receives this data, which leaves ample space for various attacks. With the binding of the secure channel endpoint and the hardware TPM, users are protected from relay attacks (with hardware-based identity) and malicious or cracked platform and software (with remote attestation). Third, with the help of the remote attestation framework, this thesis introduces a new method to include the integrity state of software services running in virtual containers in the evidence generated by the hardware TPM. This solution is especially important for softwarised network environments. Softwarised network was proposed to provide dynamic and flexible network deployment which is an ever complex task nowadays. Its main idea is to switch hardware appliances to softwarised network functions running inside virtual instances, that are full-fledged computational systems and accessible from the Internet, thus their integrity is at stake. Unfortunately, currently remote attestation work is not able to provide hardware-based integrity evidence for software services running inside virtual instances, because the direct link between the internal of virtual instances and hardware root of trust is missing. With the solution proposed in this thesis, the integrity state of the softwarised network functions running in virtual containers can be presented and evaluated with hardware-based evidence, implying the integrity of the whole softwarised network. The proposed remote attestation framework, trusted channel and trusted softwarised network are implemented in separate working prototypes. Their performance was evaluated and proved to be excellent, allowing them to be applied in real-world scenarios. Moreover, the implementation also exposes various APIs to simplify future integration with different management platforms, such as OpenStack and OpenMANO.
A blockchain is a distributed ledger for recording transactions, maintained by many nodes without central authority through a distributed cryptographic protocol. All nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Consensus protocols for tolerating Byzantine faults have received renewed attention because they also address blockchain systems. This work discusses the process of assessing and gaining confidence in the resilience of a consensus protocols exposed to faults and adversarial nodes. We advocate to follow the established practice in cryptography and computer security, relying on public reviews, detailed models, and formal proofs; the designers of several practical systems appear to be unaware of this. Moreover, we review the consensus protocols in some prominent permissioned blockchain platforms with respect to their fault models and resilience against attacks.
In this paper, we explore remarkable similarities between multi-transactional behaviors of smart contracts in cryptocurrencies such as Ethereum and classical problems of shared-memory concurrency. We examine two real-world examples from the Ethereum blockchain and analyzing how they are vulnerable to bugs that are closely reminiscent to those that often occur in traditional concurrent programs. We then elaborate on the relation between observable contract behaviors and well-studied concurrency topics, such as atomicity, interference, synchronization, and resource ownership. The described contracts-as-concurrent-objects analogy provides deeper understanding of potential threats for smart contracts, indicate better engineering practices, and enable applications of existing state-of-the-art formal verification techniques.
On-line commercial transactions involve an inherent mistrust between participant parties since, sometimes, no previous relation exists between them. Such mistrust may be a deadlock point in a trade transaction where the buyer does not want to perform the payment until the seller sends the goods and the seller does not want to do so until the buyer pays for the purchase. In this paper we present a fair protocol for data trading where the commercial deal, in terms of delivering the data and performing the payment, is atomic, since the seller cannot redeem the payment unless the buyer obtains the data and the buyer cannot obtain the data without performing the payment. The protocol is based on Bitcoin scripting language and the fairness of the protocol can be probabilistically enforced.
The Bitcoin protocol allows to save arbitrary data on the blockchain through a special instruction of the scripting language, called OP_RETURN. A growing number of protocols exploit this feature to extend the range of applications of the Bitcoin blockchain beyond transfer of currency. A point of debate in the Bitcoin community is whether loading data through OP_RETURN can negatively affect the performance of the Bitcoin network with respect to its primary goal. This paper is an empirical study of the usage of OP_RETURN over the years. We identify several protocols based on OP_RETURN, which we classify by their application domain. We measure the evolution in time of the usage of each protocol, the distribution of OP_RETURN transactions by application domain, and their space consumption.
Christian Badertscher, Ueli Maurer, Daniel Tschudi, Vassilis Zikas
Abstract Bitcoin is one of the most prominent examples of a distributed cryptographic protocol that is extensively used in reality. Nonetheless, existing security proofs are property-based, and as such they do not support composition. In this work, we put forth a universally composable treatment of the Bitcoin protocol. We specify the goal that Bitcoin aims to achieve as an instance of a parameterizable ledger functionality and present a UC abstraction of the Bitcoin blockchain protocol. Our ideal functionality is weaker than the first proposed candidate by Kiayias, Zhou, and Zikas [EUROCRYPT’16], but unlike the latter suggestion, which is arguably not implementable by the UC Bitcoin protocol, we prove that the one proposed here is securely UC-realized by the protocol assuming access to a global clock, to model time-based executions, a random oracle, to model hash functions, and an idealized network, to model message dissemination. We further show how known property-based approaches can be cast as special instances of our treatment and how their underlying assumptions can be cast in UC as part of the setup functionalities and without restricting the environment or the adversary.
In this paper, we identify a new form of attack, called the Balance attack, against proof-of-work blockchain systems. The novelty of this attack consists of delaying network communications between multiple subgroups of nodes with balanced mining power. Our theoretical analysis captures the precise tradeoff between the network delay and the mining power of the attacker needed to double spend in Ethereum with high probability. We quantify our probabilistic analysis with statistics taken from the R3 consortium, and show that a single machine needs 20 minutes to attack the consortium. Finally, we run an Ethereum private chain in a distributed system with similar settings as R3 to demonstrate the feasibility of the approach, and discuss the application of the Balance attack to Bitcoin. Our results clearly confirm that main proof-of-work blockchain protocols can be badly suited for consortium blockchains.
Johnny Dilley, Andrew Poelstra, Jonathan Wilkins, Marta Piekarska · 6 authors
Bitcoin, the first peer-to-peer electronic cash system, opened the door to permissionless, private, and trustless transactions. Attempts to repurpose Bitcoin's underlying blockchain technology have run up against fundamental limitations to privacy, faithful execution, and transaction finality. We introduce \emph{Strong Federations}: publicly verifiable, Byzantine-robust transaction networks that facilitate movement of any asset between disparate markets, without requiring third-party trust. \emph{Strong Federations} enable commercial privacy, with support for transactions where asset types and amounts are opaque, while remaining publicly verifiable. As in Bitcoin, execution fidelity is cryptographically enforced; however, \emph{Strong Federations} significantly lower capital requirements for market participants by reducing transaction latency and improving interoperability. To show how this innovative solution can be applied today, we describe \emph{\liquid}: the first implementation of \emph{Strong Federations} deployed in a Financial Market.
The decentralized cryptocurrency Bitcoin has experienced great success but also encountered many challenges. One of the challenges has been the long confirmation time. Another challenge is the lack of incentives at certain steps of the protocol, raising concerns for transaction withholding, selfish mining, etc. To address these challenges, we propose Solida, a decentralized blockchain protocol based on reconfigurable Byzantine consensus augmented by proof-of-work. Solida improves on Bitcoin in confirmation time, and provides safety and liveness assuming the adversary control less than (roughly) one-third of the total mining power.
Joshua Lind, Ittay Eyal, Peter Pietzuch, Emin Gün Sirer
Blockchain protocols are inherently limited in transaction throughput and latency. Recent efforts to address performance and scale blockchains have focused on off-chain payment channels. While such channels can achieve low latency and high throughput, deploying them securely on top of the Bitcoin blockchain has been difficult, partly because building a secure implementation requires changes to the underlying protocol and the ecosystem. We present Teechan, a full-duplex payment channel framework that exploits trusted execution environments. Teechan can be deployed securely on the existing Bitcoin blockchain without having to modify the protocol. It: (i) achieves a higher transaction throughput and lower transaction latency than prior solutions; (ii) enables unlimited full-duplex payments as long as the balance does not exceed the channel's credit; (iii) requires only a single message to be sent per payment in any direction; and (iv) places at most two transactions on the blockchain under any execution scenario. We have built and deployed the Teechan framework using Intel SGX on the Bitcoin network. Our experiments show that, not counting network latencies, Teechan can achieve 2,480 transactions per second on a single channel, with sub-millisecond latencies.
Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi · 5 authors
The surprising success of cryptocurrencies has led to a surge of interest in deploying large scale, highly robust, Byzantine fault tolerant (BFT) protocols for mission-critical applications, such as financial transactions. Although the conventional wisdom is to build atop a (weakly) synchronous protocol such as PBFT (or a variation thereof), such protocols rely critically on network timing assumptions, and only guarantee liveness when the network behaves as expected. We argue these protocols are ill-suited for this deployment scenario. We present an alternative, HoneyBadgerBFT, the first practical asynchronous BFT protocol, which guarantees liveness without making any timing assumptions. We base our solution on a novel atomic broadcast protocol that achieves optimal asymptotic efficiency. We present an implementation and experimental results to show our system can achieve throughput of tens of thousands of transactions per second, and scales to over a hundred nodes on a wide area network. We even conduct BFT experiments over Tor, without needing to tune any parameters. Unlike the alternatives, HoneyBadgerBFT simply does not care about the underlying network.
Roman Matzutt, Oliver Hohlfeld, Martin Henze, Robin Rawiel · 6 authors
As transaction fees skyrocket today, blockchains become increasingly expensive, hurting their adoption in broader applications. This work tackles the saving of transaction fees for economic blockchain applications. The key insight is that other than the existing "default'' mode to execute application logic fully on-chain, i.e., in smart contracts, and in fine granularity, i.e., user request per transaction, there are alternative execution modes with advantages in cost-effectiveness. On Ethereum, we propose a holistic middleware platform supporting flexible and secure transaction executions, including off-chain states and batching of user requests. Furthermore, we propose control-plane schemes to adapt the execution mode to the current workload for optimal runtime cost. We present a case study on the institutional accounts (e.g., coinbase.com) intensively sending Ether on Ethereum blockchains. By collecting real-life transactions, we construct workload benchmarks and show that our work saves 18%\sim 47%18%-47% per invocation than the default baseline while introducing 1.81%\sim 16.59%1.81%-16.59% blocks delay.
Emmanuelle Anceaume, Thibaut Lajoie-Mazenc, Romaric Ludinard, Bruno Sericola
Decentralized cryptocurrency systems offer a medium of exchange secured by cryptography, without the need of a centralized banking authority. Among others, Bitcoin is considered as the most mature one. Its popularity lies on the introduction of the concept of the blockchain, a public distributed ledger shared by all participants of the system. Double spending attacks and blockchain forks are two main issues in blockchain-based protocols. The first one refers to the ability of an adversary to use the very same bitcoin more than once, while blockchain forks cause transient inconsistencies in the blockchain. We show through probabilistic analysis that the reliability of recent solutions that exclusively rely on a particular type of Bitcoin actors, called miners, to guarantee the consistency of Bitcoin operations, drastically decreases with the size of the blockchain.
Die Möglichkeit der Programmierbarkeit des Bitcoins ist fast ein nachträglicher Einfall, auch wenn Sidechain‐Vorschläge diese Programmierbarkeit ein wenig leichter machen wollen und es bereits Altcoins mit verschiedenen spezifischen Anwendungen gibt. Im Gegensatz dazu wurde das Kryptowährungstechnologieprojekt Ethereum von Vitalik Buterin, seinem Erfinder, von Tag 1 als Software‐Entwicklungsplattform für dezentrale Applikationen konzipiert, und ihre Blockchain wurde speziell entwickelt, um die Ausführung dieser dezentralen Apps (auch Dapps genannt) zu unterstützen. Vitalik Buterin, 1994 in Russland geboren, war vor der Gründung von Ethereum auch involviert in die Entwicklungsprojekte Colored Coins und Mastercoins. Er gewann 2014 den "World Technology Award" und ein Stipendium des Risikokapitalgebers Peter Thiel. In dem Diskussionspapier zu Ethereum skizzierte Buterin vor allem die Grenzen einer Programmierbarkeit der Bitcoin‐Blockchain und schlug die Erstellung einer neuen komplett programmierbaren Blockchain mit einer turing‐vollständigen Programmiersprache vor. Anders als andere Blockchain‐Projekte soll die Ethereum Software nicht nur für einen Zweck nutzbar sein – sondern soll die Basis für die Erarbeitung aller möglichen Arten von Lösungen sein und dabei die Umsetzung intelligenter Verträge (Smart Contracts) ebenso erfassen als auch die Ethereum‐spezifische Idee von dezentralen autonomen Organisationen (DAOs).
A public ledger is a tamperproof sequence of data that can be read and augmented by everyone. Public ledgers have innumerable and compelling uses. They can secure, in plain sight, all kinds of transactions ---such as titles, sales, and payments--- in the exact order in which they occur. Public ledgers not only curb corruption, but also enable very sophisticated applications ---such as cryptocurrencies and smart contracts. They stand to revolutionize the way a democratic society operates. As currently implemented, however, they scale poorly and cannot achieve their potential. Algorand is a truly democratic and efficient way to implement a public ledger. Unlike prior implementations based on proof of work, it requires a negligible amount of computation, and generates a transaction history that will not "fork" with overwhelmingly high probability. Algorand is based on (a novel and super fast) message-passing Byzantine agreement. For concreteness, we shall describe Algorand only as a money platform.
Most popular blockchain solutions, like Bitcoin, rely on proof-of-work, guaranteeing that the output of the consensus is agreed upon with high probability. However, this probability depends on the delivery of messages and that the computational power of the system is sufficiently scattered among pools of nodes in the network so that no pool can mine more blocks faster than the crowd. New approaches, like Ethereum, generalise the proof-of-work approach by letting individuals deploy their own private blockchain with high transaction throughput. As companies are starting to deploy private chains, it has become crucial to better understand the guarantees blockchains offer in such a small and controlled environment. In this paper, we present the \emph{Blockchain Anomaly}, an execution that we experienced when building our private chain at NICTA/Data61. Even though this anomaly has never been acknowledged before, it may translate into dramatic consequences for the user of blockchains. Named after the infamous Paxos anomaly, this anomaly makes dependent transactions, like "Bob sends money to Carole after he received money from Alice" impossible. This anomaly relies on the fact that existing blockchains do not ensure consensus safety deterministically: there is no way for Bob to make sure that Alice actually sent him coins without Bob using an external mechanism, like converting these coins into a fiat currency that allows him to withdraw. We also explore smart contracts as a potential alternative to transactions in order to freeze coins, and show implementations of smart contract that can suffer from the Blockchain anomaly and others that may cope with it.