\documentclass[a4paper,11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8x]{inputenc}
\usepackage[french]{babel}
\usepackage{graphicx}

\usepackage{listings}
\lstdefinelanguage{pseudo}
  {morekeywords={if, then, else, end, let, and, or, 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}{Remarque}

\title{Pacemaker : un protocole de mesure de disponibilité dans les réseaux pair-à-pair}
\author{Encadrant : \\ Fabrice Le Fessant \\ INRIA-Saclay \and Étudiant : \\ Thibaut Horel}
\begin{document}
\maketitle

\subsection*{Le contexte général}

Ce rapport se situe dans le domaine des réseaux pair-à-pair. Ces réseaux possèdent des propriétés de passage à l'échelle et de robustesse par opposition aux réseaux centralisés qui en font un sujet d'étude intéressant, à la fois au niveau des applications pratiques (DNS, partage de fichiers, systèmes de fichiers distribués, calcul distribué, \ldots) et de l'étude théorique. Les travaux sur les réseaux pair-à-pair portent généralement sur :
\begin{itemize}
\item la structuration des réseaux pair-à-pair, le plus souvent par la mise en place d'une Table de Hachage Distribuée (DHT).
\item la localisation de ressources dans le réseau.
\item le routage des requêtes dans le réseau.
\end{itemize}

\subsection*{Le problème étudié}

Le problème étudié plus spécifiquement ici est celui de la mesure de disponibilité des pairs, c'est-à-dire de la fraction du temps passée par les pairs sur le réseau. Cette information de disponibilité est importante car elle permet de localiser les nœuds qui peuvent être le plus utile au réseau et sur lesquels on peut s'appuyer pour structurer ou stabiliser le réseau. On peut par exemple utiliser cette information pour sélectionner un certain nombre de \emph{super-pairs} dans le réseau, qui seront connectés en une clique, les autres pairs s'organisant autour de chacun des super-pairs.

L'utilisation que l'on peut faire d'une telle information a déjà été étudiée à plusieurs reprises (\cite{Bustamante:2004:FLP:1061831.1061848, DBLP:journals/ppl/Garces-EriceBRFU03, DBLP:conf/edbtw/BernardF09}). En revanche, la réalisation effective d'une telle mesure est restée sans réponse réellement satisfaisante. À ma connaissance, les deux seuls travaux sur le sujet sont \cite{LeFessant2008b} et \cite{DBLP:journals/tpds/MoralesG09}. La solution proposée ici met l'accent sur la non-falsifiabilité de la mesure. En effet, cette information étant calculée de façon distribuée, il est impossible d'avoir une autorité garantissant la validité de l'information. La disponibilité mesurée doit donc être exacte, même en supposant un comportement malveillant de la part des pairs.  

\subsection*{La contribution proposée}

La solution proposée ici repose sur un système de \emph{preuves} : chaque pair du réseau reçoit à intervalle régulier une preuve de sa présence. L'ensemble des preuves collectées par le pair constitue un historique de sa présence passée et permet donc de connaître sa disponibilité. L'information est non falsifiable au sens où il est impossible pour le pair de fabriquer une preuve de sa présence à un instant donné s'il n'était pas présent sur le réseau à cet instant.

La solution que l'on trouve dans \cite{LeFessant2008b} repose sur le partage d'un secret relatif à un instant donné. Le protocole mis au point dans ce rapport repose sur la même idée. Toutefois il fallait empêcher la transmission du secret après la période à laquelle est associé le secret. L'idée utilisée ici consiste à \emph{figer} la connaissance du secret des nœuds présents par le calcul d'un Arbre de Merkle. Le nœud insère son secret dans l'arbre qui est calculé globalement et qui constitue donc une empreinte de la présence de l'ensemble des nœuds à un instant donné. La mise au point du protocole repose donc principalement sur le calcul distribué d'un arbre de Merkle.

\subsection*{Les arguments en faveur de sa validité}

La solution proposée semble robuste à la fois au niveau théorique (cf. théorème \ref{thm}) et expérimental. La simulation réalisée sur un grand nombre de nœuds montre que le protocole étudié fonctionne même à grande échelle. Certaines hypothèses simplificatrices ont été faites au cours de l'étude (modèle cryptographique sous-jacent, communication simplifiée, \ldots), mais le déploiement effectué sur un réseau réel montre que ces hypothèses sont raisonnables au vu des applications pratiques.

\subsection*{Le bilan et les perspectives}

Le protocole étudié dans ce rapport apporte donc une solution effective au problème posé. La simplicité relative du protocole permet une implémentation aisée. Des expériences d'utilisation de ce protocole sur différents réseaux pair-à-pair permettrait de confirmer sa robustesse dans les cas d'application très variés du pair-à-pair. En particulier, l'influence de la topologie sous-jacente n'a pas été réellement étudiée ici. De plus, il serait intéressant d'étudier si l'information de disponibilité fournie par le protocole pourrait elle-même être utilisée pour modifier dynamiquement la structure du réseau et ainsi accroître la performance du protocole.  

\tableofcontents

\newpage

\section{Introduction}
Tous les réseaux pair-à-pair ont en commun d'avoir un dynamique complexe : naissances, morts, arrivées, départs, indisponibilité temporaires peu\-vent 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 l'élection de super-pairs \cite{Bustamante:2004:FLP:1061831.1061848, DBLP:journals/ppl/Garces-EriceBRFU03} à qui sont confiées des tâches plus importantes, dans la sélection des voisins \cite{DBLP:conf/edbtw/BernardF09}, ou la structuration du réseau \cite{DBLP:conf/dais/SachaDCM06}.
\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 oracle :
\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 \cite{DBLP:journals/tpds/MoralesG09} 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'évaluation 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}

Le protocole Pacemaker réalise un compromis entre l'approche individuelle et l'approche centralisée présentée ci-dessus : chaque pair présent dans le réseau reçoit à intervalle régulier une preuve de sa présence calculée par l'ensemble du réseau, celle-ci est stockée par le pair lui-même pour être présentée au besoin à la demande des autres pairs. Cette approche résout donc naturellement le problème de \textbf{durabilité temporelle} : l'information est disponible aussi longtemps qu'elle est utile, c'est à dire, aussi longtemps que le pair est présent sur le réseau. De plus, cette approche conserve la simplicité de l'approche individuelle en évitant la communication avec des tiers pour obtenir l'information de disponibilité.

La section 2. présente le modèle et les hypothèses sur lesquels repose Pacemaker, la section 3. contient la spécification 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.

\subsection*{Remerciements}

Je tiens à exprimer toute ma gratitude envers Fabrice Le Fessant, pour la qualité et la bienveillance de son encadrement tout au long du stage, qui m'a permis d'apprendre beaucoup sur les réseaux pair-à-pair, envers Tiphaine Turpin, pour avoir patiemment répondu à toutes mes questions sur OCaml et enfin envers mon frère Guillaume pour m'avoir conseillé les outils que j'ai utilisés au cours de la partie expérimentale de ce rapport.

\section{Modèle et notations}

\subsection{Réseau}

On considère un réseau pair-à-pair constitué d'ordinateurs reliés entre eux par un réseau de communication (par exemple Internet). On suppose qu'au-dessus de ce réseau se situe un réseau logique dans lequel chaque pair ne connaît qu'une partie d'une réseau : ce sont ses voisins\footnote{C'est le cas dans la majeure partie des protocoles pair-à-pair usuels comme par exemple Gnutella ou BitTorrent.}.

Pacemaker repose également sur la présence de pairs particuliers : certains pairs ont un rôle distingué dans le réseau, on les appelle \emph{serveurs}. Pour que le protocole fonctionne, il est nécessaire que chaque pair soit dans la composante connexe d'au moins un serveur. Le protocole reste toutefois décentralisé au sens où il ne suppose pas que les serveurs possèdent des ressources physiques supérieures à celles des autres pairs.

Pacemaker peut donc fonctionner comme un service au-dessus d'un protocole pair-à-pair déjà existant, mais il peut également être vu comme un protocole indépendant qui construit et maintient son propre réseau. La section \ref{mesh} présente une méthode ad hoc pour la construction du réseau.

\subsection{Cryptographie}
On suppose que chaque pair $p$ possède une paire 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 reçoivent, 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ées comme sûres. En particulier, la fonction de hachage ci-dessus est supposée résistante aux attaques par collision.

\subsection{Notations}

On suppose pour simplifier qu'il n'y a qu'un seul serveur, et que l'on n'étudie que la composante connexe de ce serveur. Cette hypothèse n'est pas restrictive car les serveurs ne communiquent pas entre eux. La paire de clé du serveur est notée \textsf{(KS$_{pub}$, KS$_{priv}$)}. On suppose de plus que \textsf{KS$_{pub}$} est connue par l'ensemble des pairs.

Chaque pair $p$ connaît l'ensemble des pairs auxquels il est connecté, cet ensemble est noté $NS_p$. Si $q\in NS_p$ alors $p$ peut envoyer le message $m$ à $q$ en utilisant la fonction \textsf{send($q$, $m$)}.

Enfin $\langle a|b|\ldots\rangle$ représente la sérialisation des données $a$, $b$ (et plus) pour utilisation dans les fonctions primitives, notamment $\textsf{sign}$ et $\textsf{send}$. 

\section{Protocole}

\subsection{Introduction}

L'idée générale du protocole est de générer un secret à un instant donné et de le diffuser sur le réseau. La possession de ce secret assure dans une certaine mesure la présence sur le réseau au moment où celui-ci a été diffusé. Dans cette version primitive, le protocole n'assure aucune protection contre la collusion ou la falsification : un pair pourrait révéler le secret à un autre pair qui n'était pas présent au moment de la diffusion.

La solution consiste alors à calculer à un instant donné une empreinte de la connaissance du secret par l'ensemble des pairs du réseau. Le protocole procède en trois phases :
\begin{enumerate}
\item \textbf{Semailles } Le serveur génère une graine aléatoire et la diffuse dans le réseau.
\item \textbf{Récolte } Chaque pair signe la graine avec sa clé privée et calcule un hash de la signature : ce hash est appelé \emph{jeton de présence}. Il collecte ensuite les jetons de ses voisins auxquels il ajoute son propre jeton. Il obtient ainsi une table d'associations pair/jeton. Le pair hache ensuite cette table et transmet le hash obtenu à ses pairs. Enfin, le serveur calcule un hash racine de l'ensemble des jetons reçus de la part de ses fils.
\item \textbf{Pulsation } Le serveur signe le hash calculé à la fin de la phase précédente avec sa clé privée et le diffuse dans le réseau avec la liste des jetons qui ont servi au calcul du hash racine. Ce message est appelé \emph{pulsation}. Au cours de la diffusion, chaque pair ajoute à la pulsation la liste des jetons qui ont servi au calcul du hash transmis à ses parents pendant la phase précédente.
\end{enumerate}
Au cours de la phase 2, la structure de hashs obtenue est un graphe de hashs similaire à un \emph{arbre de Merkle} \cite{DBLP:conf/sp/Merkle80} ; le hash calculé par la racine constituant une empreinte de l'ensemble des jetons des nœuds du réseau. Lors de la diffusion de la pulsation dans la phase 3, chaque pair reçoit une branche de l'arbre correspondant à un chemin allant de lui-même à la racine.

La succession de ces trois phases est appelée une ronde. La pulsation reçue dans la troisième phase constitue une preuve de la présence du pair pendant la ronde (cf. théorème \ref{thm}). Les rondes se succèdent à une fréquence dépendant des applications : des rondes plus courtes permettent d'obtenir une granularité plus fine sur l'information de disponibilité au détriment d'un plus grand usage de bande passante. Le principe des rondes se retrouve notamment dans \cite{Benaloh91efficientbroadcast}.

Le protocole utilise trois messages différents, correspondant aux trois phases :
\begin{itemize}
\item \textsf{Seed($i$, seed$^i$, $T^i$, S$^i_{seed}$)} pour diffuser la graine aléatoire au cours des semailles:
  \begin{itemize}
  \item $i$ est le numéro de ronde
  \item \textsf{seed$^i$} est la graine de la $i$-ème ronde
  \item $T^i$ est la durée de la phase de récolte
  \item \textsf{S$^i_{seed}$} est \textsf{sign($\langle$$i$|seed$^i$|$T^i\rangle$, KS$_{priv}$)}
  \end{itemize}
\item \textsf{SeedReply($i$, H$_p$)} est utilisé pour construire le graphe de hashs pendant la phase de récolte où \textsf{H$_p$} est le hash envoyé par le pair $p$, c'est-à-dire le hash de la table des jetons reçus par le pair $p$.
\item \textsf{Pulse($i$, seed$^i$, branch$^i$, S$^i_{pulse}$)} pour diffuser la pulsation:
  \begin{itemize}
  \item \textsf{branch$^i$} est la liste des tables de hashs collectés pendant la phase de récolte par les pairs situés sur le chemin suivi par ce message depuis la racine.
  \item \textsf{S$^i_{pulse}$} est \textsf{sign($\langle$i|seed$^i$|H$^i$$\rangle$, KS$_{priv}$)}.
  \end{itemize}
\end{itemize}

Les sous-sections suivantes présentent la spécification détaillée du protocole.

\subsection{Semailles}

\begin{lstlisting}[caption=Serveur au début de la ronde $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}

Le serveur initialise la ronde en générant la graine aléatoire, en la signant et en l'envoyant à ses voisins. La durée de la phase de récolte est également incluse dans le message car elle est utilisée par les pairs. On peut ainsi changer dynamiquement la granularité du protocole. D'autres informations pourraient également être envoyées, par exemple le nombre maximum que doit établir chaque pair avec ses voisins, permettant des ajustements en temps réel du protocole.

Le serveur attend ensuite pendant une durée $T^i$, au cours de laquelle il reçoit les hashs de ces fils, cf. Spec. \ref{reply}.

\newpage 
\begin{lstlisting}[caption=Pair $p$ à la réception de \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}

Le pair initialise les données relatives à la ronde. map$^i$ contiendra les jetons reçus de ses voisins par le pair. Au début de la ronde, elle contient uniquement le jeton calculé par le pair $p$.

\subsection{Récolte}

\begin{lstlisting}[caption={Exécuté toutes les $\Delta << T^i$ secondes par le pair $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}

Le pair envoie le hash de la table des jetons qu'il a collectés tout en stockant l'association hash/table correspondante. Ceci est effectué toutes $\Delta$ secondes pour permettre à l'information de ``remonter'' depuis les feuilles de l'arbre jusqu'à la racine durant la phase de récolte. Plus précisément, si $D$ est le rayon du graphe par rapport à la racine, on doit avoir $D\Delta\leq T^i$. Ceci est nécessaire pour que le hash calculé par la racine à la fin de la phase de récolte constitue effectivement une empreinte de l'ensemble du graphe.

\vspace{1cm} 

\begin{lstlisting}[caption={Serveur ou pair à la réception de \textsf{SeedReply($i$,
X$_q$)} depuis le pair $q$}, label=reply]
  if phase$^i$ = SEEDING then
    map$^i$ = $\{ q \rightarrow $X$_q \} \oplus$map$^i$;
  end if
\end{lstlisting}

Le pair $p$ met simplement à jour sa table pair/jeton. Si la table contient déjà un enregistrement pour le pair $q$, celui-ci est écrasé par le nouveau jeton. En effet, le pair $q$ a pu recevoir entre temps des jetons d'autres pairs, et donc le dernier jeton envoyé contient toujours le plus d'information.

\subsection{Pulsation}

\begin{lstlisting}[caption=Serveur après avoir attendu pendant $T^i$]
  phase$^i$ = PULSE;
  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}

À la fin de la phase de récolte, le serveur hache la table des jetons de ses fils, signe le résultat et initialise la pulsation avec cette table.

\vspace{1cm}

\begin{lstlisting}[caption={Pair $p$ à la réception de \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}$) and
    phase$^i$ = SEEDING or phase$^i$ = PULSE  
  then
     phase$^i$ = PULSE;
     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}

Le pair $p$ reçoit en plus de \textsf{S$^i_{pulse}$} (la signature du hash racine par le serveur), une branche, qui est la liste des tables de jetons agrégés par les pairs sur le chemin allant de la racine à lui-même. Le pair $p$ commence donc par vérifier que la branche reçue est consistante, c'est-à-dire que :
\begin{itemize}
\item le premier élément de la branche est effectivement la table des jetons reçus par la racine (dont le hash a été signé par la racine)
\item chaque table de jetons qui fait partie de la branche a effectivement été reçue par son père (sur le chemin de la racine au pair $p$) lors de la phase de récolte : son hash doit appartenir à la table de jetons du père
\end{itemize}

Si de plus le pair $p$ apparaît dans la dernière table de la branche, c'est-à-dire dans la table d'un de ses voisins, cela signifie que le pair $p$ a envoyé un jeton à ce voisin durant la phase de récolte, et peut donc retrouver dans l'historique de ses réponses (tableau \textsf{replies} constitué pendant la récolte) la table qui a permis le calcul du jeton. Cette table est alors agrégée à la branche courante. La branche ainsi augmentée constitue la preuve (cf. Théorème \ref{thm}) de la présence du pair $p$ au cours de cette ronde et peut donc être ajoutée à son historique (tableau \textsf{History}). La variable \textsf{included$^i$} et le test \textsf{included$^i < n$} assurent que la preuve retenue par le pair $p$ correspond au jeton calculé le plus tard pendant la phase de récolte. Cette propriété est utilisée dans l'application à l'authentification de fichiers (cf. Section \ref{sign}).

\subsection{Vérification}

Le protocole prévoit trois messages supplémentaires pour la transmission et la vérification des preuves de présence.
\begin{itemize}
  \item{\sf Availability($i$, bits):} utilisé par un pair pour transmettre son historique de présence jusque à la ronde $i$. \textsf{bits} est un tableau de bits où un $0$ (resp. un 1) à l'indice $j$ signifie que le pair était absent (resp. présent) pendant la ronde $j$.
  \item{\sf Challenge($i$):} utilisé pour demander à un pair la preuve de sa présence pendant la ronde $i$.
  \item{\sf Proof($i$, seed$^i$, branch$^i$, S$^i_p$, S$^i_{pulse}$):} utilisé par le pair $p$ pour répondre à la demande de preuve de présence pour la ronde $i$.
\end{itemize}
 
Ces messages sont utilisés comme suit :
\vspace{1cm}
\begin{lstlisting}[caption=Pair $p$ transmettant à $q$ son historique de présence au cours des $N$ dernières rondes]
  let bits$^i$ = new bitfield[$N$];
  for $x$ in [1..$N$]
    if History[$i-N+x$] = $\emptyset$ then
      bits$^i$[$i-N+x$] := 0;
    else
      bits$^i$[$i-N+x$] := 1;
    end if
  end for  
  let M$^i_{avail}$ = Availability($i$, bits);
  send($q$, M$^i_{avail}$);
\end{lstlisting}

\newpage

\begin{lstlisting}[caption={Pair $p$ envoyant à $q$ la demande de preuve \textsf{Challenge($i$)}}]
  challenges[$q$] = challenges[$q$]$\oplus${$i\rightarrow$ WAITING};
  let M$^i_{challenge}$ = Challenge($i$);
  send($q$, M$^i_{challenge}$);
\end{lstlisting}
La requête est sauvée en attendant la réponse du pair questionné.

\vspace{1cm}

\begin{lstlisting}[caption={Pair $p$ recevant la demande \textsf{Challenge($i$)} du pair $q$}]
  let M$^i_{proof}$ = Proof(History[$i$]);
  send($q$, M$^i_{proof}$);
\end{lstlisting}

\begin{lstlisting}[caption={Pair $q$ recevant du pair $p$ la preuve \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}

La vérification de la preuve est assez similaire à la vérification effectuée au moment de la réception de la pulsation : il faut vérifier la consistance de la branche, mais également que le jeton du pair $p$, \textsf{S$^i_p$} est cohérent avec le hash signé par la racine, \textsf{S$^i_{pulse}$}.

\section{Analyse} 

Nous nous intéressons ici à ce que garantit une preuve fournie par un pair et approuvée par la vérification de la Spec. \ref{lst-proof}.

\begin{thm}\label{thm}
Si :
\begin{itemize}
  \item le serveur n'est pas corrompu
  \item les pairs ne partagent pas leur clé privée
\end{itemize}
Alors si le pair $p$ fournit une preuve valide de sa présence pour la ronde $i$, c'est-à-dire une preuve passant les quatre tests suivants:
\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}
alors, le pair recevant la preuve a la garantie que le pair $p$ a été en communication avec au moins un autre pair du réseau pendant la phase de récolte de la ronde $i$ commençant au temps $t_i$ et finissant au temps $t_i+T^i$.
\end{thm}

\begin{proof}
Soit ($i$, seed$^i$, branch$^i$, S$^i_p$, S$^i_{pulse}$) la preuve fournie par le pair $p$.

\paragraph{S$^i_{p}$ a été calculé par $p$ après l'instant $t_i$}

En effet, le test 2 nous assure que S$^i_{p}$ a été calculé par $p$. De plus, au moment du calcul, $p$ connaissait la graine aléatoire \textsf{seed$^i$}. Cette graine a été choisie par le serveur au début de la ronde $i$ : ceci est garantie par le test 1 (pour l'origine de la graine) et par l'intégrité du serveur (pour ne diffuser la graine qu'après le début de la ronde $i$). L'instant de calcul de S$^i_{p}$ est donc postérieur à $t_i$.

\paragraph{branch$^i$ a été calculée avant $t_i+T_i$}

Par récurrence :

\item Le test 1. et l'intégrité du serveur nous assurent que branch$^i$[0] a été calculée avant $t_i + T_i$. En effet, le serveur commence à diffuser branch$^i$[0] à l'instant $t_i+T_i$.
\item Supposons que les tables branch$^i$[0] à branch$^i$[k] aient été calculées avant $t_i+T_i$. Nous savons par le test 3. que $t=$hash(branch$^i$[k+1])$\in$ branch$^i$[k]. Supposons alors par l'absurde que $m=$branch$^i$[k+1] ait été calculée après l'instant $t_i+T_i$ par un certain pair $q$. Alors, étant donné $t$, $q$ a été capable de calculer $m$ tel que hash($m$)$=t$ ce qui serait une attaque contre la première préimage et contredit l'hypothèse faite sur la fonction de hachage.

\paragraph{Conclusion} Les deux premières étapes de la preuve et le test 4 nous assurent donc que S$^i_{p}$ a été calculé par $p$ après $t_i$ et transmis avant $t_i+T^i$. Donc $p$ a communiqué avec au mois un pair pendant la ronde $i$ pour lui transmettre S$^i_p$, ce qui prouve le résultat annoncé.
\end{proof}

\begin{rem}
Malheureusement nous n'avons pas du tout la garantie que le pair $p$ ait respecté le protocole. Il peut par exemple avoir reçu \textsf{seed$^i$} d'un pair complice $q$, puis avoir calculé et envoyé S$^i_{p}$ à $q$ qui l'aurait inséré lui-même dans le graphe de hashs. Dans ce cas, le pair s'apparente à un pair \emph{paresseux} qui refuse de coopérer au sein du réseau : il ne reçoit que l'information minimale qui lui permet de prouver sa présence, et ne transmet aucune information utile aux autres pairs.
\end{rem}

\section{Simulation}

N'ayant pas à ma disposition de réseau pair-à-pair de grande échelle, j'ai choisi de réaliser un simulateur de réseau pair-à-pair : il s'agit d'un programme permettant de tester l'efficacité du protocole sur un grand nombre de nœuds (ici 40000). La simulation effectuée est haut niveau : chaque nœud est un élément d'un tableau et peut communiquer instantanément avec les autres nœuds. En particulier, le protocole de communication sous-jacent (IP dans la pratique) n'est pas reproduit.

\subsection{Modélisation de la présence des pairs}

Plusieurs analyses \cite{Chu02availabilityand, Sacha09exploitingheterogeneity} ainsi que des analyses que j'ai faites sur des traces de réseaux pair-à-pair réels montrent que la durée des sessions (périodes durant laquelle un pair est connecté) peut être modélisée par une loi géométrique. J'ai donc choisi de modéliser la présence des pairs par une chaîne de Markov à deux états, ON et OFF. La matrice de transition de la chaîne est entièrement déterminée par deux paramètres, $\lambda$ et $\mu$, respectivement la probabilité de passer de OFF à ON et de OFF à ON. Il est immédiat que la durée d'une session (temps passé dans l'état ON) suit une loi géométrique de paramètre $\mu$ (et donc d'espérance $\frac{1}{\mu}$). De plus il est connu que les fractions du temps passé dans l'état ON et OFF sont les probabilités de la loi stationnaire associée à la chaîne :

\begin{displaymath}
t_{OFF} = \frac{\mu}{\lambda + \mu} \qquad t_{ON} = \frac{\lambda}{\lambda + \mu}
\end{displaymath}

$t_{ON}$ est la fraction du temps passée dans l'état ON, c'est-à-dire la disponibilité du pair telle que définie en introduction. Pour un pair donné, les deux paramètres $\lambda$ et $\mu$ peuvent donc être choisis de la façon suivante : on fixe l'espérance du temps de session $E$, et la disponibilité du pair $d$ et on résout le système :

\begin{displaymath}
E = \frac{1}{\mu} \qquad d = \frac{\lambda}{\lambda + \mu}
\end{displaymath}

\subsection{Construction du réseau}\label{mesh}

Comme mentionné plus haut, \emph{Pacemaker} peut être utilisé au-dessus d'un réseau pair-à-pair déjà existant, ou comme un service indépendant. Dans ce cas, c'est au protocole qu'il incombe de construire et maintenir les connections entre les pairs. Le protocole choisi dans cette simulation est relativement simple. Chaque nœud du réseau à un degré égal à 10, c'est-à-dire qu'il peut établir au plus 10 connections avec d'autres pairs du réseau (ce qui semble raisonnable au vu des applications pratiques). Au moment où le pair se connecte, il envoie un message \textsf{Mesh} à la racine. Celle-ci accepte le pair si elle a une place vacante, et envoie au pair la liste de ses fils dans le réseau. Le pair contacte alors les fils en envoyant à chacun un message \textsf{Mesh}. Si le nœud contacté a une place vacante, il accepte le pair, sinon il lui indique un pair choisi au hasard parmi ses fils. Le processus est répété jusqu'à que le pair ait 10 voisins.

Le but de ce processus d'insertion est d'avoir un faible rayon par rapport à la racine, et ainsi permettre une diffusion rapide des messages au cours des rondes. À noter également que le réseau ainsi obtenu est redondant au sens suivant : il existe plusieurs chemins allant d'un nœud à la racine. Ceci est capital pour assurer la robustesse du protocole en cas de déconnexion des pairs.

\begin{center}
\begin{figure}[h]
\includegraphics[scale=0.6]{mesh.eps}
\caption{Répartition des pairs dans le réseau. Pour 100,000 pairs, la distance maximale à la racine est de 7.}
\end{figure}
\end{center}

Une optimisation consiste à arrêter le processus de recherche de voisins à partir d'un certain seuil. L'effet recherché est d'éviter les pairs déjà présent de constituer des cliques, qui rendrait l'insertion de nouveaux pairs très difficile. Les tests effectués au cours de la simulation montrent que pour un degré 10, le seuil de 8 (c'est-à-dire qu'un pair stoppe le processus de recherche dès qu'il est connecté à 8 voisins) semble réaliser un bon compromis entre connectivité suffisante et facilité d'insertion. En effet, dans les simulations effectuées, tous les nœuds trouvent au moins un voisin en moins de trois itérations du processus d'insertion dans le réseau.  

\subsection{Résultats}

Le simulateur a été écrit en OCaml. Le code final comprend environ 800 lignes, dont 250 pour les définitions des types et des modules servant à représenter les pairs, 150 pour l'implémentation du protocole en lui-même, 70 pour la construction du réseau, 70 pour la simulation de connexion des pairs, 150 pour la simulation des actions des pairs, le reste étant les fonctions générales d'entrée/sortie et la journalisation des données.

La simulation a été effectuée pour 40000 nœuds, sur une période simulée de 10 jours. Le simulateur procède par itérations successives : à chaque itération, chaque pair traite l'ensemble des messages qu'il a reçus au cours de l'itération précédente conformément à la spécification du protocole. Chaque itération simule une période de 20 secondes, en particulier, les messages envoyés ne sont reçus que 20 secondes plus tard, ce qui est pessimiste comparé à la réalité.

La disponibilité des pairs a été choisie uniforme sur l'intervalle $[0, 1]$, et la durée moyenne de connexion en minutes uniforme sur l'intervalle $[20, 500]$. La fréquence des rondes du protocole a été choisie égale à 10 minutes.

\begin{figure}[!h]
\begin{center}
\includegraphics[scale=0.55]{cdf.eps}
\caption{Fonction cumulative empirique de l'erreur relative de la mesure de disponibilité des pairs. 90\% des pairs ont une erreur relative inférieure à 2\%}
\end{center}
\end{figure}

L'erreur de mesure sur la disponibilité d'un pair est définie comme étant la différence entre le temps de présence réel du pair et le temps de présence qu'il est capable de prouver avec les preuves qu'il a reçues. On considère que l'obtention d'une preuve prouve la présence du pair pendant toute la durée de la ronde. En effet :
\begin{itemize}
\item le pair n'a aucun moyen de prévoir le moment de la ronde ou il recevra la preuve, ce qui protège le protocole des pairs opportunistes qui se connecteraient juste assez longtemps pour obtenir une preuve.
\item si le pair quitte le réseau entre la phase de semailles et la phase de récolte, sa position dans le réseau change et il n'apparaîtra donc pas dans les tables de jetons qu'il recevra de ses parents.
\end{itemize}

Si $M$ représente le nombre de minutes pendant lesquelles le pair a été connecté, $N$ le nombre de preuves reçues par le pair, et $T$ la durée des rondes, l'erreur relative de disponibilité est donc définie par :
\begin{displaymath}
\delta = \frac{M-TN}{M}
\end{displaymath}

À noter également que si la durée typique des sessions d'un pair est plus petite que la durée d'une ronde du protocole, le pair risque de ne pas recevoir de preuve pour cette session et donc la mesure de disponibilité perd de sa précision. Toutefois, dans la pratique, on cherche principalement à obtenir une garantie pour les pairs à forte disponibilité. Le risque principal étant les \emph{faux-positifs} par exemple dans le cas de l'élection de super-pairs.

\section{Implémentation}

L'implémentation réelle a également été écrite en OCaml et comprend environ 800 lignes de code, dont 250 pour les déclarations de type, 200 pour le protocole lui-même, 150 pour la construction du réseau, le reste étant les fonctions générales d'entrée/sortie et appels systèmes. Le protocole de communication utilisé est UDP et le protocole de construction du réseau est celui décrit en section \ref{mesh}. 

Le déploiement a été fait sur PlanetLab, un réseau d'ordinateurs mis en commun par différentes institutions et universités à travers le monde. Je n'ai malheureusement pu avoir accès qu'à 161 ordinateurs du réseau. Le nombre d'ordinateurs connectés en même temps a varié entre 139 et 161 au cours de l'expérimentation. L'expérimentation est encore en cours sur PlanetLab, les résultats seront donc présentés au cours de la soutenance.

\section{Application à la signature de documents}\label{sign}

Ce protocole peut également être utilisé pour la preuve de possession de documents électroniques. En effet, si l'on reprend la conclusion du théorème~\ref{thm}, le protocole assure que pour tout pair $p$ présent durant la ronde $i$ commençant à l'instant $t_i$,  S$^i_{p}$ a été calculé par $p$ après $t_i$ et transmis avant $t_i+T^i$. Dans le protocole, S$^i_{p}$, le jeton du pair $p$, n'est rien d'autre que la graine aléatoire de la ronde $i$ signée avec la clé privée du pair $p$. Le pair pourrait en fait signer des informations supplémentaires, comme le hash d'un fichier qu'il possède au moment de la ronde $i$, l'insertion du jeton dans l'arbre de Merkle calculé au cours de la ronde, constitue alors une preuve qu'il possédait ce fichier à cet instant : en effet, il lui suffira d'exhiber ultérieurement le fichier dont le hash est celui qui avait été inséré dans l'arbre de Merkle.

Dans le cas de la preuve de possession de plusieurs documents, l'utilisateur pourrait ajouter à son jeton l'ensemble des hashs de ses propres documents. Toutefois, ceci devient problématique dans le cas où le nombre de documents devient important, car la taille des données échanger entre les pairs doit rester la plus petite possible. La solution consiste à utiliser localement un abre de Merkle, de façon analogue à \cite{DBLP:conf/eurocrypt/BenalohM93} : le pair organise ses fichiers selon un arbre de Merkle binaire, et seul le hash de la racine est ajouté au jeton. La preuve de la possession du fichier consiste alors, comme dans \cite{DBLP:conf/sp/Merkle80}, à fournir les hashs des fichiers qui permettent de recalculer le hash de la racine. Il suffit alors de vérifier que le hash obtenu correspond au hash qui a été inséré par le protocole au cours de la ronde.

\bibliographystyle{plain}
\bibliography{biblio}

\end{document}
