From decfef69b25175e672a3216d85b9b4c7e1165b98 Mon Sep 17 00:00:00 2001
From: lefessan <lefessan@30fcff6e-8de6-41c7-acce-77ff6d1dd07b>
Date: Fri, 1 Apr 2011 08:00:38 +0000
Subject: Added previous articles

git-svn-id: https://scm.gforge.inria.fr/svn/pacemaker@1 30fcff6e-8de6-41c7-acce-77ff6d1dd07b
---
 articles/pacemaker2/specification.tex | 202 ++++++++++++++++++++++++++++++++++
 1 file changed, 202 insertions(+)
 create mode 100644 articles/pacemaker2/specification.tex

(limited to 'articles/pacemaker2/specification.tex')

diff --git a/articles/pacemaker2/specification.tex b/articles/pacemaker2/specification.tex
new file mode 100644
index 0000000..101e3f4
--- /dev/null
+++ b/articles/pacemaker2/specification.tex
@@ -0,0 +1,202 @@
+
+% #1: fig:label
+% #2: Handler title
+% #3: caption
+\newenvironment{handler}[3]{%
+\def\handlerlabel{fig:#1}%
+\def\handlertitle{#2}%
+\def\handlercaption{#3}%
+\begin{figure}%
+\center\vspace{1em}%
+\noindent\begin{tabular}{|p{\myboxlen}|}%
+\hline%
+\footnotesize%
+{\tt\bf \handlertitle}%
+}
+{%
+\\ \hline%
+\end{tabular}%
+\caption{\handlercaption}%
+\label{\handlerlabel}%
+\end{figure}%
+}
+
+
+\begin{handler}{server-init}{Server at round $i$}{}
+\begin{lstlisting}{}
+  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$
+  $\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}
+\end{handler}
+
+\begin{handler}{xn}{Server or peer receiving SeedReply ($i$, X$_q$) from peer $q$:}{}
+\begin{lstlisting}{}
+  if phase$^i$ = Seeding then
+    map$^i$ = $\{ q \rightarrow $X$_q \} \oplus$ map$^i$;
+  end if
+\end{lstlisting}
+\end{handler}
+
+\begin{handler}{xn}{Every $\Delta << T$ seconds, on peer $p$:}{}
+\begin{lstlisting}{}
+  if phase$^i$ = Seeding then
+    let H$^i$ = H(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}
+\end{handler}
+
+\begin{handler}{x1}{Peer $p$ receiving M$^i_{seed}$ = Seed ($i$,seed$^i$,S$^i_{seed}$):}{}
+\begin{lstlisting}{}
+if verify_sig( S$^i_{seed}$,  <$i$,seed$^i$>, KS$_{priv}$) 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;
+end if
+\end{lstlisting}
+\end{handler}
+
+\begin{handler}{x3}{Peer $p$ receiving
+   Pulse($i$, seed$^i$, H$^i$, level, tree$^i$, S$^i_{pulse}$):}{}
+\begin{lstlisting}{}
+  if 
+     verify_sig(S$^i_{pulse}$, <$i$, seed$^i$, H$^i$ >, KS$_{pub}$ ) 
+  then
+     phase$^i$ = Idle;
+     included$^i$ = $\bot$;
+     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$)
+     then
+       let tree'$^i$ = tree$^i$ $\oplus$ $\{$ level+1 $\rightarrow$ oldmap$^i$ $\}$;
+       M$^i_{pulse}$ = ($i$, seed$^i$, H$^i$, level+1, tree'$^i$, S$^i_{pulse}$)
+       History[$i$] = M$^i_{pulse}$;
+       included$^i$ = $n$;
+       $\forall q \in$ children$^p$, send($q$, Pulse M$^i_{pulse}$);
+     end if
+  end if
+\end{lstlisting}
+\end{handler}
+
+\begin{handler}{x4}{Peer $p$ sending to $q$ its availability at round $i$:}{}
+\begin{lstlisting}{}
+  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
+    else
+      bits$^i$[$x$] := 1
+    end if
+  end for  
+  let S$^i_{avail}$ = sign( < $i$, bits$^i$ >, K$^p_{priv}$ )
+  let M$^i_{avail}$ = ($i$,bits,S$^i_{avail}$);
+  send( $q$, Availability M$^i_{avail}$ )
+\end{lstlisting}
+\end{handler}
+
+\begin{handler}{x5}{Peer $p$ receiving Challenge($i$, nonce) from peer $q$:}{}
+\begin{lstlisting}{}
+  let M$^i_{pulse}$ = History[$i$]
+  send( $q$, Proof M$^i_{pulse}$)
+\end{lstlisting}
+\end{handler}
+
+\begin{handler}{x6}{Peer $q$ receiving from peer $p$
+    Proof ($i$, nonce, K$^i_{pub}$, trees$^i$, S$^i_p$, S$^i_{pulse}$, S$_{proof}$):}{}
+\begin{lstlisting}{}
+Peer $q$ receiving from peer $p$
+    Proof ($i$, nonce, K$^i_{pub}$, trees$^i$, S$^i_p$, S$^i_{pulse}$, S$_{proof}$):
+  if
+     ($i$, nonce, $p$) $\in$ challenges $\land$
+     verify_sig(S$^i_{pulse}$,<$i$, seed$^i$,$K^i_{pub}$,trees$^i$[0]>,KS$_{pub}$) $\land$
+     verify_sig(S$^i_p$, <$i$, seed$^i$ >, K$^p_{pub}$) $\land$
+     S$^i_p$ $\in$ trees$^i$ $\land$
+     $\forall n>0$, H(trees$^i$[n]) $\in$ trees$^i$[n-1] $\land$
+     verify_sig(S$_{proof}$, < nonce, H$^p$, H$^q$ >, K$^i_{pub}$ )
+  then
+     good_reply($p$)
+  else
+     bad_reply($p$)
+  end if
+\end{lstlisting}
+\end{handler}
+
+\endinput
+
+ A major problem in peer-to-peer networks is that peers might work together
+({\em collude}) to break security properties of a protocol. In our case, some
+peers might work together to increase their measured availability. In this 
+section, we describe an extension of our protocol to fight against collusion.
+
+ The easiest way to collude to break our original protocol is for a peer  
+to give the pulse to another peer, that was not available when the pulse 
+was distributed. This can be done as part of an exchange (for other 
+pulses) so that both peers will increase their measured availability, or 
+as part of an attack, if the peer wants to increase measured availability 
+of all peers to break the system.
+
+
+ Our solution is a three phases protocol:
+\begin{itemize}
+\item {\bf Phase 1} The server diffuses a {\em seed} for the round on the 
+network using a {\tt Seed} message. 
+
+\item {\bf Phase 2} Every client generates a signature of the 
+seed with its private key. It then computes a short hash of the 
+signature. It then joins its hash to the hashes received from its children
+and computes a new hash, that it sends to its parents, using a {\tt Tree} message.
+The server itself computes a hash from the hashes received from its children.
+
+\item {\bf Phase 3} The server computes the new pulse for the round, and
+diffuses it in a {\tt Pulse} message, together with the seed for the round and
+the hash computed in phase 2, both signed by its private key. Every parent propagates the 
+pulse to its children, adding also the list of hashes it used to compute 
+the hash sent to its parents.
+
+\end{itemize}
+
+ The goal of this extension of the original protocol is that the pulse now
+contains a piece of information recording the presence of all the peers in
+the network through a merkle-tree\cite{1979-merkle}. Colluding peers will
+only be able to use the pulse if they can provide the signature of the hash
+and the merkle tree showing it has been taken into account in the computation
+of the pulse. 
+
+ Now, let's assume peers $p$ and $q$ are colluding: peer $p$ is online
+during the diffusion of the pulse, while $q$ is offline. To be able to
+give a useful pulse to $q$, $p$ must have included $q$ into the
+merkle-tree. To do that, it must have issued a signature of the seed using
+$q$ private key, and then put the hash of the signature in its own tree. This
+means that peer $p$ must know the private key of peer $q$ to collude.
+
+ It is thus an important requirement on applications using our system that 
+they discourage peers from sharing their private keys. This can easily 
+been done by giving extra-power to key owners, i.e. for instance the owner 
+of a private key should be allowed to delete data associated with the
+key, or to book storage using the key. As a consequence, colluding peers 
+would have to trust each other, to such a high degree that collusion would 
+only be possible among a very small part of the network.
+
+We assume to know the depth of the network. Is it bad ? Probably... ;-)
+
-- 
cgit v1.2.3-70-g09d2

