diff options
Diffstat (limited to 'stage/article.tex')
| -rw-r--r-- | stage/article.tex | 130 |
1 files changed, 78 insertions, 52 deletions
diff --git a/stage/article.tex b/stage/article.tex index 37761ca..823c8d6 100644 --- a/stage/article.tex +++ b/stage/article.tex @@ -36,17 +36,17 @@ Ce rapport se situe dans le domaine des réseaux pair-à-pair. Ces réseaux poss 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 (REFERENCE). 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 REFERENCE. 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. +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 REFERENCE 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 Merkel. Cette structure de donnée contient une information globale sur le réseau et ne peut donc pas être calculé par un seul nœud. La mise au point du protocole repose donc principalement sur le calcul distribué d'un arbre de Merkel. +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. REFERENCE) 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 éte 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. +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} @@ -57,25 +57,25 @@ Le protocole étudié dans ce rapport apporte donc une solution effective au pro \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. +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 la structuration du réseau, ou bien par l'élection de super-peer (cf. ...) ou dans la sélection des voisins (cf. backup) +\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 +\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'é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} @@ -92,7 +92,7 @@ Le but du présent rapport est donc de présenter et d'étudier le protocole \em 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. +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} @@ -106,23 +106,23 @@ On considère un réseau pair-à-pair constitué d'ordinateurs reliés entre eux 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. +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 : +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. +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 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$)}. +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}$. @@ -130,17 +130,17 @@ Enfin $\langle a|b|\ldots\rangle$ représente la sérialisation des données $a$ \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. +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. +\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. +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 (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. +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} @@ -151,7 +151,7 @@ Le protocole utilise trois messages différents, correspondant aux trois phases \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 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{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. @@ -174,9 +174,9 @@ Les sous-sections suivantes présentent la spécification détaillée du protoco 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 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. REFERENCE. +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$, @@ -210,12 +210,12 @@ Le pair initialise les données relatives à la ronde. map$^i$ contiendra les je 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. +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$}] +X$_q$)} depuis le pair $q$}, label=reply] if phase$^i$ = SEEDING then map$^i$ = $\{ q \rightarrow $X$_q \} \oplus$map$^i$; end if @@ -226,7 +226,7 @@ Le pair $p$ met simplement à jour sa table pair/jeton. Si la table contient dé \subsection{Pulsation} \begin{lstlisting}[caption=Serveur après avoir attendu pendant $T^i$] - phase$^i$ = IDLE; + phase$^i$ = PULSE; let H$^i$ = hash(map$^i$); let branch$^i$ = $\emptyset$; branch$^i$[0] = map$^i$; @@ -240,10 +240,11 @@ Le pair $p$ met simplement à jour sa table pair/jeton. Si la table contient dé \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}$) then - phase$^i$ = IDLE; + 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 @@ -260,13 +261,13 @@ Le pair $p$ met simplement à jour sa table pair/jeton. Si la table contient dé 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 : +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 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). +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} @@ -279,7 +280,7 @@ Le protocole prévoit trois messages supplémentaires pour la transmission et la 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$ derniers rounds] +\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 @@ -301,6 +302,8 @@ Ces messages sont utilisés comme suit : \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}$); @@ -325,11 +328,9 @@ La vérification de la preuve est assez similaire à la vérification effectuée \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} +\begin{thm}\label{thm} Si : \begin{itemize} \item le serveur n'est pas corrompu @@ -365,16 +366,16 @@ Par récurrence : \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. +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 particuler, le protocole de communication sous-jacent (IP dans la pratique) n'est pas reproduit. +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 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$ (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 : +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 chê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} @@ -386,37 +387,62 @@ $t_{ON}$ est la fraction du temps passée dans l'état ON, c'est-à-dire la disp E = \frac{1}{\mu} \qquad d = \frac{\lambda}{\lambda + \mu} \end{displaymath} -\subsection{Construction du réseau} +\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 de gré é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épeté jusqu'à que le pair ait 10 voisins. +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 (cf. REFERENCE), 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éconnection des pairs. +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.} +\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 consistuer 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. +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 connection 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. +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} -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é. +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} -La disponibilité des pairs a été choisie uniforme sur l'intervalle $[0, 1]$, et la durée moyenne de connection en minutes uniforme sur l'intervalle $[20, 500]$. Les résultats obtenus figurent ci-dessous : +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} -IMAGE +À 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 envrion 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 REFERENCE. +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. -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 qui a duré 19 jours. +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. -\section{Conclusion, application à la signature de documents} +\bibliographystyle{plain} +\bibliography{biblio} -\end{document}
\ No newline at end of file +\end{document} |