## 4 Evaluation
### Stash Size
#### 4.3.2 Main ORAM
If the maximum of X(T) generated by the access sequence mentioned in Lemma 2 has an upper bound, _MStash_ is bounded. Let X\({}_{i}\)(T)\(\in\)[0,1] indicates whether the i-th accessed block is in T and \(\text{p}_{\text{i}}=\text{Pr}[\text{X}_{\text{i}}(\text{T})=1]\). As the uniform randomness, the probability that each bucket is chosen in ORAM Write is 1/N. For a N-length access sequence, we have E[X(T)] \(\leq\) n(T)-A. Since the logical address of each block is distinct, it means that X\({}_{i}\)(T), i = 0,..., N-1 are all statistically independent. According to Ring ORAM ([2], Section 4.3), the generate function of \(E[e^{tX(T)}]\) is bounded as \(e^{nA(e^{t-1})}\), where n = n(T) and t \(>\) 0. By the Markov Inequality, the Chernoff-bound on X(T) is  
\[ \begin{array}{ll}\Pr[X(T)\geq nZ+R]=&\Pr[e^{X(T)}\geq e^{nZ+R}]\\ &\leq E[e^{tX(T)}]\cdot e^{-t(nZ+R)}\leq e^{(e^{t}-1)An}\cdot e^{-t(nZ+R)}\\ &=\text{e}^{-tR}\cdot e^{-n(Zt-A(e^{t}-1))}\end{array}  \tag{3}\]  
From Equations (2) and (3), the probability that the size of MStash exceeds R is  
\[\Pr[MStash\geq R]\leq\sum_{n=1}n(n+1)/2\cdot e^{-tR}\cdot e^{-n(Zt-A(e^{t}-1))} <\sum_{n\geq 1}e^{-tR}\cdot e^{-n(Zt-A(e^{t}-1)-\ln 2)} \tag{4}\]  
The above inequality holds since n(n + 1)/2 \(\leq\) 2\({}^{\text{n}}\) when n\(\geq\)1. Let t = lnZ/A, as long as \(q=Z\ln Z/A-Z+A-\ln 2>0\), the overflow probability of _MStash_ is \((A/Z)^{R}\cdot e^{-q}\cdot(1-e^{-q})\), which decreases exponentially in its size R.  
The analysis shows that the size of _MStash_ only relies on parameters (\(Z\), \(A\)) and the number of blocks N has little influence on it. We simulate our scheme for a single long run. The access sequence is designed in a round-robin pattern from Lemma 2, i.e., {1,2,...,N,1,2,...}. In the initialization, we store number of \(N\) distinct data blocks to the main ORAM according to their logical addresses, e.g., block a is stored in \(\mathcal{M}_{\text{a}}\). We ran 2\({}^{25}\) logical writes and the first N logical writes were used to warm up the main ORAM to a steady state. The parameters (\(Z\),\(A\)) are set to (3, 1). Figure 2a shows the size of MStash under different \(N\). Four curves with different values of statistical security parameter \(\lambda\) are analyzed. Each curve represents the size of MStash by varying the number of blocks (\(N\)), which concludes that \(N\) has little impact on the size of MStash. Figure 2: (a) Maximum size of _MStash_ with the failure probability 2\({}^{-\lambda}\) under different \(N\); (b) Maximum size of _MStash_ with the failure probability 2\({}^{-\lambda}\) under different \((Z\), \(A)\), \(N=2^{15}\). By setting \(N=2^{15}\), Figure 2b plots the size of _MStash_ is no more than \(R\) with a failure probability \(2^{-\lambda}\). The two curves correspond to \((Z,\,A)=(3,\,1)\) and \((Z,\,A)=(4,\,2)\). Both curves are linear, which shows that the size of _MStash_ exceeds R with probability of \(2^{-\text{CR}}\), where \(c\) is a constant depending on \((Z,\,A)\). We have analyzed and evaluated the client storage required by both the main ORAM and posMap ORAM. The results show that the client storage required in posMap ORAM is \(\omega(log^{2}N)\) and the client storage required in main ORAM is \(O(B)\). Since \(B=\Omega(log^{2}N)\), the total client storage can be concluded as \(\omega(B)\). Table 3 compares the efficiency of CWORAM with those of the previous write-only ORAM schemes, as well as that of [PERSON]'s. For a logical write operation, the previous works have the minimum communication complexity \(O(BlogN)\). In CWORAM, since neither the recursive storage nor the ODS storage of position map is required, it achieves \(O(B)\) communication complexity if the size of blocks in the posMap is set to \(O(logN)\). For a logical read operation, the overhead of communication in CWORAM is the same with HiVE, i.e., \(O(B)\), which improves a factor of \(logN\) comparing to that in DetWoORM. Further, CWORAM brings a constant communication rounds which is the minimum rounds achieved by the previous works.