Preuve de non falsifiabilite

git-svn-id: https://scm.gforge.inria.fr/svn/pacemaker@64 30fcff6e-8de6-41c7-acce-77ff6d1dd07b

1 files changed, 23 insertions, 63 deletions

diff --git a/stage/article.tex b/stage/article.tex
index 55f89f3..af32985 100644
--- a/stage/article.tex
+++ b/stage/article.tex
@@ -227,10 +227,9 @@ Le pair $p$ reçoit en plus de \textsf{S$^i_{pulse}$} (la signature du hash raci
 
 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}
+\subsection{Vérification}
 
-
-Enfin, le protocole prévoit trois messages supplémentaires pour la transmission et la vérification des preuves de présence.
+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$.
@@ -256,7 +255,7 @@ Ces messages sont utilisés comme suit :
   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$]);
@@ -277,21 +276,21 @@ Ces messages sont utilisés comme suit :
      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é}
-The first problem to be adressed is the guarantee given by a proof provided by a
-peer in Spec. \ref{lst-proof}.
+
+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}
-Assuming that:
+Si :
 \begin{itemize}
-  \item the server is not corrupted
-  \item peers do not share private keys
+  \item le serveur n'est pas corrompu
+  \item les pairs ne partagent pas leur clé privé
 \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:
+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}$)}
@@ -300,74 +299,35 @@ is a proof satisfying the following four tests:
   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$.
+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}
-Let ($i$, seed$^i$, branch$^i$, S$^i_p$, S$^i_{pulse}$) be the proof provided by peer $p$.
+Soit ($i$, seed$^i$, branch$^i$, S$^i_p$, S$^i_{pulse}$) la preuve fournie par le pair $p$.
 
-\paragraph{First step: S$^i_{p}$ has been computed by $p$ after
-time $t_i$}
+\paragraph{S$^i_{p}$ a été calculé par $p$ après l'instant $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$.
+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{Second step: branch$^i$ has been computed before $t_i+T_i$}
+\paragraph{branch$^i$ a été calculée avant $t_i+T_i$}
 
-By induction:
+Par récurrence :
 
-\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$).
+\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.
 
-\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$.
+\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}
-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.
+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}
 
-\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}
-
+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}