# An Ordered Universal Accumulator Based on a Hash Chain
## 2 Background
### Definitions  
In Table 1, let \(negl:\mathbb{N}\rightarrow\mathbb{N}\) denote a negligible function; that is, for any positive polynomial \(p(\cdot)\) and any sufficiently large integer \(n\), there is \(negl(n)<1/p(n)\). \(||\) denotes the operation of concatenation between binary strings. If \(R(\cdot)\) is a randomized algorithm, then \(a\xleftarrow{R}(\cdot)\) denotes the process of choosing \(a\) according to the probability distribution induced by \(R\), and \(\langle R(\cdot)\rangle\) denotes the set of all possible values of \(a\) returned by \(R\) with positive probability. The proposed hash chain structure is shown in Figure 1, and its definition is as follows. **Definition 1** (Strong Universal Accumulators with Memory) [20]. : _Let \(M\) be a set of all values. For any set of elements to be accumulated, a strong universal accumulator can be represented by a five-tuple: \(\mathfrak{Acc}=(\)Setup, Witness, Belongs, Update, CheckUpdate\()\), where the following definitions apply:_  
1. _Setup:_ _Denotes a randomized algorithm for model construction. On the input of a security parameter_ \(k\in\mathbb{N}\)_, it outputs a data structure_ \(m_{0}\) _(the memory) and random accumulator initial value_ \(\mathfrak{Acc}_{0}\) _in the set_ \(Y=\{0,1\}^{k}\)_._
2. _Witness:_ _A randomized algorithm that, on the input_ \(x\in M\) _and memory_ \(m\)_, if_ \(x\in X\) _(element_ \(x\) _has been accumulated), outputs a membership witness_ \(w\)_; otherwise, if_ \(x\
otin X\)_, then it outputs a witness of non-membership._
3. _Belongs:_ _A randomized algorithm that, on the input_ \(x\in M\)_, witness_ \(w\)_, and accumulator value_ \(\mathfrak{Acc}\in Y\)_, outputs_ \(1\) _if_ \(w\) _is a valid witness of membership,_ \(0\) _if_ \(w\) _is a valid non-member witness, and_ \(\bot\) _if_ \(w\) _is an invalid witness._
4. _UPdate:_ _Denotes a randomized algorithm that updates the accumulator value after adding (_\(op=\)_add) or deleting (_\(op=\)_del) an element. Its input is an element_ \(x\in M\) _and an accumulator value and memory pair_ \((\mathfrak{Acc}_{bf},m_{bf})\)_, and then it outputs a new accumulator \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Symbols** & **Description** & **Symbols** & **Description** \\ \hline \(negl\) & A negligible function & \(w\) & A membership witness \\ \(H(\bullet)\) & A collision-resistant hash function & \(x\) & An accumulator element \\ \(\mathfrak{Acc}\) & Strong Universal Accumulators & \(d\) & The optimal group interval \\ \(HC\) & Hash chain structure & \(m\) & Memory \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Symbols and descriptions. Figure 1: Hash chain structure. value and memory pair \(\big{(}\mathfrak{Acc}_{af},m_{af}\big{)}\) and the witness of the update operation \(w_{op}\), where \(\mathfrak{Acc}_{bf}\) and \(\mathfrak{Acc}_{af}\) denote the accumulator values before and after the update, and the same is true for \(m_{bf}\) and \(m_{af}\). 5. _CheckUpdate:_ _A randomized algorithm that verifies the update operation. The algorithm takes an element_ \(x\in M\)_, a pair of accumulator values_ \(\left(\mathfrak{Acc}_{bf},\mathfrak{Acc}_{af}\right)\)_, and the witness of the update_ \(w_{op}\) _and then returns a bit value_ \(b\)_. The witness_ \(w_{op}\) _is valid if the output_ \(b=1\)_, and then the accumulator value after the update_ \(\mathfrak{Acc}_{af}\) _is valid. If_ \(b=0\) _is output, the witness_ \(w_{op}\) _and the accumulator value after the update_ \(\mathfrak{Acc}_{af}\) _is invalid._  
**Definition 2**. : _There exists a sequence \(\left(\mathfrak{Acc}_{i},x_{i},m_{i}\right)_{1\leq i\leq n}\) and \(\mathfrak{Acc}_{0}\), \(m_{0}\), where \(n=|X|\) and \(x_{i}\in M\) under the following conditions:_  
1. \(X=\left\{x_{i}\right\}_{1\leq i\leq n}\)_._
2. \(\left(\mathfrak{Acc}_{0},m_{0}\right)\in\langle Setup()\rangle\)_._
3.