Lăcrămioara Aştefanoaei, Pierre Chambart, Antonella Del Pozzo, Thibault Rieutord · 6 authors
First-generation blockchains provide probabilistic finality: a block can be revoked, albeit the probability decreases as the block sinks deeper into the chain. Recent proposals revisited committee-based BFT consensus to provide deterministic finality: as soon as a block is validated, it is never revoked. A distinguishing characteristic of these second-generation blockchains over classical BFT protocols is that committees change over time as the participation and the blockchain state evolve. In this paper, we push forward in this direction by proposing a formalization of the Dynamic Repeated Consensus problem and by providing generic procedures to solve it in the context of blockchains. Our approach is modular in that one can plug in different synchronizers and single-shot consensus instances. To offer a complete solution, we provide a concrete instantiation, called Tenderbake, and present a blockchain synchronizer and a single-shot consensus algorithm, working in a Byzantine and partially synchronous system model with eventually synchronous clocks. In contrast to recent proposals, our methodology is driven by the need to bound the message buffers. This is essential in preventing spamming and run-time memory errors. Moreover, Tenderbake processes can synchronize with each other without exchanging messages, leveraging instead the information stored in the blockchain.
Lăcrămioara Aştefănoaei, Pierre Chambart, Antonella Del Pozzo, Thibault Rieutord · 6 authors
First-generation blockchains provide probabilistic finality: a block can be revoked, albeit the probability decreases as the block "sinks" deeper into the chain. Recent proposals revisited committee-based BFT consensus to provide deterministic finality: as soon as a block is validated, it is never revoked. A distinguishing characteristic of these second-generation blockchains over classical BFT protocols is that committees change over time as the participation and the blockchain state evolve. In this paper, we push forward in this direction by proposing a formalization of the Dynamic Repeated Consensus problem and by providing generic procedures to solve it in the context of blockchains. Our approach is modular in that one can plug in different synchronizers and single-shot consensus. To offer a complete solution, we provide a concrete instantiation, called {{Tenderbake}}, and present a blockchain synchronizer and a single-shot consensus algorithm, working in a Byzantine and partially synchronous system model with eventually synchronous clocks. In contrast to recent proposals, our methodology is driven by the need to bound the message buffers. This is essential in preventing spamming and run-time memory errors. Moreover, {{Tenderbake}} processes can synchronize with each other without exchanging messages, leveraging instead the information stored in the blockchain.
Andrei Lihu, Jincheng Du, Igor Barjaktarević, Patrick Gerzanics · 5 authors
Bitcoin mining is a wasteful and resource-intensive process. To add a block of transactions to the blockchain, miners spend a considerable amount of energy. The Bitcoin protocol, named 'proof of work' (PoW), resembles a lottery and the underlying computational work is not useful otherwise. In this paper, we describe a novel 'proof of useful work' (PoUW) protocol based on training a machine learning model on the blockchain. Miners get a chance to create new coins after performing honest ML training work. Clients submit tasks and pay all training contributors. This is an extra incentive to participate in the network because the system does not rely only on the lottery procedure. Using our consensus protocol, interested parties can order, complete, and verify useful work in a distributed environment. We outline mechanisms to reward useful work and punish malicious actors. We aim to build better AI systems using the security of the blockchain.
The growing size of modern datasets necessitates splitting a large scale computation into smaller computations and operate in a distributed manner. Adversaries in a distributed system deliberately send erroneous data in order to affect the computation for their benefit. Boolean functions are the key components of many applications, e.g., verification functions in blockchain systems and design of cryptographic algorithms. We consider the problem of computing a Boolean function in a distributed computing system with particular focus on \emph{security against Byzantine workers}. Any Boolean function can be modeled as a multivariate polynomial with high degree in general. However, the security threshold (i.e., the maximum number of adversarial workers can be tolerated such that the correct results can be obtained) provided by the recent proposed Lagrange Coded Computing (LCC) can be extremely low if the degree of the polynomial is high. We propose three different schemes called \emph{coded Algebraic normal form (ANF)}, \emph{coded Disjunctive normal form (DNF)} and \emph{coded polynomial threshold function (PTF)}. The key idea of the proposed schemes is to model it as the concatenation of some low-degree polynomials and threshold functions. In terms of the security threshold, we show that the proposed coded ANF and coded DNF are optimal by providing a matching outer bound.
The aim of this paper is to understand whether Distributed Ledger\nTechnologies (DLTs) are ready to support complex services, such as those\nrelated to Intelligent Transportation Systems (ITS). In smart transportation\nservices, a huge amount of sensed data is generated by a multitude of vehicles.\nWhile DLTs provide very interesting features, such as immutability,\ntraceability and verifiability of data, some doubts on the scalability and\nresponsiveness of these technologies appear to be well-founded. We propose an\narchitecture for ITS that resorts to DLT features. Moreover, we provide\nexperimental results of a real test-bed over IOTA, a promising DLT for IoT.\nResults clearly show that, while the viability of the proposal cannot be\nrejected, further work is needed on the responsiveness of DLT infrastructures.\n
Deepak Puthal, Saraju P. Mohanty, Venkata P. Yanambaka, Elias Kougianos
In today's connected world, resource constrained devices are deployed for sensing and decision making applications, ranging from smart cities to environmental monitoring. Those recourse constrained devices are connected to create real-time distributed networks popularly known as the Internet of Things (IoT), fog computing and edge computing. The blockchain is gaining a lot of interest in these domains to secure the system by ignoring centralized dependencies, where proof-of-work (PoW) plays a vital role to make the whole security solution decentralized. Due to the resource limitations of the devices, PoW is not suitable for blockchain-based security solutions. This paper presents a novel consensus algorithm called Proof-of-Authentication (PoAh), which introduces a cryptographic authentication mechanism to replace PoW for resource constrained devices, and to make the blockchain application-specific. PoAh is thus suitable for private as well as permissioned blockchains. Further, PoAh not only secures the systems, but also maintains system sustainability and scalability. The proposed consensus algorithm is evaluated theoretically in simulation scenarios, and in real-time hardware testbeds to validate its performance. Finally, PoAh and its integration with the blockchain in the IoT and edge computing scenarios is discussed. The proposed PoAh, while running in limited computer resources (e.g. single-board computing devices like the Raspberry Pi) has a latency in the order of 3 secs.
Abstract Port Knocking is a method for authenticating clients through a closed stance firewall, and authorising their requested actions, enabling severs to offer services to authenticated clients, without opening ports on the firewall. Advances in port knocking have resulted in an increase in complexity in design, preventing port knocking solutions from realising their potential. This paper proposes a novel port knocking solution, named Crucible, which is a secure method of authentication, with high usability and features of stealth, allowing servers and services to remain hidden and protected. Crucible is a stateless solution, only requiring the client memorise a command, the server’s IP and a chosen password. The solution is forwarded as a method for protecting servers against attacks ranging from port scans, to zero-day exploitation. To act as a random oracle for both client and server, cryptographic hashes were generated through chaotic systems.
In recent years, blockchain technology has received unparalleled attention from academia, industry, and governments all around the world. It is considered a technological breakthrough anticipated to disrupt several application domains. This has resulted in a plethora of blockchain systems for various purposes. However, many of these blockchain systems suffer from serious shortcomings related to their performance and security, which need to be addressed before any wide-scale adoption can be achieved. A crucial component of any blockchain system is its underlying consensus algorithm, which in many ways, determines its performance and security. Therefore, to address the limitations of different blockchain systems, several existing as well novel consensus algorithms have been introduced. A systematic analysis of these algorithms will help to understand how and why any particular blockchain performs the way it functions. However, the existing studies of consensus algorithms are not comprehensive. Those studies have incomplete discussions on the properties of the algorithms and fail to analyse several major blockchain consensus algorithms in terms of their scopes. This article fills this gap by analysing a wide range of consensus algorithms using a comprehensive taxonomy of properties and by examining the implications of different issues still prevalent in consensus algorithms in detail. The result of the analysis is presented in tabular formats, which provides a visual illustration of these algorithms in a meaningful way. We have also analysed more than hundred top crypto-currencies belonging to different categories of consensus algorithms to understand their properties and to implicate different trends in these crypto-currencies. Finally, we have presented a decision tree of algorithms to be used as a tool to test the suitability of consensus algorithms under different criteria.
The state-of-the-art approach to manage blockchains is to process blocks of transactions in a shared-nothing environment. Although blockchains have the potential to provide various services for high-performance computing (HPC) systems, HPC will not be able to embrace blockchains before the following two missing pieces become available: (i) new consensus protocols being aware of the shared-storage architecture in HPC, and (ii) new fault-tolerant mechanisms compensating for HPC's programming model---the message passing interface (MPI)---that is vulnerable for blockchain-like workloads. To this end, we design a new set of consensus protocols crafted for the HPC platforms and a new fault-tolerance subsystem compensating for the failures caused by faulty MPI processes. Built on top of the new protocols and fault-tolerance mechanism, a prototype system is implemented and evaluated with two million transactions on a 500-core HPC cluster, showing $6\times$, $12\times$, and $75\times$ higher throughput than Hyperldeger, Ethereum, and Parity, respectively.
We propose in this paper BlockHouse, a decentralized/P2P storage system fully based on private blockchains. Each participant can rent his unused storage in order to host data of other members. This system uses a dual Smart Contract and Proof of Retrievability system to automatically check at a fixed frequency if the file is still hosted. In addition to transparency, the blockchain allows a better integration with all payments associated to this type of system ( regular payments, sequestration to ensure good behaviors of users, ...). Except the data transferred between the client and the server, all the actions go through a smart contract in the blockchain in order to log, pay and secure the entire storage process.
A decade long thrive of cryptocurrency has shown its potential as a source of alternative-finance and the security and the robustness of the underpinning blockchain technology. However, most cryptocurrencies fail to show inimitability and their meanings in the real world. As a result, they usually start off as favourites but quickly become the outcasts of the digital asset market. The blockchain society attempts to anchor the value of cryp-tocurrency with real values by employing smart contracts and link it with computation resources and the digital-productivity that have value and demands in the real world. But their attempts have some undesirable effects due to a limited number of practical applications. This limitation is caused by the dilemma between high performance and decentralisation (universal join-ability). The emerging of blockchain sharding models, however, has offered a possible solution to address this dilemma. In this paper, we explore a financial model for blockchain sharding that will build an active link between the value of cryptocurrency and computation resources as well as the market and labour behaviours. Our model can adjust the price of resources and the compensation for maintaining a system based on those behaviours. We anchor the value of cryptocurrency by the amount of computation resources participated in and give the cryptocurrency a meaning as the exchange between computation resources globally. Finally, we present a working example which, through financial regularities, regulates the behaviour of anonymous participants, also incents/discourages participation dynamically.
Traditional public distributed ledgers have not been able to scale-out well and work efficiently. Sharding is deemed as a promising way to solve this problem. By partitioning all nodes into small committees and letting them work in parallel, we can significantly lower the amount of communication and computation, reduce the overhead on each node's storage, as well as enhance the throughput of the distributed ledger. Existing sharding-based protocols still suffer from several serious drawbacks. The first thing is that all non-faulty nodes must connect well with each other, which demands a huge number of communication channels in the network. Moreover, previous protocols have faced great loss in efficiency in the case where the honesty of each committee's leader is in question. At the same time, no explicit incentive is provided for nodes to actively participate in the protocol. We present CycLedger, a scalable and secure parallel protocol for distributed ledger via sharding. Our protocol selects a leader and a partial set for each committee, who are in charge of maintaining intra-shard consensus and communicating with other committees, to reduce the amortized complexity of communication, computation, and storage on all nodes. We introduce a novel semi-commitment scheme between committees and a recovery procedure to prevent the system from crashing even when leaders of committees are malicious. To add incentive for the network, we use the concept of reputation, which measures each node's trusty computing power. As nodes with a higher reputation receive more rewards, there is an encouragement for nodes with strong computing ability to work honestly to gain reputation. In this way, we strike out a new path to establish scalability, security, and incentive for the sharding-based distributed ledger.
Traditional Blockchain Sharding approaches can only tolerate up to n/3 of nodes being adversary because they rely on the hyper-geometric distribution to make a failure (an adversary does not have n/3 of nodes globally but can manipulate the consensus of a Shard) hard to happen. The system must maintain a large Shard size (the number of nodes inside a Shard) to sustain the low failure probability so that only a small number of Shards may exist. In this paper, we present a new approach of Blockchain Sharding that can withstand up to n/2 of nodes being bad. We categorise the nodes into different classes, and every Shard has a fixed number of nodes from different classes. We prove that this design is much more secure than the traditional models (only have one class) and the Shard size can be reduced significantly. In this way, many more Shards can exist, and the transaction throughput can be largely increased. The improved Blockchain Sharding approach is promising to serve as the foundation for decentralised autonomous organisations and decentralised database.
We improve the fundamental security threshold of eventual consensus Proof-of-Stake (PoS) blockchain protocols under the longest-chain rule by showing, for the first time, the positive effect of rounds with concurrent honest leaders. Current security analyses reduce consistency to the dynamics of an abstract, round-based block creation process that is determined by three events associated with a round: (i) event $A$: at least one adversarial leader, (ii) event $S$: a single honest leader, and (iii) event $M$: multiple, but honest, leaders. We present an asymptotically optimal consistency analysis assuming that an honest round is more likely than an adversarial round (i.e., $\Pr[S] + \Pr[M] > \Pr[A]$); this threshold is optimal. This is a first in the literature and can be applied to both the simple synchronous communication as well as communication with bounded delays. In all existing consistency analyses, event $M$ is either penalized or treated neutrally. Specifically, the consistency analyses in Ouroboros Praos (Eurocrypt 2018) and Genesis (CCS 2018) assume that $\Pr[S] - \Pr[M] > \Pr[A]$; the analyses in Sleepy Consensus (Asiacrypt 2017) and Snow White (Fin. Crypto 2019) assume that $\Pr[S] > \Pr[A]$. Moreover, all existing analyses completely break down when $\Pr[S] < \Pr[A]$. These thresholds determine the critical trade-off between the honest majority, network delays, and consistency error. Our new results can be directly applied to improve the security guarantees of the existing protocols. We also provide an efficient algorithm to explicitly calculate these error probabilities in the synchronous setting. Furthermore, we complement these results by analyzing the setting where $S$ is rare, even allowing $\Pr[S] = 0$, under the added assumption that honest players adopt a consistent chain selection rule.
Bitcoin-NG is among the first blockchain protocols to approach the \emph{near-optimal} throughput by decoupling blockchain operation into two planes: leader election and transaction serialization. Its decoupling idea has inspired a new generation of high-performance blockchain protocols. However, the existing incentive analysis of Bitcoin-NG has several limitations. First, the impact of network capacity is ignored. Second, an integrated incentive analysis that jointly considers both key blocks and microblocks is still missing. In this paper, we aim to address these two limitations. First, we propose a new incentive analysis that takes the network capacity into account, showing that Bitcoin-NG can still maintain incentive compatibility against the microblock mining attack even under limited network capacity. Second, we leverage a Markov decision process (MDP) to jointly analyze the incentive of both key blocks and microblocks, showing that the selfish mining revenue of Bitcoin-NG is a little higher than that in Bitcoin only when the selfish miner controls more than 35\% of the mining power. We hope that our in-depth incentive analysis for Bitcoin-NG can shed some light on the mechanism design and incentive analysis of next-generation blockchain protocols.
Mustafa Safa Özdayi, Murat Kantarcıoğlu, Bradley Malin
BACKGROUND: Blockchain has emerged as a decentralized and distributed framework that enables tamper-resilience and, thus, practical immutability for stored data. This immutability property is important in scenarios where auditability is desired, such as in maintaining access logs for sensitive healthcare and biomedical data. However, the underlying data structure of blockchain, by default, does not provide capabilities to efficiently query the stored data. In this investigation, we show that it is possible to efficiently run complex audit queries over the access log data stored on blockchains by using additional key-value stores. This paper specifically reports on the approach we designed for the blockchain track of iDASH Privacy & Security Workshop 2018 competition. In this track, participants were asked to devise an efficient way to run conjunctive equality and range queries on a genomic dataset access log trail after storing it in a permissioned blockchain network consisting of 4 identical nodes, each representing a different site, created with the Multichain platform. METHODS: Multichain duplicates and indexes blockchain data locally at each node in a key-value store to support retrieval requests at a later point in time. To efficiently leverage the key-value storage mechanism, we applied various techniques and optimizations, such as bucketization, simple data duplication and batch loading by accounting for the required query types of the competition and the interface provided by Multichain. Particularly, we implemented our solution and compared its loading and query-response performance with SQLite, a commonly used relational database, using the data provided by the iDASH 2018 organizers. RESULTS: Depending on the query type and the data size, the run time difference between blockchain based query-response and SQLite based query-response ranged from 0.2 seconds to 6 seconds. A deeper inspection revealed that range queries were the bottleneck of our solution which, nevertheless, scales up linearly. CONCLUSIONS: This investigation demonstrates that blockchain-based systems can provide reasonable query-response times to complex queries even if they only use simple key-value stores to manage their data. Consequently, we show that blockchains may be useful for maintaining data with auditability and immutability requirements across multiple sites.
Despite the popularity and practical applicability of blockchains, there is very limited work on the theoretical foundation of blockchains: The lack of rigorous theory and analysis behind the curtain of blockchains has severely staggered its broader applications. This paper attempts to lay out a theoretical foundation for a specific type of blockchains---the ones requiring basic authenticity from the participants, also called \textit{permissioned blockchain}. We formulate permissioned blockchain systems and operations into a game-theoretical problem by incorporating constraints implied by the wisdom from distributed computing and Byzantine systems. We show that in a noncooperative blockchain game (NBG), a Nash equilibrium can be efficiently found in a closed-form even though the game involves more than two players. Somewhat surprisingly, the simulation results of the Nash equilibrium implies that the game can reach a stable status regardless of the number of Byzantine nodes and trustworthy players. We then study a harder problem where players are allowed to form coalitions: the coalitional blockchain game (CBG). We show that although the Shapley value for a CBG can be expressed in a more succinct form, its core is empty.
We address the problem of fairness and transparency in online marketplaces selling digital content, where all parties are not actively participating in the trade. We present the design, implementation and evaluation of VADER, a highly scalable solution for multi-party fair digital exchange that combines the trusted execution of blockchains with intelligent protocol design and incentivization schemes. We prototype VADER on Hyperledger Fabric and extensively evaluate our system on a realistic testbed spanning five public cloud datacenters, spread across four continents. Our results demonstrate that VADER adds only minimal overhead of 16% in median case compared to a baseline solution, while significantly outperforming a naive blockchain based solution that adds an overhead of 764%.
This demo abstract introduces a new light-weight programming language koa which is suitable for blockchain system design and implementation. In this abstract, the basic features of koa are introduced including working system (with playground), architecture, and virtual machine operations. Rum-time execution of software implemented by koa will be presented during the session.
Yinqiu Liu, Kai Qian, Jianli Chen, Kun Wang · 5 authors
As an emerging technology, blockchain has achieved great success in numerous application scenarios, from intelligent healthcare to smart cities. However, a long-standing bottleneck hindering its further development is the massive resource consumption attributed to the distributed storage and computation methods. This makes blockchain suffer from insufficient performance and poor scalability. Here, we analyze the recent blockchain techniques and demonstrate that the potential of widely-adopted consensus-based scaling is seriously limited, especially in the current era when Moore's law-based hardware scaling is about to end. We achieve this by developing an open-source benchmarking tool, called Prism, for investigating the key factors causing low resource efficiency and then discuss various topology and hardware innovations which could help to scale up blockchain. To the best of our knowledge, this is the first in-depth study that explores the next-generation scaling strategies by conducting large-scale and comprehensive benchmarking.
Blockchain has emerged as a promising technology that can guarantee data consistency and integrity among distributed participants. It has been used in many applications of the Internet of Things (IoT). However, since IoT applications often introduce a massive number of devices into blockchain systems, the efficiency of the blockchain becomes a serious problem. In this article, we analyze the key factors affecting the efficiency of blockchain. Unlike most existing solutions that handle this from the computing perspective, we consider the problem from the communication perspective. In particular, we propose a coordinated satellite-terrestrial network to create efficient blockchains. We also derive a network scheduling strategy for the proposed architecture. Simulation results demonstrate that the proposed system can support blockchains for higher efficiency. Moreover, several open research issues and design challenges will be discussed.
Vasilios Mavroudis, Karl Wüst, Aritra Dhar, Kari Kostiainen · 5 authors
Permissionless blockchains offer many advantages but also have significant limitations including high latency. This prevents their use in important scenarios such as retail payments, where merchants should approve payments fast. Prior works have attempted to mitigate this problem by moving transactions off the chain. However, such Layer-2 solutions have their own problems: payment channels require a separate deposit towards each merchant and thus significant locked-in funds from customers; payment hubs require very large operator deposits that depend on the number of customers; and side-chains require trusted validators. In this paper, we propose Snappy, a novel solution that enables recipients, like merchants, to safely accept fast payments. In Snappy, all payments are on the chain, while small customer collaterals and moderate merchant collaterals act as payment guarantees. Besides receiving payments, merchants also act as statekeepers who collectively track and approve incoming payments using majority voting. In case of a double-spending attack, the victim merchant can recover lost funds either from the collateral of the malicious customer or a colluding statekeeper (merchant). Snappy overcomes the main problems of previous solutions: a single customer collateral can be used to shop with many merchants; merchant collaterals are independent of the number of customers; and validators do not have to be trusted. Our Ethereum prototype shows that safe, fast (<2 seconds) and cheap payments are possible on existing blockchains.
The recent proliferation of Electronic Commerce (E-commerce) has been further escalated by multifaceted emerging payment solutions such as cryptocurrencies, mobile, peer-to-peer (P2P) and social media payment platforms. While these technological advancements are gaining tremendous popularity, mostly for their ease of use, various impediments such as security and privacy concerns, societal and cultural norms etc. forbear the users' adoption trends to some extents. This article examines the current status of the social media payment platforms as well as the projection of future adoption trends. Our research underlines the motivations and obstacles to the adoption of social media platforms.
The interoperability across multiple blockchains would play a critical role in future blockchain-based data management paradigm. Existing techniques either work only for two blockchains or requires a centralized component to govern the cross-blockchain transaction execution, neither of which would meet the scalability requirement. This paper proposes a new distributed commit protocol, namely \textit{cross-blockchain transaction} (CBT), for conducting transactions across an arbitrary number of blockchains without any centralized component. The key idea of CBT is to extend the two-phase commit protocol with a heartbeat mechanism to ensure the liveness of CBT without introducing additional nodes or blockchains. We have implemented CBT and compared it to the state-of-the-art protocols, demonstrating CBT's low overhead (3.6\% between two blockchains, less than $1\%$ among 32 or more blockchains) and high scalability (linear scalability on up to 64-blockchain transactions). In addition, we developed a graphic user interface for users to virtually monitor the status of the cross-blockchain transactions.