Riepilogo Tecnico: ZKBoost - Addestramento Verificabile a Conoscenza Zero per XGBoost

1. Enunciato del Problema

Man mano che i modelli di machine learning, in particolare gli Alberi Decisionali con Boosting Graduale (GBDT) come XGBoost, vengono sempre più distribuiti in domini sensibili (ad esempio, finanza, sanità), si riscontra una grave mancanza di garanzie crittografiche riguardo all'integrità del modello. I clienti non possono verificare che un modello $M$ distribuito sia stato genuinamente addestrato su un specifico dataset $D$ utilizzando gli iperparametri prescritti, senza che il proprietario del modello riveli dati proprietari o parametri del modello.

Le soluzioni esistenti di Prova di Addestramento a Conoscenza Zero (zkPoT) incontrano ostacoli significativi quando applicate a XGBoost:

• Inefficienza Computazionale: Riecheggiare in modo ingenuo il processo di addestramento di XGBoost all'interno di un circuito di Prova a Conoscenza Zero (ZKP) è proibitivamente costoso. Ciò è dovuto alla necessità di partizionamento dei dati cieco a ogni nodo e alla natura sequenziale della costruzione dell'albero (dove ogni albero dipende dalle previsioni degli alberi precedenti).
• Vulnerabilità di Sicurezza: I lavori precedenti su addestramento e inferenza ZK per alberi decisionali soffrono di sottili difetti di sicurezza. Questi includono potenziali fughe di informazioni sulla topologia dell'albero e "lacune di correttezza" (soundness gaps) in cui un provatore malevolo potrebbe sfruttare l'overflow dell'aritmetica modulare per discostarsi dall'algoritmo di addestramento corretto pur superando comunque la verifica.
• Incompatibilità Numerica: XGBoost standard si basa sull'aritmetica in virgola mobile, che è non deterministica tra diversi hardware e incompatibile con l'aritmetica ad anello finito richiesta dalla maggior parte dei sistemi ZKP.

2. Metodologia

Gli autori propongono ZKBoost, il primo protocollo zkPoT specificamente progettato per XGBoost. L'approccio si compone di tre pilastri tecnici principali:

A. XGBoost a Punto Fisso (TrainXGB)

Per colmare il divario tra XGBoost standard e i requisiti ZKP, gli autori implementano una versione a punto fisso di XGBoost.

• Aritmetica: Tutte le operazioni (addizione, moltiplicazione, divisione) sono eseguite su interi con un fattore di scala globale implicito, eliminando la non deterministica della virgola mobile.
• Approssimazioni: Le funzioni non lineari essenziali per XGBoost, come la funzione sigmoide ($\sigma$) e i log-odds ($\sigma^{-1}$), sono sostituite con approssimazioni compatibili con le prove (espansioni lineari a tratti e serie di Taylor troncate) che mantengono un'accuratezza entro l'1% rispetto all'implementazione standard in virgola mobile.
• Determinismo: Questa riformulazione garantisce che la traccia di addestramento sia unica e riproducibile, formando una relazione NP ben definita adatta alla verifica ZK.

B. Modello Generico zkPoT (CertXGB)

Invece di rieseguire il processo di addestramento dall'alto verso il basso (dalla radice alle foglie), gli autori progettano un algoritmo di certificazione, CertXGB, che verifica il risultato dell'addestramento dal basso verso l'alto e in parallelo.

• Logica di Verifica: Dato un modello rivendicato $M$ (insieme di alberi) e un dataset $D$, CertXGB:
  1. Valuta gli alberi sui dati per determinare gli indici delle foglie.
  2. Ricostruisce gli istogrammi del gradiente e dell'Hessian dalle foglie fino alla radice.
  3. Verifica che le divisioni scelte dal provatore massimizzino il guadagno derivato da questi istogrammi ricostruiti.
  4. Controlla che i pesi delle foglie siano coerenti con gli istogrammi.
• Parallelismo: Questa ristrutturazione disaccoppia la convalida dei singoli alberi dalle dipendenze inter-albero, permettendo la verifica di più alberi in parallelo, riducendo significativamente i costi per il provatore.
• Nascita della Topologia: Per prevenire la fuga di informazioni sulla struttura dell'albero (ad esempio, quali nodi sono stati potati), il protocollo sostituisce i nodi potati con valori "finti" (dummy). Lo ZKP verifica in modo cieco che questi dummy vengano utilizzati esattamente quando la condizione di potatura (guadagno $\le 0$) è soddisfatta.

C. Istanza Sicura con VOLE-ZKP

Il protocollo è istanziato utilizzando un framework ZKP basato sulla Valutazione Lineare Cieca di Vettori (VOLE).

• Sottoprotocolli: Gli autori progettano gadget ZK specifici per operazioni non lineari critiche:
  • Confronto: Prove di decomposizione in bit migliorate per prevenire attacchi di "wrap-around" in cui un provatore malevolo potrebbe invertire il Bit più Significativo (MSB) per alterare i risultati del confronto.
  • Divisione e Troncamento: Prove che gestiscono ampi intervalli di valori senza richiedere migliaia di vincoli, garantendo la correttezza contro l'overflow modulare.
  • Costruzione dell'Istogramma: Una prova LogUp ponderata sostituisce l'approccio ZK-RAM più costoso utilizzato nei lavori precedenti, riducendo l'overhead di circa 3-4 volte.
• Controlli di Intervallo Globali: Il protocollo impone controlli di intervallo globali sui valori intermedi per prevenire attacchi di overflow aritmetico che potrebbero compromettere la correttezza.

3. Contributi Chiave

1. Primo zkPoT per XGBoost: Il documento presenta il primo protocollo che permette a un proprietario di modello di provare l'addestramento corretto di un modello XGBoost su un dataset impegnato senza rivelare dati o parametri.
2. Algoritmo CertXGB: Un modello generico di certificazione che ristruttura la convalida dell'addestramento rendendola dal basso verso l'alto e parallelizzabile, offrendo un miglioramento significativo rispetto alla riesecuzione ingenua.
3. Istanza Sicura ed Efficiente: Un'implementazione basata su VOLE che affronta le lacune di correttezza riscontrate nei precedenti lavori di addestramento ZK (in particolare riguardo a overflow e fuga di topologia) mantenendo al contempo un'alta efficienza.
4. XGBoost a Punto Fisso: Un'implementazione pratica di XGBoost a punto fisso che corrisponde all'accuratezza standard in virgola mobile entro l'1% su dataset reali, rendendolo compatibile con l'aritmetica ZKP.

4. Risultati Sperimentali

Gli autori hanno implementato ZKBoost in C++ e lo hanno valutato su tre dataset reali: Cancro al Seno, Default di Credito e Covertype.

• Accuratezza: L'implementazione di XGBoost a punto fisso raggiunge un'accuratezza entro l'1% rispetto a XGBoost standard in virgola mobile su tutte le configurazioni di iperparametri e dataset testati.
• Prestazioni rispetto alla Baseline: Rispetto a Sparrow (un lavoro correlato per alberi decisionali ordinari e foreste casuali), ZKBoost è 3–6 volte più veloce su varie dimensioni di dataset, nonostante offra garanzie di sicurezza più forti (nascita della topologia dell'albero e controlli rigorosi di correttezza).
• Scalabilità:
  • Numero di Alberi: Il tempo di prova scala linearmente con il numero di alberi.
  • Dimensione del Dataset: Il tempo di prova non è significativamente influenzato dal numero di punti dati (fino a 100k), grazie alla prova efficiente di costruzione dell'istogramma.
• Condizioni di Rete: Gli esperimenti hanno simulato condizioni sia LAN (5 Gbps) che WAN (1 Gbps, latenza di 60 ms). Sebbene la latenza WAN aumenti il tempo totale di circa l'83-87%, le prove vengono ancora generate in tempi ragionevoli (ad esempio, circa 52 minuti per un dataset di 100k con 100 alberi in WAN).

5. Significato e Affermazioni

Il documento afferma di essere il primo a fornire uno zkPoT pratico, sicuro ed efficiente per XGBoost, un algoritmo dominante nell'elaborazione di dati tabulari. Il significato risiede in:

• ML-as-a-Service Affidabile: Consentire ai clienti di verificare l'integrità dell'addestramento senza esporre dati proprietari.
• Conformità: Permettere la verifica che i modelli siano stati addestrati su fonti di dati approvate (ad esempio, dati censuari) o che abbiano escluso contenuti protetti.
• Avanzamenti nella Sicurezza: Il lavoro identifica e risolve specifiche vulnerabilità di correttezza (attacchi di overflow, fuga di topologia) nei precedenti protocolli di addestramento ZK, offrendo una base più robusta per il Machine Learning a Conoscenza Zero (ZKML).
• Praticità: Dimostrando che l'aritmetica a punto fisso può corrispondere all'accuratezza in virgola mobile e che il protocollo funziona efficientemente su hardware commerciale, gli autori sostengono che l'addestramento verificabile di XGBoost è fattibile per applicazioni reali ad alto rischio come il rilevamento delle frodi e la previsione del rischio creditizio.

Gli autori notano che, sebbene l'istanza corrente sia mirata alla classificazione binaria, il framework può concettualmente estendersi alla classificazione multiclasse, e un lavoro futuro potrebbe esplorare prove succinte non interattive per la verificabilità pubblica.