Analyse and improve Crosslink's security against combined eclipse / validator key compromise attacks

[daira]

Consider the following situation: the adversary has partitioned the network, and we are analysing $\mathsf{LOG} {\mathrm{fin}}$ agreement on a side of the partition where the attacker fully controls what honest messages are received and when. (This is not contradicted by the desired security assumptions for $\mathsf{LOG} {\mathsf{fin}}$ agreement.)

Suppose that an honest node is syncing from scratch. It has only the following information:

• A baked-in checkpoint that commits to the last agreed bc‑block (which implies a last-agreed bft‑block) and the validator public keys at some previous point in time.
• Its current local time.

We can make the following assumptions:

• The activation bc‑block of the last settled network upgrade is final at the baked-in checkpoint.
• There is a global clock such that no honest node's local clock ever differs from the global clock by more than $\Delta$.
• A newly started honest node $i$ will only expose $\mathsf{LOG}_ {\mathsf{fin},i}^t$ to its clients once it is "synced".

We can define honest node $i$ to be "synced" once its bc-best-chain $\mathsf{ch}_i^t$ is such that:

• $\mathsf{snapshot}(\mathsf{LF}(\mathsf{ch} i^t \lceil {\mathrm{bc}}^\sigma))$ extends the baked-in checkpoint's last agreed bc-block.
• The timestamp of $\mathsf{snapshot}(\mathsf{LF}(\mathsf{ch} i^t \lceil {\mathrm{bc}}^\sigma))$ is within some threshold of its current local time.

This is essentially zcashd's existing definition of "synced", with $\mathsf{snapshot}(\mathsf{LF}(\mathsf{ch} i^t \lceil {\mathrm{bc}}^\sigma))$ in place of the tip of the best valid block chain.

Since past validator private keys might be less well-protected than current keys, we might be concerned about the possibility that these keys could be compromised by an adversary. Therefore, it is necessary to be able to update the key for a given validator, and a practical proof-of-stake protocol will also need some way to update the validator set.

It is not strictly required for validators to have persistent public keys used to authenticate their cast votes; for example, each vote that a validator casts could be authenticated directly by a signature of knowledge that re-proves that validator's stake. But direct authentication using a "signature-of-stake" would not solve the issue of validators' past spending keys potentially being compromised. (In fact it could make it worse because the spending keys would need to be online.)

Vulnerability to past key compromise is not obviously inherent to proof-of-stake. Suppose that each validator periodically generates a new wallet, moves all of its stake into that wallet, and then updates its validator public key using a new proof of its stake. Then, we might hope that compromise of the old wallet keys would no longer grant authority to vote for proposals in subsequent epochs. However, given that a newly started node only knows the current time and a baked-in checkpoint, an adversary might be able to partition the node so that it cannot see the transactions that moved a given validator's stake, because they are after the checkpoint. (It is pointless to require the stake to be periodically moved by consensus, because in the fake history created by the adversary after they have compromised a validator's old wallet, they can transfer it to another address that they control.)

In order to take advantage of compromising past keys in this way, an adversary first partitions the target node $i$ from the rest of the network, such that it completely controls node $i$'s network view. (Without loss of generality we can consider the difficulty of attacking just one honest node. If the attack is successful, then that node can be convinced to vote with the adversary in future attacks — but if targetting even one honest node were infeasible, then it would not be easier overall to target multiple nodes using the same attack, since one must be convinced to accept the fake history first.)

For simplicity assume that node $i$ is not a validator. The adversary chooses some "divergence point" in the real network history after the baked-in checkpoint, such that the following additional conditions are met:

1. At the divergence point, the adversary controls keys that were valid after the checkpoint (i.e. both compromised and its own keys) for at least a two-thirds subset of voting units.
2. The adversary must have sufficient mining power that it is able to create a fake history, starting from the divergence point, with block timestamps that catch up to the current global clock (which is advancing during the attack).

Starting from the divergence point, the adversary creates a fake history in which bc-blocks are found as slowly as possible. That is, each block's timestamp differs from the previous block by the maximum allowed amount. (In Zcash's current protocol, each block's timestamp can be greater than the median timestamp of the preceding 11 blocks by at most 90 minutes, which means that the average timestamp gap over a long range of blocks can be at most 15 minutes.)

Choosing gaps between block timestamps that are as large as possible is advantageous for the adversary because:

• it minimizes the number of bc‑blocks the adversary needs to find in order for the last bc‑block's timestamp to reach a point that the target node will consider to be "synced";
• it causes the difficulty to decline at the maximum rate, which for Zcash's current difficulty adjustment is 24.24% (that is, $1 - \frac{1}{1 + \mathsf{MaxAdjustDown}}$) per bc‑block.

Note that this per-block decline in difficulty is large enough that the difficulty will drop to the minimum in a relatively small number of blocks. The sum to infinity of the geometric series $1 + r + r^2 + ...$ where $r = \frac{1}{1 + \mathsf{MaxAdjustDown}}$ is $4.125$, so the expected work that the adversary has to do before reaching the minimum difficulty is bounded by $4.125$ times the expected work to find a block at the initial difficulty.

The attacker can reduce the number of blocks it needs to find in the fake history by choosing a divergence point as late as possible, but this is subject to the constraint that it still controls two thirds of voting units at that point — i.e. none of the legitimate holders of units that it is depending on had by that point moved their stake away from the compromised spending keys and updated the corresponding validator keys.

In order to achieve liveness, the BFT protocol necessarily must be able to tolerate no proposal being made in a given BFT epoch. So, the adversary's simplest option would be to fake a history that has no proposals. However, that would not result in a violation of $\mathsf{LOG} {\mathrm{fin}}$ agreement. To obtain a valid attack against $\mathsf{LOG} {\mathrm{fin}}$ agreement, the adversary must satisfy the requirements for one of its proposals (that snapshots one of its blocks in the fake history) to become final. It cannot rely on any votes from honest nodes to help it in the attack, because an honest node will not vote until it has synced, and an honest node that has seen the real history will not vote for a proposal in the fake history. This is why the adversary needs to control two thirds of voting units for this attack.

Whether condition 2. is possible depends on the PoW protocol's difficulty adjustment algorithm and maximum allowed gap between block timestamps. Suppose, for the sake of argument, that there were no difficulty adjustment after the baked-in checkpoint, and no opportunity to manipulate block timestamps. Then for an adversary with less mining power than implied by the difficulty at the checkpoint, it would not be feasible to create a fake history fast enough to ever reach the timestamp needed for an honest node to consider that history to be "synced". (Note that the adversary's problem here is not to keep up with the rest of the network, but with the cumulative work that is expected at a real global time.)

If, on the other hand, the protocol did not put any constraint on the timestamp gap, then nothing would stop the adversary from creating a fake history with just the minimal number of bc‑blocks needed for one of the attacker's blocks to be confirmed (which is $2\sigma + 1$ according to the argument in Questions About Crosslink). Although this is not a plausible history of the real network (because real blocks would have been found much more quickly), that does not help unless honest nodes will actually reject it when syncing.

Enforcing a maximum timestamp gap is not sufficient by itself, because the difficulty in the fake history will decrease as long as the timestamp gaps are larger than the target block spacing. As calculated above, with Zcash's current difficulty adjustment, the adversary can quickly cause the difficulty to drop to the minimum and only pay for a few blocks of work at the initial difficulty.

Even if a significantly higher lower bound were put on the difficulty, in practice it would be very hard to prevent fake history attacks, although they could be made more expensive. Suppose for example that an adversary has a quarter of the network hash rate at the divergence point. As long as the difficulty adjustment allows the hash rate to fall to a quarter of some previous value (which is a plausible drop in real PoW hash rate), it is impossible to prevent such an adversary from being able to eventually create a fake history that catches up to the current global time.

The existence of this attack does not contradict previous safety analysis of $\mathsf{LOG} {\mathrm{fin}}$. In order to carry it out, an adversary needs to break explicit security assumptions for both $\Pi {\mathrm{bft}}$ and $\Pi {\mathrm{bc}}$. The observation I'm making is just that if we are intending to claim that Crosslink provides safety of $\mathsf{LOG} {\mathrm{fin}}$ even in an asynchronous setting, we should address known weak points in the design of $\Pi_ {\mathrm{bc}}$ in that setting, such as its potential vulnerability to eclipse attacks while syncing.

The following features would be helpful to increase the cost of this class of attacks:

• Allowing validator keys to be kept off-line.
• Creating an expectation that validators will periodically transfer their stake to a new wallet and then update their validation keys (using a new stake proof).
  • There is a trade-off here between the time that an adversary has available to compromise the current set of keys, and the need for validators to perform an operation that requires their long-term keys more frequently. Another possibility would be to use a forward-secure signature scheme for validator keys.
• Given the above expectation, baking more recent checkpoints into a node implementation increases the cost of an attack, insofar as it stops an adversary from gaining anything by compromising keys that were no longer valid at the checkpoint.
• Enforcing a maximum gap between bc‑block timestamps.
• Enforcing a minimum difficulty that is a significant fraction of the expected difficulty.

[daira]

@nathan-at-least points out that this video and research may be relevant: https://www.youtube.com/watch?v=-uxHoEfxXC4