SNARKBlock: Federated Anonymous Blocklisting from Hidden Common Input Aggregate Proofs

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 the HICIAP zero-knowledge proof system, which addresses a common problem in privacy-preserving protocols: using zero-knowledge proofs for repeated but unlinakble interactions. Rerandomzing a Groth16 proof achieves unlinkability without the need to recompute the proof for every interaction. But this technique does not apply to applications where each interaction includes multiple Groth16 proofs over a common hidden input (e.g., the user’s identity). Here, the best known approach is to commit to the hidden input and feed it to each proof, but this creates a persistent identifier, forcing recomputation. HICIAP resolves this problem by aggregating n Groth16 proofs into one $O(\log n) -$sized, $O(\log n) -$verification time proof which also shows that the input proofs share a hidden input. Because HICIAP is zero-knowledge, repeated shows of the same aggregate or an updated aggregate are unlinkable even though the underlying Groth16 proofs are never recomputed.