{'fraction_non_alphanumeric': 0.034250960307298337, 'fraction_numerical': 0.013036899080433012, 'mean_word_length': 4.494883274704189, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Effect of Bitcoin fee on transaction-confirmation process

In Bitcoin system, transactions are prioritized according to transaction fees. Transactions without fees are given low priority and likely to wait for confirmation. Because the demand of micro payment in Bitcoin is expected to increase due to low remittance cost, it is important to quantitatively investigate how transactions with small fees of Bitcoin affect the transaction-confirmation time. In this paper, we analyze the transaction-confirmation time by queueing theory. We model the transaction-confirmation process of Bitcoin as a priority queueing system with batch service, deriving the mean transaction-confirmation time. Numerical examples show how the demand of transactions with low fees affects the transaction-confirmation time. We also consider the effect of the maximum block size on the transaction-confirmation time.


Introduction
Bitcoin is a digital currency system that was invented by Satoshi Nakamoto in 2008 [14]. Unlike the existing online payment systems such as credit cards and debit ones, a remarkable feature of Bitcoin system is its decentralized nature. Bitcoin does not have a central authority to manage Bitcoin transactions. All the Bitcoin transactions are registered in the ledger called blockchain, and the blockchain is maintained by a volunteer-based peer-to-peer (P2P) network. Volunteer nodes joining the P2P network hold the same replica of the blockchain, which enables everyone to check consistency of transactions.
From information-technology point of view, Bitcoin is fast, secure, and has lower fees than the existing payment schemes. These features make Bitcoin advantageous for both consumers and retailers. Due to low fees for processing transactions, Bitcoin is expected to accelerate the use of micro payment such as buying daily items and small amount remittance.
Every transaction needs to be stored into a block that a volunteer node, called miner, creates, and the block needs to be appended to the tail of the blockchain when a miner succeeds in creating the block. An average time interval of block creation is adjusted to be about 10 minutes. Only transactions in blocks included in the blockchain are admitted as valid ones, which are called confirmed transactions. It is said that to avoid double-spending, if the user receives the coin in a transaction, he/she should wait to use it until the block including the transaction and some subsequent blocks are created [24].
When a sender creates a transaction, he/she can make the transaction include a fee, which can be received by the miner who creates a block that stores the transaction. There is no incentive for miners to store transactions without fee into the block they are creating. Since the Bitcoin system restricts the number of transactions which a block can hold, miners may put a higher priority on transactions with a larger fee. Therefore, the transaction-confirmation time of transactions with a small fee tend to be much larger than those of ones with a large fee.
Note that in micro-payment case, the fee amount of micro-payment transactions is likely to be small due to its small amount remittance. If the use of micro payment becomes popular in the future, the confirmation time of transactions with small fees will be too long for users to make micro payment.
In this paper, we consider how the growth of micro payment affects the confirmation process of small amount transactions. We collect statistics from the blockchain, investigating the transaction-confirmation time. Then we model the transaction-confirmation process of Bitcoin as a queueing system with bulk service and priority mechanism, deriving the mean transaction-confirmation time for each-priority transaction. In numerical examples, we show how the transaction-confirmation time is affected with the increase in demand of micro payment.
The rest of the paper is organized as follows. We briefly review the related work in Section 2. Section 3 shows a summary of Bitcoin system, mainly focusing on the blockchain construction and the impact of transaction fee on the transaction-confirmation process. Section 4 shows some statistics about Bitcoin, some of which are used in the later experiments. In Section 5, we describe the queueing model for the confirmation process of Bitcoin system, and the analysis of the queueing model is presented. In Section 6, we show some numerical examples, discussing the effect of the demand of transactions with low fee on the confirmation time of transactions. Concluding remarks are given in Section 7.

Related Work
Recently, Bitcoin has attracted considerable attention, and been widely studied in various research communities. For example, the economic community studies Bitcoin system from the virtual-currency point of view. The aspects of applications of encryption and P2P networking are of interest in computer science [8]. The community of social science focuses on the incentive mechanism of Bitcoin ecosystem. Comprehensive reviews in terms of technology principles, history, risks and regulatory issues are well provided in [4,19,5]. Almost all papers on Bitcoin are introduced in [23]. Here, we present only papers close to our research.
One of important issues in Bitcoin is transaction fee. It is expected that transaction fees become incentives for miners to provide much computation power in order to verify transactions. The authors of [13] investigate the trends of transaction fees by analyzing 55.5 million transaction records, revealing the regime shift of Bitcoin transaction fees. It is shown that transactions with nonzero fee are likely to be processed faster than those with zero fee, and that the amount of fee doesn't affect the transaction latency significantly. In terms of the latter claim, however, their statistical analysis shows the tendency that transactions with small fee are likely to wait longer than those with large fee.
Another important issue is the maximum block size. Currently, the maximum block size is limited to 1 Mbyte due to a security reason of spam attack [15]. It is reported in [25] that Bitcoin handles at most seven transactions per second (tps) due to the maximum block size of 1 Mbyte. In order for Bitcoin to scale to tens of thousands of tps, which is equivalent to the processing speed of credit card transactions, enlarging the maximum block size is considered. There exist many discussions about the effect of the maximum block size on the incentive of miners. To the best of the authors' knowledge, however, there is no work for quantitatively investigating the impact of the enlargement of the maximum block size on the transaction-confirmation time.
Block confirmation time also affects the scalability of Bitcoin. Sompolinsky and Zohar [16,17] propose a modification to the blockchain, called GHOST, so that block confirmation time becomes about 600 times shorter than the original Bitcoin without loosing the security of Bitcoin. Kiayias and Panagiotakos [12] show a formal security proof and the speed-security tradeoff of GHOST. A security issue about shortening block confirmation time is double spending, which is studied in [3,10].
The block-construction process can be modeled as a queueing system with batch service, in which a group of customers leave the system simultaneously at service completion. There exist literature for the analysis of queues with batch service. Chaudhry and Templeton consider an M/G B /1 queueing system with batch service [6,7]. In M/G B /1, customers arrive at the system according to a Poisson process, the number of servers is one, and the service time distribution follows a general distribution. If there exist customers in queue at a service completion, the server accommodates customers as a batch, where the batch size is limited to some constant. Using supplemental variable technique, the authors derive the joint distribution of the remaining service time and the number of customers in queue. In [6,7], however, the priority mechanism is not taken into consideration. To the best of the authors' knowledge, priority queueing system with batch service has not been fully studied yet. In this paper, we model the transaction-confirmation process of Bitcoin as a queueing system in which both priority mechanism and batch service are taken into consideration.

Summary of Bitcoin System
In this section, we give a brief summary of Bitcoin system. The readers are referred to [2] for details.

Transaction Confirmation Process
The Bitcoin system realizes virtual currency with two types of information data: transactions and blocks. A transaction is the base of value transfer between payer and payee, while a block is a data unit for storing several confirmed transactions.
When a payer makes payment to a payee in Bitcoin system, the payer issues a transaction into the Bitcoin P2P network. The transaction contains the amount of payment, the source account(s) of the payer, the destination account(s) of the payee, and the fee that the payer pays to a miner (and the others). The transaction is propagated through the P2P network, and temporally stored in memory pool of volunteer nodes, called miners.
The role of miner nodes is to generate a block, which contains transactions to be validated. Miners try to solve a mathematical problem based on a cryptographic hash algorithm for block generation (referred to as proof-of-work [14]). The miner who finds its solution first becomes a winner, and is awarded reward 1 , which consists of some fixed value called coinbase and the fees of transactions included in the block, and the right to add a new block to the blockchain. The solution to the problem is included in the new block, and the miners try again to solve a new mathematical problem for the next block. This competition process is called mining. Embedding the solution for the current block to the next block plays an important role for preventing from falsification of previous blocks. The difficulty of problems in Bitcoin mining is automatically adjusted by the system so that the time interval between consecutive block generations is 10 minutes on average.
Since miners do not gain any profit from transactions without fee and the total size of transactions that a block can store is limited to 1 Mbyte in the Bitcoin system, some miners may ignore such transactions. Therefore, it is considered that the transaction-confirmation time of transactions without fee is much bigger than those of ones with fee.
In [13], the authors study trends of Bitcoin transaction fee conventions by analyzing the transaction fees paid with 55.5 million transactions recorded in the blockchain. They find that the confirmation time of transactions without fee are longer than those with fee. It is also reported that difference between transaction-confirmation times for different fees are not significant. In terms of the latter claim, however, their statistical analysis reveals that transactions with fee of 0.0005 are likely to wait longer than those with fee of 0.001. (See Table  Table 1 [13].) If the demand of transactions for micro payment increases in future, those transactions may suffer from a very long confirmation time because payers of micro payment are not willing to pay fee and the resulting priority of their transactions is low.

Bitcoin Transaction Statistics
In this section, we show some statistics of Bitcoin blocks and transactions. We collected data of blocks and transactions from blockchain.info [22]. We chose the two-year mining period from October 2013 to September 2015. Table 1 shows statistics of block-generation time. The statistics are calculated from 115,921 blocks in the measurement period. In this table, the mean block-generation time is 544.09 s, approximately 9 minutes. This is smaller than 10 minutes, the average time interval between consecutive block generations. This result, however, supports that Bitcoin mining is managed according to the system protocol. Table 2 shows the number of transactions in a block. Here, we count not only transactions issued by users, but also coinbase transactions. The mean number of transactions in a block is 529.27, and hence the mean rate of transaction processing is 1.05 transaction/s. Table 3 shows the statistics of the transaction size in byte. The mean transaction size for the two-year period is 571.34 bytes. Since the maximum block size is 1 Mbyte, we can roughly approximate the maximum number of transactions in a block equal to 1750.3.

Basic Statistics
In order to investigate the impact of transactions with small fee on the transaction-confirmation time, we classify transactions into priority classes. Remind that the confirmation time of transactions with a small fee are longer than those with a large fee [13]. This implies that transactions without fee are given  the lowest priority for the block-inclusion process. Therefore, we classify transactions into two types, high (H) and low (L), in terms of the amount of fee added to a transaction. Transactions with fee greater than or equal to 0.0001 BTC 2 are classified into H class, while those without fee smaller than 0.0001 BTC are prioritized as L class. We show the cumulative frequency of the fee amount for transactions in Table 4. Table 5 shows the statistics of transactions by type. Here, classless indicates the statistics for all the transactions, and TCT is the transaction-confirmation time. The mean arrival rate is the number of transactions per day. In this table, the mean transaction-confirmation time for the overall transactions is 1,075.0 [s] ≈ 17.917 minutes, almost twice greater than the mean block-generation time.
In terms of priority-type statistics, the mean transaction-confirmation time for L class is greater than that for H class, and its difference is 2,870.0 [s] ≈ 47.833 minutes. Figure 1 illustrates how the fee-amount distribution changes over time. The fee-amount distribution is the ratio of the amount of H/L-transactions to that of transactions issued in one day. Each region in Figure 1 shows the percentage of transactions in two different classes.

Fee-amount distribution and transaction-arrival rate
In Figure 1, the percentage of each class fluctuates in a small range, except that L-class has a spike from July 2015 to October 2015. It is reported in [22] that the number of transactions per day exhibits a rapid increase during the  same period. From these observations, we can claim that the percentages of H and L classes remain almost the same even though the volume of transactions increases rapidly. Figure 2 represents the transaction-arrival rate of each class. The horizontal axis is day, and its origin is October 1, 2013. We observe in this figure that the transaction-arrival rate of each class gradually increases with fluctuation over time. The exceptional spikes are observed in the range of 650 to 730, the same period in Figure 1.
From these figures, we can expect that the transaction-arrival rate monotonically grows, keeping the same percentage of fee-amount class.

Priority Queueing Analysis
This section describes our queueing model of Bitcoin transaction processing and main results of transaction-confirmation time. The detailed derivations are presented in Appendix A.

Mean Transaction-Confirmation Time
Let S i denote the ith block-generation time. In this paper, we regard a block-generation time as a service time. We assume {S i }'s are independent and identically distributed (i.i.d.) and have a distribution function G(x). Let g(x) denote the probability density function of G(x). The mean block-generation time E[S] is given by A transaction arrives at the system according to a Poisson process with rate λ. Transactions arriving to the system are served in a batch manner. A batch service starts when a transaction arrives at the system in idle state. The consecutive transactions arriving at the system are served in a batch until the number of batch size equals b. That is, newly arriving transactions are included into the creating block as long as the resulting block size is smaller than the maximum block size b. This assumption follows from the behavior of the default Bitcoin client described in [2].
Let N (t) denote the number of transactions in system at time t, and X(t) denote the elapsed service time at t. We define P n (x, t) (n = 1, 2, . . . , x, t ≥ 0) and P 0 (t) as 3 3 We follow the definition of Pn(x, t) in [6,7]. Rigorously, we define Pn(x, t) as assuming it exists.
Note that P n (x, t)dx is the joint probability that at time t, there are n transactions in system and the elapsed service time lies between x and x + dx. We also define limiting distributions P n (x) = lim t→∞ P n (x, t) and P 0 = lim t→∞ P 0 (t).
Let ξ(x) denote the hazard rate of S, which is given by .
Let T denote the sojourn time of a transaction. In the context of Bitcoin, T is the transaction-confirmation time, i.e., the time interval from the time epoch at which a user issues a transaction to the point when the block including the transaction is confirmed. Then, we have the following theorem.

Theorem 1. The mean transaction-confirmation time E[T ] is given by
where Proof. See Appendix A.1.

Transaction-Confirmation Time for Priority Queueing Model
In this subsection, we consider the system in which transactions are prioritized for the inclusion to a block, deriving the mean transaction-confirmation time for each priority class.
We assume that transactions are classified into c priority classes. For 1 ≤ i, j ≤ c, i class transactions have priority over transactions of class j when i < j. Let λ i (i = 1, 2, . . . , c) denote the arrival rate of i-class transactions. We assume that c i=1 λ i E[S] < 1. We define T i as the sojourn time of class i transactions. For simplicity, we introduce the following notation Assuming that the system is work conserving, we have the following theorem. In the following section of numerical examples, we consider two priorityclass case: high and low. Let λ H and λ L denote the arrival rate of high-priority transactions and that of low-priority ones, respectively. Let also T H and T L denote the sojourn time of high-priority transactions and that of low-priority ones, respectively. In this two priority-class case, we obtain

Numerical Examples
In this section, we show some numerical examples obtained from the analytical results in previous section. First, we consider the distribution of blockgeneration time with a simple mining model. Then, we show the transactionconfirmation times of H-and L-class transactions, investigating how the transactionarrival rate and the block size affect the performance measure.

Distribution of block-generation time
In order to calculate the mean transaction-confirmation time, we need to determine G(x), the distribution of the block-generation time. In [9], the authors claim that the block-generation time is exponentially distributed. They consider a hash calculation by a miner node as a Bernoulli trial, which is independent of previous hash calculations. This yields that the number of experiments for the first success is given by geometric distribution, and hence it can be approximated by exponential distribution. In Appendix B, we show an alternative approach to the block-generation time distribution with extreme value theory.
In subsection 4.1, we showed that the mean block-generation time is 544.09 [s]. That is, the mean block-generation rate is 1.8379 × 10 −3 . In the following, we assume that the block-generation time S follows the exponential distribution given by where µ = 1.8379 × 10 −3 .
In Figure 3, we plot the relative frequency of the block-generation time obtained from the measured data, and the probability density function of the above exponential distribution. The horizontal axis represents the block-generation time in second, and the vertical axis is the logarithmic scale of the frequency  values. This figure shows a good agreement between the measured data and exponential distribution. The Laplace-Stieltjes transform (LST) of G(x) is given by With the above setting, we calculate mean sojourn times of transactions in previous section.

Verification of analysis
In order to validate the analysis in section 5, we conducted discrete-event simulation experiments. The simulation model is the same as the priority queueing one described in section 5. We developed a simulation program with C++, and generated 50 samples for one estimate of the transaction-confirmation time, calculating the 95% confidence interval. Figure 4 represents the analytical and simulation results of mean transactionconfirmation times for H and L classes. Here, we set b = 1000, and the horizontal axis is the overall arrival rate λ, given by λ = λ H + λ L . We increase λ, keeping  the ratio of λ H to λ L constant. More precisely, let ζ denote the ratio of λ H to λ L . From Table 5, we set ζ as ζ = λ H λ L = 0.90466 0.068082 = 13.288.
By using ζ, λ H and λ L are described as With λ H and λ L , we calculate E[T H ] and E[T L ] as the function of λ. Figure 4 shows overall good agreement between the analysis and simulation for both H and L classes. Remind that E[T i ]'s given in Theorem 2 (and hence E[T H ] of (2) and E[T L ] of (3)) are approximations. Figure 4 suggests that our approximation analysis becomes exact when the block-generation time is exponentially distributed.
In the following subsections, we show the numerical results calculated by (2) and (3).

Comparison of analysis and measurement
Next, we compare analytical results of the transaction-confirmation time with measurement ones of Table 5. Table 6 shows the results of measurement and analysis for the transaction-confirmation time in three cases: classless, H class and L class. We calculate the transaction-confirmation time for classless case by (1), while we compute E[T H ] (resp. E[T L ]) from (2) (resp. (3)). In the analytical computation, we set b = 1750, which is an estimate obtained from Table 2.
In Table 6, the measurement value for classless case is almost twice larger than the corresponding analytical one. We also observe that discrepancies between measurement and analysis for H and L classes are large, and that the discrepancy for L class is significantly larger than that for H class.
First, we consider the reason of the discrepancy for classless case. In the previous subsection, we concluded that the block-generation time follows an exponential distribution with mean 544.095 [s]. Note that the arrival rate of classless case is 0.97275, and hence the system utilization ρ is ρ = λE[S] = 0.97275 × 544.095 = 529.27.
Since the maximum block size b is 1750, the system is not overloaded. In such a situation of low utilization, a newly arriving transaction is likely to be included in the block which is under the current mining process.
Remind that our analytical model follows the behavior of the default bitcoin client for updating the blockchain described in [2], that is, miners include newly arriving transactions into the creating block as long as the resulting block size is smaller than the maximum block size. The above comparison result implicitly means that a newly arriving transaction is not included in the block currently processed, but is included to the block following the currently processed block. This conjecture is supported by the fact that the block-generation time follows an exponential distribution. In the underloaded situation, the confirmation time of a newly arriving transaction consists of the remaining generation time of the block under mining and the generation time of the next block. Due to the memoryless property of exponential distribution, the remaining blockgeneration time also follows the same exponential distribution. This results in that the transaction-confirmation time is almost twice larger than the blockgeneration time.
Next, we consider the reason why the discrepancy between measurement and analysis for L class is larger than that for H class. In our analytical model, we assumed that L-class transactions in system are served as long as the block being in service is not occupied by H-class transactions. The large discrepancy between measurement and analysis for L class in Table 6 implies that L-class transactions in Bitcoin system are less served than the assumed priority queueing discipline. As we stated in introduction, there is little incentive for miners to build a block with transactions with small fees. This result suggests that there exist miners who intentionally exclude transactions with small fees from the block inclusion process. According to the above discussion, we can conjecture that miner nodes don't follow the behavior of the default bitcoin client, and that there may exist miners who never include transactions with small fees to a block.

Mean transaction-confirmation time: classless case
In this subsection, we show the mean transaction-confirmation time for classless case. Figure 5  Note that the case of b = 2000 approximately illustrates the transactionconfirmation time under the block-size limit of 1 Mbyte. The transactionconfirmation time rapidly increases when λ becomes greater than 3. Roughly speaking, the transaction-confirmation time becomes intolerable when the number of transactions issued in one second is greater than three. This is just the reason why the maximum block-size limit is an important issue for the scalability of Bitcoin.
Note also that b = 3000, 4000 and 5000 can be regarded as cases of the maximum block size equal to 1.5 Mbytes, 2 Mbytes and 2.5Mbytes, respectively. We can see that enlarging the maximum block size is effective to make the transaction-confirmation time small. Even when b = 5000, however, the transaction-confirmation time becomes worse around λ = 8. This result suggests that enlarging the maximum block size is not effective for the scalability of Bitcoin.

Mean transaction-confirmation time: two-priority case
In this subsection, we investigate how the priority mechanism in Bitcoin affects the transaction-confirmation time. We consider two scenarios in terms of the increase in the arrival rate of transactions. In the first scenario, λ L changes under a fixed λ H . This scenario illustrates the case in which the demand of micro payment grows independently. In the second scenario, on the other hand, we increase the overall transaction-arrival rate λ = λ H + λ L , keeping the ratio of λ H to λ L constant. This case corresponds to the growth of Bitcoin-user population. Figure 6 represents how the mean transaction-confirmation time is affected by the arrival rate of L-class transactions. In this figure, λ H is fixed at 0.90466, as shown in Table 5, and we plot five cases of b.

Impact of increase in L-class transactions
In Figure 6, E[T L ] for each b grows exponentially with the increase in λ L , while E[T H ]'s are almost the same and remain constant. This result shows that the priority mechanism provides a low transaction-confirmation time for H-class transactions, while L-class transactions are likely to suffer from a large transaction-confirmation time when the arrival rate of L-class transactions is high. Remind that the mean arrival rate of L-class transactions is 0.068082, and that the current maximum block size can be roughly approximated by b = 2000. Figure 6 indicates that if the arrival rate of L-class transactions becomes 30 times larger than 0.068082 (λ L ≈ 2) and the maximum block size  Figure 7 is slow, however, E[T H ] rapidly increases around λ = 9. This result indicates that increasing the maximum block size is not a fundamental solution for the scalability of Bitcoin.

Conclusion
In this paper, we analyzed the transaction-confirmation time for Bitcoin by queueing theory. We modeled the transaction-confirmation process as a singleserver queue with batch service and priority mechanism. Assuming that the priority of a transaction depends only on its input, we derived the mean confir that for the maximum block size of 1 Mbyte, transactions with small fees suffer from an extremely large confirmation time if the arrival rate of transactions whose fee is smaller than 0.0001 BTC becomes four times larger than the current arrival rate. We also found that enhancing the maximum block size is not an effective way to mitigate the transaction-confirmation time. Further study is needed for the scalability of Bitcoin.
the assumptions Intuitively, (A.1) is a balance equation in which the exiting rate from state 0 is equal to the entering rate into the same state. The first term in the right-hand side (r.h.s.) of (A.2) is derived from the event that the number of transactions does not change during a small time interval, while the second term is yielded from the event that a transaction arrives at the system with n transactions. We derive (A.3) in a similar manner. We also have the following boundary conditions Note that the left-hand side of (A.4) is the probability that there exist n transactions in system at the beginning of the service time. This event occurs just after the service completion in the state with n + b transactions. (Remind that b transactions are served simultaneously when the number of transactions in system is greater than or equal to b.) The equation of (A.5) can be derived in a similar manner, noting that the service with one transaction starts when a transaction arrival occurs at system in idle (the second term in the r.h.s. of (A.5)). The normalizing condition is given by We define the following probability generating functions (pgf's) where G * (s) is the LST of G(x) and given by For notational simplicity, we define α k (k = 1, 2, . . . , b) as From Rouche's theorem (see, for example, [18]), it is shown that the equation has b roots inside |z| = 1 + for a small real number > 0. One of them is z = 1. Let z * m (m = 1, 2, . . . , b − 1) denote the m-th root of (A.9) different from 1. Hence, from (A.8), we have the following From (A.11), P (z) is yielded as Substituting z = 1 into (A.8) yields Note that (A.13) holds if the following stability condition holds.
Substituting the above expressions into (A.12) yields The mean number of transactions in the system E[N ] is given by Let T denote the sojourn time of a transaction. Note that in Bitcoin case, T is the transaction-confirmation time. From Little's theorem, the mean sojourn time of a transaction E[T ] is yielded as .
Since E[T ] is a function of λ, we define f (λ) ≡ E[T ] for the following subsection.
Appendix A.2. Proof of Priority Queueing Analysis Consider a sample path in which a low-priority transaction arrives at the system in idle and starts a busy period. Consider also the other sample path in which a high-priority transaction arrives at the system in idle and starts a busy period. In our model, note that the elapsed service time of high-priority transaction in the former sample path is smaller than that in the latter one. This implies that our priority queueing model is not work conserving.
When the system utilization c i=1 λ i E[S] is large, however, the busy period becomes large and the idle state rarely occurs. In such high-utilization environment, the event that an low-priority transaction starts a busy period rarely occurs. Assuming that the system is work conserving [20], we have Note that for i < j, any class-j transactions don't affect the service of class-i transactions. In other words, T i is independent of transactions whose priority class is lower than i, and hence (A.17) holds not only c but also i = 2, 3, . . . , c−1. This yields We then obtain

Appendix B. Block-Generation Time Distribution
In this section, we prove that the block-generation time follows an exponential distribution.
Remind that each miner node tries to solve the mathematical problem based on a cryptographic hash algorithm. This problem consists of calculating a hash of the block being formed and adjusting a nonce word such that the resulting hash value is smaller than or equal to a targeted value called difficulty [19]. The number of nonce words the miner tries is tremendously huge, making the mathematical problem too difficult. Here, we assume that the number of nonce words is finite and equal to M .
When a miner tries one nonce word and finds it incorrect, the miner immediately tries the other word and never tries the same nonce again. We can model the mining process as the following urn model without replacement. That is, we have an urn containing M balls, of which M − 1 are white and one is red. The red ball is a winner. One ball is withdrawn from the urn at a time, and then it is removed from the urn without replacement. In this setting, the probability that the red ball is drawn at kth trial is 1/M , a discrete-uniform distribution. If one trial is performed at a unit time, the probability that the red ball is drawn at time k is also given by 1/M .
Suppose that there exist n miner nodes. Without loss of generality, we assume that the number of winning nonce words is one and that the number of nonce words is M . Let Y i (i = 1, 2, . . . , n) denote the time at which miner i finds a winning nonce word. We assume Y i 's are i.i.d. We define the block-generation time as L n . Then we have L n = min{Y 1 , Y 2 , . . . , Y n }.
For simplicity, we assume Y i follows a continuous-uniform distribution U (0, M ), that is, Then, the distribution of L n is yielded as Pr{L n ≤ x} = Pr{min(X 1 , . . . , X n ) ≤ x} = 1 − Pr{min(X 1 , . . . , X n ) > x} Now consider a limit distribution of (L n − b n )/a n for sequences of constants {a n > 0} and b n . In extreme value theory, it is known that the distribution of (L n − b n )/a n for the minimum of X i 's converges to a Weibull distribution when X i follows uniform distribution ( [11] p. 59, Table A.1).
From this result, for a large n, we can approximate the distribution of L n by Pr{L n ≤ x} ≈ 1 − exp{−(n/M )x}.
This result implies that L n follows an exponential distribution when n is large. Figure 3 in subsection 6.1 shows a good agreement between exponential distribution and measured data. According to [21], the number of miner nodes is about 5,700, and hence this number is large enough so that the block-generation time is well approximated by exponential distribution.