relatedwork.tex

\chapter{Related Work}\label{chap:relatedwork}
Selfish mining is a statistical attack. In order to analyze profit, it is therefore beneficial to analytically model selfish mining. Moreover to study the impact of deviating mining strategies and gain realisitic resulsts, it is very important to represent the blockchain network as close to reality as possible in a mining model. In the following recent selfish mining models as well as network models will be discussed.


\section{Selfish Mining Models}
Proof-of-work Mining is most commonly modelled through Markov decision processes.
It is generally used to model decision making, where the outcomes are influenced by random processes and the decision of the decision maker~\cite{ibe2013markov}.
In the case of selfish mining controls his decision making process and for the rest of the network, the block arrival and block propagation is modelled through stochastic processes. Once implemented, a Markov model can be used to analytically estimate system properties. Selfish mining is concerned with maximizing obtained mining rewards, which is also called revenue.

\citeauthor{eyal} first described a selfish mining model based on Markov decision processes~\cite{eyal}.
They ran simulations to estimate revenue gain. Since blockchain systems use a peer-to-peer network to propagate mined blocks, it is important to analyze how the network was implemented in this model. Block propagation time is considered negligible compared to block generation time~\cite{eyal}. As a result, \citeauthor{eyal} consider communication to be instantaneous~\citep{eyal}. They found that selfish mining increases profitiability for a relative mining power greater than $25\%$ compared to the network.

\citeauthor{optimal_sm} further extended the model to consider all possible actions a selfish miner can perceive. Block propagation time remains unassessed, since it is again considered to be much smaller than block generation time.  \citeauthor{optimal_sm} again utilize Markov decision processes to model the system. They find a number of optimal policies and provide an analysis on the upper bound of revenue increase through selfish mining strategies.
This Markov model was widely used and adopted in other research directions studying other aspects of selfish mining. For example, the behavior of multiple selfish miners was simulated through \citeauthor{multi_sm}~\cite{multi_sm}. One of the main findings is that the lower bound on the profitability treshhold decreases with the number of selfish miners.
\citeauthor{deepDiveSM}~\cite{deepDiveSM} extended the model of \citeauthor{optimal_sm}~\cite{optimal_sm} even further to analyze multiple selfish miners. This resulted in a more complex state space of the markov decision process. They show that in fact for the symmetric selfish miner, i.e. all selfish miners have the same hashrate, the profitability threshhold decreases, but for the asymmetric case the threshhold increases. The focus of this research was to deepen the understanding of different selfish mining strategies. However, networking factors remained unassessed.

\citeauthor{xiao_modeling} study the impact on the profitability threshhold and revenue gain of a networking advantage possessed by the selfish miner~\cite{xiao_modeling}. They model the network as a graph and find that networking advantage correlates to the betweenness centrality of the selfish miner. Additionally it highly affects the profitability threshhold and revenue gain of the attacker. This indicates that the structure of the network influences the selfish mining strategy. However, this model remains very abstract, since only the peer-to-peer layer and structure is modelled as a graph, disregarding any limitations imposed by physical infrastructure such as bandwidth. Nonetheless, it indicates that the underlying network influences the blockchain overlay, strengthening the assumption that there is a highly influencial dependency between networking effects and selfish mining.

It is not contested by any of the previous research that network capabilities and communication delay impact selfish mining~\cite{multi_sm}, although most research model block propagation as instantaneous.
In addition, most research which is concerned with selfish mining builts on top of the model presented by \citeauthor{optimal_sm}.
This contributes to the negligence of networking effects, when analyzing selfish mining.
Assuming that the underlying network does influence the system built on top, this master thesis aims to analyze the impact of networking effects on selfish mining. It is therefore important to represent the network in the model, that is used to analyze selfish mining.

\section{Blockchain Network Models}
Bitcoin and Proof-of-Work blockchains in general have been modelled and analyzed from a networking perspective. In order to study selfish mining with the context of networking effects it is necessary to analyze the network. 
Most blockchain network models are concerned with the estimation of consistency. Consistency is the property of a blockchain that all honest parties output the same block sequence.
\citeauthor{garay2015bitcoin} study the core of the Bitcoin protocol formally~\cite{garay2015bitcoin}. They analyze the protocol in a synchronous communication network and show persistence and liveness of committed transactions. They further proof that the adversarial computational power bound to reach Byzantine Agreement is $1/2$ of the network for a synchronized network. The adversarial bound decreases as the network drifts further away from synchronization~\cite{garay2015bitcoin}.
The analysis of \citeauthor{garay2015bitcoin} indicates that the networks synchronicity highly influences the behavior of proof-of-work blockchains.

\citeauthor{pass2017analysis} propose a new network model to analyze blockchains in terms of consistency and liveness in an asynchronous network~\cite{pass2017analysis}. They do not make any assumptions of synchronicity and proof consistency in a network with adversarial delays that are a-priori bounded. They show that the proof of work hardness needs to be set as a function of the maximum network delay. New peers joining the network or peers getting corrupted are also modelled. They prove that Nakamoto's protocol satisfies consistency even in a network with message delays. However, those network delays are modelled to be always adversarial. This leaves out networking factors impacting the system which are caused by honest behavior.

\citeauthor{kiffer2018better} built on top of the models of \citeauthor{garay2015bitcoin} and \citeauthor{pass2017analysis}, but formulate a simple Markov chain based method to analyze consistency. Additionally, they provide lower bounds for consistency. They also analyze the GHOST protocol, where consensus is built over the heaviest observed subtree, in addition to the longest chain rule~\cite{kiffer2018better}. The model is based on rounds of communication. The modelled adversary controls a fraction of honest peers and  can delay and reorder messages within a threshhold $\delta$. The model therefore again captures only network attacks from an adversary, but disregards other networking effects.

\citeauthor{gervais2016security} introduce a novel framework to analyse security and performance~\cite{gervais2016security}. They model how network and consensus parameters influence stale block rate, block propagation times, throughput and security. Stale blocks are blocks which do not contribute to the consensus mechanism. Selfish mining is modelled as a Markov decision process. The network layer is characterized by block size and the information propagation mechanism. \citeauthor{gervais2016security} simulate the system over a network consisting of point-to-point connections between peers~\cite{gervais2016security}. Those channels are defined by latency and bandwidth. Latency is set using global IP latency statistics. One major result is that an increasing block size increases block propagation time linearly and stale block rate exponentially. 

\citeauthor{gopalan} utilize rumor-spreading to implement a new stochastic network model~\cite{gopalan}. They study stability and scalability of their model. Each peer communicates at a given rate his oldest blocks to his neighbors. Communication channels are also bandwidth limited. This setup introduces network delays to blocks, which depends on the instantaneous network congestion.
Unlike previous stochastic network models, \citeauthor{gopalan} do not introduce delay based on sampling data, but rather on the communication behavior of peers. Since network congestion depends on the behavior of peers and selfish mining is a deviating behavior, the model introduced by \citeauthor{gopalan} will be used in the following to analyze selfish mining and networking effects.