path: root/stage/article.tex

\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{Défis}


Enfin, 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}


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

\section{Analyse} 

\subsection{Non falsifiabilité}
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}

\subsection{Détection des pairs menteurs}
\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}


\section{Simulation}

\subsection{Modélisation de la disponibilité des pairs}

\subsection{Construction du réseau}

\subsection{Résultats}

\section{Implémentation}

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

\end{document}