text:
\section{Acknowledgement}
This work was partially financed by the SCALE-IoT project (Grant No. DFF - 7026-00042B) granted by the Danish Council for Independent Research, the Aarhus Universitets Forskningsfond Starting Grant Project AUFF-2017-FLS-7-1, Aarhus University's DIGIT Centre, the ERC Horizon 2020 Grant No 669255 (MPCPRO), the ELLIIT grant and the Swedish Foundation for Strategic Research, grant RIT17-00.
}
Finally, the authors would like to kindly thank Prof. Claudio Orlandi for useful discussions and insights on our work.

 \fi
\bibliographystyle{IEEEtran}

\section{Analysis of Yggdrasil}\label{sec:analysis}

In the following, we analyze the compression rate and the privacy (uncertainty measure) achieved by \name. In this section, unless stated otherwise, we use $\log(x)$ as the logarithm in base $2$ of $x$.

\vspace{-5pt}
\subsection{Client Compression Ratio}
We begin our analysis with studying the compression ratio on the client side, i.e., \ucr.
To compute  \ucr for one string \file,
we need to accurately measure the size of \local.
Assuming \user performed $\nodel=n_o-n_b$ subsequent \deletions on \file,
then \local contains the \nodel deleted values (each value has $k$ bits)
and a pointer to their original locations in \file (each pointer has $\lceil\log(n_{o})\rceil$).
Therefore, the required storage needed in \user is equal to:
\begin{equation*}
\size(\system, \user, \file) = \nodel(\lceil \log(n_{o})\rceil + k) + \sizefid,
\end{equation*}
where $\sizefid$ is the size in bits of a file identifier ($\sizefid=\size(\id)$).
If our \database has $f$ files, the required storage on the \user side for the whole \database is
\begin{equation*}
\size(\system, \user, \database) = f(\nodel(\lceil \log(n_{o})\rceil + k) + \sizefid).
\end{equation*}

If \database contains \nof strings, the total storage size required for \database prior to the transformations of \name is
\begin{equation*}
|\database| = \nof\cdot k\cdot n_{o}.
\end{equation*}

Thus,
\begin{equation}
\ucr = \frac{\nodel(\lceil \log(n_{o})\rceil + k) + \sizefid}{k\cdot n_o}.
\label{eq:ygg_ucr}
\end{equation}

Clearly $\ucr<1$ if and only if
$$\sizefid + x\cdot(\lceil\log(n_{o})\rceil + k) < k\cdot n_{o}.$$

\subsection{Cloud Compression Ratio}
The data stored in \cloud The size of data stored in the \cloud consists of $b$ basis, where each basis has $n_{b}$ symbols of size $k$; one file identifier \id per string $\file$ and the \deviation generated in \compress procedure for deduplicated strings. Each \swap in \cloud adds $2\lceil\log(n_{o})\rceil$ and each \changev adds $k + \lceil\log(n_{o})\rceil$ to \deviation. As there are $\nof - \nob$ deduplicated strings and the number of operations in \cloud for each \file is bounded by \threshold, we have
\begin{equation*}
\size(\system, \cloud, \database) \leq \nob \cdot k\cdot n_{b} + \nof\cdot \sizefid + (\nof - \nob)\cdot \threshold(2\lceil\log(n_{o})\rceil).
\end{equation*}
 Therefore, for the compression ratio in \cloud, we have:
\begin{equation*}
\ccr = \frac{\sizefid + 2\threshold\lceil\log(n_{o})\rceil + \baseF( k\cdot n_{b} - 2\threshold\lceil\log(n_{o})\rceil)}{k\cdot n_{o}}.
\end{equation*}
where $\baseF$ is the fraction of number of bases to the number of original strings, i.e., $r=\frac{\nob}{\nof}$
The condition for achieving a compression ratio of less than one is:
$$r \leq 1 - \frac{\sizefid - k\cdot \nodel}{k\cdot (n_{o}-\nodel)- 2\threshold\lceil\log(n_{o})\rceil}\Leftrightarrow \ccr \leq 1.$$

\subsection{Global Compression Ratio}
The global compression ratio of the system is given by the sum of the \user compression ratio and the \cloud one. Thus,
\begin{equation}
\footnotesize
\compratio = \frac{2\sizefid + k\cdot x + (2\threshold + \nodel)\lceil\log(n_{o})\rceil + \baseF( k\cdot n_{b} - 2\threshold\lceil\log(n_{o})\rceil)}{k\cdot n_{o}}.
\label{eq:C1}
\end{equation}

\subsection{Uncertainty of Multiple $1$-Deletions}

We now calculate the uncertainty of a data item after \user performs $\nodel$ 1-deletions.
We consider the probability distribution \distribution over the set of $k$-bit symbols to be uniformly random, i.e., every symbol
has the same probability $1/2^k$ to be selected.
In this setting, our definition of uncertainty (Eq.~\eqref{eq:uncertainty}) states that the uncertainty of a string $\unmetric(\outsource)$ is equal to $1$ over the number of original strings $\tilde{\file}$ that can be generated by the base $\outsource$ output to the \cloud.
Let \nopreim denote this value, then~\cite{bartle2000introduction}

\begin{equation}
\nopreim = \sum_{j=0}^{n_{o}-n_{b}} {n_{o} \choose j+n_{b}} (2^{k}-1)^{n_{o}-n_{b}-j}.
\label{eq:nopreim}
\end{equation}
Intuitively, \nopreim counts the number of `preimagines of \upload', i.e., how many $n_o$-element strings \file  can generate the same base \outsource for a combination of $\nodel$ \deletions.
For large enough $n_o$ and $n_b \geq n_b$, a good lower bound is to consider the first term in the summation, i.e.,  $\nopreim \geq {n_{o} \choose n_{b}} (2^{k}-1)^{n_{o}-n_{b}}.$
Using Eq.~\ref{eq:nopreim}, the uncertainty metric for a record $\file\gets\distribution$ is
\begin{equation*}
\unmetric(\file) = \frac{1}{\nopreim} =  \frac{(2^{k}-1)^{n_{b}-n_{o}}}{\sum_{j=0}^{n_{o}-n_{b}} {n_{o} \choose j+n_{b}} (2^{k}-1)^{-j}.}.
\end{equation*}
Table~\ref{tab:M1} shows this number for various symbol sizes $k$, original string sizes $n_{o}$, and basis size $n_{b}$.
Even for small sequences of $n_o = 15$ with $k = 2$, the uncertainty is in the order of $10^{-7}$.
For more realistic cases, e.g., $n_o = 1000$, $n_b = 500$ and $k = 8$, the uncertainty metric is $10^{-1503}$, creating a high degree of potential uncertainty on \cloud.

\begin{table}[!t]
	\caption{Numerical computation of \nopreim and \unmetric for varying $k,n_o$ and $n_b$. }
	\vspace{-.8em}
	\centering
	\begin{tabular}{|c|c|c||c|c|}
		\hline
		$k$ & $n_{b}$ & $n_{o}$ & $\nopreim$ & $\unmetric$ \\
		\hline
		\rule{0pt}{8pt}2 & 10 & 15 & $8.53\times 10^{6}$ & $1.17\times 10^{-7}$ \\
		\hline
		\rule{0pt}{8pt}4 & 10 & 15 & $2.35\times 10^{9}$& $4.26\times 10^{-10}$ \\
		\hline
		\rule{0pt}{8pt}8 & 10 & 15 & $3.24\times 10^{15}$& $3.08\times 10^{-16}$\\
		\hline
		\rule{0pt}{8pt}2 & 100 & 150 & $1.72\times 10^{64}$& $5.81\times 10^{-65}$\\
		\hline
		\rule{0pt}{8pt}4 & 100 & 150 & $1.32\times 10^{99}$ & $7.58\times 10^{-100}$\\
		\hline
		\rule{0pt}{8pt}8 & 100 & 150 & $4.28\times 10^{160}$& $2.34\times 10^{-161}$\\
		\hline
		\rule{0pt}{8pt}2 & 500 & 1000 & $1.47\times 10^{538}$& $6.80\times 10^{-539}$\\
		\hline
		\rule{0pt}{8pt}4 & 500 & 1000 & $3.21\times 10^{887}$& $3.12\times 10^{-888}$\\
		\hline
		\rule{0pt}{8pt}8 & 500 & 1000 & $5.05\times 10^{1502}$& $1.98\times 10^{-1503}$\\
		\hline
	\end{tabular}
\vspace{-1em}
	\label{tab:M1}
\end{table}

\iffalse
\subsection{one $y$-deletions}

In the case of deletion of more than one element, we analyze the problem by dividing it to two separate cases. In this subsection, we consider that any number of deletions of elements in one action is possible if all the cells have identical values and are placed in continuous positions in the original string. In this case, we always have $y \leq n_{o} - 1$.

In the first case, if we delete $y$ elements, we add $y-1$ zeros to the end of the string. This approach will preserve the size of all bases and deviations to be equal after a specific amount of deletions. This approach also preserves security by covering the actual amount of deleted elements.

The second case does not include the insertion of zeros to the end of the string. This approach can generate some problems as the size of bases and/or deviations are not necessarily equal after specific number of transformations. However, this approach is much easier and can be used with combination of some ideas to preserve the equality in the size of all bases and deviations in order to form a valid transformation function.

\subsubsection{First case}

In this case, the size of each basis is exactly the same as the case of one 1-deletion as the number of elements is reduced by 1 in the transformation. Hence, the value of $n_{b}$ is identical to the case of one 1-deletion. However, the value of $s_{d}$ is different as we need to store the number of deleted cells, hence:

$$s_{d} = 2\log(n_{o}) + k.$$

Therefore, the value of $Cr$ will be equal to:

$$\mathcal{C} = r\cdot\frac{n_{o}-1}{n_{o}} + \frac{2\log(n_{o}) + k}{k\cdot n_{o}}$$

which implies a worse compression ratio than a single 1-deletion. In this case, the compression ratio is lower than 1 if and only if:

$$ r \leq 1- \frac{2\log(n_{o})}{k\cdot(n_{o} - 1)}.$$

The compression ratio in  client and cloud is equal to:

$$\mathcal{C}_{c} = r\cdot \frac{n_{o}-1}{n_{o}},$$
$$\mathcal{C}_{u} = \frac{2\log(n_{o}) + k}{k\cdot n_{o}}.$$

Similar to the 1-deletion, we always have $\mathcal{C}_{c}\leq 1$ as we always have $r \leq 1$. In this case, $\mathcal{C}_{u} \leq 1$ if and only if $2\log(n_{o}) + k \leq k\cdot n_{o},$ which is true in most practical cases.

If we consider the hash keys in storage, the compression ratios will be:
$$\mathcal{C}_{c} = r\cdot \frac{s_{d} + k\cdot (n_{o}-1)}{k\cdot (n_{o})} = r\cdot (1-\frac{k-s_{d}}{k\cdot n_{o}}),$$
$$\mathcal{C}_{u} = \frac{s_{d} + 2\log(n_{o}) + k}{k\cdot n_{o}}.$$

Here, the conditions for a valid compression is as follows:
$$r \leq \frac{k\cdot n_{o}}{s_{d} + k\cdot (n_{o}-1)}\Leftrightarrow \mathcal{C}_{c} \leq 1.$$
$$s_{d} + 2\log(n_{o}) + k \leq k\cdot n_{o}\Leftrightarrow \mathcal{C}_{u} \leq 1.$$

To find the value of $\mathcal{U}$, we must note that the number of possible strings to generate is relevant to the number of zeros at the end of the basis.
Consider exactly $c \leq (n_{b}-1)$ zeros at the end of the basis, then, the number of elements that was deleted to generate the original string, i.e., $i$, is between 1 and $(c+1)$, i.e., $1 \leq i\leq (c+1)$.
For each value of $i$, we insert $i$ elements of the same value to a position of the basis and delete $(i-1)$ zeros from the end. So for each value of $i$, we generate a number of original strings equal to the case of 1-deletion. The only possible duplicate strings are generated by adding an arbitrary amount of zeros to the end of the basis, which are $(c+1)$ cases. Hence, the number of possible strings that can be generated in this case is equal to:

$$\mathcal{U}_{c} = (c+1) \cdot \big(2^{k}\cdot(n_{b}+1) - n_{b}\big) - (c+1)= (c+1)\cdot (2^{k}\cdot(n_{b} + 1) - n_{b} - 1).$$

Using this equation combined with the probability of each basis in a uniformly random environment, we get the following result for the average number of possible strings genrated by a random basis:

$$\mathcal{U} = \frac{1}{2^{k\cdot n_{b}}}\cdot \sum_{c=0}^{n_{b}-1} 2^{k\cdot(n_{b}-c-1)}(2^{k}-1)\Big( (c+1)\cdot (2^{k}\cdot(n_{b} + 1) - n_{b} - 1)\Big).$$

$$\Rightarrow \mathcal{U} = \frac{(n_{b} + 1) (2^{k} (2^{k\cdot n_{b}} - 1) - 2^{k}\cdot n_{b} + n_{b})}{2^{k\cdot n_{b}}}.$$

This equation is derived by the fact that there are $2^{k\cdot(n_{b}-c-1)}(2^{k}-1)$ possible bases with exactly $c$ zeros in the end of the basis and the total number of bases is equal to $2^{k\cdot n_{b}}$. Also, this value is independent to $n_{o}$, because we only allow one deletion with any arbitrary size, so this value is rtue for any value of $n_{o}$. For a large value of $k$, we have:

$$\lim\limits_{k \rightarrow \infty} \mathcal{U} = 2^{k}(n_{b} + 1).$$

Which is equal to the case of one 1-deletion. Because in large enough $k$, the probability of having zeros in the end of the string is negligible, so we will have only one 1-deletion.

In order to confirm the correctness of the general equation, we used Python to generate all possible original from a random basis for $k=\{2,4\}$ and $n_{b} = \{10,12\}$. In order to make sure that the result is close to the average, we carried out the transformation for 100 random bases and reported the average. As can be seen in table~\ref{tab:M2}, the results from theory and simulation are tight.

\begin{table}[!t]
	\centering
	\caption{Number of possible strings that can be generated using a basis in one $y$-deletions}
	\begin{tabular}{|c|c||c|c|}
		\hline
		$k$ & $n_{b}$ &  $\mathcal{U}$ & Simulation\\
		\hline
		2 & 10 & 44 & 46.83\\
		\hline
		2 & 12 & 52 & 51.86\\
		\hline
		4 & 10 & 176 & 176.42 \\
		\hline
		4 & 12 & 208 & 209.23\\
		\hline
	\end{tabular}

	\label{tab:M2}
\end{table}

In order to find the possible number of bases that can be hit by a string, we find the probability that we can delete $y$ values from the string, which is equal to the probability that there are $y$ continuous elements in the string with identical values.

The probability that $y$ continuous elements in an original string are identical can be found using the principal of exclusion and inclusion. This probability is equal to:

$$P_{y} = \Big|\bigcup\limits_{c}\bigcup\limits_{i=y}^{n_{o}} S_{i, c}\Big|,$$

where $|S_{i,c}|$ denotes the number of strings with $i$ continuous elements of the value of $c$. For a simple example, if $n_{o} = 4$, $k=2$, we have:

$$|S_{2,2}| = 40,$$
$$|S_{2,2} \cup S_{2,1}| = 2.$$

The value of $|S_{i,c}|$ and their unions that are used in the calculation can be found by simple combinatorics equations.
This probability indicates the probability that we can delete $y$ elements in one transformation.
Therefore, the expected possible number of bases that can be hit by a string is equal to:

$$\mathcal{B} = \frac{1}{2^{k\cdot n_{o}}}\sum_{y=2}^{n_{o}} P_{y}.$$

\subsubsection{Second case}

In this case, we simply have:

$$n_{b} \leq n_{o} - y.$$
$$s_{d} = 2\log(n_{o}) + k.$$

Therefore, the compression ratio is bounded by:

$$\mathcal{C} \leq r\cdot\frac{n_{o}-y}{n_{o}} + \frac{(2\log(n_{o}) + k)}{k\cdot n_{o}},$$

which is lower than 1 if and only if:

$$r \leq \frac{k\cdot n_{o} - 2\log(n_{o}) - k}{k\cdot (n_{o} - y)}$$

The compression ratio in client and cloud is equal to:

$$\mathcal{C}_{u} = r\cdot \frac{n_{o}-y}{n_{o}},$$
$$\mathcal{C}_{c} = \frac{2\log(n_{o}) + k}{k\cdot n_{o}}.$$

Similar to the first case, we always have $\mathcal{C}_{c}\leq 1$ as we always have $r \leq 1$. Also, $\mathcal{C}_{c} \leq 1$ if and only if $2\log(n_{o}) + k \leq k\cdot n_{o}.$

If we consider the hash keys in storage, the compression ratios will be:
$$\mathcal{C}_{c} = r\cdot \frac{s_{d} + k\cdot (n_{o}-y)}{k\cdot n_{o}} = r\cdot (1-\frac{k\cdot y-s_{d}}{k\cdot n_{o}}),$$
$$\mathcal{C}_{u} = \frac{s_{d} + 2\log(n_{o}) + k}{k\cdot n_{o}}.$$

Here, the conditions for a valid compression is as follows:
$$r \leq \frac{k\cdot n_{o}}{s_{d} + k\cdot (n_{o}-y)}\Leftrightarrow \mathcal{C}_{c} \leq 1,$$
$$s_{d} + 2\log(n_{o}) + k \leq k\cdot n_{o}\Leftrightarrow \mathcal{C}_{u} \leq 1.$$

In order to find the number of possible strings that can be generated by a basis, we have to consider that we need to insert exactly $n_{o}-n_{b}$ number of an arbitrary value to a position in the basis in order to generate a string. We have $2^{k}$ possible values and $(n_{b}+1)$ possible positions, subtracting the potential duplicates, we have:

$$\mathcal{U} = 2^{k}\cdot (n_{b} +1) - n_{b}.$$

The number of bases that can be hit by a string is equal to the first case. The only difference is that after each deletion no zero is added to the end of the basis, which does not make or prevent any duplicates. Hence:

$$\mathcal{B} = \frac{1}{2^{k\cdot n_{o}}}\sum_{y=2}^{n_{o}} P_{y}.$$

\subsection{multiple $y$-deletions}

In the general case of multiple $y$-deletion, we need to consider that theoretically we can generate strings of infinite length from a basis. Hence, we suppose that we know the size of the original string when trying to generate a basis.

In both cases, we suppose that the transformations consist of $x$ number of $y$-deletions. The total number of deleted elements is denoted by $z$. Obviously, $z \leq x\cdot y$ and $z \leq n_{o} - 1$.

\subsubsection{First case}

In this case, we have:

$$s_{d} = x\cdot (2\log(n_{o}) + k),$$
$$n_{b} = n_{o}-x.$$

The compression ratio is equal to:

$$\mathcal{C} = r\cdot \frac{n_{o}-x}{n_{o}} + \frac{x\cdot (2\log(n_{o}) + k)}{k\cdot n_{o}},$$

this value is lower than 1 if and only if we have:

$$r\leq 1-\frac{2x\cdot \log(n_{o})}{k\cdot (n_{o}-x)}.$$

This condition is a little tighter than the equation on multiple 1-deletion, because the deviation size is larger. Therefore, in order to have an efficient compression. the number of bases should be lower then the case were only 1-deletions are allowed.

The compression ratio in client and cloud is equal to:

$$\mathcal{C}_{c} = r\cdot \frac{n_{o}-x}{n_{o}},$$
$$\mathcal{C}_{u} = \frac{x\cdot (2\log(n_{o}) + k)}{k\cdot n_{o}}.$$

Similar to the first case, we always have $\mathcal{C}_{c}\leq 1$ as we always have $r \leq 1$. Also, $\mathcal{C}_{u} \leq 1$ if and only if:
$$x \leq \frac{k\cdot n_{o}}{2\log(n_{o} + k)}.$$

If we consider the hash keys in storage, the compression ratios will be:
$$\mathcal{C}_{c} = r\cdot \frac{s_{d} + k\cdot (n_{o}-x)}{k\cdot n_{o}} = r\cdot (1-\frac{k\cdot x-s_{d}}{k\cdot n_{o}}),$$
$$\mathcal{C}_{u} = \frac{s_{d} + x\cdot(\log(n_{o}) + k)}{k\cdot n_{o}}.$$

Here, the conditions for a valid compression is as follows:
$$r \leq \frac{k\cdot n_{o}}{s_{d} + k\cdot (n_{o}-x)}\Leftrightarrow \mathcal{C}_{c} \leq 1.$$
$$s_{d} + x\cdot(\log(n_{o}) + k) \leq k\cdot n_{o}\Leftrightarrow \mathcal{C}_{u} \leq 1.$$

In order to calculate the uncertainty metric in this case, we consider that we only know the basis as well as the number of elements in the original strings. This assumption leads to the fact that we do not know how many deletions were carried out. We can only guess the deletions by the number of zeros at the end of basis. For example, if $n_{b} = 10$, $n_{o} = 13$ and there are 2 zeros at the end of the basis, the following set of deletions are valid:

\begin{itemize}
	\item three 1-deletions.
	\item two 1-deletions and one 2-deletion.
	\item two 1-deletions and one 3-deletion.
	\item one 1-deletion and two 2-deletion.
\end{itemize}

In general case, if there are $c$ zeros at the end of the basis, our transformations must satisfy the following two equations:

\begin{enumerate}
	\item $t_{1} + t_{2} + ... + t_{n_{o} - 1} = n_{o} - n_{b}.$
	\item $t_{2} + 2t_{3} + ... + (n_{o}-2)t_{n_{o}-1} \leq c.$
\end{enumerate}

In these equations, $t_{i}$ denotes the number of $i$-deletions.

For each case of the values $t = [t_{1}, ..., t_{n_{o}-1}]$, we solve the problem by following procedure:
\begin{enumerate}
	\item Set $T = \sum_{i=1}^{n_{o} -1}t_{i}$.
	\item Remove $c^{\prime} = t_{2} + 2t_{3} + ... + (n_{o}-2)t_{n_{o}-1}$ zeros from the end of the basis. We call the result the reduced basis.
	\item Find the number of sequences with the length of $n = T + n_{b} - c^{\prime}$ that has the reduced basis as its subsequence. The number of these sequences equal to:
	\begin{equation*}
	\begin{split}
	& \mathcal{U}^{\prime}_{t} = \sum_{j=0}^{T-c^{\prime}} {T+n_{b}-c^{\prime} \choose j+n_{b}} (2^{k}-1)^{T-c^{\prime}-j} \\
	& \Rightarrow \mathcal{U}^{\prime}_{t}  = 2^{k.(T+n_{b} - c^{\prime})} - (2^{k} - 1)^{T-c^{\prime} + 1} \Big( \\
	& {T-c^{\prime} + n_{b}\choose n_{b} - 1} \pFq{2}{1}{1, 1 - n_{b}}{ T-c^{\prime} + 2}{ 1 - 2^{k}}\Big).
	\end{split}
	\end{equation*}
	\item  Assign each added element a value of $t_{i}$, which would be the number of that particular element. This value equals the number of permutations of the numbers $[t_{0}, t_{1},..., t_{n_{o} - 1}].$ The number of permutations is dependent to whether the value of different $t_{i}$ are equal or not. In any case, this value is easily computed by combinatorics techniques. We denote this value as $P_{t}$. The upper bound for the value of $P_{t}$ is when each $t_{i}$ is distinct, therefore, we have:
	$$P_{t} \leq (n_{o} - 1)!$$
	\item Remove the duplicates. The duplicates occurs when there are two identical elements in the consecutive positions of the string. The total number of duplicates for each case can be found using the principle of inclusion and exclusion. We denote this value as $D_{t}$. The lower bound for this value occurs when all elements have distinct values, which is an acceptable assumption in large field sizes, i.e., large enough $k$. In this case, the duplicates occur only when an identical element is inserted either before and after an already existed element. There are $\sum_{i}t_{i} = n_{o} - n_{b}$ places to insert, hence: $D_{t} \geq n_{o} - n_{b} - 1$.
\end{enumerate}

Regarding the procedure, the total number of strings in each case is equal to:

$$\mathcal{U}_{t} = P_{t}\cdot S^{\prime}_{t} - D_{t}.$$

Using the bounds, we get:

\begin{equation*}
\begin{split}
&\mathcal{U}_{t} \leq (n_{o} - 1)!\Bigg(2^{k.(T+n_{b} - c^{\prime})} - (2^{k} - 1)^{T-c^{\prime} + 1} {T-c^{\prime} + n_{b}\choose n_{b} - 1} \\
&\times \pFq{2}{1}{1, 1 - n_{b}}{ T-c^{\prime} + 2}{ 1 - 2^{k}}\Bigg) - (n_{o} - n_{b} - 1). \\
\end{split}
\end{equation*}

The total number of possible strings that can be generated is found by summation over all possible sets, hence:

$$\mathcal{U} = \sum_{t} P_{t}\cdot S^{\prime}_{t} - D_{t},$$
which is bounded by:

\begin{equation*}
\begin{split}
&\mathcal{U} \leq \sum_{T,c}(n_{o} - 1)!\Bigg(2^{k.(T+n_{b} - c^{\prime})} - (2^{k} - 1)^{T-c^{\prime} + 1} {T-c^{\prime} + n_{b}\choose n_{b} - 1} \\
&\times \pFq{2}{1}{1, 1 - n_{b}}{ T-c^{\prime} + 2}{ 1 - 2^{k}}\Bigg) - (n_{o} - n_{b} - 1), \\
\end{split}
\end{equation*}
for all possible values of $T$ and $c^{\prime}$.

Note that there are no possibility of duplicates between different cases. The upper bound for this value is by considering all possible strings that can be generated by the basis after removing $0\leq x \leq c$ zeros from its end and considering only 1-deletions. For example, if there are 3 zeros at the end of the basis, we need to count the possible number of original strings that can be generated by basis and the basis after removing 1, 2 and 3 zeros. Each case can be treated as generating an original string from a basis with length of $n_{b} - x$. Hence:

$$\mathcal{U} \leq \sum_{x=0}^{c}{n_{o}\choose n_{b}-c}(2^{k}-1)^{n_{o}-n_{b}+c} \pFq{2}{1}{1, n_{b}-c - n_{o}}{ n_{b}-c + 1} {\frac{1}{1-2^{k}}}.$$

If we only consider some especial cases in the calculation of $\mathcal{U}$, we will have a lower bound for the value of $\mathcal{U}$. For example a lower bound is defined by only considering the case of $n_{o}-n_{b}$ 1-deletions and one $y$-deletion and $n_{o}-n_{b}-1$ 1-deletions for all $y \leq c$. For the case of one $y$-deletion and $n_{o}-n_{b}-1$ 1-deletions, we calculate the number of original strings using following procedure:

\begin{enumerate}
	\item Insert $y$ elements with the same value in an arbitrary position. The number of unique strings that can be generated this way is equal to the number of strings in one 1-deletion case, hence:
	$$\mathcal{U}_{1} = 2^{k}.(n_{b} + 1).$$
	\item Generate a string by using the newly generated string as basis and $n_{o}-n_{b}-1$ 1-deletions. In this case, the number of unique strings that are generated is equal to:
	\begin{equation*}
	\begin{split}
	& \mathcal{U}_{2} = {n_{o}\choose n_{b}+1}(2^{k}-1)^{n_{o}-n_{b}-1} \times \\
	& \pFq{2}{1}{1, n_{b} - n_{o}+1}{ n_{b} + 2} {\frac{1}{1-2^{k}}}. \\
	\end{split}
	\end{equation*}
	\item There are no duplicates between the generated strings, hence the total number of original strings is equal to:
	\begin{equation*}
	\begin{split}
	& \mathcal{U}_{3} = \mathcal{U}_{1}\times \mathcal{U}_{2} = 2^{k}.(n_{b} + 1) {n_{o}\choose n_{b}+1}(2^{k}-1)^{n_{o}-n_{b}-1} \times \\
	& \pFq{2}{1}{1, n_{b} - n_{o}+1}{ n_{b} + 2} {\frac{1}{1-2^{k}}} \\
	\end{split}
	\end{equation*}
\end{enumerate}

Combining $\mathcal{U}_{3}$ with the number of strings that are generated in the case of $n_{o}-n_{b}$ 1-deletions, we get the following lower bound for the uncertainty metric:

\begin{equation*}
\begin{split}
&\mathcal{U} \geq {n_{o}\choose n_{b}}(2^{k}-1)^{n_{o}-n_{b}} \pFq{2}{1}{1, n_{b} - n_{o}}{ n_{b} + 1} {\frac{1}{1-2^{k}}} + \\
&2^{k}.(n_{b} + 1) {n_{o}\choose n_{b}+1}(2^{k}-1)^{n_{o}-n_{b}-1} \times \\
& \pFq{2}{1}{1, n_{b} - n_{o}+1}{ n_{b} + 2} {\frac{1}{1-2^{k}}}.
\end{split}
\end{equation*}

This equation can be further improved to be a tighter upper bound by considering more special cases.

The number of bases that can be generated by a string is equal to the number of possible deletion sequences of the form $[d_{1}, ..., d_{n_{o}-n_{b}}]$, where each deletion $d_{i}$ has the output of the previous deletion, i.e., $d_{i-1}$ and outputs a reduced string when an arbitrary number of consecutive identical elements are deleted. The input of $d_{1}$ is the original string. The lower bound for this value is when each deletion is a 1-deletion. Hence,

$$\mathcal{B} \geq {n_{o}\choose n_{b}}$$

\subsubsection{Second case}

In this case, we have:

$$s_{d} = x\cdot (2log(n_{o}) + k),$$
$$n_{b} = n_{o}-z.$$

The compression ratio is bounded by:

$$\mathcal{C} \leq r\cdot \frac{n_{o}-z}{n_{o}} + \frac{x\cdot (2\log(n_{o}) + k)}{k\cdot n_{o}},$$

this value is lower than 1 if and only if we have:

$$r\leq \frac{k\cdot n_{o} - 2x\cdot \log(n_{o}) -x\cdot k}{k\cdot (n_{o} - z)}.$$

The compression ratio in client and cloud is equal to:

$$\mathcal{C}_{c} = r\cdot \frac{n_{o}-z}{n_{o}},$$
$$\mathcal{C}_{u} = \frac{x\cdot (2\log(n_{o}) + k)}{k\cdot _{o}}.$$

In this case, we always have $\mathcal{C}_{c}\leq 1$ as we always have $r \leq 1$. Also, the compression ratio in the client is exactly the same as the first case, hence the compression ratio in the client is lower than 1 if and only if:

$$x \leq \frac{k\cdot n_{o}}{2\log(n_{o} + k)}.$$

If we consider the hash keys in storage, the compression ratios will be:
$$\mathcal{C}_{c} = r\cdot \frac{s_{d} + k\cdot (n_{o}-z)}{k\cdot n_{o}} = r\cdot (1-\frac{k\cdot z-s_{d}}{k\cdot n_{o}}),$$
$$\mathcal{C}_{u} = \frac{s_{d} + x\cdot (2\log(n_{o}) + k)}{k\cdot n_{o}}.$$

Here, the conditions for a valid compression is as follows:
$$r \leq \frac{k\cdot n_{o}}{s_{d} + k\cdot (n_{o}-z)}\Leftrightarrow \mathcal{C}_{c} \leq 1,$$
$$s_{d} + x\cdot(2\log(n_{o}) + k) \leq k\cdot n_{o}\Leftrightarrow \mathcal{C}_{u} \leq 1.$$

In this case, the total number of strings that can be generated by a basis is exactly equal to the case of $z$ 1-deletions, hence:

$$\mathcal{U} = \sum_{j=0}^{n_{o}-n_{b}} {n_{o} \choose j+n_{b}} (2^{k}-1)^{n_{o}-n_{b}-j},$$
$$\Rightarrow \mathcal{U} = {n_{o}\choose n_{b}}(2^{k}-1)^{n_{o}-n_{b}} \pFq{2}{1}{1, n_{b} - n_{o}}{ n_{b} + 1} {\frac{1}{1-2^{k}}}.$$

The number of possible bases that we can hit is equal to the number of subsequences of length $n_{b}$, hence,

$$\mathcal{B} = {n_{o}+n_{b}-1\choose n_{b}}.$$

\fi

\subsection{Most Probable String}

Let $P(\file=o|\outsource,\distribution)$ denote the probability of an original string $o$ of length $n_o$, given a basis \outsource and a probability distribution of \distribution for the symbols in the original strings.
From an attacker's perspective, the key is to identify the most probable string, i.e., the string $o$ in the set of all strings of size $n_{o}$, that has
$\max\limits_{o} P(\file=o|\outsource,\distribution)$.
From a system designer's perspective, a similar question is interesting to achieve a higher privacy in the system.
Namely, the system wants to \emph{minimize} this probability.

In order to generate the original data, the attacker needs to add $n_{o} - n_{b}$ symbols to the basis in arbitrary positions.
In this setup, The most probable strings is the string with the most number of duplicates in the reconstruction. The duplicates occur when we insert a value $i$ between consecutive elements in basis that already has value $i$.
Suppose the longest consecutive elements of value $i$ in \outsource has length $l_{i}$, hence, the number of possible duplicates is equal to:
$$\max\limits_{i}\sum_{j=0}^{n_{o}-n_{b}} (l_{i}+j) = \max\limits_{i}\frac{1}{2} (n_{o}-n_{b}+1)(2\cdot l_{i} +n_{o}-n_{b}).$$

Therefore, the most probable string has a probability of:
\begin{equation}
\begin{split}
&\max\limits_{o}P(\file=o|\outsource,\distribution) = \\
& \max\limits_{i}\Big(\frac{1}{2} p_{i}^{n_{o}-n_{b}}\cdot (n_{o}-n_{b}+1)(2\cdot l_{i} +n_{o}-n_{b})\Big),
\end{split}
\end{equation}
Clearly, there is a strong dependence on the probability distribution of the original strings.
To reduce this probability for a set of data, we can define several policies:

\textbf{Policy 1:} Set the probability distribution of the elements in the basis to be as close as possible to uniformly random distribution, e.g., a ciphertext. This may be counterproductive for the compression process. However, approaching a uniform distribution provides clear privacy advantages. A system designer can try to select the level of protection desired.

\textbf{Policy 2:} A basis does not include consecutive identical symbols, especially the symbols with higher probability.

\section{Conclusion}\label{sec:conclusion}
We presented \name, a protocol that allows Cloud Storage Providers to carry out deduplication across data uploaded by multiple clients, while introducing a level of uncertainty which provides privacy for the data sent by the individual clients.
This injection of uncertainty is carried out by each client individually by transforming the data prior to upload and
storing a compact description of such transformations locally.
We propose an improvement on the concept of generalized deduplication to increase its compression potential, that consists of allowing the CSP to swap and change values of the records it receives from clients.
Our numerical results show that \name reduces the amount of data stored in the Cloud, in the local device and even in the system as a whole, while providing a high degree of uncertainty regarding the data uploaded by each client.
A side advantage of \name is that it can protect from side channel attacks from malicious clients trying to gain knowledge about the data stored by other clients in the Cloud.
Future work will consider malicious adversaries and clients that do not reveal the original size of the chunk and only comply with the expected basis size of the Cloud.
This added uncertainty requires further analysis as the attacker would not have the information about the chunk's original size as prior knowledge.

\section{\name}\label{sec:contribution}

We begin by describing the set of allowed transformations in \name. Then we explain the protocol in detail.

\input{sections/transformations}

\vspace{-4pt}
\subsection{Proposed Protocol}

We describe \name, our protocol for privacy-aware dual deduplication in multi client settings.
The protocol is run between \user and \cloud, components of \system and is parametrized by
\begin{enumerate*}[label=(\alph*)]
	\item a distance metric \dist;
	\item a threshold value $\threshold>0$ that indicates the maximum number of operations allowed in the \cloud per string;
\end{enumerate*}
At initialization
\cloud holds an initial set $n_b$-size strings called bases $\baseset=\{\base_1,\ldots, \base_b\}$.
\footnote{We do not specify how to construct the initial set \baseset. However, the \compress algorithm of \name essentially allows to start from an empty $\baseset=\varnothing$ and populate it according to the uploaded files.}
$\baseset$ can be updated over time, but the full potential of updating \baseset  will be studied in future work.

At its core, the protocol performs a number of operations in the \user with a focus on privacy protection
prior to uploading to the \cloud.
\cloud uses the information from each \user and the $\baseset$ to attempt deduplication of similar bases that are $\threshold$ operations away given a \dist metric.
If the data is similar to one basis in the $\baseset$, it will be deduplicated, otherwise, it will be stored as it is.
In the following, we provide a description of the various operations of \name and where they take place.

\begin{description}
\item[$\setup(\baseset)$:]
	This algorithm is run by the \cloud periodically.
	It takes as input a set of bases \baseset

	and outputs a policy \policy that concisely describes \baseset.\footnote{Policies ensure efficient deduplication according to the current set of bases.
	To give an example \policy could encode
	`binary strings of length $n_b$ with $5$ number of 0s towards the end'.
}

\item[$\upload(\policy,\file)$:]
	This algorithm is run by \user using a given \policy
	On input of a file \file, \deletions are applied to \file according to \policy
	until it results in a string \outsource with the size of $n_{b}$,
	and its corresponding deviation \local.
	Then, it generates a unique file identifier \id for the pair (\outsource, \local).
	It outputs the pair (\id,\outsource) to the CSP,
	while the pair (\id,\local) are stored locally on the \user.

	\item[$\compress(\baseset, \id, \outsource)$:]
	This algorithm is run by the \cloud.
	It takes as input \baseset,

	a file identifier \id and a string \outsource.
	Then, it performs the following steps:
\vspace{.3em}

	1. If $\outsource =\hit{\base}\in \baseset$ set $\deviation=\varnothing$ and go to step 4.
\vspace{.3em}

	2. If $\exists \hit{\base}\in \baseset$ that $0<\dist( \outsource, \baseset) \leq\threshold$
	then:

\hspace{1em}- Repeatedly apply \swap and \changev on \outsource until reaching the target $\hit\base$. Denote by $\deviation$ the corresponding string of deviations.
\vspace{.3em}

	3. If $\forall\hit{\base}\in\baseset$ that $\dist(\outsource,\baseset)>\threshold$ set $\hit{\base}:=\outsource$,
	set $\deviation=\varnothing$ and add \hit{\base} to \baseset.
\vspace{.3em}

	4. Perform deduplication by storing
	the file identifier \id, a pointer to \hit{\base} and the string \deviation.

	\item[$\get(\id, \local, \cdot)$:]

	This algorithm is initiated by \user sending an \id, symbolizing a request to retrieve the item that was outsourced with that \id.
	Upon receiving a response \outsource from \cloud, the
	\user uses the information encoded in the local deviation \local connected to \id to invert the deletions that led to \outsource, thus reconstructing \file.

      \item[$\decompress(\database, \cdot)$:]

      This algorithm is run on \cloud upon receiving a query of the form \id.
      	\cloud checks whether it has stored \id.
      	If not, it ignores the query, otherwise it retrieve the corresponding item (\id, \base,\deviation) and inverts the generalized deduplication performed by \compress  to reconstruct the decompressed \outsource corresponding to the outsourced string. \outsource is sent back to \user.
\end{description}

\begin{figure}[!t]
	\centering
	\begin{tikzpicture}[font=\small\sffamily, thick, scale=0.7]

	\node[cloud, cloud puffs=19, cloud ignores aspect, minimum width=6cm, minimum height=2.5cm, align=center, draw] at (0cm, 0cm) {};
	\node [alias=cloud] at (0,-1.2){};

		\node [alias=setup,style={rectangle, draw=red!60, fill=red!5, very thick}] at (-2.5,0.33){1. \setup};

		\node [alias=set] at ([xshift=45pt] setup.east){$\baseset$};

		\node [alias=swap,style={rectangle, draw=red!60, fill=red!5, very thick}] at ([xshift=45pt] set.east){3. \compress};

		\node [alias=rec,style={rectangle, draw=red!60, fill=red!5, very thick}] at (0.14,-.7){\decompress};

		\draw (.7,-3.2) node[anchor=north,rounded rectangle,minimum width=3.3cm, minimum height=.8cm,
		draw, alias=one]{};

		\node[alias=get,style={rectangle, draw=blue!60, fill=blue!5, very thick}] at (-.5,-3.8) {{\get}};

		\node[alias=upload,style={rectangle, draw=blue!60, fill=blue!5, very thick}] at ([xshift=42pt]get.east) {2. \upload};

		\node [alias=policy, style={rectangle,  minimum width=1.1cm,minimum height=1.1cm, draw=black!60, thin}] at ([xshift=-60pt] get.west){$\policy$};

	\path[->, dashed,thin] (policy) edge (one);
	\path[->, thick,red] ( setup.south) edge [bend right] ([yshift=2pt]policy.north);

	\path[->, very thick,blue] ( upload.east) edge [bend right] (swap.south);

		\path[->, very thick,blue] ( [xshift=-4pt,yshift=3pt] get.north) edge [bend left] ([xshift=-4pt]rec.south);

		\path[->, thick,red] ( [xshift=4pt] rec.south) edge [bend left] ([xshift=4pt,yshift=3pt]get.north) ;

			\path[->, dashed,thin] (set.west) edge (setup.east);
			\path[->, dashed,thin] (swap.west) edge (set.east);
			\path[->, dashed,thin] ([yshift=3pt]set.south) edge (rec.north);

	\end{tikzpicture}
	\vspace{-.8em}
	\caption{\name System Model for Secure, Multi-client Dual Deduplication}
	\label{fig:deletion}
	\vspace{-1.5em}

\end{figure}

\section{Simulation Results and Discussion}\label{sec:experiments}

In this section, we first show our simulation results and then discuss the results and the performance of \name.
In order to validate our system, we use the data of $18$~GB of HDFS logs as our dataset.
We developed a C++ implementation of a \name client applying random $1$-deletions and a server performing swap and change value operations.
The client and server both carry out deduplication steps separately.
For the sake of storage friendly implementation, we defined the \id of bases to be a global variable auto-incremented by the Cloud.
This means that each \id has a storage size of $\log(\mathcal{N}_{b})$ where $\mathcal{N}_{b}$ is the number of bases after deduplication.
This can be later changed to standard fingerprint functions, e.g., SHA-1, SHA-256, in the Cloud.
The impact of these slightly larger \id is minor for bases of 1~KB of more in size, which is the case we focus on in the following.

Fig.~\ref{fig:result1} shows
that a judicious selection of the number of transformations results in a total compression ratio $\compratio = 0.5527$ for $n_{b} = 950$ and $\compratio = 0.6583$ for $n_{b} = 900$.
For a fixed value of $n_{b}$, the compression ratio in the \user is constant as the client always performs $n_{o} - n_{b}$ deletions.
However, the compression ratio of the \cloud differs depending on the maximum number of allowed swap and change value operations ($\threshold$).
A small $\threshold$ results in high compression rates. In fact, overall stored data may be higher than the original size because the number of bases that are deduplicated is low.
Thus, the extra storage required to store the operations is larger than the gains from deduplication.
A higher $\threshold$ allows for more bases to be deduplicated.
We show that there exists a minimum point for both \cloud and overall compression ratio.
This is the best compression ratio achievable for a given pair ($k$, $n_{b}$) for $n_o = 1024$.
Our analysis shows that this minimum is close to the median of the swap distance between all bases, which can be used in future work as a heuristic for the optimal value of $\threshold$.
Larger $\threshold$ values result in an increase in the compression ratio, because there are diminishing returns on the deduplication potential and the cost of recording additional operations results in much higher storage costs.

Fig.~\ref{fig:result1}.(c) shows the best compression ratio achieved for various values of $n_{b}$ and $k$ and a fixed $n_o$ and shows an optimal selection of $n_b$ and $k$ to achieve the highest overall compression.
Fig.~\ref{fig:result1}.(c) shows that this minimum point is reached for a lower $n_b$ when $k$ is smaller, e.g., the best compression ratio for $k=2$ is achieved at $n_{b} = 900$, while the best compression ratio for $k=8$ is achieved at $n_{b} =950$.
We also observe that $k=8$ provides the best potential for compression overall ($49$~\% of original data) with only small degradations of the compression rate around the optimal point.
This is important in practice as the \user's may aim to achieve different uncertainty - storage trade-offs and $k=8$ corresponds to byte representations that are good to achieve efficient software implementations.
Note that for $(k,n_b,n_o)=(8,950,1024)$ the number of possible original strings that could generate each basis uploaded to the \cloud is around $10^{293}$.
For $k = 16, 32$ the cost of storing the deviation for each elimination in the \user is high, which limits the overall potential for compression in the \user and, thus, in the overall system.
Table~\ref{tab1} provides details for the \cloud and \user compression ratios for different $k$ and $n_b$.

\begin{table}[t]
	\caption{The Best Compression Rate for overall data, cloud and client for $n_{o} = 1024$ for different values of $k$.}
	\vspace{-1.3em}
	\begin{center}
		\begin{tabular}{|c|c|c||c|c|c|}
			\hline
			$n_{b}$ & $k$ & $\threshold$ & $\compratio$& $\ucr$ & $\ccr$ \\
			\hline
			900& 2 & 85 & 0.5527 & 0.2482 & 0.3158\\
			900& 4 & 44 & 0.5341 & 0.2119 & 0.3012\\
			900& 8 & 25 & 0.5419 & 0.1773 & 0.3645 \\
			900& 16 & 16 & 0.8493 & 0.1468 & 0.7025\\
			900& 32 & 6 & 0.9329 & 0.1159 & 0.08168 \\
			\hline
			950& 2 & 115 & 0.6583 & 0.4423 & 0.2159\\
			950& 4 & 59 & 0.5927 & 0.4038 & 0.1889 \\
			950& 8 & 31 & 0.4912 & 0.3645 & 0.1266 \\
			950& 16 & 15 & 0.8922 & 0.3218 & 0.6705\\
			950& 32 & 7 & 1.0657 & 0.2894 & 0.7352 \\
			\hline
		\end{tabular}
		\label{tab1}
		\vspace{-2.5em}
	\end{center}
\end{table}

\section{Introduction}
\label{intro}
The massive migration of data from  storage facilities on `the Premise' to `the Cloud' has led to a boom in the offer of Cloud Storage Providers (CSPs).
Nowadays, people can turn to a vast spectrum of CSPs that offer a virtually unlimited storage accessible from `anywhere' in the world.
To deliver the promised features to multiple clients at a competitive price, CSPs resort to compression techniques that reduce the footprint of data, so as to fit more in less space.
A popular approach to reach this goal is to adopt \textit{data deduplication} techniques.
In brief, these solutions work by recognizing whether a freshly uploaded file is \emph{the same} as one already stored on the server.
If so, there is no need to store the new file: a pointer to the already existing copy would suffice.
Obviously the chance that clients upload the exact same data is quite low, but applying this technique on chunks of files leads to a non trivial compression capability.
This relevant
when a client stores different versions of the same file (thus, files have several common chunks), or different clients use the same kind of files, e.g., virtual machine disk images of different Linux distributions~\cite{Jin2009,Ng2011}

Vestergaard et al. recently proposed \emph{generalized deduplication} (GD)~\cite{Vestergaard2019a,Vestergaard2019b}, a technique to further reduce the footprint of the storage systems.
The intuition behind GD is to perform data compression on chunks that are \emph{nearly} identical rather than \emph{exactly} the same.
This is possible by using a transformation function that maps each chunk to a \emph{basis} and a \emph{deviation}, where different chunks may have the same basis but different and unique deviations to differentiate them.
The system assigns a fingerprint, e.g., a hash function to each basis
and carries out deduplication on the bases.
Using GD, similar chunks, i.e., chunks that are mapped to the same basis are deduplicated together.
The system then stores a pointer to the basis and the deviation in form of a small textual deviation with the information on how the new chunk \textit{differs} from the pointed basis.
It has been shown that generalized deduplication achieves a higher level of compression than classic deduplication techniques~\cite{Vestergaard2019b}.

Trivially, deduplication techniques perform better on highly correlated data.
However, similarities appear only if the files are uploaded in plaintext\footnote{Alternatively, the files could be encrytped using a deterministic encryption scheme, and then uploaded. However deterministic encryption cannot be semantically secure.
Moreover to guarantee meaningful deduplication of ciphertexts generated by different clients there needs to be some coordination on the encryption key.}, which is not desirable in many applications.
Privacy-conscious clients may upload encrypted data to the Cloud.
The semantic security of the encryption implies that ciphertexts look random. In particular, files that could be deduplicated become uncorrelated when encrypted, undermining the whole purpose of deduplication.

Up to now, the bulk of work performs deduplication for storage on plaintext data at one location, usually on the Cloud side, since it is assumed to have more computational power a client.
In contrast, we consider the following \emph{unorthodox} setting: secure deduplication is carried out, in a subsequent manner, by two parties.
That is, the client (e.g., user end device, local storage system, private Cloud) and the server (e.g., CSP).
We call this method \emph{dual deduplication}.
We present a solution that allows clients to outsource their data in a privacy-preserving manner, while the server is guaranteed a high compression rate.

We achieve this solution by letting the clients preprocess their data prior to upload.
The outcome of this process is a pair where the first item is an outsourced generalized deduplication friendly `\textit{basis}' that the client sends to the cloud. In practice, this could be achieved by the client uploading a single file containing a number of unique bases of the same size or by uploading each basis separately.
The second item is a deviation, a short string that simultaneously serves two purposes:
(1) enabling the correct recovery of the original data from the outsourced file (e.g., indicating which basis was used and how was it modified to generate the $i$-th data chunk);
and (2) providing some level of privacy on the outsourced data.

Having received a set of deduplication-friendly bases, the CSP can use GD to successfully deduplicate bases received from numerous clients, reducing the total storage space to a fraction of what could be achieved from raw, unprocessed data.
Although the overall storage space needed by the server and the clients may be higher than if deduplication was carried out only on the server side,
the storage space required by each party, i.e., client and server separately, is considerably smaller compared to plain storage on the client side or generalized deduplication on unprocessed data on the server side.

We name our solution \name, as the Cosmic Tree of Life in the Norse mythology.
\name is an enormous ash tree that connects the different worlds with the heavens.
We use this as a metaphor for our system
(see Fig. \ref{fig:system}).
The clients preprocess the data and keep a fraction of it for privacy reasons.
The Cloud collects the deduplication-friently bases output by the clients and organizes them into a (compressed) foliage.

The contributions of this paper are organized as follows.
Section \ref{sec:model} introduces
the framework of \name;
the kind of adversary we deal with (an honest-but-curious CSP) and its goal (to reconstruct clients' original data);
and the mathematical expressions we use to measure the performance of the system including compression ratios, and the uncertainty metric measuring the privacy retained by clients against our adversary.
Section \ref{sec:contribution} explains our solution, \name, in detail (its algorithms and how they interact).
Section \ref{sec:analysis} presents our
upper bounds on the different compression ratios and privacy analysis of our solution.
Section \ref{sec:experiments} collects and discusses the numerical results obtained when testing \name on  a real dataset of HDFS log files.
Our main focus is the compression potential of our proposal in different settings depending on the way we parse raw data and the type of transformations allowed on the clients' side.
Section \ref{sec:conclusion} concludes the paper and highlights directions for future work.

\section{System Model and Performance Metrics}\label{sec:model}

In this section, we define our system model, the attacker model and then present the metrics we use to analyze the performance and privacy of our proposal \name.

\subsection{System Model}\label{sec:model_system}
Figure~\ref{fig:system} depicts our system model.
Clients' desiderata is
to retain some level of privacy on their files
while minimizing the amount of local storage.
The CSP desiderata is to optimize its storage space.
In order to meet all desiderata simultaneously,
we let
clients apply some transformations on their data, prior to upload.
Such transformations aim to prevent the CSP (or any third party) from easily guessing the clients' original (raw) data while requiring required minimal storage on the clients' side.
To minimize the storage requirements on the Cloud side,
we let the CSP perform Generalized Deduplication.
To further decrease storage, our model envisions a CSP that processes outsourced data before running GD.

We consider that the system operates on data strings with $k$-bit symbols, i.e., any symbol can take $N = 2^k$ possible values.
A file is broken up into a number of original strings of size $n_o$ symbols, i.e., $\file \in (\{0,1\}^k)^{n_o}$.
After a client applies its transformation, the resulting base (called \outsource) of size $n_b$ symbols
and there is an associated local deviation \local that captures the changes performed on the original string.
At a given point, there are $\nof$ strings in the \user and $\nob$ bases stored in the \cloud.

\begin{figure}[!t]
	\centering
	\vspace{-0.1em}
\begin{tikzpicture}[font=\small\sffamily, thick, scale=0.61]

\node[cloud, cloud puffs=19, cloud ignores aspect, minimum width=4cm, minimum height=1.4cm, align=center, draw] at (0cm, 0cm) {Cloud};
\node [alias=cloud] at (0,-1.2){};
\draw (-2.2,-4.5) node[anchor=north east,rounded rectangle,
draw, alias=one]{Client$_1$};
\path[<->,very thick] (one) edge [bend right] ([xshift=-6pt] cloud);
\draw (0,-4) node[anchor=north,rounded rectangle,
draw, alias=two]{Client$_2$};
\path[<->,very thick] (two) edge ([xshift=0pt] cloud);

\draw (1.7,-4.6) node[anchor=north west, rounded rectangle,
draw, alias=three]{Client$_3$};
\path[<->,very thick] (three) edge [bend left] ([xshift=6pt] cloud);

\draw (2,-3.2) node[anchor=north west,rounded rectangle,
draw, alias=fuor]{Client$_n$};
\path[<->,very thick] (fuor) edge [bend left] ([xshift=12pt] cloud);

\end{tikzpicture}
\vspace{-0.7em}
\caption{\name system model: several independent clients upload data to the same cloud storage provider.}
\label{fig:system}
\vspace{-1.5em}
\end{figure}

An instructive example of Client side transformations is the (randomized) \textit{$1$-deletion} depicted in Figure~\ref{dataFig}.
This transformation takes in input a string $\file$ of $n$ elements,
selects a component of $\file$ at random, say the $i$-th, and outputs
the base $\file'$ of $n-1$ elements obtained from $\file$ by removing (deleting) the $i$-th element, and the 2-element deviation $ D$ consisting of the deleted value and its original position $i$ (in $\file$).

To build up intuition, the more \textit{deletions} a client performs before uploading its data the harder it is for a CSP to reconstruct the original data.
This increases the privacy of the outsourced data, however, the storage footprint on the client's side also increases.
Section \ref{sec:transformations} elaborates on the transformations deployed in \name, while
Section \ref{sec:analysis} analyzes the trade off between level of uncertainty and storage size on the client end.

\begin{figure*}[t]
	\centering
	\begin{tikzpicture}[
	node distance=0pt,
	start chain = A,
	X/.style = {rectangle, draw
		minimum width=2ex, minimum height=3ex,
		outer sep=0pt, on chain},
	B/.style = {decorate,
		decoration={brace, amplitude=5pt,
			pre=moveto,pre length=1pt,post=moveto,post length=1pt,
			raise=1mm,
			#1},
		thick},
	B/.default=mirror,
	]
	\foreach \i in {4,6,1,3,0,7}
	\node[X,right] {\i};

		\node[X,text=red,right] {1};

	\foreach \i in {2,2,
		5,4}
	\node[X,right] {\i};

	\node (end)[X, right] {5};
	\node (begin)[X, right = 1.3cm] {4};

	\foreach \i in {6,1,3,0,7,2,2,
		5,4,5}
	\node[X, right] {\i};

	\node[X,,text=red, right = 1 cm]{1};

	\node[X, right] {6};

	\draw [arrow] (end)  -- (begin);
	\node (B1) [inner sep=1pt,above=of A-6.north west] {Original/Raw Data ($\file$)};
	\node (B2) [inner sep=1pt,above=of A-19.north west] {Base to Outsource ($\file'$)};
	\node (B3) [inner sep=1pt,above=of A-25.north west] {Deviation ($D$)};
		\foreach \x [count=\i] in {0, ...,11}
		\node [below=of A-\i]{\textcolor{black!50}{\x}};
		\node[below=of A-1, xshift=-30pt]{\textcolor{black!50}{$position$}};
		\foreach \x  in {0, ...,10}
		\pgfmathsetmacro{\i}{\x+13}
		\node [below=of A-\i,xshift=-5pt, yshift=-6pt]{\textcolor{black!50}{\x}};
		\node [below=of A-24,xshift=-9pt]{\textcolor{red!50}{{$value$}}};
		\node [below=of A-25,xshift=11pt ]{\textcolor{black!50}{$pointer$}};

		\end{tikzpicture}
		\vspace{-1em}
	\caption{Example of a 1-deletion: the random index is $i=6$ and the corresponding deleted value is 1 (highlighted in red).}
	\label{dataFig}
\vspace{-1em}
\end{figure*}
\vspace{-3pt}
\subsection{Attacker Model}\label{sec:attacker_model}
We consider privacy against a computationally unbounded, honest-but-curious CSP,
In detail, we assume this CSP
knows the distribution of clients' raw files \distribution,
reads all data outsourced by clients, and
has unlimited computational power.
The attacker's goal is to correctly reconstruct
 the clients' original files.
We discuss how to measure the success probability of such attacks in the next section (\ref{sec:metrics}) through the `uncertainty metric'.
Investigating how to reach security against a malicious attacker, either CSP or client is left as future work.

\subsection{Performance Metrics}\label{sec:metrics}

In what follows, \database denotes a database (collection of arbitrary files \file),
\system denotes the dual deduplication system described in Section \ref{sec:model_system},
\size\ is a function that takes as input a system \system, a party, e.g., \user or \cloud and a database \database, and returns
the size of the storage space required by the given party to store \database according to the system \system.

Since our model describes systems where both \user and \cloud store some piece of information,
it is natural to define three quantities to measure the system compression capability.

\begin{description}
	\item[{Client Compression Ratio:}]
\begin{equation}\label{eq:ucr}
	\ucr = \frac{\size(\system, \user, \database)}{|\database|}.
\end{equation}

\item[{Cloud Compression Ratio:}]
	\begin{equation}\label{eq:ccr}
	\ccr = \frac{\size(\system, \cloud, \database)}{|\database|}.
\end{equation}

\item[{Global Compression Ratio:}]
	\begin{equation}\label{eq:gcr}
	\compratio  = \frac{\size(\system, \user, \database)+\size(\system, \cloud, \database)}{|\database|}.
	\end{equation}
\end{description}

Concretely, \compratio measures the compression capability of our system.
The lower the value of \compratio the better the compression level and the smaller the overall storage space required.
An ideal solution would have $\compratio< 1$.

Now we define a metric for evaluating the privacy of a system \system.
The uncertainty metric \unmetric measures the degree of uncertainty a honest-but-curious CSP
 faces when trying to retrieve clients' original files from the data they outsource.
 To formally define \unmetric we need a distribution \distribution defined on the database \database. This essentially simulates the fact that CSP may know what are the most common files.
Thus  we define
\begin{description}
	\item[Uncertainty Metric:]
\begin{equation}\label{eq:uncertainty}
\unmetric(\file) = Prob_{\file\gets {\distribution}}[  \file^*\gets\adversary(\distribution, \file') | \file^*=\file]
\end{equation}
\end{description}
where $\file'$ is the outsourced data uploaded by the clients to the Cloud in correspondence to the original \file.

\subsection{Allowed Transformations in \name}\label{sec:transformations}
From information theory, we know four functions to transform a string.
Namely, \begin{enumerate*}[label=(\roman*)]
	\item \label{lins}
 insert an element to a position,
 \item \label{ldel}
 delete an element from a position,
 \item \label{lswap}
  swap two elements, and
 \item \label{lchange}
 change the value of a given position.
\end{enumerate*}
Note that swap and change value do not change the length of the string, while insert and delete do.

\name allows \user and \cloud to determine policies on how to transform the data to obtain deduplication friendly strings.
The aim is to minimize the number of operations to perform while achieving efficient deduplication rate on the Cloud and some level of privacy at the Client side.
These policies typically require a metric to determine similarities among strings.
A natural metric is
the \textbf{Hamming distance}, indicating the number of positions with different values in two strings of the same length.
This essentially tells us how many \emph{change value} operations we need to transform a string into another. \textbf{Swap Distance} indicates the number of operations to change a string into another using only the \emph{swap} and \emph{change value}.
\textbf{Damerau–Levenshtein Distance} is the most complete metric, essentially indicating the number of operations to transform one string into another if we use all 4 transformations \ref{lins}-\ref{lchange}~\cite{brill2000improved}.

Previous work on GD focused primarily on changing values operations using Hamming or Reed-Solomon codes~\cite{rasmus,Vestergaard2019b}.
Here we instead consider the three operations \ref{ldel}-\ref{lswap}-\ref{lchange}: delete (\deletions), swap (\swap) and change value (\changev).
We discard the \emph{insert} function as it increases the size of a string, which is counterproductive for compressing the data.

In \name,
\user applies \deletions transformations on \database prior to sending data to \cloud to achieve the desired level of privacy.\footnote{Note that \deletions drops random components from the original string (Fig. \ref{dataFig}) and thus
acts as a deletion channel~\cite{mitzenmacher2009} for the \cloud.
The hardness of the reconstruction of the original data reflects into the \user's privacy level.}
\cloud applies \swap and \changev to reduce the distance between the strings uploaded by \user, generating strings that are suitable for genealized deduplication.

redpajama_set_name: RedPajamaArXiv


There is certainly no shortage of sophisticated machinery that can measure how healthy you are, from scanners to genetic and molecular tests that can expose the inner workings of your cells, but doctors may soon be relying on something far simpler to gauge your well-being. Don't be surprised if at your next checkup, your physician asks you to take a stroll.
That's right, a walk. While researchers have known that walking speed is a good proxy for how healthy and functional someone is, new work suggests that how fast you walk may also be a strong predictor for how long older adults will live.
The findings confirm previous studies that had linked walking speed to health, but for the first time, the benefit is quantified in a way that could be helpful for physicians treating older patients. How quickly an elderly person walks is a good indicator of how well a variety of their organ systems are functioning, from the most obvious muscle, joint and skeletal networks to the heart, lungs, blood, brain, nerves and other cells. Assessing a person's overall function by their walking speed could be an easy and inexpensive way for doctors to determine, for instance, whether their patients could benefit from preventive health measures such as changes in diet or exercise that could extend their survival even more. Or, alternatively, the test could identify patients who are in poorer health, and could improve their survival chances with additional treatments or other medical interventions. By tracking walking speed, doctors can also measure whether a patient's health is declining over time, since a slowing in gait could signal an impending medical problem.
Can You Harvest Energy from Body Movement?


For the newly diagnosed in a place of fear and confusion, Mindful Advocacy relates to both the quirky and common worries you face when being treated for a mental health concern. Every week, we go to bat for each other by sharing stories of struggle and triumph; inciting uplifting conversations in an accessible podcast format. Believe us: You're not crazy, but denying help when you need it truly is. So, ask those wildcard questions. We're here for you.
One way to be okay in your own skin is to accept yourself as you are in the way you practice joy, but especially grief. Racha Tahani Lawler, midwife and mama, addresses how to be with and for someone going though a loss. When we are our own strongest advocates, we are ensuring that ourselves and our loved ones are not spoken for, but heard fully.
Your body belongs here on planet earth, as-is. Kelsey Domann-Scholz, Counselor and Graduate Student, discuss intuitive eating and body-liberation, as it may pertain to all bodies. She speaks kindly and lovingly to any who are unsure about how to accept themselves. We address trauma and behavior, while holding medical concerns in mind. Food is not immoral. It's okay. And so are you.
This one's all about boundaries and burnout. We want none of it. Tune in to hear from impact coach, Robyn Eckersley, about how she tends to the values of her own personality and ultimately, what she stands for. We'd love to see you do the same! Discover how to groom down your have-to's to only the necessary and then fill your life up with get-to's so that you are aligned with your passions and being fueled along the way.
Cory Ravize shares her understanding of what it means to speak up for oneself and be a champion of experience during this day and age. She also encourages us to be a friend and look for that network of care to seek solid understanding. Whether you're in a season or lifetime of have/have-not, know that we're here to listen as well as impart our own stories and thereby bridge gaps and bring insight.
Diana Collins joins us to discuss slowing down, being present and noticing memorable details as a way of appreciating and valuing life. Please see The Always with Me Foundation and her work with new mothers experiencing Postpartum Depression.
Katie Draznin of @_thejourneywithin_ lets us in on her experiences with fear. From an eating disorder in high school to clearing out material possessions and traveling the world, to her fear of success and how that continues to impact her life. Katie has lots of good insight to share. So, hop in that driver's seat and take control of what you can manage, starting with a little inspiring conversation. Thanks for tuning in!
Alice Vo Edwards, PhD student in the making, addresses ADHD as it has impacted her and her family. She describes the solution she's found as an academic planner created by her and her daughter. Local to Las Vegas, she and Sara Paye have a casual interview at Women's Coworking Space Bloom where they first met. Understanding ADHD not only helps those with this specific diagnosis, it helps others accept themselves as they are as well. Remember, sometimes you just gotta "shake it off."


Photo: Andy Churchill, chairman, Churchill Drilling Tools.
LONDON -- A major UAE operator has recovered from stuck pipe by severing its drill string in just 2.5 hr, reports Churchill Drilling Tools, a global oilfield service company specializing in drilling innovation.
Churchill's HyPR HoleSaver, the world's first hydraulic pipe recovery system, was activated on a well offshore of the UAE on March 16, after the BHA became stuck at 9,070 ft due to a pack-off in a challenging formation.
However, the operator had placed a HyPR HoleSaver sub in its string as contingency against stuck pipe. Activating Churchill's DAV MX CircSub, the operator first regained circulation and well control. The HyPR HoleSaver Dart was subsequently dropped and pumped to redirect the flow of mud through the dart's ports creating a high velocity stream of fluid to hydraulically sever the string. After 2.5 hr of pumping at 550 gpm the operator applied some torque and the string parted with ease.
Avoiding the need for explosives, chemicals, or indeed any additional equipment or rig personnel, the operator recovered 8,335 ft of challenging hole, and was able to begin sidetrack operations shortly afterwards.
Churchill Drilling Tools' Chairman Andy Churchill said, "The team did a great job in optimizing the configuration and subsequently supporting the operator to get out of hole quickly and safely. Despite the simplicity of the system, it's important for operators to know that we're on hand to review and assist with their strategy and its execution.


text:
'use strict';

/**
 * A Tide Query helper class that checks whether a pr is covered by the query.
 */
class TideQuery {
    constructor(query) {
        this.repos = query.repos;
        this.orgs = query.orgs;
        this.labels = query.labels;
        this.missingLabels = query.missingLabels;
    }

  /**
   * Returns true if the pr is covered by the query.
   * @param pr
   * @returns {boolean}
   */
  matchPr(pr) {
        let isMatched = false;
        if (this.repos) {
            isMatched |= this.repos.indexOf(pr.Repository.NameWithOwner) !== -1;
        } else if (this.orgs) {
            isMatched |= this.orgs.indexOf(pr.Repository.Owner.Login) !== -1;
        }
        return isMatched;
    }

  /**
   * Returns labels and missing labels of the query.
   * @returns {{labels: string[], missingLabels: string[]}}
   */
  getQuery() {
        return {
            labels: this.labels,
            missingLabels: this.missingLabels
        }
    }
}

/**
 * Submit the query by redirecting the page with the query and let window.onload
 * sends the request.
 * @param {Element} input query input element
 */
function submitQuery(input) {
    const query = getPRQuery(input.value);
    input.value = query;
    window.location.search = '?query=' + encodeURIComponent(query);
}

/**
 * Creates a XMLHTTP request to /pr-data.js.
 * @param {function} fulfillFn
 * @param {function} errorHandler
 * @return {XMLHttpRequest}
 */
function createXMLHTTPRequest(fulfillFn, errorHandler) {
    const request = new XMLHttpRequest();
    const url = "/pr-data.js";
    request.onreadystatechange = () => {
        if (request.readyState === 4 && request.status === 200) {
            fulfillFn(request);
        }
    };
    request.onerror = () => {
        errorHandler();
    };
    request.withCredentials = true;
    request.open("POST", url, true);
    request.setRequestHeader("Content-type", "application/x-www-form-urlencoded");

    return request;
}

/**
 * Makes sure the search query is looking for pull requests by dropping all
 * is:issue and type:pr tokens and adds is:pr if does not exist.
 * @param {string} q
 * @return {string}
 */
function getPRQuery(q) {
    const tokens = q.replace(/\+/g, " ").split(" ");
    // Firstly, drop all pr/issue search tokens
    let result = tokens.filter(tkn => {
        tkn = tkn.trim();
        return !(tkn === "is:issue" || tkn === "type:issue" || tkn === "is:pr"
            || tkn === "type:pr");
    }).join(" ");
    // Returns the query with is:pr to the start of the query
    result = "is:pr " + result;
    return result;
}

/**
 * Redraw the page
 * @param {Object} prData
 */
function redraw(prData) {
    const mainContainer = document.querySelector("#main-container");
    while (mainContainer.firstChild) {
        mainContainer.removeChild(mainContainer.firstChild);
    }
    if (prData && prData.Login) {
        loadPrStatus(prData);
    } else {
        forceGithubLogin();
    }
}

/**
 * Enables/disables the progress bar.
 * @param {boolean} isStarted
 */
function loadProgress(isStarted) {
    const pg = document.querySelector("#loading-progress");
    if (isStarted) {
        pg.classList.remove("hidden");
    } else {
        pg.classList.add("hidden");
    }
}

/**
 * Handles the URL query on load event.
 */
function onLoadQuery() {
    const query = window.location.search.substring(1);
    const params = query.split("&");
    if (!params[0]) {
        return "";
    }
    const val = params[0].slice("query=".length);
    if (val && val !== "") {
        return decodeURIComponent(val.replace(/\+/g, ' '));
    }
    return "";
}

/**
 * Gets cookie by its name.
 * @param {string} name
 */
function getCookieByName(name) {
    if (!document.cookie) {
        return "";
    }
    const cookies = decodeURIComponent(document.cookie).split(";");
    for (let i = 0; i < cookies.length; i++) {
        const c = cookies[i].trim();
        const pref = name + "=";
        if (c.indexOf(pref) === 0) {
            return c.slice(pref.length);
        }
    }
    return "";
}

window.onload = () => {
    document.querySelectorAll("dialog").forEach((dialog) => {
        dialogPolyfill.registerDialog(dialog);
        dialog.querySelector('.close').addEventListener('click', () => {
            dialog.close();
        });
    });
    // Check URL, if the search is empty, adds search query by default format
    // ?is:pr state:open query="author:<user_login>"
    if (window.location.search === "") {
        const login = getCookieByName("github_login");
        const searchQuery = "is:pr state:open " + "author:" + login;
        window.location.search = "?query=" + encodeURIComponent(searchQuery);
    }
    const request = createXMLHTTPRequest((request) => {
        const prData = JSON.parse(request.responseText);
        redraw(prData);
        loadProgress(false);
    }, () => {
        loadProgress(false);
        const mainContainer = document.querySelector("#main-container");
            mainContainer.appendChild(createMessage("Something wrongs! We could not fulfill your request"));
    });
    loadProgress(true);
    request.send("query=" + onLoadQuery());
};

function createSearchCard() {
    const searchCard = document.createElement("DIV");
    searchCard.id = "search-card";
    searchCard.classList.add("pr-card", "mdl-card");

    // Input box
    const input = document.createElement("TEXTAREA");
    input.id = "search-input";
    input.value = decodeURIComponent(window.location.search.slice("query=".length + 1));
    input.rows = 1;
    input.spellcheck = false;
    input.addEventListener("keydown", (event) => {
        if (event.keyCode === 13) {
            event.preventDefault();
            submitQuery(input);
        } else {
            const el = event.target;
            el.style.height  = "auto";
            el.style.height = event.target.scrollHeight + "px";
        }
    });
    input.addEventListener("focus", (event) => {
        const el = event.target;
        el.style.height  = "auto";
        el.style.height = event.target.scrollHeight + "px";
    });
    // Refresh button
    const refBtn = createIcon("refresh", "Reload the query", ["search-button"], true);
    refBtn.addEventListener("click", () => {
        submitQuery(input);
    }, true);
    const userBtn = createIcon("person", "Show my open pull requests", ["search-button"], true);
    userBtn.addEventListener("click", () => {
        const login = getCookieByName("github_login");
        const searchQuery = "is:pr state:open " + "author:" + login;
        window.location.search = "?query=" + encodeURIComponent(searchQuery);
    });

    const actionCtn = document.createElement("DIV");
    actionCtn.id = "search-action";
    actionCtn.appendChild(userBtn);
    actionCtn.appendChild(refBtn);

    const inputContainer = document.createElement("DIV");
    inputContainer.id = "search-input-ctn";
    inputContainer.appendChild(input);
    inputContainer.appendChild(actionCtn);

    const title = document.createElement("H6");
    title.textContent = "Github search query";
    const infoBtn = createIcon("info", "More information about the search query", ["search-info"], true);
    const titleCtn = document.createElement("DIV");
    titleCtn.appendChild(title);
    titleCtn.appendChild(infoBtn);
    titleCtn.classList.add("search-title");

    const searchDialog = document.querySelector("#search-dialog");
    infoBtn.addEventListener("click", () => {
        searchDialog.showModal();
    });

    searchCard.appendChild(titleCtn);
    searchCard.appendChild(inputContainer);
    return searchCard;
}

/**
 * GetFullPRContexts gathers build jobs and pr contexts. It firstly takes
 * all pr contexts and only replaces contexts that have existing Prow Jobs. Tide
 * context will be omitted from the list.
 * @param builds
 * @param contexts
 * @returns {Array}
 */
function getFullPRContext(builds, contexts) {
    const contextMap = new Map();
    if (contexts) {
        for (let context of contexts) {
            if (context.Context === "tide") {
                continue;
            }
            contextMap.set(context.Context, {
                context: context.Context,
                description: context.Description,
                state: context.State.toLowerCase(),
                discrepancy: null,
        });
      }
    }
    if (builds) {
        for (let build of builds) {
            let discrepancy = null;
            // If Github context exits, check if mismatch or not.
            if (contextMap.has(build.context)) {
                const githubContext = contextMap.get(build.context);
                // TODO (qhuynh96): ProwJob's states and Github contexts states
                // are not equivalent in some states.
                if (githubContext.state !== build.state) {
                    discrepancy = "Github context and Prow Job states mismatch";
                }
            }
            contextMap.set(build.context, {
                context: build.context,
                description: build.description,
                state: build.state,
                url: build.url,
                discrepancy: discrepancy
            });
        }
    }
    const fullContexts = [];
    for (let value of contextMap.values()) {
        fullContexts.push(value);
    }
    return fullContexts;
}

/**
 * Loads Pr Status
 */
function loadPrStatus(prData) {
    const tideQueries = [];
    for (let query of tideData.TideQueries) {
        tideQueries.push(new TideQuery(query));
    }

    const container = document.querySelector("#main-container");
    container.appendChild(createSearchCard());
    if (!prData.PullRequestsWithContexts || prData.PullRequestsWithContexts.length === 0) {
        const msg = createMessage("No open PRs found", "");
        container.appendChild(msg);
        return;
    }
    for (let prWithContext of prData.PullRequestsWithContexts) {
        // There might be multiple runs of jobs for a build.
        // allBuilds is sorted with the most recent builds first, so
        // we only need to keep the first build for each job name.
        let pr = prWithContext.PullRequest;
        let seenJobs = {};
        let builds = [];
        for (let build of allBuilds) {
            if (build.type === 'presubmit' &&
                build.repo === pr.Repository.NameWithOwner &&
                build.base_ref === pr.BaseRef.Name &&
                build.number === pr.Number &&
                build.pull_sha === pr.HeadRefOID) {
                if (!seenJobs[build.job]) {  // First (latest) build for job.
                    seenJobs[build.job] = true;
                    builds.push(build);
                }
            }
        }
        const githubContexts = prWithContext.Contexts;
        const contexts = getFullPRContext(builds, githubContexts);
        const validQueries = [];
        for (let query of tideQueries) {
           if (query.matchPr(pr)) {
               validQueries.push(query.getQuery());
           }
        }
        container.appendChild(createPRCard(pr, contexts, validQueries, tideData.Pools));
    }
}

/**
 * Creates Pool labels.
 * @param pr
 * @param tidePool
 * @return {Element}
 */
function createTidePoolLabel(pr, tidePool) {
    if (!tidePool || tidePool.length === 0) {
        return null;
    }
    const poolTypes = [tidePool.Target, tidePool.BatchPending,
        tidePool.SuccessPRs, tidePool.PendingPRs, tidePool.MissingPRs];
    const inPoolId = poolTypes.findIndex(poolType => {
        if (!poolType) {
            return false;
        }
        const index = poolType.findIndex(prInPool => {
            return prInPool.Number === pr.Number;
        });
        return index !== -1;
    });
    const label = document.createElement("SPAN");
    if (inPoolId === -1) {
        return null;
    }
    const labelTitle = ["Merging", "In Batch & Test Pending",
        "Test Passing & Merge Pending", "Test Pending",
        "Test failed/Missing Labels"];
    const labelStyle = ["merging", "batching", "passing", "pending", "failed"];
    label.textContent = "In Pool - " + labelTitle[inPoolId];
    label.classList.add("title-label", "mdl-shadow--2dp", labelStyle[inPoolId]);

    return label;
}

/**
 * Creates a label for the title. It will prioritise the merge status over the
 * job status. Saying that, if the pr has jobs failed and does not meet merge
 * requirements, it will show that the PR needs to resolve labels.
 * @param isMerge {boolean}
 * @param jobStatus {string}
 * @param mergeAbility {number}
 * @return {Element}
 */
function createTitleLabel(isMerge, jobStatus, mergeAbility) {
    const label = document.createElement("SPAN");
    label.classList.add("title-label");
    if (isMerge) {
        label.textContent = "Merged";
        label.classList.add("merging");
    } else if (mergeAbility === -1) {
        label.textContent = "Unknown Merge Requirements";
        label.classList.add("unknown");
    } else if (mergeAbility === 0) {
        label.textContent = "Needs to Resolve Labels";
        label.classList.add("pending");
    } else {
        if (jobStatus === "succeeded") {
            label.textContent = "Good to be merged";
            label.classList.add(jobStatus);
        } else {
            label.textContent = "Jobs " + jobStatus;
            label.classList.add(jobStatus);
        }
    }

    return label;
}

/**
 * Creates PR Card title.
 * @param {Object} pr
 * @param {Array<Object>} tidePools
 * @param {string} jobStatus
 * @param {number} mergeAbility
 * @return {Element}
 */
function createPRCardTitle(pr, tidePools, jobStatus, mergeAbility) {
    const prTitle = document.createElement("DIV");
    prTitle.classList.add("mdl-card__title");

    const title = document.createElement("H4");
    title.textContent = "#" + pr.Number;
    title.classList.add("mdl-card__title-text");

    const subtitle = document.createElement("H5");
    subtitle.textContent = pr.Repository.NameWithOwner;
    subtitle.classList.add("mdl-card__subtitle-text");

    const link = document.createElement("A");
    link.href = "https://github.com/" + pr.Repository.NameWithOwner + "/pull/"
        + pr.Number;
    link.appendChild(title);

    const prTitleText = document.createElement("DIV");
    prTitleText.appendChild(link);
    prTitleText.appendChild(subtitle);
    prTitleText.classList.add("pr-title-text");
    prTitle.appendChild(prTitleText);

    const pool = tidePools.filter(pool => {
        const repo = pool.Org + "/" + pool.Repo;
        return pr.Repository.NameWithOwner === repo && pr.BaseRef.Name
            === pool.Branch;
    });
    let tidePoolLabel = createTidePoolLabel(pr, pool[0]);
    if (!tidePoolLabel) {
        tidePoolLabel = createTitleLabel(pr.Merged, jobStatus, mergeAbility);
    }
    prTitle.appendChild(tidePoolLabel);

    return prTitle;
}

/**
 * Creates a list of contexts.
 * @param contexts
 * @param itemStyle
 * @return {Element}
 */
function createContextList(contexts, itemStyle = []) {
    const container = document.createElement("UL");
    container.classList.add("mdl-list", "job-list");
    const getStateIcon = (state) => {
        switch (state) {
            case "success":
                return "check_circle";
            case "failure":
                return "error";
            case "pending":
                return "watch_later";
            case "triggered":
                return "schedule";
            case "aborted":
                return "remove_circle";
            case "error":
                return "warning";
            default:
                return "";
        }
    };
    const getItemContainer = (context) => {
        if (context.url) {
            const item = document.createElement("A");
            item.href = context.url;
            return item;
        } else {
            return document.createElement("DIV");
        }
    };
    contexts.forEach(context => {
        const elCon = document.createElement("LI");
        elCon.classList.add("mdl-list__item", "job-list-item", ...itemStyle);
        const item = getItemContainer(context);
        item.classList.add("mdl-list__item-primary-content");
        item.appendChild(createIcon(
            getStateIcon(context.state),
            "",
            ["state", context.state, "mdl-list__item-icon"]));
        item.appendChild(document.createTextNode(context.context));
        if (context.discrepancy) {
            item.appendChild(createIcon(
                "warning",
                context.discrepancy,
                ["state", "context-warning", "mdl-list__item-icon"]));
        }
        elCon.appendChild(item);
        if (context.description) {
            const itemDesc = document.createElement("SPAN");
            itemDesc.textContent = context.description;
            itemDesc.style.color = "grey";
            itemDesc.style.fontSize = "14px";
            elCon.appendChild(itemDesc);
        }
        container.appendChild(elCon);
    });
    return container;
}

/**
 * Creates Job status.
 * @param builds
 * @return {Element}
 */
function createJobStatus(builds) {
    const statusContainer = document.createElement("DIV");
    statusContainer.classList.add("status-container");
    const status = document.createElement("DIV");
    const failedJobs = builds.filter(build => {
        return build.state === "failure";
    });
    // Job status indicator
    const state = jobStatus(builds);
    let statusText = "";
    let stateIcon = "";
    switch (state) {
        case "succeeded":
            statusText = "All tests passed";
            stateIcon = "check_circle";
            break;
        case "failed":
            statusText = failedJobs.length + " test" + (failedJobs.length === 1 ? "" : "s") + " failed";
            stateIcon = "error";
            break;
        case "unknown":
            statusText = "No test found";
            break;
        default:
            statusText = "Tests are running";
            stateIcon = "watch_later";
    }
    const arrowIcon = createIcon("expand_more");
    arrowIcon.classList.add("arrow-icon");
    if (state === "unknown") {
        arrowIcon.classList.add("hidden");
        const p = document.createElement("P");
        p.textContent = "Test results for this PR are not in our record but you can always find them on PR's GitHub page. Sorry for any inconvenience!";

        status.appendChild(document.createTextNode(statusText));
        status.appendChild(createStatusHelp("No test found", [p]));
        status.classList.add("no-status");
    } else {
        status.appendChild(createIcon(stateIcon, "", ["status-icon", state]));
        status.appendChild(document.createTextNode(statusText));
    }
    status.classList.add("status");
    statusContainer.appendChild(status);
    // Job list
    let failedJobsList;
    if (failedJobs.length > 0) {
        failedJobsList = createContextList(failedJobs);
        statusContainer.appendChild(failedJobsList);
    }
    const jobList = createContextList(builds);
    jobList.classList.add("hidden");
    status.addEventListener("click", () => {
        if (state === "unknown") {
            return;
        }
        if (failedJobsList) {
            failedJobsList.classList.add("hidden");
        }
        jobList.classList.toggle("hidden");
        arrowIcon.textContent = arrowIcon.textContent === "expand_more"
            ? "expand_less" : "expand_more";
    });

    status.appendChild(arrowIcon);
    statusContainer.appendChild(jobList);
    return statusContainer;
}

/**
 * Creates a merge requirement cell.
 * @param labels
 * @param notMissingLabel
 * @return {Element}
 */
function createMergeLabelCell(labels, notMissingLabel = false) {
    const cell = document.createElement("TD");
    labels.forEach(label => {
        const labelEl = document.createElement("SPAN");
        const name = label.name.split(" ").join("");
        labelEl.classList.add("merge-table-label", "mdl-shadow--2dp", "label",
            name);
        labelEl.textContent = label.name;
        const toDisplay = label.own ^ notMissingLabel;
        if (toDisplay) {
            cell.appendChild(labelEl);
        }
    });

    return cell;
}

function processLabelName(label) {
    label = label.split(" ").join("");
    if (label.startsWith("area/")) {
        return "area";
    } else if (label.startsWith("size/")) {
        return label.slice(5);
    } else {
        return label;
    }
}

/**
 * Appends labels to a container
 * @param {Element} container
 * @param {Array<string>} labels
 */
function appendLabelsToContainer(container, labels) {
    while (container.firstChild) {
        container.removeChild(container.firstChild);
    }
    labels.forEach(label => {
        const labelEl = document.createElement("SPAN");

        let labelName = processLabelName(label);
        labelEl.classList.add("merge-table-label", "mdl-shadow--2dp", "label", labelName);
        labelEl.textContent = label;
        container.appendChild(labelEl);
    });
}

/**
 * Creates merge requirement table for queries.
 * @param prLabels
 * @param queries
 * @return {Element}
 */
function createQueriesTable(prLabels, queries) {
    const table = document.createElement("TABLE");
    table.classList.add("merge-table");
    const thead = document.createElement("THEAD");
    const allLabelHeaderRow = document.createElement("TR");
    const allLabelHeaderCell = document.createElement("TD");
    // Creates all pr labels header.
    allLabelHeaderCell.textContent = "PR's Labels";
    allLabelHeaderCell.colSpan = 3;
    allLabelHeaderRow.appendChild(allLabelHeaderCell);
    thead.appendChild(allLabelHeaderRow);

    const allLabelRow = document.createElement("TR");
    const allLabelCell = document.createElement("TD");
    allLabelCell.colSpan = 3;
    appendLabelsToContainer(allLabelCell, prLabels.map(label => {
        return label.Label.Name;
    }));
    allLabelRow.appendChild(allLabelCell);
    thead.appendChild(allLabelRow);

    const tableRow = document.createElement("TR");
    const col1 = document.createElement("TD");
    col1.textContent = "Required Labels (Missing)";
    const col2 = document.createElement("TD");
    col2.textContent = "Forbidden Labels (Shouldn't have)";
    const col3 = document.createElement("TD");

    const body = document.createElement("TBODY");
    queries.forEach(query => {
        const row = document.createElement("TR");
        row.append(createMergeLabelCell(query.labels, true));
        row.append(createMergeLabelCell(query.missingLabels));

        const mergeIcon = document.createElement("TD");
        mergeIcon.classList.add("merge-table-icon");
        const iconButton = createIcon("information", "Clicks to see query details", [], true);
        mergeIcon.appendChild(iconButton);
        row.appendChild(mergeIcon);

        body.appendChild(row);
        const dialog = document.querySelector("#query-dialog");
        const allRequired = document.querySelector("#query-all-required");
        const allForbidden = document.querySelector("#query-all-forbidden");
        iconButton.addEventListener("click", () => {
            appendLabelsToContainer(allRequired, query.labels.map(label => {
                return label.name;
            }));
            appendLabelsToContainer(allForbidden, query.missingLabels.map(label => {
                return label.name;
            }));
            dialog.showModal();
        });
    });

    tableRow.appendChild(col1);
    tableRow.appendChild(col2);
    tableRow.appendChild(col3);
    thead.appendChild(tableRow);
    table.appendChild(thead);
    table.appendChild(body);

    return table;
}

/**
 * Creates the merge requirement status.b
 * @param prLabels
 * @param queries
 * @return {Element}
 */
function createMergeStatus(prLabels, queries) {
    prLabels = prLabels ? prLabels : [];
    const statusContainer = document.createElement("DIV");
    statusContainer.classList.add("status-container");
    const status = document.createElement("DIV");
    const mergeAbility = isAbleToMerge(queries);
    if (mergeAbility === 0) {
        status.appendChild(createIcon("error", "", ["status-icon", "failed"]));
        status.appendChild(document.createTextNode("Does not meet merge requirements"));
        // Creates help button
        const iconButton = createIcon("help", "", ["help-icon-button"], true);
        status.appendChild(iconButton);
        // Shows dialog
        const dialog = document.querySelector("#merge-help-dialog");
        iconButton.addEventListener("click", (event) => {
            dialog.showModal();
            event.stopPropagation();
        });
    } else if (mergeAbility === 1) {
        status.appendChild(createIcon("check_circle", "", ["status-icon", "succeeded"]));
        status.appendChild(document.createTextNode("Meets merge requirements"));
    } else {
        status.appendChild(document.createTextNode("No Tide query found"));
        status.classList.add("no-status");
        const p = document.createElement("P");
        p.textContent = "This repo may not be configured to use Tide.";
        status.appendChild(createStatusHelp("Tide query not found", [p]));
    }
    const arrowIcon= createIcon("expand_less");
    arrowIcon.classList.add("arrow-icon");

    status.classList.add("status");
    status.appendChild(arrowIcon);

    const queriesTable = createQueriesTable(prLabels, queries);
    if (mergeAbility !== 0) {
        queriesTable.classList.add("hidden");
        arrowIcon.textContent = "expand_more";
    }
    status.addEventListener("click", () => {
        queriesTable.classList.toggle("hidden");
        if (queriesTable.classList.contains("hidden")) {
            const offLabels = queriesTable.querySelectorAll(
                ".merge-table-label.off");
            offLabels.forEach(offLabel => {
                offLabel.classList.add("hidden");
            });
        }
        arrowIcon.textContent = arrowIcon.textContent === "expand_more"
            ? "expand_less" : "expand_more";
    });

    statusContainer.appendChild(status);
    statusContainer.appendChild(queriesTable);
    return statusContainer;
}

/**
 * Creates a help button on the status.
 * @param {string} title
 * @param {Array<Element>} content
 * @return {Element}
 */
function createStatusHelp(title, content) {
    const dialog = document.querySelector("#status-help-dialog");
    const dialogTitle = dialog.querySelector(".mdl-dialog__title");
    const dialogContent = dialog.querySelector(".mdl-dialog__content");
    const helpIcon = createIcon("help", "", ["help-icon-button"], true);
    helpIcon.addEventListener("click", (event) => {
        dialogTitle.textContent = title;
        while (dialogContent.firstChild) {
            dialogContent.removeChild(dialogContent.firstChild);
        }
        content.forEach(el => {
            dialogContent.appendChild(el);
        });
        dialog.showModal();
        event.stopPropagation();
    });

    return helpIcon;
}

function createPRCardBody(pr, builds, queries) {
    const cardBody = document.createElement("DIV");
    const title = document.createElement("H3");
    title.textContent = pr.Title;

    cardBody.classList.add("mdl-card__supporting-text");
    cardBody.appendChild(title);
    cardBody.appendChild(createJobStatus(builds));
    const nodes = pr.Labels && pr.Labels.Nodes ? pr.Labels.Nodes : [];
    cardBody.appendChild(createMergeStatus(nodes, queries));

    return cardBody;
}

/**
 * Compare function that prioritizes jobs which are in failure state.
 * @param a
 * @param b
 * @return {number}
 */
function compareJobFn(a, b) {
    const stateToPrio = [];
    stateToPrio["success"] = stateToPrio["expected"] = 3;
    stateToPrio["aborted"] = 2;
    stateToPrio["pending"] = stateToPrio["triggered"] = 1;
    stateToPrio["error"] = stateToPrio["failure"] = 0;

    return stateToPrio[a.state] > stateToPrio[b.state] ? 1
        : stateToPrio[a.state] < stateToPrio[b.state] ? -1 : 0;
}

/**
 * Creates a PR card.
 * @param {Object} pr
 * @param {Array<Object>} builds
 * @param {Array<Object>} queries
 * @param {Array<Object>} tidePools
 * @return {Element}
 */
function createPRCard(pr, builds = [], queries = [], tidePools = []) {
    builds = builds ? builds : [];
    queries = queries ? queries : [];
    tidePools = tidePools ? tidePools : [];
    const prCard = document.createElement("DIV");
    // jobs need to be sorted from high priority (failure, error) to low
    // priority (success)
    builds.sort(compareJobFn);
    const prLabelsSet = new Set();
    if (pr.Labels && pr.Labels.Nodes) {
        pr.Labels.Nodes.forEach(label => {
            prLabelsSet.add(label.Label.Name);
        });
    }
    const processedQuery = [];
    queries.forEach(query => {
        let score = 0.0;
        const labels = [];
        const missingLabels = [];
        query.labels.sort((a, b) => {
            if (a.length === b.length) {
                return 0;
            }
            return a.length < b.length ? -1 : 1;
        });
        query.missingLabels.sort((a, b) => {
            if (a.length === b.length) {
                return 0;
            }
            return a.length < b.length ? -1 : 1;
        });
        query.labels.forEach(label => {
            labels.push({name: label, own: prLabelsSet.has(label)});
            score += labels[labels.length - 1].own ? 1 : 0;
        });
        query.missingLabels.forEach(label => {
            missingLabels.push({name: label, own: prLabelsSet.has(label)});
            score += missingLabels[missingLabels.length - 1].own ? 0 : 1;
        });
        score = (labels.length + missingLabels.length > 0) ? score
            / (labels.length + missingLabels.length) : 1.0;
        processedQuery.push(
            {score: score, labels: labels, missingLabels: missingLabels});
    });
    // Sort queries by descending score order.
    processedQuery.sort((q1, q2) => {
        if (Math.abs(q1.score - q2.score) < Number.EPSILON) {
            return 0;
        }
        return q1.score > q2.score ? -1 : 1;
    });
    prCard.classList.add("pr-card", "mdl-card");
    prCard.appendChild(createPRCardTitle(pr, tidePools, jobStatus(builds), isAbleToMerge(processedQuery)));
    prCard.appendChild(createPRCardBody(pr, builds, processedQuery));
    return prCard;
}

/**
 * Redirect to initiate github login flow.
 */
function forceGithubLogin() {
	window.location.href = window.location.origin + "/github-login";
}

/**
 * Returns the job status based on its state.
 * @param builds
 * @return {string}
 */
function jobStatus(builds) {
    if (builds.length === 0) {
        return "unknown";
    }
    switch (builds[0].state) {
        case "success":
        case "expected":
            return "succeeded";
        case "failure":
        case "error":
            return "failed";
        default:
            return "pending";
    }
}

/**
 * Returns -1 if there is no query. 1 if the PR is able to be merged by checking
 * the score of the first query in the query list (score === 1), the list has
 * been sorted by scores, otherwise 0.
 * @param queries
 * @return {number}
 */
function isAbleToMerge(queries) {
    if (queries.length === 0) {
        return -1;
    }
    return Math.abs(queries[0].score - 1.0) < Number.EPSILON ? 1 : 0;
}

/**
 * Returns an icon element.
 * @param {string} iconString icon name
 * @param {string} tooltip tooltip string
 * @param {Array<string>} styles
 * @param {boolean} isButton
 * @return {Element}
 */
function createIcon(iconString, tooltip = "", styles = [], isButton = false) {
    const icon = document.createElement("I");
    icon.classList.add("icon-button", "material-icons");
    icon.textContent = iconString;
    if (tooltip !== "") {
        icon.title = tooltip;
    }
    if (!isButton) {
        icon.classList.add(...styles);
        return icon;
    }
    const container = document.createElement("BUTTON");
    container.appendChild(icon);
    container.classList.add("mdl-button", "mdl-js-button", "mdl-button--icon",
        ...styles);

    return container;
}

/**
 * Create a simple message with an icon.
 * @param msg
 * @param icStr
 * @return {HTMLElement}
 */
function createMessage(msg, icStr) {
    const el = document.createElement("H3");
    el.textContent = msg;
    if (icStr !== "") {
        const ic = createIcon(icStr, "", ["message-icon"]);
        el.appendChild((ic));
    }
    const msgContainer = document.createElement("DIV");
    msgContainer.appendChild(el);
    msgContainer.classList.add("message");

    return msgContainer;
}

document.addEventListener("DOMContentLoaded", function(event) {
   configure();
});

function configure() {
    if (!branding){
        return;
    }
    if (branding.logo !== '') {
        document.getElementById('img').src = branding.logo;
    }
    if (branding.favicon !== '') {
        document.getElementById('favicon').href = branding.favicon;
    }
    if (branding.background_color !== '') {
        document.body.style.background = branding.background_color;
    }
    if (branding.header_color !== '') {
        document.getElementsByTagName('header')[0].style.backgroundColor = branding.header_color;
    }
}

redpajama_set_name: RedPajamaGithub