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

Basic Information

• Paper ID: 2508.06489
• Title: Voting-Based Semi-Parallel Proof-of-Work Protocol
• Authors: Mustafa Doger, Sennur Ulukus (University of Maryland, College Park)
• Classification: cs.CR cs.DC cs.DM cs.IT math.IT math.PR
• Publication Date: October 10, 2025 (arXiv v2)
• Paper Link: https://arxiv.org/abs/2508.06489

Abstract

Parallel Proof-of-Work (PoW) protocols have been proposed to improve the security guarantees, transaction throughput, and confirmation latency of Nakamoto consensus. This paper first examines existing parallel PoW protocols and develops hardcoded incentive attack structures. Theoretical results and simulations demonstrate that existing parallel PoW protocols are more vulnerable to incentive attacks than Nakamoto consensus, with lower profitable thresholds and higher relative rewards. Subsequently, the paper introduces a voting-based semi-parallel PoW protocol that outperforms both Nakamoto consensus and existing parallel PoW protocols in practical aspects including communication overhead, throughput, transaction conflicts, protocol incentive compatibility, and fair transaction fee distribution between voters and leaders. The protocol's consistency is evaluated using state-of-the-art analysis, and a Markov Decision Process (MDP) model is employed to confirm claims regarding the protocol's resistance to incentive attacks.

Research Background and Motivation

Problem Context

1. Limitations of Nakamoto Consensus:
   • Block arrival times follow an exponential distribution with high variance, allowing adversaries to profit by deviating from honest behavior
   • Small miners must wait extended periods to receive rewards (potentially decades in Bitcoin)
   • Unfair reward distribution incentivizes miners to form mining pools, threatening decentralization and creating new vulnerabilities
2. Inadequacies of Existing Solutions:
   • Existing parallel PoW protocols reduce variance but suffer from serious incentive attack vulnerabilities
   • High communication overhead and severe transaction conflict issues
   • Lack of rigorous security violation analysis

Research Motivation

This work aims to design a protocol that combines the advantages of parallel PoW (reduced variance, increased throughput) while effectively resisting incentive attacks.

Core Contributions

1. Vulnerability Discovery: Conducts in-depth analysis of existing parallel PoW protocols (Bobtail, Tailstorm, DAG-style voting), revealing they are more vulnerable to incentive attacks than Nakamoto consensus
2. Protocol Design: Proposes a voting-based semi-parallel PoW protocol achieving:
   • Reduced communication overhead
   • Elimination of transaction conflicts
   • Enhanced incentive compatibility
   • Fair transaction fee distribution
3. Theoretical Analysis:
   • Evaluates double-spending attack probability using state-of-the-art security delay analysis
   • Constructs MDP model to analyze incentive attack resistance
   • Provides rigorous mathematical proofs and simulation verification
4. Performance Improvements: Outperforms existing solutions across multiple practical dimensions including security, throughput, and fairness

Methodology Details

Task Definition

Design a blockchain consensus protocol with miner proof-of-work and transaction proposals as inputs, and confirmed transaction ledger as output, satisfying:

• Security: Resistance to double-spending and incentive attacks
• Liveness: Guarantee of eventual transaction confirmation
• Fairness: Reasonable reward distribution mechanism

Protocol Architecture

1. Block and Chain Structure

• Each block contains L or L+1 valid PoW solutions (proofs)
• Proofs classified into two types:
  • Initiator Proof: Contains 6 components ωᵢʰ = (ωᵢ,₁ʰ, ..., ωᵢ,₆ʰ)
  • Incremental Proof: Similar structure with incremental height information

2. Key Components

• ωᵢ,₆ʰ: Nonce ensuring fₕ(ωᵢʰ) < Tₗ
• ωᵢ,₅ʰ: Miner address hash
• ωᵢ,₄ʰ: Merkle root of proposed ledger
• ωᵢ,₃ʰ: Accumulated transaction fees
• ωᵢ,₂ʰ: Proof digest of previous block

3. Ledger Election Mechanism

Selects ledger with highest fee payment:

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

4. Communication Optimization

• Miners conceal proposed ledgers until accumulating L votes
• Only winning ledger requires sharing, significantly reducing communication overhead
• Incremental proofs average approximately (6+Es̄)×32 bytes

Technical Innovations

1. Semi-Parallel Design:
   • Allows at most two parallel proofs at the same proof height
   • Borrows k-cluster rule from PHANTOM protocol (k=1)
   • Balances parallelism and security
2. Voting Mechanism:
   • Each proof serves as both a vote for the previous block and a ledger proposal for the current block
   • Achieves incentive compatibility by concealing ledger content while revealing fee amounts
3. Reward Distribution:
   • Parallel proofs share rewards equally (penalty mechanism)
   • Transaction fees distributed proportionally between ledger creator and voters
   • Leader receives r proportion, voters share (1-r) proportion

Experimental Setup

Attack Model Analysis

1. Bobtail Protocol:
   • Develops DoS proof withholding attack
   • Profitable threshold αₜ = 0 (any hash power can profit from attack)
2. Tailstorm Protocol:
   • Proof withholding attack
   • Profitable threshold αₜ ≤ 1/L
3. DAG-style Voting:
   • When α > 1/3, attack is more advantageous than Nakamoto's selfish mining upper bound

Simulation Parameters

• Network delay: δ = 1 second (proofs), Δ = 10 seconds (ledgers)
• Bitcoin parameters: λB = 1/600, α = 0.25
• Parallelism degree: L = 10, 25, 50, 100
• Simulation rounds: 100,000 - 1,000,000

MDP Model

• State space: (a, h, fork, p) where p indicates parallel proof existence
• Action space: adopt, override, match, wait
• Objective function: relative reward ratio

Experimental Results

Existing Protocol Vulnerability Verification

Security Analysis

1. Double-Spending Attack Probability:
   • L=50, α=0.25, 1-block confirmation: upper bound ~10⁻⁴
   • Compared to Bitcoin's 22-block confirmation achieving 10⁻³, this protocol achieves superior security in less than 2 block times
2. Incentive Attack Resistance:
   • More secure than Nakamoto consensus when γ≥0.3
   • Slightly inferior when γ<0.3 but still superior to existing parallel PoW protocols

Performance Improvements

• Communication Overhead: Significantly reduced, transmitting only winning ledger
• Transaction Conflicts: Completely eliminated, single miner creates ledger
• Throughput: Arbitrarily scalable, ledger size proportional to proof height
• Fairness: Small miners receive rewards regularly

Related Work

Parallel PoW Protocols

• Original Parallel PoW: Requires L parallel proofs, vulnerable to proof withholding attacks
• Bobtail: Introduces support value mechanism but remains susceptible to minimum hash attacks
• Tailstorm/DAG-style: Tree and DAG structures with reward mechanism defects

Other Improvement Approaches

• Fruitchain: Increased throughput and fairness
• Bitcoin-NG: Leader election mechanism
• GHOST/PHANTOM: DAG structures allowing multiple parent blocks
• Multi-stage PoW: Decomposing PoW into multiple stages

Conclusions and Discussion

Main Conclusions

1. Existing parallel PoW protocols are more fragile against incentive attacks than Nakamoto consensus
2. The proposed semi-parallel protocol achieves significant improvements in security, efficiency, and fairness
3. Clever design achieves balance between parallelism and security

Limitations

1. Requires assumption of small network delays
2. Joint attack analysis of transaction fees and mining rewards requires further refinement
3. Implementation details for practical deployment need further consideration

Future Directions

1. Consider fair reward mechanisms under higher k-cluster rules
2. Analyze more complex network models and attack strategies
3. Prototype implementation and testing of actual systems

In-Depth Evaluation

Strengths

1. Theoretical Rigor: Provides complete mathematical analysis and MDP modeling
2. Problem Importance: Addresses critical security issues in parallel PoW protocols
3. Methodological Innovation: Clever combination of semi-parallel design and voting mechanism
4. Comprehensive Experiments: Combines theoretical analysis with simulation verification
5. Practical Value: Improvements across multiple dimensions

Weaknesses

1. Complexity: Relatively complex protocol design with high implementation difficulty
2. Assumption Constraints: Network delay assumptions may be difficult to satisfy in practice
3. Parameter Tuning: Multiple parameters (L, r, etc.) require more guidance for optimal selection
4. Long-term Analysis: Lacks dynamic analysis of long-term economic incentives

Impact

1. Academic Value: Reveals systematic security issues in parallel PoW protocols
2. Practical Significance: Provides new insights for blockchain protocol design
3. Reproducibility: Provides detailed algorithm and simulation code framework

Applicable Scenarios

• Blockchain applications requiring high throughput and low latency
• Decentralized systems with high fairness requirements
• Environments with relatively stable network conditions

References

The paper cites 48 relevant references covering important works in blockchain consensus, incentive mechanisms, security analysis, and other areas, providing a solid theoretical foundation for the research.