American Institute of Mathematical Sciences

Advanced
May  2020, 16(3): 1077-1098. doi: 10.3934/jimo.2018193

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 Published  December 2018

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

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: Bitcoin, blockchain, transaction-confirmation time, priority queue.
Mathematics Subject Classification: Primary: 68M20, 90B22; Secondary: 60K25.
Citation: Yoshiaki Kawase, Shoji Kasahara. Priority queueing analysis of transaction-confirmation time for Bitcoin. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1077-1098. doi: 10.3934/jimo.2018193
References:
[1]

A. M. Antonopoulos, Mastering Bitcoin, O'Reilly, 2014. Google Scholar

[2]

M. L. Chaudhry and J. G. C. Templeton, The queuing system M/GB/1 and its ramifications, European Journal of Operational Research, 6 (1981), 56-60.  doi: 10.1016/0377-2217(81)90328-3.  Google Scholar

[3]

M. L. Chaudhry and J. G. C. Templeton, A First Course in Bulk Queues, John Wiley & Sons, 1983.  Google Scholar

[4]

http://www.meti.go.jp/committee/kenkyukai/sansei/fintech\_kadai/pdf/003\_02\_00.pdf Google Scholar

[5]

http://www.coindesk.com/1mb-block-size-today-bitcoin/ Google Scholar

[6]

https://blockchain.info/ Google Scholar

[7]

http://www.coindesk.com/segregated-witness-bitcoin-block-size-debate/ Google Scholar

[8]

S. Kasahara and J. Kawahara, Effect of Bitcoin fee on transaction-confirmation process, arXiv: 1604.00103[cs.CR]. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[11]

S. Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, 2008. Available from: https://bitcoin.org/bitcoin.pdf. Google Scholar

[12]

J. Poon and T. Dryja, The bitcoin lightning network: Scalable off-chain instant payments, https://lightning.network/lightning-network-paper.pdf, 2016. Google Scholar

[13]

H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation, Vol. 2. Finite systems. North-Holland Publishing Co., Amsterdam, 1993.  Google Scholar

[14]

https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki Google Scholar

[15]

F. Tschorsch and B. Scheuermann, Bitcoin and beyond: A technical survey on decentralized digital currencies, Tutorials, 18 (2016), 2084-2123.   Google Scholar

[16]

https://www.bitcoincash.org/ Google Scholar

[17]

https://www.coindesk.com/segwits-slow-rollout-bitcoins-capacity-hasnt-seen/ Google Scholar

show all references

References:
[1]

A. M. Antonopoulos, Mastering Bitcoin, O'Reilly, 2014. Google Scholar

[2]

M. L. Chaudhry and J. G. C. Templeton, The queuing system M/GB/1 and its ramifications, European Journal of Operational Research, 6 (1981), 56-60.  doi: 10.1016/0377-2217(81)90328-3.  Google Scholar

[3]

M. L. Chaudhry and J. G. C. Templeton, A First Course in Bulk Queues, John Wiley & Sons, 1983.  Google Scholar

[4]

http://www.meti.go.jp/committee/kenkyukai/sansei/fintech\_kadai/pdf/003\_02\_00.pdf Google Scholar

[5]

http://www.coindesk.com/1mb-block-size-today-bitcoin/ Google Scholar

[6]

https://blockchain.info/ Google Scholar

[7]

http://www.coindesk.com/segregated-witness-bitcoin-block-size-debate/ Google Scholar

[8]

S. Kasahara and J. Kawahara, Effect of Bitcoin fee on transaction-confirmation process, arXiv: 1604.00103[cs.CR]. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[11]

S. Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System, 2008. Available from: https://bitcoin.org/bitcoin.pdf. Google Scholar

[12]

J. Poon and T. Dryja, The bitcoin lightning network: Scalable off-chain instant payments, https://lightning.network/lightning-network-paper.pdf, 2016. Google Scholar

[13]

H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation, Vol. 2. Finite systems. North-Holland Publishing Co., Amsterdam, 1993.  Google Scholar

[14]

https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki Google Scholar

[15]

F. Tschorsch and B. Scheuermann, Bitcoin and beyond: A technical survey on decentralized digital currencies, Tutorials, 18 (2016), 2084-2123.   Google Scholar

[16]

https://www.bitcoincash.org/ Google Scholar

[17]

https://www.coindesk.com/segwits-slow-rollout-bitcoins-capacity-hasnt-seen/ Google Scholar

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as 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 $
Figure Options

Download full-size image

Download as 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 $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  The mean transaction-arrival rate
Figure Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as 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
Table Options

Download as excel

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
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
Table Options

Download as excel

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
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
Table Options

Download as excel

Period 1st
2013/10-2014/09		 2nd
2014/10-2015/09		 Overall
2013/10-2015/09
Classless 3.72401 15.32505 10.17893
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
Table Options

Download as excel

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
[1]

Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075
[2]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183
[3]

Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493
[4]

Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189
[5]

Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258
[6]

Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044
[7]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (341)
  • HTML views (1222)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences