\documentclass[a4,11pt,titlepage]{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 encadré par Fabrice Le Fessant}
\begin{document}

\maketitle
\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 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 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 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}

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é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}

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éoendant qui construit et maintient son propre réseau. La section ... 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 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. En particulier, la fonction de hachage ci-dessus est considérée comme 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 paris 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énerale 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} (REFERENCE) ; 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 (REFERENCE). 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 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_{pulse}$} 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 graph 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 example 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. REFERENCE.

\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'ensenble du graphe.

\begin{lstlisting}[caption={Serveur ou pair à la réception de \textsf{SeedReply($i$,
X$_q$)} depuis le pair $q$}]
  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$ = 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}

À 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.

\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}$) 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}

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 aggré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 cacul du jeton. Cette table est alors agrégée à la branche courante. La branche ainsi augmentée constitue la preuve (REFERENCE) 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 (REFERENCE).

\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 :
\begin{lstlisting}[caption=Pair $p$ transmettant à $q$ son historique de présence au cours des $N$ derniers rounds]
  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}

\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é.

\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} 

\subsection{Non falsifiabilité}

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

\begin{thm}
Si :
\begin{itemize}
  \item le serveur n'est pas corrompu
  \item les pairs ne partagent pas leur clé privé
\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ère é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 graph 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 plutôt haut niveau car elle ne simule pas l
\subsection{Modélisation de la présence des pairs}
Plusieurs analyes (REFERENCE) 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 chaine de Markov à deux états, ON et OFF. La matrice de transition de la chaine 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$. De plus il est connu que les fraction du temps passé dans l'état ON et OFF sont les inverses de la probabilité stationnaire de la chaine :
\subsection{Construction du réseau}

\subsection{Résultats}

\section{Implémentation}

\section{Conclusion, application à la signature de documents}

\end{document}