Zk-SNARK 마켓플레이스와 유용한 작업 증명

기본 정보

• 논문 ID: 2510.09729
• 제목: Zk-SNARK Marketplace with Proof of Useful Work
• 저자: Samuel Oleksak, Richard Gazdik, Martin Peresini, Ivan Homoliak (브르노 공과대학교, 체코)
• 분류: cs.CR (암호학 및 보안)
• 발표 시간: 2025년 10월 10일 (arXiv 사전인쇄본)
• 논문 링크: https://arxiv.org/abs/2510.09729

초록

전통적인 작업 증명(PoW)은 무허가 블록체인 합의 프로토콜 중 가장 안전한 것으로 널리 인정되고 있으나, 계산 집약적이고 외부적으로 무용한 퍼즐에 의존하여 막대한 전력 에너지 낭비를 초래한다. 이 문제를 완화하기 위해 유용한 작업 증명(PoUW)이 대안으로 제시되었으며, 블록체인 플랫폼의 보안을 보호하면서 동시에 현실 세계의 가치를 창출할 수 있다. 그러나 기존의 PoUW 제안들은 종종 체인의 무결성과 채굴자 신원을 퍼즐 해결 방안에 포함시키지 못하여 PoW의 필수 요구사항을 만족하지 않으므로 공격에 취약하다. 본 논문은 클라이언트가 외주한 zk-SNARK 증명 계산을 부산물로 활용하면서 동시에 합의 프로토콜을 보호하는 PoUW 합의 프로토콜을 제시한다. 이 메커니즘을 더욱 활용하여 분산형 zk-SNARK 증명 생성 외주 마켓플레이스를 설계했으며, 저자들의 지식으로는 합의 계층에서 작동하면서 PoW의 모든 필수 속성을 만족하는 첫 번째 사례이다.

연구 배경 및 동기

핵심 문제

1. 에너지 낭비 문제: 전통적인 PoW 프로토콜(예: 비트코인)은 실제 용도가 없는 계산을 수행하기 위해 막대한 전력을 소비하며, 비트코인 채굴은 연간 65.4메가톤의 CO2 배출을 초래할 수 있으며, 이는 그리스의 국가 수준 배출량에 해당한다.
2. zk-SNARK 계산 병목: zk-SNARK 증명 생성은 계산 및 메모리 측면에서 매우 집약적이며, 일반적으로 수십 GB의 RAM과 고급 하드웨어에서 수십 분이 필요하여 리소스 제약이 있는 장치에서 실용적이지 않다.
3. 기존 PoUW 방안의 보안 결함: 기존 PoUW 제안들은 PoW의 핵심 보안 요구사항, 특히 신선성(freshness) 속성을 만족하지 못하여 재생 공격에 취약하다.

연구 동기

• PoUW와 zk-SNARK 생성의 이중 요구사항을 결합하여 블록체인 보안을 보장하면서 동시에 유용한 암호학 증명을 생성하는 합의 프로토콜 설계
• 합의 계층에서 작동하는 첫 번째 범용 zk-SNARK 계산 마켓플레이스 생성
• 기존 PoUW 방안의 보안 부족 문제 해결

핵심 기여

1. 획기적인 PoUW-zk-SNARK 융합 프로토콜: zk-SNARK 증명 생성을 유용한 작업으로 활용하는 새로운 PoUW 합의 프로토콜을 제시하고, 합의 프로토콜에 보안을 제공하는 첫 번째 분산형 SNARK 계산 마켓플레이스를 구축했다.
2. 개인 입력 지원 확장 방안: 공개 무허가 블록체인 환경에서 개인 입력을 포함하는 zk-SNARK 증명 계산 위임의 과제를 해결하고, 증인 난독화 외주(WOO) 기술을 제시했다.
3. 완전한 보안성 분석: 제시된 합의 프로토콜 및 그 확장의 보안 속성을 포괄적으로 분석하고 증명하여 PoW의 모든 필수 조건을 만족한다.
4. 혁신적인 블록 제안자 선택 메커니즘: 가중 복권을 기반으로 한 블록 제안자 선택 알고리즘을 설계하고, 버킷 메커니즘을 결합하여 낭비 작업을 감소시킨다.

방법론 상세 설명

작업 정의

다음과 같은 PoUW 합의 프로토콜을 설계한다:

• 입력: 클라이언트가 제출한 산술 회로 및 증명 매개변수
• 출력: 유효한 zk-SNARK 증명 및 안전한 블록체인 합의
• 제약 조건: PoW의 모든 필수 속성 만족(비대칭성, 세분성, 상각 방지 등)

시스템 아키텍처

네트워크 참여자

1. 클라이언트(Clients): 합의에 참여하지 않으며, 코인 이전 거래 및 증명 요청 거래 생성
2. 채굴자(Miners/Full nodes): 합의에 참여하고, 거래를 선택하며, SNARK 증명을 생성하고, 블록을 발행 및 검증
3. 회로 등록 노드(Circuit registry nodes): SNARK 회로 등록부를 유지하고, 신뢰할 수 있는 설정의 SMPC에 참여

블록 구조

각 블록은 두 가지 거래 유형을 포함한다:

• 코인 거래(Coin transactions): 기본 화폐 작업
• 증명 거래(Proof transactions): SNARK 생성 요청을 캡슐화

핵심 기술 메커니즘

1. 블록 제안자 선택 알고리즘

진화 과정:

• (A) 기본 방법: 채굴자는 최소 난이도 임계값 κ에 도달하기 위해 충분한 증명을 생성해야 함
• (B) 복권 메커니즘 추가: 새 증명이 추가될 때마다 복권이 트리거되며, 승리 확률은: $P_{win}(i) = \frac{C_i}{\kappa}$ 여기서 $C_i$는 i번째 증명의 복잡도
• (C) 낭비 작업 감소: 누적 작업을 고려하는 매개변수 ψ 도입: $P_{win}(i) = \frac{C_i}{\kappa} + \psi \cdot \frac{\sum_{j<i} C_j}{\kappa}$
• (D) 병렬 블록 생산: 선형 체인 제약을 완화하여 병렬 채굴 허용
• (E) 버킷 메커니즘: 거래를 거래 해시 접두사에 따라 다양한 버킷에 할당하여 충돌 감소

2. 블록체인 무결성 보장

무결성 매개변수 η:

• 현재 블록 헤더(이전 블록 해시 및 코인 거래 포함)를 해싱하여 계산
• 산술 회로에 공개 매개변수로 주입
• 복권 실패 시 새로 생성된 증명을 포함하도록 η 재계산
• 증명이 도용되는 것을 방지하는 암호학적으로 연결된 증명 체인 형성

3. 회로 등록 서브네트워크

기능:

• 산술 회로의 분산형 등록 및 검색
• SMPC를 통한 신뢰할 수 있는 설정
• 증명 키 및 검증 키 저장
• 노드가 기본 화폐를 스테이킹하도록 요구하며, 부정행위 시 슬래싱

기술 혁신 포인트

1. 무결성 임베딩: 무결성 매개변수를 통해 증명을 특정 블록에 바인딩하여 PoW의 신선성 요구사항 만족
2. 버킷 병렬화: Sycomore의 동적 샤딩 아이디어를 차용하여 네트워크 요구에 따라 버킷 수를 동적으로 조정
3. 증인 난독화 외주(WOO): 가산 마스크를 사용하여 개인 입력 개인정보 보호
4. 복권 가중 메커니즘: 회로 복잡도에 따라 승리 확률을 조정하여 공정성 보장

실험 설정

모델링 방법

무작위 시간 색칠 페트리 네트(STCPN)를 사용하여 합의 프로토콜을 모델링하고, Python의 simpn 라이브러리로 구현한다.

실험 가정

• H1: 보상 분배는 노드 채굴 계산 능력에 정비례
• H2: 선택된 증명의 복잡도는 보상에 영향을 주지 않음
• H3: ψ 매개변수 도입으로 낭비 작업 감소를 위해 중앙화 증가를 대가로 함
• H4: 버킷 메커니즘이 낭비 작업을 감소시킴

실험 구성

• 증명 생성 프로세스 및 채굴자 상호작용에 초점
• 코인 거래 확인 시간 무시(상대적으로 순간적)
• 채굴자가 회로 등록 데이터를 이미 캐시했다고 가정

실험 결과

주요 발견

1. 공정성 검증(H1)

• 블록 보상 비율과 계산 능력 비율이 선형 관계(y=x)를 보임
• 핵심 문제: 증명 보상 비율이 이차 관계(y=x²)를 보이며, 강한 채굴자는 더 많은 블록을 생성할 뿐만 아니라 각 블록의 평균 강도도 더 높음
• 영향: 채굴 풀 형성을 장려할 수 있으며, 증명 보상이 총 보상에서 차지하는 비중을 최소화해야 함

2. 복잡도 독립성(H2)

• 서로 다른 증명 크기 선호도를 가진 채굴자들이 동일한 계산 능력 하에서 유사한 보상 비율을 획득
• 시스템이 증명 복잡도 선택에 대한 공정성을 검증

3. ψ 매개변수 영향(H3)

• ψ 증가에 따라 낭비 작업이 약 78%에서 70%로 감소
• 그러나 최강 채굴자의 보상 점유율은 약 37.5%에서 47.5%로 증가
• 낭비 작업 감소와 중앙화 증가 간의 트레이드오프 확인

4. 버킷 효과(H4)

• 버킷 수 증가가 낭비 작업을 현저히 감소시킴
• 16개 버킷과 16개 채굴자 구성에서 낭비 작업을 약 20%까지 감소 가능
• 버킷 수는 메모리 풀에서 사용 가능한 증명 수에 의해 제한됨

성능 분석

Groth16 증명 시간

• 증명 시간이 제약 수량과 선형 관계: T(n) = a·n + b
• 예측 가능한 성능 및 효율적인 리소스 할당 지원
• 검증 시간은 밀리초 수준이며 회로 복잡도와 무관

WOO 성능 오버헤드

• 난독화 회로의 원본 회로 대비 시간 오버헤드는 항상 0.1초 미만
• 오버헤드가 회로 규모에 따라 현저히 증가하지 않음
• 실시간, 개인정보 보호 증명 생성에 적합

관련 연구

PoUW 프로토콜

• Primecoin(2013): 소수 체인 검색, 수론에 기여
• Ofelimos: 조합 최적화 문제 사용
• Coin.AI: 분산형 심층 학습
• 한계: 기존 방안들은 신선성 속성이 일반적으로 부족하여 재생 공격에 취약

증명 생성 마켓플레이스

• 합의 통합형: Mina 프로토콜의 Snarketplace(응용 계층)
• 독립 네트워크형: =nil; Foundation Proof Market, RISC Zero의 Bonsai
• 본 논문의 장점: 합의 계층에서 작동하는 첫 번째 범용 zk-SNARK 마켓플레이스

결론 및 논의

주요 결론

1. PoW의 모든 필수 속성을 만족하는 PoUW 프로토콜을 성공적으로 설계
2. 첫 번째 합의 계층 zk-SNARK 계산 마켓플레이스 구축
3. WOO 기술을 통해 개인 입력 보호 문제 해결
4. 실험으로 시스템의 공정성 및 효율성 검증

한계

1. 증명 보상의 이차 효과: 채굴 중앙화를 초래할 수 있음
2. 회로 재사용성 제한: WOO 기술은 각 클라이언트마다 특정 회로 생성 필요
3. 신뢰할 수 있는 설정 의존: 여전히 SMPC를 위한 신뢰할 수 있는 설정 필요
4. Groth16 제한: 특정 증명 방식에 의존

향후 방향

1. 다른 증명 방식(예: STARK)의 적용 가능성 탐색
2. 중앙화 위험을 감소시키기 위한 보상 메커니즘 최적화
3. 효율성 향상을 위한 회로 재사용 메커니즘 개선
4. 더 많은 유형의 유용한 계산으로 확장

심층 평가

장점

1. 높은 혁신성: zk-SNARK 생성과 PoUW 합의를 처음으로 결합
2. 이론적 완전성: PoW의 모든 보안 요구사항을 포괄적으로 만족
3. 높은 실용 가치: 두 가지 중요한 실제 문제 해결
4. 심층 분석: 페트리 네트 모델링을 통한 체계적 평가
5. 개인정보 보호: WOO 기술이 우아한 개인 입력 솔루션 제공

부족한 점

1. 높은 복잡도: 시스템 설계가 상대적으로 복잡하며 구현 난이도 높음
2. 중앙화 위험: 증명 보상의 이차 효과로 인한 불공정 가능성
3. 확장성 제한: 회로 등록 및 신뢰할 수 있는 설정이 병목이 될 수 있음
4. 실제 검증 부족: 실제 환경에서의 대규모 테스트 부재

영향력

1. 학술 기여: PoUW 분야에 새로운 연구 방향 제시
2. 실무 의의: 더 환경 친화적인 블록체인 기술 발전 추진 가능
3. 기술 영감: WOO 기술을 다른 개인정보 보호 계산 시나리오에 적용 가능

적용 시나리오

1. 대량의 zk-SNARK 증명이 필요한 블록체인 응용
2. 개인정보 보호 요구사항이 높은 계산 외주 시나리오
3. 환경 친화적을 추구하는 신형 블록체인 프로젝트
4. 분산형 계산 능력이 필요한 응용

참고문헌

논문은 48개의 관련 문헌을 인용하며, PoW/PoUW 프로토콜, zk-SNARK 기술, 블록체인 합의 메커니즘 등 여러 분야의 중요한 연구를 포괄하여 연구에 견고한 이론적 기초를 제공한다.