Paper 2021/1577

SNARKBlock: Federated Anonymous Blocklisting from Hidden Common Input Aggregate Proofs

Michael Rosenberg and Mary Maller and Ian Miers

Abstract

Moderation is an essential tool to fight harassment and prevent spam. The use of strong user identities makes moderation easier, but trends towards strong identity pose serious privacy issues, especially when identities are linked across social media platforms. Zero-knowledge blocklists allow cross-platform blocking of users but, counter-intuitively, do not link users identities inter- or intra-platform, or to the fact they were blocked. Unfortunately, existing approaches (Tsang et al. '10), require that servers do work linear in the size of the blocklist for each verification of a non-membership proof. We design and implement SNARKBlock, a new protocol for zero-knowledge blocklisting with server-side verification that is logarithmic in the size of the blocklist. SnarkBlock is also the first approach to support ad-hoc, federated blocklisting: websites can mix and match their own blocklists from other blocklists and dynamically choose which identity providers they trust. Our core technical advance, of separate interest, is $\mathsf{HICIAP}$, a zero-knowledge proof that aggregates $n$ Groth16 proofs into one $O(\log n)$-sized proof which also shows that the input proofs share a common hidden input.