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

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

基本信息

  • 论文ID: 2508.06489
  • 标题: Voting-Based Semi-Parallel Proof-of-Work Protocol
  • 作者: Mustafa Doger, Sennur Ulukus (University of Maryland, College Park)
  • 分类: 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)模型来证实关于协议对激励攻击抵抗力的声明。

研究背景与动机

问题背景

  1. 中本聪共识的局限性：
    • 区块到达时间服从指数分布，具有高方差特性，使得对手可以利用这种高方差通过偏离诚实行为获利
    • 小矿工需要等待很长时间才能获得奖励（例如在比特币系统中可能需要数十年）
    • 不公平的奖励分配导致矿工组成矿池，威胁去中心化并创造新的漏洞
  2. 现有解决方案的不足：
    • 现有并行PoW协议虽然降低了方差，但在激励攻击方面存在严重漏洞
    • 通信开销大，交易冲突问题严重
    • 缺乏严格的安全违规分析

研究动机

本文旨在设计一个既能享受并行PoW优势（降低方差、提高吞吐量），又能有效抵御激励攻击的新协议。

核心贡献

  1. 漏洞发现：对现有并行PoW协议（Bobtail、Tailstorm、DAG-style voting）进行深入分析，发现它们比中本聪共识更容易受到激励攻击
  2. 协议设计：提出基于投票的半并行PoW协议，实现以下特性：
    • 降低通信开销
    • 避免交易冲突
    • 提高激励兼容性
    • 公平的交易费用分配
  3. 理论分析：
    • 使用最先进的安全延迟分析评估双花攻击概率
    • 构建MDP模型分析激励攻击抵抗力
    • 提供严格的数学证明和仿真验证
  4. 性能提升：在多个实用角度均优于现有方案，包括安全性、吞吐量和公平性

方法详解

任务定义

设计一个区块链共识协议，输入为矿工的工作量证明和交易提案，输出为确认的交易账本，需要满足：

  • 安全性：抵御双花和激励攻击
  • 活性：保证交易最终确认
  • 公平性：合理的奖励分配机制

协议架构

1. 区块和链结构

  • 每个区块包含L或L+1个有效PoW解（证明）
  • 证明分为两类：
    • 发起者证明：包含6部分 ωᵢʰ = (ωᵢ,₁ʰ, ..., ωᵢ,₆ʰ)
    • 增量证明：类似结构但具有增量高度信息

2. 关键组件

  • ωᵢ,₆ʰ：随机数，确保 fₕ(ωᵢʰ) < Tₗ
  • ωᵢ,₅ʰ：矿工地址哈希
  • ωᵢ,₄ʰ：提议账本的Merkle根
  • ωᵢ,₃ʰ：累计交易费用
  • ωᵢ,₂ʰ：前一区块的证明摘要

3. 账本选举机制

选择支付最高费用的账本：

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

4. 通信优化

  • 矿工隐藏提议账本直到累积L个投票
  • 只有获胜账本需要共享，大幅降低通信开销
  • 增量证明平均只包含约(6+Es̄)×32字节

技术创新点

  1. 半并行设计：
    • 允许最多两个并行证明在同一证明高度
    • 借鉴PHANTOM协议的k-cluster规则（k=1）
    • 在并行性和安全性之间找到平衡
  2. 投票机制：
    • 每个证明既是对前一区块的投票，也是对当前区块的账本提案
    • 通过隐藏账本内容但公开费用金额实现激励兼容
  3. 奖励分配：
    • 并行证明平分奖励（惩罚机制）
    • 交易费用在账本创建者和投票者间按比例分配
    • 领导者获得 r 比例，投票者分享 (1-r) 比例

实验设置

攻击模型分析

  1. Bobtail协议：
    • 开发DoS证明扣留攻击
    • 盈利阈值αₜ = 0（任何算力都可盈利攻击）
  2. Tailstorm协议：
    • 证明扣留攻击
    • 盈利阈值αₜ ≤ 1/L
  3. DAG-style投票：
    • 当α > 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时相对奖励主要问题
Bobtail0~0.65信息优势攻击
Tailstorm1/L~0.66证明扣留攻击
DAG-style>1/L~0.70奖励机制缺陷

安全性分析

  1. 双花攻击概率：
    • L=50, α=0.25, 1-区块确认：上界约10⁻⁴
    • 相比比特币22区块确认达到10⁻³，本协议在不到2个区块时间内达到更好安全性
  2. 激励攻击抵抗力：
    • γ≥0.3时比中本聪共识更安全
    • γ<0.3时略逊于中本聪共识但仍优于现有并行PoW协议

性能提升

  • 通信开销：大幅降低，只需传输获胜账本
  • 交易冲突：完全避免，单一矿工创建账本
  • 吞吐量：可任意扩展，账本大小与证明高度成正比
  • 公平性：小矿工也能定期获得奖励

相关工作

并行PoW协议

  • 原始并行PoW：需要L个并行证明，存在证明扣留攻击漏洞
  • Bobtail：引入支持值机制，但仍易受最小哈希攻击
  • Tailstorm/DAG-style：树形和DAG结构，奖励机制存在缺陷

其他改进方案

  • Fruitchain：提高吞吐量和公平性
  • Bitcoin-NG：领导者选举机制
  • GHOST/PHANTOM：允许多父区块的DAG结构
  • 多阶段PoW：将PoW分解为多个阶段

结论与讨论

主要结论

  1. 现有并行PoW协议在激励攻击方面比中本聪共识更脆弱
  2. 提出的半并行协议在安全性、效率和公平性方面均有显著改进
  3. 通过巧妙的设计实现了并行性和安全性的平衡

局限性

  1. 需要网络延迟较小的假设
  2. 交易费用和挖矿奖励的联合攻击分析仍需完善
  3. 实际部署中的实现细节需要进一步考虑

未来方向

  1. 考虑更高k-cluster规则下的公平奖励机制
  2. 分析更复杂的网络模型和攻击策略
  3. 实际系统的原型实现和测试

深度评价

优点

  1. 理论严谨：提供了完整的数学分析和MDP建模
  2. 问题重要：解决了并行PoW协议的关键安全问题
  3. 方法创新：半并行设计和投票机制的巧妙结合
  4. 实验充分：理论分析与仿真验证相结合
  5. 实用价值：在多个维度均有实际改进

不足

  1. 复杂性：协议设计相对复杂，实现难度较高
  2. 假设限制：对网络延迟的假设可能在实际中难以满足
  3. 参数调优：多个参数（L, r等）的最优选择需要更多指导
  4. 长期分析：缺乏长期经济激励的动态分析

影响力

  1. 学术价值：揭示了并行PoW协议的系统性安全问题
  2. 实践意义：为区块链协议设计提供了新的思路
  3. 可复现性：提供了详细的算法和仿真代码框架

适用场景

  • 需要高吞吐量和低延迟的区块链应用
  • 对公平性要求较高的去中心化系统
  • 网络条件相对稳定的环境

参考文献

论文引用了48篇相关文献，涵盖了区块链共识、激励机制、安全分析等多个方面的重要工作，为研究提供了坚实的理论基础。