\EndProcedure\r
\end{algorithmic}\r
\r
- \begin{algorithmic}[1]\r
- \Function{ValidHmac}{$DE_s,SK_s,hmac_{stored}$}\r
- \State $hmac_{computed} \gets Hmac(DE_s,SK_s)$\r
- \State \Return {$hmac_{stored} = hmac_{computed}$}\r
- \EndFunction\r
- \end{algorithmic}\r
- \r
- \begin{algorithmic}[1]\r
- \Function{ValidPrevHmac}{$s_s,DE_s,hmac_{p_s},hmac_{p_{sto}}$}\r
- \If{$s_s = 0 \land hmac_{p_s} = \emptyset$}\Comment{First slot - no previous HMAC}\r
- \State \Return $true$\r
- \Else\r
- \State \Return {$hmac_{p_{sto}} = hmac_{p_s}$}\r
- \EndIf\r
- \EndFunction\r
- \end{algorithmic}\r
- \r
\begin{algorithmic}[1]\r
\Function{GetQueSta}{$DE_s$}\r
- \State $de_{qs} \gets de_s$ \textit{such that} $de_s \in DE_s, \r
- de_s \in D \land de_s = qs$\r
+ \State $de_{qs} \gets ss$ \textit{such that} $ss \in DE_s, \r
+ de_s \in D \land type(de_s) = "qs"$\r
\If{$de_{qs} \neq \emptyset$}\r
\State $qs_{ret} \gets GetQS(de_{qs})$\r
\Else\r
\r
\begin{algorithmic}[1]\r
\Function{GetSlotSeq}{$DE_s$}\r
- \State $DE_{ss} \gets \{de_s | de_s \in DE_s, de_s = ss\}$\r
+ \State $DE_{ss} \gets \{de | de \in DE_s \land type(de) = "ss"\}$\r
\State \Return{$DE_{ss}$}\r
\EndFunction\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
\Function{GetColRes}{$DE_s$}\r
- \State $DE_{cr} \gets \{de_s | de_s \in DE_s, de_s = cr\}$\r
+ \State $DE_{cr} \gets \{de | de \in DE_s \land type(de) = "cr"\}$\r
\State \Return{$DE_{cr}$}\r
\EndFunction\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
\Function{UpdateDT}{$DT_s,DE_s,LV_s,s_s$}\r
- \State $DE_{s_{kv}} \gets \{de_s | de_s \in DE_s, de_s = kv\}$\r
+ \State $DE_{s_{kv}} \gets \{de_s | de_s \in DE_s, type(de_s) = "kv"\}$\r
\ForAll{$de_s \in DE_s$}\r
\State $kv_s \gets GetKV(de_s)$\r
\State $LV_s \gets \Call{UpdateKVLivEnt}{LV_s,kv_s,s_s}$\r
\EndIf\r
\State $DE_g \gets GetDatEnt(Dat_g)$\r
\State $hmac_{p_{stored}} \gets GetPrevHmac(Dat_g)$\r
- \If{$\neg \Call{ValidPrevHmac}{s_g,DE_g,hmac_{p_g},hmac_{p_{stored}}}$}\r
+ \If {$ \neg(s_g = 0 \land hmac_{p_g} = 0) \land hmac_{p_{stored}} \neq hmac_{p_g}$}\r
\State \Call{Error}{'Invalid previous HMAC value'}\r
\EndIf\r
- \State $hmac_{c_g} \gets GetCurrHmac(Dat_g)$\r
- \If{$\neg \Call{ValidHmac}{DE_g,SK,hmac_{c_g}}$}\r
+ \If{$\Call{Hmac}{DE_g,SK} \neq GetCurrHmac(Dat_g)$ }\r
\State \Call{Error}{'Invalid current HMAC value'}\r
\EndIf\r
\State $hmac_{p_g} \gets Hmac(DE_g,SK)$\Comment{Update $hmac_{p_g}$ for next check}\r
\end{algorithmic}\r
\r
\begin{algorithmic}[1]\r
- \Function{GetValFromKey}{$k_g$}\r
+ \Function{Get}{$k_g$} \Comment{Interface function to get a value}\r
\State $\tuple{k_s,v_s} \gets \tuple{k,v}$ \textit{such that} $\tuple{k,v} \r
\in DT \land k = k_g$\r
\State \Return{$v_s$}\r
\forall \tuple{ck_s,\tuple{k_s, v_s}} \in KV_s, k = k_s$ \\\r
\r
\begin{algorithmic}[1]\r
- \Function{PutKVPair}{$KV_s,\tuple{k_s,v_s}$}\r
+ \Function{Put}{$KV_s,\tuple{k_s,v_s}$} \Comment{Interface function to update a key-value pair}\r
\State $\tuple{ck_s,\tuple{k_s,v_t}} \gets GetKVPair(KV,k_s)$\r
\If{$\tuple{ck_s,\tuple{k_s,v_t}} = \emptyset$}\r
\State $KV_s \gets KV_s \cup \{\tuple{ck_p, \tuple{k_s,v_s}}\}$\r
\r
\begin{prop} \r
Every client $\mathsf{J}$ who sends a message $\mathsf{t}$ \r
-has $\mathsf{\mathscr{P}_t}$ as its latest stored message, and \r
-$\mathsf{s_t = s_{\mathscr{P}_t} + 1}$. \r
+has parent $\mathsf{p_t}$ as its latest stored message, and \r
+$\mathsf{s_t = s_{p_t} + 1}$. \r
\end{prop}\r
\begin{proof} True by definition, because $J$ sets \r
-$\mathsf{hmac_p(t) = hmac_c(\mathscr{P}_t)}$ and \r
-$\mathsf{s_t = }$ $\mathsf{s_{\mathscr{P}_t + 1}}$ when a message \r
+$\mathsf{hmac_p(t) = hmac_c(p_t)}$ and \r
+$\mathsf{s_t = }$ $\mathsf{s_{p_t + 1}}$ when a message \r
is sent. \r
\end{proof}\r
\r
Then $\mathsf{t}$ is in the path of $\mathsf{u}$. \r
\end{lem}\r
\begin{proof}\r
- By contradiction, we will prove that if $\mathsf{t}$ is not in the path of \r
- $\mathsf{u}$, then it is impossible for client $\mathsf{C}$ to receive both\r
- messages without throwing any errors. Clearly $\mathsf{C}$ will throw an error \r
- if $\mathsf{s_t = s_u}$. So $\mathsf{s_t < s_u}$. Additionally, if $\mathsf{C}$ \r
- receives $\mathsf{u}$ before $\mathsf{t}$, this will cause it to throw an \r
- error, so $\mathsf{t}$ is received before $\mathsf{u}$.\r
- \r
- Assume that $\mathsf{t}$ is not in the path of $\mathsf{u}$. Take $\mathsf{u}$ \r
- to be the packet of smallest sequence number for which this occurs, and \r
- $\mathsf{t}$ be the packet with greatest sequence number for this $\mathsf{u}$. \r
- We will prove that an error occurs upon receipt of $\mathsf{u}$.\r
-Assume otherwise. Then there are some pairs $\mathsf{(t,u)}$ that violate this lemma. Take a specific $\mathsf{(t,u)}$ such that $\mathsf{s_u}$ is minimized and $\mathsf{s_t}$ is maximized for this choice of $\mathsf{s_u}$.\r
++Assume otherwise. Then there are some pairs $\mathsf{(t,u)}$ that violate this lemma. \r
++Take a specific $\mathsf{(t,u)}$ such that $\mathsf{s_u}$ is minimized and \r
++$\mathsf{s_t}$ is maximized for this choice of $\mathsf{s_u}$.\r
+ \r
+ Clearly $\mathsf{C}$ will throw an error if $\mathsf{s_t = s_u}$. So \r
+ $\mathsf{s_t < s_u}$. Additionally, if $\mathsf{C}$ receives $\mathsf{u}$ before \r
+ $\mathsf{t}$, this will cause it to throw an error, so $\mathsf{t}$ is received \r
+ before $\mathsf{u}$. We will prove that an error occurs upon receipt of $\mathsf{u}$.\r
\r
Let $\mathsf{r_1}$ be the earliest member of the path of $\mathsf{t}$ that is \r
not in the path of $\mathsf{u}$, and $\mathsf{q}$ be its parent. Message \r
sent $\mathsf{l_1}$. Because no client can send two messages with the same sequence number, and \r
$\mathsf{s_{r_1} = s_{l_1} = s_q + 1}$, $\mathsf{J \neq K}$.\r
\r
-We also know the following three facts: \r
+We also know the following facts: \r
\r
\begin{prop} No client sends both a message in \r
-$\mathsf{(r_2,...,t)}$ and a message in $\mathsf{(l_2,...,u)}$. \end{prop}\r
+$\mathsf{(r_2,...,t)}$ and a message in $\mathsf{(l_2,...,u)}$. \r
+\end{prop}\r
\r
\begin{proof}\r
To send a message $\mathsf{p}$ that is the parent of some other \r
message, one must have received the parent of $\mathsf{p}$. Since \r
$\mathsf{u}$ is the message with smallest sequence number received by any \r
client that violates Lemma 1, no client receives both a message in $\mathsf{r}$ \r
-and a message in $\mathsf{l}$. \end{proof}\r
+and a message in $\mathsf{l}$. \r
+\end{proof}\r
\r
-\begin{prop} $\mathsf{C}$ does not receive any message with \r
-sequence number strictly between $\mathsf{s_t}$ and $\mathsf{s_u}$. \end{prop}\r
+\begin{prop} $\mathsf{C}$ does not receive any message with a\r
+sequence number strictly between $\mathsf{s_t}$ and $\mathsf{s_u}$. \r
+\end{prop}\r
\r
-\begin{proof} If there were such a message with sequence number smaller than $\mathsf{s_u}$, it would contradict the assumption that $\mathsf{u}$ is the message with least sequence number that violates Lemma 1. \end{proof}\r
+\begin{proof} If there were such a message with sequence number smaller than \r
+$\mathsf{s_u}$, it would contradict the assumption that $\mathsf{u}$ is the \r
+message with the least sequence number that violates Lemma 1. \r
+\end{proof}\r
\r
There are two cases:\r
\begin{itemize}\r
projects / iotcloud.git / commitdiff