기술 요약: SNARKChain – 범용 SNARK 마켓플레이스를 갖춘 유용한 작업 증명(PoUW) 블록체인

1. 문제 정의

작업 증명(PoW)은 가장 안전한 허가 없는 합의 프로토콜로 남아 있으나, 블록체인 외부에서는 가치를 창출하지 못하는 계산 집약적인 퍼즐(예: 해시 충돌)에 의존하기 때문에 심각한 환경적 비효율성을 겪고 있습니다. 유용한 작업 증명(PoUW)은 이러한 임의의 퍼즐을 과학적 시뮬레이션이나 암호학적 증명과 같이 실질적인 가치를 생성하는 작업으로 대체하는 것을 목표로 합니다. 그러나 기존의 PoUW 제안들은 신선도(replay attack에 대한 저항성), 체인 무결성 임베딩, 그리고 채굴자 신원 바인딩과 같은 엄격한 PoW 보안 요구 사항을 충족하는 데 어려움을 겪고 있습니다.

동시에, 영지식 증명(zk-SNARK)의 생성은 많은 사용자에게 계산적으로 매우 부담스러워 외주화가 필요합니다. SNARK 생성을 위한 탈중앙화된 마켓플레이스가 존재하기는 하지만, 이들은 대개 애플리케이션 계층에서 작동하거나 특수화된 회로(circuit)로 제한되어 있으며, 일반적인 역량을 유지하면서 증명 생성을 합의 계층에 직접 통합하는 데 실패하고 있습니다.

2. 방법론

저자들은 클라이언트가 외주를 준 SNARK 증명 생성이 "유용한 작업"이 되는 새로운 합의 프로토콜인 SNARKChain을 제안합니다. 이 시스템은 증명을 생성하여 네트워크를 보호하는 채굴자들이 존재하는 탈중앙화된 마켓플레이스로 기능합니다.

핵심 아키텍처

네트워크는 세 가지 참여자 역할을 구성합니다:

1. 클라이언트(Clients): 코인 트랜잭션과 함께 SNARK 생성을 요청하는 산술 회로 및 파라미터가 포함된 "증명 트랜잭션"을 제출합니다.
2. 채굴자(Miners/Full Nodes): 트랜잭션을 선택하고, 필요한 SNARK 증명을 생성하며, 블록을 게시하기 위해 경쟁합니다. 이들은 증명이 포함된 블록에 대한 보상을 받습니다.
3. 회로 레지스트리 노드(Circuit Registry Nodes): 산술 회로의 탈중앙화된 등록, 증명/검증 키의 저장, 그리고 신뢰할 수 있는 설정(Trusted Setup)을 위한 보안 다자간 계산(SMPC)에 참여하는 스테이킹된 하위 네트워크입니다.

합의 메커니즘: 로터리(Lottery)와 무결성

PoUW의 특정 과제를 해결하기 위해, 프로토콜은 로터리 메커니즘과 무결성 바인딩을 도입합니다:

• 로터리 기반 블록 선택: 현재의 난이도 목표($\kappa$)에 대한 생성된 증명의 복잡도($C_i$)에 비례하는 가중치 로터리를 사용합니다. 이는 고정된 난이도 임계값에 도달하도록 요구하는 대신(이는 가장 강력한 채굴자에 의한 중앙화를 초래함), 다음과 같은 승리 확률($P_{win}$)을 가집니다:
  $$P_{win}(i) = \frac{C_i}{\kappa}$$
  이를 통해 **진전 독립성(progress-freeness)**을 보장합니다. 즉, 승리 확률은 이미 소비한 시간에 의존하는 것이 아니라 가장 최근에 생성된 증명에만 의존합니다.

• 무결성 파라미터($\eta$): 증명 탈취 및 재사용 공격(replay attacks)을 방출하기 위해, 각 산술 회로는 공용 integrity 파라미터를 포함하도록 수정됩니다. 이 파라미터는 구성 중인 블록 헤더의 해시로부터 유도됩니다. 만약 채굴자가 로터리에서 탈락할 경우, 그들은 새로 생성된 증명을 포함하도록 무결성 파라미터를 다시 계산해야 하며, 이는 블록 내에 암호학적으로 연결된 증명 체인을 생성합니다. 이는 증명이 검증을 무효화하지 않고 다른 블록에서 재사용될 수 없도록 보장합니다.

• 분산 방지(Amortization Prevention): 채굴자들이 증명을 배치(batching)함으로써 부당한 이득을 취하는 것을 방지하기 위해, 시스템은 mask 파라미터(채굴자 주소와 회로 사용 횟수의 결합)를 사용하며, 공용 입력(integrity 파라미터와 같은)의 변경이 Groth16에서의 전체 QAP 평가를 무효화하여 전체 재계산을 요구하도록 보장합니다.

• 버케팅(Bucketing): 여러 채굴자가 병렬로 작업할 때 발생하는 트랜잭션 중복으로 인한 낭비된 작업을 줄이기 위해, 프로토콜은 트랜잭션 해시 접두사를 기준으로 트랜잭션 공간을 "버킷"으로 분할합니다. 채굴자는 버킷을 선택함으로써 서로 겹치지 않는 트랜잭션 세트를 확보하고 충돌을 최소화합니다.

암호학적 세부 사항

시스템은 Groth16 SNARK를 활용합니다. 저자들은 Groth16의 상수 크기 증명(128 바이트)과 제약 조건 수에 따른 선형 증명 시간 때문에 이를 선택했습니다. 프로토콜은 단일 특수 회로에 국한되지 않고 (ZoKrates나 Circom과 같은 DSL로 정의된) 범용 회로를 지원합니다.

3. 주요 기여

본 논문은 다음과 같은 기여를 주장합니다:

1. 최초의 합의 계층 SNARK 마켓플레이스: 본 제안은 증명 생성이 블록 보안과 분리될 수 없는 데로, 합의 계층에서 직접 작동하는 범용 zk-SNARK 생성에 대한 최초의 탈중앙화된 마켓플레이스를 나타냅니다.
2. PoUW 프로토콜 설계: 자원 집약적인 SNARK 계산을 노드로 오프로딩하여, PoW의 모든 중요한 속성(비대칭성, 입도성, 분산 방지성, 독립성, 효율성, 위조 불가능성, 신선도, 결정론, 진전 독립성, 공개 검증 가능성)을 충족하는 독창적인 접근 방식을 제공합니다.
3. 프라이빗 입력 처리: 초기 설계의 공용 파라미터 제한 문제를 해결하기 위해, 위트니스 난독화 외주화(witness obfuscation outsourcing)를 통한 프라이빗 파라미터 처리 방법을 제안합니다(부록에 상세 기술).
4. 보안 분석: Stochastic Time Colored Petri Nets를 사용한 정식 분석 및 시뮬레이션을 통해 프로토콜이 공정성과 보안 속성을 유지함을 입증합니다.

4. 결과 및 평가

저자들은 네 가지 가설을 테스트하기 위해 페트리 네트(Petri net) 모델을 사용하여 프로토콜을 평가했습니다:

• H1 (공정성): 보상 분포는 채굴 능력에 상응합니다. 시뮬레이션 결과, 블록 보상은 계산 능력에 따라 선형적으로 확장됨을 확인했습니다. 그러나 증명 보상은 능력에 따라 이차적 의존성을 보였으며, 이는 채굴 풀의 중앙화를 방지하기 위해 증명 보상을 블록 보상에 비해 최소화해야 함을 시사합니다.
• H2 (독립성): 선택된 증명의 복잡도가 보상을 불공정하게 왜곡하지 않습니다. 결과에 따르면, 더 큰 증명을 선호하는 채굴자가 불균형적인 블록 보상을 얻지는 않았으나, 더 많은 증명을 생성했습니다.
• H3 (중앙화 vs 효율성): 더 긴 증명 체인을 선호하도록 하는 파라미터($\psi$)를 도입하면 낭비되는 작업은 줄어들지만 중앙화는 증가합니다. 이 트레이드오프는 효율성을 개선할 수는 있지만, 네트워크의 공정성을 해칠 위험이 있음을 시사합니다.
• H4 (버케팅): 버킷 수를 늘리면 트랜잭션 중복으로 인한 낭비된 작업이 크게 감소합니다. 시뮬레이션 결과, 더 많은 버킷 수가 더 낮은 낭비된 작업 비율과 상관관계가 있음을 보여주었습니다.

분석 결과, Groth16은 증명 생성 시간에 대해 필요한 선형 스케일링을 제공하여 프로토콜을 예측 가능하고 확장 가능하게 만듭니다.

5. 의의 및 주장

본 논문은 SNARKChain을 블록체인의 에너지 낭비와 zk-SNARK 생성의 높은 비용이라는 이중 과제에 대한 해결책으로 포지셔닝합니다.

• 보안: 이전의 PoUW 제안들과 달리, 이 시스템은 체인의 무결성과 채굴자의 신원을 퍼즐 솔루션에 직접 임베딩하여 PoW의 엄격한 "신선도" 및 "위조 불가능성" 요구 사항을 충족합니다.
• 유용성: 이는 PoW의 "낭비"를 프라이버시, 확장성 및 광범위한 애플리케이션에서의 크로스체인 상호 운용성에 사용될 수 있는 가치 있는 암호학적 증명으로 전환합니다.
• 참신함: 저자들은 자신들이 알고 있는 한, 이것이 일반 목적의 SNARK 생성을 합의 계층에 성공적으로 통합하면서 모든 필수적인 PoW 속성을 충족하는 최초의 시스템이라고 주장합니다.

결론적으로, ($\psi$ 파라미터를 통한 낭비된 작업과 중앙화 사이의 트레이드오프와 같은) 과제가 남아 있음에도 불구하고, 제안된 프로토콜은 유용한 암호학적 부산물을 생성하는 안전하고 에너지 효율적인 블록체인을 향한 실행 가능한 경로를 제공합니다.