# An Ordered Universal Accumulator Based on a Hash Chain
## 3 Hash Chain Accumulator Scheme
### Scheme Structure  
Suppose that the set \(X\) to be accumulated is ordered, where the \(i\)-th element \(x_{i}\in X=\{x_{1},x_{2},\ldots,x_{n}\},n\in\mathbb{N}\). There is a collision-resistant hash function family \(\mathfrak{H}:K\times M\to Y\) containing many collision-resistant hash functions \(H\), where \(M\) is the set of all binary strings, \(Y\) denotes the set of \(\{0,1\}^{k}\), and \(k\in\mathbb{N}\) is a sufficiently large security parameter. This scheme constructs a strong universal accumulator with memory based on the hash chain, as follows. The scheme selects a proper \(k\in\mathbb{N}\) as a security parameter, and the set \(X=\{x_{1},x_{2},\ldots,x_{n}\}\) is a subset of \(M=\{0,1\}^{k}\). The memory \(m\) denotes the model of the set \(X\). The hash chain accumulator (HC) operation is defined as follows:1. **Setup**: A hash function randomly selected from the hash function family \(\mathfrak{H}\) is denoted by \(H\). Let the set of elements to be accumulated \(X\) be an empty set, and an initial value \(a\) is randomly selected. \(H(a)\) is used as the initial value of the hash chain after being computed by the collision-resistant hash function \(H\). 2. **Witness**: On the input \(x\in M\) and memory \(m\), the witness \(w=(w_{1},w_{2})\) is calculated. In the algorithm, if \(x\in X\), then it sets \(w_{1}=\left[\mathrm{H}_{0},\ldots,\mathrm{H}_{isd},\mathrm{H}_{(i+1)*d}, \ldots,\mathrm{H}_{n}\right]\) and \(w_{2}=\left[x_{isd},x_{isd+1},\ldots,x_{(i+1)*d}\right]\), where \(d\) denotes a proper interval. \(w_{1}\) represents hash chain nodes in \(d\) intervals. \(w_{2}\) is the set of elements between two hash chain nodes containing the element \(x\), \(w_{2}\subseteq X\). If \(x\
otin X\), \(w_{1}\) is not changed and \(w_{2}=\left[x_{isd},x_{isd+1},\ldots,x_{j},x_{k},\ldots,x_{(i+1)*d}\right]\), where \(x_{j}<x<x_{k}\) and \(\left(x_{j},x_{k}\right)\) are continuous elements in the set. 3. **Belongs**: On the input \(x\in M\), the witness \(w=(w_{1},w_{2})\) and accumulator value \(\mathfrak{Acc}\) are generated, where \(w_{1}=\left[\mathrm{H}_{0},\ldots,\mathrm{H}_{isd},\mathrm{H}_{(i+1)*d}, \ldots,\mathrm{H}_{n}\right]\) and \(w_{2}=\left[x_{isd},x_{isd+1},\ldots,x_{(i+1)*d}\right]\). The verifier validates \(H_{n}=\mathfrak{Acc}\) and (2) \(\mathrm{H}_{(i+1)*d}=H(\ldots(H(H(i_{s}{}_{id})||x_{isd+1}))\ldots||x_{(i+1)*d})\). If (1) is not satisfied, the algorithm returns \(\bot\); if (1) and (2) hold and \(x\in w_{2}\), the algorithm outputs 1; the algorithm outputs 0 if \(x\
otin w_{2}\). 4. **Update**: On the input \(x\in M\), the accumulator value before the update \(\mathfrak{Acc}_{bf}\) and memory \(m_{bf}\) are generated. The Update algorithm has two states: add and delete. 1. If \(op=add\) and \(x\
otin X\), the algorithm adds the element \(x\) to the set \(X\), i.e., \(X=\left\{x_{1},x_{2},\ldots,x_{n},x\right\}\); the hash value is computed after splicing x and the tail node Hn to become the new tail node of the hash chain, and the updated accumulator value is \(\mathfrak{Acc}_{af}=H(\mathfrak{Acc}_{bf},x)\). The witness of the update can be expressed as \(w_{\mathrm{add}}=(\mathrm{add},\left[\mathfrak{A}_{bf},\mathfrak{Acc}_{af} \right],\left[x\right])\). 2. If \(op=\mathrm{del}\) and \(x\in X\), the algorithm first locates the element \(x\) in the set \(X\) and then removes it from the set. The hash function in our scheme is collision-resistant. To ensure the correctness of the hash chain accumulator model, the algorithm needs to recalculate the chain node after the element \(x\) in the hash chain and build a new hash chain \(HC^{\prime}:\mathfrak{Acc}_{af}=\mathfrak{Acc}_{bf}\setminus x\). 5. **CheckUpdate**: On the input \(x\in M\), the witness \(w\) and the accumulator values before and after the update \(\mathfrak{Acc}_{bf}\) and \(\mathfrak{Acc}_{af}\) are generated. 1. The algorithm calculates \(\mathfrak{Acc}^{\prime}=H(\mathfrak{Acc}_{bf},x)\) if \(w=(add,w_{1},w_{2})\).