# An Ordered Universal Accumulator Based on a Hash Chain
## 5 Results  
### Theory Analysis  
In Section 3, the HC accumulator divides the entire hash chain into multiple groups at \(d\) intervals when constructing the witness \(w_{1}\) and constructs the membership witness of element \(x\) based on the group.  
If the accumulated element set \(X\) size is \(n\), the optimal grouping interval \(d\) should be \(\sqrt{n}\).  
Suppose that the set \(X\) is divided into \(s\) groups at \(d\) intervals. Then, \(w_{1}=\left[H_{0},H_{d},\ldots,H_{(s-1)\,\mathsf{add}},H_{n}\right]\). It can be seen that the larger the number of groups \(s\), the larger the witness \(w_{1}\) to be transmitted. To minimize the witness size, we minimize f(s) = g + s, where g \(\times\) d = n. Substituting g = n/d, we obtain f(d) = n/d + d. By the AM-GM inequality (the inequality of arithmetic and geometric means [31]), \((n/d+d)/2\geq\sqrt{(n/d)\times d}=\sqrt{n}\). Equality holds when n/\(d=d\); thus, \(d=\sqrt{n}\) minimizes f(k). Therefore, the optimal grouping interval is \(\sqrt{n}\). Therefore, in order to ensure that the size of the transmission witness is as small as possible, the optimal group interval \(d\) should be \(\sqrt{n}\).  
The verification efficiency of this model depends on the size of the evidence \(w\), and in this article, \(\sqrt{n}\); that is, the verification efficiency is \(O\big{(}\sqrt{n}\big{)}\). At the same time, to store the set \(X\) at the scale \(n\), the storage efficiency of this model is \(O(n)\).  
Table 2 shows the efficiency comparison with other accumulator schemes, where S and D represent static accumulators and dynamic accumulators, respectively; U represents a general accumulator; lmt indicates whether there is a limit to the number of accumulator set elements; trapdoor indicates whether the accumulator needs a trapdoor; and \(|\mathsf{pp}|\), \(|\mathsf{w}|\), and \(|\mathsf{u}|\) represent the sizes of the public parameters, membership witness, and non-membership witness. Note that in Table 2, the \(|\mathsf{pp}|\) column for RSA-based accumulators refers to the size of the public accumulator _value_, not the size of the underlying RSA modulus itself.  
According to Table 2, compared with the DT model and CKS scheme based on bilinear pairs, the HC accumulator has no limit on the number of accumulated set elements, and compared with the BM scheme, CL scheme, BBF scheme, and DT scheme based on bilinear pairs and RSA, the HC accumulator does not require the involvement of a trusted third party when performing related accumulator operations and supports a public update. An accumulator based on a bilinear pair needs to set the upper bound of the set in advance before building the model, and its common parameter size is the same as the set size, both of which are \(O(q)\). The HC accumulator only needs to determine a suitable hash function, so its public parameter size is \(O(1)\). Since the accumulator based on the hash function does not require a trusted administrator, and the witness it gives can be self-certified by the verifier, the CHKO scheme and HC accumulator generate larger witnesses than the accumulator model based on RSA and bilinear pairs. The time required by RSA and bilinear map accumulators to generate non-membership witnesses is proportional to the number of elements in the set. And, the witness must be updated by the accumulator manager itself and then broadcast to all members, which will bring a large communication overhead to the system. Although the HC accumulator generates a larger witness than the CHKO scheme, it needs to store all the elements in the tree structure (including all of the root nodes and the leaf node) with a spatial complexity of \(O(2\text{N})\), while the HC accumulator only stores all the elements in the hash chain, with a spatial complexity of \(O(\text{N})\). In scenes where a large number of elements are frequently added, HC achieves an average space reduction of 50% compared to CHKO. Furthermore, the HC scheme is significantly simpler in design and implementation.