기술 요약: ZKBoost - XGBoost 를 위한 영지식 증명 가능 학습

1. 문제 제기

머신러닝 모델, 특히 XGBoost 와 같은 경사 부스팅 결정 트리 (GBDT) 가 금융, 의료와 같은 민감한 분야에서 점점 더 배포됨에 따라, 모델 무결성에 대한 암호학적 보장의 부재가 치명적인 문제가 되고 있습니다. 클라이언트는 모델 소유자가 독점 데이터나 모델 매개변수를 공개하지 않고도 배포된 모델 $M$이 지정된 하이퍼파라미터를 사용하여 특정 데이터셋 $D$에 대해 진정으로 학습되었음을 검증할 수 없습니다.

기존의 학습에 대한 영지식 증명 (zkPoT) 솔루션은 XGBoost 에 적용될 때 다음과 같은 중대한 장애물에 직면합니다:

• 계산 비효율성: 영지식 증명 (ZKP) 회로 내에서 XGBoost 학습 과정을 순진하게 재실행하는 것은 과도하게 비용이 듭니다. 이는 각 노드에서 은밀한 데이터 분할이 필요하고, 트리 구성이 순차적 (각 트리가 이전 트리의 예측에 의존함) 이기 때문입니다.
• 보안 취약점: 결정 트리에 대한 이전의 ZK 학습 및 추론 작업들은 미묘한 보안 결함을 겪고 있습니다. 여기에는 트리 토폴로지의 잠재적 유출과 악의적인 증명자가 모듈 산술 오버플로우를 악용하여 올바른 학습 알고리즘에서 벗어나더라도 검증을 통과할 수 있는 '정합성 간격 (soundness gaps)'이 포함됩니다.
• 수치적 비호환성: 표준 XGBoost 는 부동 소수점 산술에 의존하는데, 이는 하드웨어 간에 비결정적이며 대부분의 ZKP 시스템에서 요구하는 유한 링 (finite-ring) 산술과 호환되지 않습니다.

2. 방법론

저자들은 XGBoost 를 위해 특별히 설계된 최초의 zkPoT 프로토콜인 ZKBoost를 제안합니다. 이 접근 방식은 세 가지 주요 기술적 기둥으로 구성됩니다:

A. 고정 소수점 XGBoost (TrainXGB)

표준 XGBoost 와 ZKP 요구 사항 간의 격차를 해소하기 위해, 저자들은 XGBoost 의 고정 소수점 버전을 구현합니다.

• 산술: 모든 연산 (덧셈, 곱셈, 나눗셈) 은 암시적인 전역 스케일링 인자가 있는 정수上进行 수행되어 부동 소수점의 비결정성을 제거합니다.
• 근사: 시그모이드 함수 ($\sigma$) 와 로그 오즈 ($\sigma^{-1}$) 와 같이 XGBoost 에 필수적인 비선형 함수는 표준 부동 소수점 구현의 정확도 내에서 1% 이내의 정확도를 유지하는 증명 친화적 근사 (구간 선형 및 절단된 테일러 전개) 로 대체됩니다.
• 결정성: 이 재구성은 학습 추적이 고유하고 재현 가능하도록 보장하여, ZK 검증에 적합한 잘 정의된 NP 관계를 형성합니다.

B. 범용 zkPoT 템플릿 (CertXGB)

저자들은 학습 과정을 위에서 아래로 (루트에서 리프까지) 재실행하는 대신, 학습 결과를 아래에서 위로 그리고 병렬로 검증하는 인증 알고리즘인 CertXGB를 설계합니다.

• 검증 논리: 주장된 모델 $M$(트리 앙상블) 과 데이터셋 $D$가 주어지면, CertXGB 는 다음을 수행합니다:
  1. 데이터에 트리를 평가하여 리프 인덱스를 결정합니다.
  2. 리프에서 루트까지 그래디언트 및 헤시안 히스토그램을 재구성합니다.
  3. 증명자가 선택한 분할이 재구성된 히스토그램에서 유도된 이득을 최대화하는지 검증합니다.
  4. 리프 가중치가 히스토그램과 일관성이 있는지 확인합니다.
• 병렬성: 이 재구성은 개별 트리의 검증을 트리 간 의존성에서 분리하여 여러 트리를 병렬로 검증할 수 있게 하므로, 증명자 비용을 크게 줄입니다.
• 토폴로지 숨김: 트리 구조 (예: 어떤 노드가 가지치기되었는지) 가 유출되는 것을 방지하기 위해, 프로토콜은 가지치기된 노드를 '더미 (dummy)' 값으로 대체합니다. ZKP 는 가지치기 조건 (이득 $\le 0$) 이 충족될 때 이러한 더미가 정확히 사용됨을 은밀하게 검증합니다.

C. VOLE-ZKP 를 통한 안전한 인스턴스화

프로토콜은 벡터 은밀 선형 평가 (VOLE) 기반 ZKP 프레임워크를 사용하여 인스턴스화됩니다.

• 서브프로토콜: 저자들은 중요한 비선형 연산을 위한 특정 ZK 가젯을 설계합니다:
  • 비교: 악의적인 증명자가 비교 결과를 변경하기 위해 가장 중요한 비트 (MSB) 를 뒤집을 수 있는 '랩어라운드 (wrap-around)' 공격을 방지하기 위해 개선된 비트 분해 증명을 사용합니다.
  • 나눗셈 및 절단: 수천 개의 제약 조건을 요구하지 않고 넓은 범위의 값을 처리하는 증명을 통해 모듈 오버플로우에 대한 정합성을 보장합니다.
  • 히스토그램 구성: 이전 작업에서 사용된 더 비싼 ZK-RAM 접근 방식을 대체하는 가중 LogUp 증명을 사용하여 오버헤드를 약 3-4 배 줄입니다.
• 전역 범위 검사: 정합성을 깨뜨릴 수 있는 산술 오버플로우 공격을 방지하기 위해 프로토콜은 중간 값에 전역 범위 검사를 적용합니다.

3. 주요 기여

1. XGBoost 를 위한 최초의 zkPoT: 이 논문은 모델 소유자가 데이터나 매개변수를 공개하지 않고도 커밋된 데이터셋에 대한 XGBoost 모델의 올바른 학습을 증명할 수 있는 최초의 프로토콜을 제시합니다.
2. CertXGB 알고리즘: 학습 검증을 아래에서 위로 그리고 병렬화 가능하도록 재구성하는 범용 인증 템플릿으로, 순진한 재실행에 비해 상당한 개선을 제공합니다.
3. 안전하고 효율적인 인스턴스화: 이전 ZK 학습 작업에서 발견된 정합성 간격 (특히 오버플로우 및 토폴로지 유출과 관련하여) 을 해결하면서도 높은 효율성을 유지하는 VOLE 기반 구현입니다.
4. 고정 소수점 XGBoost: 실제 데이터셋에서 표준 부동 소수점 정확도 within 1% 이내를 달성하는 실용적인 고정 소수점 XGBoost 구현으로, ZKP 산술과 호환되도록 합니다.

4. 실험 결과

저자들은 C++ 로 ZKBoost 를 구현하고 Breast Cancer, Credit Default, Covertype 의 세 가지 실제 데이터셋에서 평가했습니다.

• 정확도: 고정 소수점 XGBoost 구현은 모든 테스트된 하이퍼파라미터 구성과 데이터셋에서 표준 부동 소수점 XGBoost 와 1% 이내의 정확도를 달성합니다.
• 기존 작업 대비 성능: 일반 결정 트리와 랜덤 포레스트를 위한 관련 작업인 Sparrow와 비교할 때, ZKBoost 는 더 강력한 보안 보장 (트리 토폴로지 숨김 및 엄격한 정합성 검사) 을 제공함에도 불구하고 다양한 데이터셋 크기에서 3~6 배 더 빠릅니다.
• 확장성:
  • 트리 수: 증명 시간은 트리의 수에 비례하여 선형적으로 증가합니다.
  • 데이터셋 크기: 효율적인 히스토그램 구성 증명 덕분에 데이터 포인트 수 (최대 10 만 개) 에 따라 증명 시간이 크게 영향을 받지 않습니다.
• 네트워크 조건: LAN(5 Gbps) 과 WAN(1 Gbps, 60ms 지연 시간) 조건을 모두 시뮬레이션했습니다. WAN 지연 시간은 총 시간을 약 83-87% 증가시키지만, 증명은 여전히 합리적인 시간 내에 생성됩니다 (예: WAN 에서 10 만 개 데이터셋과 100 개의 트리에 대해 약 52 분).

5. 중요성 및 주장

이 논문은 표 데이터 처리에서 지배적인 알고리즘인 XGBoost 에 대한 실용적이고 안전하며 효율적인 zkPoT 를 최초로 제공한다고 주장합니다. 그 중요성은 다음과 같습니다:

• 신뢰할 수 있는 ML-as-a-Service: 클라이언트가 독점 데이터를 노출하지 않고도 학습 무결성을 검증할 수 있게 합니다.
• 준수: 모델이 승인된 데이터 소스 (예: 인구 조사 데이터) 로 학습되었거나 보호된 콘텐츠가 제외되었음을 검증할 수 있게 합니다.
• 보안 진전: 이 작업은 이전 ZK 학습 프로토콜의 특정 정합성 취약점 (오버플로우 공격, 토폴로지 유출) 을 식별하고 패치하여, 영지식 머신러닝 (ZKML) 을 위한 더 견고한 기반을 제공합니다.
• 실용성: 고정 소수점 산술이 부동 소수점 정확도와 일치할 수 있음을 증명하고 프로토콜이 상용 하드웨어에서 효율적으로 실행됨을 보여줌으로써, 저자들은 사기 탐지 및 신용 위험 예측과 같은 실제의 고위험 애플리케이션에 검증 가능한 XGBoost 학습이 가능하다고 주장합니다.

저자들은 현재 인스턴스화가 이진 분류를 대상으로 하지만, 프레임워크는 개념적으로 다중 클래스 분류로 확장될 수 있으며, 향후 작업은 공개 검증을 위한 비상호적 간결 증명을 탐구할 수 있다고 언급합니다.