# Proof of Unlearning: Definitions and Instantiation

arXiv: https://arxiv.org/abs/2210.11334 · HTML: https://mlsanity.com/paper/2210.11334/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Placed in Machine unlearning, one of 12 directions in LLM safety and security.
- Builds on 39 of its 95 references that are in the map.
- First posted on arXiv 20 Oct 2022.

## Placed in

- LLM safety and security / [Machine unlearning](https://mlsanity.com/safety/machine-unlearning/)

## Builds on (most cited first, 30 of 39)

- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Stealing Machine Learning Models via Prediction APIs](https://mlsanity.com/paper/1609.02943/) (2016)
- [Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks](https://mlsanity.com/paper/1911.04933/) (2019)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [A Survey of Machine Unlearning](https://mlsanity.com/paper/2209.02299/) (2022)
- [Machine Unlearning of Features and Labels](https://mlsanity.com/paper/2108.11577/) (2021)
- [When Machine Unlearning Jeopardizes Privacy](https://mlsanity.com/paper/2005.02205/) (2020)
- [Forgetting Outside the Box: Scrubbing Deep Networks of Information Accessible from Input-Output Observations](https://mlsanity.com/paper/2003.02960/) (2020)
- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning](https://mlsanity.com/paper/2110.11891/) (2021)
- [Membership Leakage in Label-Only Exposures](https://mlsanity.com/paper/2007.15528/) (2020)
- [Graph Unlearning](https://mlsanity.com/paper/2103.14991/) (2021)
- [The Right to be Forgotten in Federated Learning: An Efficient Realization with Rapid Retraining](https://mlsanity.com/paper/2203.07320/) (2022)
- [Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware](https://mlsanity.com/paper/1806.03287/) (2018)
- [Proof-of-Learning: Definitions and Practice](https://mlsanity.com/paper/2103.05633/) (2021)
- [Recommendation Unlearning](https://mlsanity.com/paper/2201.06820/) (2022)
- [Manipulating SGD with Data Ordering Attacks](https://mlsanity.com/paper/2104.09667/) (2021)
- [Towards Probabilistic Verification of Machine Unlearning](https://mlsanity.com/paper/2003.04247/) (2020)
- [VeriFi: Towards Verifiable Federated Unlearning](https://mlsanity.com/paper/2205.12709/) (2022)
- [Chiron: Privacy-preserving Machine Learning as a Service](https://mlsanity.com/paper/1803.05961/) (2018)
- [MLCapsule: Guarded Offline Deployment of Machine Learning as a Service](https://mlsanity.com/paper/1808.00590/) (2018)
- [VeriML: Enabling Integrity Assurances and Fair Payments for Machine Learning as a Service](https://mlsanity.com/paper/1909.06961/) (2019)
- [Deletion Inference, Reconstruction, and Compliance in Machine (Un)Learning](https://mlsanity.com/paper/2202.03460/) (2022)
- [Helen: Maliciously Secure Coopetitive Learning for Linear Models](https://mlsanity.com/paper/1907.07212/) (2019)
- ["Adversarial Examples" for Proof-of-Learning](https://mlsanity.com/paper/2108.09454/) (2021)
- [Efficient Deep Learning on Multi-Source Private Data](https://mlsanity.com/paper/1807.06689/) (2018)

## Built on by (most cited first, 15 of 15)

- [Machine Unlearning: Solutions and Challenges](https://mlsanity.com/paper/2308.07061/) (2023)
- [Exploring the Landscape of Machine Unlearning: A Comprehensive Survey and Taxonomy](https://mlsanity.com/paper/2305.06360/) (2023)
- [Verification of Machine Unlearning is Fragile](https://mlsanity.com/paper/2408.00929/) (2024)
- [zkDL: Efficient Zero-Knowledge Proofs of Deep Learning Training](https://mlsanity.com/paper/2307.16273/) (2023)
- [Towards Reliable Forgetting: A Survey on Machine Unlearning Verification](https://mlsanity.com/paper/2506.15115/) (2025)
- [A Survey on Recommendation Unlearning: Fundamentals, Taxonomy, Evaluation, and Open Questions](https://mlsanity.com/paper/2412.12836/) (2024)
- [Really Unlearned? Verifying Machine Unlearning via Influential Sample Pairs](https://mlsanity.com/paper/2406.10953/) (2024)
- [Evaluating of Machine Unlearning: Robustness Verification Without Prior Modifications](https://mlsanity.com/paper/2410.10120/) (2024)
- [Exploring Incremental Unlearning: Techniques, Challenges, and Future Directions](https://mlsanity.com/paper/2502.16708/) (2025)
- [ZK-APEX: Zero-Knowledge Approximate Personalized Unlearning with Executable Proofs](https://mlsanity.com/paper/2512.09953/) (2025)
- [Governing AI Forgetting: Auditing for Machine Unlearning Compliance](https://mlsanity.com/paper/2602.14553/) (2026)
- [zkUnlearner: A Zero-Knowledge Framework for Verifiable Unlearning with Multi-Granularity and Forgery-Resistance](https://mlsanity.com/paper/2509.07290/) (2025)
- [Client-Verifiable and Efficient Federated Unlearning in Low-Altitude Wireless Networks](https://mlsanity.com/paper/2603.29688/) (2026)
- [Auditing Machine Unlearning: A Systematic Research on Whether Models Truly Forget](https://mlsanity.com/paper/2606.16110/) (2026)
- [From Mathematical to Executable Certificates for Machine Unlearning](https://mlsanity.com/paper/2610.02268/) (2026)

## Abstract (arXiv)

The "Right to be Forgotten" rule in machine learning (ML) practice enables some individual data to be deleted from a trained model, as pursued by recently developed machine unlearning techniques. To truly comply with the rule, a natural and necessary step is to verify if the individual data are indeed deleted after unlearning. Yet, previous parameter-space verification metrics may be easily evaded by a distrustful model trainer. Thus, Thudi et al. recently present a call to action on algorithm-level verification in USENIX Security'22. We respond to the call, by reconsidering the unlearning problem in the scenario of machine learning as a service (MLaaS), and proposing a new definition framework for Proof of Unlearning (PoUL) on algorithm level. Specifically, our PoUL definitions (i) enforce correctness properties on both the pre and post phases of unlearning, so as to prevent the state-of-the-art forging attacks; (ii) highlight proper practicality requirements of both the prover and verifier sides with minimal invasiveness to the off-the-shelf service pipeline and computational workloads. Under the definition framework, we subsequently present a trusted hardware-empowered instantiation using SGX enclave, by logically incorporating an authentication layer for tracing the data lineage with a proving layer for supporting the audit of learning. We customize authenticated data structures to support large out-of-enclave storage with simple operation logic, and meanwhile, enable proving complex unlearning logic with affordable memory footprints in the enclave. We finally validate the feasibility of the proposed instantiation with a proof-of-concept implementation and multi-dimensional performance evaluation.