% #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... ;-)