This work proposes Practical Byzantine Fault Tolerance (PBFT) ordering service needed for block formation in permissioned blockchain environments. Contrary to current PBFT implementations that only provide a single point of entry to the ordering service, we allow each ordering node to act as an entry point that proposes and conducts the consensus process of including new record in the distributed ledger. To ensure atomicity of record insertion in distributed ledger, we have developed a bandwidth reservation protocol that uses a modification of CSMA/CA protocol to regulate access to the broadcast medium formed by the P2P network of TCP connections between orderers. We have modeled record insertion service time in a cluster where ordering nodes have random position within Cartesian coordinate system. We have also modeled total request access time to the ledger which includes waiting time in the ordered's queue and record insertion time. These models are used to evaluate system performance under variable request rate ordering service, variable number of nodes and variable physical cluster dimensions. We also address cluster interconnections which can increase coverage and capacity of PBFT system.
Abhilash Kancharla, Jongho Seol, Hye-Young Kim, Nohpill Park
This paper proposes a quantitative model for a new blockchain technology that distributes public ledger in a decentralized manner, referred to as Distributed Decentralized chain (DDC). A clique of k nodes in the P2P network participates in storing a complete copy of blockchain instead of having every node carry an entire copy. The proposed model is k-Queue Variable Bulk Arrival and Static Bulk Service queueing model (k-VBASBS), in which the state is defined by (i,k), where i is the number of slots from 0 upto n in a block on the current node, and k is the number of distributed nodes to store a complete copy of a chain of blocks. Without loss of generality and practicality, it is assumed that there are two different transaction posting rates assumed to take into account the overhead of inter-node (i.e., μ(inter-node)) control-hopping versus the one of the original intra-node posting rate (i.e., μ(intra-node)), and μ(inter-node)μ<<(intra-node). Based on the proposed k-VBASBS model, the average waiting time, space requirement, and throughput of the transactions will be simulated for the performance, and the dependability will be also modeled and simulated by the vulnerability to 51% attack.
Long Shi, Taotao Wang, Jun Li, Shengli Zhang · 5 authors
As the underlying consensus protocol of Bitcoin and Ethereum blockchains, Proof-of-Work (PoW) features a cryptographic mathematical puzzle whose solution is easy to verify but extremely hard to solve. Under PoW, miners maintain the security of blockchain by devoting computing powers to solve the puzzle; the miner who has solved the puzzle successfully generates a block, along with a reward (e.g., a set of cryptocurrency). The average waiting time to generate a block is inversely proportional to the computing power of the miner. To reduce the average block generation time, a group of individual miners can form a centralized mining pool to aggregate their computing power to solve the puzzle together and share the reward contained in the block. However, if the aggregated computing power of the pool forms a substantial portion of the total computing power in the network, the pooled mining undermines the core spirit of blockchain, i.e., the decentralization, and harms its security. To discourage the pooled mining, we develop a new consensus protocol called Proof-of-Age (PoA) that builds upon the native PoW protocol. The core idea of PoA lies in using Age-of-Work (AoW) to measure the effective mining periods that the miners have devoted to maintaining the security of blockchain. Unlike in the native PoW protocol, in our PoA protocol, miners benefit from its effective mining periods even if they have not successfully mined a block. We first employ a continuous time Markov chain (CTMC) to model the block generation process of the PoA based blockchain. Based on this CTMC model, we then analyze the block generation rates of the mining pool and solo miners respectively. Our analytical results verify that under PoA, the block generation rates of miners in the mining pool are reduced compared to that of solo miners, thereby disincentivizing the pooled mining. Finally, we simulate the mining process in the PoA blockchain to demonstrate the consistency of the analytical results.
This paper presents a queueing model for mining-based public blockchains and validations with respect to specific yet practical characteristics of public blockchains such as Bitcoin and Ethereum, primarily in terms of transaction queue size and block waiting time, as an alternative solution to the conventional industrial networks for the trustworthiness it offers. A set of variables taken into account in this model lists the network traffic intensity, the maximum number of transactions in a block, the block time, and the transaction arrival rate, to mention a few. The proposed model provides a comprehensive yet fundamental basis to assure and ultimately optimize the design of blockchain technology-based applications in specific terms of performance. Numerical simulations have been conducted and the efficacy of the proposed model is validated in a quantitative yet practical manner versus Bitcoin and Ethereum.
Daniel M. Kane, Andreas Fackler, Adam GÄ…gol, Damian Straszak
There has been recently a lot of progress in designing efficient partially synchronous BFT consensus protocols that are meant to serve as core consensus engines for Proof of Stake blockchain systems. While the state-of-the-art solutions attain virtually optimal performance under this theoretical model, there is still room for improvement, as several practical aspects of such systems are not captured by this model. Most notably, during regular execution, due to financial incentives in such systems, one expects an overwhelming fraction of nodes to honestly follow the protocol rules and only few of them to be faulty, most likely due to temporary network issues. Intuitively, the fact that almost all nodes behave honestly should result in stronger confidence in blocks finalized in such periods, however it is not the case under the classical model, where finality is binary. We propose Highway, a new consensus protocol that is safe and live in the classical partially synchronous BFT model, while at the same time offering practical improvements over existing solutions. Specifically, block finality in Highway is not binary but is expressed by fraction of nodes that would need to break the protocol rules in order for a block to be reverted. During periods of honest participation finality of blocks might reach well beyond 1/3 (as what would be the maximum for classical protocols), up to even 1 (complete certainty). Having finality defined this way, Highway offers flexibility with respect to the configuration of security thresholds among nodes running the protocol, allowing nodes with lower thresholds to reach finality faster than the ones requiring higher levels of confidence.
Roberta Pellegrino, Nicola Costantino, Danilo Tauro
The purpose of this paper is to study how advanced information about customer needs obtained through an Advance Purchase Discount (APD) contract can be exploited to coordinate the capital flow and enhance the efficiency of a two-stage supply chain (SC) under decentralized control in cases of stochastic customer demand. We developed an APD model in the form of an option contract, where the model and evaluation include the flexibility for the upstream firm to decide whether to provide a discount for an advance purchase at its own discretion. Applying the model to a Fortune 100 company, a leader in the Fast Mover Consumer Goods (FMCG) industry, showed that under certain conditions, and with suitably chosen contract parameters, management of decentralized control via APD contracts can lead to system-wide efficiency, and the individual decision makers pursue their own best interests, ensuring a win-win condition.
Mining blocks on a blockchain equipped with a proof of work consensus protocol is well known to be resource consuming. A miner bears the operational cost, mainly electricity consumption and IT gear, of mining and is compensated by a capital gain when a block is discovered. This paper aims at quantifying the profitability of mining when the possible event of ruin is also considered. This is done by formulating a tractable stochastic model and using tools from applied probability and analysis, including the explicit solution of a certain type of advanced functional differential equation. The expected profit at a future time point is determined for the situation when the miner follows the protocol as well as when the miner withholds blocks. The obtained explicit expressions allow us to analyze the sensitivity with respect to the different model components and to identify conditions under which selfish mining is a strategic advantage.
This paper proposes a novel embedded Markovian queueing model of the M(1,n)/Mn/1 type in order to establish a theoretical foundation to design a blockchain-based system with specific interest in Ethereum. The model assumes variable bulk arrivals of transactions in Poisson distribution, i.e., M(1,n), where n the number of slots across all the mined transactions and static bulk service of transactions in exponential time, i.e., Mn, for posting in the current block, namely, VBASBP. The primary performance measurements to be taken are the average number of slots no matter how many transactions are mined under the assumption of the maximum number of slots per block as specified by n; the average waiting time per slot; and the throughput in terms of the average number of slots to be processed per time. The variable bulk arrival rate is assumed to vary linearly proportional to the size of the transactions in a multiple of per slot, and the static bulk service is assumed to take place when the number of slots in the mined transactions reaches at n, i.e., a bulk processing of multiple transactions in multiple slots for posting in a block. Numerical simulations are conducted on Matlab to demonstrate the efficacy of the model.
Michael Neuder, Daniel J. Moroz, Rithvik Rao, David C. Parkes
Blockchains are intended to be immutable, so an attacker who is able to delete transactions through a chain reorganization (a malicious reorg) can perform a profitable double-spend attack. We study the rate at which an attacker can execute reorgs in the Tezos Proof-of-Stake protocol. As an example, an attacker with 40% of the staking power is able to execute a 20-block malicious reorg at an average rate of once per day, and the attack probability increases super-linearly as the staking power grows beyond 40%. Moreover, an attacker of the Tezos protocol knows in advance when an attack opportunity will arise, and can use this knowledge to arrange transactions to double-spend. We show that in particular cases, the Tezos protocol can be adjusted to protect against deep reorgs. For instance, we demonstrate protocol parameters that reduce the rate of length-20 reorg opportunities for a 40% attacker by two orders of magnitude. We also observe a trade-off between optimizing for robustness to deep reorgs (costly deviations that may be net profitable because they enable double-spends) and robustness to selfish mining (mining deviations that result in typically short reorgs that are profitable even without double-spends). That is, the parameters that optimally protect against one make the other attack easy. Finally, we develop a method that monitors the Tezos blockchain health with respect to malicious reorgs using only publicly available information.
Rhys Bowden, Paul Keeler, A. E. Krzesinski, Peter Taylor
In the original Bitcoin paper and other research papers since, it is assumed that Bitcoin blocks are mined at the instants of a homogeneous Poisson process. Based on blockchain block arrival data and stochastic analysis of the block arrival process, we demonstrate that this is not the case. We present a framework for studying the block arrival process, including two refined mathematical models for block arrivals, determined by combining models for a period of constant difficulty and how the difficulty evolves over time.
This paper proposes a real-time chain and a novel embedded Markovian queueing model with variable bulk arrival (VBA) and variable bulk service (VBS) in order to establish and assure a theoretical foundation to design a blockchain-based real-time system with particular interest in Ethereum. Based on the proposed model, various performances are simulated in a numerical manner in order to validate the efficacy of the model by checking good agreements with the results against intuitive and typical expectations as a baseline. A demo of the proposed real-time chain is developed in this work by modifying the open source of Ethereum Geth 1.9.11. The work in this paper will provide both a theoretical foundation to design and optimize the performances of the proposed real-time chain, and ultimately address and resolve the performance bottleneck due to the conventional block-synchrony by employing an asynchrony by the real-time deadline to some extent.
Proof-of-work cryptocurrencies are heavily criticized for the alleged inefficiency of their mining mechanism. However, critics fail to distinguish between the resources that are used to secure the blockchain and those that are wasted. In this paper, we introduce a simple mining model and use this model to analyze the consensus protocol's efficiency, while accounting for the heterogeneity of the miners involved. We categorize the resources allocated by the miners as either useful or wasteful, and then use this to introduce a new measure of efficiency. We then demonstrate how this value depends on a set of potential miners and the variation of their marginal costs. Using this model, we then consider the existence of botnets and show how one could affect the security of the network. This analysis indicates that botnets can significantly change the mining landscape and, under certain circumstances, may lead to a dissipation ratio greater than one.
We consider two different continuous-time Markov chain models recently studied in Göbel et al.[8 Göbel, J.; Keeler, H. P.; Krzesinski, A. E.; Taylor, P. G. Bitcoin blockchain dynamics: The selfish-mine strategy in the presence of propagation delay. Perform. Eval. 2016, 104, 23–41. DOI: 10.1016/j.peva.2016.07.001.[Crossref], [Web of Science ®] , [Google Scholar]], which were created to model the interactions between a small pool of miners, and a larger collection of miners, within the Bitcoin network. The first model we discuss represents the case where all miners behave honestly and follow the Bitcoin protocol, while the second model represents the case where the smaller pool of miners use the Selfish Mining strategy of Eyal and Sirer[3 Eyal, I.; Sirer, E. G. Majority is not enough: Bitcoin mining is vulnerable. In Financial Cryptography and Data Security; Springer, Berlin, 2013; 436–454. [Google Scholar]]. We give a new derivation of the stationary distribution of the process in the honest mining case and further build on the results of Göbel et al.[8 Göbel, J.; Keeler, H. P.; Krzesinski, A. E.; Taylor, P. G. Bitcoin blockchain dynamics: The selfish-mine strategy in the presence of propagation delay. Perform. Eval. 2016, 104, 23–41. DOI: 10.1016/j.peva.2016.07.001.[Crossref], [Web of Science ®] , [Google Scholar]] by showing that the normalizing constant can be expressed in closed-form. We also use similar techniques to derive expressions for the Laplace transforms of the transition functions. We then illustrate how these techniques yield similar expressions for the stationary distribution of the process when the smaller pool implements Selfish Mining: the Laplace transforms of the transition functions can be calculated as well. Lastly, we briefly explain how our methods can be extended to more general models of a similar type.
Elham Akbari, Wenbing Zhao, Shunkun Yang, Xiong Luo
It has been well recognized that traditional blockchains have limited throughput. It is intuitive to achieve higher throughput by increasing the block size and shortening the block interval. In this paper, we study the security implications on doing so, and define the boundary for acceptable block sizes and block intervals. We define the security of the blockchain in terms of the stale block rate in the network and carry out an empirical study using a blockchain simulator to find the optimal block parameters (i.e., size and interval). We show that it is possible to achieve sufficiently high throughput for a blockchain platform to be used for activities beyond cryptocurrency, such as state-level electronic voting.
In this article, we study the performance of blockchains by analyzing the common prefix depth, chain quality coefficient, and chain growth speed coefficient. These three parameters characterize the liveness and consistency of transactions which are important for the proper operation of the blockchain. We examine how these three parameters are affected under an adaptive double-spend attack (ADSA). To maintain the performance of a blockchain against ADSA, the user nodes can use a larger number, z, of confirmation blocks for validating a transaction. A comparison of the values of z needed to achieve a given target probability of successful attack is provided for ADSA and the traditional double-spend attack with different system models. The results indicate that a larger value of z is required under ADSA. A more realistic reward model for attackers is also introduced. It is found that the expected reward of an attacker decreases rapidly to zero as z is increased.
Blockchain technology has recently obtained widespread attention. And it is being regarded as potentially even more disruptive than the Internet, whose usage includes large areas of applications ranging from crypto currency, financial services, reputation system, Internet of Things, sharing economy to public and social services. The existing works of blockchain primarily are focused on key components and potential applications. However, in the existing blockchain systems, the waiting time of transactions is too long. Furthermore, it may produce serious consequences because many important transactions are not handled timely. To solve the problem, in the paper, the blockchain Queuing model with non-preemptive limited-priority is established, which considers the different transactions having different priority when being mined. There are two classes of transactions in the model, one is high-priority transaction with pay or with prior interest, the other is low-priority transaction without pay or without prior interest. And high-priority transactions can be mined preferentially when mining process is not occupied. If low-priority transaction is being mined, the arriving high-priority transaction will wait for the mining accomplishment. Through the analysis of the model, we compute average waiting time, average staying time and average length of queue. From simulation of the model, we find that transactions with pay or with prior interest and increase service rate of mining are effective for reducing waiting time. Besides, the two factors mutually reinforce to shorten waiting time. Finally, we conclude this paper and point out the direction of future research.
Jun Zhao, Jing Tang, Zengxiang Li, Huaxiong Wang · 6 authors
Formal analyses of blockchain protocols have received much attention recently. Consistency results of Nakamoto's blockchain protocol are often expressed in a quantity $c$, which denotes the expected number of network delays before some block is mined. With $μ$ (resp., $ν$) denoting the fraction of computational power controlled by benign miners (resp., the adversary), where $μ+ ν= 1$, we prove for the first time that to ensure the consistency property of Nakamoto's blockchain protocol in an asynchronous network, it suffices to have $c$ to be just slightly greater than $\frac{2μ}{\ln (μ/ν)}$. Such a result is both neater and stronger than existing ones. In the proof, we formulate novel Markov chains which characterize the numbers of mined blocks in different rounds.
Abstract A shared ledger is a record of transactions that can be updated by any member of a group of users. The notion of independent and consistent record-keeping in a shared ledger is important for blockchain and more generally for distributed ledger technologies. In this paper we analyze a stochastic model for the shared ledger known as the tangle, which was devised as the basis for the IOTA cryptocurrency. The model is a random directed acyclic graph, and its growth is described by a non-Markovian stochastic process. We first prove ergodicity of the stochastic process, and then derive a delay differential equation for the fluid model which describes the tangle at high arrival rate. We prove convergence in probability of the tangle process to the fluid model, and also prove global stability of the fluid model. The convergence proof relies on martingale techniques.
Despite the growing interest in cryptocurrencies, the delays incurred to confirm transactions are one of the factors that hamper the wide adoption of systems such as Bitcoin. Bitcoin transactions usually are confirmed in short periods (minutes), but still much larger than conventional credit card systems (seconds). In this work, we propose a framework encompassing machine learning and a queueing theory model to (i) identify which transactions will be confirmed; and (ii) characterize the confirmation time of confirmed transactions. The proposed queueing theory model accounts for factors such as the activity time of blocks and the mean time between transactions. We parameterize the model for transactions that are confirmed within minutes, suggesting that its integration into a more general framework is a step towards building scalability to Bitcoin.
<p style='text-indent:20px;'>In Bitcoin system, a transaction is given a priority value according to its attributes such as the remittance amount and fee, and transactions with high priorities are likely to be confirmed faster than those with low priorities. In this paper, we analyze the transaction-confirmation time for Bitcoin system. We model the transaction-confirmation process as a queueing system with batch service, M/<inline-formula><tex-math id="M1">\begin{document}$ \mbox{G}^B $\end{document}</tex-math></inline-formula>/1. We consider the joint distribution of numbers of transactions in system and the elapsed service time, deriving the mean transaction-confirmation time. Using the result, we derive the recursive formulae of mean transaction-confirmation times of an M/<inline-formula><tex-math id="M2">\begin{document}$ \mbox{G}^B $\end{document}</tex-math></inline-formula>/1 queue with priority service discipline. In numerical examples, we show the effect of the maximum block size on the mean transaction-confirmation time, investigating the accuracy region of our queueing model. We also discuss how the increase in micropayments, which are likely to be given low priorities, affects the transaction-confirmation time.
Jan 1, 2019·Proceedings of the ... Annual Hawaii International Conference on System Sciences/Proceedings of the Annual Hawaii International Conference on System Sciences
In this paper, the authors review documented problems in military intelligence that appear well suited for improvement via blockchain technology. We review guidance from the literature related to determining blockchain technology applicability and propose a decision aid tailored to military intelligence perspectives. We also propose applying batch queueing theory to enable initial feasibility studies and present analysis toward the first known case study of military intelligence incorporation of blockchain technology, a project reviewing blockchain applicability to an intelligence database that stores geographic locations of units of interest.