-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcontribution.tex
152 lines (124 loc) · 16.2 KB
/
contribution.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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
\chapter{A Network-centric Model for Selfish Mining}\label{chap:contribution}
The goal of this thesis is to analyze the relationship between selfish mining and networking effects. The model proposed by \gopalan~ appears to be suitable to analyze this relationship. It offers networking effects because it is based on rumor spreading, as well as analytical properties, such as that it can be utilized to simulate the system execution time.
The first step to analyze the relationship between selfish mining and networking effects is to identify important system factors. Based on the model introduced by \gopalan, we develop a new model, the Selfish Rumor Model, which also includes adversarial behavior. Through the combination of a rumor-spreading model and an abstract blockchain mining protocol, the impact of networking effects on selfish mining can be studied.
\section{System Factors}
Under the assumption that adversarial mining strategies and network properties influence each other it is important to categorize those factors and characterize their interdependencies. Factors can be split up into local and global factors, as well as network and mining properties.
\begin{figure}[t]
\centering
\small
{\renewcommand{\arraystretch}{3}
\begin{tabular}{|c|c|c|c|}
\hline
&\textbf{Local Factors} &\textbf{Global Factors} &\textbf{Adversarial Factors}\\
\hline
\textbf{Network Factors} &\footnotesize \makecell{Network Graph Topology \\ Network Size \\ Bandwidth Distribution \\} &\footnotesize \makecell{Geographic Location \\ Topological Location \\ Bandwidth \\}
&\footnotesize \multirow{2}{*}{\makecell{Number of Selfish Miners \\ Mining Power of Selfish Miners}}\\
\cline{1-3}
\textbf{Mining Factors} &\footnotesize \makecell{ Mining Power Distribution \\ Difficulty} &\footnotesize \makecell{Mining Power \\ Mining Strategy} &\\
\hline
\end{tabular}
}
\caption{Key factors influencing the selfish rumor model}
\label{keyfactors}
\end{figure}
\subsection{Network Factors}
A blockchain system is a distributed system and utilizes a network to propagate information. As such the network behavior is important for the blockchain system. Network factors influence how information is spread. Those factors are visualized in Table~\ref{keyfactors}. An important characteristic is how fast information is spread. On a global level this is highly influenced by how big the network is. In addition to network size, the network graph topology also plays a major role in how information is propagated through the network. In general a more densely connected network can propagate information faster to each peer. Another crucial factor is bandwidth distribution. The Bandwidth of a peer determines at what rate he can communicate. On a given network size the combination of bandwidth distribution and network graph topology influences drastically how fast information can spread. As an example let us consider an exponential degree distribution and an exponential bandwidth distribution. On the one hand information will spread reasonably fast, when a high bandwidth node also has a high degree. On the other hand if a node with a very low bandwidth has a high degree, he will become a bottleneck.
From a local point of view the location of a peer becomes important. Both geographic and topological location determine how fast a peer receives and sends information. Together with the amount of bandwidth the location also determines how much information is routed through that specific peer. Generally speaking a more central peer receives and sends information faster and also becomes a intermediate routing point more often. One can measure the centrality of a node by analyzing his betweenness centrality. The betweenness centrality is a measure on how many shortest paths a node lies between any other pair of two nodes.
\subsection{Mining Factors}
Additionally, in a blockchain system key factors include mining factors. Those factors influence the mining process of each individual miner. On a global scale mining power distribution and difficulty are characteristic. Difficulty determines at which rate a new block is introduced to the network. Mining power distribution determines, where the new block is how likely to arrive. They are both key factors influencing the average block propagation, since an ill combination of both can lead to network congestion. As an example consider a peer with a high relative mining power, who only has one outgoing connection to the network. This one connection is clearly a bottleneck prone to lead to congestion. With a low difficulty the peer will mine many blocks in a short amount of time and will flood the peer connecting him to the network. This will result in an overall higher average block propagation time.
From a local point of view a miners mining process is mainly influenced by his mining power and the executed mining strategy. If a miner recruits additional computing power, he will gain increased mining power and produce more blocks. If a miner executes an adversarial mining strategy such as selfish mining in contrast to honest mining, he will have a different reference selection and a different block publishing behavior.
\subsection{Adversarial Factors}
Adversarial factors also influence a blockchain system. Because of the mining protocol a blockchain system faces additional threads outside of adversaries attacking the underlying network structure. Peers can execute block withholding strategies such as selfish mining. By executing selfish mining strategies the forkrate of the blockchain is increased and the overall growth decreased. Multiple selfish miners escalate this problem. Multiple selfish miners work against each other, but the power threshold above which a selfish miner gains revenue decreases proportionally to the number of selfish miners\ref{multi_sm}.
We can denote that the network, mining and adversarial factors mentioned above play a crucial part for the behavior of the overall system. It is therefore important to select those factors carefully and construct scenarios which analyze a wide variety of possible system factor combinations. In the next section we will now introduce the Selfish Rumor Model.
\section{Selfish Rumor Model}\label{selfishmodel}
The selfish miner behaves different to an honest miner and therefore can be modeled by altering the reference selection and communication process. The reference selection process is policy driven, and can thus be modified by providing a new selfish policy. However, for the analysis of \gopalan~ the edge set is only represented in an abstract form, since at most the height of a block is important. As a result, specifics concerning the edge set are never discussed. For selfish mining to be implemented into the model, the reference selection process becomes very important and has to be further specified.
\paragraph{Reference Selection Process Specification}
\gopalan~ introduce an edge set $E_{G_{p_i}}(t)$ for each peer for each point in time. Those edges represent selected references.
Additionally, we will introduce the notion of a Topblock $b_{{top}_{pi}}$.
The following rules apply:
\begin{enumerate}
\item $b_{{top}_{pi}}(t) \in L_{p_i}(t)$
\item If peer $p_j$ updates peer $p_i$ with a block $b'$ at time $t$, $b_{{top}_{pi}}(t) = b'$ if the height of $b'$ is strictly greater than the height of the previous Topblock $b_{{top}_{pi}}(t^-)$.
\item If on an event of $A$ a new block $b$ arrives to peer $p_i$ at time $t$, he will select $b_{{top}_{pi}}(t^-)$ as the parent reference of $b$. As a result $(b,b_{{top}_{pi}}(t^-)$ will be added to $E_{G_{p_i}}(t))$ and will be communicated through the network. Furthermore, $b_{{top}_{pi}}(t)$ will be set to $b$, such that $b_{{top}_{pi}}(t) = b$.
\end{enumerate}
Through the above described rules reference selection is deterministically defined. It binds reference selection to the block arriving first to a peer. This is important, since a clear reference selection definition is crucial for estimating the success of selfish mining. The remainder of the section will discuss the new Selfish Rumor Model.
\paragraph{Selfish Rumor Model}
The Selfish Rumor Model is based on the Blockchain Gossip Model introduced by \gopalan . The construction of the Selfish Rumor Model can be seen as a modification of the Blockchain Gossip Model and is best explained in that manner. However, introducing adversarial mining strategies and altering key factors such as mining power distribution, changes the new model in such a drastic way that it has to be considered a new model.
The first aspect to be modified is the communication process.
Key idea of selfish mining is block withholding. The selfish miner possesses three blockchain representations.
\begin{itemize}
\item $G_{SM_{public}}(t)$: which is updated by other peers.
\item $G_{SM_{comm}}(t)$: which is used to update other peers.
\item $G_{SM_{private}}(t)$: with the following relations:
\begin{itemize}
\item $G_{SM_{public}}(t)\subseteq G_{SM_{private}}(t)$.
\item $G_{SM_{private}}(t)\backslash G_{SM_{public}}(t)$ represents blocks mined but unpublished by the selfish miner.
\end{itemize}
\end{itemize}
\begin{figure}[t]
\begin{center}
\resizebox{\columnwidth}{!}{%
\begin{tikzpicture}
\small
\node[sm node] (1) {$Selfish~Miner$};
\node(2) [left = 1cm of 1] {$Arrival~Process~A$};
\node[block] (3) [above right = 0.6cm and 0.2cm]{$G_{SM_{public}}(t)$};
\node[block] (5) [ below =1.2cm of 3 ]{ $G_{SM_{comm}}(t)$ };
\node[block] (4) [left=0.6cm of 5]{$G_{SM_{private}}(t)$};
\node [cloud,fill=green!20, draw,very thick,cloud puffs=10,cloud puff arc=120, aspect=3, inner ysep=1em, right=1cm of 1](6) {$Other~Miners$};
\draw [arrow] (2) |- (4);
\draw [arrow] (3) -| node[anchor=south] {$U_{pub-priv}$}(4);
\draw [arrow] (4.south) -- +(0,-0.6) -| node[pos=0.3, anchor=south] {$U_{priv-com}$}(5);
\draw [arrow] (6) |- node[pos=0.78,anchor=south] {$T_{p_i}$}(3);
\draw [arrow] (5) -| node[pos=0.22,anchor=south] {$T_{SM}$}(6);
\end{tikzpicture}
}
\end{center}
\caption{Abstract representation of model entities and communication processes}
\label{fig:model_vis}
\end{figure}
The concept has been visualized in Figure~\ref{fig:model_vis}.
A total number of five processes is used to let all entities interact with each other.
\begin{itemize}
\item $Arrival~Process~A$: Blocks arrive to the selfish miner over the external arrival process $A$.
\item $T_{p_i}$: Ensures blocks from other peers are communicated to $G_{SM_{public}}(t)$.
\item $U_{pub-priv}$: Ensures that $G_{SM_{public}}(t)\subseteq G_{SM_{private}}(t)$ holds true, meaning $U_{pub-priv}$ updates $G_{SM_{private}}(t)$, when new blocks arrive to $G_{SM_{public}}(t)$ from other peers.
\item $U_{priv-com}$: Updates $G_{SM_{comm}}(t)$ according to $G_{SM_{private}}(t)$ and the selfish mining rules $S$.
\item $T_{SM}$: Ensures other peers are updated with blocks from $G_{SM_{comm}}(t)$.
\end{itemize}
Peer $SM \in P$ has an associated policy slightly different to the policy described in the Gopalan model~\ref{policy}. Note that to follow the Tree Policy~\citep{gopalan}, a deterministic rule has to be established for the case that $|O_{SM} \cap L_{SM}(t)| > 1$.
Assume that $SM$ has the knowledge of the set of blocks mined through him, $M_{SM}(t) \subset B_{G_{SM}}(t)$. $SM$ will set
\begin{equation}
(L_{SM}(t) \cap M_{SM}(t)) \neq \emptyset \rightarrow L'_{SM}(t) \subset ( L_{SM}(t) \cap M_{SM}(t))
\label{smpolicy}
\end{equation}
It then follows that $|L'_{SM}(t)|=1$.
This modified tree policy sets references according to the original selfish mining protocol described by \citeauthor{eyal}.
$S$ is a set of rules which describes how $G_{SM_{private}}(t)$ updates $G_{SM_{comm}}(t)$. The rules have to follow the state description of \citeauthor{eyal}~\ref{eyalmodel}. Therefore we need a state variable describing the difference between private and public chain.
Let $s$ be the state variable determining selfish mining actions~\citep{eyal}.
Then $s$ can be described as a difference between $G_{SM_{private}}(t)$ and $G_{SM_{public}}(t)$.
\begin{equation}
max\_ dist\_mined(G_{SM_{private}}(t)) := d(j,0), j \in M_{p_i}(t)
\end{equation}
\begin{equation}
s(t) := max\_ dist\_mined(G_{SM_{private}}(t)) - max\_ dist(G_{SM_{public}}(t))
\end{equation}
Let $t_{inc}$ refer to the set of times, where $s$ increased and analogous $t_{dec}$ refer to the set of times, where $s$ decreased.
Selfish mining is protocol, which needs a formulation of states in order to be characterized. \citeauthor{gopalan} introduced $t^-$ as a point in time infinitesimally before $t$. In addition to describe selfish mining a function is needed to access the point in time where $s$ changed last.
Let $f_{-1}(t)$ be a function that outputs the point in time, where $s$ changed the latest before $t$.
Now all tools are available to characterize the selfish mining protocol on top of the stochastic network model introduced by \citeauthor{gopalan}.
$U_{priv-com}$ can be characterized through four kind of update actions. Analogous to Subsection~\ref{eyalmodel}, those actions are $Lead~Publish$, $Competition~Publish$, $Publish$ and $Adopt$. $Mining$, the fifth action described in Subsection~\ref{eyalmodel}, is modelled through the arrival process.
This can be used to model the selfish mining protocol desribed by \citeauthor{eyal}.
\begin{enumerate}
\item $Lead~Publish$: Assume $t \in t_{inc}$ and $s(t) \geq 2$, then $U_{priv-com}$ updates $G_{SM_{comm}}(t)$, such that $G_{SM_{comm}}(t) = G_{SM_{private}}(t)$. Once the selfish miner has established a lead of two blocks against the public chain, he will update the blockchain representation used for communication towards other peers. In other words, he publishes the private chain.
\item $Competition~Publish$: Assume $t \in t_{dec}$, $s(t) = 0$, $s(f_{-1}(t)) = 1$, $s(f_{-1}(t)^-) = 0$. This means that the selfish miner mined a block, did not publish it and now received a block from another of the same height. This leads to the competition scenario. Accordingly, $U_{priv-com}$ updates $G_{SM_{comm}}(t)$, such that it includes the subgraph induced by the nodes on the paths between $L'_{SM}(t)$ and ${0}$. The selfish miner will publish the block, which caused the private chain to lead by one against the public chain, before he received a new block. This transitions to
\begin{equation}
0'(t) \rightarrow \left( t \in t_{dec} \wedge s(t) = 0 \wedge s(f_{-1}(t)) = 1 \wedge s(f_{-1}(t)^-) = 0\right)
\end{equation}
This situation $0'$ is also shown and visualized in Subsection~\ref{eyalmodel} and causes the selfish miner to execute honest mining for only the next step. \label{comppub}
\item $Publish$: Assume $0'(t^-)=\top$ and $t \in t_{inc}$, $U_{priv-com}$ updates $G_{SM_{comm}}(t)$, such that it includes the subgraph induced by the nodes on the paths between $L'_{SM}(t)$ and ${0}$. The selfish miner will publish his newly mined block, because he was previously in $0'$.
\item $Adopt$: Assume $0'(t^-)=\top$ and $s(t)=-1$, then $U_{priv-com}$ updates $G_{SM_{comm}}(t)$, such that $G_{SM_{comm}}(t) = G_{SM_{private}}(t)$. The selfish miner will adopt the public chain, because he was previously in $0'$.
\end{enumerate}
The above section introduced a new model, the Selfish Rumor Model.
However, a number of core contributions of \gopalan still hold true, such as the results proofing that Poisson processes are a good approximation of the real process. Furthermore, since peer-to-peer networks based on regular grids, regular trees and random geometric networks are already proven to be non scaleable the Selfish Rumor Model can rely on regular-random networks. The Selfish Rumor Model utilizes the tree-policy. \gopalan stated that any blockchain constructed under the tree policy is one-ended as long as the network is stable. A blockchain is one-ended if there are infinitely many confirmed blocks and a stable network means an infinite sequence of times, where the system is consistent. Since selfish mining does not influence the system to produce an infinite amount of inconsistent system times, the network has to considered stable. As a result the proof on the one-endedness of the blockchain DAG also holds true.
Through the combination of rumor-spreading mechanisms for an abstract network layer representation and adversarial mining strategies, this model can be used to analyze the relationship between the selfish mining attack and networking effects.