In this paper, a novel Byzantine consensus protocol among $n$ players is proposed for the partially synchronous model. In particular, by assuming that standard cryptography is unbreakable, and that $n>\max\bigl(\frac{3}{2}k+3t,2(k+t)\bigr)$, this protocol is an equilibrium where no coalition of $k$ rational players can coordinate to increase their expected utility regardless of the arbitrary behavior of up to $t$ Byzantine players. We show that a baiting strategy is necessary and sufficient to solve this, so-called rational agreement problem. First, we show that it is impossible to solve this rational agreement problem without implementing a baiting strategy, a strategy that rewards rational players for betraying its coalition, by exposing undeniable proofs of fraud. Second, we propose the Huntsman protocol that solves the rational agreement problem by building recent advances in the context of accountable Byzantine agreement in partial synchrony. This protocol finds applications in distributed ledgers where players are incentivized to steal assets by leading other players to a disagreement on two distinct decisions where they ``double spend''.
Sharding can significantly improve the blockchain scalability, by dividing nodes into small groups called shards that can handle transactions in parallel. However, all existing sharding systems adopt complete sharding, i.e., shards are isolated. It raises additional overhead to guarantee the atomicity and consistency of cross-shard transactions and seriously degrades the sharding performance. In this paper, we present Pyramid, the first layered sharding blockchain system, in which some shards can store the full records of multiple shards thus the cross-shard transactions can be processed and validated in these shards internally. When committing cross-shard transactions, to achieve consistency among the related shards, a layered sharding consensus based on the collaboration among several shards is presented. Compared with complete sharding in which each cross-shard transaction is split into multiple sub-transactions and cost multiple consensus rounds to commit, the layered sharding consensus can commit cross-shard transactions in one round. Furthermore, the security, scalability, and performance of layered sharding with different sharding structures are theoretically analyzed. Finally, we implement a prototype for Pyramid and its evaluation results illustrate that compared with the state-of-the-art complete sharding systems, Pyramid can improve the transaction throughput by 2.95 times in a system with 17 shards and 3500 nodes.
In this paper, we propose Tree-chain a fast scalable consensus algorithm that bases the validator selection on an existing function in relatively all existing blockchains: hash function output. Tree-chain is a leader selection consensus algorithm that moves away from a linear blockchain structure, to a tree-structured blockchain where each branch is managed by a particular validator. Each validator is periodically allocated to a random consensus code range which matches specific patterns of the most significant bits of the hash function output. Each validator is then responsible for transactions whose hash falls within the consensus code allocated to the validator. Because transactions are allocated deterministically to validators based on random consensus code allocations, Tree-chain eliminates the significant inefficiency of conventional blockchains for validator selection, such as proof-of work. Tree-chain does not require the validators to follow any additional algorithms before committing blocks which in turn significantly increases its throughput. Implementation results show that Tree-chain can run on small tiny IoT devices with limited resources which in turn highlights its resource efficiency.
Smart contract execution engines are a central part of transaction processing in blockchains. One of the most widely used execution engines is the Ethereum Virtual Machine (EVM). EVM performance is a key determinant of the overall blockchain system. Being able to gather detailed insights into EVM performance characteristics is essential not only when implementing EVMs, but also when designing and dimensioning blockchain-based information systems. Today, there is no precise and easy-to-use solution to gather such information. To address this issue, we introduce EVM-Perf, a high-precision EVM evaluation, and analysis framework. Our framework allows detailed performance analysis of arbitrary EVM implementations. Unlike previous work, it leverages statical analysis methods to achieve higher levels of accuracy. We provide an open-source implementation of EVM-Perf and use it to conduct extensive performance analysis for different physical machines. It comprises both machines with x86_64 as well as ARMv8 instruction set architecture. We discuss how EVM-Perf supports system architects with machine selection as well as configurations of Ethereum deployments, e.g., determining Gas limits or block intervals.
The Algorand consensus protocol, introduced by Chen and Micali in 2016, uses a pure proof-of-stake protocol based on Byzantine agreement rather than the well-known Bitcoin proof-of-work. In this paper, we analyze specific security properties of Algorand related to "unpredictability". The unpredictability property has been initially defined by Boneh et al. in the context of single secret leader election. We show that Algorand satisfies the original unpredictability property. Then, we extend the unpredictability property to a more generic property referred to as "t-forward unpredictability" and show that for a particular setting of Algorand, the t-forward unpredictability property is not satisfied. Specifically, we provide a strategy enabling to predict the future leaders.
Hyperledger Fabric is an enterprise grade permissioned distributed ledger platform that offers modularity for a broad set of industry use cases. One modular component is a pluggable ordering service that establishes consensus on the order of transactions and batches them into blocks. However, as of the time of this writing, there is no production grade Byzantine Fault-Tolerant (BFT) ordering service for Fabric, with the latest version (v2.3) supporting only Crash Fault-Tolerance (CFT).In this work we describe the design and implementation of a BFT ordering service for Fabric, employing a new BFT consensus library. The new library, based on the BFT-SMART protocol and written in Go, is tailored to the blockchain use-case, yet is general enough to cater to a wide variety of other uses. The BFT library's design and integration into Fabric address crucial aspects that were left unsolved in all prior work, making them unfit for production use. We evaluate the new BFT ordering service by comparing it with the currently supported Raft-based CFT ordering service in Hyperledger Fabric.
Distributed ledgers based on Proof-of-Work (PoW) are typically vulnerable when mining participation is low. During these periods, an attacker with a mining majority can mount serious attacks, like double spending or transaction censorship. Our work explores mechanisms to secure a ledger against such adversaries and puts forth the first rigorous study of checkpointing as a protection from 51% attacks. The core idea is to employ an external set of parties to finalize blocks after their creation. This idea takes the form of checkpointing and timestamping, the former ensuring low latency in a federated setting and the latter being fully decentralized. Crucially, we identify and protect against a (previously undocumented) attack, "block lead", thus our scheme is the first to guarantee liveness.
Proof of Staked Hardware Consensus (PoSH) Consensus was designed to achieve Nakamoto-style probabilistic consensus on the contents of a cryptocurrency ledger in a permissionless decentralized network while serving as the foundation of an openly mintable cryptocurrency without winner-takes-all lottery-style block rewards. This demo paper presents a proof of concept implementation of a PoSH consensus blockchain and the technical solutions the implementation introduces to realize PoSH in practice.
David Heath, Yibin Yang, David Devecsery, Vladimir Kolesnikov
We build a complete and efficient ZK toolchain that handles proof statements encoded as arbitrary ANSI C programs.Zero-Knowledge (ZK) proofs are foundational in cryptography. Recent ZK research has focused intensely on non-interactive proofs of small statements, useful in blockchain scenarios. We instead target large statements that are useful, e.g., in proving properties of programs.Recent work (Heath and Kolesnikov, CCS 2020 [HK20a]) designed an efficient proof-of-concept ZK machine (ZKM). Their machine executes arbitrary programs over a minimal instruction set, authenticating in ZK the program execution. In this work, we significantly extend this research thrust, both in terms of efficiency and generality. Our contributions include:• A rich and performance-oriented architecture for representing arbitrary ZK proofs as programs.• A complete compiler toolchain providing full support for ANSI C95 programs. We ran off-the-shelf buggy versions of the Linux programs sed and gzip, proving in ZK that each program has a bug. To our knowledge, this is the first ZK system capable of executing standard Linux programs.• Improved ZK oblivious RAM (ORAM). [HK20a] introduced an efficient ZK-specific ORAM BubbleRAM that consumes O(log2n) communication per access. We extend BubbleRAM with multi-level caching, decreasing communication to O(log n) per access. This introduces the possibility of a cache miss, which we handle cheaply. Our experiments show that cache misses are rare; in isolation, i.e., ignoring other processor costs, BubbleCache improves communication over BubbleRAM by more than 8×. Using BubbleCache improves our processor’s total communication (including costs of cache misses) by ≈ 25-30%.• Numerous low-level optimizations, resulting in a CPU that is both more expressive and ≈ 5.5× faster than [HK20a]’s.• Attention to user experience. Our engineer-facing ZK instrumentation and extensions are minimal and easy to use.Put together, our system is efficient and general, and can run many standard Linux programs. The resultant machine runs at up to 11KHz on a 1Gbps LAN and supports MBs of RAM.
Blockchain has found applications to track ownership of digital assets. Yet, several blockchains were shown vulnerable to network attacks. It is thus crucial for companies to adopt secure blockchains before moving them to production. In this paper, we present Red Belly Blockchain (RBBC), the first secure blockchain whose throughput scales to hundreds of geodistributed consensus participants. To this end, we drastically revisited Byzantine Fault Tolerant (BFT) blockchains through three contributions: (i) defining the Set Byzantine Con-sensus problem of agreeing on a superblock of all proposed blocks instead of a single block; (ii) adopting a fair leaderless design to offer censorship-resistance guaranteeing the commit of correctly requested transactions; (iii) introducing sharded verification to limit the number of signature verifications without hampering security. We evaluate RBBC on up to 1000 VMs of 3 different types, spread across 4 continents, and under attacks. Although its performance is affected by attacks, RBBC scales in that its throughput increases to hundreds of consensus nodes and achieves 30k TPS throughput and 3 second latency on 1000 VMs, hence improving by 3× both the latency and the throughput of its closest competitor.
Jae-Yun Kim, Jun-Mo Lee, Yeon-Jae Koo, Sang-Hyeon Park · 5 authors
Ethereum is a popular account-based blockchain whose number of accounts and transactions has skyrocketed, causing its data explosion. As a result, ordinary clients using PCs or smartphones cannot easily bootstrap as a full node, but rely on other full nodes to verify transactions, thus being exposed to security risks. The most serious overhead is caused by synchronizing the state of all accounts in the block's state trie, which takes several tens of gigabytes. Observing that more than 95% of the accounts are dormant, we propose a novel state optimization technique, named Ethanos. Ethanos downsizes the state trie by periodically emptying it, and then re-build it only with the active accounts used in the period's transactions. Ethanos runs transactions using the accounts available in the current period's state trie as well as those available at the end of the previous period's state trie. For an account in neither of the tries, the account first restores itself by transmitting a restore transaction. One important result of this state management is that a node can now bootstrap only with the latest period's state trie, yet can fully verify all transactions thereafter. We evaluated Ethanos with real Ethereum transactions for 300,000 blocks from the 7.0 million block, with a one-week period of emptying the state trie. Our result shows that Ethanos can sharply reduce the state trie, with only a tiny fraction of the restore transactions. More importantly, unlike the Ethereum state trie which continues to grow as time goes on, the Ethanos state trie size at the end of each period is bounded by a few hundred MB, when there are more than one million, one-week-active accounts.
Consensus protocols are used for the distributed management of large databases in an environment without trust among participants. The choice of a specific protocol depends on the purpose and characteristics of the system itself. The subjects of the paper are consensus protocols in permissioned blockchains. The objective of this paper is to identify functional advantages and disadvantages of observed protocol. The analysis covers a total of six consensus protocols for permissioned blockchains. The following characteristics were compared: security, trust among participants, throughput and scalability. The results show that no protocol shows absolute dominance in all aspects of the comparison. Paxos and Raft are intended for systems in which there is no suspicion of unreliable users, but only the problem of a temporary shutdown. Practical Byzantine Fault Tolerance is intended for systems with a small number of nodes. Federated Byzantine Fault Tolerance shows better scalability and is more suitable for large systems, but can withstand a smaller number of malicious nodes. Proof-of-authority can withstand the largest number of malicious nodes without interfering with the functioning of the system. When choosing a consensus protocol for a blockchain application, one should take into account priority characteristics.
Blockchain is widely used nowadays and it is expected to be more exploited in the near future. Blockchain tends to be more used due to its security layer beyond any active component. Therefore, companies are relying on cutting expenses through converging to the blockchain network and to stop relying on traditional security components due to their high costs and security concerns. The Blockchain technology provides several advantages therefore more applications will be leveraging Distributed Ledger Technologies (DLTs) in the upcoming future. The current work is focused around tackling the use of Blockchain for Cyber Threat Intelligence (CTI) sharing providing a new means to disseminate securely threats data between Security Operations Center (SOC) teams.
Data marketplaces (DMs) promote the benefits of the Internet of Things (IoT) in smart cities. To facilitate the easy exchanges of real-time IoT data streams between device owners and third-party applications, it is required to provide scalable, interoperable, and secured services for large numbers of distributed IoT devices operated by different application vendors. Thanks to decentralization, immutability, and auditability, Blockchain is promising to enable a tamper-proof and trust-free framework to enhance performance and security issues in centralized DMs. However, directly integrating blockchains into large-scale IoT-based DMs still faces many limitations, such as high resource and energy demands, low transaction throughput, poor scalability, and challenges in privacy preservation. This paper introduces a novel Federated Ledgers-based Framework for Hierarchical Decentralized Data Marketplaces (Fed-DDM). In Fed-DDM, participants are divided into multiple permissioned domains given their registrations. Each domain leverages an efficient Byzantine Fault Tolerance (BFT) consensus protocol to commit transactions of a domain on a private intra-ledger. A public inter-ledger network adopts a scalable Proof-of-Work (PoW) consensus protocol to federate multiple private intra-ledger networks. We design a smart contract-enabled inter-ledger protocol to guarantee the security of the cross-domain operations on a public federated ledger without exposing sensitive privacy information from private ledgers. A proof-of-concept prototype is implemented, and the experimental results verify the feasibility of the proposed Fed-DDM solution with performance and security guarantees.
Blockchain is a distributed database shared among disparate parties. It promises to enable new applications and solutions to wide-ranging domains. However, today's blockchains suffer from low throughput and high latency. This impedes widespread adoption of more complex blockchain-based applications. We propose a new direction for the future development of blockchains: pushing utmost work to client-side to make the blockchain-core as simple as possible. To show the feasibility and practicability of this idea, we construct both client-assisted consensus and client-assisted smart contracts. The client-assisted consensus only requires a single round-trip between clients and blockchain nodes; it is leaderless and parallelizable. Our experimental results show that it can process thousands of transactions per second when the number of replicas is 400. The client-assisted smart contract pushes the expensive execution to client-side and ensures the correctness by verifiable computation. It avoids duplicated execution, allows parallel execution and reduces transaction/blockchain sizes.
There are few topics out there, that seem to create as much confusion and discussion as blockchains. This has a multitude of reasons: (1) A large number of drastically different concepts and systems are unified under the very broad term "blockchain". (2) The topic touches a variety of different fields, including databases, distributed processing, networks, cryptography, and even economics. (3) There exists a large number of different applications of the technology.The goal of this paper is to simplify and structure the discussion of blockchain technology. We first introduce a simple formalization of the basic components, that appear again and again in a variety of blockchain systems. Second, we formalize four important execution models, that express the workflow of a large number of blockchain systems. Third, along the way, the we also discuss certain misconceptions, that constantly reappear in discussions. We believe that a common formalization of the transaction processing behavior of blockchain systems both helps beginners to get into the topic as well as can bring experts from different fields to a common denominator when discussing blockchain systems.
Yongjie Bai, Zhi Yang, Hui Li, Han Wang · 6 authors
Blockchain is an emerging distributed storage technology in recent years. It can hold all historical data, transaction records, and other related information from the past by using a self-referencing blockchain data storage structure. Consensus is the core technology of blockchain, which ensures consistency of data of different nodes and also enables the blockchain to have Byzantine fault tolerance. However, most consensus algorithms are serialized. With the increase in the number of nodes, throughput of system decreases rapidly. Proof of Vote (PoV) is an efficient voting-based consensus algorithm. It separates the voting and bookkeeping rights and has a great traffic complexity of . Based on PoV, we propose a more efficient and practical consensus algorithm called Parallel Proof of Vote (PPoV), which allows multiple nodes to generate blocks in parallel within a consensus cycle. Analysis and experiments show that the performance of PPoV is 2-5 times higher than typical BFT consensus as the number of nodes in range of 4-100.
Proof of Stake (PoS) has been talked about extensively as an alternative way of reaching consensus in blockchain systems. However, there are few publications on how PoS can be used to create new blocks in detail. The undisputed lead proponent for PoS is Ethereum. However, virtually all discussions regarding PoS for Ethereum are centered on selecting a block using PoS after one or more candidate blocks have already been somehow created. PeerCoin was the first blockchain system that incorporated PoS in block creation. Unfortunately, there is no known documentation on how PoS works in PeerCoin. In this paper, we fill this gap by presenting a detailed explanation of the PeerCoin PoS algorithm based on PeerCoin source code. We also dispel the misconception that PeerCoin PoS is based on Proof of Work (PoW) and hence would consume a lot of energy just like proof of work (PoW). In fact, it resembles PoW only on surface and differs from PoW substantially in terms of how to meet the difficulty target.
The exploitation of smart-contract vulnerabilities can lead to catastrophic losses. Formal verification can be a useful tool in identifying these vulnerabilities before deployment. We present an encoding of Solidity and the Ethereum blockchain using Boogie, an intermediate verification language. Based on this formalisation, we create Solidifier: a bounded model checker for Solidity. Distinctive features of our encoding are precisely capturing Solidity's unorthodox memory model, a notion of lazy blockchain exploration, and memory-precise verification harnesses. Unlike much of the work in this area, our modus operandi is not matching contracts against specific known behavioural patterns that might lead to vulnerabilities. Rather, we provide a tool to find errors/bad states - be they vulnerabilities or not - that might be reached through behaviours that might not follow such a pattern.
Access control management in a collaborative environment composed of a multitude of distributed autonomous organizations is a challenging task. To answer the challenge, in this paper we propose a novel approach that incorporates semantic technologies in the Attribute-Based Access Control (ABAC) approach. Building on the basic principles of ABAC, our approach allows for a highly expressive modeling of the context in which access decisions are made, by providing mechanisms to describe rich relationships among entities, which can evolve over time. In addition, our system works in a truly decentralized manner, which makes it suitable for geographically distributed enterprise systems. We show the feasibility in practice of our approach through some experimental results.
Vicent Cholvi, Antonio Fernández Anta, Chryssis Georgiou, Nicolas Nicolaou · 6 authors
In order to formalize Distributed Ledger Technologies and their interconnections, recent research has introduced the concept of a Distributed Ledger Object (denoted $$\mathcal {O}^L$$ ), a concurrent abstraction that maintains a totally ordered sequence of records, capturing the essence of blockchains and distributed ledgers. In this work, we introduce the Distributed Grow-only Set object (denoted $$\mathcal {O}^{GS}$$ ), a novel abstraction that, unlike the $$\mathcal {O}^L$$ , maintains an immutable set of records by supporting only Add and Get operations. This object is inspired by the Grow-only Set (G-Set) a well-known Conflict-free Replicated Data Type (CRDT). We formally define the $$\mathcal {O}^{GS}$$ and present a Byzantine-tolerant, consensus-free implementation (denoted as $$\mathcal {O}^{GS}_B$$ ) that ensures eventual consistency. Building on this implementation, we propose consensus-free algorithmic solutions to two fundamental problems: the Atomic Appends problem, which concerns atomically appending multiple records to distinct ledgers, and the Atomic Adds problem, its counterpart in the context of G-Sets. Additionally, we show how the $$\mathcal {O}^{GS}_B$$ can be leveraged to construct a consensus-free, Single-Writer Byzantine-tolerant $$\mathcal {O}^L$$ . We argue that the applicability of the $$\mathcal {O}^{GS}_B$$ extends well beyond these specific use cases, offering a lightweight and efficient foundation for a variety of distributed applications.
Vicent Cholvi, Antonio Fernández Anta, Chryssis Georgiou, Nicolas Nicolaou · 6 authors
In order to formalize Distributed Ledger Technologies and their\ninterconnections, a recent line of research work has formulated the notion of\nDistributed Ledger Object (DLO), which is a concurrent object that maintains a\ntotally ordered sequence of records, abstracting blockchains and distributed\nledgers. Through DLO, the Atomic Appends problem, intended as the need of a\nprimitive able to append multiple records to distinct ledgers in an atomic way,\nis studied as a basic interconnection problem among ledgers.\n In this work, we propose the Distributed Grow-only Set object (DSO), which\ninstead of maintaining a sequence of records, as in a DLO, maintains a set of\nrecords in an immutable way: only Add and Get operations are provided. This\nobject is inspired by the Grow-only Set (G-Set) data type which is part of the\nConflict-free Replicated Data Types. We formally specify the object and we\nprovide a consensus-free Byzantine-tolerant implementation that guarantees\neventual consistency. We then use our Byzantine-tolerant DSO (BDSO)\nimplementation to provide consensus-free algorithmic solutions to the Atomic\nAppends and Atomic Adds (the analogous problem of atomic appends applied on\nG-Sets) problems, as well as to construct consensus-free Single-Writer BDLOs.\nWe believe that the BDSO has applications beyond the above-mentioned problems.\n
Henrik Nellemose Knudsen, Jakob Svennevik Notland, Peter Halland Haro, Truls Bakkejord Ræder · 5 authors
Blockchain technologies originate from cryptocurrencies. Thus, most blockchain technologies assume an environment with a fast and stable network. However, in some blockchain-based systems, e.g., supply chain management (SCM) systems, some Internet of Things (IoT) nodes can only rely on the low-quality network sometimes to achieve consensus. Thus, it is critical to understand the applicability of existing consensus algorithms in such environments. We performed a systematic mapping study to evaluate and compare existing consensus mechanisms’ capability to provide integrity and security with varying network properties. Our study identified 25 state-of-the-art consensus algorithms from published and preprint literature. We categorized and compared the consensus algorithms qualitatively based on established performance and integrity metrics and well-known blockchain security issues. Results show that consensus algorithms that rely on synchronous network for correctness cannot provide the expected integrity. Such consensus algorithms may also be vulnerable to distributed-denial-of-service (DDOS) and routing attacks, given limited network throughput. Conversely, asynchronous consensus algorithms, e.g., Honey-BadgerBFT, are deemed more robust against many of these attacks and may provide high integrity in asynchronous events.