  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.
