diff options
Diffstat (limited to 'articles/pacemaker2/specification.tex')
| -rw-r--r-- | articles/pacemaker2/specification.tex | 202 |
1 files changed, 202 insertions, 0 deletions
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... ;-) + |