## 4 Evaluation
### Stash Size
#### 4.3.2 Main ORAM  
The analysis of stash size in the main ORAM could follow the idea proposed by Path ORAM [13]. Similar to the posMap ORAM, \(\mathit{ORAM}_{\infty}^{M,L}\) is defined in which the bucket size is infinite and \(\mathit{ORAM}_{Z}^{M,L}\) is defined in which the bucket size is \(Z\). First, the states of \(\mathit{ORAM}_{Z}^{M,L}\) and \(\mathit{ORAM}_{\infty}^{M,L}\) after a post-process algorithm are discussed. Then, the overflow probability of \(\mathit{ORAM}_{Z}^{M,L}\) is analyzed. Afterwards, the influence of access sequence on the stash size is analyzed. Finally, the bound of stash size is calculated. Let \(b_{\infty}\) be a bucket in \(\mathit{ORAM}_{\infty}^{M,L}\) and \(b_{Z}\) be a bucket in \(\mathit{ORAM}_{Z}^{M,L}\). Suppose \(\mathit{ORAM}_{\infty}^{M,L}\) and \(\mathit{ORAM}_{Z}^{M,L}\) are running the same access sequence with the same randomness. A post-process of \(\mathit{ORAM}_{\infty}^{M,L}\) is carried out as follows. The buckets involved in ORAM Write are visited one-by-one. At time stamp \(i\), if \(b_{\infty,i}\) has more blocks than \(b_{Z,i}\), the extra blocks are stored in the client. If \(b_{\infty,i}\) has less blocks than \(b_{Z,i}\), the blocks which do not reside in \(b_{\infty,i}\) must be stored in the client. Then, these less blocks are stored in \(b_{\infty,i}\). Therefore, the state of \(\mathit{ORAM}_{\infty}^{M,L}\) after post-process is identical to \(\mathit{ORAM}_{Z}^{M,L}\). Let \(T\) represents a sequence of buckets randomly chosen by ORAM Writes in \(\mathit{ORAM}_{\infty}^{M,L}\), \(X(T)\) denote the number of fresh blocks in \(T\), and \(n(T)\) denote the number of buckets in \(T\). **Lemma 1**. : _The \(\mathit{MStash}\) size is more than \(R\) if and only if there exists a sequence of buckets \(T\) such that \(X(T)\)\(>\)\(Z\):\(n(T)\)+\(R\)._  
If there exists a sequence of buckets \(T\) such that \(X(T)\)\(>\)\(Z\)-\(n(T)\)+\(R\), then the client storage generated by post-process of \(\mathit{ORAM}_{\infty}^{M,L}\) is larger than \(R\). As the \(\mathit{MStash}\) has the same state with the client storage generated by post-process of \(\mathit{ORAM}_{\infty}^{M,L}\), the \(\mathit{MStash}\) size in \(\mathit{ORAM}_{Z}^{M,L}\) is also larger than \(R\). Otherwise, the \(\mathit{MStash}\) size is no more than \(R\). For \(n\) buckets, it contains the most numbers of \(n(n\)+1)/2 sequences mentioned in Lemma 1. By using a union bound, we have  
\[ \begin{array}{ll}\Pr[\mathit{MStash}\geq R]=&\Pr[\exists T\in\mathit{ORAM}_ {\infty}^{L},X(T)\geq Z\cdot n(T)+R]\\ &<\sum\limits_{n\geq 1}n(n+1)/2\max\limits_{T:n(T)=n}\Pr[X(T)\geq Z \cdot n(T)+R]\end{array}  \tag{2}\]  
**Lemma 2**. : _For all access sequences constructed by \(N\) blocks, the probability \(Pr[X(T)\geq Z\cdot n(T)+R]\) is maximized under the access sequence in which the logical address of each block only appears exactly once._ \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & & & & **(\(S\),\(A^{\prime}\))** & \\ \cline{2-5} \(\Lambda\) & **(3,1)** & **(4,3)** & **(5,4)** & **(6,5)** \\ \hline
40 & 15 & 32 & 33 & 34 \\
80 & 37 & 63 & 64 & 65 \\
128 & 67 & 91 & 93 & 94 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The bound of \(\mathit{PStash}\) with the overflow probability \(2^{-\lambda}\). Suppose there is a logical address in access sequence a that has been written twice. Then, there exists two indices i and j, i \(<\) j, such that \(\text{a}_{\text{i}}=\text{a}_{\text{j}}\). Let T be the sequence of buckets such that X(T) is maximized under sequence a. Without the j-th ORAM Write, X(T) remains the maximum. On the contrary, if there is no duplicated logical address in an access sequence, then the j-th logical address is distinct with other logical addresses. In the j-th ORAM Write, if the j-th logical block is stored in T, the maximum number of blocks in T becomes X(T) = X(T)+1, as the bucket size is infinite. Therefore, the access sequence in which each logical address only appears once maximizes the stash size.