ZINK: Privacy-preserving and Verifiable Influence Maximization in Social Networks

Influence maximization (IM) is a fundamental problem in social networks, where the goal is to identify a set of seed nodes that can maximize the spread of influence. While many existing IM algorithms assume full access to the network structure or rely on online learning, these social graphs maintained by real-world platforms (e.g., TikTok) are often derived from sensitive user interactions and are proprietary. Despite having a strong incentive to help advertisers identify effective seed nodes, e.g., to promote their ad services, these platforms face significant constraints due to privacy concerns and intellectual property protections. As a result, the major users of IM algorithms often lack access to the underlying social network. To address this tension, we propose ZINK, a zero-knowledge proof (ZKP) framework for influence maximization. ZINK allows the platform to compute and prove the effectiveness of IM results (i.e., a set of seed nodes that maximizes influence spread) over a proprietary yet cryptographically committed social network, without revealing any information beyond the IM result itself. However, IM problem is inherently complex, and naïve solutions for ZKP protocols is often impractical for a non-trivial social network. Thus, we introduce several practical assumptions and optimizations that make ZKP for IM tractable and efficient. We implement ZINK and evaluate it on real-world datasets, showing that it scales to networks with thousands of nodes. Compared to commercial ZKVMs, ZINK manifests up to 42.72× speed up in proof generation with a moderate verification cost and constant proof size.