ShadowBlock: Efficient Dynamic Anonymous Blocklisting and Its Cross-chain Application

Online harassment, incitement to violence, racist behavior, and other harmful content on social media can damage social harmony and even break the law. Traditional blocklisting technologies can block malicious users, but this comes at the expense of identity privacy. The anonymous blocklisting has emerged as an effective mechanism to restrict the abuse of freedom of speech while protecting user identity privacy. However, the state-of-the-art anonymous blocklisting schemes suffer from either poor dynamism or low efficiency, requiring users to regenerate proofs after blocklist updates, incurring proof or verification overhead that grows with the blocklist size, or supporting only append-only updates without true removal. In this paper, we propose \mathsf {ShadowBlock}, an efficient dynamic anonymous blocklisting scheme. Specifically, we utilize the pseudorandom function and cryptographic accumulator to construct the public blocklisting, enabling users to prove they are not on the blocklisting in an anonymous manner. To improve verification efficiency, we design an aggregation zero-knowledge proof mechanism that converts multiple verification operations into a single one. In addition, we leverage the accumulator's property to achieve efficient updates of the blocklisting, i.e., the original proof can be reused with minimal updates rather than regenerating the entire proof. Experiments show that \mathsf {ShadowBlock} has better dynamics and efficiency than the existing schemes. Finally, the discussion on applications indicates that \mathsf {ShadowBlock} also holds significant value and has broad prospects in emerging fields such as cross-chain identity management.