오류정정 코드 기반 SNARK가 빠른 인코딩과 큰 상대 거리를 동시에 요구하는데, 최적의 비율-거리 트레이드오프를 갖는 Reed-Solomon 코드는 FFT 친화적 체에 의존해 필드에 구애받지 않는 구성에 한계가 있다는 문제를 다룬다. 이 논문은 임의의 체에서 효율적으로 인코딩 가능한 확장-누적(EA) 코드를 재검토해, 정확 가중치 앙상블에서 샘플된 희소 확장 행렬을 가진 EA 코드가 충분히 큰 유한체 위에서 높은 확률로 Singleton 경계에 임의로 근접한 비율-거리 트레이드오프를 달성함을 증명해 기존 추측을 해결했다. 이를 기반으로 EA 코드 기반의 필드 무관 다항식 커밋먼트 스킴 Flare를 구성했으며, 크기 M인 명제에 대해 O(M log M) 프루버 시간과 O(log²M) 증명 크기를 달성해 기존 O(√M) 증명 크기를 개선했다.
- •임의 체에서 효율적 인코딩 가능한 확장-누적(EA) 코드가 Singleton 경계에 근접함을 증명, 기존 추측 해결
- •정확 가중치 앙상블 기반 희소 확장 행렬로 강한 거리 보장 확보
- •EA 코드 기반 필드 무관 다항식 커밋먼트 스킴 Flare 구성
- •EA 코드 제약 관계용 효율적 IOP와 코드 전환·무작위 선형 툴딩 결합
- •O(M log M) 프루버 시간, O(log²M) 증명 크기로 기존 O(√M) 증명 크기 개선
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
EA Codes Approaching Singleton Bound (with Application to Field-Agnostic SNARKs)
- 1.EA 코드가 Singleton 바운드에 근접한 율-거리 트레이드오프를 고확률로 달성함을 증명, 기존 추측 해결
- 2.이를 바탕으로 EA 코드 기반 필드-비종속 다항식 커밋먼트 스킴 'Flare' 신규 제안
- 3.Flare는 O(M log M) 증명자 시간, O(log^2 M) 증명 크기로 기존 O(√M) 증명 크기 개선
왜 중요한가?
Reed-Solomon 코드처럼 FFT 친화적 필드에 의존하지 않고도 Singleton 바운드에 가까운 성능을 내는 코드를 확보해, 필드에 구애받지 않는 zkSNARK 설계의 선택지를 넓혔다.
언급 프로젝트
이 연구는 오류 수정 코드를 기반으로 하는 SNARKs(영지식 증명 시스템)의 핵심 개선 사항으로, 특정 필드에 구애받지 않고 싱글톤 경계에 근접하는 EA 코드를 제안합니다. 이는 기존 리드-솔로몬 코드의 FFT-친화적 필드 의존성 한계를 극복하여, 더 넓은 범위의 블록체인 플랫폼과 애플리케이션에서 SNARKs를 유연하게 적용할 수 있게 합니다. 국내 블록체인 프로젝트들이 확장성과 프라이버시 강화를 위해 영지식 증명 기술을 적극적으로 탐색하는 가운데, 본 기술은 다양한 환경에서의 상용화 가능성을 높여 핵심적인 기여를 할 것으로 기대됩니다.
본문 미리보기
SNARKs based on error-correcting codes require codes that simultaneously support fast encoding and large relative distance. Reed--Solomon codes achieve the optimal rate--distance tradeoff given by the Singleton bound, but their fast encoding relies on FFT-friendly fields, limiting their applicability to field-agnostic constructions. In this work, we revisit expand--accumulate (EA) codes, a simple family of linear codes that admit efficient encoding over arbitrary fields. We prove strong dista
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:25AI 초안
