While many researchers adopt a sharding approach to design scaling blockchains, few works have studied the transaction placement problem incurred by sharding protocols. The widely-used hashing placement algorithm renders an overwhelming portion of transactions as cross-shard. In this paper, we analyze the high cost of cross-shard transactions and reveal that most Bitcoin transactions have simple dependencies and can become single-shard under a placement algorithm taking transaction dependencies into account. In addition, we perform a case study of OptChain, which is the state-of-the-art transaction placement algorithm for sharded blockchains, and find a shortcoming of it. A simple fix is proposed, and our evaluation results demonstrate that the proposed fix effectively helps OptChain overcome the shortcoming and significantly improve the system performance under a special workload. The authors of OptChain made some revisions to the algorithm description after noticing our work. Their updated algorithm does not exhibit the shortcoming under the workloads employed by this paper.
Vishal Sharma, Zengpeng Li, Paweł Szałachowski, Teik Guan Tan · 5 authors
Decentralized control, low-complexity, flexible and efficient communications are the requirements of an architecture that aims to scale blockchains beyond the current state. Such properties are attainable by reducing ledger size and providing parallel operations in the blockchain. Sharding is one of the approaches that lower the burden of the nodes and enhance performance. However, the current solutions lack the features for resolving concurrency during cross-shard communications. With multiple participants belonging to different shards, handling concurrent operations is essential for optimal sharding. This issue becomes prominent due to the lack of architectural support and requires additional consensus for cross-shard communications. Relying on the advantages of hybrid Proof-of-Work/Proof-of-Stake (PoW/PoS), like Ethereum , hybrid consensus and 2-hop blockchain , we propose Reinshard , a new blockchain that inherits the properties of hybrid consensus for optimal sharding. Reinshard uses PoW and PoS chain-pairs with PoS sub-chains for all the valid chain-pairs where the hybrid consensus is attained through Verifiable Delay Function (VDF). Our architecture provides a secure method of arranging nodes in shards and resolves concurrency conflicts using the delay factor of VDF. The applicability of Reinshard is demonstrated through security and experimental evaluations. A practical concurrency problem is considered to show the efficacy of Reinshard in providing optimal sharding.
Blockchain protocols come with a variety of security guarantees. For example, BFT-inspired protocols such as Algorand tend to be secure in the partially synchronous setting, while longest chain protocols like Bitcoin will normally require stronger synchronicity to be secure. Another fundamental distinction, directly relevant to scalability solutions such as sharding, is whether or not a single untrusted user is able to point to *certificates*, which provide incontrovertible proof of block confirmation. Algorand produces such certificates, while Bitcoin does not. Are these properties accidental? Or are they inherent consequences of the paradigm of protocol design? Our aim in this paper is to understand what, fundamentally, governs the nature of security for permissionless blockchain protocols. Using the framework developed in (Lewis-Pye and Roughgarden, 2021), we prove general results showing that these questions relate directly to properties of the user selection process, i.e., the method (such as proof-of-work or proof-of-stake) which is used to select users with the task of updating state. Our results suffice to establish, for example, that the production of certificates is impossible for proof-of-work protocols, but is automatic for standard forms of proof-of-stake protocols. As a byproduct of our work, we also define a number of security notions and identify the equivalences and inequivalences among them.
Thomas Jakobsche, Nicolas Lachiche, Aurélien Cavelan, Florina M. Ciorba
Applications running on HPC systems waste time and energy if they: (a) use resources inefficiently, (b) deviate from allocation purpose (e.g. cryptocurrency mining), or (c) encounter errors and failures. It is important to know which applications are running on the system, how they use the system, and whether they have been executed before. To recognize known applications during execution on a noisy system, we draw inspiration from the way Shazam recognizes known songs playing in a crowded bar. Our contribution is an Execution Fingerprint Dictionary (EFD) that stores execution fingerprints of system metrics (keys) linked to application and input size information (values) as key-value pairs for application recognition. Related work often relies on extensive system monitoring (many system metrics collected over large time windows) and employs machine learning methods to identify applications. Our solution only uses the first 2 minutes and a single system metric to achieve F-scores above 95 percent, providing comparable results to related work but with a fraction of the necessary data and a straightforward mechanism of recognition.
Sep 9, 2021·(2021, August). Application of Blockchain Technology for Educational Platform. In International Conference on Human Interaction and Emerging Technologies (pp. 1283-1287). Springer, Cham
Matija Šipek, Martin Žagar, Branko Mihaljević, Nikola Drašković
Nowadays, huge amounts of data are generated every second, and a quantity of that data can be defined as sensitive. Blockchain technology has private, secure, transparent and decentralized exchange of data as native. It is adaptable and can be used in a wide range of Internet-based interactive systems in academic and industrial settings. The essential part of programmable distributed ledgers such as Ethereum, Polkadot, Cardano and other Web 3.0 technologies are smart contracts. Smart contracts are programs executed on the global blockchain, the code is public as well as all of the data managed within the transactions, thus creating a system that is reliable and cannot be cheated if designed properly. In this paper, in order to make the educational system more transparent and versatile we will describe an educational learning platform designed as a distributed system.
Moritz Platt, Johannes Sedlmeir, Daniel Platt, Jiahua Xu · 7 authors
Popular permissionless distributed ledger technology (DLT) systems using proof-of-work (PoW) for Sybil attack resistance have extreme energy requirements, drawing stern criticism from academia, business and the media. DLT systems building on alternative consensus mechanisms, particularly proof-of-stake (PoS), aim to address this downside. In this paper, we take an initial step towards comparing the energy requirements of such systems to understand whether they achieve this goal equally well. While multiple studies have analysed the energy demands of individual blockchains, little comparative work has been done. We approach this research gap by formalising a basic consumption model for PoS blockchains. Applying this model to six archetypal blockchains generates three main findings. First, we confirm the concerns around the energy footprint of PoW by showing that Bitcoin's energy consumption exceeds the energy consumption of all PoS-based systems analysed by at least three orders of magnitude. Second, we illustrate that there are significant differences in energy consumption among the PoS-based systems analysed, with permissionless systems having a larger energy footprint overall owing to their higher replication factor. Third, we point out that the type of hardware that validators use has a considerable impact on whether the energy consumption of PoS blockchains is comparable with or considerably larger than that of centralised systems.
Selma Steinhoff, Chrysoula Stathakopoulou, Matej Pavlovič, Marko Vukolić
Reconfiguration of long-lived blockchain and Byzantine fault-tolerant (BFT) systems poses fundamental security challenges. In case of state-of-the-art Proof-of-Stake (PoS) blockchains, stake reconfiguration enables so-called long-range attacks, which can lead to forks. Similarly, permissioned blockchain systems, typically based on BFT, reconfigure internally, which makes them susceptible to a similar "I still work here" attack. In this work, we propose BMS (Blockchain/BFT Membership Service) offering a secure and dynamic reconfiguration service for BFT and blockchain systems, preventing long-range and similar attacks. In particular: (1) we propose a root BMS for permissioned blockchains, implemented as an Ethereum smart contract and evaluate it reconfiguring the recently proposed Mir-BFT protocol, (2) we discuss how our BMS extends to PoS blockchains and how it can reduce PoS stake unbonding time from weeks/months to the order of minutes, and (3) we discuss possible extensions of BMS to hierarchical deployments as well as to multiple root BMSs.
A verifiable random function (VRF in short) is a powerful pseudo-random function that provides a non-interactively public verifiable proof for the correctness of its output. Recently, VRFs have found essential applications in blockchain design, such as random beacons and proof-of-stake consensus protocols. To our knowledge, the first generation of blockchain systems used inherently inefficient proof-of-work consensuses, and the research community tried to achieve the same properties by proposing proof-of-stake schemes where resource-intensive proof-of-work is emulated by cryptographic constructions. Unfortunately, those most discussed proof-of-stake consensuses (e.g., Algorand and Ouroborous family) are not future-proof because the building blocks are secure only under the classical hard assumptions; in particular, their designs ignore the advent of quantum computing and its implications. In this paper, we propose a generic compiler to obtain the post-quantum VRF from the simple VRF solution using symmetric-key primitives (e.g., non-interactive zero-knowledge system) with an intrinsic property of quantum-secure. Our novel solution is realized via two efficient zero-knowledge systems ZKBoo and ZKB++, respectively, to validate the compiler correctness. Our proof-of-concept implementation indicates that even today, the overheads introduced by our solution are acceptable in real-world deployments. We also demonstrate potential applications of a quantum-secure VRF, such as quantum-secure decentralized random beacon and lottery-based proof of stake consensus blockchain protocol.
Martin Perešíni, Federico Matteo Benčić, Kamil Malinka, Ivan Homoliak
In response to the bottleneck of processing throughput inherent to single chain PoW blockchains, several proposals have substituted a single chain for Directed Acyclic Graphs (DAGs). In this work, we investigate two notable DAG-oriented designs. We focus on PHANTOM (and its optimization GHOSTDAG), which proposes a custom transaction selection strategy that enables to increase the throughput of the network. However, the related work lacks a thorough investigation of corner cases that deviate from the protocol in terms of transaction selection strategy. Therefore, we build a custom simulator that extends open source simulation tools to support multiple chains and enables us to investigate such corner cases. Our experiments show that malicious actors who diverge from the proposed transaction selection strategy make more profit as compared to honest miners. Moreover, they have a detrimental effect on the processing throughput of the PHANTOM (and GHOSTDAG) due to same transactions being included in more than one block of different chains. Finally, we show that multiple miners not following the transaction selection strategy are incentivized to create a shared mining pool instead of mining independently, which has a negative impact on decentralization.
Nicolas T. Courtois, Kacper T. Gradon, Klaus Schmeh
This paper provides an overview of how crypto currency and blockchain engineering interacts with the law enforcement. We point out that a large proportion of crypto users are amateur investors and the dominant and the largest segment in crypto crime are simply investment scams (!). We look at various questions of criminal use and misuse of technology, especially in the areas of money laundering or cashing out the profits originating from illicit activities. The aim of the paper is to raise a set of concerns arising in the criminal justice and policing circles, based on the interviews with law enforcement practitioners, and to see how cryptos could be reconciled with public security and safety. We propose a simplified classification of crimes related to crypto currency. We study the development of blockchains in a broader context of applied cryptography and payment technology. Ransomware is a big threat but we also need protection against corporate misconduct or negligence, with untested financial services breaching customer trust or government regulations. Not paying taxes is illegal, but there is more at stake: exposing crypto holders to losing all their savings in scams or thefts. Interestingly, privacy helps to defend on multiple fronts: against social engineering, targeted crime, scams, and also against cybersecurity thefts and hacks.
Blockchain is a type of decentralized distributed network which acts as an immutable digital ledger. Despite the absence of any central governing authority to validate the blocks in the ledger, it is considered secure and immutable due to the consensus protocol among various nodes of the network. A consensus algorithm is a mechanism that guarantees the reliability of the blockchain and helps all connected nodes or peers to reach common ground regarding the present state of the blockchain network thus an ideal consensus algorithm must be secure, reliable, and fast. There are several different algorithms to reach a consensus among the nodes thus this article seeks to test the practicality of Proof of Authority in the blockchain network as a consensus algorithm and its comparison with current mainstream consensus algorithms.
Nakamoto's seminal work gave rise to permissionless blockchains -- as well as a wide range of proposals to mitigate their performance shortcomings. Despite substantial throughput and energy efficiency achievements, most proposals only bring modest (or marginal) gains in transaction commit latency. Consequently, commit latencies in today's permissionless blockchain landscape remain prohibitively high. This paper proposes NimbleChain, a novel algorithm that extends permissionless blockchains based on Nakamoto consensus with a fast path that delivers causal promises of commitment, or simply promises. Since promises only partially order transactions, their latency is only a small fraction of the totally-ordered commitment latency of Nakamoto consensus. Still, the weak consistency guarantees of promises are strong enough to correctly implement cryptocurrencies. To the best of our knowledge, NimbleChain is the first system to bring together fast, partially-ordered transactions with consensus-based, totally-ordered transactions in a permissionless setting. This hybrid consistency model is able to speed up cryptocurrency transactions while still supporting smart contracts, which typically have (strong) sequential consistency needs. We implement NimbleChain as an extension of Ethereum and evaluate it in a 500-node geo-distributed deployment. The results show NimbleChain can promise a cryptocurrency transactions up to an order of magnitude faster than a vanilla Ethereum implementation, with marginal overheads.
Andrea Flamini, Riccardo Longo, Alessio Meneghetti
In this paper we extend the \emph{Multidimensional Byzantine Agreement (MBA) Protocol}, a {leaderless} Byzantine agreement for lists of arbitrary values, into a protocol suitable for wide gossiping networks: \emph{Cob}. This generalization allows the consensus process to be run by an incomplete network of nodes provided with (non-synchronized) same-speed clocks. Not all nodes are active in every step, so the network size does not hamper the efficiency, as long as the gossiping broadcast delivers the messages to every node in reasonable time. These network assumptions model more closely real-life communication channels, so the Cob protocol may be applicable to a variety of practical problems, such as blockchain platforms implementing sharding. Cob has the same Bernoulli-like distribution that upper-bounds the number of steps as the MBA protocol. We prove its correctness and security assuming a supermajority of honest nodes in the network, and compare its performance with Algorand.
Nakamoto consensus underlies the security of many of the world's largest cryptocurrencies, such as Bitcoin and Ethereum. Common lore is that Nakamoto consensus only achieves consistency and liveness under a regime where the difficulty of its underlying mining puzzle is very high, negatively impacting overall throughput and latency. In this work, we study Nakamoto consensus under a wide range of puzzle difficulties, including very easy puzzles. We first analyze an adversary-free setting and show that, surprisingly, the common prefix of the blockchain grows quickly even with easy puzzles. In a setting with adversaries, we provide a small backwards-compatible change to Nakamoto consensus to achieve consistency and liveness with easy puzzles. Our insight relies on a careful choice of \emph{symmetry-breaking strategy}, which was significantly underestimated in prior work. We introduce a new method -- \emph{coalescing random walks} -- to analyzing the correctness of Nakamoto consensus under the uniformly-at-random symmetry-breaking strategy. This method is more powerful than existing analysis methods that focus on bounding the number of {\it convergence opportunities}.
Caciano dos Santos Machado, Renan R. S. dos Santos, Carla Merkle Westphall
Community networks are prone to free-riders, i.e., participants who take advantage of cooperation from others' routers but do not contribute reciprocally. In this paper, we present HARPIA, a system for credit-based incentive mechanisms for data forwarding in community networks aimed to prevent selfish behavior. HARPIA does not require a trusted third-party or tamper-resistant security modules as in other incentive mechanisms. Instead, it uses a distributed accounting scheme (DPIFA) to estimate the balance of data forwarding contribution and consumption of each network router and settle correspondent cryptocurrency debts on an Ethereum smart contract. On-chain settlement transactions are performed every HARPIA cycle (e.g., daily, weekly, monthly) and must be validated by at least m-of-n network routers using a multi-signature scheme (MuSig). We also realized a performance evaluation, security threat assessment, and cryptocurrency costs estimation. Results show that our proposal is suitable for community networks with up to 64 infrastructure routers under specific m-of-n MuSig thresholds.
In order to have transactions executed and recorded on blockchains such as the Ethereum Mainnet, fees expressed in crypto-currency units of the blockchain must be paid. One can buy crypto-currency called Ether of the Ethereum blockchain from exchanges and pay for the transaction fees. In the case of test networks (such as Rinkeby) or scientific research blockchains (such as Bloxberg), free crypto-currency, Ether, is distributed to users via faucets. Since transaction slots on the blocks, storage and smart contract executions are consuming blockchain resources, Ethers are distributed by fixed small amounts to users. Users may have different amount of Ether requirements; some small amounts and some large amounts during different times. As a result, rather than allowing the user to get a fixed small amount of Ether, a more general distribution mechanism that allows a user to demand and claim arbitrary amounts of Ether, while satisfying fairness among users, is needed. For this end, Max-min Fairness based schemes have been used in centralized settings. Our work contributes a Max-min Fairness based algorithm and its Solidity smart contract implementation that requires low transaction costs independent of the number of users. This is important on the Ethereum blockchain, since a smart contract execution with transaction costs depending on the number of users would mean block gas limit exhaustion problem will eventually be met, making the smart contract ineffective. We report tests which confirm that the low transaction cost aims have been achieved by our algorithm.
Aug 19, 2021·2021 IEEE Intl Conf on Dependable, Autonomic and Secure Computing, Intl Conf on Pervasive Intelligence and Computing, Intl Conf on Cloud and Big Data Computing, Intl Conf on Cyber Science and Technology Congress (DASC/PiCom/CBDCom/CyberSciTech)
Shiv Sondhi, Sherif Saad, Kevin Shi, Mohammad Abdullah Al Mamun · 5 authors
A critical component of any blockchain or distributed ledger technology (DLT) platform is the consensus algorithm. Blockchain consensus algorithms are the primary vehicle for the nodes within a blockchain network to reach an agreement. In recent years, many blockchain consensus algorithms have been proposed mainly for private and permissioned blockchain networks. However, the performance of these algorithms and their reliability in hostile environments or the presence of byzantine and other network failures are not well understood. In addition, the testing and validation of blockchain applications come with many technical challenges. In this paper, we apply chaos engineering and testing to understand the performance of consensus algorithms in the presence of different loads, byzantine failure and other communication failure scenarios. We apply chaos engineering to evaluate the performance of three different consensus algorithms (PBFT, Clique, Raft) and their respective blockchain platforms. We measure the blockchain network's throughput, latency, and success rate while executing chaos and load tests. We develop lightweight blockchain applications to execute our test in a semi-production environment. Our results show that using chaos engineering helps understand how different consensus algorithms perform in a hostile or unreliable environment and the limitations of blockchain platforms. Our work demonstrates the benefits of using chaos engineering in testing complex distributed systems such as blockchain networks.
Andreas Rumsch, Christoph Imboden, Alberto Calatroni, Martin Camenzind · 6 authors
More and more household appliances connect to the Internet and exchange data freely. This is the foundation for true smart buildings. However, there is still no uniform communication technology available, which can connect all appliances from all vendors. Protocols differ between manufacturers making interoperability difficult or even impossible. Manufacturers cannot rely on a reference for the implementation and real estate developers and operators are reluctant to commit to a system until it is clear which one will prevail. A similar situation is evident in smart grids and applies equally to the energy supply industry. This fragmentation ultimately leads to missed opportunities in terms of business models which could connect customers with service providers. We present a first draft of an architecture: SINA - Smart Interoperability Architecture. SINA is based on existing decentralized infrastructure, which avoids creating a dependency of the market participants on an overpowering service provider. The core element of the technical solution is an open-source module integrated in the private clouds of the manufacturers, energy suppliers and service providers. The architecture addresses problems of data ownership, privacy and data security avoiding central administrative structures. It manages data access and transfer in a decentralized and distributed system. SINA uses a blockchain and smart contracts to make sure that the pieces of information about which data are accessed, by whom they are accessed, how they are processed, and which monetary transactions take place are immutably stored and made available. This allows providers to offer services to users in a transparent and trustworthy manner. Finally, SINA includes a matchmaking block which helps service providers find potential customers and vice versa. This set of features makes SINA unique.
Verifiable delay functions have found a lot of applications in blockchain technology in recent times. Continuous verifiable delay functions are an improvement over the basic notion of VDFs with recursive capabilities. We are proposing the application of VDF for constructing more space time-efficient provers and simulators required for the iterative non-interactive zero-knowledge systems.
Max Mathys, Roland Schmid, Jakub Sliwinski, Roger Wattenhofer
We present Accept, a simple, asynchronous transaction system that achieves perfect horizontal scaling. Usual blockchain-based transaction systems come with a fundamental throughput limitation as they require that all (potentially unrelated) transactions must be totally ordered. Such solutions thus require serious compromises or are outright unsuitable for large-scale applications, such as global retail payments. Accept provides efficient horizontal scaling without any limitation. To that end, Accept satisfies a relaxed form of consensus and does not establish an ordering of unrelated transactions. Furthermore, Accept achieves instant finality and does not depend on a source of randomness.
Abstract The number of users approaching the world of cryptocurrencies exploded in the last years, and consequently the daily interactions on their underlying distributed ledgers have intensified. In this paper, we analyze the flow of these digital transactions in a certain period of time, trying to discover important insights on the typical use of these technologies by studying, through complex network theory, the patterns of interactions in four prominent and different Distributed Ledger Technologies (DLTs), namely Bitcoin, DogeCoin, Ethereum, Ripple. In particular, we describe the Distributed Ledger Network Analyzer (DiLeNA), a software tool for the investigation of the transactions network recorded in DLTs. We show that studying the network characteristics and peculiarities is of paramount importance, in order to understand how users interact in the DLT. For instance, our analyses reveal that all transaction graphs exhibit small world properties.
Quan Nguyen, André Cronje, Michael Kong, Egor Lysenko · 5 authors
This paper consolidates the core technologies and key concepts of our novel Lachesis consensus protocol and Fantom Opera platform, which is permissionless, leaderless and EVM compatible. We introduce our new protocol, so-called Lachesis, for distributed networks achieving Byzantine fault tolerance (BFT)~\cite{lachesis01}. Each node in Lachesis protocol operates on a local block DAG, namely \emph{OPERA DAG}. Aiming for a low time to finality (TTF) for transactions, our general model considers DAG streams of high speed but asynchronous events. We integrate Proof-of-Stake (PoS) into a DAG model in Lachesis protocol to improve performance and security. Our general model of trustless system leverages participants' stake as their validating power~\cite{stakedag}. Lachesis's consensus algorithm uses Lamport timestamps, graph layering and concurrent common knowledge to guarantee a consistent total ordering of event blocks and transactions. In addition, Lachesis protocol allows dynamic participation of new nodes into Opera network. Lachesis optimizes DAG storage and processing time by splitting local history into checkpoints (so-called epochs). We also propose a model to improve stake decentralization, and network safety and liveness ~\cite{stairdag}. Built on our novel Lachesis protocol, Fantom's Opera platform is a public, leaderless, asynchronous BFT, layer-1 blockchain, with guaranteed deterministic finality. Hence, Lachesis protocol is suitable for distributed ledgers by leveraging asynchronous partially ordered sets with logical time ordering instead of blockchains. We also present our proofs into a model that can be applied to abstract asynchronous distributed system.
Fault tolerance of a blockchain is often characterized by the fraction $f$ of "adversarial power" that it can tolerate in the system. Despite the fast progress in blockchain designs in recent years, existing blockchain systems can still only tolerate $f$ below $0.5$. Can practically usable blockchains tolerate a malicious majority, i.e., $f$ above $0.5$? This work presents a positive answer to this question. We first note that the well-known impossibility of {\em byzantine consensus} for $f$ above $0.5$ does not carry over to blockchains. To tolerate $f$ above $0.5$, we use {\em byzantine broadcast}, instead of byzantine consensus, as the core of the blockchain. A major obstacle in doing so, however, is that the resulting blockchain may have extremely low throughput. To overcome this central technical challenge, we propose a novel byzantine broadcast protocol OverlayBB, that can tolerate $f$ above $0.5$ while achieving good throughput. Using OverlayBB as the core, we present the design, implementation, and evaluation of a novel Proof-of-Stake blockchain called BCube. BCube can tolerate a malicious majority, while achieving practically usable transaction throughput and confirmation latency in our experiments with $10000$ nodes and under $f = 0.7$. To our knowledge, BCube is the first blockchain that can achieve such properties.
The recent surge in federated data management applications has brought forth concerns about the security of underlying data and the consistency of replicas in the presence of malicious attacks. A prominent solution in this direction is to employ a permissioned blockchain framework that is modeled around traditional Byzantine Fault-Tolerant (BFT) consensus protocols. Any federated application expects its data to be globally scattered to achieve faster access. But, prior works have shown that traditional BFT protocols are slow. This has led to the rise of sharded-replicated blockchains. Existing BFT protocols for these sharded blockchains are efficient if client transactions require access to a single-shard, but face performance degradation if there is a cross-shard transaction that requires access to multiple shards. As cross-shard transactions are common, to resolve this dilemma, we present RingBFT, a novel meta-BFT protocol for sharded blockchains. RingBFT requires shards to adhere to the ring order, and follow the principle of process, forward, and re-transmit while ensuring the communication between shards is linear. Our evaluation of RingBFT against state-of-the-art sharding BFT protocols illustrates that RingBFT achieves up to 18x higher throughput, gracefully scales to nearly 500 globally distributed nodes, and achieves a peak throughput of 1.2 million transactions per second.