diff options
Diffstat (limited to 'stage')
| -rw-r--r-- | stage/article.tex | 181 |
1 files changed, 95 insertions, 86 deletions
diff --git a/stage/article.tex b/stage/article.tex index 5809b93..55f89f3 100644 --- a/stage/article.tex +++ b/stage/article.tex @@ -1,4 +1,4 @@ -\documentclass[a4,11pt]{article} +\documentclass[a4,11pt,titlepage]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage[french]{babel} @@ -21,6 +21,8 @@ basicstyle=\small, keywordstyle=\bfseries, captionpos=b} \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. @@ -90,82 +92,42 @@ Enfin $\langle a|b|\ldots\rangle$ représente la sérialisation des données $a$ \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{Semaille :} Le serveur génére une graine aléatoire et la diffuse dans le réseau. -\item \textbf{Signature et hachage :} Chaque pair signe la graine avec sa clé privée et calcule un hash de la signature. Il collecte ensuite les hashs de ses voisins auxquels il ajoute son propre hash. Le pair hache ensuite le tableau de hashs ainsi obtenu puis le transmet à ses pairs. Enfin, le serveur calcule un hash racine de l'ensemble des hashs 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 hashs qui ont servi au calcul du hash racine. Ce message est appelé \emph{pulsation}. Au cours de la diffusion, les pairs ajoutent à la pulsation la liste des hashs 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, -On obtient ainsi un arbe de hashage (cf. Merkel, De mare). - -\subsection{Semaille} - -The server generates a unique seed and initiates -a seed pulse which is diffused through the network. Upon receiving the seed, -each peer signs it with his private key and hashes it. This hash is called the -\emph{token} of the peer. - -\textsf{Seed($i$, seed$^i$, $T^i$, S$^i_{seed}$)} is used to diffuse the seed -pulse during this phase, where: -\begin{itemize} - \item $i$ is the round number. - \item \textsf{seed$^i$} is the seed of round $i$. - \item $T^i$ is the duration of the seeding phase. - \item \textsf{S$^i_{pulse}$} is - \textsf{sign($\langle$$i$|seed$^i$|$T^i\rangle$, KS$_{priv}$)}. -\end{itemize} - -\subsection{Signature et hachage} +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. -Each peer starts collecting the tokens of his -neighbors and adds his own token to the collected hashes, obtaining a -peer-token map. The hash of this map yields a new token which is sent back to -the neighbors. This progressively builds a hash graph, until the root -server itself hashes the tokens of its children. +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. -\textsf{SeedReply($i$, H$_p$)} is used to build the hash graph during this phase, -where \textsf{H$_p$} is the token sent by peer $p$, that is, the hash of -the collected map of the tokens received by peer $p$. - -\subsubsection{Pulsation} - -The server initiates a new pulse with the map it has -collected from its childrens. Upon receiving the pulse, each peer adds to the -pulse the map associated with the token that has been collected during -Phase 2. Thus, each peer receives a list of hash maps -corresponding to a path from the root to himself in the hash graph computed during Phase 2. - -\textsf{Pulse($i$, seed$^i$, branch$^i$, S$^i_{pulse}$)} is used to diffuse the pulse during this -phase, where: +Le protocole utilise trois messages différents, correspondant aux trois phases : \begin{itemize} - \item \textsf{branch$^i$} is a list of hash maps associated to a path from the server - to the current peer. - \item \textsf{S$^i_{pulse}$} is \textsf{sign($\langle$i|seed$^i$|H$^i$$\rangle$, KS$_{priv}$)}. +\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} -\subsubsection*{Challenges} +Les sous-sections suivantes présentent la spécification détaillée du protocole. -The protocol also provides the following request/reply logic to challenge the -availability of a peer: +\subsection{Semailles} -\begin{itemize} - \item{\sf Availability($i$, bits):} used by a peer to send his avaibility - history up to round $i$. \textsf{bits} is a bit array where a $0$ (resp. 1) - bit at index $j$ means that the peer was absent (resp. available) during round - $j$. - \item{\sf Challenge($i$):} used to ask a peer the proof of his presence - during round $i$. - - \item{\sf Proof($i$, seed$^i$, branch$^i$, S$^i_p$, S$^i_{pulse}$):} to answer - a challenge, where \textsf{S$^i_p$} is \textsf{sign($\langle$i|seed$^i$$\rangle$, K$^p_{priv}$)}. -\end{itemize} - -\subsection{Phase 1: Seeding} - -\begin{lstlisting}[caption=Server at round $i$] +\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}$); @@ -176,8 +138,12 @@ availability of a peer: wait $T^i$; \end{lstlisting} -\begin{lstlisting}[caption={Peer $p$ receiving \textsf{Seed($i$, -seed$^i$, $T^i$, S$^i_{seed}$)}}] +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 @@ -193,9 +159,11 @@ seed$^i$, $T^i$, S$^i_{seed}$)}}] end if \end{lstlisting} -\subsection{Phase 2: Hashing} +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={Every $\Delta << T^i$ seconds, on peer $p$}] +\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$); @@ -205,16 +173,20 @@ seed$^i$, $T^i$, S$^i_{seed}$)}}] end if \end{lstlisting} -\begin{lstlisting}[caption={Server or peer receiving \textsf{SeedReply($i$, -X$_q$)} from peer $q$}] +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} -\subsection{Phase 3: Pulse} +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. -\begin{lstlisting}[caption=Server at round $i$ (after having waited $T^i$)] +\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$; @@ -224,7 +196,9 @@ X$_q$)} from peer $q$}] $\forall q \in$ NS$_{server}$, send($q$, M$^i_{pulse}$); \end{lstlisting} -\begin{lstlisting}[caption={Peer $p$ receiving \textsf{Pulse($i$, seed$^i$, branch$^i$, S$^i_{pulse}$)}}] +À 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 @@ -245,33 +219,51 @@ X$_q$)} from peer $q$}] end if \end{lstlisting} -\subsection{Challenges} -\begin{lstlisting}[caption=Peer $p$ sending to $q$ his availability over the last $N_t$ rounds] - let bits$^i$ = new bitfield[$N_t$]; - for $x$ in [1..$N_t$] - if History[$i-N_t+x$] = $\emptyset$ then - bits$^i$[$x$] := 0; +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$[$x$] := 1; + 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={Peer $p$ sending to $q$ \textsf{Challenge($i$)}}] +\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={Peer $p$ receiving \textsf{Challenge($i$)} from peer -$q$}] + +\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} -\newpage -\begin{lstlisting}[caption={Peer $q$ receiving from peer $p$ \textsf{Proof($i$, seed$^i$, branch$^i$, S$^i_p$, S$^i_{pulse}$)}}, label=lst-proof] + +\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 @@ -354,6 +346,23 @@ 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} |