Michele Bottone, Franco Raimondi, Giuseppe Primiero
In the past ten years distributed ledgers such as Bitcoin and smart contracts that can run code autonomously have seen an exponential growth both in terms of research interest and in terms of industrial and financial applications. These find a natural application in the area of Sensor Networks and Cyber-Physical Systems. However, the incentive architecture of blockchains requires massive computational resources for mining, delays in the confirmation of transactions and, more importantly, continuously growing transaction fees, which are ill-suited to systems in which services may be provided by resource-limited devices and confirmation times and transaction costs should be kept minimal, ideally absent. We focus on a new block-less, fee-less paradigm for distributed ledgers suitable for the WSN, IoT and CPS in which transactions are nodes of a directed acyclic graph, that overcomes the limitations of blockchains for these applications, and where e.g. sensors can be at the same time issuers of transactions and validators of previous transactions. In particular, we present and release open-source a simulation environment that can be easily extended and analysed, and confirms the available results on the performance of the network.
Distributed Ledger Technology (DLT) is probably going, in the near future, to disrupt B2B and B2C interactions even more than the advent of the World Wide Web, thanks to the transfer of trust from personal and commercial relationships to computing algorithms. However, a less commonly perceived property of DLT is that of enabler of decentralized computing. In this paper, we explore the use of DLT to innovate Industrial Cyber-Physical Systems.
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.
Incorporating accountability mechanisms in online services requires effective trust management and immutable, traceable source of truth for transaction evidence. The emergence of the blockchain technology brings in high hopes for fulfilling most of those requirements. However, a major challenge is to find a proper consensus protocol that is applicable to the crowdsourcing services in particular and online services in general. Building upon the idea of using blockchain as the underlying technology to enable tracing transactions for service contracts and dispute arbitration, this paper proposes a novel consensus protocol that is suitable for the crowdsourcing as well as the general online service industry. The new consensus protocol is called “Proof-of-Trust” (PoT) consensus; it selects transaction validators based on the service participants' trust values while leveraging RAFT leader election and Shamir's secret sharing algorithms. The PoT protocol avoids the low throughput and resource intensive pitfalls associated with Bitcoin' s “Proof-of-Work” (PoW) mining, while addressing the scalability issue associated with the traditional Paxos-based and Byzantine Fault Tolerance (BFT)-based algorithms. In addition, it addresses the unfaithful behaviors that cannot be dealt with in the traditional BFT algorithms. The paper demonstrates that our approach can provide a viable accountability solution for the online service industry.
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.
Hung Dang, Tien Tuan Anh Dinh, Dumitrel Loghin, Ee‐Chien Chang · 6 authors
Existing blockchain systems scale poorly because of their distributed consensus protocols. Current attempts at improving blockchain scalability are limited to cryptocurrency. Scaling blockchain systems under general workloads (i.e., non-cryptocurrency applications) remains an open question. In this work, we take a principled approach to apply sharding, which is a well-studied and proven technique to scale out databases, to blockchain systems in order to improve their transaction throughput at scale. This is challenging, however, due to the fundamental difference in failure models between databases and blockchain. To achieve our goal, we first enhance the performance of Byzantine consensus protocols, by doing so we improve individual shards' throughput. Next, we design an efficient shard formation protocol that leverages a trusted random beacon to securely assign nodes into shards. We rely on trusted hardware, namely Intel SGX, to achieve high performance for both consensus and shard formation protocol. Third, we design a general distributed transaction protocol that ensures safety and liveness even when transaction coordinators are malicious. Finally, we conduct an extensive evaluation of our design both on a local cluster and on Google Cloud Platform. The results show that our consensus and shard formation protocols outperform state-of-the-art solutions at scale. More importantly, our sharded blockchain reaches a high throughput that can handle Visa-level workloads, and is the largest ever reported in a realistic environment.
Electric Autonomous Vehicles (EAVs) promise to be an effective way to solve\ntransportation issues such as accidents, emissions and congestion, and aim at\nestablishing the foundation of Machine-to-Machine (M2M) economy. For this to be\npossible, the market should be able to offer appropriate charging services\nwithout involving humans. The state-of-the-art mechanisms of charging and\nbilling do not meet this requirement, and often impose service fees for value\ntransactions that may also endanger users and their location privacy. This\npaper aims at filling this gap and envisions a new charging architecture and a\nbilling framework for EAV which would enable M2M transactions via the use of\nDistributed Ledger Technology (DLT).\n
Electric Autonomous Vehicles (EAVs) promise to be an effective way to solve transportation issues such as accidents, emissions and congestion, and aim at establishing the foundation of Machine-to-Machine (M2M) economy. For this to be possible, the market should be able to offer appropriate charging services without involving humans. The state-of-the-art mechanisms of charging and billing do not meet this requirement, and often impose service fees for value transactions that may also endanger users and their location privacy. This paper aims at filling this gap and envisions a new charging architecture and a billing framework for EAV which would enable M2M transactions via the use of Distributed Ledger Technology (DLT).
Bitcoin provides freshness properties by forming a blockchain where each block is associated with its timestamp and the previous block. Due to these properties, the Bitcoin protocol is being used as a decentralized, trusted, and secure timestamping service. Although Bitcoin participants which create new blocks cannot modify their order, they can manipulate timestamps almost undetected. This undermines the Bitcoin protocol as a reliable timestamping service. In particular, a newcomer that synchronizes the entire blockchain has a little guarantee about timestamps of all blocks.
In this paper, we present a simple yet powerful mechanism that increases the reliability of Bitcoin timestamps. Our protocol can provide evidence that a block was created within a certain time range. The protocol is efficient, backward compatible, and surprisingly, currently deployed SSL/TLS servers can act as reference time sources. The protocol has many applications and can be used for detecting various attacks against the Bitcoin protocol.
Decentralized crypto-currencies based on the blockchain architecture\nunder-utilize available network bandwidth, making them unable to scale to\nthousands of transactions per second. We define the Blockclique architecture,\nthat addresses this limitation by sharding transactions in a block graph with a\nfixed number of threads. The architecture allows the creation of intrinsically\ncompatible blocks in parallel, where each block references one previous block\nof each thread. The consistency of the Blockclique protocol is formally\nestablished in presence of attackers. An experimental evaluation of the\narchitecture's performance in large realistic networks demonstrates an\nefficient use of available bandwidth and a throughput of thousands of\ntransactions per second.\n
Σκοπός της παρούσας διπλωματικής εργασίας είναι η εξέταση της τεχνολογίας που κρύβεται πίσω από τα κρυπτονομίσματα. Η τεχνολογία αυτή είναι το Blockchain και συγκεκριμένα το Blockchain Ethereum, το οποίο είναι μια δημόσια αποκεντρωμένη και κατανεμημένη πλατφόρμα που επιτρέπει σε οποιονδήποτε να δημιουργεί και να χρησιμοποιεί αποκεντρωμένες εφαρμογές που λειτουργούν με αυτή την τεχνολογία. Η καινοτομία της τεχνολογίας Blockchain δίνει λύση στο ζήτημα που αφορά την συγχρονισμένη καταγραφή δεδομένων σε ένα κατανεμημένο δίκτυο από ανεξάρτητους και άγνωστους μεταξύ τους κόμβους (υπολογιστές), συμφωνώντας ότι τα δεδομένα που αποθηκεύονται κάθε φορά είναι ακριβώς τα ίδια. Όλοι οι υπολογιστές που συμμετέχουν σε ένα δίκτυο Blockchain έχουν ακριβώς τα ίδια δεδομένα χωρίς να μπορούν να τα αλλάξουν ή να τα παραμετροποιήσουν, ενώ η ασφάλεια αυτών των δεδομένων επιτυγχάνεται μέσω της κρυπτογραφίας. \nΧρησιμοποιώντας λοιπόν την τεχνολογία Ethereum Blockchain, επιχειρήθηκε η δημιουργία μιας αποκεντρωμένης κατανεμημένης εφαρμογής σε συνεργασία με την εταιρία Intelen Inc. Συγκεκριμένα, έγινε χρήση της τεχνολογίας Blockchain για να επιτευχθεί επικοινωνία μεταξύ έξυπνων οικιακών μπαταριών χωρίς να απαιτείται η παρέμβαση οποιασδήποτε κεντρικής αρχής. Με άλλα λόγια δημιουργήθηκε σχετική εφαρμογή όπου οι έξυπνες μπαταρίες είναι σε θέση να χρησιμοποιήσουν το προσωπικό τους ηλεκτρονικό πορτοφόλι για να ανταλλάζουν κρυπτονομίσματα και πληροφορίες χωρίς την παρέμβαση από τρίτα άτομα.
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP , as long as one is willing to make a suitable physical assumption : if the provers are spatially isolated, then they can be assumed to be playing independent strategies. Quantum mechanics, however, tells us that this assumption is unrealistic, because spatially-isolated provers could share a quantum entangled state and realize a non-local correlated strategy. The MIP * model captures this setting. In this work, we study the following question: Does spatial isolation still suffice to unconditionally achieve zero knowledge even in the presence of quantum entanglement? We answer this question in the affirmative: we prove that every language in NEXP has a 2-prover zero knowledge interactive proof that is sound against entangled provers; that is, NEXP ⊆ ZK-MIP * . Our proof consists of constructing a zero knowledge interactive probabilistically checkable proof with a strong algebraic structure, and then lifting it to the MIP * model. This lifting relies on a new framework that builds on recent advances in low-degree testing against entangled strategies, and clearly separates classical and quantum tools. Our main technical contribution is the development of new algebraic techniques for obtaining unconditional zero knowledge; this includes a zero knowledge variant of the celebrated sumcheck protocol, a key building block in many probabilistic proof systems. A core component of our sumcheck protocol is a new algebraic commitment scheme, whose analysis relies on algebraic complexity theory.
Emmanuelle Anceaume, Antonella Del Pozzo, Romaric Ludinard, Maria Potop-Butucaru · 5 authors
The presented work continues the line of recent distributed computing community efforts dedicated to the theoretical aspects of blockchains. This paper is the first to specify blockchains as a composition of abstract data types all together with a hierarchy of consistency criteria that formally characterizes the histories admissible for distributed programs that use them. Our work is based on an original oracle-based construction that, along with new consistency definitions, captures the eventual convergence process in blockchain systems. The paper presents as well some results on implementability of the presented abstractions and a mapping of representative existing blockchains from both academia and industry in our framework.
Reasoning about commutativity between data-structure operations is an important problem with applications including parallelizing compilers, optimistic parallelization and, more recently, Ethereum smart contracts. There have been research results on automatic generation of commutativity conditions, yet we are unaware of any fully automated technique to generate conditions that are both sound and effective. We have designed such a technique, driven by an algorithm that iteratively refines a conservative approximation of the commutativity (and non-commutativity) condition for a pair of methods into an increasingly precise version. The algorithm terminates if/when the entire state space has been considered, and can be aborted at any time to obtain a partial yet sound commutativity condition. We have generalized our work to left-/right-movers and proved relative completeness. We describe aspects of our technique that lead to useful commutativity conditions, including how predicates are selected during refinement and heuristics that impact the output shape of the condition. We have implemented our technique in a prototype open-source tool Servois. Our algorithm produces quantifier-free queries that are dispatched to a back-end SMT solver. We evaluate Servois through two case studies: (i) We synthesize commutativity conditions for a range of data structures including Set, HashTable, Accumulator, Counter, and Stack. (ii) We consider an Ethereum smart contract called BlockKing, and show that Servois can detect serious concurrency-related vulnerabilities and guide developers to construct robust and efficient implementations.
Antonio Fernández Anta, Chryssis Georgiou, Kishori M. Konwar, Nicolas Nicolaou
Despite the hype about blockchains and distributed ledgers, no formal abstraction of these objects has been proposed. To face this issue, in this paper we provide a proper formulation of a distributed ledger object. In brief, we define a ledger object as a sequence of records, and we provide the operations and the properties that such an object should support. Implementation of a ledger object on top of multiple (possibly geographically dispersed) computing devices gives rise to the distributed ledger object. In contrast to the centralized object, distribution allows operations to be applied concurrently on the ledger, introducing challenges on the consistency of the ledger in each participant. We provide the definitions of three well known consistency guarantees in terms of the operations supported by the ledger object: (1) atomic consistency (linearizability), (2) sequential consistency, and (3) eventual consistency. We then provide implementations of distributed ledgers on asynchronous message passing crash-prone systems using an Atomic Broadcast service, and show that they provide eventual, sequential or atomic consistency semantics. We conclude with a variation of the ledger - the validated ledger - which requires that each record in the ledger satisfies a particular validation rule.
Existing Byzantine fault tolerance (BFT) protocols face significant challenges in the consortium blockchain scenario. On the one hand, we can make little assumptions about the reliability and security of the underlying Internet. On the other hand, the applications on consortium blockchains demand a system as scalable as the Bit-coin but providing much higher performance, as well as provable safety. We present a new BFT protocol, Gosig, that combines crypto-based secret leader selection and multi-round voting in the protocol layer with implementation layer optimizations such as gossip-based message propagation. In particular, Gosig guarantees safety even in a network fully controlled by adversaries, while providing provable liveness with easy-to-achieve network connectivity assumption. On a wide area testbed consisting of 140 Amazon EC2 servers spanning 14 cities on five continents, we show that Gosig can achieve over 4,000 transactions per second with less than 1 minute transaction confirmation time.