We present Veil, a decentralized messaging protocol that unifies metadata protection, spam prevention, and offline message delivery through a single mechanism: Proof-of-Relay. In Veil, sending a message requires a zero-knowledge proof that the sender has faithfully relayed messages for others through a stratified mixnet. The relay work itself constitutes the anonymizing infrastructure, eliminating the need for cryptocurrency tokens, blockchain consensus, or trusted third parties. We make three contributions. First, we prove that bilateral non-transferable credits with epoch-bound nullifiers achieve incentive compatibility without a global state, a general result applicable beyond messaging to any peer-to-peer system requiring fair exchange. Second, we establish a Growth-Isolation Impossibility theorem showing that no CRDT merge function can simultaneously resist inflation and guarantee completeness for monotonically growing verifiable evidence, and present a resolution via penalty-log CRDTs with locally-computed growth. Third, we prove a constructive adversary bound: any adversary controlling a fraction f of relay nodes necessarily contributes to sender anonymity entropy, while the individual deanonymization probability remains bounded, ensuring that adversarial participation requires a productive contribution while individual targeting remains negligible. Veil requires no economic investment to participate; privacy is earned through device contribution alone. We analyze the protocol's security under a global passive adversary with formal indistinguishability definitions, bound Sybil infiltration under depth-limited social vouching, and demonstrate mobile feasibility with verified constraint counts via Nova folding over BabyJubjub.
Anirudh Gupta Surisetty (Tue,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: