해시 기반 다항식 커밋먼트 스킴(PCS)인 FRI는 영지식증명에서 준다항식 크기의 증명을 가능케 하지만, 가장 큰 코드워드를 다루는 초기 폴딩 라운드가 증명자 연산의 대부분을 차지해 비용이 크다. 연구진이 제안한 'ReedWeave'는 다항식을 여러 개의 작은 성분으로 분해해 인터리빙과 폴딩을 결합함으로써, 증명자 비용을 O(d log d)에서 O(d log(d/m))으로 줄이면서도 준다항식 검증 시간은 그대로 유지한다. Goldilocks 필드에서 32스레드로 100비트 보안 수준 벤치마크를 수행한 결과(d=2^24, m=64), 커밋 475.0ms·오픈 111.6ms·검증 2.07ms·증명 크기 594.7KiB를 기록했으며, 기존 FRI 대비 각각 6.9배·51.5배·4.2배, STIR 대비 2.9배·68.5배·2.1배 빨랐다. 증명 크기도 FRI의 0.69배로 더 작아, 실용적인 성능-효율 개선을 동시에 달성했다.
- •FRI의 초기 폴딩 라운드가 큰 코드워드를 다뤄 증명자 비용을 지배하는 문제를 해결
- •다항식을 여러 성분으로 분해해 인터리빙과 폴딩을 결합한 ReedWeave 제안
- •증명자 비용을 O(d log d)에서 O(d log(d/m))로 절감, 검증은 준다항식 유지
- •d=2^24 벤치마크에서 FRI 대비 커밋·오픈·검증 6.9배·51.5배·4.2배 향상
- •STIR 대비 2.9배·68.5배·2.1배 향상, 증명 크기는 FRI의 0.69배로 축소
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
ReedWeave: Faster Reed-Solomon Polynomial Commitments from Interleaving and Folding
- 1.ReedWeave는 FRI에 인터리빙+폴딩을 결합해 프로버 비용을 O(d log d)→O(d log(d/m))로 감소
- 2.d=2^24, m=64 조건에서 커밋 475ms·오픈 111.6ms·검증 2.07ms, 증명 크기 594.7KiB 달성
- 3.기존 FRI(ICALP 2018) 대비 커밋 6.9배, 오픈 51.5배, 검증 4.2배 빠르고 증명 크기 0.69배
- 4.STIR(CRYPTO 2024) 대비로도 오픈 68.5배 등 속도 우위, 증명 크기는 STIR의 2.31배
왜 중요한가?
zk-STARK 등 투명 영지식증명 시스템의 프로버 병목은 FRI 단계인데, ReedWeave는 이를 실질적으로 완화해 롤업·검증가능 컴퓨팅의 증명 생성 시간과 인프라 비용을 크게 낮출 잠재력이 있다.
이 연구는 블록체인 핵심 기술인 다항식 커밋먼트 방식의 속도를 획기적으로 향상시키는 방법을 제시합니다. 이는 국내 블록체인 프로젝트들이 영지식 증명(ZKP) 기반 솔루션의 효율성과 확장성을 개선하여 글로벌 경쟁력을 확보하는 데 중요한 기반이 될 수 있습니다. 빠른 검증 속도는 사용자 경험과 서비스 안정성에 직접적인 영향을 미치므로, 관련 기술 도입에 관심이 필요합니다.
본문 미리보기
Polynomial commitment schemes (PCSs) allow a prover to commit to a polynomial and later prove its evaluations succinctly. Among hash-based constructions, FRI (Ben-Sasson et al., ICALP 2018) and its follow-up works achieve polylogarithmic proofs by recursively ``folding'' Reed-Solomon (RS) codes. However, their concrete evaluation costs remain relatively high, as the first few folding rounds operate on the largest codewords and dominate the prover work. We present \emph{ReedWeave}, a Reed-Solomo
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
