Proof-of-stake blockchains are vulnerable to long range attacks. In a long range attack, an adversary obtains the keys of past validators (e.g., by bribing them at no cost since they do not use these keys anymore) and is thus able to re-write the entire history of the blockchain with those. We propose Winkle, a decentralized checkpointing mechanism operated by coin holders, whose keys are harder to compromise than validators'. The idea is that coin holders will vote for a block in order to certify the chain. Every time someone sends a transaction, it will contain a vote for a block. Whenever enough users (weighted by the amount of money they own) have voted for that block, it is considered checkpointed. The difficulty of designing such a scheme comes from the fact that money changes hands constantly. We present proofs of security based on flexible security assumptions. We discuss how users key rotation increases security, how minting coins can be accommodated and how delegation allows for faster checkpointing. We evaluate how quickly checkpoint occurs using an experimental evaluation on the Bitcoin and Ethereum blockchains, with and without delegation.

This is joint work with Lera Nikolaenko and George Danezis.