# An Ordered Universal Accumulator Based on a Hash Chain
## 2 Background  
### Related Works  
The concept of the cryptographic accumulator was first proposed by [PERSON] et al. in 1993 [PERSON] et al. (1993), and an accumulator based on the RSA assumption was constructed. A limitation is that the accumulation set is fixed. It belongs to the category of static accumulators (once a static accumulator is created, the set it represents is immutable). [PERSON] et al. proposed the concept of the dynamic accumulator in 2002, which can support the dynamic addition and deletion of elements in the accumulating set ([PERSON] et al., 2002). However, this model can only give the membership witness of the element and cannot prove that an element is not in the set (i.e., non-membership witness). On this basis, [PERSON] et al. proposed the concept of a universal accumulator ([PERSON] et al., 2003), which can generate a membership witness and non-membership witness. From the perspective of existing security assumptions, accumulators can be categorized into three main types: RSA-based accumulators ([PERSON] et al., 2003; [PERSON] et al., 2003; [PERSON] et al., 2003; [PERSON] et al., 2003), bilinear-pairing-based accumulators ([PERSON] et al., 2003; [PERSON] et al., 2003; [PERSON] et al., 2003), and hash-tree-based accumulators ([PERSON] et al., 2003). Regarding storage requirements, accumulators are classified as either memory-based (requiring storage of the accumulated set) or memoryless (not requiring such storage). Additionally, accumulators are divided into strong accumulators, which do not require trapdoor information, and weak accumulators, which do. These cryptographic tools have found applications in diverse areas, such as certificate revocation, medical diagnostics, group signatures, timestamps, stateless blockchains, and more ([PERSON] et al., 2003; [PERSON] et al., 2003; [PERSON] et al., 2003; [PERSON] et al., 2003; [PERSON] et al., 2003; [PERSON] et al., 2003). RSA and bilinear-pair-based accumulators have drawbacks, including the need for a trusted administrator, which limits their application to centralized systems, as well as the requirement to protect trap values in order to maintain accumulator integrity ([PERSON] et al., 2003). This is contradictory to all decentralized systems. On the other hand, because the accumulator value needs to be maintained synchronously by a trusted administrator, it introduces excessive communication overhead for the entire system, making it unsuitable for resource-constrained devices. The only known family of accumulators that can be safely used in an untrusted system are those based on Merkle trees. This is because Merkle trees do not require trapdoor values at any point during their operations ([PERSON] et al., 2003). Merkle trees are accumulators based on hash trees. In this structure, data values are associated with the leaf nodes of a binary tree. The values of sibling nodes are hashed in order to compute the value associated with their parent node, and so on and so forth, until a value for the root of the tree is obtained. The Merkle tree accumulates the hash upward to obtain the tree's root. It is defined as the accumulator of the set of values associated with the leaves of the tree. [PERSON] et al. improved the original Merkle tree ([PERSON] et al., 2003). The proposed CHKO model can dynamically add and delete accumulated elements and can provide a membership witness and non-member witness. The scheme is provably secure under the assumption of the existence of a collision-resistant hash function. However, the construction and maintenance of the Merkle tree is more complicated, and it takes up a lot of memory during verification. While [PERSON] [3] demonstrated the security benefits of hash chains in digital signatures, the HC accumulator extends these advantages to the domain of set membership, achieving trust minimization and self-verifiable proofs, alongside storage efficiency gains over tree-based accumulators.