diff options
Diffstat (limited to 'stage/article.tex')
| -rw-r--r-- | stage/article.tex | 245 |
1 files changed, 132 insertions, 113 deletions
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} |