Binary GKR: Keccak 증명 속도 기록을 깨는 새로운 제로 지식 증명 시스템
원작자: 웨이켄 천
이더리움 가상 머신(EVM)에서 Keccak 해시 함수는 상태 트리(Merkle Patricia Trees)의 구성 및 검증에 널리 사용되며, 이는 영지식 증명의 주요 계산 오버헤드를 차지합니다. 케칵을 효율적으로 증명하는 방법은 영지식 증명 분야에서 오랫동안 해결되지 않은 기술적 문제입니다.
이러한 과제를 해결하기 위해 Polyhedra 팀은 Keccak 및 기타 이진 연산을 위해 설계된 고성능 증명 시스템인 Binary GKR을 도입했습니다.
핵심 진행 상황: 케착 증명 속도가 5.7배 증가했습니다.
이진 GKR은 지금까지 가장 빠른 Keccak 제로 지식 증명 성능을 달성했으며, 이는 기존 이진 증명 시스템 FRI-Binius의 최적 솔루션보다 약 5.7배 빠릅니다. 이러한 획기적인 발견은 이론적인 의미가 매우 클 뿐만 아니라, 실제 응용 분야에서도 새로운 가능성을 열어주었습니다.
응용 전망: zkEVM의 "범용 가속 사이드카"
우리는 Binary GKR이 다양한 zkEVM 아키텍처에서 "범용 가속 사이드카" 역할을 하여 Ethereum 상태 트리에서 많은 수의 Keccak 연산을 효율적으로 처리하고, 이를 통해 증명 비용을 크게 줄이고 시스템 처리량과 응답 속도를 향상시킬 수 있다고 믿습니다.
Polyhedra는 Binary GKR의 제품화와 오픈 소스 프로세스를 지속적으로 홍보하여 Ethereum과 더 광범위한 생태계에서 zk 아키텍처의 업그레이드를 지원할 것입니다.
Keccak: 제로 지식 이더리움의 성배
이더리움은 점차적으로 제로 지식 증명 기반 레이어 1로 진화하고 있습니다. 21개 팀이 참여하고 22개의 ZK(E)VM 구현을 다루는 Ethproofs 프로젝트는 이더리움의 역사적 블록을 완벽하게 증명하려 시도하며 중요한 진전을 이루고 있습니다.
Ethproofs 공식 웹사이트 에서는 여러 팀의 진행 상황을 실시간으로 볼 수 있습니다. ZkCloud, Succinct, Snarkify, ZKM 등의 프로젝트는 최신 블록에 대한 ZK 증명을 지속적으로 제출하기 시작했습니다. 이러한 추세의 궁극적인 목표는 이더리움을 제로 지식 증명으로 구동되는 실행 계층으로 구축하는 반면, 합의 계층은 거래 목록 제안과 같은 가벼운 작업만 완료하면 되는 것입니다.
zkEVM 아키텍처가 직면한 가장 큰 과제: Keccak의 증명 효율성 병목 현상
현재 zkEVM을 구현하려는 Ethereum 호환 zkRollup 프로젝트(Polygon, Taiko, Scroll 등)가 여러 개 있습니다. 그러나 CPU에서는 효율적인 기존 EVM의 일부 작업은 제로 지식 증명 시스템에서는 비용이 많이 듭니다. 주요 성능 병목 현상은 Keccak 해시 함수입니다.
Keccak은 전체 체인 상태를 해시 형태로 기록하는 이더리움의 머클 패트리샤 트리를 구축하는 데 널리 사용됩니다. 그러나 Keccak의 기본 연산은 대부분 ZK 시스템에서 사용하는 소수 필드 연산 모델과 호환되지 않는 비트 수준 연산을 기반으로 하기 때문에 성능이 크게 저하됩니다.
Keccak 해시 함수가 본질적으로 "비트 연산"의 모음인 이유를 이해하는 데 도움이 되도록 핵심 연산 5가지, 즉 θ(세타), ρ(로), π(파이), χ(카이), ι(이오타)를 간략하게 보여드리겠습니다. 이러한 연산은 각 셀이 64비트 정수인 5 × 5 행렬 구조에 적용되며, 이를 "워드"라고 합니다. 전체 행렬은 5개의 행과 5개의 열로 구성되어 있습니다.
θ(세타): 먼저 각 열의 패리티 값을 계산한 후, 왼쪽에 인접한 열과 배타적 논리합을 수행합니다. 동시에 오른쪽에 인접한 열은 왼쪽으로 회전한 후 배타적으로 OR됩니다. 이 과정에는 "XOR" 및 "좌회전"과 같은 기본적인 이진 연산이 포함됩니다.
ρ (Rho): 행렬의 각 단어를 조금씩 왼쪽으로 회전합니다. 각 단어의 회전 거리는 다르지만 모두 미리 설정된 고정값입니다. 이 단계는 전적으로 "왼손" 작업으로 구성됩니다.
π(파이): 행렬에 있는 단어를 고정된 패턴에 따라 재배열합니다. 이 과정은 단지 위치 순열일 뿐이므로, 일반적으로 영지식 증명에서는 "비용이 없는 연산"으로 간주됩니다.
χ (카이): 각 행을 따라 비트 단위 조합 연산을 수행하고, 각 단어는 행의 왼쪽과 오른쪽에 있는 두 인접 단어와 결합됩니다. 이러한 연산에는 '배타적 또는', '부정' 및 '그리고'가 포함됩니다.
ι (이오타): 고정 상수를 사용하여 행렬의 첫 번째 단어에 대해 XOR 연산을 수행합니다. 여기에는 "XOR" 연산만 포함됩니다.
Keccak을 영지식 증명으로 구현하는 데 있어 가장 큰 과제는 이러한 비트 수준 연산을 효율적으로 표현하는 방법입니다. 특히 각 연산이 64비트 정수에서 수행될 때 더욱 그렇습니다. 이것이 우리가 이것을 Keccak-1600이라고 부르는 이유입니다. 각 라운드의 상태 공간이 5 × 5 × 64 = 1600비트이기 때문입니다. 이 작업 과정은 24번 반복되어야 합니다.
다음으로, Keccak을 구현하기 위한 몇 가지 이전 시도를 간략히 살펴보겠습니다.
시도 1: Groth 16 또는 기타 R 1 CS 기반 증명 시스템
현재 가장 인기 있고 직접적인 방법은 Groth 16이나 다른 R 1 CS(Rank-1 Constraint System) 증명 시스템을 사용하여 Keccak을 구현하는 것입니다. Groth 16에서 비트 연산을 표현하기 위해 각 비트를 0 또는 1로 표현하고 산술 관계를 통해 다음과 같은 논리 연산을 시뮬레이션합니다.
배타적 또는: a + b − 2 ab 표현식을 사용합니다.
부정: 1 − a라는 표현을 사용합니다(일반적으로 다른 제약 조건에 통합하는 데 자유롭습니다)
그리고: a × b라는 표현을 사용하세요.
그러나 회전-왼쪽 및 기타 순열 연산과 같은 연산은 일반적으로 ZK 환경에서 비용이 없는 연산으로 간주되며 추가적인 제약 조건이 필요하지 않습니다.
계산에 따르면, 케칵의 각 라운드에 포함되는 제약 조건의 수는 다음과 같습니다.
세타 연산은 약 4480개의 제약 조건을 생성합니다.
ρ 및 π 작업은 "비용이 0"입니다.
χ 연산은 약 3200개의 제약 조건을 생성합니다.
이 작업은 약 64개의 제약 조건을 생성합니다.
따라서 Keccak-1600(24라운드)을 모두 채우면 Groth 16에 185,856개의 제약이 발생합니다.
Ingonyama의 ICICLE 라이브러리의 데이터에 따르면, Nvidia 4090 GPU에서는 Keccak ZK 증명을 생성하는 데 약 30~40밀리초가 걸리고, CPU에서는 약 450밀리초가 걸립니다. 8192개의 케칵 연산을 증명해야 하는 경우 GPU는 최소 250~300초가 걸리는 반면 CPU는 거의 1시간이 걸릴 수 있습니다.
시도 2: 조회 기반 증명 시스템
좀 더 현대적인 최적화 방법은 데이터를 일괄적으로(예: 4비트 또는 8비트 그룹) 처리하고 조회 테이블을 통해 모든 비트 연산을 수행하는 것입니다. 즉, 각 64비트 정수는 여러 개의 작은 블록(예: 8비트 청크 8개)으로 나뉜 다음, 조회 테이블을 사용하여 논리 연산을 수행합니다.
구체적으로 다음과 같은 조회 테이블이 있습니다.
XOR 조회 테이블: 두 개의 8비트 청크의 XOR 값을 계산하는 데 사용되는 2 8 × 2 8 조회 테이블입니다. 이를 통해 기존의 8개 제약 조건 대신 1개 제약 조건으로 8비트 XOR을 수행할 수 있습니다.
AND 연산 조회 테이블: 이는 또한 2 ⁸ × 2 ⁸ 조회 테이블로, 두 개의 8비트 청크의 비트 AND 연산에 사용됩니다. 제약조건을 저장하는 효과는 XOR과 유사합니다.
왼쪽 회전 조회 테이블: Keccak에서 자주 발생하는 왼쪽 회전 연산을 처리하기 위해 여러 개의 조회 테이블이 도입되었습니다. 구체적으로: 8k+1, 8k+2 등의 회전 거리에 해당하는 크기가 2⁸인 7개의 조회 테이블(여기서 k는 음이 아닌 정수)입니다. 회전을 전혀 처리하지 않는 시도 1과 비교했을 때, 이 접근 방식은 라운드당 약 192개의 추가 제약 조건이라는 추가적인 오버헤드를 발생시킵니다. 하지만 다른 부분에 비하면 이 비용은 여전히 비교적 적습니다.
이 시스템을 구현하기 위해 우리는 더 이상 Groth 16을 사용하지 않지만, 조회 테이블에 대한 보다 완벽한 지원을 제공하는 Stwo 및 Plonky 3와 같은 소규모 도메인 증명 시스템을 사용하는 데 더 적합합니다. 이 방식에 따르면 완전한 Keccak 연산 하나에는 약 27,264개의 제약 조건이 필요하고, 이를 조회 테이블 호출과 결합하면 제약 조건의 전체 개수를 크게 줄일 수 있습니다. 이는 Groth 16에 비해 상당한 최적화입니다.
하지만 이러한 최적화는 성능 면에서 절대적으로 우위를 점하는 것은 아닙니다. 조회 테이블 자체의 호출 및 관리에도 오버헤드가 발생하므로, 적절하게 처리하지 않으면 제약 조건 수 감소로 인한 이점을 상쇄할 수 있습니다. 따라서 일부 시나리오에서는 실제 운영 효율성이 Groth 16 기반 구현만큼 좋지 않을 수 있습니다.
시도 3: 비니우스
조회 테이블이나 사용자 정의 게이트를 통해 얻을 수 있는 속도 향상 효과는 실제로는 기대했던 만큼 크지 않을 수 있습니다. 조회 자체의 오버헤드가 제약 조건 최적화 효과를 상쇄할 수 있기 때문입니다. 따라서 Keccak 증명의 효율성을 더욱 개선하기 위해 다른 방법을 모색해야 합니다.
이것이 케착이 "영지식의 성배"로 알려진 이유입니다. 비교해 보면, SHA-256과 Blake 2/3과 같은 초기 해시 함수도 XOR과 AND와 같은 비트 연산에 의존하지만, 가장 큰 성능 병목 현상은 정수 덧셈에서 발생합니다. 정수 덧셈은 증명 시스템에서 여러 개의 4비트 청크로 나누어 최적화하는 경우가 많은데, 이를 통해 성능이 크게 향상됩니다. 하지만 Keccak은 정수 덧셈을 포함하지 않으므로 이러한 최적화 전략은 여기서는 실패합니다.
현재 가장 최첨단 솔루션은 Binius입니다. 이 시스템의 핵심 아이디어는 Keccak이 전적으로 비트 연산으로 구성되었기 때문에 비트 기반 증명 시스템을 사용하여 구현할 수 있다는 것입니다. 여기서 비니우스가 돌파구를 찾습니다.
비니우스에서 케칵은 이진체인 유한체 𝐹₂에 대한 연산으로 표현됩니다. XOR은 본질적으로 𝐹₂에 추가된 것일 뿐이므로, 관련된 오버헤드는 거의 완전히 제거됩니다. 전반적인 프로세스는 일련의 다항식 연산으로 구성되며, 비트 회전 연산도 비트별 처리 모델에 쉽게 구현할 수 있습니다. 비용은 주로 x 단계에 나타나는 AND 게이트에 집중되어 있는 것으로 나타났습니다.
Binius의 벤치마크 테스트에 따르면 8192개의 Keccak 연산을 증명하는 데 약 12.35초밖에 걸리지 않는데, 이는 Groth 16(시도 1)과 조회 테이블 방식(시도 2)보다 훨씬 더 나은 결과입니다.
비니우스가 끝일까요? 실제로는 그렇지 않습니다. 우리는 Keccak 증명에서 일부 중복을 제거함으로써 현재 Binius 구현보다 약 5배 정도 성능을 향상시킬 수 있음을 발견했습니다.
Polyhedra가 Keccak에 최적화된 이진 증명 시스템인 Binary GKR을 출시합니다.
Polyhedra 팀은 새로운 증명 시스템인 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과 같은 연산을 "무료로" 수행할 수 있습니다. 또한, 비니우스의 방법과 유사하게 이진체에 기반한 다항식 커밋은 더 큰 숫자체를 사용함으로써 발생하는 중복을 피하며, 이는 시스템의 성능과 효율성을 모두 크게 향상시킵니다.
3. 이진 연산을 위한 미리 계산된 테이블
이진 GKR 논문의 핵심 혁신은 회로 구조의 높은 희소성을 최대한 활용하여 GKR 프로토콜의 증명 효율성이 크게 향상되었다는 것입니다. 이러한 희소성은 많은 비트를 동시에 처리할 때에도 유지됩니다. 우리가 하는 일은 GKR 프로토콜에서 여러 비트를 다항식으로 "패키징"하는 것입니다(참고: 이는 중간 다항식이며 커밋이 필요하지 않습니다). 그런 다음 이 패키징된 데이터에 직접 GKR 프로토콜 작업을 수행합니다.
여전히 희소성이 높기 때문에 사전 계산된 테이블을 활용하여 증명자가 기존 GKR 프로토콜보다 훨씬 적은 계산 오버헤드로 증명을 생성할 수 있습니다. 이러한 최적화는 이진 관계를 처리할 때 GKR의 효율성을 크게 향상시킵니다.
이 글에서는 위에서 언급한 세 번째 기술적 최적화, 즉 이진 연산을 위한 미리 계산된 테이블에 초점을 맞출 것입니다.
다항식으로 비트 패킹
우리 방식의 핵심은 데이터 병렬 부울 회로를 위해 특별히 설계된 GKR 프로토콜을 위한 새로운 합계 검사 방법입니다. 이 방법은 증명자의 계산 부담을 효과적으로 줄이고 여러 비트를 다항식으로 묶어 효율성을 크게 향상시킵니다.
이진 관계를 보다 효율적으로 평가하기
기존 GKR과 비교해 바이너리 GKR은 새로운 최적화 공간을 제공합니다.
이 전처리 테이블은 매우 작습니다. 매개변수를 적절히 설정하면 테이블 크기를 약 15MB 이하로 유지할 수 있습니다. 이 크기는 CPU의 L3 캐시에 쉽게 들어가므로 테이블 조회 작업이 매우 효율적입니다.
이 기술은 거의 모든 이진 연산에 적용 가능하며 이진 GKR 구성의 성능 향상의 핵심입니다.
구현 및 평가
우리는 arkworks 생태계를 기반으로 Rust에서 SNARK 시스템을 구현하고 다양한 크기의 무작위 부울 회로에 대한 포괄적인 벤치마크를 수행했습니다.
무작위 부울 회로 외에도 우리는 또한 영지식 증명의 "성배"인 케칵에 초점을 맞춥니다. 우리는 Keccak 증명을 통해 제안된 방법의 성능을 Binius와 비교합니다. 둘 다 이진 도메인 연산을 기반으로 합니다.
8192개의 Keccak 호출을 처리할 때 Binius는 증명을 생성하는 데 12.35초가 걸리는 반면, 우리의 방법은 2.18초만 걸립니다. 동시에 Keccak의 간결한 구조 덕분에 검증 시간도 0.035초로 더 단축되었습니다. 통신 오버헤드 측면에서 증명 크기는 1.052MB입니다.
결론
이 글에서는 Keccak과 같은 이진 함수에 대한 최적화에 초점을 맞춰, 영지식 증명 분야에서 Polyhedra 팀의 최신 진행 상황을 소개합니다. 이 성과는 다양한 유형의 zkEVM을 구축하기 위한 효율적인 "보조 모듈"로 사용될 수 있습니다.
우리는 Binary GKR을 RISC Zero 및 SP 1과 같은 zkEVM 시스템에 통합하여 Keccak 성능 병목 현상을 완화하는 역할을 더욱 검증할 계획입니다. 궁극적인 목표는 기존 EVM 아키텍처를 파괴하지 않고 레이어 1의 완전한 SNARK화를 향해 이더리움의 진행을 가속화하는 것입니다.
원본 링크: https://blog.polyhedra.network/binary-gkr/
