Several blockchain projects are considering proof-of-stake mechanisms in place of proof-of-work, attracted by the lower energy costs. Some proof-of-stake protocols based on BFT systems such as HotStuff or Tendermint appear to provide faster and deterministic finality. In these protocols, a set of nodes known as validators, that are identified by their public key, operates the consensus protocol such that any user can verify it using only publicly available information by verifying the validators’ signatures. The set of validators changes periodically, with respect to a specific governance mechanism.
However, as any consensus protocol that is not based on resource consumption (such as proof-of-work, proof-of-space and so on) they are vulnerable to an attack known in the literature as Long-Range Attack. In a Long-Range Attack, an adversary obtains the secret keys of past validators (e.g., by bribing them at no cost since they do not use these keys any more) and is thus able to re-write the entire history of the blockchain with those. A user that has been offline for a long period of time could then be fooled by the adversarial chain.
To solve this problem, we propose Winkle, a decentralised checkpointing mechanism operated by coin holders, whose keys are harder to compromise than validators’ as they are more numerous. By analogy, in Bitcoin, taking control of one-third of the total supply of money would require at least 889 keys, whereas only 4 mining pools control more than half of the hash power (see figure above).
Our Protocol
The idea of Winkle is that coin holders will checkpoint the honest chain, such that if an adversary creates an alternative chain, its chain will not be checkpointed (since the adversary does not control the keys of coin holders) and is thus easily differentiable from the honest chain.
Every time someone sends a transaction, it will contain a vote for a checkpoint. Every coin carries the vote of its sender (we call this the propagation rule). The vote is also associated with the remaining value in the account. For example, if an account A1 has 10 coins and sends 1 coin to an account A2 with a vote for checkpoint ckpt, then there is a system-wide vote with a weight of 10 for checkpoint ckpt: 9 of which is associated with A1 and 1 associated with A2. This also means that an account could have different votes for different coins held, e.g., if A2 received one coin from account A1 with a vote for ckpt and one coin from another account A3 that voted for a previous checkpoint ckpt′, then A2 carries one vote for ckpt and one vote for ckpt′. Whenever A2 sends a new vote, then all of the coins in the account will be counted towards that new vote, and the previous votes are over-written.
Whenever some fraction of the money has voted for a checkpoint, it is accepted. Because consensus based on BFT does not allow forks, users need not choose which block to vote on; this is implied by the consensus protocol. Only users who are offline for a long time may be fooled.
The difficulty of designing such a scheme comes from the fact that money changes hands constantly, by design. We thus need to make sure that checkpoints stay consistent even if the coin holders set changes entirely from one state of the database to another. We achieve this by relying on a realistic and flexible set of assumptions both on the fraction of accounts that are corrupted at any point in time and on the amount of money that is sent during one block.
To provide security guarantees even in the case of leakage of honest coin holders keys to the adversary, we additionally incorporate key rotations in our mechanism. This means that if keys are leaked to the adversary after users have carried out a key rotation, the scheme stays secure (this is also known as forward secrecy).
Lastly, our scheme is robust even when money is created and destroyed (as is the case with the proposed Libra stablecoins), and when the key used to mint and destroy money has been leaked to the adversary. This is achieved by requiring that every minting event takes effect only after the block containing it gets confirmed as a checkpoint.
Another challenge with this design is its high latency. It can indeed take a long time before enough coins vote. For example, if Winkle was implemented on top of Bitcoin or Ethereum, it would currently take up to three years for a checkpoint to be accepted.
See below some graphs for the finality time (the time it would take for a checkpoint to be accepted) in Ethereum and Bitcoin. For Ethereum a checkpoint takes between 50 days and up to a year to be confirmed (with mean 204 days), and for Bitcoin, a checkpoint takes between 4 months and up to three years to be confirmed (with mean 601 days). Note that this finality time is different than the time online users need to wait before their transaction is confirmed. It represents the time validators need to stay honest to ensure the security of the protocol even after key compromise. Under the assumptions that validators remain honest for longer than finality, then transactions are confirmed instantaneously as per the underlying consensus protocol.
To speed things up, we also propose a delegation scheme. Users can now delegate their stake to another user. Whenever the delegate votes, this vote will count with the weight of all of the coins that are under their control. This means that we do not need to wait for every user to vote in order to get a checkpoint accepted, as long as the idle users have delegated their stake to an active delegate.
Delegation can, however, be seen as adding more centralisation and thus making a long-range attack on coin-holders more likely since there would be fewer keys to compromise. To be sure that our delegation scheme is decentralised enough, while still providing good enough latency, we add on top of it a reward system, inspired by the one presented by Brunjes et al. that incentivises the creation of exactly k pools. This prevents having all the users delegating to the same delegates as long as they are rational. With such a delegation scheme, our simulators show that the finality time could be reduced to hours (instead of years).
Our paper, “Winkle: Foiling Long-Range Attacks in Proof-of-Stake Systems”, includes further details and proofs. This work will be presented at The Second ACM Advances in Financial Technologies (AFT’20) in October.
Perceptive to treat spendable UTXO as “stake”. Some feedback on the specific implementation:
> It can indeed take a long time before enough coins vote.
Most blockchains have the same UTXO circulating repeatedly, so this mechanism seems to only require attackers to control a small portion of UTXO in practice. This suggests you’d be better off modifying the Saito approach and deriving work from fees paid instead of money transferred. Add a mechanism to burn a portion of those fees, and you’ve imposed a cost-of-attack as attackers are forced to burn money proportional to the transaction fees they are required to fund on their stealth chain.
This should be better than just layering a POS mechanism atop another POS mechanism as you get genuine economic security — there is always a cost required for attack. How to implement some sort of cost-of-attack lottery in the mechanism is the real question though, especially if the lower-layer blockchain still makes the production of blocks free.