Puncturable Signatures and Applications in Proof-of-Stake Blockchain Protocol

Xinyu Li, Jing Xu, Xiong Fan, Yuchen Wang, Zhenfeng Zhang

Abstract

Proof-of-stake (PoS) blockchain protocols offer a sustainable alternative to energy-intensive proof-of-work systems. However, they are uniquely vulnerable to long-range secret key leakage (LRSL) attacks, where an adversary compromises old keys to rewrite history. This paper introduces an efficient puncturable signature scheme based on Bloom filters and the strong Diffie-Hellman assumption. By enabling fine-grained, near-instantaneous key puncturing, the proposed construction provides a practical defense against LRSL attacks. Experimental results demonstrate that this scheme significantly outperforms traditional forward-secure signatures in terms of signature size, signing/verification speed, and key update efficiency.

Introduction

In PoS blockchains, validators are selected based on their stake. A critical threat in this environment is the long-range attack: if an adversary obtains the secret keys of users who held a majority stake at some point in the past, they can sign an alternative chain history. To mitigate this, validators must evolve their keys so that old messages (or time slots) can no longer be signed. While forward-secure signatures (FSS) have been used for this purpose, they often suffer from performance bottlenecks that hinder practical deployment.

The Puncturable Signature Scheme

The authors propose a puncturable signature (PS) scheme that allows a user to "puncture" their secret key for a specific message prefix, such as a slot ID. Once a key is punctured for a specific slot, it can never again produce a valid signature for that slot, effectively neutralizing the threat of historical forgery even if the current key is leaked.

Innovation: Bloom Filter Integration

The core of the efficiency gains lies in the use of a Bloom filter—a space-efficient probabilistic data structure.

  1. Key Structure: The secret key consists of elements mapped to the bits of a Bloom filter.
  2. Puncturing Mechanism: To revoke the ability to sign a specific slot ID, the user hashes the ID to identify indices in the Bloom filter and deletes the corresponding secret key elements.
  3. Probabilistic Trade-off: While Bloom filters can have false positives (potentially preventing a validator from signing a legitimate block), the authors argue this minor liveness risk is a necessary trade-off for the massive security and speed gains required for real-time blockchain consensus.

Key Results

The proposed scheme was implemented in C using the AMCL library and benchmarked against two leading forward-secure signature schemes ([10] and [11]) at 128-bit and 192-bit security levels.

Extracted figure from page 3 of Puncturable Signatures and Applications in Proof-of-Stake Blockchain Protocol

As shown in the experimental data, the puncturable signature scheme achieves dramatic improvements:

  • Key Update Efficiency: Key updates are nearly instantaneous (approx. $10^{-5}$ ms), whereas traditional FSS schemes require hundreds to thousands of milliseconds.
  • Signature Size: The signatures remain small and constant in size. At 128-bit security, the signature is only 129 bytes, significantly smaller than the 418 bytes to 1.87 KB required by FSS alternatives.
  • Computational Speed: Both signing and verification times are substantially reduced, facilitating higher transaction throughput.

Conclusion

By leveraging Bloom filters for prefix-based puncturing, this work provides a highly efficient cryptographic primitive tailored for PoS blockchains. The scheme effectively resolves the performance issues associated with long-range attack prevention, offering a scalable path forward for secure, decentralized protocols. Future work may address the initial secret key storage requirements and explore methods to eliminate the small probabilistic error inherent in Bloom filter constructions.

Summary updated

Abstract

Proof-of-stake blockchain protocols are becoming one of the most promising alternatives to the energy-consuming proof-of-work protocols. However, one particularly critical threat in the PoS setting is the well-known long-range attacks caused by secret key leakage (LRSL attack). Specifically, an adversary can attempt to control/compromise accounts possessing substantial stake at some past moment such that double-spend or erase past transactions, violating the fundamental persistence property of blockchain. Puncturable signatures provide a satisfying solution to construct practical proof-of-stake blockchain resilient to LRSL attack, despite of the fact that existent constructions are not efficient enough for practical deployments. In this paper, we provide an in-depth study of puncturable signatures and explore its applications in the proof-of-stake blockchain. We formalize a security model that allows the adversary for adaptive signing and puncturing queries, and show a construction with efficient puncturing operations based on the Bloom filter data structure and strong Diffie-Hellman assumption. The puncturing functionality we desire is for a particular part of message, like prefix, instead of the whole message. Furthermore, we use puncturable signatures to construct practical proof-of-stake blockchain protocols that are resilient to LRSL attack, while previously the forward-secure signature is used to immunize this attack. We implement our scheme and provide experimental results showing that in comparison with the forward-secure signature, our construction performs substantially better on signature size, signing and verification efficiency, significantly on key update efficiency.
BibTeX
@misc{li2019puncturable,
  author = {Xinyu Li and Jing Xu and Xiong Fan and Yuchen Wang and Zhenfeng Zhang},
  title = {{Puncturable Signatures and Applications in Proof-of-Stake Blockchain Protocol}},
  year = {2019},
  eprint = {1909.03955},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.03955},
}

Loading related content...

Figure