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.
- Key Structure: The secret key consists of elements mapped to the bits of a Bloom filter.
- 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.
- 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.
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