기술 요약: ZK-Flex

문제 정의

영지식 증명(Zero-Knowledge Proofs, ZKPs), 특히 널리 채택된 Groth16 프로토콜은 계산의 정확성을 프라이버시를 유지하며 검증할 수 있게 해준다. 그러나 증명 생성은 계산 집약적이며, 크게 두 단계인 다항식(POLY) 계산(NTT를 포함한 Number-Theoretic Transform)과 타원 곡선(EC) 계산(MSM을 포함한 Multi-Scalar Multiplication)으로 나뉜다. 이 두 단계는 전체 증명 시간의 약 95%를 차지한다.

ZKPs를 위한 하드웨어 가속은 두 가지 주요 과제에 직면해 있다:

1. 대정밀도 모듈러 곱셈(Large-Precision Modular Multiplication): ZKP 프로토콜은 큰 유한체(예: 256, 384, 또는 768비트) 상에서 동작하며, 이는 비분해 가능한 소수 모듈러스(non-decomposable prime moduli)로 인해 잔여수 시스템(Residue Number System, RNS) 병렬성을 용이하게 활용할 수 없다. 표준적인 학교 방식(schoolbook) 곱셈은 비효율적이며, 기존의 재구성 가능한 가속기들은 이러한 다양한 정밀도를 효율적으로 지원하는 데 어려움을 겪는다.
2. 동적 워크로드 변화(Dynamic Workload Shifting): POLY와 EC 워크로드 사이의 균형은 문제의 크기(예: 제약 조건의 수)에 따라 동적으로 변한다. NTT와 MSM을 위한 별도의 엔진을 가진 기존 가속기들은 한 엔진이 유휴 상태가 되고 다른 엔진이 병목 현상이 되는 상황에서 낮은 자원 활용도를 보이는 문제를 겪는다. 또한, ReZK 및 LegoZK와 같은 기존 솔루션들은 정밀도 확장성(ReZK는 최대 384비트까지)이나 면적 효율성(LegoZK) 측면에서 제한적이며, 더 효율적인 변형들을 활용하지 못하는 고정된 알고리즘 매핑에 의존한다.

방법론

저자들은 유연하고 확장 가능한 소프트웨어-하드웨어 공동 설계 프레임워크인 ZK-Flex를 제안한다. 이 시스템은 호스트 측 소프트웨어 최적화 도구와 특화된 ASIC 가속기를 통합한다.

소프트웨어 계층 최적화

소프트웨어 계층은 워크로드를 분석하고 하드웨어를 위한 최적화된 명령어를 생성한다:

• 다음 매끄러운 합성수(Next Smooth Composite, NSC) 패딩: 전통적인 시스템은 다항식 길이를 다음 2의 거듭제곱(NP2)으로 패딩하는데, 이는 후속 MSM 단계에서의 점(point)의 수를 급격히 증가시킬 수 있다. ZK-Flex는 NSC 전략을 도입하여, 작은 소인수(2, 3, 5, 7 등)로 구성된 "매끄러운 합성수"로 패딩한다. 이는 제약 조건이 2의 거듭제곱 근처에 있지 않을 때 MSM 워크로드를 크게 줄여준다.
• 혼합 기수(Mixed-Radix) NTT: NSC 패딩을 지원하기 위해, 본 프레임워크는 기수 2, 3, 4, 5, 7, 8을 지원하는 혼합 기수 NTT 엔진을 채택한다. 소프트웨어에는 혼합 기수 NTT의 오버헤드와 MSM 비용 절감 사이의 트레이드오프를 조절하는 추정기가 포함되어 있어, 각 워크로드에 대해 최적의 전략(NP2 vs. NSC)을 선택한다.
• 적응형 MSM 구성: EC 최적화 도구는 가용 메모리 용량과 병렬성에 따라 Pippenger 버킷 기반 MSM 알고리즘에 대한 최적의 윈도우 크기와 타일링 전략을 자동으로 결정한다. 또한 부호 있는 숫자 표현(signed-digit representation)과 혼합 점 덧셈(mixed point addition, MPADD)을 활용하여 모듈러 곱셈을 줄인다.

하드웨어 아키텍처

하드웨어 가속기는 TCore(Toom–Cook Core)라고 불리는 재구성 가능한 코어를 중심으로 구축된다:

• TCore 설계: TCore는 Karatsuba 곱셈을 일반화한 Toom–Cook 알고리즘에 기반한 계층적 아키텍처이다. 이는 면적 오버헤드를 최소화하는 하이브리드 Toom-2/Toom-3 방식을 사용하여 256비트, 384비트, 768비트 정밀도를 지원한다. 코어는 평가(evaluation), 정수 곱셈, 보간(interpolation) 단계를 위한 그룹으로 구성된 처리 요소(Processing Elements, PEs)로 이루어져 있다.
• 확장 가능한 구성: 여러 개의 TCore 유닛은 **Ruche 기반 네트워크 온 칩(Network-on-Chip, NoC)**을 통해 상호 연결된다. 이를 통해 다양한 기수의 NTT 버터플라이 및 다양한 타원 곡선 점 연산(PADD, PDBL 등)과 같은 고수준 커널을 구성할 수 있어, 하드웨어가 다양한 암호화 파라미터에 적응할 수 있게 한다.
• 연결 리스트 메모리 관리: MSM 누적 중 발생하는 메모리 제약 문제를 해결하기 위해, ZK-Flex는 연결 리스트(linked-list) 메모리 메커니즘을 도입한다. 모든 병렬 엔진에 전용 버킷 메모리를 할당하는 대신(이는 확장이 어렵다), 이 기술은 포인터를 사용하여 버킷 내의 점들을 클러스터링한다. 이를 통해 여러 MPADD 엔진이 충돌 없이 공통 버킷 메모리를 공유할 수 있게 하여, 제한된 온칩 메모리 용량 하에서도 병렬성을 크게 향상시킨다.

주요 기여

1. 통합 SW-HW 공동 설계: ZK-Flex는 알고리즘 선택(NSC 패딩, 혼합 기수 NTT)과 하드웨어 아키텍처(Toom–Cook 코어, 연결 리스트 메모리)를 결합하여 ZKP 생성의 특정 병목 현상을 해결하는 최초의 프레임워크이다.
2. 유연한 다중 정밀도 코어: 하이브리드 Toom-2/3 접근 방식을 통해 최소한의 면적 오버헤드로 256, 384, 768비트 연산을 지원하는 TCore를 도입함으로써, 기존 재구성 가능 가속기의 정밀도 한계를 극복하였다.
3. 효율적인 메모리 관리: 연결 리스트 메모리 메커니즘은 버킷 메모리 요구량의 초선형적 증가 없이 MSM 연산에서 높은 병렬성을 가능하게 하여, 기존 설계의 핵심적인 활용 병목을 해결한다.
4. 포괄적인 평가: 본 프레임워크는 암호화 프리미티브, 블록체인 애플리케이션(Groth16), 머신러닝 모델(Lenet, VGG16)을 포함한 다양한 ZKP 워크로드에 대해 평가되었다.

결과

저자들은 28nm 공정 노드를 사용하여 ZK-Flex를 합성하였으며, 이를 최신 가속기(PipeZK, GZKP, LegoZK) 및 CPU 베이스라인과 비교 평가하였다.

• 성능 향상: ZK-Flex는 가장 우수한 기존 재구성 가능 가속기(LegoZK) 대비 증명 생성 지연 시간에서 5–11배의 속도 향상을 달s한다. 특정 사례(예: VGG16)에서는 최대 11.5배의 속도 향상에 도달한다.
• 면적 효율성: 본 프레임워크는 이전 연구들보다 최대 3.8배 높은 면적 효율성(proofs/s/mm²)을 보여준다.
• 구성 요소 성능:
  • NTT: LegoZK 대비 1.48배에서 1.84배의 속도 향상을 달성한다.
  • MSM: LegoZK 대비 2.69배에서 4.16배의 속도 향상을 달성한다.
• 소프트웨어 영향: 절제 연구(Ablation studies)에 따르면, 소프트웨어 최적화(POLY 및 EC 최적화 도구)는 최적화가 없는 베이스라인 대비 평균 2.4배의 속도 향상을 기여하며, 특정 시나리오에서는 최대 4.2배에 달하는 이득을 보인다.

의의 및 주장

본 논문은 ZK-Flex가 고성능 재구성 가능 ZKP 가속을 위한 새로운 토대를 마련했다고 주장한다. 대정밀도 산술 효율성과 동적 워크로드 활용이라는 두 가지 과제를 해결함으로써, ZK-Flex는 기존의 하드웨어 전용 또는 부분적으로 최적화된 접근 방식의 한계를 극복한다. 저자들은 이 프레임워크를 높은 자원 활용도와 면적 효율성을 유지하면서 블록체인 롤업에서 머신러닝 검증에 이르기까지 다양한 암호화 파라미터와 애플리케이션 도메인에 걸쳐 확장 가능한 최첨단 솔루션으로 포지셔닝한다.