# An Ordered Universal Accumulator Based on a Hash Chain
## 1 Introduction  
A cryptographic accumulator is a primitive that generates a short commitment uniquely representing a set, enabling membership or non-membership proofs via witnesses. Existing accumulator schemes encounter new challenges when applied to emerging fields. In resource-constrained environments, such as mobile devices, and blockchain applications that demand efficient on-chain verification, there is an increasing need for lightweight, low-overhead accumulator schemes capable of naturally preserving the order of element additions. To address these pressing requirements, this paper focuses on the study of hash chain accumulators. Although RSA-based accumulators are robust, they typically involve computationally intensive operations, such as exponentiation, which can impose a significant overhead on resource-limited devices and on-chain blockchain verification. Merkle tree accumulators, another commonly used approach, excel in membership verification. However, they can suffer from storage inefficiencies and increased complexity, particularly when adapted to scenarios that require ordered element additions and frequent updates. In contrast, hash chain accumulators stand out due to their inherent simplicity and computational efficiency, relying primarily on lightweight hash function operations. Furthermore, hash chain accumulators provide efficient batch verification, enabling the simultaneous verification of multiple elements with minimal overhead--an advantage that is less readilyavailable or more computationally expensive in RSA and Merkle tree-based schemes. This batch verification capability is particularly advantageous in high-throughput systems and applications dealing with large datasets. The concept of the \"hash chain\" was first proposed by [PERSON] [1]. This scheme uses the hash function iteratively, which offers good resistance to interference, and the server only needs to save the final hash value to verify all hash sequences. [PERSON] et al. proposed star-shaped and tree-shaped hash chains [2]: the scheme can verify each packet individually and can tolerate any degree of packet loss. The advantage of the tree-shaped hash chain signature scheme lies in its lower communication load compared to the star hash chain, but there is a delay in the sender, and a block of data packets must be collected before sending, and each packet has less payload. And, further explored digital signature schemes, like those discussed by [PERSON] [3], offer an efficient method for message authentication, particularly advantageous in scenarios with potential packet loss [3]. [PERSON] et al. proposed a new message hash chain model, in which the hash value of the transmitted message is iteratively hashed to form a hash chain representing the message sequence [4]. Hash chain technology is also widely used in streaming, wireless transmission, and TCP protocols [5; 6; 7; 8; 9; 10]. The increasing demand for secure and efficient data management in distributed systems, such as mobile phone and IoT networks, has driven the need for lightweight cryptographic primitives like accumulators. Hash-chain-based accumulators are particularly attractive due to their simplicity and efficiency, making them suitable for resource-constrained environments. Our work builds upon this trend by introducing an ordered universal accumulator model based on hash chains, which can be efficiently and safely used in untrusted systems. The Merkle tree is one of the most widely used data structures for cryptographic accumulators. In this structure, each leaf node represents a data element, while each internal node is the hash of its child nodes. Merkle trees are efficient for verifying the inclusion of elements and proving non-membership. However, they face limitations in terms of storage efficiency and adaptability to certain emerging applications. We propose an ordered universal accumulator model based on hash chains (HC accumulator), which can be efficiently and safely used in an untrusted system.