+++ /dev/null
-\documentclass[11pt]{article}\r
-\newcommand{\tuple}[1]{\ensuremath \langle #1 \rangle}\r
-\usepackage{color}\r
-\usepackage{amsthm}\r
-\usepackage{amsmath}\r
-\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx\r
-\newtheorem{theorem}{Theorem}\r
-\newtheorem{defn}{Definition}\r
-\newcommand{\note}[1]{{\color{red} \bf [[#1]]}}\r
-\newcommand{\push}[1][1]{\hskip\dimexpr #1\algorithmicindent\relax}\r
-\begin{document}\r
-\section{Approach}\r
-\r
-\subsection{Keys}\r
-\r
-Each device has: user id + password\r
-\r
-Server login is:\r
-hash1(user id), hash1(password)\r
-\r
-Symmetric Crypto keys is:\r
-hash2(user id | password)\r
-\r
-Server has finite length queue of entries + max\_entry\_identifier +\r
-server login key\r
-\r
-\subsection{Entry layout}\r
-Each entry has:\r
-\begin{enumerate}\r
-\item Sequence identifier\r
-\item Random IV (if needed by crypto algorithm)\r
-\item Encrypted payload\r
-\end{enumerate}\r
-\r
-Payload has:\r
-\begin{enumerate}\r
-\item Sequence identifier\r
-\item Machine id (most probably something like a 64-bit random number \r
-that is self-generated by client)\r
-\item HMAC of previous slot\r
-\item Data entries\r
-\item HMAC of current slot\r
-\end{enumerate}\r
-\r
-A data entry can be one of these:\r
-\begin{enumerate}\r
-\item All or part of a Key-value entry\r
-\item Slot sequence entry: Machine id + last message identifier \r
-\newline {The purpose of this is to keep the record of the last slot \r
-from a certain client if a client's update has to expunge that other \r
-client's last entry from the queue. This is kept in the slot until \r
-the entry owner inserts a newer update into the queue.}\r
-\item Queue state entry: Includes queue size \newline {The purpose \r
-of this is for the client to tell if the server lies about the number \r
-of slots in the queue, e.g. if there are 2 queue state entry in the queue, \r
-e.g. 50 and 70, the client knows that when it sees 50, it should expect \r
-at most 50 slots in the queue and after it sees 70, it should expect \r
-50 slots before that queue state entry slot 50 and at most 70 slots. \r
-The queue state entry slot 70 is counted as slot number 51 in the queue.}\r
-\end{enumerate}\r
-\r
-\subsection{Live status}\r
-\r
-Live status of entries:\r
-\begin{enumerate}\r
-\item Key-Value Entry is dead if either (a) there is a newer key-value pair or (b) it is incomplete.\r
- \r
-\item Slot sequence number (of either a message version data\r
-or user-level data) is dead if there is a newer slot from the same machine.\r
-\r
-\item Queue state entry is dead if there is a newer queue state entry.\r
-{In the case of queue state entries 50 and 70, this means that queue state \r
-entry 50 is dead and 70 is live. However, not until the number of slots reaches \r
-70 that queue state entry 50 will be expunged from the queue.}\r
-\end{enumerate}\r
-\r
-When data is at the end of the queue ready to expunge, if:\r
-\begin{enumerate}\r
-\item The key-value entry is not dead, it must be reinserted at the\r
-beginning of the queue.\r
-\r
-\item If the slot sequence number is not dead, then a message sequence\r
-entry must be inserted.\r
-\r
-\item If the queue state entry is not dead, it must be reinserted at the\r
-beginning of the queue.\r
-\end{enumerate}\r
-\r
-\r
-\paragraph{Reads:}\r
-Client sends a sequence number. Server replies with either: all data\r
-entries or all newer data entries.\r
-\r
-\paragraph{Writes:}\r
-Client sends slot, server verifies that sequence number is valid,\r
-checks entry hash, and replies with an accept message if all checks\r
-pass. On success, client updates its sequence number. On failure,\r
-server sends updates slots to client and client validates those slots.\r
-\r
-\paragraph{Local state on each client:}\r
-A list of machines and the corresponding latest sequence numbers.\r
-\r
-\paragraph{Validation procedure on client:}\r
-\begin{enumerate}\r
-\item Decrypt each new slot in order.\r
-\item For each slot:\r
- (a) check its HMAC, and\r
- (b) check that the previous entry HMAC field matches the previous\r
- entry.\r
-\item Check that the last message version for our machine matches our\r
-last message sent.\r
-\item For all other machines, check that the latest sequence number is\r
-at least as large (never goes backwards).\r
-\item That the queue has a current queue state entry.\r
-\item That the number of entries received is consistent with the size\r
-specified in the queue state entry.\r
-\end{enumerate}\r
-\r
-Key-value entries can span multiple slots. They aren't valid until\r
-they are complete.\r
-\r
-\subsection{Resizing Queue}\r
-Client can make a request to resize the queue. This is done as a write that combines:\r
- (a) a slot with the message, and\r
- (b) a request to the server\r
-\r
-\subsection{Server Algorithm}\r
-$s \in SN$ is a sequence number\\\r
-$sv \in SV$ is a slot's value\\\r
-$slot_s = \tuple{s, sv} \in Q \subseteq SN \times SV$ \\\r
-\r
-\textbf{State} \\\r
-\textit{Q = set of live slots on server} \\\r
-\textit{max = maximum number of slots (input only for resize message)} \\\r
-\textit{n = number of slots} \\\r
-\r
-\begin{algorithmic}[1]\r
-\Function{GetSlot}{$s'$}\r
-\State \Return{$\{\tuple{s, sv} \in Q \mid s \geq s'\}$}\r
-\EndFunction\r
-\end{algorithmic}\r
-\r
-\begin{algorithmic}[1]\r
-\Function{PutSlot}{$s',sv',max'$}\r
-\If{$(max' \neq \emptyset) \land (max' > max)$}\Comment{Resize}\r
- \State $Q' \gets new\:queue\:of\:\langle s,sv \rangle\:with\r
- \:size\:max'$\r
- \State $Q \gets Q' \cup Q$\r
- \State $max \gets max'$\r
-\EndIf\r
-\If{$(s' = s_n + d)$}\r
- \If{$n = max$}\r
- \State $Q \gets Q - \{\langle s_n,sv_n \rangle\}$\r
- \Else \Comment{$n < max$}\r
- \State $n \gets n + 1$\r
- \EndIf\r
- \State $Q \gets Q \cup \{\langle s',sv' \rangle\}$\r
- \State \Return{$true$}\r
-\Else\r
- \State \Return{$(false,\{\langle i,sv_i \rangle \in Q \mid \r
- s' \leq i \leq s_n\})$}\r
-\EndIf\r
-\EndFunction\r
-\end{algorithmic}\r
-\r
-\subsection{Client Algorithm}\r
-\begin{algorithmic}[1]\r
-\Function{CallClient}{$uid,pw,d,m,max,s,Data*,Result*$}\r
-\textit{\r
-\newline{// uid = user identification}\r
-\newline{// pw = password}\r
-\newline{// d = new data for write}\r
-\newline{// m = client message (read/write/resize)}\r
-\newline{// max = maximum number of slots (input only for resize message)}\r
-\newline{// n = number of slots}\r
-\newline{// s = sequence number for server request}\r
-\newline{// t = sequence numbers of slots on server}\r
-\newline{// mid = machine identification}\r
-\newline{// seq = sequence number inside slot}\r
-\newline{// newSlot = new slot}\r
-\newline{// expSlot = expunged/expired slot}\r
-\newline{// slotSeqE = slot sequence entry}\r
-\newline{// M = list of all machines/devices with their respective latest s on client}\r
-\newline{// Data = array of slots written/read (input only for write)}\r
-\newline{// Result = array of decrypted and valid slots after a read}\r
-\newline{// Slot = one data slot)}\r
-\newline{// DSlot = one decrypted data slot)}\r
-}\r
-\State $SK = Hash(uid + pw)$\r
-\If{$m = read$}\r
- \State $Data \gets CallServer(m,max,s,Data)$\r
- \If{$Data = \emptyset$}\r
- \State $ReportError(\emptyset,read)$\r
- \Else\r
- \If{$\neg HasCurrentQueueStateEntry(Data)$}\r
- \State $ReportError(DSlot_i,read)$\r
- \EndIf\r
- \ForAll{$Slot_i \in Data$}\r
- \State $DSlot_i \gets Decrypt(SK,Slot_i)$\Comment{Check s and HMAC}\r
- \If{$\neg (ValidSeqN(DSlot_i) \land ValidHmac(DSlot_i) \land $\\\r
- \push[1] $ValidPrevHmac(DSlot_i))$}\r
- \State $ReportError(DSlot_i,read)$\r
- \Else\Comment{Check only live entries}\r
- \If{$IsLiveSlotSequenceEntry(DSlot_i)$}\r
- \State $lastS \gets LastSeqN(DSlot_i)$\r
- \State $lastMid \gets LastMachineId(DSlot_i)$\r
- \If{$lastS \neq LastSeqN(lastMid,M)$}\r
- \State $ReportError(DSlot_i,read)$\r
- \EndIf\r
- \ElsIf{$IsLiveKeyValueEntry(DSlot_i)$}\r
- \State $mid \gets MachineId(DSlot_i)$\r
- \State $seq \gets SeqN(DSlot_i)$\r
- \If{$IsOwnMid(mid)$}\r
- \If{$IsLastS(mid,seq,Data) \land $\\\r
- \push[1] $(seq \neq LastSeqN(mid,M))$}\r
- \State $ReportError(DSlot_i,read)$\r
- \EndIf\r
- \Else\Comment{Check s for other machines}\r
- \If{$IsLastS(mid,seq,Data) \land $\\\r
- \push[1] $(seq < LastSeqN(mid,M))$}\r
- \State $ReportError(DSlot_i,read)$\r
- \EndIf\r
- \EndIf\Comment{Check queue state entry}\r
- \ElsIf{$IsLiveQueueStateEntry(DSlot_i)$}\r
- \If{$IsCurrentQueueState(DSlot_i)$}\r
- \If{$Length(Data) > QueueLength(DSlot_i)$}\r
- \State $ReportError(DSlot_i,read)$\r
- \EndIf\r
- \EndIf\r
- \Else\r
- \State $ReportError(DSlot_i,read)$\r
- \EndIf\r
- \EndIf\r
- \State $Result \gets Concat(Result, DSlot_i)$\r
- \EndFor\r
- \EndIf\r
-\r
-\ElsIf{$m = write$}\r
- \State $newSlot \gets CreateSlot(d)$\r
- \State $Data[1] \gets Encrypt(SK,newSlot)$\r
- \State $Data \gets CallServer(m,max,s,Data)$\r
- \If{$Data = \emptyset$}\r
- \State $ReportError(\emptyset,write)$\r
- \Else\Comment Check for valid return value from server\r
- \If{$\neg ValidOldLastEntry(Data[1])$}\r
- \State $ReportError(Data[1],write)$\r
- \Else\Comment{Check if we need slot sequence entry}\r
- \If{$Length(Data) = 2$}\r
- \State $expSlot \gets Decrypt(SK,Data[2])$\r
- \State $mid \gets MachineId(expSlot)$\r
- \State $seq \gets SeqN(expSlot)$\r
- \If{$seq = LastSeqN(mid,M)$}\Comment{Liveness check}\r
- \State $slotSeqE \gets CreateSlotSeqE(mid,seq)$\r
- \State $Data[1] \gets Encrypt(SK,slotSeqE)$\r
- \State $Data \gets CallServer(m,max,s,Data)$\r
- \EndIf\r
- \Else\r
- \State $ReportError(Data,write)$\r
- \EndIf\r
- \EndIf\r
- \EndIf\r
-\r
-\ElsIf{$m = resize$}\r
- \State $Data \gets CallServer(m,max,s,Data)$\r
- \If{$Data = \emptyset$}\r
- \State $ReportError(\emptyset,resize)$\r
- \EndIf\r
-\EndIf\r
-\State \Return{$Result$}\r
-\EndFunction\r
-\end{algorithmic}\r
-\r
-\subsection{Formal Guarantees}\r
-\r
-\textit{To be completed ...}\r
-\r
-\begin{defn}[System Execution]\r
-Let \\\r
-\begin{center}\r
-$Q = \{slot_{sn_1}, slot_{sn_2}, \dots, Slot_{sn_n}\}$, \\\r
-$SN = \{sn_1, sn_2, \dots, sn_n\}$ \\\r
-\end{center}\r
-denote a queue $Q$ of $n$ slots, with each slot entry being denoted by a\r
-valid sequence number $sn_i \in SN$. $Q$ represents a total order of all \r
-slot updates from all corresponding machines.\r
-%\textit{Formalize a system execution as a sequence of slot updates...\r
-%There is a total order of all slot updates.}\r
-\end{defn}\r
-\r
-\begin{defn}[Transitive Closure]\r
-A transitive closure $\tau : \tau = \epsilon_{update(slot_i)} R $\r
-$\epsilon_{receive(slot_i)}$ is a relation from slot update event\r
-$\epsilon$ to a slot receive event $\epsilon$ for $slot_i$.\r
-%Define transitive closure relation for slot updates... There is an\r
-%edge from a slot update to a slot receive event if the receive event\r
-%reads from the update event.\r
-\end{defn}\r
-\r
-\begin{defn}[Suborder]\r
-Let \\\r
-\begin{center}\r
-$q = \{slot_{i}, slot_{i+1}, \dots, slot_{j}\}, \r
-sn_1 \leq i \leq j \leq sn_n \Longrightarrow q \subseteq Q$\r
-\end{center}\r
-denote a suborder of the total order. Set q is a sequence of contiguous\r
-slot updates that is a subset of a total order of all slot updates in Q.\r
-%Define suborder of total order. It is a sequence of contiguous slots\r
-%updates (as observed by a given device).\r
-\end{defn}\r
-\r
-\begin{defn}[Prefix of a suborder]\r
-Given a suborder \\ \r
-\begin{center}\r
-$q' = \{slot_{i}, slot_{i+1}, \dots, slot_{j}, \dots\}, \r
-sn_1 \leq i \leq j \leq sn_n \Longrightarrow \r
-q' \subseteq Q$\r
-\end{center}\r
-with $slot_{j}$ as a slot update in $q'$, the prefix of $q'$ is a sequence \r
-of all slot updates $\{slot_{i}, slot_{i+1}, \dots, slot_{j-1}\} \cup\r
-slot_{j}$.\r
-%Given a sub order $o=u_{i},u_{i+1},...,u_j, u_{j+i},..., u', ...$ and\r
-%a slot update $u'$ in $o$, the prefix of $o$ is a sequence of all\r
-%updates that occur before $u'$ and $u'$.\r
-\end{defn}\r
-\r
-\begin{defn}[Consistency between a suborder and a total order]\r
-A suborder $q'$ is consistent with a total order $T$ of $Q$, if all\r
-updates in $q'$ appear in $T$ and they appear in the same order, as \r
-the following:\r
-\begin{center}\r
-$q' = \{slot_{i}, slot_{i+1}, \dots, slot_{j}\},$\r
-$T = \{slot_{sn_1}, \dots, slot_{i}, slot_{i+1}, \dots, slot_{j}, \dots,\r
-slot_{sn_n}\},$ \\ $sn_1 \leq i \leq j \leq sn_n \Longrightarrow\r
-q' \subseteq T$\r
-\end{center}\r
-%A suborder $o$ is consistent with a total order $t$, if all updates in $o$ %appear in $t$ and they appear in the same order.\r
-\end{defn}\r
-\r
-\begin{defn}[Consistency between suborders]\r
-Two suborders U and V are consistent if there exist a total order T \r
-such that both U and V are suborders of T.\r
-\begin{center}\r
-$U = \{slot_{i}, slot_{i+1}, \dots, slot_{j}\},$ \\\r
-$V = \{slot_{k}, slot_{k+1}, \dots, slot_{l}\},$ \\\r
-$sn_1 \leq i \leq j \leq k \leq l \leq sn_n,$ \\\r
-$U \subset T \land V \subset T$ \\\r
-$T = \{slot_{sn_1}, \dots, slot_{i}, slot_{i+1}, \dots, slot_{j}, $\\\r
-$\dots, slot_{k}, slot_{k+1}, \dots, slot_{l}, \dots, slot_{sn_n}\}$\r
-\end{center}\r
-%Define notion of consistency between suborders... Two suborders U,V\r
-%are consistent if there exist a total order T such that both U and V\r
-%are suborders of T.\r
-\end{defn}\r
-\r
-\begin{defn}[Error-free execution]\r
-An error-free execution, for which the client does not flag any errors\r
-is defined by the following criteria:\r
-\begin{enumerate}\r
-\item Item 1\r
-\item Item 2\r
-\end{enumerate}\r
-%not flag any errors...\r
-%Define error-free execution --- execution for which the client does\r
-%not flag any errors...\r
-\end{defn}\r
-\r
-\begin{theorem} Error-free execution of algorithm ensures that the suborder\r
-for node n is consistent with the prefix suborder for all other nodes\r
-that are in the transitive closure.\r
-\end{theorem}\r
-\begin{proof}\r
-\textit{TODO}\r
-\end{proof}\r
-\r
-\begin{defn}[State of Data Structure]\r
-Define in terms of playing all updates sequentially onto local data\r
-structure.\r
-\end{defn}\r
-\r
-\begin{theorem}\r
-Algorithm gives consistent view of data structure.\r
-\end{theorem}\r
-\begin{proof}\r
-\textit{TODO}\r
-\end{proof}\r
-\r
-\subsection{Future Work}\r
-\paragraph{Support Messages}\r
- A message is dead once receiving machine sends an entry with a newer\r
- sequence identifier\r
-\r
-\paragraph{Persistent data structures}\r
- Root object w/ fields\r
- Other objects can be reachable from root\r
- Each object has its own entries\r
- Dead objects correspond to dead \r
-\r
-\paragraph{Multiple App Sharing}\r
-\r
-Idea is to separate subspace of entries... Shared with other cloud...\r
-\end{document}\r
-\r
projects / iotcloud.git / blobdiff