Protocols for Univariate Sumcheck

이 논문은 단변수 (Univariate) 합체 (Sumcheck) 프로토콜을 위한 세 가지 새로운 접근 방식을 제안합니다. 저자 Malcom Mohamed 는 기존에 다변수 (Multivariate) 시스템에서 주로 사용되던 효율적인 증명 기법을 단변수 시스템 (특히 단위근의 근을 도메인으로 사용하는 시스템) 에 적용할 수 있는 방법을 제시하며, 증명자 (Prover) 의 계산 복잡도를 선형 시간 (Linear Time) 으로 유지하면서 검증자 (Verifier) 의 통신 부하를 줄이는 것을 목표로 합니다.

다음은 논문의 상세한 기술적 요약입니다.

1. 문제 정의 (Problem)

SNARK(Succinct Non-interactive Argument of Knowledge) 시스템은 데이터를 다항식으로 인코딩하고 대수적 기법을 사용하여 NP 언어에 대한 사실을 증명합니다. 이 과정에서 Sumcheck은 핵심 구성 요소로 작용합니다.

• 다변수 vs 단변수 시스템:
  • 다변수 시스템: 데이터 인코딩에 다중선형 확장 (Multilinear Extension, mlex) 을 사용합니다. 표준 다변수 Sumcheck 프로토콜 (LFKN) 은 증명자 효율성이 매우 높지만, 라운드 수가 많고 검증자에게 많은 통신 부하를 줍니다.
  • 단변수 시스템: 데이터 인코딩에 단변수 확장 (Univariate Extension, unex) 을 사용합니다. 표준 단변수 프로토콜 (Aurora 등) 은 라운드 수가 적어 (보통 1 라운드) 대역폭과 검증자 친화적이지만, 증명자의 계산 비용이 높거나 효율성이 떨어질 수 있습니다.
• 핵심 질문: "다변수 Sumcheck 프로토콜의 증명자 효율성 (선형 시간) 을 유지하면서 단변수 시스템에 적용할 수 있는 프로토콜이 존재하는가?"
• 기존 접근법의 한계: 기존 연구들은 다변수와 단변수를 연결하는 '어댑터 (Adaptor)'를 사용했으나, 대부분 증명자 시간이 준선형 (Quasilinear) 이었거나, 기저 변환 (Basis translation) 에 따른 오버헤드가 있었습니다. 또한, Gemini 프로토콜을 기반으로 한 선형 시간 단변수 Sumcheck 프로토콜은 공개된 구체적인 구현이 없었습니다.

2. 방법론 (Methodology)

저자는 세 가지 주요 접근법을 제시하며, 모두 단변수 다항식을 다변수 다항식 (또는 그 역) 으로 매핑하여 기존 기법을 활용하는 방식을 취합니다.

2.1. 다중선형 확장 (mlex) 을 단변수 확장 (unex) 으로 평가 (Section 3)

• Square Evaluation Folding: mlex의 부분 평가를 unex를 통해 수행하는 선형 시간 재귀적 폴딩 프로토콜을 제안합니다.
• 핵심 아이디어: 단변수 다항식 $f(x)$를 짝수 계수 부분 ($f_{sq}$) 과 홀수 계수 부분 ($f_{no}$) 으로 분해합니다.
  • $f(x) = f_{sq}(x^2) + x f_{no}(x^2)$ 관계를 이용합니다.
  • 이를 통해 $m$차원의 다변수 평가 문제를 $m$개의 단변수 평가 문제로 변환하고, 이를 재귀적으로 해결합니다.
• 프로토콜 2: 증명자가 $f_{sq}$와 $f_{no}$에 대한 오라클을 보내고, 검증자가 무작위 점에서 Lagrange 보간 공식을 통해 일관성을 확인합니다.

2.2. 직접적인 단변수 Sumcheck (Section 4)

• DGM 프로토콜의 수정 (Protocol 3): Drake, Gabizon, Meckler (DGM) 가 제안한 도메인 식별 (Domain Identity) 프로토콜을 분석하여, 원래 버전의 결함 (차수 불일치로 인한 무결성 검증 실패) 을 수정합니다.
  • 수정된 프로토콜은 다항식의 짝수/홀수 부분을 분리하고, Gemini 어댑터와 결합하여 선형 시간 Sumcheck 을 구현합니다.
• 직접적인 Gemini 축소 (Protocol 4): DGM 의 복잡한 단계를 우회하여, Invers Kronecker Substitution을 직접 활용합니다.
  • 단변수 다항식 $f(w^i)$를 다변수 다항식 $mlin[f](w^i, w^{2i}, \dots)$로 직접 매핑합니다.
  • 표준 다변수 Sumcheck 로직을 단변수 도메인에 직접 적용하여 가장 간단하고 효율적인 프로토콜을 구축합니다.

2.3. 라운드 축소 (Round Reduction)

• 위 프로토콜들은 $m$라운드에서 $k$라운드 ($k < m$) 에서 중단할 수 있습니다.
• 중단된 후 남은 작은 주장은 Aurora와 같은 단일 라운드 Sumcheck 프로토콜로 처리하여 전체 라운드 수를 $O(\log m)$ 또는 $O(\sqrt{m})$까지 줄일 수 있습니다.
• 이 과정에서 추가적인 오버헤드 없이 증명자 시간을 선형으로 유지합니다.

3. 주요 기여 (Key Contributions)

1. 선형 시간 단변수 Sumcheck 프로토콜의 실현:
   • 기존에 불가능하거나 비효율적이었던 단변수 Sumcheck 에서 증명자 시간을 $O(2^m)$ (선형) 으로 달성하는 세 가지 프로토콜을 제안했습니다.
   • 특히 Protocol 4는 가장 효율적이며, 표준 다변수 Sumcheck 과 유사한 성능을 보입니다.
2. DGM 프로토콜의 결함 발견 및 수정:
   • 커뮤니티에서 논의되던 DGM 프로토콜이 수학적으로 결함이 있음을 지적하고, 이를 수정하여 Gemini 기반 선형 시간 Sumcheck 의 유효성을 입증했습니다.
3. 기저 변환 (Basis Translation) 오버헤드 제거:
   • 기존 어댑터 방식 (값을 계수로 매핑 등) 은 기저 변환에 추가 비용이 들었으나, 제안된 방법 (특히 Protocol 2 와 4) 은 값 대 값 (Values-to-Values) 매핑을 사용하여 이러한 오버헤드를 제거했습니다.
4. 유연한 라운드 축소:
   • $O(\log m)$ 또는 $O(\sqrt{m})$ 라운드로 축소할 수 있는 자연스러운 방법을 제공하며, 이는 검증자의 통신 비용을 크게 줄여줍니다.

4. 결과 및 성능 분석 (Results)

논문 내 Table 2에 따르면, 제안된 프로토콜들은 기존 Aurora 방식과 비교하여 다음과 같은 이점을 가집니다:

• 증명자 시간 (Prover Time): 모든 제안된 프로토콜에서 $O(d^2 2^m)$ 또는 $O(\binom{d+q}{q} d 2^m)$으로, 기존 다변수 Sumcheck 과 동급의 선형 시간 복잡도를 가집니다.
• 검증자 시간 및 통신:
  • Protocol 2 + LFKN: 다변수 Sumcheck 과 결합하여 효율성을 높입니다.
  • Protocol 4 + Gemini: 가장 효율적인 조합으로, 오라클 수와 필드 요소 전송량을 최소화합니다.
  • 라운드 축소 적용 시: 라운드 수가 $\log(m)$으로 줄어들어 검증자 부하가 크게 감소합니다.
• 오라클 수: Protocol 4 는 Gemini 와 결합 시 다른 어댑터들보다 적은 수의 오라클을 전송합니다.

5. 의의 및 중요성 (Significance)

• SNARK 설계의 통합: 이 연구는 "다변수 세계"의 증명자 효율성과 "단변수 세계"의 검증자 효율성 (낮은 라운드, 낮은 통신) 을 동시에 달성할 수 있음을 보여줍니다.
• Aurora 프로토콜의 개선: 현재 Aurora 와 같은 단변수 기반 SNARK 를 사용하는 모든 애플리케이션은 이 프로토콜을 도입하여 증명자 효율성을 획기적으로 개선할 수 있습니다.
• 실용성: 제안된 프로토콜들은 이론적일 뿐만 아니라, 실제 구현 가능한 선형 시간 복잡도를 가지며, 기존 시스템 (Gemini, Aurora 등) 과 호환되어 즉시 적용 가능한 솔루션을 제공합니다.

요약하자면, 이 논문은 단변수 Sumcheck 의 병목 현상이었던 증명자 효율성 문제를 해결하고, 다변수 기법의 장점을 단변수 시스템에 자연스럽게 융합함으로써 차세대 SNARK 설계에 중요한 이정표를 제시했습니다.