BlockDAG Throughput

To compare BlockDAG throughput with blockchain, I take Bitcoin and Etherum as the references in the following table, part of dag’s data comes from this presentation: https://youtu.be/57DCYtk0lWI at 32’.

type	$k$	$\mathbf{D}_{max}$	$δ$	$λ$	throughput	bandwidth	storage	block size	tx size
Bitcoin	0	15s	4.88%	1 Blk/600s	~3.33 txn/s	~1.667 KB/s	~0.15 GB/Day	1 MB	~0.5 KB
Ethereum	0	15s	86.47%	1 Blk/15s	~15 txn/s	~1.667 KB/s	~0.15 GB/Day	~25 KB	~0.1 KB
dag A	354	15s	1.0‰	10 Blks/s	1k txn/s	0.5 MB/s	~43.2 GB/Day	50 KB	0.5 KB
dag B	1621	15s	1.0‰	50 Blks/s	10k txn/s	5 MB/s	~432 GB/Day	100 KB	0.5 KB
dag C	48	15s	1.0‰	1 Blk/s	1M txn/s	500 MB/s	~43.2 TB/Day	0.5 GB	0.5 KB

Note:

• $k$: maximum allowed parallel creation of blocks
• $\mathbf{D}_{max}$: the time for a message to propagate to the entire network. Or ‘Network Diameter’.
• $λ$: block creation rate
• $δ$: probability of an honest block being marked red.

For Bitcoin, here we take 1MB block size before SegWit, and suppose bitcoin average transaction size is 0.5KB according to https://charts.bitcoin.com/chart/transaction-size

For Ethereum, here we use a roughly block size 25KB/block (actually, ethereum don’t have fixed limitation for block size but a block gas limitation, the maximum block size could be 46KB, 25KB is the rough average of 2018 according to https://etherscan.io/chart/blocksize). And we roughly suppose 15 transactions/second (Ethereum does roughly 10-30 transactions per second (TPS) according to https://etherscan.io/chart/tx )

About $\mathbf{D}_{max}$, according to a research paper on Information Propagation in the Bitcoin Network by Decker and Wattenhofer. The mean time for a node to see a block is 12.6 seconds. This paper gets some of the causes of propagation speed: “For blocks, whose size is larger than 20kB, each kilobyte costs an additional 80ms delay until a majority knows about the block.”, Block Size is a dominating factor.

In bitcoin, Sotoshi Nakomomo took the assumption that D (‘Network Diameter’) is much smaller than 10 minutes, and take λ as 1/600 so that $D \cdot λ \ll 1$.

There’s a very nice measurement for block propagation speed: http://bitcoinstats.com/network/propagation/. Based on its daily snapshot (from 22/11/2013 to 05/04/2017), I work out the mean value and fill into the following table:

Year	Block 50%	Block 90%	Transaction 50%	Transaction 90%
2013	4.6s	42.6s	1.4s	16.8s
2014	4.1s	23.6s	1.1s	9.1s
2015	5.6s	53.2s	0.9s	4.6s
2016	4.3s	27.8s	1.7s	8.6s
2017	2.4s	11.8s	3.4s	14.3s

Based on above data, and since the network is evolving at a breakneck pace, what was true yesterday might not be true tomorrow. We can simply take our assumption of $D_{max}$ as 15 seconds at following research.

In Phantom paper, k depends on the assumption of $D_{max}$ and δ, defined as follows:

$$ k(D_{max},δ) := min\left \lbrace \hat k∈\mathbb N: \sum_{j=\hat k+1}^\infty e^{-2 \cdot D_{max} \cdot λ} \cdot \frac{(2 \cdot D_{max} \cdot λ)^j}{j!} < δ \right \rbrace \tag{1}$$

This equation arises from a probability of events for a Poisson distribution( https://en.wikipedia.org/wiki/Poisson_distribution ). An event can occur 0, 1, 2, … times in an interval. The average number of events in an interval is designated (lambda). Lambda is the event rate, also called the rate parameter. The probability of observing k events in an interval is given by the equation:

$$ P(k\ events\ in\ internal) = e^{-λ} \cdot \frac{λ^k}{k!} $$
The equation $(1)$ is to calculate the probalility of, given that block A was created at time t, a event where more than k additional blocks have been created during [t-D,t+D].

Let’s write equation $(1)$ in another form:

$$ k(D_{max},δ) := min\left \lbrace \hat k∈\mathbb N: e^{-2 \cdot D_{max} \cdot λ} \cdot \Bigl(\sum_{j=\hat k+1}^\infty \frac{(2 \cdot D_{max} \cdot λ)^j}{j!}\Bigr) < δ \right \rbrace \tag{1.1}$$

We first start by noticing that the above equation can be simplified by the following math truth:
$$ e^x = \sum_{n=0}^\infty \frac{x^n}{n!} \tag{1.2}$$
So, we can get the following form to avoid the calculation of an infinite sum:
$$ \sum_{j=\hat k+1}^\infty \frac{(2 \cdot D_{max} \cdot λ)^j}{j!} = e^{2 \cdot D_{max} \cdot λ} - \sum_{j=0}^k \frac{(2 \cdot D_{max} \cdot λ)^j}{j!} \tag{1.3}$$

then, we can get the following form of this equation:

$$k(D_{max},δ) := min\left \lbrace \hat k∈\mathbb N: e^{-2 \cdot D_{max} \cdot λ} \cdot \Bigl( e^{2 \cdot D_{max} \cdot λ} - \sum_{j=0}^k \frac{(2 \cdot D_{max} \cdot λ)^j}{j!} \Bigr) < δ \right \rbrace$$
$$\tag{1.4}$$
Or in another form:

$$k(D_{max},δ) := min\left \lbrace \hat k∈\mathbb N: \Bigl(1 - \sum_{j=0}^k e^{-2 \cdot D_{max} \cdot λ} \cdot \frac{(2 \cdot D_{max} \cdot λ)^j}{j!}\Bigr) < δ \right \rbrace \tag{1.5}$$

Or in another form to put 1 on the right side:

$$k(D_{max},δ) := min\left \lbrace \hat k∈\mathbb N: \sum_{j=0}^k e^{-2 \cdot D_{max} \cdot λ} \cdot \frac{(2 \cdot D_{max} \cdot λ)^j}{j!} > (1 - δ) \right \rbrace \tag{1.6}$$

In case of an assumption of $D_{max}=15 seconds$ and $δ=1.0‰$, the map between $k$ and $λ$ as follows:

k	λ	$D_{max}$	δ
2	1/600	15s	1.0‰
8	1/15	15s	1.0‰
48	1	15s	1.0‰
189	5	15s	1.0‰
355	10	15s	1.0‰
517	15	15s	1.0‰
677	20	15s	1.0‰
1621	50	15s	1.0‰

According to above result, perhaps Bitcoin can make an evolving to BlockDAG with $k=2$, using smaller block size and decrease the block reward correspondingly，that will get up to triple Bitcoin transaction throughput; similiar case for Ethereum, evolving to BlockDAG with $k=8$ will get up to 9 times of transaction throughput, theoretically.

Here is a modified Python version based on Lexi Antea‘s source phantom_k.py, you can run it to verify the calculation:

from math import exp, log
from decimal import Decimal

Dmax = Decimal('15.0') # An upper bound on delay diameter, in seconds
lamb = Decimal('10.0')  # Block creation frequency, in hertz
delta = Decimal('0.001')  # Fraction of honest blocks marked red
oneMinusDelta = Decimal('1.0') - delta

# Calculates the factorial of integer n; returns a Decimal
fac= []
def fact(n):
    if n == 0:
        return 1
    elif n < 0:
        return NaN
    elif len(fac)>n:
	return fac[n]
    else:
        res = Decimal(1);
        for i in range(1,n+1):
            res = res*Decimal(i)
	fac.append(res)
        return res

# Calculates the (2*Dmax*lamb)^j
powj= []
def xpower(j):
    if j == 0:
	return 1
    elif j < 0:
	return NaN
    elif len(powj)>j:
	return powj[j]
    else:
    	temp = Decimal(2)*Dmax*lamb
	res = (temp**j)
	powj.append(res)
	return res

# Calculates the LHS of the expression
def val(k):
    temp = Decimal(2)*Dmax*lamb
    neg_temp = -temp
    s = 0
    for j in range(k+1):
        s += xpower(j)/fact(j)

    s *= neg_temp.exp()
    return s

k = -1
v = 0
while v < oneMinusDelta:
    k = k+1
    v = val(k)
    print("k=",k,"p=",1-v)

print("final result:")
print("k=",k,"p=",1-v)

(to be continued…)