[Consensus Attack] Posterior Corruption

[sternhenri]

This is a write up from a conversation with @sa8 and @ZenGround0 regarding Posterior Corruption and its feasibility on both EC and an SPC protocol.

Conclusion I believe that VDF use and Storage-Power based consensus independently provide adequate defenses against posterior corruption in Filecoin.

Background For a quick reminder, posterior corruption attacks (aka long-range attacks) has an attacker corrupt keys after the fact to rewrite history over an extended period, for instance by purchasing a majority of network power from (formerly) honest participants who have cashed out of the currency a long time ago, and then using that acquired power to rewrite history moving forward and eventually releasing a longer (or heavier) chain rewritten from the time of attack onward. It's one of the major issues with PoS. Typical defenses are checkpointing or key-evolving cryptography.

In EC EC as used in Filecoin has two features that impact the feasibility of running a posterior corruption attack on it:

• a: Its use of VDFs as part of block generation (or more precisely ticket generation) -- argument could be made for Fantomette or others.
• b: Its use of VRFs as part of ticket generation -- true of many protocols
• c: The fact that stake/power is based on a hard-resource, in our case storage -- argument could be made for Chia or others.

The attack context is as follows: attacker A acquires C>50% of power expressed at round X (ie in power table at round X-L) and proceeds to rewrite history. We take K to be the randomness lookback, L to be the power table lookback (at which stake/power is sampled) and Y to be the number of rounds between every PoST.

The attacker has full power over the contents of the blocks produced by corrupted miners (whose keys were purchased). For those, A can simply generate new tickets and new block signatures. However, this is not so for non-corrupted blocks.

Given that each block depends on the blocks before it, by changing any content in corrupted blocks, the attacker will change the chain's structure altogether: by changing block content for corrupted keys, the attacker will render honest blocks invalid (since A is unable to republish them with an updated pointers to corrupted prior blocks, see b), thereby yielding different TipSets (or no TipSets) at "honest" rounds, and changing the ticket chain within K blocks of the first round within which the smallest ticket was honest.

Thereafter, the attacker will be mining with C% of power, adding C% of its expect weight at each round. Given our use of VDFs (see a), this chain is unlikely to overtake the honest one.

We see that VDF use (or a hard block delay) forces the attacker to mine blocks at the same rate as the honest chain, thereby making any overtake of the network (given partial ownership of total stake) unlikely.

You could picture the attacker purchasing 100% of power from rounds X to X+K (that is the keys in the power table from X-L to X-L+K), thereby making sure A has full controller over all future tickets. In that case however A is constrained to only mining with those keys, which assuming power in the network (ie storage) increases over time would yield a lighter chain (thanks to our VDF use again a).

Now, let's introduce c into our thinking. Filecoin relies on storage-based power after all.

We start by noting that this means it is possible for total "stake" or power to drop in the network (i.e. storage goes offline) in Filecoin while it is not in traditional PoS. Assuming power drops in the network (ie total storage drops), A could run a successful attack in spite of the VDF, given our current weight function which includes a function of total power in the chain: the miner would have to select X to be peak power, and then use that to mine heavier average blocks than are currently being mined by the honest network, eventually overtaking it. The network is designed to incent power growth, but it's an interesting thought.

On the flip-side, storage-backed stake is extremely beneficial: Firstly, power is initially tied to a chain (through SEALing), so at the point that A purchases stake, this stake is tied to the given chain and cannot just be applied to an existing fork. Secondly, the corrupted power will disappear within Y rounds: in order to maintain corrupted power, the attacker actually has to keep producing PoSTs every Y rounds, lest that power get slashed. In that sense, the price of a successful attack is not just the price of corruption, but the price of maintaining that power by running storage. Thus, it is clearly far more beneficial to behave honestly (and not incur the price of corruption) here. We should also be safe from short-term variants of this attack (where the attacker attempts to corrupt keys from the near past) so long as L == Y (so the power table reflects safe power) and miners cannot redeem their FIL for at least L blocks after leaving the power table (i.e. they should not be able to sell their keys while their power is reflected on the table).

Edit : the above point is dubious. L should be equal to proving period... a bit of lag doesn't matter but making it smaller doesn't help much (could get lucky)

[sternhenri]

@ZenGround0 @sa8 does this reflect our convo? Anything to add?

[sternhenri]

Purchasing all power from round n to n + k, you would stop being able to run the attack after some time since the ticket chain would change (PoSTs would no longer be replayable).

In the case of purchasing 100% of power in the network at a given time, the real mitigation really is weight function (and assumption that chain total power grows).

• There is an arg that since PoST randomness is sampled from the chain, they should not be fully reusable (nice spot Red), but...
  • To prevent grinding I assume they would only depend on tickets themselves, therefore if you own 100% of the power, you could swap out the txs and keep the tickets.
  • so this is not a valid defense (however it does preclude 99% purchases from being successful in the limit)

This is a weaker case for Posterior corruption resistance without VDFs than previously thought. But this attack assumes 100% of keys get sold (ie 0 honest miners), in which case the attack depends on total power on the chain not growing.

[sternhenri]

I'll add that outside of PoST replays, I ignore any sort of timing based attacks based on disk reuse: eg. slow down the clock (which you can owning all the power, or 51% even) and generate proofs using the same disk over and over (or some dishonest amount of disk): this strategic set of disk I/Os would likely slow down consensus meaning you don't catch up to real chain...

[sternhenri]

cc @whyrusleeping @bvohaska @nicola @mhammersley @lucaniz @porcuquine on the dependencies for some of this on how PoST randomness is sampled.

[bvohaska]

@sternhenri: great write-up! I have a few questions,

From the Background section could you add,

• definition of keys
• definition of key-evolving cryptography

Rephrasing the attack a little bit, can you tell me if the following statements are true:

Assuming,

1. A computational bound C which is representation of an adversary's computational ability
2. Beginning at block height h which is m blocks behind the current block height
3. The adversary is able to obtain greater stake in the present which is only valid in the past
   • The adversary convinces a miner to transfer power/stake for some block h_i which is at least k blocks in the past
   • This deal would not be valid if posted to the blockchain and is only valid if an adversary is able to rewrite the history of the blockchain

An adversary should not be able to generate m blocks b_prime such that

1. Miners are convinced that b_prime are valid
2. For some time t_success, if the adversary has generated b_prime and has caught up to the current block height, then the adversary is not bounded by PPT or t_success > f_time(lambda). For some security parameter lambda
3. If (1) and (2) hold then an adversary should gain negligible advantage over an honest miner in claiming rewards for future blocks

With less formal wording, an attacker shouldn't be able to obtain stake or power by making deals in the present for blocks in the past, start generating new blocks that are in the past but include this acquired power, be able to catch up t the current block height, and convince miners that this new chain is valid.

With this reasoning, attack quantification can be represented by quantifying,

• (Computational Bound) Given a VDF, how much computational resources would an adversary need to perform this attack
• (Economic Bound) Given this advantage, how much return on investment could an adversary get by performing this attack

[sternhenri]

I expect what you are saying is true, but I have a hard time understanding proposition 2, so I may be missing something.

With regards to the quantification, I think it also depends on the chain state's evolution itself.

[bvohaska]

Proposition 2 bounds the attack to an adversary who (1) can only compute in BPP and (2) can only perform a certain number of calculations bounded in time by f_time(lambda).

[sternhenri]

Noted! THanks for explaining, then yes I am on the same page as you!