ExpProof: Operationalizing Explanations for Confidential Models with ZKPs
This page was written by an AI model to give a high-level overview of the paper. Please check the paper for detail: PMLR.
Explanations of machine learning (ML) predictions are meant to build trust, and regulations such as the "right to explanation" increasingly demand them. Many of the settings where they are demanded are adversarial: a bank that denies a loan based on a model's prediction has an incentive to return an explanation the applicant cannot contest, rather than one that reveals how the model actually decided. Prior work shows that explanations can be manipulated with practical attacks. Two features of real deployments make this easy. Models are kept confidential for intellectual-property and legal reasons, so the owner can swap models (one for predictions, another for explanations, or a different one after an audit). And popular explanation algorithms such as LIME (Local Interpretable Model-Agnostic Explanations) are randomized and have tunable parameters, and nothing guarantees the owner ran them as specified.
The existing remedy is consistency checking: collect many prediction-explanation pairs and test whether they fit together. The paper argues this puts the whole burden on the customer, needs many queries that an individual customer does not have, and has been shown to be hard for local explanations. Even a perfectly faithful explanation algorithm does not help if the owner can choose which model and parameters to run it with.
The paper's answer, ExpProof, uses two cryptographic tools. A commitment binds the model owner, before any query arrives, to one fixed set of model weights and explanation parameters without revealing them. A zero-knowledge proof (ZKP) then lets the owner prove, for each query, that the prediction and the LIME explanation were computed correctly from the committed weights, while revealing nothing more about the weights than the prediction and explanation themselves do. The customer checks the proof in a fraction of a second, without seeing the model.
Running LIME as-is inside a ZKP is impractical: it needs random sampling, exponentials, many model inferences and an optimization (a weighted LASSO regression), and ZKP systems work over integers and are slow at non-linear functions. The paper therefore studies ZKP-amenable variants of LIME (uniform or Gaussian sampling, with or without the exponential similarity kernel, and a new BorderLIME that first searches for a nearby point with the opposite label), and it proves results instead of recomputing them where checking is cheaper. Random samples come from a Poseidon hash keyed by randomness from both sides; exponentials and the Gaussian inverse CDF are checked against lookup tables; and instead of solving LASSO inside the proof, the circuit checks that the owner's solution has a duality gap below a public threshold. The system is built on the ezkl library with the Halo2 proof system, in about 3.7k lines of Rust.
The authors evaluate small fully connected ReLU neural networks (2 layers of 16 units) and random forests on three fairness benchmarks (Adult, Credit, German Credit), on a 64-CPU server with no GPU and no added parallelization. For neural networks with standard LIME variants, proof generation takes at most about 1.5 minutes, verification at most about 0.12 seconds, and proofs are at most about 13 KB. The variants give similar explanation fidelity, and the paper names Gaussian sampling with no kernel as likely the most practical. BorderLIME is at least as faithful as standard LIME and sometimes better, at a larger cost (4.85 vs 1.17 minutes to prove for the neural networks). As models get deeper, proving the model inferences dominates the cost.
Key takeaways
- In adversarial settings (loans, audits) a confidential model's owner can swap models or tune the explanation algorithm, so explanations alone do not build trust.
- ExpProof commits the owner to fixed weights and explanation parameters, then attaches a zero-knowledge proof to each explanation showing it is LIME run correctly on the committed model, without revealing the weights.
- To make LIME provable, the paper tries sampling and kernel variants and a new BorderLIME, and checks results instead of recomputing them: hash-derived randomness, lookup tables for non-linear functions, and a duality-gap check in place of solving LASSO.
- On 2-layer neural networks with standard LIME variants: at most about 1.5 minutes to prove, 0.12 seconds to verify, 13 KB per proof, on CPUs only. Gaussian sampling without a kernel is the paper's practical pick.
- ExpProof proves the explanation was computed correctly; it does not stop a model trained to give innocuous explanations, which the paper says needs a separate zero-knowledge proof of training.
From a LIME explanation to a zero-knowledge proof of it
The cryptographic background, LIME, what a solution must guarantee, the provable LIME variants, the circuit, and what it costs.
1 · Background: commitments and zero-knowledge proofs
ExpProof uses two standard cryptographic primitives. A commitment scheme turns a private value w into a short public string comw. It is hiding (comw reveals nothing about w) and binding (no other value w′ opens to the same comw). Publishing a commitment to the model weights fixes the model without disclosing it.
A zero-knowledge proof involves a prover holding a private input (the witness w) and a verifier, who both know a circuit P and a public input x. The prover convinces the verifier that it knows a w with P(x, w) = 1, and the protocol has three properties:
- Complete: an honest prover with a valid witness always convinces an honest verifier.
- Sound: except with negligible probability, a cheating prover cannot convince the verifier when no valid witness exists, however it deviates from the protocol.
- Zero-knowledge: the verifier learns nothing about w beyond the fact that P(x, w) = 1, even if it deviates from the protocol.
A classic result says any NP statement can be proved this way. The paper uses succinct ZKPs, whose proofs are small and fast to check. The catch, which shapes the whole design, is that the computation must be written as an arithmetic circuit over integers, and proving is expensive even for simple steps; non-linear functions such as exponentials are not supported directly.
2 · Background: what LIME computes
LIME explains one prediction f(x) of a complex classifier by fitting a simple linear model around x. The linear model's coefficients say how much each input feature pushed the prediction, and the largest ones are the explanation. The paper's Algorithm 1:
- Sample a neighborhood. Draw n random points zi around x.
- Weight by distance. Give each sample a weight πi = exp(−ℓ2(x, zi)2/σ2), the exponential similarity kernel, so nearer points count more. The bandwidth σ sets how local the explanation is.
- Query the model. Compute f(zi) for every sample.
- Fit a sparse linear model. Solve a weighted LASSO regression: minimize Σ πi(f(zi) − w⊤zi)2 plus an ℓ1 penalty on w, which drives most coefficients to zero.
- Report the top K. Sort the coefficients by absolute value and return the K largest with their features.
The paper picks LIME because it is popular, model-agnostic, and local (a customer usually cares about the model's behavior around their own input). Every step is a problem for a ZKP: randomness must be provably fair, the kernel is an exponential, step 3 is n model inferences, and step 4 is an optimization.
3 · Threat model and what a solution must guarantee
A model owner holds a confidential classifier f. A customer sends an input x and receives a prediction f(x) and an explanation E(f, x). The paper assumes the owner trains the model without manipulation, that LIME's parameters are public and set in good faith, and that the owner does not know in advance which queries it will get. At query time the owner may change the prediction, use a model other than the trained one, or run a different or corrupted explanation algorithm. The paper lists five requirements:
| Requirement | Meaning | How ExpProof provides it |
|---|---|---|
| Model uniformity | The same model is used for every input | Commitment to the weights before any query |
| Explanation correctness | The explanation algorithm is run correctly for every input | A ZKP attached to each explanation |
| Model consistency | The same model produces the prediction and the explanation | Both are computed and proved in one system against the same commitment |
| Weight confidentiality | Nothing leaks about the weights beyond what the prediction and explanation already reveal | A by-product of the commitment and ZKP (formal statement in Appendix A.1) |
| Technique reliability | The guarantee mechanism is itself sound and complete | Inherited from the proof system (Appendix A.1) |
4 · ZKP-amenable LIME variants and BorderLIME
Since LIME must be reimplemented as a circuit anyway, the paper asks whether variants exist that explain about as well but cost less to prove. It varies the two steps repeated for every sample (sampling and the kernel), giving four standard variants named by their initials:
| Variant | Sampling around x | Kernel weight πi | Extra circuit work |
|---|---|---|---|
| G+E | Gaussian | exponential | inverse-CDF lookup and exponential lookup |
| G+N | Gaussian | none (πi = 1) | inverse-CDF lookup |
| U+E | uniform | exponential | exponential lookup |
| U+N | uniform | none (πi = 1) | neither |
BorderLIME addresses a separate weakness. If x is far from the model's decision boundary, every sampled neighbor gets the same label and the explanation is vacuous. Prior work fixes this with a radial search for the nearest point of the opposite class, which needs many inferences and would be expensive to prove. BorderLIME replaces it with a line search:
- Sample m random directions from x.
- Along each direction, step by a fixed length δ until the label changes or an iteration limit T is reached. The directions are independent, so they can be searched in parallel.
- Take the opposite-label point closest to x as xborder, and run any LIME variant there instead of at x.
The step length is the model's stability radius: the smallest, over inputs from the data distribution, of the largest radius around an input within which the prediction does not change. Choosing it well is left open; the paper suggests finding it offline and either proving it once or committing to it.
5 · The protocol and the ZK LIME circuit
ExpProof has two phases (Algorithm 5). In the commitment phase, run once, the owner samples a random value rp and publishes commitments to it and to the weights W. The architecture is public, and LIME's parameters are public or committed. In the online phase, for every query, the customer sends x and a random value rv; the owner computes the prediction, the LIME samples and their labels, the explanation and a dual LASSO solution, and produces one proof that ties them all to the commitments (Algorithm 6, ZK LIME).
6 · Verifying instead of recomputing
The paper's main efficiency principle is that checking an answer can be cheaper than computing it. Each LIME step gets its own strategy:
- Sampling. Samples come from the Poseidon hash, a hash function designed to be cheap inside ZKP circuits, keyed by rp + rv. Because the owner committed to rp before seeing rv, and the customer picks rv, the key is uniformly random in the view of both parties. The circuit checks the hashes with ezkl's built-in Poseidon circuit. Gaussian samples are made from uniform ones by the inverse CDF, checked against a lookup table.
- Exponential kernel. The circuit checks each kernel value against a lookup table of the exponential function.
- Inference. The prediction and every sample's label are checked with ezkl's inference circuit, so better inference provers plug in directly.
- LASSO. The circuit does not run an optimizer. The owner solves LASSO outside the proof and supplies the solution and a dual feasible point as part of the witness; the circuit evaluates the closed-form primal and dual objectives and checks that their gap is at most ε, and that the dual point satisfies its feasibility constraint.
- Top-K. The circuit checks that the reported features and values are the K largest LASSO coefficients.
7 · Implementation and evaluation setup
| Item | Setting |
|---|---|
| Proof system | ezkl library (version 18.1.1) on Halo2, with KZG commitments; about 3.7k lines of Rust. All configurations use 218 Halo2 rows and 200k-row lookup tables. |
| Hardware | Ubuntu server, 64 x86-64 CPUs, 256 GB memory. No GPUs; ezkl's own multithreading only, no added parallelization. |
| Datasets | Fairness benchmarks Adult (14 features), Credit (23 features), German Credit (20 features); continuous features standardized. |
| Models | 2-layer fully connected ReLU networks, 16 hidden units per layer, weights in fixed point with four decimal places (about 1% test-accuracy drop); random forests of 5 to 6 trees. |
| LIME settings | n = 300 samples, K = 5; uniform hypercube of half-edge 0.2 or Gaussian with standard deviation 0.2; kernel bandwidth √(#features) × 0.75 (the LIME library default); ε = 0.001. |
| BorderLIME settings | T = 250 iterations, m = 5 directions (then reduced while every input still finds an opposite-class point); δ is the smallest of {0.01, 0.03, 0.05, 0.07, 0.1, 0.15} that finds an opposite-class point for all 50 inputs, a heuristic estimate. |
| Fidelity metric | Prediction similarity: the fraction of 1000 points near the input on which the linear explanation and the model agree. |
| Overhead metrics | Proof-generation time, verification time, proof size; averaged over 50 test inputs. |
8 · Results: fidelity and overhead
- Standard variants explain about equally well. For the neural networks, the fidelity error bars of the four variants overlap substantially (the paper suggests the small neighborhoods make kernel and sampling matter little). On Credit, the dataset with the most features, Gaussian sampling does slightly better than uniform.
- Overhead is small and similar across datasets. For neural networks and standard LIME, proof generation takes at most about 1.5 minutes, verification at most about 0.12 seconds, and proofs are at most about 13 KB. Gaussian sampling and the exponential kernel each add cost, because each adds a step to the circuit.
- The paper's pick: Gaussian sampling with no kernel (G+N) is "likely the most amenable for a practical ZKP system": faithful explanations at a small overhead.
- BorderLIME. The gap between Gaussian and uniform sampling widens; tripling the samples for uniform sampling closes it on Adult and German. BorderLIME G+N is at least as faithful as standard LIME G+N and sometimes better, and with 5000 samples it does better consistently for the neural networks and equals or beats it for the random forests (Appendix B). It costs more to prove because the border-point search is also proved:
| G+N variant | Proof generation | Verification | Proof size |
|---|---|---|---|
| Neural network, standard LIME | 1.17 min | 0.11 s | 10.40 KB |
| Neural network, BorderLIME | 4.85 min | 0.30 s | 18.30 KB |
| Random forest, standard LIME | 2.02 min | 0.14 s | 16.20 KB |
| Random forest, BorderLIME | 8.46 min | 0.44 s | 17.25 KB |
From the paper's Tables 2 and 3; the paper reports the results as consistent across the three datasets. Random-forest fidelity and overhead trends match the neural networks (Appendix B.2).
9 · Where the proving time goes
An ablation on Credit with the most expensive variant (G+E, n = 300) splits proof generation into three parts and grows the network from 2 to 40 hidden layers of 16 units. Sampling plus kernel and LASSO stay almost constant; proving the inferences grows with depth and becomes the largest part.
Scaling width as well as depth (16 to 64 units, 2 to 20 layers, the paper's Figure 4), total proof-generation and verification times grow polynomially; the largest configuration takes roughly 50 minutes to prove and about 6 seconds to verify (read from Figure 4). Feature dimension has a smaller effect. Because inference proving is a plug-in module, the paper expects advances in proving inference to carry over, citing a state-of-the-art inference proof of about 15 minutes for a 13-billion-parameter model.
10 · Limitations the paper states
- A corrupted model is out of scope. ExpProof proves the explanation was computed correctly for the committed model. It cannot stop a model trained to give innocuous explanations alongside biased predictions (for example by adding an explanation-manipulating term to the training loss). That needs a zero-knowledge proof of training, which the paper leaves to existing work.
- The explanation method itself must be trustworthy. End-to-end trust needs explanations that are faithful, stable and robust to adversarial attacks, as well as verifiable. The paper addresses only verifiability under confidentiality and views it as complementary to work on the other two.
- Parameters are assumed honest. LIME's parameters and ε are public and assumed to be set in good faith; the paper recommends that ε be set by the verifier or a regulator.
- The stability radius is heuristic. BorderLIME's δ was picked by a search over a small set of values and is not guaranteed minimal; finding it properly is future work.
- Future directions. Designing explanation algorithms that are efficient in ZKPs and robust to manipulation by construction, and finding other ML computations where ZKPs can provide verifiable trust guarantees.
FAQ
Q·What does "operationalizing explanations" mean here?▾
Making explanations usable as a trust tool in settings where the parties have opposing interests. The paper starts from prior work arguing that post-hoc explanations fail in adversarial contexts, because the party producing them can manipulate them. ExpProof does not change what LIME computes; it makes it checkable that LIME was computed correctly, on the model the owner committed to.
Q·How is this different from existing zero-knowledge ML (proofs of inference)?▾
Prior zkML work mostly proves that a model's inference, or its training, was done correctly, and some work proves properties such as fairness or accuracy of a confidential model. ExpProof proves an explanation. Proving inference is one component of it (the prediction and the label of every LIME sample), and the paper uses ezkl's inference circuit as a plug-in module, but the explanation also needs provable randomness, a kernel, a LASSO fit and a top-K selection. The paper describes itself as, to the authors' knowledge, the first work to identify the need for proving explanations.
Q·Why not let customers or auditors run consistency checks?▾
The paper gives three reasons: checks place the whole burden on the customer, they need many prediction-explanation pairs that an individual customer does not have, and prior work shows auditing local explanations this way is hard. With ExpProof the owner does the expensive work (minutes of proving) and the customer's check takes a fraction of a second.
Q·What does the customer learn about the model?▾
Nothing beyond what the prediction and the explanation already reveal. That is the zero-knowledge property, and the paper's Appendix A.1 states and sketches proofs for completeness, knowledge soundness and zero knowledge, inheriting them from Halo2. The architecture is assumed public; only the weights are confidential.
Q·Can the owner still cheat?▾
Not by swapping models, changing parameters after the fact, or running LIME incorrectly: the commitment and the proof rule those out. But it can train a model that produces innocuous explanations alongside biased predictions, for instance by adding an explanation-manipulating term to the training loss. The paper says preventing that requires a zero-knowledge proof of training, which is outside its scope.
Q·Why does the randomness come from both sides?▾
LIME's samples are random, and an owner that picks its own samples could choose a neighborhood that gives a convenient explanation. The owner commits to a random value rp during setup, the customer supplies rv with each query, and samples are generated by the Poseidon hash keyed with rp + rv. Neither side alone controls the key, so it is uniformly random in the view of both; the circuit checks the hashing.
Q·Why check a duality gap instead of solving LASSO inside the proof?▾
An optimizer is iterative and would be expensive to express as a circuit. Checking a solution is cheaper: the owner solves LASSO outside the proof and supplies a dual feasible point, and the circuit only evaluates the closed-form primal and dual objectives, checks that their gap is at most ε, and checks dual feasibility. This also handles the fact that ZKP arithmetic is fixed-point, so the solution is quantized. In the experiments ε = 0.001.
Q·Who chooses ε and the other LIME parameters?▾
They are public (or committed) and assumed to be set in good faith. The paper argues ε in particular must be public, because a prover free to choose it could set it to any value, and should ideally come from the verifier or a regulator based on how much error is tolerable, independent of the model and data.
Q·Which LIME variant should one use?▾
The paper's recommendation is Gaussian sampling with no kernel (G+N). The four standard variants gave similar fidelity in its experiments, Gaussian sampling did slightly better on the highest-dimensional dataset, and dropping the exponential kernel removes a step from the circuit. If the input may be far from the decision boundary, BorderLIME gives explanations at least as faithful as standard LIME, at roughly four times the proving time in the neural-network experiments (4.85 vs 1.17 minutes; the ratio is this summary's arithmetic).
Q·Does it scale to large models?▾
The experiments use small models: 2-layer networks of 16 units and random forests of 5 to 6 trees, with ablations up to 40 layers and 64 units per layer. Proving the model inferences dominates cost as models grow, and total proving time grows polynomially with depth and width. The paper's argument for larger models is that inference proving is a plug-in module, so progress there (it cites about 15 minutes for a 13-billion-parameter model) carries over. Explanations of large models are not evaluated.
Q·Does quantization change the model?▾
Slightly. ZKP libraries work over integers, so the network weights are converted to fixed point with four decimal places, which cost about 1% test accuracy in the paper's networks. The committed and proved model is the quantized one.
Q·What does the evaluation not show?▾
It covers three tabular fairness datasets, small networks and random forests, and one explanation method (LIME and its variants). Fidelity is measured by prediction similarity, not by user studies. Runs are CPU-only with no added parallelization, so the times are not tuned for speed; the paper notes BorderLIME's direction searches could run in parallel. Robustness of the explanations to manipulation is explicitly left to other work.