🤖 machine learning

ZKBoost: Zero-Knowledge Verifiable Training for XGBoost

This paper introduces ZKBoost, the first zero-knowledge proof of training protocol for XGBoost that enables model owners to cryptographically verify correct training on committed datasets without revealing data or parameters, while overcoming previous security vulnerabilities and achieving efficiency through a specialized fixed-point implementation and VOLE-based instantiation.

Original authors: Nikolas Melissaris, Antigoni Polychroniadou, Akira Takahashi, Chenkai Weng, Jiayi Xu

Published 2026-05-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nikolas Melissaris, Antigoni Polychroniadou, Akira Takahashi, Chenkai Weng, Jiayi Xu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you hire a chef to cook a complex, secret recipe for a very important banquet. You want to be 100% sure they actually followed the recipe step-by-step using the specific ingredients you provided, but you have two big problems:

You can't see the kitchen: The chef refuses to let you watch them cook because the recipe is their "trade secret" (Intellectual Property).
You can't see the ingredients: The chef refuses to show you the specific batch of vegetables they used because that data belongs to a private farm (Privacy).

Usually, you just have to trust the chef. But what if they are a fraud? What if they bought a pre-made meal, labeled it as "freshly cooked," and served it to you?

ZKBoost is a new digital tool that solves this problem. It allows the chef (the model owner) to prove to you (the verifier) that they cooked the meal exactly according to the rules, using your specific ingredients, without ever showing you the recipe or the ingredients.

Here is how the paper explains this magic, broken down into simple concepts:

1. The "Black Box" Problem

In the world of machine learning, XGBoost is like a superstar chef. It's incredibly good at predicting things (like whether a credit card transaction is fraud or if a patient has a disease) based on data tables.

However, when a company trains an XGBoost model, they keep the data and the final "recipe" (the model) secret. If a client wants to verify that the model wasn't faked or trained on bad data, they usually can't. They can't peek inside without breaking privacy laws or losing trade secrets.

2. The "Zero-Knowledge" Magic Trick

The paper introduces ZKBoost, which uses a cryptographic technique called Zero-Knowledge Proofs (ZKP).

Think of a Zero-Knowledge Proof like a magic mirror.

The chef stands in front of the mirror.
The mirror shows the client a glowing green checkmark saying, "Yes, the cooking happened correctly!"
But the mirror does not show the chef's face, the ingredients, or the recipe. It only proves the action was done right.

3. Why Was This So Hard Before?

The authors explain that doing this for XGBoost was like trying to prove you built a house by showing you laid every single brick, but you had to do it while blindfolded and in a language no one understood.

The "Blindfold" (Oblivious Partitioning): XGBoost works by constantly sorting data into different buckets (like sorting apples by size). Doing this in a "blind" cryptographic way is incredibly slow and expensive.
The "Secret Sauce" (Tree Splits): The model makes decisions based on hidden thresholds. Previous attempts to prove this were "leaky"—they accidentally revealed the shape of the decision trees (the topology), which is a trade secret.
The "Math Glitch" (Security Gaps): Some old methods allowed a dishonest prover to cheat by causing "math overflow" (like a calculator rolling over from 999 to 000) to fake a correct result.

4. The ZKBoost Solution: Two Big Tricks

The paper proposes two main innovations to fix these issues:

Trick A: The "Bottom-Up" Inspection (The Generic Template)

Normally, to verify a tree was built correctly, you'd have to re-run the whole cooking process from scratch, which is slow.

The Old Way: Watch the chef build the tree from the top down, step-by-step.
The ZKBoost Way: The authors created a new method called CertXGB. Instead of watching the chef build the tree, they look at the finished tree and work backwards (bottom-up).
- They check the leaves first, then the branches, then the trunk.
- This allows them to verify many trees at the same time (parallel processing), making the proof 3 to 6 times faster than previous methods.
- Crucially, this method checks the math without revealing which branches were cut off (pruning), keeping the tree's shape secret.

Trick B: The "Fixed-Point" Switch (The Security Fix)

XGBoost usually uses "floating-point" math (like 3.14159...), which is messy for cryptography because computers handle decimals differently on different machines.

The Problem: If the math isn't exact, the proof fails. Also, floating-point math is huge and slow to prove.
The Solution: The authors converted XGBoost to use Fixed-Point arithmetic.
- Analogy: Instead of measuring ingredients in "cups and fractions" (floating point), they measure everything in "tablespoons" (integers).
- They proved that even though they are using "tablespoons" instead of "cups," the final dish tastes exactly the same (within 1% accuracy) as the original floating-point version.
- This makes the math "proof-friendly," secure against overflow cheating, and much faster.

5. The Results: Fast and Secure

The authors tested their system on real-world datasets (like credit card fraud and cancer detection).

Speed: Their system is significantly faster than the closest competitor (Sparrow), especially when dealing with large amounts of data.
Accuracy: The "tablespoon" version (Fixed-Point) is just as accurate as the "cup" version (Floating-Point).
Security: They fixed the "math overflow" loopholes that allowed cheaters to fake results in previous systems.

Summary

ZKBoost is the first system that lets a model owner say, "I promise I trained this AI on your private data using our specific rules," and prove it with a cryptographic receipt. It does this by:

Checking the work backwards to save time.
Switching to simpler math (integers) to ensure security and speed.
Hiding the recipe and ingredients completely while still proving the cooking was honest.

This means clients can finally trust that the AI models they use are genuine, without forcing companies to reveal their trade secrets or private customer data.

Technical Summary: ZKBoost - Zero-Knowledge Verifiable Training for XGBoost

1. Problem Statement

As machine learning models, particularly Gradient Boosted Decision Trees (GBDTs) like XGBoost, are increasingly deployed in sensitive domains (e.g., finance, healthcare), there is a critical lack of cryptographic guarantees regarding model integrity. Clients cannot verify that a deployed model $M$ was genuinely trained on a specific dataset $D$ using prescribed hyperparameters without the model owner revealing proprietary data or model parameters.

Existing Zero-Knowledge Proof of Training (zkPoT) solutions face significant hurdles when applied to XGBoost:

Computational Inefficiency: Naively re-executing the XGBoost training process within a Zero-Knowledge Proof (ZKP) circuit is prohibitively expensive. This is due to the need for oblivious data partitioning at every node and the sequential nature of tree construction (where each tree depends on the predictions of previous trees).
Security Vulnerabilities: Previous works on ZK training and inference for decision trees suffer from subtle security flaws. These include potential leakage of tree topology and "soundness gaps" where a malicious prover could exploit modular arithmetic overflow to deviate from the correct training algorithm while still passing verification.
Numerical Incompatibility: Standard XGBoost relies on floating-point arithmetic, which is non-deterministic across hardware and incompatible with the finite-ring arithmetic required by most ZKP systems.

2. Methodology

The authors propose ZKBoost, the first zkPoT protocol specifically designed for XGBoost. The approach consists of three main technical pillars:

A. Fixed-Point XGBoost (TrainXGB)

To bridge the gap between standard XGBoost and ZKP requirements, the authors implement a fixed-point version of XGBoost.

Arithmetic: All operations (addition, multiplication, division) are performed on integers with an implicit global scaling factor, eliminating floating-point non-determinism.
Approximations: Non-linear functions essential to XGBoost, such as the sigmoid function ( $\sigma$ ) and log-odds ( $\sigma^{-1}$ ), are replaced with proof-friendly approximations (piecewise-linear and truncated Taylor expansions) that maintain accuracy within 1% of the standard floating-point implementation.
Determinism: This reformulation ensures that the training trace is unique and reproducible, forming a well-defined NP relation suitable for ZK verification.

B. Generic zkPoT Template (CertXGB)

Instead of re-executing the training process top-down (root to leaves), the authors design a certification algorithm, CertXGB, that verifies the training result bottom-up and in parallel.

Verification Logic: Given a claimed model $M$ $M$ (tree ensemble) and dataset $D$ $D$ , CertXGB:
1. Evaluates the trees on the data to determine leaf indices.
2. Reconstructs gradient and Hessian histograms from the leaves up to the root.
3. Verifies that the splits chosen by the prover maximize the gain derived from these reconstructed histograms.
4. Checks that leaf weights are consistent with the histograms.
Parallelism: This restructuring decouples the validation of individual trees from inter-tree dependencies, allowing multiple trees to be verified in parallel, significantly reducing prover costs.
Topology Hiding: To prevent leaking tree structure (e.g., which nodes were pruned), the protocol replaces pruned nodes with "dummy" values. The ZKP verifies obliviously that these dummies are used exactly when the pruning condition (gain $\le 0$ ) is met.

C. Secure Instantiation with VOLE-ZKP

The protocol is instantiated using a Vector Oblivious Linear Evaluation (VOLE)-based ZKP framework.

Subprotocols: The authors design specific ZK gadgets for critical non-linear operations:
- Comparison: Improved bit-decomposition proofs to prevent "wrap-around" attacks where a malicious prover could flip the Most Significant Bit (MSB) to alter comparison results.
- Division and Truncation: Proofs that handle large ranges of values without requiring thousands of constraints, ensuring soundness against modular overflow.
- Histogram Construction: A weighted LogUp proof replaces the more expensive ZK-RAM approach used in prior work, reducing overhead by approximately 3-4x.
Global Range Checks: The protocol enforces global range checks on intermediate values to prevent arithmetic overflow attacks that could break soundness.

3. Key Contributions

First zkPoT for XGBoost: The paper presents the first protocol enabling a model owner to prove correct training of an XGBoost model on a committed dataset without revealing data or parameters.
CertXGB Algorithm: A generic certification template that restructures training validation to be bottom-up and parallelizable, offering a significant improvement over naive re-execution.
Secure and Efficient Instantiation: A VOLE-based implementation that addresses soundness gaps found in previous ZK training works (specifically regarding overflow and topology leakage) while maintaining high efficiency.
Fixed-Point XGBoost: A practical, fixed-point implementation of XGBoost that matches standard floating-point accuracy within 1% on real-world datasets, making it compatible with ZKP arithmetic.

4. Experimental Results

The authors implemented ZKBoost in C++ and evaluated it on three real-world datasets: Breast Cancer, Credit Default, and Covertype.

Accuracy: The fixed-point XGBoost implementation achieves accuracy within 1% of standard floating-point XGBoost across all tested hyperparameter configurations and datasets.
Performance vs. Baseline: Compared to Sparrow (a related work for ordinary decision trees and random forests), ZKBoost is 3–6 times faster across various dataset sizes, despite providing stronger security guarantees (hiding tree topology and rigorous soundness checks).
Scalability:
- Tree Count: Proving time scales linearly with the number of trees.
- Dataset Size: Proving time is not significantly impacted by the number of data points (up to 100k), thanks to the efficient histogram construction proof.
Network Conditions: Experiments simulated both LAN (5 Gbps) and WAN (1 Gbps, 60ms latency) conditions. While WAN latency increases total time by ~83-87%, proofs are still generated in reasonable timeframes (e.g., ~52 minutes for a 100k dataset with 100 trees in WAN).

5. Significance and Claims

The paper claims to be the first to provide a practical, secure, and efficient zkPoT for XGBoost, a dominant algorithm in tabular data processing. The significance lies in:

Trustworthy ML-as-a-Service: Enabling clients to verify training integrity without exposing proprietary data.
Compliance: Allowing verification that models were trained on approved data sources (e.g., census data) or excluded protected content.
Security Advancements: The work identifies and patches specific soundness vulnerabilities (overflow attacks, topology leakage) in previous ZK training protocols, offering a more robust foundation for Zero-Knowledge Machine Learning (ZKML).
Practicality: By demonstrating that fixed-point arithmetic can match floating-point accuracy and that the protocol runs efficiently on commodity hardware, the authors argue that verifiable XGBoost training is feasible for real-world high-stakes applications like fraud detection and credit risk prediction.

The authors note that while the current instantiation targets binary classification, the framework can conceptually extend to multi-class classification, and future work could explore non-interactive succinct proofs for public verifiability.