2025-11-15T03:58:11.519172

Voting-Based Semi-Parallel Proof-of-Work Protocol

Doger, Ulukus

Parallel Proof-of-Work (PoW) protocols are suggested to improve the safety guarantees, transaction throughput and confirmation latencies of Nakamoto consensus. In this work, we first consider the existing parallel PoW protocols and develop hard-coded incentive attack structures. Our theoretical results and simulations show that the existing parallel PoW protocols are more vulnerable to incentive attacks than the Nakamoto consensus, e.g., attacks have smaller profitability threshold and they result in higher relative rewards. Next, we introduce a voting-based semi-parallel PoW protocol that outperforms both Nakamoto consensus and the existing parallel PoW protocols from most practical perspectives such as communication overheads, throughput, transaction conflicts, incentive compatibility of the protocol as well as a fair distribution of transaction fees among the voters and the leaders. We use state-of-the-art analysis to evaluate the consistency of the protocol and consider Markov decision process (MDP) models to substantiate our claims about the resilience of our protocol against incentive attacks.

academic

투표 기반 반병렬 작업증명 프로토콜

기본 정보

논문 ID: 2508.06489
제목: Voting-Based Semi-Parallel Proof-of-Work Protocol
저자: Mustafa Doger, Sennur Ulukus (메릴랜드 대학교 칼리지 파크)
분류: cs.CR cs.DC cs.DM cs.IT math.IT math.PR
발표 시간: 2025년 10월 10일 (arXiv v2)
논문 링크: https://arxiv.org/abs/2508.06489

초록

병렬 작업증명(Parallel Proof-of-Work, PoW) 프로토콜은 나카모토 합의의 보안 보장, 거래 처리량 및 확인 지연을 개선하기 위해 제안되었습니다. 본 논문은 먼저 기존의 병렬 PoW 프로토콜을 검토하고 하드코딩된 인센티브 공격 구조를 개발합니다. 이론적 결과와 시뮬레이션은 기존 병렬 PoW 프로토콜이 나카모토 합의보다 인센티브 공격에 더 취약함을 보여주며, 공격이 더 낮은 수익성 임계값을 가지며 더 높은 상대 보상을 초래합니다. 다음으로, 본 논문은 통신 오버헤드, 처리량, 거래 충돌, 프로토콜 인센티브 양립성 및 투표자와 리더 간의 거래 수수료 공정한 분배 등의 실용적 측면에서 나카모토 합의 및 기존 병렬 PoW 프로토콜을 능가하는 투표 기반 반병렬 PoW 프로토콜을 소개합니다. 최첨단 분석을 사용하여 프로토콜의 일관성을 평가하고, 마르코프 결정 과정(MDP) 모델을 고려하여 프로토콜의 인센티브 공격 저항성에 관한 주장을 확인합니다.

연구 배경 및 동기

문제 배경

나카모토 합의의 한계:
- 블록 도착 시간이 지수분포를 따르며 높은 분산 특성을 가지므로, 공격자가 이러한 높은 분산을 이용하여 정직한 행동에서 벗어나 이익을 얻을 수 있음
- 소규모 채굴자는 보상을 받기 위해 매우 오랜 시간을 기다려야 함(예: 비트코인 시스템에서 수십 년 소요 가능)
- 불공정한 보상 분배로 인해 채굴자들이 채굴풀을 구성하게 되어 탈중앙화를 위협하고 새로운 취약점 생성
기존 해결책의 부족함:
- 기존 병렬 PoW 프로토콜은 분산을 감소시키지만 인센티브 공격 측면에서 심각한 결함 존재
- 통신 오버헤드가 크고 거래 충돌 문제 심각
- 보안 위반에 대한 엄격한 분석 부족

연구 동기

본 논문은 병렬 PoW의 장점(분산 감소, 처리량 증가)을 누리면서도 인센티브 공격에 효과적으로 저항할 수 있는 새로운 프로토콜을 설계하는 것을 목표로 합니다.

핵심 기여

취약점 발견: 기존 병렬 PoW 프로토콜(Bobtail, Tailstorm, DAG 스타일 투표)에 대한 심층 분석을 통해 나카모토 합의보다 인센티브 공격에 더 취약함을 발견
프로토콜 설계: 다음 특성을 구현하는 투표 기반 반병렬 PoW 프로토콜 제안:
- 통신 오버헤드 감소
- 거래 충돌 회피
- 인센티브 양립성 향상
- 공정한 거래 수수료 분배
이론적 분석:
- 최첨단 보안 지연 분석을 사용하여 이중 지불 공격 확률 평가
- 인센티브 공격 저항력 분석을 위한 MDP 모델 구축
- 엄격한 수학적 증명 및 시뮬레이션 검증 제공
성능 향상: 보안, 처리량 및 공정성을 포함한 여러 실용적 측면에서 기존 방안을 능가

방법론 상세 설명

작업 정의

채굴자의 작업증명과 거래 제안을 입력으로 받고 확인된 거래 원장을 출력으로 하는 블록체인 합의 프로토콜 설계. 다음을 만족해야 함:

보안성: 이중 지불 및 인센티브 공격 저항
활성: 거래 최종 확인 보장
공정성: 합리적인 보상 분배 메커니즘

프로토콜 아키텍처

1. 블록 및 체인 구조

각 블록은 L 또는 L+1개의 유효한 PoW 솔루션(증명) 포함
증명은 두 가지 유형으로 분류:
- 개시자 증명: 6부분 포함 ωᵢʰ = (ωᵢ,₁ʰ, ..., ωᵢ,₆ʰ)
- 증분 증명: 유사한 구조이지만 증분 높이 정보 포함

2. 핵심 구성 요소

ωᵢ,₆ʰ: 난스(Nonce), fₕ(ωᵢʰ) < Tₗ 보장
ωᵢ,₅ʰ: 채굴자 주소 해시
ωᵢ,₄ʰ: 제안된 원장의 머클 루트
ωᵢ,₃ʰ: 누적 거래 수수료
ωᵢ,₂ʰ: 이전 블록의 증명 요약

3. 원장 선택 메커니즘

최고 수수료를 지불하는 원장 선택:

ωᵢ,₁ʰ = ωⱼ*,₄ʰ⁻¹ where j* = argmax_j{v(ωⱼ,₃ʰ⁻¹)}

4. 통신 최적화

채굴자는 L개의 투표를 누적할 때까지 제안된 원장 숨김
승리한 원장만 공유 필요로 하여 통신 오버헤드 대폭 감소
증분 증명은 평균적으로 약 (6+Es̄)×32 바이트만 포함

기술 혁신 포인트

반병렬 설계:
- 동일한 증명 높이에서 최대 두 개의 병렬 증명 허용
- PHANTOM 프로토콜의 k-클러스터 규칙 차용(k=1)
- 병렬성과 보안성 간의 균형 달성
투표 메커니즘:
- 각 증명은 이전 블록에 대한 투표이면서 동시에 현재 블록의 원장 제안
- 원장 내용은 숨기되 수수료 금액은 공개하여 인센티브 양립성 구현
보상 분배:
- 병렬 증명은 보상을 균등 분배(처벌 메커니즘)
- 거래 수수료는 원장 생성자와 투표자 간에 비례 분배
- 리더가 r 비율 획득, 투표자가 (1-r) 비율 공유

실험 설정

공격 모델 분석

Bobtail 프로토콜:
- DoS 증명 보류 공격 개발
- 수익성 임계값 αₜ = 0(모든 계산력이 수익성 있는 공격 가능)
Tailstorm 프로토콜:
- 증명 보류 공격
- 수익성 임계값 αₜ ≤ 1/L
DAG 스타일 투표:
- α > 1/3일 때, 공격이 나카모토 합의의 자기중심 채굴 상한보다 더 유리

시뮬레이션 매개변수

네트워크 지연: δ = 1초(증명), Δ = 10초(원장)
비트코인 매개변수: λB = 1/600, α = 0.25
병렬도: L = 10, 25, 50, 100
시뮬레이션 라운드: 100,000 - 1,000,000회

MDP 모델

상태 공간: (a, h, fork, p) 여기서 p는 병렬 증명 존재 여부
행동 공간: adopt, override, match, wait
목적 함수: 상대 보상 비율

실험 결과

기존 프로토콜 취약점 검증

프로토콜	수익성 임계값	α=0.33일 때 상대 보상	주요 문제
Bobtail	0	~0.65	정보 우위 공격
Tailstorm	1/L	~0.66	증명 보류 공격
DAG 스타일	>1/L	~0.70	보상 메커니즘 결함

보안성 분석

이중 지불 공격 확률:
- L=50, α=0.25, 1-블록 확인: 상한 약 10⁻⁴
- 비트코인의 22-블록 확인이 10⁻³에 도달하는 것과 비교하면, 본 프로토콜은 2개 미만의 블록 시간 내에 더 나은 보안성 달성
인센티브 공격 저항력:
- γ≥0.3일 때 나카모토 합의보다 더 안전
- γ<0.3일 때 나카모토 합의보다 약간 열등하지만 기존 병렬 PoW 프로토콜보다 여전히 우수