-
Notifications
You must be signed in to change notification settings - Fork 0
/
model.tex
142 lines (116 loc) · 12.1 KB
/
model.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
\chapter{Model}\label{chap:model}
In order to study the relationship of networking effects and selfish mining, it is essential to capture network properties in an analytic model. The model can then be used to estimate selfish mining profitability in dependence of assumed parameters.
\section{Bitcoin Mining Fundamentals}
To understand selfish mining and its implications on network behavior, it is essential to understand Bitcoin mining in general.
Bitcoin utilizes a proof-of-work blockchain as a distributed ledger technology.
It includes transactions into so called blocks. Each block possesses a unique ID and references a previous block~\cite{tschorsch}. This construct builds a directed acyclic graph rooted in the genesis block.
A correct block includes a nonce, which solves the cryptographic proof-of-work puzzle. The challenge is to alter the nonce until the hash of the set of transactions, the hash of the previous block, and the nonce produce a partial hash collision. Essentially, the hash has to be smaller than some threshold value, which is also referred to as difficulty~\cite{tschorsch}.
Thus, Bitcoin binds block creation to the computational resources a peer possesses, since the partial hash collision can only be solved through trial and error. The correctness of the block is easily verifiable through third parties. Thus, Bitcoin ensures a fair leader election through this process.
Bitcoin uses a peer-to-peer network to propagate the mined blocks in the system. The network is unstructured as every peer tries to maintain a minimum of eight connections and performs neighbor discovery over DNS and by asking neighbors~\cite{tschorsch}. Blocks are propagated over the peer-to-peer layer through flooding.
Once a miner finds a proof-of-work solution, he can publish the block and receives rewards through transaction fees and mining rewards. This provides an incentive for the miner to generate as many correct blocks as possible~\cite{1}.
Consensus is established over the longest chain rule~\cite{1}. This means that the block ending the longest chain determines the state of the blockchain. This also implies that a miner only receives rewards, if his mined blocks are included in the main chain. Thus, a miner wants to produce as many correct blocks, that are part of the main chain, as possible. A protocol maximizing reward gain is thus incentive compatible.
A miner produces a share of blocks proportionally to his relative share of computational power of the whole network. Thus, a miner should produce a share of the main chain proportional to his relative share of computational power.
The original protocol, in the following also referred to as honest mining, assumes publishing blocks immediately after mining. Honest mining is assumed to be incentive compatible~\cite{1}. It follows, that no miner can earn disproportionate rewards by deviating from the protocol.
Consequently, earning disproportionate rewards through deviation from the honest mining protocol would disprove Bitcoin's incentive compatability claim.
\section{Selfish Mining}\label{eyalmodel}
One protocol deviation is selfish mining, which was first introduced by \citeauthor{eyal}~\cite{eyal}.
Selfish Mining is a vulnerability which aims at increasing revenue through block withholding. The selfish miner aims at producing a greater share of blocks in the main chain than his relative share of computational power of the network. Therefore, selfish mining violates Bitcoin's incentive compatibility claim, as it offers a more profitable mining protocol than honest mining. This is problematic, since it not only breaks fair leader election, but also results in potentially longer confirmation times for transactions of users.
~\citeauthor{eyal} model the network over a set of miners. Each miner finds a subsequent block after a time interval that is exponentially distributed~\cite{eyal}. They further define the revenue of a miner as his fraction of total blocks on the longest chain.
The selfish miner withholds mined blocks~\cite{eyal}. This selfish miner now possesses a private chain, which differs from the publicly known chain. Based on the difference between those two chains, the selfish miner performs actions.
\begin{figure}[t]
\begin{center}
\resizebox{.5\columnwidth}{!}{%
\begin{tikzpicture}
\node[sm circ] (0) {$0$};
\node[sm circ] (1)[right=1.2cm of 0] {$1$};
\node[sm circ] (2)[right=1.2cm of 1] {$2$};
\node[sm circ] (4)[above=0.5cm of 0] {$0^{\prime}$};
\draw [arrow] (0.east) -- node[pos= 0.5, anchor=south] {\tiny $Mining$}(1.west);
\draw [arrow] (1.north) |- node[pos=0.5, anchor=south] {\tiny $Competition$ $Publish$}(4.east);
\draw [arrow] (2.south) -- +(0,-0.4) -| node[pos=0.3, anchor=south] {\tiny $Lead$ $Publish$}(0);
\draw [arrow] (1.east) -- node[pos= 0.5, anchor=south] {\tiny $Mining$}(2.west);
\draw [arrow] (4) -- node[pos=0.3,anchor=west] {\tiny $Publish/Adopt$}(0);
\end{tikzpicture}
}
\end{center}
\caption{Abstract representation of state transtitions of eyal and sirer model for one selfish miner}
\label{fig:eyal_model}
\end{figure}
For clarification the state space and actions are modelled in Figure~\ref{fig:eyal_model}. The numbers in the states indicate the lead of the private to the public chain, where $s$ denotes the lead of the private chain compared to the public chain. We can identify a total of five different actions.
\begin{itemize}
\item $Mining$: This action means that the peer has mined a block. Mining adds the block to the private chain. It therefore causes $s$ to increase.
\item $Lead$ $Publish$: When $s$ increases to 2, the selfish miner will publish his private chain. It therefore causes $s$ to change from 2 to 0.
\item $Competition$ $Publish$: When $s$ is 1 and the selfish miner receives a block from another peer, he will publish his block of the same height from the private chain instead of the received one, to compete against the other miner. This causes a state transition to $0'$.
\item $Publish$: If the selfish miner is in state $0'$, he is in a competition situation.
The selfish miner will immediately publish his next mined block. This will cause the selfish miner to transition to state $0$.
\item $Adopt$: The selfish miner will adopt the main chain once he receives a new block in a competition situation.
\end{itemize}
Executing this protocol leads to a strict revenue increase, if the mining power is greater than $33\%$ according to \citeauthor{eyal}~\cite{eyal}.
\paragraph{Network Propagation Factor}\label{netpropfac}
\cauth{eyal} also introduced a selfish mining focused network metric, called $\gamma$. $\gamma$ is measured in competition publish situations~\ref{eyalmodel}. In a competition publish situation two competing blocks are propagated through the network. An honest peer will adopt the first block increasing his blockchain height. $\gamma$ describes the computational power fraction of the network the selfish miner block reaches before the other block. This is an advantage since now the selfish miner and the fraction he reached first start mining together on a consecutive block, securing the selfish miners block in the main chain while the competing block remains a fork.
\section{Blockchain Gossip Model}\label{gopalan}
The Blockchain Gossip Model of \citeauthor{gopalan} consists of a set of peers $P$ connected through a peer-to-peer network. Peers add blocks to the blockchain through a process called mining.
The peer-to-peer network is modelled as an undirected Graph $H = (V,E)$.
An edge $(i,j) \in E$ represents communication possibilities between $v_i \in V$ and $v_j \in V$.
The set of vertices is finite, such that $|V|=N \in \mathbb{N}$.
Vertices are associated with peers, such that $v_i$ represents peer $p_i \in P$.
Additionally, a directed acyclic graph $G_{p_i}(t) = (B_{G_{p_i}}(t),E_{G_{p_i}}(t))$ is associated with each peer $p_i$, at each point in time $t \in \mathbb{R+}$.
The vertex set $B_{G_{p_i}}(t) \subset \mathbb{N}$ represents the blocks known of peer $p_i$ at time $t$. The associated edge set of $E_{G_{p_i}}(t)$ represents references between blocks.
The following holds true for shorter notations:
\begin{equation}
B_G(t) = \cup_{i=1}^N B_{G_{p_i}}(t) \texttt{ and } E_G(t) = \cup_{i=1}^N E_{G_{p_i}}(t)
\label{unisondef}
\end{equation}
Furthermore, the following equations hold for the principle of blockchains:
\begin{equation}
\forall p \in P: G_{p_i}(0) = (\{0\},\emptyset)
\label{genesis}
\end{equation}
\begin{equation}
t_1 < t_2 \rightarrow B_{G_{p_i}}(t_1) \subseteq B_{G_{p_i}}(t_2)
\label{nodegrow}
\end{equation}
\begin{equation}
t_1 < t_2 \rightarrow E_{G_{p_i}}(t_1) \subseteq E_{G_{p_i}}(t_2)
\label{edgegrow}
\end{equation}
Note that in this representation $0$ denotes the genesis block described in Equation~\ref{genesis}.
$G_{p_i}(t)$ evolves over time. Blocks arrive over continuous time according to a stationary point process $A$ with intensity $\lambda$. Each block $b \in \mathbb{N}$ arrives at a random peer $p_i$.
This models peer $p_i$ mining block $b$ at time $t$ and that at this time the block is also added to $B_{G_{p_i}}(t)$.
References are added to $E_{G_{p_i}}(t)$ according to policy and depending on $G_{p_i}(t^-)$, where $t^-$ is a moment in time infinitesimally before $t$. $O_i$ denotes the set of outgoing neighbors of block $i$.
The communication is modelled as a marked point process $T_{p_i}$.
Each mark corresponds to another peer $p_j \in P\backslash \{p_i\}$.
In an epoch peer $p_i$ contacts $p_j$ and thus, adds the lowest numbered block of $B_{p_i}(t)\backslash B_{p_j}(t)$ to the set of Vertices $B_{p_j}$. If $B_{p_i}(t)\backslash B_{p_j}(t)$ is not empty, $E_{p_j}$ is also updated accordingly.
The peer-to-peer network dynamics are modelled as a continuous time rumor-spreading process with exogenous arrivals~\citep{gopalan}. Since communication is bound to the process $T_{p_i}$, the block dissemination is bandwidth limited.
Reference selection and thus $O_{p_i}$ is chosen according to longest chain policies~\citep{gopalan}.
Let $L_{p_i}(t)$ denote the set of blocks farthest away from the genesis block $0$, known to peer $p_i$ at time $t$.
\begin{equation}
L_{p_i}(t) := \{j \in B_{p_i}(t): d(j,0)\geq d(j',0), \forall j' \in B_{p_i}(t) \}
\label{policy}
\end{equation}
Let $max\_ dist(G_{p_i}(t))$ denote that distance.
Note that the set $O_{p_i} \cap L_{p_i}(t)$ is non empty. This constructs a simple directed acyclic graph. The Tree Policy~\citep{gopalan} can then be determined as $|O_{p_i}|=1$ and establishes the following relationship:
\begin{equation}
|E_{G_{p_i}}(t)| = |B_{G_{p_i}}(t)| -1
\end{equation}
Every block will have exactly one outgoing reference, according to a deterministic rule~\citep{gopalan}. \citeauthor{gopalan} assume that the block with the lower index number will be chosen.
\begin{figure}[t]
\centering
{\renewcommand{\arraystretch}{1.5}
\begin{tabular}{|c|c|}
\hline
\textbf{Key Elements} &\textbf{Short Description}\\
\hline
$G_{p_i}(t)$ & \footnotesize Blockchain graph representation consisting of $(B_{G_{p_i}}(t),E_{G_{p_i}}(t))$ for every peer, time variant\\
$B_{G_{p_i}}(t)$ & \footnotesize Blockset of each peer, time variant\\
$E_{G_{p_i}}(t))$ & \footnotesize Edgeset of each peer, time variant \\
$T_{p_i}$ & \footnotesize The communication process for each peer, sends blocks from $p_i$ outwards\\
$L_{p_i}(t)$ & \footnotesize The set of blocks farthest away from the genesis block\\
\hline
\end{tabular}
}
\caption{Overview of Key Model Elements}
\label{OverviewElements}
\end{figure}
To sum up we have given a short overview of important key elements of the model introduced by \gopalan in Table~\ref{OverviewElements}.
Bitcoin's mining protocol has the goal of fair leader election. However, deviating mining protocols show vulnerabilities in the incentive system. The above section introduced a model to analyze network properties of blockchain systems in an analytical manner. Additionally, it discussed adversarial mining protocols and the model they have been analyzed on. The next section will develop a new model, based on the Blockchain Gossip Model introduced by \gopalan. This model can then be utilized to also analyze adversarial mining strategies, such as selfish mining.