원문 작성자: 웨이켕 첸
이더리움 가상 머신(EVM)에서, Keccak 해시 함수는 상태 트리(머클 패트리샤 트리) 구성 및 검증에 광범위하게 사용되며, 제로 지식 증명에서 주요 계산 비용을 차지합니다. Keccak을 얼마나 효율적으로 증명할 수 있는지는 제로 지식 증명 분야의 오랜 미해결 기술적 과제입니다.
이러한 도전에 대응하기 위해, Polyhedra 팀은 Keccak 및 기타 이진 연산을 위해 특별히 설계된 고성능 증명 시스템인 Binary GKR을 출시했습니다.
핵심 진전: Keccak 증명 속도 5.7배 향상
Binary GKR은 지금까지 가장 빠른 Keccak 제로 지식 증명 성능을 달성했으며, 기존 최적의 이진 증명 시스템인 FRI-Binius에 비해 약 5.7배 속도 향상을 이뤘습니다. 이 breakthrough는 이론적으로 중요한 의미를 가질 뿐만 아니라 실제 응용에 새로운 가능성을 열었습니다.
응용 전망: zkEVM의 "범용 가속 사이드카"
우리는 Binary GKR이 다양한 zkEVM 아키텍처에서 "범용 가속 사이드카"로 사용될 수 있다고 생각합니다. 이는 이더리움 상태 트리의 대량 Keccak 연산을 효율적으로 처리하여 증명 비용을 크게 낮추고 시스템 처리량과 응답 속도를 향상시킬 수 있습니다.
Polyhedra는 Binary GKR의 제품화 및 오픈소스 프로세스를 지속적으로 추진하여 이더리움 및 더 광범위한 생태계의 zk 아키텍처 업그레이드를 지원할 것입니다.
(이하 생략)이것이 바로 Keccak이 "제로 지식의 성배"로 불리는 이유입니다. 초기의 해시 함수인 SHA-256과 Blake 2/3와 비교했을 때, 이들도 XOR, AND 등의 비트 연산에 의존하지만, 그 최대 성능 병목 현상은 정수 덧셈에서 비롯됩니다. 정수 덧셈은 일반적으로 증명 시스템에서 여러 4비트 블록으로 분해하여 최적화되어 성능을 크게 향상시킵니다. 하지만 Keccak은 어떤 정수 덧셈도 포함하지 않기 때문에 이러한 최적화 전략이 여기서는 무효화됩니다.
현재 가장 최첨단 솔루션은 Binius입니다. 이 시스템의 핵심 아이디어는 Keccak이 완전히 비트 연산으로 구성되어 있으므로, 비트를 기본 단위로 하는 증명 시스템을 사용할 수 있다는 것입니다. 이것이 Binius의 혁신적인 부분입니다.
Binius에서 Keccak은 유한체 𝐹₂(이진 필드) 상의 연산으로 표현됩니다. XOR이 본질적으로 𝐹₂에서의 덧셈이므로, 관련 오버헤드가 거의 완전히 제거됩니다. 전체 과정은 일련의 다항식 연산으로 구성되며, 비트 회전 연산도 비트 단위 처리 모델에서 쉽게 구현할 수 있습니다. 증명 비용은 주로 χ 단계에 나타나는 AND 게이트에 집중됩니다.
Binius의 벤치마크 결과, 8192회의 Keccak 연산 증명 시 약 12.35초가 소요되어 Groth 16(시도 1)과 룩업 테이블 방법(시도 2)보다 훨씬 우수합니다.
Binius가 최종 목표일까요? 그렇지 않습니다. Keccak 증명에서 일부 중복된 부분을 제거함으로써 현재 Binius 구현보다 약 5배 성능을 더 향상시킬 수 있다는 것을 발견했습니다.
폴리헤드라, Keccak에 최적화된 이진 증명 시스템 Binary GKR 출시
폴리헤드라 팀은 완전히 새로운 증명 시스템인 Binary GKR(자세한 내용은 ePrint 2025/717 참조)을 구축하고 있습니다. 이는 이진 연산에 대한 효율적인 증명에 특화된 프레임워크로, 특히 Keccak과 같이 비트 연산을 핵심으로 하는 함수에 적합합니다. Binary GKR의 핵심 장점은 다음 세 가지 핵심 기술 혁신에서 비롯됩니다:
1. GKR 프로토콜 기반, 반복 계산 최적화
우리는 Binary GKR 설계에서 GKR 프로토콜(Goldwasser–Kalai–Rothblum)을 기반으로 선택했는데, 이는 반복 계산으로 인한 중복 오버헤드를 효과적으로 줄일 수 있기 때문입니다.
일반적인 zkEVM 시나리오에서 Keccak은 "사이드카 증명기"로 등장하여 zkEVM이 위임한 대량의 Keccak 연산 작업을 일괄 처리합니다. 따라서 우리가 대상으로 하는 회로 구조는 본질적으로 많은 반복 패턴을 가지고 있으며, 예를 들어 8192회의 Keccak 호출은 일반적인 규모입니다.
더 중요한 것은 Keccak 알고리즘 자체가 매우 반복적이라는 점입니다:
5 × 5 상태 행렬에서 유사한 부울 연산을 반복적으로 수행합니다;
전체 과정에는 거의 동일한 24라운드 단계가 포함됩니다;
각 라운드의 구조는 동일하고 입력 상태만 다릅니다.
이러한 특성으로 Keccak은 GKR 프로토콜의 "천연 적합 대상"이 됩니다:
검증자 비용이 낮아 고빈도 검증 시나리오에 적합합니다;
증명자는 구조적 반복성을 충분히 활용하여 계산 경로를 재사용하고 증명 오버헤드를 크게 단순화할 수 있습니다;
기존의 일반 증명 시스템에 비해 대량 Keccak 시나리오에서 뚜렷한 성능 이점을 가집니다.
2. 이진 필드 기반 다항식 약속
우리는 선형 코드 기반 다항식 약속 방식을 채택했으며, 이는 직접 이진 필드에서 실행됩니다. 앞서 언급했듯이, 원시 이진 표현을 사용하면 XOR과 같은 연산을 "무료로" 얻을 수 있습니다. 또한 Binius의 방법과 유사하게, 이진 필드 기반 다항식 약속은 더 큰 수 필드 사용으로 인한 중복을 피하여 시스템의 성능과 효율성을 크게 향상시킵니다.
3. 이진 연산을 위한 사전 계산 테이블
Binary GKR 논문의 핵심 혁신은 회로 구조의 높은 희소성을 충분히 활용하여 GKR 프로토콜의 증명 효율성을 크게 향상시킨 것입니다. 여러 비트를 동시에 처리할 때도 이 희소성은 여전히 유지됩니다. 우리의 접근 방식은 여러 비트를 GKR 프로토콜의 다항식(중간 다항식이며 약속할 필요 없음)에 "패킹"한 후, 이러한 패킹된 데이터에 직접 GKR 프로토콜 연산을 수행하는 것입니다.
희소성이 여전히 매우 높기 때문에, 우리는 사전 계산 테이블을 활용하여 증명자가 기존 GKR 프로토콜보다 훨씬 낮은 계산 오버헤드로 증명을 생성할 수 있게 합니다. 이 최적화는 GKR의 이진 관계 처리 효율성을 크게 향상시킵니다.
본 문서는 위의 세 번째 기술 최적화, 즉 이진 연산을 위한 사전 계산 테이블에 중점을 둘 것입니다.
(이하 생략, 번역 계속됨)
