CP-SNARK를 위한 효율적인 일괄 처리 프레임워크 = Efficient Batching Framework for CP-SNARKs

국문 초록 (Abstract)

zk-SNARK는 블록체인 응용에서 프라이버시를 보장하는 핵심 기술이지만, 다수의 암호학적 약정(commitment)을 처리할 때 확장성 한계에 직면한다. LegoSNARK는 모듈 구성을 통해 CP-SNARK(Commit-and-Prove SNARK) 증명자의 연산을 줄였으나, 약정 수(ℓ)에 비례해 연결 증명(linking proof)의 검증 비용이 선형적으로 증가하는 새로운 병목을 초래했다. 이러한 비용은 모든 연산이 가스비로 귀결되는 온체인(on-chain) 환경에서 특히 치명적이다.
본 논문은 동형성에 기반한 ‘회로 내 집계(in-circuit aggregation)’를 통해 CP-SNARK의 검증 병목을 해소하는 새로운 배치 프레임워크를 제안한다. 핵심 아이디어는 다수의 약정에 대한 검증자의 결합 연산을 증명자가 회로 내에서 수행하는 무작위 선형 결합으로 대체하는 것이다. 이를 통해 집계의 유효성은 SNARK 회로로 보장하면서, 검증자는 고비용의 연결 증명을 다수의 약정이 아닌 단일 집계 약정에 대해서만 수행하도록 만들어 검증 비용을 상수 시간으로 축소한다.
제안한 접근법은 검증자의 연결 증명 오버헤드를 O(ℓ)에서 상수 시간 O(1)로 낮춘다. 대신 증명 회로에 약정의 수에 비례하는 제약이 추가되는 트레이드오프가 발생하지만, 이는 자원이 풍부한 오프체인(off-chain) 환경에서 충분히 수용 가능하다. 결과적으로 본 프레임워크는 증명자의 연산 부담을 다소 증가시키는 대신, 온체인 검증 비용을 크게 절감하는 비대칭적 효율성을 달성한다.
본 프레임워크는 Groth16 및 Plonk 기반으로 구체화되었고, 선행 연구 LegoSNARK, Eclipse 와 비교 분석한다.
실험 결과, 스마트 컨트랙트 상의 TPS는 배치 크기 2^{10}에서 최대 10배 향상되었다. 이는 본 프레임워크가 대규모 프라이버시 보존 블록체인 응용에서 실용적임을 뒷받침한다.

다국어 초록 (Multilingual Abstract)

As blockchain applications expand, ensuring both scalability and privacy is critical. While Commit-and-Prove SNARKs (CP-SNARKs) enhance prover efficiency, they face a bottleneck where additional verifying linking proof costs increase linearly with the number of commitments.
This thesis proposes a new batching framework that cryptographically aggregates multiple individual commitments into a single one. This enables the linking proof system to verify only the aggregated commitment, drastically reducing verification overhead.
Experiments demonstrate that verifying 2^{13} commitments takes 0.011, improving 22 times over LegoSNARK. Furthermore, the system supports a throughput of approximately 5,300 commitments per second in a blockchain environment. These results highlight the framework's potential for scalable privacy solutions in real-world applications like Decentralized Identity (DID) and anonymous payments.

목차 (Table of Contents)

• 1 서론 1
• 1.1 연구 배경 1
• 1.2 관련 연구 및 한계 1
• 1.3 연구 목표 2
• 1.4 연구 기여 3
• 2 배경 지식 4
• 2.1 표기법 4
• 2.2 페더슨 약정 4
• 2.3 간결한 비대화형 지식 논증(SNARK) 4
• 2.4 Σ-프로토콜 6
• 3 새로운 배치 프레임워크 7
• 3.1 약정 키 분할 7
• 3.2 Σ-프로토콜을 이용한 배치 약정 8
• 3.3 전체 프로토콜 구성 8
• 3.4 CP-SNARK로의 확장 11
• 4 구체적인 인스턴스화 13
• 4.1 Groth16 기반 13
• 4.2 Plonk 기반 15
• 4.3 복잡도 분석 17
• 4.4 성능 고찰 17
• 5 실험 19
• 5.1 비교 분석 19
• 5.2 블록체인 응용 21
• 6 결론 23
• 참고 문헌 24
• 영문 요약 27