FIP: Improving EC security with Consistent Broadcast

[guy-goren]

FIP: Improving EC security with Consistent Broadcast

Simple Summary

Modifies client behaviour (in particular the miners) to verify that the sender is not equivocating before accepting a block.

Abstract

Currently, a block is accepted if it is received before the cutoff time and is the first from its sender in the epoch. Blocks that are received after the cutoff time are ignored. This mechanism enables an attacker to exploit the cutoff in order to send equivocating blocks (i.e., different blocks in the same epoch, with the same "winning ticket") to different miners, causing miners to build upon different tipsets and, hence, damaging the progress of the honest chain.

This proposal suggests a simple fix to the above. A recipient waits a predefined time (e.g. 6 seconds) between receiving a block and accepting it. If, during this time, the recipient detects equivocation, it does not accept the block. By waiting, the recipient can be practically certain that a sender's equivocation will be suppressed since by this time (practically) all other miners would also hear of the block via gossip.

Change Motivation

A security analysis shows that, given the current "best effort" broadcast combined with the cutoff time, an attacker with $>20%$ of the power (storage) can break the security of Filecoin. The proposed improvement essentially replaces the best effort broadcast (beb) with a variant of consistent broadcast (cb). The difference is, in short, that beb broadcast allows two honest miners to deliver different blocks published by an equivocating Byzantine miner in the same epoch, which cb does not. The result will be that an attacker will require $>44%$ of the total power (adjusted storage) to successfully mount this particular attack.

Specification

The following pseudocode describes the consistent broadcast verification algorithm at a high level. Notice that the proposed change affects only the Filecoin miner as a receiver of a tipset; sending (and gossiping) a block remains unchanged. Delta is a tunable parameter which corresponds to the assumed upper bound on gossip delay (originating from an honest node). The protocol also uses block_set, a dictionary where a key is a tuple <round, winning_ticket> and a value is a set of blocks (for efficiency, blocks could be represented by their hashes).

Delta = 6 seconds                  # time for gossip to reach all
Upon receiving block B=<source, round, winning_ticket> do:
    propagate B acording to the gossip protocol;
    if B is valid:
        if not block_set[round, winning_ticket]:
            block_set[round, winning_ticket] = {};
        block_set[round, winning_ticket].add(B);    # can use hash of B
        if len(block_set[round, winning_ticket])>1:
            return                 # detected equivoqation
        wait Delta;                # wait the gossip time to ensure reach
        if len(block_set[round, winning_ticket])==1:
            return B

Garbage collection is handled orthogonally: block_set[round, winning_ticket] can be deleted after $k\ge1$ epochs (depending on how long you wish to allow block propagation -- currently $k=1$ in EC).

Design Rationale

The design goal is to introduce a simple change without severe repercussion to other functionalities of the systems. This means approaching the core of the matter (the mechanism that enable equivocation). This allows for orthogonal changes in the incentive design mechanism, since the change does not tie them together.

Potential strategies

The ConsensusLab team explored potential mitigation strategies and narrowed down the list for the following possible strategies: (for more details see this document)

• Removing tipsets from EC, effectivelly boiling down the protocol to a longest-chain instead of a longest-tipset protocol. By removing tipsets and having a traditional blockchain design (i.e., one block per epoch) the problem is mitigated.

  👍 Simple to implement -- changing the expected number of blocks from 5 to 1.

  👍 Easier to analyse theoretically -- trivially follows the existing literature on Proof-of-Stake blockchains.

  👎 Damages the expected settelment times in the simple case. I.e., it takes longer (more epochs) to achieve 99% settlement certainty against the simple block witholding attack.

  👎 The impact of a change would be substantial and very possibly negatively percieved by the community. Changing the number of blocks per epoch affects the miners economic calculations directly and is very visible to miners and the entire ecosystem. This is a very negative point about this option.

  👎 Requires a Filecoin upgrade. Might split the blockchain between adopting miners and not-yet adopting miners.

• Adding an asynchronous consistent broadcast layer. By adding a Consistent broadcast (C-BCast) the attacker can no longer equivocate. This solves the problem at its core.

  👍 Strikes at the core of the issue --- the equivocation of the attacker, by making a very targetted and specific consensus change.

  👍 Arguably easier to be accepted by miners. They feel no meaningful difference (same number of expected blocks, same payments, etc.), the change is behind the scenes only.

  👍 Does not depend on timing assumptions.

  👎 Requires a Filecoin upgrade. A miner that adopts the change cannot receive blocks from miners that didn't adopt the change.

• Adding a synchronous consistent BCast layer (with the 6 second magic number).

  👍 Strikes at the core of the issue --- the equivocation of the attacker, by making a very targetted and specific consensus change.

  👍 Arguably easier to be accepted by miners. They feel no meaningful difference (same number of expected blocks, same payments, etc.), the change is behind the scenes only.

  👍 Does not require a fork.

  👎 Depends on timing assumptions. That is, gossip propagation within 6 seconds.

---

The ConsensusLab research team recommends the use of synchronous consistent broadcast as the mitigation strategy (i.e., the last of the three proposed mitigations). The benefits of easy adoption due to only "behind the scence changes" and no Filecoin-upgrade required, outweigh the shortcomings (timing assumptions). Moreover, even if the timing assumptions are violated, the consistency degrades gracefully (that is, a slightly longer than expected gossip delay would lead to only a small amount of equivocating blocks being accepted rather than to a "cliff phenomenon" where all equivocating blocks are accepted). Also, using the synchronous approach does not require significant changes to the underlying broadcast protocol, which is already well tested and has built-in failure detecting mechnisms.

Backwards Compatibility

The proposal does not introduce backward compatibility issues. A miner that adopted the change will still accept blocks from honest non-adopting miners, and non-adopting miners will still accept blocks from adopting miners. The systems' security will improve monotonically with the share of adopting miners.

Test Cases

The following tests need to be done:

• Demonstrating the attack on the current system (with naive BCast)
  • We have the implementation of the basic attack (for each round independently).
  • No tests in testground were performed.
• Showing the same attack after the implementation of Consistent BCast
  • We have the implementation of an upgraded lotus client (incorporates consistent BCast).
  • We have the implementation of an attacking node (same as before).
  • No test in testground was performed.
• Showing the performance of the improved protocol in normal test cases
  • We have the implementation of an upgraded lotus client (incorporates consistent BCast).
  • Possibly run a few upgraded miners on mainnet for a while showing that they function correctly. This is possible since the fix does not break consensus.

Security Considerations

Replacing the naive best-effort broadcast with consistent broadcast improves considerably the security of Filecoin. There is the risk of using the synchronous approach which relies on timing assumptions (in cases of extreme network asynchrony, in which case the modified protocol would not be worse in terms in security than the current protocol). However, the benefits of the synchronous approach outweigh the risks.
Regarding liveness, we do not forsee problems due to the added delay prior to acceptance. This is because 1) assuming a worst-case propagation delay of 6 secondes, any cutoff$>12$ suffices, and 2) the additional 6 seconds waiting period does not require resources, so it may be used to precompute (e.g. winning PoSt) for the mining period.

Incentive Considerations

The proposal is intentionally decoupled from incentive considerations. It is neither dependent on them, nor does it limit changes to incentive mechanisms.

A question may arise: isn't equivocation slashable in Filecoin, and therfore should not concern us?
Equivocating is indeed slashable, however, there are 2 issues regarding slashing as a solution.
tl;dr: 1) conceptually, it is dangerous to rely on rationality that is based only on internal incentives. 2) Slashing/Blacklisting does not solve the problem.

1. Assuming rationality of the attacker implies that we know their incentives (typically assumed that those incentives are just to maximize their internal profits in Filecoin). In practice, we don't really know the attacker incentives. For example, since performing this attack would severely damage Filecoin's credibility, an attacker that "rationally" gains extra Filecoins from the attack might, actually, lose due to Filecoin's collapse. On the other hand, an attacker that externally benefits from a Filecoin collapse (e.g. short trading) might not care about the slashing. Thus, it is dangerous to rely on rationality that is based only on internal incentives.
2. Slashing/Blacklisting does not solve the problem. In Filecoin, an attacker can spread their power (storage) over multiple identities. For example, a 20% attacker can have as much as $3.6\times10^5$ different identities. Since these identities seem independent to all but the attacker, slashing will only affect the individual identity that equivocated at that epoch. Therefore, the attacker can sacrifice (w.h.p.) one identity per epoch. And even after attacking for ~1000 epochs the attacker will only sacrifice less than 0.03% of her resources.

Product Considerations

By mitigating attack on Filecoin, the proposal improves the resilience of the system. The proposal does not require any operational changes (besides adopting the protocol update) from the users.

Implementation

The prototype implementation lives in the following repo:

• Upgraded version of Lotus with consistent broadcast: Implementation of the synchronous consistent broadcast fix over Lotus.

Copyright

Copyright and related rights waived via CC0.

[ranchalp]

I think the approach of reducing the expected number of blocks from 5 to 1 means increasing the probability of having no blocks in a given epoch, significantly affecting performance (1 is in expectation). I suggest adding this con to that approach.

Also, the hackmd link should be publicly available or not linked in this proposal?

Has the security of the traditional approach (and the new synchronous patch) been analysed in terms of different finalisation blockdepths?

[guy-goren]

There is still no tight analysis regarding the safety of EC with the patch (although we do not currently know of a significant attack with less than 40%). Hence, no tight finalization is claimed precisely. However, we can show that the the security of EC with the patch is no less than before, and in the specific case of the shown weakness (the n-split attack), the patch mitigates the attack significantly.

[anorth]

Thanks for the proposal!

I note that the mitigation path of removing tipsets is more complex than merely changing the expected number of blocks from 5 to 1. While a single secret leader election would bring many benefits, my understanding is that it's a somewhat open problem. But happily your recommended mitigation is much simpler.

[DecentCr8]

Not fully understand what's the difference than just simply extending the cutoff time to 12s (6+6) timeline.
Or, this is a must step to remove tipsets from EC? but, it's hard to understand while this document is not accessible.

[guy-goren]

1. Just doubling the cutoff time to 12s will not do the trick. A malicious participant can simply send the equivocating blocks later. The main point is that once you received a block you continue gossiping it, thus, after 6 seconds you're confident that everyone have also gotten it.
2. Regarding tipsets, this FIP does not suggest to remove them. Removing tipsets was another possibility that we explored, but due to the strong side effects it would incur we are not recommending it.
3. Thanks for raising the accessibility problem. It should be visible now.

[steven004]

@guy-goren , as mentioned, a storage provider is free to take or not take this approach. That is, this is not a protocol change, but in implementation. Then, the question is why a rational storage provider is willing to adopt it.

Let's say there are two storage providers P1 and P2. P1 takes this approach with cutoff time at the 6th second and setting delta=6s, and P2 does not adopt it but set the cutoff time to the 12s. Remember the two storage providers will start the election proof calculation and do wPoSt after 12s in an epoch since 6+6=12.
In epoch n, both P1 and P2 received 3 blocks (A, B, and C) with the same parent, while A and B arrived at the 2nd and 4th second in the current epoch, but C arrived at the 8th second. Let's assume both P1 and P2 has the right to generate a block at this round. Thus, C will be invalid for P1 but valid for P2.
The result will be: P1 takes A&B as parent and P2 will take A, B and C. There is a fork, and in next round, P2 wins since it's heavier.

It looks it's more beneficial when not adopting it as a rational storage provider. Is there anything wrong here?

[guy-goren]

It is also not rational for a miner to impose upon itself a cutoff time (same example you gave when the cutoff is 6). However, we also consider "honest" behavior, that is, behaving according to the suggested protocol (in our case adding the consistent broadcast guarantee). This is if the miner is interested in the well being of the entire system (and believes that others do so as well). I agree that it's better if we could mitigate byzantine behavior with a protocol in which "rationality" of the majority is enough (and no "honesty" is required). But, unfortunately, we do not have one (unless you make some weird assumptions about what is rational, in which case you entangle "honesty" with "rationality").

Now consider also what happens if most miners adopt the change (which is why we suggest to push it as more than a mere recommendation). Instead of only P1 and P2 we add P3, P4, and P5. Suppose that the others adopt the proposal (similarly to P1), now the heavier tipset (in the next round/epoch) excludes P2's block because it is inconsistent with the rest (the "honest" miners). Thus, in the long term, it might not be profitable to resist the honest majority.
For the short term, though, that is a valid point. In fact the headstart attack on FIlecoin that does something similar. But it does not pose a significant threat since it cannot be sustained long enough to cause a severe damage.

@steven004 My apologies for not being more concise (my reply is quite wordy). Please let me know if I haven't been clear.

[steven004]

Another piece of information, which may not be accurate.
In the current Filecoin network, most medium and large storage providers customized the code for algorithm optimization and block generation. As far as I know, many of them (>50% I think) have their own cutoff setting. Depending on their network and computing power, it could be at the 15th or 20th second, or even close to the epoch bound.

[steven004]

With different cutoff time and delta setting, honest (or rational) storage providers will be hard to achieve a consensus in the case above. The storage provider with cutoff time at 6s + delta 6s will not take block C, but another storage provider with cutoff setting at 9s will take it. It will be good if all honest storage providers have the same setting, but I am not sure if it really works.

[steven004]

I'm just expressing my concerns here. Back to the proposal itself, I have no objection. It does no harm, and if it is a step toward a big goal, it might be worth a shot.