-\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 A transaction:\r
- \begin{itemize}\r
- \item Contains a sequence number, a set of key value pair updates and a guard condition that can be evaluated.\r
- \item Must have the same arbitrator for all its key value pair updates and reads within the guard condition\r
- \end{itemize}\r
- \r
- \item A Commit\r
- \newline{Commits a transaction into the block chain. Until a transaction is committed, no client can be sure if that transaction's key value updates will be used to update the state of the system. Once an arbitrator commits a transaction then that transaction becomes a permanent state change in the system. Transactions should be committed and aborted in order of their sequence numbers.}\r
- \r
- \item An Abort\r
- \newline{An abort is used to show that a transactions key value update should not be used in the state change of the system. This occurs when the guard of a transaction evaluates to false meaning that the conditions under-which this transaction should be committed no longer exists in the system (another transaction could have been committed first that would have changed the system in a way that makes the current transaction invalid).}\r
- \r
- \item New Key:\r
- \newline{This creates a new key and assignes an arbitrator to that key. Only the first new key message for a given key is valid. Once a new key message is inserted into the block chain it is never removed and no other new key entries for the same key name can be inserted into the block chain.}\r
- \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 from a certain client if a client's update has to expunge that other client's last entry from the queue. This is kept in the slot until the entry owner inserts a newer update into the queue.}\r
-\r
- \item Queue state entry: Includes queue size \r
- \newline {The purpose of this is for the client to tell if the server lies about the number of slots in the queue, e.g. if there are 2 queue state entry in the queue, e.g. 50 and 70, the client knows that when it sees 50, it should expect at most 50 slots in the queue and after it sees 70, it should expect 50 slots before that queue state entry slot 50 and at most 70 slots. The queue state entry slot 70 is counted as slot number 51 in the queue.}\r
-\r
- \item Collision resolution entry: message identifier + machine id of a collision winner\r
- \newline {The purpose of this is to keep keep track of the winner of all the collisions until all clients have seen the particular entry.}\r
-\end{enumerate}\r
-\r
-\subsection{Live status}\r
-\r
-Live status of entries:\r
-\begin{enumerate}\r
- \item Transaction is live if it has not been committed or aborted yet.\r
- \r
- \item Abort is live until the machine ID that created the transaction that is being aborted inserts into the block chain a message with a sequence number greater than the abort (that client sees the abort).\r
- \r
- \item Commit is dead if for all key value updates in the commit there is a commit with the same key value update that is newer (larger sequence number). The committing client (arbitrator) will see those newer commits since it is the one that generates them.\r
- \r
- \item New Key messages are always kept alive. Keys can not be deleted. Deleted keys will cause arbitration to fail if a key is deleted then reassigned to a new client device for arbitration.\r
- \r
- \item Slot sequence number (of either a message version data 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 entry 50 is dead and 70 is live. However, not until the number of slots reaches 70 that queue state entry 50 will be expunged from the queue. Further all entries before the 50 entry will also not be expunged until the queue size has reached 70}\r
-\r
- \item Collision resolution entry is dead if this entry has been seen by all clients after a collision happens.\r
-\end{enumerate}\r
-\r
-When data is at the end of the queue ready to expunge, if:\r
-\begin{enumerate}\r
- \item If any entry is not dead it must be reinserted into the queue.\r
-\r
- \item If the slot sequence number is not dead, then a message sequence entry must be inserted.\r
-\end{enumerate}\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 entry (in case of a gap do not check for slots on gap margins).\r
- \item That no slots are slots we have seen before (server trying to pass old slots). \r
- \r
- \item For all other machines, check that the latest sequence number is at least as large (never goes backwards).\r
- \r
- \item That the queue has a current queue state entry.\r
- \r
- \item That the number of entries received is consistent with the size specified in the queue state entry and/or the queue is growing in size.\r
-\end{enumerate}\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 (b) a request to the server. The queue can only be expanded, never contracted; attempting to decrease the size of the queue will cause future clients to throw an error.\r
-\r
-\r