infinity0 · February 4, 2020 12:14
diff --git a/Background b/Background
 \section{Background}
 \paragraph{Gossip} In a peer-to-peer gossip network we have to figure out how the nodes connect to each other. Two possibilities are a r-regular random graph and the SlimFly topology.

 For the current assignment you can assume that the full list of peers is known, and available to each peer. (Networks where this is not the case, are vulnerable to the Sybil attack, which is out-of-scope for the time being.)

 The topology should work for any sized network. Some topologies are optimised for particular network sizes (e.g. n = k ^ 2 for some k) and degrade for other sizes. This is bad.

 There should be an efficient algorithm that each node can run to figure out its own neighbours. For example, for r-regular random graphs the only known way of doing this[1] is for everyone to generate the whole graph, whose computation costs O(n^3). This is not ideal. For our purposes, anything below O(n^2) can be considered reasonably efficient.

 [1] (The naive method of selecting r random outgoing neighbours from the whole set N does not work, because this will result in non-regularity for the incoming neighbours.)

 Some topologies, such as SlimFly, assume that each node has a co-ordinate or index in some space. This is insufficient for a peer-to-peer network; we need to reify the assumption and provide a concrete construction that maps the list of peers to their co-ordinate or index. The cost of this mapping needs to be considered as part of the cost of "figuring out my neighbours". So for example if it takes O(n^2) to figure out my own co-ordinate, and then O(1) to figure out my own neighbours in the co-ordinate space, then O(n^2) to reverse-map my neighbour co-ordinates to their actual peer ids, then the overall cost is still O(n^2).

 For a gossip-network, the main characteristics we want to aim for are:

 - to minimise the network diameter
 - to maximise the number of edges it takes for an attacker to cut the network in half (e.g. into two disconnnected subnetworks that are both greater in size than 1/3 of the whole network)

 There also are various other more sophisticated / precisely-defined properties that are also interesting, that are mentioned in various papers in the literature.

 \paragraph{Slim Fly}

 \paragraph{ r-regular random graphs}

 %what do we have to do in Slim Fly for our system?
diff --git a/Design b/Design
 \section{System Design}


 \subsection{Model}
 We have the following assumptions for the validators 
 \begin{itemize}
 \item minimal capacity can be assumed to be 
 \item validator set changes once a day,
 \item almost stable, except a very few ones might be eliminated.
 \item decentralised
 \end{itemize}

 \subsection{Attack model}
 Our adversary knows topology and can see all the traffic among actors of the protocol.
 We also assume the adversary is active.
 This includes participating in the protocol (being internal) and blocking, injecting, delaying traffic.
 However, we have limits on how much traffic the adversary can inject without being detected. (assumption? or consequence of protocol)
 Furthermore, we assume our adversary is static that means that once the adversary is participating as a number of validators, it cannot change into a different setup.
 Finally, we assume the adversary can at most control less than 1/3 of all validators, regardless of the validators capacities and resistance against denial of service attacks. 

 \subsection{Routing and Congestion Control}
 Once a message is sent the receiver needs to send back an acknowledgement, if the acknowledgement does arrive within a time-frame
 the sender sends the message again through a different neighbour.
 Neighbours report (broadcast) their capacity to their neighbours.
 We use a dynamic routing strategy called restricted UGAL\cite{}, where we use min route for neighbours that are not congested
 and restricted Valiant \cite{} otherwise. We restrict the Valiant routing by only selecting intermediary nodes that are close by.

 Another problem that occurs is how dropping acknowledgements are handled. 

 %System model: minimal capacity, set changes once a day, almost stable, decentralized
 %Attack model: static, 1/3 nodes, 1/3 capacity?, internal, knows topology, active, 'limits on injecting traffic without detection'(assumption? or consequence of protocol)
 %routing+congestion: restricted Valiant, min route without congestion, acknowledgements (discussion on dropping acknowledgements)
 %theoretical bounds on how long it takes to get 2/3 of acks
 %arguments on resistance to partitioning (maybe theory on eclipse)
diff --git a/Intro b/Intro
 \section{Introduction}
 Networking is an essential component of distributed systems such as blockchain technologies that enable decentralised data storage. The networking scheme impacts the performance, security and resilience against attacks of such systems. In this project the aim is to identify a networking scheme where the blockchain system is resistance against  adversaries that attack the delivery of data over the network (application layer). The blockchain systems used in this project is the Polkadot systems\cite{}.

 %Concrete Problem: permissoned, proof-of-stake of medium size, stable nodes -> which topology? which routing algorithm? resilience and congestion control?
 The aim of this assignment is to determine the best topology and routing algorithm for the Polkadot is a proof-of-stake blockchain system given a number of options. 

 Most networking schemes of blockchain projects use gossiping. However, in Polkadot many targeted data has to be sent that is only intended for a given participant and gossiping creates too much unnecessary traffic, which might lead to congestion. Moreover,  no end-to-end acknowledgements or other detection mechanism is used that notifies the sender of failed communication.  Another common networking scheme in distributed systems are DHT routing schemes such as Kademlia\cite{} and Chord \cite{} that were designed for high churn systems. However, the number of intermediary hops communication needs to traverse until it reaches the recipient is often high.

 In this assignment:
 \begin{itemize} 
 \item the adoption of Slim Fly in decentralised setting (maybe also r-regular random graphs) should be investigated, 
 \item a solution for congestion control and routing should be investigated, 
 \end{itemize}

 The results should show figures for time is takes for delivery guarantees and simulations results of performance and resistance against failures. 
diff --git a/Main b/Main
 \title{Investigating Networking Schemes for Polkadot}

 \begin{document}
 \maketitle
 \input{intro}
 %Motivation: blockchain resistance (reliability?) against  adversaries that attack the delivery of data over the network (application layer)

 %Concrete Problem: permissoned, proof-of-stake of medium size, stable nodes -> which topology? which routing algorithm? resilience and congestion control?

 %Why previous solutions do not work? gossiping: too much unnecessary traffic-> congestion, no end-to-end acknowledgements; (detection?) DHTs: high diameter in comparison, made for churn

 %Solution: adopt Slim Fly to decentralized setting, solution for congestion control, routing;

 %Eval: delivery guarantees, simulations of performance and resistance

 \input{background}
 %Polkadot in general: Done

 %Slim Fly: Fatemeh TODO

 %what do we have to do in Slim Fly for our system?

 \input{design}
 %System model: minimal capacity, set changes once a day, almost stable, decentralized
 %Attack model: static, 1/3 nodes, 1/3 capacity?, internal, knows topology, active, 'limits on injecting traffic without detection'(assumption? or consequence of protocol)
 %routing+congestion: restricted Valiant, min route without congestion, acknowledgements (discussion on dropping acknowledgements)
 %theoretical bounds on how long it takes to get 2/3 of acks
 %arguments on resistance to partitioning (maybe theory on eclipse)

 \input{simulations}
 %Performance without adversary: input work loads: number of parachains, number of validators, capacity of validators, frequency of blocks; output metrics: delivery time, goodput, throughput, failure rate (failed delivery to some nodes vs. failed delievery to more than 1/3)

 %Performance with adversary: input: strategy (just dropping? + own traffic), number/capacity of adversaries (can we show uniform capacity dist best?), work loads as above, metrics: as above;

 %Resilience: prob to partition graph; adversaries: how clustered is the adversary? number congested nodes? ability to choose congested nodes?



 \input{relatedwork}
 %gossiping, DHTs

 \end{document}
diff --git a/Simulations b/Simulations
 %Performance without adversary: input work loads: number of parachains, number of validators, capacity of validators, frequency of blocks; output metrics: delivery time, goodput, throughput, failure rate (failed delivery to some nodes vs. failed delievery to more than 1/3)

 %Performance with adversary: input: strategy (just dropping? + own traffic), number/capacity of adversaries (can we show uniform capacity dist best?), work loads as above, metrics: as above;

 %Resilience: prob to partition graph; adversaries: how clustered is the adversary? number congested nodes? ability to choose congested nodes?
	\section{Background}
	\paragraph{Gossip} In a peer-to-peer gossip network we have to figure out how the nodes connect to each other. Two possibilities are a r-regular random graph and the SlimFly topology.

	For the current assignment you can assume that the full list of peers is known, and available to each peer. (Networks where this is not the case, are vulnerable to the Sybil attack, which is out-of-scope for the time being.)

	The topology should work for any sized network. Some topologies are optimised for particular network sizes (e.g. n = k ^ 2 for some k) and degrade for other sizes. This is bad.

	There should be an efficient algorithm that each node can run to figure out its own neighbours. For example, for r-regular random graphs the only known way of doing this[1] is for everyone to generate the whole graph, whose computation costs O(n^3). This is not ideal. For our purposes, anything below O(n^2) can be considered reasonably efficient.

	[1] (The naive method of selecting r random outgoing neighbours from the whole set N does not work, because this will result in non-regularity for the incoming neighbours.)

	Some topologies, such as SlimFly, assume that each node has a co-ordinate or index in some space. This is insufficient for a peer-to-peer network; we need to reify the assumption and provide a concrete construction that maps the list of peers to their co-ordinate or index. The cost of this mapping needs to be considered as part of the cost of "figuring out my neighbours". So for example if it takes O(n^2) to figure out my own co-ordinate, and then O(1) to figure out my own neighbours in the co-ordinate space, then O(n^2) to reverse-map my neighbour co-ordinates to their actual peer ids, then the overall cost is still O(n^2).

	For a gossip-network, the main characteristics we want to aim for are:

	- to minimise the network diameter
	- to maximise the number of edges it takes for an attacker to cut the network in half (e.g. into two disconnnected subnetworks that are both greater in size than 1/3 of the whole network)

	There also are various other more sophisticated / precisely-defined properties that are also interesting, that are mentioned in various papers in the literature.

	\paragraph{Slim Fly}

	\paragraph{ r-regular random graphs}

	%what do we have to do in Slim Fly for our system?
	\section{System Design}


	\subsection{Model}
	We have the following assumptions for the validators
	\begin{itemize}
	\item minimal capacity can be assumed to be
	\item validator set changes once a day,
	\item almost stable, except a very few ones might be eliminated.
	\item decentralised
	\end{itemize}

	\subsection{Attack model}
	Our adversary knows topology and can see all the traffic among actors of the protocol.
	We also assume the adversary is active.
	This includes participating in the protocol (being internal) and blocking, injecting, delaying traffic.
	However, we have limits on how much traffic the adversary can inject without being detected. (assumption? or consequence of protocol)
	Furthermore, we assume our adversary is static that means that once the adversary is participating as a number of validators, it cannot change into a different setup.
	Finally, we assume the adversary can at most control less than 1/3 of all validators, regardless of the validators capacities and resistance against denial of service attacks.

	\subsection{Routing and Congestion Control}
	Once a message is sent the receiver needs to send back an acknowledgement, if the acknowledgement does arrive within a time-frame
	the sender sends the message again through a different neighbour.
	Neighbours report (broadcast) their capacity to their neighbours.
	We use a dynamic routing strategy called restricted UGAL\cite{}, where we use min route for neighbours that are not congested
	and restricted Valiant \cite{} otherwise. We restrict the Valiant routing by only selecting intermediary nodes that are close by.

	Another problem that occurs is how dropping acknowledgements are handled.

	%System model: minimal capacity, set changes once a day, almost stable, decentralized
	%Attack model: static, 1/3 nodes, 1/3 capacity?, internal, knows topology, active, 'limits on injecting traffic without detection'(assumption? or consequence of protocol)
	%routing+congestion: restricted Valiant, min route without congestion, acknowledgements (discussion on dropping acknowledgements)
	%theoretical bounds on how long it takes to get 2/3 of acks
	%arguments on resistance to partitioning (maybe theory on eclipse)
	\section{Introduction}
	Networking is an essential component of distributed systems such as blockchain technologies that enable decentralised data storage. The networking scheme impacts the performance, security and resilience against attacks of such systems. In this project the aim is to identify a networking scheme where the blockchain system is resistance against adversaries that attack the delivery of data over the network (application layer). The blockchain systems used in this project is the Polkadot systems\cite{}.

	%Concrete Problem: permissoned, proof-of-stake of medium size, stable nodes -> which topology? which routing algorithm? resilience and congestion control?
	The aim of this assignment is to determine the best topology and routing algorithm for the Polkadot is a proof-of-stake blockchain system given a number of options.

	Most networking schemes of blockchain projects use gossiping. However, in Polkadot many targeted data has to be sent that is only intended for a given participant and gossiping creates too much unnecessary traffic, which might lead to congestion. Moreover, no end-to-end acknowledgements or other detection mechanism is used that notifies the sender of failed communication. Another common networking scheme in distributed systems are DHT routing schemes such as Kademlia\cite{} and Chord \cite{} that were designed for high churn systems. However, the number of intermediary hops communication needs to traverse until it reaches the recipient is often high.

	In this assignment:
	\begin{itemize}
	\item the adoption of Slim Fly in decentralised setting (maybe also r-regular random graphs) should be investigated,
	\item a solution for congestion control and routing should be investigated,
	\end{itemize}

	The results should show figures for time is takes for delivery guarantees and simulations results of performance and resistance against failures.
	\title{Investigating Networking Schemes for Polkadot}

	\begin{document}
	\maketitle
	\input{intro}
	%Motivation: blockchain resistance (reliability?) against adversaries that attack the delivery of data over the network (application layer)

	%Concrete Problem: permissoned, proof-of-stake of medium size, stable nodes -> which topology? which routing algorithm? resilience and congestion control?

	%Why previous solutions do not work? gossiping: too much unnecessary traffic-> congestion, no end-to-end acknowledgements; (detection?) DHTs: high diameter in comparison, made for churn

	%Solution: adopt Slim Fly to decentralized setting, solution for congestion control, routing;

	%Eval: delivery guarantees, simulations of performance and resistance

	\input{background}
	%Polkadot in general: Done

	%Slim Fly: Fatemeh TODO

	%what do we have to do in Slim Fly for our system?

	\input{design}
	%System model: minimal capacity, set changes once a day, almost stable, decentralized
	%Attack model: static, 1/3 nodes, 1/3 capacity?, internal, knows topology, active, 'limits on injecting traffic without detection'(assumption? or consequence of protocol)
	%routing+congestion: restricted Valiant, min route without congestion, acknowledgements (discussion on dropping acknowledgements)
	%theoretical bounds on how long it takes to get 2/3 of acks
	%arguments on resistance to partitioning (maybe theory on eclipse)

	\input{simulations}
	%Performance without adversary: input work loads: number of parachains, number of validators, capacity of validators, frequency of blocks; output metrics: delivery time, goodput, throughput, failure rate (failed delivery to some nodes vs. failed delievery to more than 1/3)

	%Performance with adversary: input: strategy (just dropping? + own traffic), number/capacity of adversaries (can we show uniform capacity dist best?), work loads as above, metrics: as above;

	%Resilience: prob to partition graph; adversaries: how clustered is the adversary? number congested nodes? ability to choose congested nodes?



	\input{relatedwork}
	%gossiping, DHTs

	\end{document}