Speeding up Sumcheck using Algebraic Geometry

출처:IACR ePrint (암호학)

AI 인사이트

개발자

1.이진 보존 곱셈코드를 대수기하학 기반으로 새로 구성, Reed-Solomon 대비 효율 개선
2.F_2^128 위에서 64비트 메시지를 길이 222 이진 곱 메시지로 인코딩하는 명시적 코드 제시
3.제네러스-95 곡선 기반 코드로 sumcheck 첫 라운드(univariate skip) 전송량을 3배 이상 축소
4.Flock 증명시스템에 구현해 2^32 제약에서 skip 라운드 2.36배, 전체 zerocheck 1.65배 가속

왜 중요한가?

이진체 기반 증명시스템이 Reed-Solomon 곱연산에서 겪던 로그배 비용 증가 문제를 binary-preserving 코드로 근본 해결해, zk 증명시스템의 프루버 성능 병목을 실질적으로 줄인다.

언급 프로젝트

Flock

본문 미리보기

The sumcheck protocol, a ubiquitous component of modern proof-systems, enables proving the sum of evaluations of a low-degree multivariate polynomial. In theory, sumcheck has been generalized from polynomials to (tensors of) any multiplication code, a code whose pointwise products of codewords lie in a related product code. All practical systems nonetheless specifically use polynomials. For proof-systems over binary fields that target Boolean circuits, this choice has a real cost: the product of

전체 내용이 궁금하다면?

원문을 직접 읽어보세요

원문 보기