\texttt{Range-Arithmetic}: Verifiable Deep Learning Inference on an Untrusted Party

기술 요약: Range-Arithmetic – 신뢰할 수 없는 제3자에 대한 검증 가능한 딥러닝 추론

문제 정의
탈중앙화 머신러닝(ML) 시스템은 블록체인의 한계를 극복하기 위해, 자원 집약적인 작업(예: 심층 신경망(DNN) 추론)을 신뢰할 수 없는 외부 당사자(증명자)에게 오프로딩하는 방식에 점점 더 의존하고 있습니다. 이 패러다임에서 핵심적인 과제는 검증자가 전체 과정을 재실행하는 비용이 매우 높기 때문에, 이러한 위탁된 계산의 무결성을 보장하면서도 재실행 없이 이를 수행하는 것입니다.

기존의 검증 가능한 컴퓨팅(VC) 기술은 ML에 적용될 때 상당한 장애물에 직면합니다. 대부분의 VC 스킴은 유한체(finite field) 상에서 작동하며 산술 연산(덧셈 및 곱셈)으로 제한됩니다. 그러나 표준 ML 계산에는 다음과 같은 비산술적 연산이 포함됩니다:

1. 고정 소수점 반올림(Fixed-point rounding): 행렬 곱셈 후 정밀도를 관리하고 오버플로를 방지하기 위해 필요합니다.
2. 비선형 활성화 함수: ReLU(Rectified Linear Unit)와 같은 함수입니다.

이러한 연산을 기존 VC 프레임워크 내에서 표현하려면 복잡한 불리언 회로 인코딩, 고차 다항식 또는 대규모 사전 계산 룩업 테이블(lookup table)이 필요합니다. 이러한 접근 방식은 증명자의 노력, 검증자 비용, 통신 대역폭에 상당한 오버헤드를 발생시키거나, ReLU와 반올림을 동시에 지원하지 못하는 문제를 야기합니다.

방법론: Range-Arithmetic 프레임워크
저자들은 유한체 기반의 증명 시스템과 호환성을 유지하면서 DNN 추론을 효율적으로 검증하도록 설계된 새로운 프레임워크인 Range-Arithmetic을 제안합니다. 핵심 혁신은 비산술적 연산을 sum-check 프로토콜과 결합된 범위 증명(range proofs)을 통해 검증 가능한 산술 단계로 변환함으로써, 불리언 인코딩이나 대규모 룩업 테이블을 피하는 데 있습니다.

이 프레임워크는 다음 메커니즘을 통해 작동합니다:

1. 행렬 곱셈 검증:
   행렬 곱셈($C = AB$)의 검증은 sum-check 문제로 재구성됩니다. 행렬 요소를 유한체 상의 다변량 확장(Multilinear Extensions, MLE)으로 표현함으로써, 곱셈의 정확성을 다항식 항등성을 검증하는 문제로 환원합니다. 저자들은 Schwartz-Zippel 보조정리를 활용하여 임의의 점(random points)에서 이 항등성을 확인하며, sum-check 프로토콜을 사용하여 통신 복잡도를 $O(\log n)$으로 줄입니다.

2. 반올림 검증:
   곱셈 후에 적용되는 반올림 연산 $R(x)$를 검증하기 위해, 저자들은 이 과정을 산술적 제약 조건으로 분해합니다. 반올림 과정에서 버려지는 부분($E$)과 반올림 분수의 분자($D$)를 정의합니다. 정확성은 **집계된 범위 증명(aggregated range proofs)**을 통해 두 가지 조건을 증명함으로써 보장됩니다:

   • 버려지는 비트가 특정 작은 구간($-2^{s-1} \leq e_i < 2^{s-1}$) 내에 존재함.
   • 남은 값이 오버플로(wrap-around) 없이 $2^s$의 정수 배임.
     이 접근 방식은 오버플로를 방지하기 위해 큰 유한체를 요구하지 않고도 표준 범위 증명을 사용하여 반올림을 검증할 수 있게 합니다.

3. ReLU 검증:
   $\text{ReLU}(x) = \max(0, x) = (x + |x|)/2$로 정의되는 ReLU 함수는 다음과 같이 검증됩니다:

   • 범위 증명을 사용하여 절대값 $Y = |A|$가 비음수임을 증명합니다.
   • sum-check 프로토콜을 사용하여 모든 요소에 대해 $a_i^2 = y_i^2$임을 증명합니다(다항식 $f(x) = \tilde{I}(s, x)(\tilde{a}^2(x) - \tilde{y}^2(x))$ 사용).
   • 최종 선형 결합 $B = (A + Y)/2$를 검증합니다.

4. 구성(Composition):
   프레임워크는 신경망 추론을 레이어의 시퀀스로 취급합니다. 각 레이어(행렬 곱셈과 반올림 또는 ReLU 활성화)는 독립적으로 검증됩니다. 한 레이어의 출력 커밋먼트(output commitment)는 다음 레이어의 입력으로 사용되어, 대규모 중간 행렬을 다시 전송하지 않고도 검증 알고리즘의 모듈형 구성을 가능하게 합니다.

주요 기여
본 논문은 다음과 같은 구체적인 기여를 주장합니다:

• 통합 프레임워크: Range-Arithmetic은 고정 소수점 반올림과 ReLU를 모두 지원하면서 $O(n^3)$ 증명자 복잡도, $O(n^2)$ 검증자 복잡도, $O(\log n)$ 통신 복잡도를 동시에 달성한 최초의 방법입니다.
• 오버헤드 제거: 이 방식은 이전 연구들에서 흔히 나타나는 불리언 회로 인코딩, 큰 유한체(오버플로 방지용), 대규모 사전 계산 룩업 테이블의 필요성을 제거합니다.
• 전처리 없음: R1CS 기반 또는 산술 회로 방식과 달리, 이 방법은 전처리나 인코딩 오버헤드를 요구하지 않습니다.
• 실용성: 오버플로를 피하기 위해 유한체를 확장할 필요가 없으므로, 암호학적 크기의 소수(primes)를 사용하는 환경에서도 실용적입니다.

실험 결과
저자들은 선형 신경 네트워크와 MNIST 데이터셋(6비트 정수 및 8비트 소수점 사용)으로 학습된 4개 레이어 완전 연결 네트워크 사례 연구를 통해 제안된 알고리즘을 평가했습니다.

• 성능 비교: ReLU 지원이 부족하고 필드 확장이 필요한 최신 방법[20]과 비교했을 때, Range-Arithmetic은 네트워크 레이어 수가 증가함에 따라 우수한 성능을 보여주었습니다.
• 지표: 제안된 방법은 증명자와 검증자 모두의 계산 비용을 줄였으며, 통신 오버헤드도 낮추었습니다.
• 상세 수치: MNIST 사례 연구에서 증명자 실행 시간은 약 230밀리초, 검증자 실행 시간은 약 154밀리초였습니다.
• 확장성: 행렬 크기가 커짐에 따라 통신 비용은 로그 단위로 증가한 반면, 증명자 및 검증자 실행 시간은 다항식 규모로 확장되었습니다.

의의 및 주장
본 논문은 Range-Arithmetic이 신뢰할 수 없는 당사자에 대한 검증 가능한 DNN 추론에 있어 증명자 노력, 검증자 비용, 통신, 그리고 기능적 완전성 사이에서 "가장 균형 잡힌 트레이드오프"를 제공한다고 위치시킵니다. 저자들은 순수 ReLU 검증에는 룩업 기반 방식이 더 빠를 수 있지만, 대규모 보조 테이블을 요구한다는 점에서 자원이 제한된 검증자에게는 부적절하다고 강조합니다. Range-Arithmetic은 이러한 테이블을 경량 범위 증명으로 대체하여, 특정 제약 조건이 있는 탈중앙화 ML 시스템에 더 일반적이고 효율적인 솔루션을 제공합니다. 이 연구는 재실행 없이도 복잡한 비산술적 ML 연산을 효율적으로 검증할 수 있게 함으로써, 개방적이고 역동적인 환경에서 신뢰할 수 있고 자율적인 AI 애플리케이션을 촉진하는 것을 목표로 합니다.