\documentclass[a4paper,10pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}

\usepackage{listings}
\lstdefinelanguage{pseudo}
  {morekeywords={if, then, else, end, let, and, for, in, while}}
\lstset{escapechar=?, mathescape=true, language=pseudo, frame=single,
basicstyle=\small, keywordstyle=\bfseries, captionpos=b}
\renewcommand{\lstlistingname}{Spec.}

\usepackage{amsthm}
\newtheorem{thm}{Theorem}

\theoremstyle{remark}
\newtheorem*{rem}{Remark}

\title{Pacemaker : un protocole de mesure de disponibilité dans les réseaux pair-à-pair}
\date{Sujet proposé et supervisé par Fabrice Le Fessant}
\begin{document}

\maketitle

\section{Introduction}
Tous les réseaux pair-à-pair ont en commun d'avoir un dynamique complexe : naissances, morts, arrivées, départs, indisponibilité temporaires peuvent survenir à tout instant. Ainsi, la \emph{disponibilité} d'un nœud, c'est à dire la fraction du temps passée par ce nœud sur le réseau, est une propriété importante pour déterminer l'impact de ce nœud sur le réseau.

C'est pourquoi de nombreux protocoles de réseaux pair-à-pair s'appuient sur la disponibilité des nœuds. Deux utilisations différentes de cette information sont à distinguer :
\begin{itemize}
\item la structuration du réseau, ou bien par l'élection de super-peer (cf. ...) ou dans la sélection des voisins (cf. backup)
\item assurer une plus grande justice dans la répartition d'un service : faire en sorte que les gens qui ont la plus grande disponibilité aient plus d'avantages sur le réseau.
\end{itemize}

Malheureusement, la plupart de ces stratégies supposent donné un oracle qui fournirait cette information de disponibilité. Plusieurs approches permettent d'obtenir cet orcale :
\begin{itemize}
\item de façon individuelle : chaque nœud est en charge de surveiller et de stocker sa propre disponibilité
\item l'évaluation par les pairs : à chaque nœud est associé un ensemble de pairs chargés de surveiller sa disponibilité
\item de façon centralisée : un nœud s'occupant de surveiller le réseau et de stocker la disponibilité de l'ensemble des nœuds du réseau
\end{itemize}
Chacune de ces approches présente une limite manifeste :
\begin{itemize}
\item l'approche individuelle autorise les nœuds à mentir sur leur propre disponibilité, pour obtenir par exemple plus d'avantages sur le réseau. Ceci met donc en défaut une des principales utilisation de l'information de disponibilité.
\item l'évaluation par les pairs résout le problème de passage à l'échelle, mais est très sensible à la collusion : des groupes de nœuds peuvent choisir de coopérer en se choisissant mutuellement comme évaluateurs et ainsi mentir collectivement sur leur disponibilité. Le protocole AVMON qui utilise ce procédé contourne le problème de la collusion en imposant que les évaluateurs soient choisis de façon semi-aléatoire, mais cette méthode impose malheureusement une limite inférieure sur la taille du réseau. De plus, l'évluation par les pairs n'assure pas la durabilité des informations de disponibilités : l'ensemble des mes évaluateurs à un instant donné sera-t-il toujours présent sur le réseau dans plusieurs mois ?
\item l'approche centralisée n'est pas passable à l'échelle : quand le nombre de pairs dans le réseau devient trop grand, le nœud en charge de la surveillance ne peut ni garder une vision globale du réseau ni répondre à toutes les requêtes de pairs cherchant à s'informer sur la disponibilité d'autres pairs.
\end{itemize}

Le but du présent rapport est donc de présenter et d'étudier le protocole \emph{Pacemaker}\footnote{Le nom provient du fonctionnement du protocole ; celui-ci est basé sur la propagation de pulsations dans le réseau, présentant ainsi une certaine analogie avec les stimulateurs cardiaques.}. Le protocole devra assurer les propriétés suivantes :
\begin{itemize}
\item \textbf{passage à l'échelle :} la complexité temporelle et spatiale doit être au plus logarithmique en le nombre de nœuds du réseau
\item \textbf{précision :} l'erreur entre la disponibilité mesurée par le protocole et la disponibilité réelle doit être négligeable
\item \textbf{non falsifiabilité :} un pair ne doit pas pouvoir mentir au sujet de sa propre disponibilité
\item \textbf{résistance à la collusion :} les pairs ne doivent pas pouvoir coopérer pour mentir sur leur disponibilité
\item \textbf{faible impact sur le réseau :} la quantité de données échangées sur le réseau doit être limitée
\item \textbf{répartition de charge :} le travail effectué par le protocole est réparti de façon homogène sur le réseau
\item \textbf{durabilité temporelle :} l'historique de disponibilité d'un nœud doit être préservé dans le temps
\end{itemize}

La section 2. présente le modèle et les hypothèses sur lesquels repose Pacemaker, la section 3. contient la spéficiation complète du protocole, les sections suivantes s'attachent à l'analyse théorique et expérimentale du protocole, à travers une simulation et un déploiement sur PlanetLab\footnote{PlanetLab est un réseau constitués d'ordinateurs fournis par diverses entreprises et universités à travers le monde et mis à la disposition de l'ensemble des membres du réseau.}.

\section{Modèle et notations}

\subsection{Réseau}



\subsection{Cryptographie}
On suppose que chaque pair $p$ possède une pair de clé publique/privée \textsf{(K$^p_{pub}$, K$^p_{priv}$)} donnant accés aux primitives cryptographiques suivantes : 
\begin{itemize}
 \item{\sf sign(data, K$_{priv}$) :} renvoie une signature pour \textsf{data} en utilisant la clé privée \textsf{K$_{priv}$}.
 \item{\sf verify(S, data, K$_{pub}$) :} vérifie que \textsf{S} est une signature pour \textsf{data} créée avec la clé privée \textsf{K$_{priv}$} associée à la clé publique \textsf{K$_{pub}$}.
 \item{\sf hash(data) :} renvoie un hash de \textsf{data}.
\end{itemize}

On considére donc que les pairs connaissent toujours l'expéditeur des messages qu'ils recoivent, ceux-ci étant identifiés de façon unique par leur clé publique. Les attaques cryptographiques usuelles ne sont pas étudiées ici, et les primitives ci-dessus sont considérés comme sûres. De même. la fonction de hachage ci-dessus est considérée comme résistante aux attaques par collision (au moins sur la durée caractéristique d'utilisation du protocole).

The key pair of the server will be denoted by \textsf{(KS$_{pub}$,
KS$_{priv}$)}. \textsf{KS$_{pub}$} is assumed to be known by every peer.

Each peer $p$ knows the list of peers to whom he is connected, this list is denoted by $NS_p$.
If $q\in NS_p$ then $p$ can send the message $m$ to $q$ using the function \textsf{send($q$, $m$)}.

$\langle a|b|\ldots\rangle$ will be used to denote the serialisation
(depending on the implemetation) of two or more pieces of data.

\subsection{Principle}

The protcol works in three phases:

\subsubsection*{Phase 1: Seeding}

The server generates a unique seed and initiates
a seed pulse which is diffused through the network. Upon receiving the seed,
each peer signs it with his private key and hashes it. This hash is called the
\emph{token} of the peer.

\textsf{Seed($i$, seed$^i$, $T^i$, S$^i_{seed}$)} is used to diffuse the seed
pulse during this phase, where:
\begin{itemize}
    \item $i$ is the round number.
    \item \textsf{seed$^i$} is the seed of round $i$.
	\item $T^i$ is the duration of the seeding phase.
	\item \textsf{S$^i_{pulse}$} is
	\textsf{sign($\langle$$i$|seed$^i$|$T^i\rangle$, KS$_{priv}$)}.
\end{itemize}

\subsubsection*{Phase 2: Hashing}

Each peer starts collecting the tokens of his
neighbors and adds his own token to the collected hashes, obtaining a
peer-token map. The hash of this map yields a new token which is sent back to
the neighbors. This progressively builds a hash graph, until the root
server itself hashes the tokens of its children. 

\textsf{SeedReply($i$, H$_p$)} is used to build the hash graph during this phase,
where \textsf{H$_p$} is the token sent by peer $p$, that is, the hash of
the collected map of the tokens received by peer $p$.

\subsubsection*{Phase 3: Pulse}

The server initiates a new pulse with the map it has
collected from its childrens. Upon receiving the pulse, each peer adds to the
pulse the map associated with the token that has been collected during 
Phase 2. Thus, each peer receives a list of hash maps
corresponding to a path from the root to himself in the hash graph computed during Phase 2.

\textsf{Pulse($i$, seed$^i$, branch$^i$, S$^i_{pulse}$)} is used to diffuse the pulse during this
phase, where:
\begin{itemize}
    \item \textsf{branch$^i$} is a list of hash maps associated to a path from the server
    to the current peer.
    \item \textsf{S$^i_{pulse}$} is \textsf{sign($\langle$i|seed$^i$|H$^i$$\rangle$, KS$_{priv}$)}.
\end{itemize}

\subsubsection*{Challenges}

The protocol also provides the following request/reply logic to challenge the
availability of a peer:

\begin{itemize}
  \item{\sf Availability($i$, bits):} used by a peer to send his avaibility
  history up to round $i$. \textsf{bits} is a bit array where a $0$ (resp. 1)
  bit at index $j$ means that the peer was absent (resp. available) during round
  $j$.
  \item{\sf Challenge($i$):} used to ask a peer the proof of his presence
  during round $i$.
  
  \item{\sf Proof($i$, seed$^i$, branch$^i$, S$^i_p$, S$^i_{pulse}$):} to answer
  a challenge, where \textsf{S$^i_p$} is \textsf{sign($\langle$i|seed$^i$$\rangle$, K$^p_{priv}$)}.
\end{itemize}

\subsection{Phase 1: Seeding}

\begin{lstlisting}[caption=Server at round $i$]
  let phase$^i$ = SEEDING;
  let seed$^i$ = random_seed();
  let S$^i_{seed}$ = sign($\langle$$i$|seed$^i$|$T^i$$\rangle$, KS$_{priv}$);
  let M$^i_{seed}$ = Seed($i$, seed$^i$, $T^i$, S$^i_{seed}$);
  let map$^i$ = $\emptyset$;
  $\forall q \in$ NS$_{server}$, send($q$, M$^i_{seed}$);

  wait $T^i$;
\end{lstlisting}

\begin{lstlisting}[caption={Peer $p$ receiving \textsf{Seed($i$,
seed$^i$, $T^i$, S$^i_{seed}$)}}]
  if
    verify(S$^i_{seed}$, $\langle$$i$|seed$^i$|$T^i$$\rangle$, KS$_{pub}$)
  then
    $\forall q \in$ NS$_p$, send($q$, M$^i_{seed}$);    

    let S$^i_p$ = sign($\langle$$i$|seed$^i$$\rangle$, K$^p_{priv}$);
    let map$^i$ = {$p \rightarrow$hash(S$^i_p$)};
    let nreplies$^i$ = 0;
    let replies$^i$ = $\emptyset$;
    let included$^i$ = $\bot$;
    let duration$^i$ = $T^i$;
    let phase$^i$ = SEEDING;
  end if
\end{lstlisting}

\subsection{Phase 2: Hashing}

\begin{lstlisting}[caption={Every $\Delta << T^i$ seconds, on peer $p$}]
  if phase$^i$ = SEEDING then
    let H$^i$ = hash(map$^i$);
    let M$^i_{seedreply}$ = SeedReply($i$, H$^i$);
    nreplies$^i$ = nreplies$^i+1$;
    replies$^i$[nreplies$^i$] = (H$^i$, map$^i$);
    $\forall q \in$ NS$_p$, send($q$, M$^i_{seedreply}$);    
  end if
\end{lstlisting}

\begin{lstlisting}[caption={Server or peer receiving \textsf{SeedReply($i$,
X$_q$)} from peer $q$}]
  if phase$^i$ = SEEDING then
    map$^i$ = $\{ q \rightarrow $X$_q \} \oplus$map$^i$;
  end if
\end{lstlisting}

\subsection{Phase 3: Pulse}

\begin{lstlisting}[caption=Server at round $i$ (after having waited $T^i$)]
  phase$^i$ = IDLE;
  let H$^i$ = hash(map$^i$);
  let branch$^i$ = $\emptyset$;
  branch$^i$[0] = map$^i$;
  let S$^i_{pulse}$ = sign($\langle$$i$|seed$^i$|H$^i$$\rangle$, KS$_{priv}$);
  let M$^i_{pulse}$ = Pulse($i$, seed$^i$, branch$^i$, S$^i_{pulse}$); 
  $\forall q \in$ NS$_{server}$, send($q$, M$^i_{pulse}$);
\end{lstlisting}

\begin{lstlisting}[caption={Peer $p$ receiving \textsf{Pulse($i$, seed$^i$, branch$^i$, S$^i_{pulse}$)}}]
  if
    verify(S$^i_{pulse}$, $\langle$$i$|seed$^i$|hash(branch$^i$[0])$\rangle$,
    KS$_{pub}$) then
     phase$^i$ = IDLE;
     let level = length(branch$^i$)-1;
     if
       $\exists$ {$p$ $\rightarrow$ H$^i$} $\in$ branch$^i$[level] and
       $\exists\; n\; |$replies[$n$] = (H$^i$, oldmap$^i$) and
       included$^i < n$ and
       $\forall\; n\in$[1..level], hash(branch$^i$[n]) $\in$ branch$^i$[n-1]
     then
       branch$^i$[level+1] = oldmap$^i$;
       let M$^i_{pulse}$ = Pulse($i$, seed$^i$, branch'$^i$, S$^i_{pulse}$);
       History[$i$] = ($i$, seed$^i$, branch'$^i$, S$^i_p$, S$^i_{pulse}$);
       included$^i$ = $n$;
       $\forall q \in$ NS$_p$, send($q$, M$^i_{pulse}$);
    end if
  end if
\end{lstlisting}

\subsection{Challenges}
\begin{lstlisting}[caption=Peer $p$ sending to $q$ his availability over the last $N_t$ rounds]
  let bits$^i$ = new bitfield[$N_t$];
  for $x$ in [1..$N_t$]
    if History[$i-N_t+x$] = $\emptyset$ then
      bits$^i$[$x$] := 0;
    else
      bits$^i$[$x$] := 1;
    end if
  end for  
  let M$^i_{avail}$ = Availability($i$, bits);
  send($q$, M$^i_{avail}$);
\end{lstlisting}

\begin{lstlisting}[caption={Peer $p$ sending to $q$ \textsf{Challenge($i$)}}]
  challenges[$q$] = challenges[$q$]$\oplus${$i\rightarrow$ WAITING};
  let M$^i_{challenge}$ = Challenge($i$);
  send($q$, M$^i_{challenge}$);
\end{lstlisting}

\begin{lstlisting}[caption={Peer $p$ receiving \textsf{Challenge($i$)} from peer
$q$}]
  let M$^i_{proof}$ = Proof(History[$i$]);
  send($q$, M$^i_{proof}$);
\end{lstlisting}
\newpage
\begin{lstlisting}[caption={Peer $q$ receiving from peer $p$ \textsf{Proof($i$, seed$^i$, branch$^i$, S$^i_p$, S$^i_{pulse}$)}}, label=lst-proof]
  let level = length(branch$^i$)-1;
  if
     $i$ $\in$ challenges[p] and
     verify(S$^i_{pulse}$, $\langle$$i$|seed$^i$|hash(branch$^i$[0])$\rangle$, KS$_{pub}$) and
     verify(S$^i_p$, $\langle i$|seed$^i\rangle$, K$^p_{pub}$) and 
     $\forall\; n\in$[1..level], hash(branch$^i$[n]) $\in$ branch$^i$[n-1] and 
     {$p\rightarrow$hash(S$^i_p$)} $\in$ branch$^i$[level]
  then
     challenge[$q$] = challenge[$q$]$\oplus${$i\rightarrow$ PROVEN};
  else
     challenge[$q$] = challenge[$q$]$\oplus${$i\rightarrow$ WRONG};
  end if
\end{lstlisting}

\section{Analysis} 

The first problem to be adressed is the guarantee given by a proof provided by a
peer in Spec. \ref{lst-proof}.

\begin{thm}
Assuming that:
\begin{itemize}
  \item the server is not corrupted
  \item peers do not share private keys
\end{itemize}
Then if peer $p$ provides a valid proof of his presence during round $i$, that
is a proof satisfying the following four tests:
\begin{enumerate}
  \item \emph{verify(S$^i_{pulse}$,
  $\langle$$i$|seed$^i$|hash(branch$^i$[0])$\rangle$, KS$_{pub}$)}
  \item \emph{verify(S$^i_p$, $\langle i$|seed$^i\rangle$, K$^p_{pub}$)}
  \item \emph{$\forall\; n\in$[1..N], hash(branch$^i$[n]) $\in$
  branch$^i$[n-1]}
  \item \emph{{$p\rightarrow$hash(S$^i_p$)} $\in$ branch$^i$[N]}
\end{enumerate}
then the holder of the proof has the guarantee that $p$ has been communicating
with at least one other peer during the seeding phase of round $i$ starting at time $t_i$ and ending at time $t_i+T^i$.
\end{thm}

\begin{proof}
Let ($i$, seed$^i$, branch$^i$, S$^i_p$, S$^i_{pulse}$) be the proof provided by peer $p$.

\paragraph{First step: S$^i_{p}$ has been computed by $p$ after
time $t_i$}

Indeed, with test 2 we have the guarantee that S$^i_{p}$ has been computed
by $p$. Furthermore, at the time of computation $p$ knew the seed
\textsf{seed$^i$}. This seed has been generated randomly by the server at the
beginning of round $i$ : this is guaranteed by test 1 and by the integrity of
the server. Thus the time of computation of S$^i_{p}$ is posterior to $t_i$.

\paragraph{Second step: branch$^i$ has been computed before $t_i+T_i$}

By induction:

\subparagraph{Basis:} Test 1 and the integrity of the server guarantee
that branch$^i$[0] has been computed before $t_i+T_i$ (the server
sends branch$^i$[0] at time $t_i+T_i$).

\subparagraph{Inductive Step:} Let us now assume that branch$^i$[0] up to
branch$^i$[k] have been computed before $t_i+T_i$. We know (test 3)
that $t=$hash(branch$^i$[k+1])$\in$ branch$^i$[k].
Now assume by contraction that $m=$branch$^i$[k+1]) has been computed
after $t_i+T_i$ by some peer $q$. Then given $t$, $q$ has been able to compute
$m$ such that hash($m$)$=t$ which would be a successful first preimage
attack on the hash function.

\paragraph{Conclusion:} Using the first two steps and test 4, we now have the
guarantee that S$^i_{p}$ has been computed by $p$ after $t_i$ and transmitted
before $t_i+T^i$. Thus $p$ has been communicating with some peer during round
$i$.
\end{proof}

\begin{rem}
Unfortunately we have no guarantee that peer $p$ has been respecting the
protocol at all. For example he could have just received see$^i$ from a
colluding peer $q$, computed and sent back S$^i_{p}$ to $q$ who would have
inserted S$^i_{p}$ in the branch himself.
\end{rem}
\end{document}