QIP: 0008 Title: The Numerical Way of Calculating Online Confirmation Times in SPECTRE Author: Zhixiang Zhu <[email protected]> Category: Core Status: Draft Created: 2019-05-05
Qitmeer adopts PHANTOM and SPECTRE as the core concensus protocol. However, the SPECTRE paper is hard to read and understand from developers' or implementors' perspectives. Therefore, it is not easy to find out the explicit algorithm or formula to calculate the exact confirmation time of a block. This proposal tries to solve the problem by focusing on describing the method to calculate confirmation times.
The SPECTRE paper provides two ways of accepting (confirming) a block, i.e. the offline way and the online way. The online way is more straightforward. The simulation results of the paper also adopted the online way. This proposal adopts the same way.
By adopting online confirmation policy, a mining node must keep online and maintain good connections with other nodes in the mining network before a block gains confirmation since the node received that block. This assumption is highly reasonable for many practical scenarios, e.g., a cashier serving a continuous line of customers. The main benefit of the online version is that it relies on a tighter analysis, and therefore accepts transactions slightly faster.
If the mining node may become offline before the received node gains confirmation, the node should adopt offline policy to confirm the acception of the block. The offline policy will be described in another proposal.
When a node v receives a block x, it loops to calculate a risk value of the block with Algorithm 7 in the SPECTRE paper. It accepts the block when the risk is smaller than a given threshold ϵ. The online confirmation time of block x in node v is the time since x is received by v until x is accpeted by v.
Figure 1. Algorithm for checking whether to accept a block. Correction: The Gx at the end of line 4 should be Gtv.
The definition of risk_hidden(T, g) in the algorithm appears in formula (45)-(46) in the SPECTRE paper. It upper bounds the probability that block x is preceded by some attacker’s block y in pairwise order, where y is published later than x. The formula is defined as follows:
Figure 2. The definition of risk_hidden.
where
-
d is the upper bound on the recent delay diameter in the network,
-
α is the attacker’s relative computational power,
-
λ is the block creation rate,
-
Poiss(a, b) is defined as e-aab/b!,
-
x+ is defined as max{0, x},
-
and π is the stationary distribution which we will explain below.
π is actually a vector. Informally, it is the statistical distribution of how much more blocks attacker nodes have created than honest nodes have created since block x is published, which is called gap in the SPECTRE paper. π(l) is the probability that the value of gap is l.
The value of gap changes as time goes on, forming a random walk which induces an ergodic Markov chain. Theorietically, it could be any integer ranging from negative infinity to positive infinity. In the worst case, it is always non-negative. Only when the gap is non-negative is there a risk for block x to be received less or equal votes than some attacker’s block y which is published later than x, so that y precedes x in pairwise order. This is why in the formula of risk_hidden the index l, i.e. the value of gap, starts out equal to 0 instead of negative infinity.
Since the random walk of l induces an ergodic Markov chain, l has a unique stationary distribution, which is π. In order to calculate π, we need to calculate the transition probability matrix of the random walk.
Suppose that the value of l ranges from 0 to N, where N is infinity in the above definition. We define the transition probability matrix as an N by N matrix T. We also denote by δ := α · λ · d. For all 1 ≤ l < N - 1, Tl-1,l = 1 - α, Tl+1,l = α, and for l = N - 1: Tl-1,l = 1 - α, Tl,l = α. The first column of the matrix is defined by: T0,0 := (1 - α) · e-δ, T1,0 = e-δ · α + e-δ · δ, for 1 < l < N - 1: Tl,0 = e-δ · δl/l!, and TN-1,0 = 1 - e-δ · (δ0/0! + δ1/1! + … + δN-2/(N-2)!). π is the eigenvector of T corresponding to the eigenvalue 1, where π(l) ≥ 0 and the sum of π is 1.
In practice, π(l) is very close to zero when l is very large, so we can just pick some N ≫ 1 instead of infinity. Therefore, the formula of risk_hidden becomes
Figure 3. The definition of risk_hidden where l ranges from 0 to N.
It is recommended to calculate π with some well-tested Markov chain library such as the markovchain package in R.
The sum of series with index m seems to be a sum of infinite series. However, for m > g - l we
have (g - l - m)+ = 0 and .
Therefore, the formula of risk_hidden can be further converted as blelow, where Poisscdf is the cumulative distribution function (CDF) of Poisson distribution.
Figure 4. The converted formula risk_hidden.
With the converted formula we are able to calculate risk_hidden in numerical way. We provide our implementation with R: https://github.com/Qitmeer/spectre-poc/blob/master/risk_hidden.R