Transaction Confirmation Time

In what follows, we analyze the transaction confirmation time in Bitcoin (adapted from [1,11]). Recall that transactions are confirmed by means of a PoW, as shown in (3.1).

We start by noting the following observations:

• 1. The probability of success in a single-nonce trial is negligible. Since SHA-256 is a pseudorandom permutation function, each of the 2³² nonces has probability of satisfying the PoW.
• 2. Miners compute their PoW independently; therefore, the success probability of one miner does not depend on the progress of others.
• 3. Miners frequently restart the generation of their PoW and whenever a new transaction is added to the memory pool of a miner, the Merkle root (included in the block) changes.
• 4. The time interval, dt, between the announcement of successive transactions is in the order of a few tens of seconds.

Given the first two observations, the probability of a miner of succeeding in a single block generation attempt can be modeled as an independent Bernoulli process with success probability e = . Based on the last observation,

consecutive block generation attempts can be modeled as sequential Bernoulli trials with replacement. This claim is justified by the fact that the PoW progress invested by a miner (expressed as a number of hash calculations) prior to a PoW reset is negligible in comparison to 2²⁵⁶ — 1.²

Let Hi refer to the number of attempts that a miner performs within a time period S. The probability p_i of m _i finding at least one correct PoW within these trials is given by p_i = 1 — (1 — e)ⁿⁱ .Since e and n_i are small, p_i can be approximated to p_i = 1 — (1 — e)ⁿⁱ « n_ie. Therefore, the set of trials of m_i within S constitutes a single Bernoulli process with success probability n_ie.

Assuming that there are l miners, m_i, i = 1.. .l with success probability p_i, i = 1... l respectively, the overall probability of success in block generation can be approximated to:

This is true when pl C 1 and when the miners have equal computing power

(i.e., pi = p, i = 1 . . . l).

We divide time into equal-sized intervals of size S; let t₀ = 0 denote the time when the last block was generated. Here, each miner can make up to Hi trials for block generation within each interval. Let the random variable X_k denote the event of success in the time interval between t_k and t_k+1. That is,

It is clear that Prob(X_k = 1) = pr. We denote by Y, the number of attempts performed by miners until a success is achieved. Note that Y’s values are distributed according to the geometric distribution model since:

2 This is the case since the PoW progress approximates 2³⁵ ^ 2²⁵⁶ — 1 given the computing power of most Bitcoin miners [12,13].

Assuming a constant rate of trials per time window 6, the number of failures until a success is observed in block generation is proportional to the block generation time T.

Given this, we conclude that the distribution of block generation times can be modeled with a shifted geometric distribution with parameter pr [14]. In Figure 4.4, we sketch this distribution using parameters p = 0.19, and 6 = 60 seconds as advocated in [11]. Figure 4.4 shows that each block confirmation requires on average 10 minutes with a standard deviation of almost 20 minutes.