Paper 2026/907

Zero-Knowledge Proofs for Gradient Boosted Decision Trees

Abstract

Gradient boosted decision trees (GBDTs) are widely used for tabular data in finance, healthcare, and risk ssessment. As GBDT training and inference are increasingly outsourced, clients need to verify that models are trained as claimed and predictions are consistent with those models, while providers may need to keep training data and model parameters private. This makes zero-knowledge proofs for GBDT training and inference a natural solution. Existing approaches typically compile training certification into circuits and prove their execution using generic ZKP backends, incurring high prover costs. Directly proving the underlying algebraic relations offers an alternative, but proving each relation separately incurs substantial costs for committing to and opening auxiliary witnesses. Batching is challenging because these witnesses have different shapes and sizes and are encoded over different domains. We present \textsc{Terrae}, a zero-knowledge proof system for quantized GBDT training and inference based on KZG polynomial commitments. \textsc{Terrae} avoids both proving circuit computation and proving each constraint separately by leveraging the structure of GBDT training and two new batching techniques: domain-lifting batching for low-degree algebraic constraints and interleaving batching for same-form non-native constraints. Both techniques work over differently-sized domains and reduce many constraints to a single claim without introducing extra polynomial commitments. We also design a histogram proof that proves the correctness of aggregating sample-wise updates into histograms, which may be of independent interest. Our evaluation shows that, compared with prior work CertXGB instantiated with the same KZG backend, \textsc{Terrae} achieves proof-generation speedups of $3.18$--$13.55\times$ for training and $1.96$--$4.31\times$ for inference across completed benchmark comparisons, with lower peak prover memory, at the cost of moderately larger proofs and higher verification time.