증명이 하드웨어를 만날 때: 영지식 시스템에서의 NTT와 SumCheck 비교

ZKP(Zero-Knowledge Proof) 커뮤니티에서는 SumCheck 프로토콜이 Number Theoretic Transform (NTT)보다 점근적으로 더 효율적이라는 논의가 오랫동안 지속되어 왔습니다. NTT는 $O(N ext{ log } N)$의 연산이 필요한 반면, SumCheck은 $O(N)$의 산술 연산만을 필요로 하기 때문입니다. 동시에, 하드웨어 가속기 설계자들은 NTT가 지역성(locality)과 데이터 재사용(data reuse)의 이점을 얻어 하드웨어 친화적이라고 제안하는 반면, SumCheck은 순차적이고 의존적인 라운드(rounds)로 인해 어려움을 겪는다고 주장합니다. 이러한 상충하는 직관에도 불구하고, NTT 기반과 SumCheck 기반 증명 프리미티브(proving primitives) 사이의 하드웨어-시스템 수준의 트레이드오프(trade-offs)는 여전히 충분히 이해되지 않은 상태로 남아 있습니다. 개별 가속기 설계를 넘어, 본 연구는 우리가 아는 한 통합된 아키텍처 프레임워크 하에서 NTT 기반 및 SumCheck 기반 증명 프리미티브를 하드웨어-시스템 수준에서 직접 비교한 첫 번째 사례를 제시합니다. 우리는 zkSNARKs의 공통 빌딩 블록인 ZeroCheck 프로토콜의 맥락에서 이들을 연구합니다. 우리는 두 프리미티브 모두에 대해 최적화된 시스템을 구현했습니다. 두 방식 모두 동일한 수준의 온칩(on-chip) SRAM 및 오프칩(off-chip) 대역폭 예산 하에서 평가되었습니다. 우리의 결과는 보편적인 승자는 없다는 것을 보여줍니다. 일반적으로 SumCheck은 고차 다항식(high-degree polynomials)에 대해 NTT보다 우수한 성능을 보입니다. 저차 다항식(low-degree polynomials)의 경우, 성능은 메모리 가용성에 따라 달라집니다. 주어진 SRAM 예산 하에서, NTT는 데이터 재사용을 활용함으로써 중간 규모의 워크로드(workloads)에 대해 더 나은 성능을 제공할 수 있습니다. 암호학적 프로토콜 설계와 하드웨어 아키텍처를 잇는 이러한 발견은 NTT 및 SumCheck 기반 영지식 증명 시스템의 증명 비용(proving cost)을 이해하는 데 실질적인 지침을 제공합니다.