Résumé Technique : ZKBoost - Entraînement Vérifiable à Connaissance Nulle pour XGBoost

1. Énoncé du Problème

À mesure que les modèles d'apprentissage automatique, en particulier les arbres de décision à gradient boosté (GBDT) comme XGBoost, sont de plus en plus déployés dans des domaines sensibles (par exemple, la finance, la santé), il existe une carence critique en garanties cryptographiques concernant l'intégrité du modèle. Les clients ne peuvent pas vérifier qu'un modèle déployé $M$ a été véritablement entraîné sur un jeu de données spécifique $D$ en utilisant des hyperparamètres prescrits, sans que le propriétaire du modèle révèle des données propriétaires ou des paramètres du modèle.

Les solutions existantes de Preuve à Connaissance Nulle d'Entraînement (zkPoT) rencontrent des obstacles majeurs lorsqu'elles sont appliquées à XGBoost :

• Inefficacité Computationnelle : Réexécuter naïvement le processus d'entraînement de XGBoost au sein d'un circuit de Preuve à Connaissance Nulle (ZKP) est prohibitivement coûteux. Cela est dû à la nécessité d'une partition de données aveugle à chaque nœud et à la nature séquentielle de la construction de l'arbre (où chaque arbre dépend des prédictions des arbres précédents).
• Vulnérabilités de Sécurité : Les travaux antérieurs sur l'entraînement et l'inférence à connaissance nulle pour les arbres de décision souffrent de failles de sécurité subtiles. Ceux-ci incluent une fuite potentielle de la topologie de l'arbre et des « lacunes de justesse » où un prouveur malveillant pourrait exploiter un débordement d'arithmétique modulaire pour s'écarter de l'algorithme d'entraînement correct tout en passant la vérification.
• Incompatibilité Numérique : XGBoost standard repose sur l'arithmétique à virgule flottante, qui est non déterministe sur différents matériels et incompatible avec l'arithmétique d'anneau fini requise par la plupart des systèmes ZKP.

2. Méthodologie

Les auteurs proposent ZKBoost, le premier protocole zkPoT spécifiquement conçu pour XGBoost. L'approche repose sur trois piliers techniques principaux :

A. XGBoost à Point Fixe (TrainXGB)

Pour combler le fossé entre XGBoost standard et les exigences des ZKP, les auteurs implémentent une version à point fixe de XGBoost.

• Arithmétique : Toutes les opérations (addition, multiplication, division) sont effectuées sur des entiers avec un facteur d'échelle global implicite, éliminant le non-déterminisme des virgules flottantes.
• Approximations : Les fonctions non linéaires essentielles à XGBoost, telles que la fonction sigmoïde ($\sigma$) et les log-odds ($\sigma^{-1}$), sont remplacées par des approximations compatibles avec les preuves (linéaires par morceaux et développements de Taylor tronqués) qui maintiennent une précision dans une marge de 1 % par rapport à l'implémentation standard à virgule flottante.
• Déterminisme : Cette reformulation garantit que la trace d'entraînement est unique et reproductible, formant une relation NP bien définie adaptée à la vérification ZK.

B. Modèle Générique zkPoT (CertXGB)

Au lieu de réexécuter le processus d'entraînement de haut en bas (de la racine aux feuilles), les auteurs conçoivent un algorithme de certification, CertXGB, qui vérifie le résultat de l'entraînement de bas en haut et en parallèle.

• Logique de Vérification : Étant donné un modèle revendiqué $M$ (ensemble d'arbres) et un jeu de données $D$, CertXGB :
  1. Évalue les arbres sur les données pour déterminer les indices des feuilles.
  2. Reconstruit les histogrammes de gradient et de Hessien depuis les feuilles jusqu'à la racine.
  3. Vérifie que les séparations choisies par le prouveur maximisent le gain dérivé de ces histogrammes reconstruits.
  4. Vérifie que les poids des feuilles sont cohérents avec les histogrammes.
• Parallélisme : Cette restructuration découple la validation des arbres individuels des dépendances inter-arbres, permettant de vérifier plusieurs arbres en parallèle, réduisant ainsi considérablement les coûts pour le prouveur.
• Cachage de la Topologie : Pour empêcher la fuite de la structure de l'arbre (par exemple, quels nœuds ont été élagués), le protocole remplace les nœuds élagués par des valeurs « factices ». Le ZKP vérifie de manière aveugle que ces factices sont utilisés exactement lorsque la condition d'élagage (gain $\le 0$) est remplie.

C. Instantiation Sécurisée avec VOLE-ZKP

Le protocole est instancié en utilisant un cadre ZKP basé sur l'Évaluation Linéaire Aveugle Vectorielle (VOLE).

• Sous-protocoles : Les auteurs conçoivent des gadgets ZK spécifiques pour les opérations non linéaires critiques :
  • Comparaison : Preuves de décomposition de bits améliorées pour prévenir les attaques de « dépassement » où un prouveur malveillant pourrait inverser le bit de poids fort (MSB) pour altérer les résultats de comparaison.
  • Division et Troncature : Preuves qui gèrent de grandes plages de valeurs sans nécessiter des milliers de contraintes, assurant la justesse contre les débordements modulaires.
  • Construction d'Histogramme : Une preuve LogUp pondérée remplace l'approche ZK-RAM plus coûteuse utilisée dans les travaux antérieurs, réduisant la surcharge d'environ 3 à 4 fois.
• Vérifications de Plages Globales : Le protocole impose des vérifications de plages globales sur les valeurs intermédiaires pour prévenir les attaques par débordement arithmétique qui pourraient briser la justesse.

3. Contributions Clés

1. Premier zkPoT pour XGBoost : L'article présente le premier protocole permettant à un propriétaire de modèle de prouver l'entraînement correct d'un modèle XGBoost sur un jeu de données engagé sans révéler les données ou les paramètres.
2. Algorithme CertXGB : Un modèle de certification générique qui restructure la validation de l'entraînement pour être de bas en haut et parallélisable, offrant une amélioration significative par rapport à la réexécution naïve.
3. Instantiation Sécurisée et Efficace : Une implémentation basée sur VOLE qui comble les lacunes de justesse trouvées dans les travaux précédents sur l'entraînement ZK (spécifiquement concernant les débordements et la fuite de topologie) tout en maintenant une haute efficacité.
4. XGBoost à Point Fixe : Une implémentation pratique de XGBoost à point fixe qui correspond à la précision des virgules flottantes standard à moins de 1 % sur des jeux de données réels, la rendant compatible avec l'arithmétique ZKP.

4. Résultats Expérimentaux

Les auteurs ont implémenté ZKBoost en C++ et l'ont évalué sur trois jeux de données réels : Cancer du sein, Défaut de Crédit et Covertype.

• Précision : L'implémentation de XGBoost à point fixe atteint une précision dans une marge de 1 % par rapport à XGBoost standard à virgule flottante sur toutes les configurations d'hyperparamètres et jeux de données testés.
• Performance par rapport à la Référence : Comparé à Sparrow (un travail connexe pour les arbres de décision ordinaires et les forêts aléatoires), ZKBoost est 3 à 6 fois plus rapide à travers diverses tailles de jeux de données, malgré l'offre de garanties de sécurité plus fortes (cachage de la topologie de l'arbre et vérifications rigoureuses de justesse).
• Évolutivité :
  • Nombre d'Arbres : Le temps de preuve évolue linéairement avec le nombre d'arbres.
  • Taille du Jeu de Données : Le temps de preuve n'est pas significativement affecté par le nombre de points de données (jusqu'à 100k), grâce à la preuve de construction d'histogramme efficace.
• Conditions Réseau : Les expériences ont simulé des conditions LAN (5 Gbps) et WAN (1 Gbps, latence de 60 ms). Bien que la latence WAN augmente le temps total d'environ 83-87 %, les preuves sont toujours générées dans des délais raisonnables (par exemple, environ 52 minutes pour un jeu de données de 100k avec 100 arbres en WAN).

5. Importance et Revendications

L'article revendique être le premier à fournir un zkPoT pratique, sécurisé et efficace pour XGBoost, un algorithme dominant dans le traitement de données tabulaires. L'importance réside dans :

• ML-as-a-Service digne de Confiance : Permettre aux clients de vérifier l'intégrité de l'entraînement sans exposer de données propriétaires.
• Conformité : Permettre de vérifier que les modèles ont été entraînés sur des sources de données approuvées (par exemple, données de recensement) ou ont exclu du contenu protégé.
• Avancées en Sécurité : Le travail identifie et corrige des vulnérabilités de justesse spécifiques (attaques par débordement, fuite de topologie) dans les protocoles d'entraînement ZK précédents, offrant une base plus robuste pour l'Apprentissage Automatique à Connaissance Nulle (ZKML).
• Praticité : En démontrant que l'arithmétique à point fixe peut correspondre à la précision des virgules flottantes et que le protocole s'exécute efficacement sur du matériel standard, les auteurs soutiennent que l'entraînement vérifiable de XGBoost est réalisable pour des applications réelles à haut risque comme la détection de fraude et la prédiction du risque de crédit.

Les auteurs notent que bien que l'instanciation actuelle cible la classification binaire, le cadre peut conceptuellement s'étendre à la classification multi-classes, et des travaux futurs pourraient explorer des preuves succinctes non interactives pour la vérifiabilité publique.