zkFU: Verifiable Federated Unlearning via Trace-Consistent Subtraction and Zero-Knowledge Proofs

Federated unlearning needs both effective client removal and verifiable evidence of the removal computation. Existing methods largely optimize forgetting and utility, while direct cryptographic replay scales with the training history. We introduce zkFU, which combines compact zero-knowledge certification with retained-aware recovery. Its key idea is to use linear aggregation to turn committed client updates into a compact deletion relation. Trace-consistent gradient subtraction (TCGS) computes a retained-normalized seed for weighted client requests. Homomorphic commitment aggregation then reduces certification to an O(d) affine statement after public aggregation, compared with O(NTd) direct replay over N clients, T rounds, and d parameters. TraceTrust recovers utility through sparse trust filtering, scale calibration, and forgetting-direction-shielded repair. We prove certificate soundness, zero knowledge, and completeness, and bound the seed’s mismatch with retained-only retraining. The construction supports cumulative requests and public-coefficient linear aggregation rules, including FedAvg and its common variants. Across three datasets and 11 baselines, zkFU alone ranks in the top two for both retained accuracy and KL divergence to retraining. Twenty-seed tests establish equivalence to retraining within ±1 percentage point in mean membership- inference gap under a shadow-model attack on Fashion-MNIST and CIFAR-10. The Halo2 prototype verifies an 11M-parameter ResNet-18 certificate in 29 s. A matched Fashion-MNIST comparison projects about 930× lower proving time than the implemented aggregation-only replay baseline.