<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.
The goal of this research is to estimate the data propagation time on the Bitcoin network. Using network coordinates, we estimate the communication latency between computers. Such latency estimation contributes future optimization of data propagation. In this research, we report an experiment on computing the network coordinates. In the current Bitcoin network, it is very difficult to acquire internode delay because the network topology is not available. In this study, we calculate the delay based on our topology estimation and describe the effectiveness of the network coordinates using various topology estimation parameters.
Sam M. Werner, Paul J. Pritz, Alexei Zamyatin, William J. Knottenbelt
Mining pools in Proof-of-Work cryptocurrencies allow miners to pool their computational resources as a means of reducing payout variance. In Ethereum, uncle blocks are valid Proof-of-Work solutions which do not become the head of the blockchain, yet yield rewards if later referenced by main chain blocks. Mining pool operators are faced with the non-trivial task of fairly distributing rewards for both block types among pool participants.Inspired by empirical observations, we formally reconstruct a Sybil attack exploiting the uncle block distribution policy in a queue-based mining pool. To ensure fairness of the queue-based payout scheme, we propose a mitigation. We examine the effectiveness of the attack strategy under the current and the proposed policy via a discrete-event simulation. Our findings show that the observed attack can indeed be obviated by altering the current reward scheme.
This paper presents a stochastic model for block arrival times based on the difficulty retargeting rule used in Bitcoin, as well as other proof-of-work blockchains. Unlike some previous work, this paper explicitly models the difficulty target as a random variable which is a function of the previous block arrival times and affecting the block times in the next retargeting period. An explicit marginal distribution is derived for the time between successive blocks (the blocktime), while allowing for randomly changing difficulty. This paper also aims to serve as an introduction to Bitcoin and proof-of-work blockchains for the controls community, focusing on the difficulty retargeting procedure used in Bitcoin.
Bruno Andriamanalimanana, Chen-Fu Chiang, Jorge Novillo, Sam Sengupta · 5 authors
A central problem with distributed ledger technologies involves the latency that must be incurred in processing and verifying transactions to be accepted as permanent records in the ledger. In many applications, high latency is simply not a tolerable aspect of the governance of the ledger. To help reduce latency, we first propose a theoretical pulsed injection protocol then apply innovative inventory theory onto the unverified transactions in the system. To utilize a probabilistic model for the pulsed injection of transactions, we calibrate the optimum pulsed transaction injection batch size to ensure equilibrium and optimal performance of the system.
This paper proposes Consensus-Before-Talk (CBT), a spectrum etiquette architecture leveraged by distributed ledger technology (DLT). In CBT, secondary users' spectrum access requests reach a consensus in a distributed way, thereby enabling collision-free distributed dynamic spectrum access. To achieve this consensus, the secondary users need to pay for the extra request exchanging delays. Incorporating the consensus delay, the end-to-end latency under CBT is investigated. Both the latency analysis and numerical evaluation validate that the proposed CBT achieves the lower end-to-end latency particularly under severe secondary user traffic, compared to the Listen-Before-Talk (LBT) benchmark scheme.
Blockchain has many benefits including decentralization, availability, persistency, consistency, anonymity, auditability and accountability, and it also covers a wide spectrum of applications ranging from cryptocurrency, financial services, reputation system, Internet of Things, sharing economy to public and social services. Not only may blockchain be regarded as a by-product of Bitcoin cryptocurrency systems, but also it is a type of distributed ledger technology through using a trustworthy, decentralized log of totally ordered transactions. By summarizing the literature of blockchain, it is found that more papers focus on engineering implementation and realization, while little work has been done on basic theory, for example, mathematical models (Markov processes, queueing theory and game models), performance analysis and optimization of blockchain systems. In this paper, we develop queueing theory of blockchain systems and provide system performance evaluation. To do this, we design a Markovian batch-service queueing system with two different service stages, while the two stages are suitable to well express the mining process in the miners pool and the building of a new blockchain. By using the matrix-geometric solution, we obtain a system stable condition and express three key performance measures: (a) The number of transactions in the queue, (b) the number of transactions in a block, and (c) the transaction-confirmation time. Finally, We use numerical examples to verify computability of our theoretical results. Although our queueing model is simple under exponential or Poisson assumptions, our analytic method will open a series of potentially promising research in queueing theory of blockchain systems.
Jul 1, 2018·2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData)
In Bitcoin, it is well known that the confirmation of a transaction issued by a user takes a longer time than the mean block-generation time of 10 minutes. In order to understand the stochastic behavior of the transaction-confirmation process, we consider a queueing model with batch service and general input. In our queueing model, we assume that the transaction interarrival times are independent and identically distributed (i.i.d.), and follow a general distribution, and that the transactions waiting in the queue are served in a batch manner. We define the number of transactions in queue just before a transaction arrival as the system state, deriving the steady-state distribution and the mean transaction-confirmation time by matrix analytic method. In numerical examples, we compare analytical results with trace-driven simulation, discussing the applicability of our queueing model to the prediction of the transaction-confirmation time. It is found that exponential-type distributions such as exponential distribution and hyper-exponential one can accurately estimate the mean transaction-confirmation time for the current maximum block-size limit of 1 Mbyte.
We analyze the economic incentives generated by the proof-of-stake mechanism discussed in the Ethereum Casper upgrade proposal. Compared with proof-of-work, proof-of-stake has a different cost structure for attackers. In Budish (2018), three equations characterize the limits of Bitcoin, which has a proof-of-work mechanism. We investigate their counterparts and evaluate the risk of double-spending attack and sabotage attack. We argue that PoS is safer than PoW agaisnt double-spending attack because of the tractability of attackers, which implies a large "stock" cost for the attacker. Compared to a PoW system whose mining equipments are repurposable, PoS is also safer against a sabotage attack.
The synchronization process inherent to the Bitcoin network gives rise to an infinite-server model with the unusual feature that customers interact. Among the closed-form characteristics that we derive for this model is the busy period distribution which, counterintuitively, does not depend on the arrival rate. We explain this by exploiting the equivalence between two specific service disciplines, which is also used to derive the model's stationary distribution. Next to these closed-form results, the second major contribution concerns an asymptotic result: a fluid limit in the presence of service delays. Since fluid limits arise under scalings of the law-of-large-numbers type, they are usually deterministic, but in the setting of the model discussed in this paper the fluid limit is random (more specifically, of growth-collapse type).
We correct the double spend race analysis given in Nakamoto’s foundational Bitcoin article and find the exact closed-form formula for the probability of success of a double spend attack using the regularized incomplete beta function. We give the first proof of its exponential decay on the number of confirmations, often cited in the literature, and find an asymptotic formula. Larger number of confirmations are required compared to those given by Nakamoto. We also compute this probability conditional to the knowledge of the time of the confirmations. This provides a finer risk analysis than the classical one.