From 965a27eb2690de09861a254759aa3f8c79dfbcc7 Mon Sep 17 00:00:00 2001
From: thibauth <thibauth@30fcff6e-8de6-41c7-acce-77ff6d1dd07b>
Date: Fri, 22 Apr 2011 15:38:22 +0000
Subject: Hopefully a clean and working (?) version of the protocol. The
 duration of the seeding phase is now sent in the seed message. This way, the
 peers don't have to know it in advance, and the server can choose to change
 it between rounds

git-svn-id: https://scm.gforge.inria.fr/svn/pacemaker@8 30fcff6e-8de6-41c7-acce-77ff6d1dd07b
---
 stage/article.tex | 245 +++++++++++++++++++++++++++++-------------------------
 1 file changed, 132 insertions(+), 113 deletions(-)

(limited to 'stage/article.tex')

diff --git a/stage/article.tex b/stage/article.tex
index e500d96..b373384 100644
--- a/stage/article.tex
+++ b/stage/article.tex
@@ -14,28 +14,9 @@ basicstyle=\sffamily\small, keywordstyle=\sffamily\bfseries}
 
 \maketitle
 
-\section{Base protocol}
+\section{Protocol}
 
-\subsection{Principle}
-
-\begin{itemize}
-  \item{\bf Phase 1:} 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 its private key and hashes it. This hash is called the
-  \emph{token} of the peer.
-  \item{\bf Phase 2:} Each peer starts collecting the tokens of its
-  neighbors and add its own hash 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 tree until the root
-  server itselfs hashes the tokens of its children.
-  \item{\bf Phase 3:} 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 branch from the root to itself in the hash tree computed during phase 2. 
-\end{itemize}
-
-\subsection{Messages}
+\subsection{Assumptions and notations}
 
 It is assumed that each peer $p$ has a pair of public/private key
 \textsf{(K$^p_{pub}$, K$^p_{priv}$)} and has access to the 3
@@ -46,135 +27,167 @@ following cryptographic primitives:
  \item{\sf verify(S, data, K$_{pub}$):} Verifies that \textsf{S} is a
  signature for \textsf{data} that was created using the private key
  \textsf{K$_{priv}$} associated with \textsf{K$_{pub}$}.
-
  \item{\sf hash(data):} Returns the hash of \textsf{data}.
 \end{itemize}
 
 The key pair of the server will be denoted by \textsf{(KS$_{pub}$,
-KS$_{priv}$)}. \textsf{KS$_{pub}$} is assumed to be known by every peer. 
+KS$_{priv}$)}. \textsf{KS$_{pub}$} is assumed to be known by every peer.
+
+Each peer $p$ knows the list of peers to whom he is connected, this list is denoted by $NS_p$.
+If $q\in NS_p$ then $p$ can send the message $m$ to $q$ using the function \textsf{send($q$, $m$)}.
+
+$\langle a, b, \ldots\rangle$ will be used to denote the serialisation (depending on the implemetation) of
+two or more pieces of data.
+
+\subsection{Principle}
+
+The protcol works in three phases:
+
+\subsubsection*{Phase 1: Seeding}
+
+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.
 
-The following messages are used in the protocol :
+\textsf{Seed($i$, seed$^i$, $T$, S$^i_{seed}$)} is used to diffuse the seed
+pulse during this phase, where:
 \begin{itemize}
-  \item{\sf Seed($i$, seed$^i$, S$^i_{seed}$):} used to diffuse the seed
-  pulse during phase 1, where:
-  \begin{itemize}
-  	\item $i$ is the round number.
-  	\item \textsf{seed$^i$} is the seed of round $i$.
-  	\item \textsf{S$^i_{pulse}$} is \textsf{sign(<$i$, seed$^i$>, KS$_{priv}$)}.
-  \end{itemize}
-  
-  \item{\sf SeedReply($i$, H$_p$):} used to build the hash tree during Phase 2,
-  where \textsf{H$_p$} is the token received from peer $p$, that is, the hash of
-  the collected map of the tokens received by peer $p$.
-  
-  \item{\sf Pulse($i$, seed$^i$, H$^i$, level, branch$^i$, S$^i_{pulse}$):} used
-  during Phase 3. Where:
-  \begin{itemize}
-    \item \textsf{H$^i$} is the hash of the map built by the server during
-    phase 2.
-    \item \textsf{level} is the current level in the branch built from the root
-    server to the current peer.
-    \item \textsf{branch$^i$} is a branch of hash maps going from the server
-    to the current peer. This branch is a part of the hash tree built during
-    phase 2.
-    \item \textsf{S$^i_{pulse}$} is \textsf{sign(<i, seed$^i$, H$^i$>, KS$_{priv}$)}
-  \end{itemize}
+	\item $i$ is the round number.
+	\item \textsf{seed$^i$} is the seed of round $i$.
+	\item $T$ is the length of the seeding phase.
+	\item \textsf{S$^i_{pulse}$} is \textsf{sign($\langle$$i$, seed$^i$, $T$$\rangle$, KS$_{priv}$)}.
+\end{itemize}
+
+\subsubsection*{Phase 2: Hashing}
+
+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. 
+
+\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*{Phase 3: Pulse}
+
+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:
+\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}$)}.
 \end{itemize}
- 
+
+\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 its avaibility
+  \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 its presence
+  \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_{pulse}$, S$^i_p$):} to answer
-  a challenge, where \textsf{S$^i_p$} is \textsf{sign(<i, seed$^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}
 
-A peer can also choose to send its availability history up to round $i$
+\subsection{Phase 1: Seeding}
 
-\subsection{Protocol}
-
-\subsubsection{Proof building}
 \begin{lstlisting}[title=Server at round $i$]
-  let phase$^i$ = Seeding;
+  let phase$^i$ = SEEDING;
   let seed$^i$ = random_seed();
-  let S$^i_{seed}$ = sign(<$i$,seed$^i$>, KS$_{priv}$);
-  let M$^i_{seed}$ = Seed($i$, seed$^i$, S$^i_{seed}$);
-  let map$^i$ = $\emptyset$
+  let S$^i_{seed}$ = sign($\langle$$i$,seed$^i$, $T$$\rangle$, KS$_{priv}$);
+  let M$^i_{seed}$ = Seed($i$, seed$^i$, $T$, S$^i_{seed}$);
+  let map$^i$ = $\emptyset$;
   $\forall q \in$ NS$_{server}$, send($q$, M$^i_{seed}$);
 
   wait $T$;
-
-  phase$^i$ = Idle;
-  H$^i$ = Hash(map$^i$);
-  let S$^i_{pulse}$ = sign(<$i$,seed$^i$,H$^i$>, KS$_{priv}$);
-  let M$^i_{pulse}$ = Pulse($i$, seed$^i$, H$^i$, 0, 
-                      $\{$ 0 $\rightarrow$ map$^i$ $\}$, S$^i_{pulse}$); 
-  $\forall q \in$ NS$_{server}$, send($q$, M$^i_{pulse}$);
 \end{lstlisting}
 
-\begin{lstlisting}[title={Server or peer receiving \textsf{SeedReply($i$,
-X$_q$)} from peer $q$}]
-  if phase$^i$ = Seeding then
-    map$^i$ = $\{ q \rightarrow $X$_q \} \oplus$map$^i$;
+\begin{lstlisting}[title={Peer $p$ receiving \textsf{Seed($i$,
+seed$^i$, $T$, S$^i_{seed}$)}}]
+  if
+    verify(S$^i_{seed}$, $\langle$$i$,seed$^i$,$T$$\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 phase$^i$ = SEEDING;
   end if
 \end{lstlisting}
 
+\subsection{Phase 2: Hashing}
+
 \begin{lstlisting}[title={Every $\Delta << T$ seconds, on peer $p$}]
-  if phase$^i$ = Seeding then
-    let H$^i$ = H(map$^i$);
+  if phase$^i$ = SEEDING then
+    let H$^i$ = hash(map$^i$);
     let M$^i_{seedreply}$ = SeedReply($i$, H$^i$);
-    nreplies$^i$ = nreplies$^i$ + 1;
+    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}
 
-\begin{lstlisting}[title={Peer $p$ receiving M$^i_{seed}$ = \textsf{Seed($i$,
-seed$^i$, S$^i_{seed}$)}}]
-  if
-    verify_sig(S$^i_{seed}$, <$i$,seed$^i$>, KS$_{pub}$)
-  then
-    $\forall q \in$ NS$_p$, send($q$, M$^i_{seed}$);    
-
-    let S$^i_p$ = sign(<$i$,seed$^i$>, K$^p_{priv}$);
-    let map$^i$ = $\{p \rightarrow H(S^i_p)\}$;
-    nreplies$^i$ = 0;
-    phase$^i$ = Seeding;
+\begin{lstlisting}[title={Server or peer receiving \textsf{SeedReply($i$,
+X$_q$)} from peer $q$}]
+  if phase$^i$ = SEEDING then
+    map$^i$ = $\{ q \rightarrow $X$_q \} \oplus$map$^i$;
   end if
 \end{lstlisting}
 
-\begin{lstlisting}[title={Peer $p$ receiving \textsf{Pulse($i$, seed$^i$, H$^i$,
-level, tree$^i$, S$^i_{pulse}$)}}]
+\subsection{Phase 3: Pulse}
+
+\begin{lstlisting}[title=Server at round $i$ (after having waited $T$)]
+  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}
+
+\begin{lstlisting}[title={Peer $p$ receiving \textsf{Pulse($i$, seed$^i$, branch$^i$, S$^i_{pulse}$)}}]
   if
-    verify_sig(S$^i_{pulse}$, <$i$,seed$^i$,H$^i$>, KS$_{pub}$) 
+    verify(S$^i_{pulse}$, $\langle$$i$,seed$^i$,hash(branch$^i$[0])$\rangle$, KS$_{pub}$) 
   then
-     phase$^i$ = Idle;
-     included$^i$ = $\bot$;
+     phase$^i$ = IDLE;
+     let level = length(branch$^i$)-1;
      if
-       $\exists$ $\{$ $p$ $\rightarrow$ H$^i$ $\}$ $\in$ tree$^i$[level] and
-       $\exists$ $n$ $|$ replies[$n$] = (H$^i$, oldmap$^i$) and
-       included$^i$ $<$ $n$ and
-       verify_tree(H$^i$, level, tree$^i$)
+       $\exists$ {$p$ $\rightarrow$ H$^i$} $\in$ branch$^i$[level] and
+       $\exists\; n\; |$replies[$n$] = (H$^i$, oldmap$^i$) and
+       included$^i$ $$\langle$ n$ and
+       $\forall\; n\in$[1..level], hash(branch$^i$[n]) $\in$ branch$^i$[n-1]
      then
-       let tree'$^i$ = tree$^i$$\oplus$$\{$level+1 $\rightarrow$ oldmap$^i$$\}$;
-       let M$^i_{pulse}$ = Pulse($i$, seed$^i$, H$^i$, level+1, tree'$^i$, S$^i_{pulse}$);
-       History[$i$] = M$^i_{pulse}$;
+       let branch'$^i$ = 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$ children$^p$, send($q$, M$^i_{pulse}$);
+       $\forall q \in$ NS$_p$, send($q$, M$^i_{pulse}$);
     end if
   end if
 \end{lstlisting}
 
-\subsubsection{Challenges}
-\begin{lstlisting}[title=Peer $p$ sending to $q$ its availability at round $i$]
+\subsection{Challenges}
+\begin{lstlisting}[title=Peer $p$ sending to $q$ his availability at round $i$ 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
@@ -184,27 +197,33 @@ level, tree$^i$, S$^i_{pulse}$)}}]
     end if
   end for  
   let M$^i_{avail}$ = Availability($i$, bits);
-  send($q$, M$^i_{avail}$)
+  send($q$, M$^i_{avail}$);
+\end{lstlisting}
+
+\begin{lstlisting}[title={Peer $p$ sending to $q$ \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}[title={Peer $p$ receiving \textsf{Challenge($i$)} from peer
 $q$}]
-  let M$^i_{pulse}$ = History[$i$];
-  send($q$, Proof M$^i_{pulse}$)
+  let M$^i_{pulse}$ = Proof(History[$i$]);
+  send($q$, M$^i_{pulse}$);
 \end{lstlisting}
 
-\begin{lstlisting}[title={Peer $q$ receiving from peer $p$ \textsf{Proof($i$, nonce, K$^i_{pub}$, trees$^i$, S$^i_p$, S$^i_{pulse}$, S$_{proof}$)}}]
+\begin{lstlisting}[title={Peer $q$ receiving from peer $p$ \textsf{Proof($i$, seed$^i$, branch$^i$, S$^i_p$, S$^i_{pulse}$)}}]
+  let level = length(branch$^i$)-1;
   if
-     ($i$, nonce, $p$) $\in$ challenges and
-     verify_sig(S$^i_{pulse}$, <$i$,seed$^i$,$K^i_{pub}$,trees$^i$[0]>,KS$_{pub}$) and
-     verify_sig(S$^i_p$, <$i$, seed$^i$ >, K$^p_{pub}$) and
-     S$^i_p$ $\in$ trees$^i$ and
-     $\forall n>0$, H(trees$^i$[n]) $\in$ trees$^i$[n-1] and
-     verify_sig(S$_{proof}$, < nonce, H$^p$, H$^q$ >, K$^i_{pub}$)
+     $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
+     {$p\rightarrow$hash(S$^i_p$)} $\in$ branch$^i$[level] and
+     $\forall\; n\in$[1..level], hash(branch$^i$[n]) $\in$ branch$^i$[n-1]
   then
-     good_reply($p$)
+     challenge[$q$] = challenge[$q$]$\oplus${$i\rightarrow$ PROVEN};
   else
-     bad_reply($p$)
+     challenge[$q$] = challenge[$q$]$\oplus${$i\rightarrow$ WRONG};
   end if
 \end{lstlisting}
 
-- 
cgit v1.2.3-70-g09d2

