Priority queueing analysis of transaction-confirmation time for Bitcoin

Yoshiaki Kawase; Shoji Kasahara

doi:10.3934/jimo.2018193

Article Contents

2020, Volume 16, Issue 3: 1077-1098. Doi: 10.3934/jimo.2018193

This issue Previous Article The (functional) law of the iterated logarithm of the sojourn time for a multiclass queue Next Article Utility maximization for bandwidth allocation in peer-to-peer file-sharing networks

Priority queueing analysis of transaction-confirmation time for Bitcoin

Yoshiaki Kawase and
Shoji Kasahara

Graduate School of Information Science, Nara Institute of Science and Technology, Takayama 8916-5, Ikoma, Nara 6300192, Japan

Received: October 2017

Revised: April 2018

Early access: December 25, 2018

Published online: December 25, 2018

The second author is supported by Grant-in-Aid for Scientific Research (B) No. 15H04008 and SCAT Foundation.

Abstract / Introduction Full Text(HTML) Figure(13) / Table(4) Related Papers Cited by

Abstract

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/$ \mbox{G}^B $/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/$ \mbox{G}^B $/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.

Keywords:

Mathematics Subject Classification: Primary: 68M20, 90B22; Secondary: 60K25.

Citation:

Full Text(HTML)

Figure 1. Comparison of analysis and simulation for basic queueing model

Download: Full-size image PowerPoint slide

Figure 2. Comparison of analysis and simulation for priority-queueing model

Download: Full-size image PowerPoint slide

Figure 3. Transaction-confirmation time vs. block size, 1st period (October 2013 to September 2014). $ \lambda = 0.7336929 $, $ \mu = 0.0019748858 $, and the coefficient of variation of transaction inter-arrival time: $ 3.72401599 $

Download: Full-size image PowerPoint slide

Figure 4. Transaction-confirmation time vs. block size, 2nd period (October 2014 to September 2015). $ \lambda = 1.2081311 $, $ \mu = 0.0017009449 $, and the coefficient of variation of transaction inter-arrival time: $ 15.3250509 $

Download: Full-size image PowerPoint slide

Figure 5. The mean transaction-arrival rate

Download: Full-size image PowerPoint slide

Figure 6. Transaction-confirmation time vs. block size, October 2013 to September 2014. $ \lambda_H = 0.7203544 $, $ \mu = 0.0019748858 $

Download: Full-size image PowerPoint slide

Figure 7. Transaction-confirmation time vs. block size, October 2014 to September 2015. $ \lambda_H = 1.1494675 $, $ \mu = 0.0017009449 $

Download: Full-size image PowerPoint slide

Figure 8. Transaction-confirmation time vs. block size, October 2013 to September 2014. $ \lambda_L = 0.0133385 $, $ \mu = 0.0019748858 $

Download: Full-size image PowerPoint slide

Figure 9. Transaction-confirmation time vs. block size, October 2014 to September 2015. $ \lambda_L = 0.0586636 $, $ \mu = 0.0017009449 $

Download: Full-size image PowerPoint slide

Figure 10. The effects of the block size on the transaction-confirmation time

Download: Full-size image PowerPoint slide

Figure 11. The effects of the micropayments on the transaction-confirmation time

Download: Full-size image PowerPoint slide

Figure 12. The effect of the block size on the transaction-confirmation time of high-priority transactions

Download: Full-size image PowerPoint slide

Figure 13. The effects of the block size on the transaction-confirmation time of low-priority transactions

Download: Full-size image PowerPoint slide

Table 1. Mean transaction confirmation time for each priority

Period		Classless [s]	Low priority [s]	High priority [s]
1st	(2013/10/1-2014/9/30)	1060.67797	1947.47115	1044.25043
2nd	(2014/10/1-2015/9/30)	1171.98866	4887.56496	1070.32818
overall	(2013/10/1-2015/9/30)	1124.13286	3888.06977	1059.06133

| Show Table

DownLoad: CSV

Table 2. Comparison of analysis and measurement

Transaction Type	Arrival Rate	Measurement [s]	Analysis[s]
Classless	0.9709120529	1124.13286	1112.025339
High Priority	0.9349109906	1059.06133	1108.773595
Low Priority	0.0360010622	3888.06977	1196.469817

| Show Table

DownLoad: CSV

Table 3. Coefficients of variation for transaction interarrival time

Period	1st 2013/10-2014/09	2nd 2014/10-2015/09	Overall 2013/10-2015/09
Classless	3.72401	15.32505	10.17893

| Show Table

DownLoad: CSV

Table 4. Coefficients of variation for transaction interarrival time, two-priority classes

Period	1st 2013/10-2014/09	2nd 2014/10-2015/09	Overall 2013/10-2015/09
Low Priority	1.66569	3.90654	3.01387
High Priority	3.70045	14.94895	9.99103

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. M. Antonopoulos, Mastering Bitcoin, O'Reilly, 2014.
[2]	M. L. Chaudhry and J. G. C. Templeton, The queuing system M/G^B/1 and its ramifications, European Journal of Operational Research, 6 (1981), 56-60. doi: 10.1016/0377-2217(81)90328-3.
[3]	M. L. Chaudhry and J. G. C. Templeton, A First Course in Bulk Queues, John Wiley & Sons, 1983.
[4]	http://www.meti.go.jp/committee/kenkyukai/sansei/fintech\_kadai/pdf/003\_02\_00.pdf
[5]	http://www.coindesk.com/1mb-block-size-today-bitcoin/
[6]	https://blockchain.info/
[7]	http://www.coindesk.com/segregated-witness-bitcoin-block-size-debate/
[8]	S. Kasahara and J. Kawahara, Effect of Bitcoin fee on transaction-confirmation process, arXiv: 1604.00103[cs.CR].
[9]	Y. Kawase and S. Kasahara, Transaction-Confirmation Time for Bitcoin: A Queueing Analytical Approach to Blockchain Mechanism, The 12th International Conference on Queueing Theory and Network Applications (QTNA2017), Qinhuangdao, China, August 21-23, 2017.
[10]	M. Möser and R. Böhome, Trends, tips, tolls: A longitudinal study of bitcoin transaction fees, Financial Cryptography and Data Security, Lecture Notes in Computer Science, Springer, 8976 (2015), 19-33. doi: 10.1007/978-3-662-48051-9_2.
[11]	S. Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, 2008. Available from: https://bitcoin.org/bitcoin.pdf.
[12]	J. Poon and T. Dryja, The bitcoin lightning network: Scalable off-chain instant payments, https://lightning.network/lightning-network-paper.pdf, 2016.
[13]	H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation, Vol. 2. Finite systems. North-Holland Publishing Co., Amsterdam, 1993.
[14]	https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki
[15]	F. Tschorsch and B. Scheuermann, Bitcoin and beyond: A technical survey on decentralized digital currencies, Tutorials, 18 (2016), 2084-2123.
[16]	https://www.bitcoincash.org/
[17]	https://www.coindesk.com/segwits-slow-rollout-bitcoins-capacity-hasnt-seen/