forking attack on current weighting function

[whyrusleeping]

Currently, our weighting function looks like Y + (X * winnersPowerRatio).

If an attacker forks off onto their own chain, and mines blocks on it until they can slash out the other miners (who are active on the main chain still) then they can get effectively 100% of the power in their chain, and can grow the weight of the chain much faster than the main chain can.

Essentially, with the current weighting function, the more decentralized the network power is, the more slowly the weight grows.

One potential solution is to have total power explicitly included in this function, but the remaining question there is whether or not we need the 'tiebreaker' or not.

[whyrusleeping]

cc @jbenet, would love your input here.

[jbenet]

and can grow the weight of the chain much faster than the main chain can.

how do they grow the weight of the chain much faster? (some possibilities come to mind, but can you explain what you're thinking a bit more concretely?)

[whyrusleeping]

@jbenet given that the current 'delta weight' function at each block is roughly 1 + minerPowerFraction, if a miner were to become 100% of the power in a fork, they could mine at every round, and increase the weight by 2, where back on the main chain, each miner would increase the weight by less than 2 (because they each have less than 100% of the power).

[jbenet]

@whyrusleeping thanks

notes:

• should just straight disallow any miner having more than 1/2 of the power-- it's a security break.
  • arguably, we could have arbitrary caps-- single miner identities shouldn't have over 1/x. (yes, sybills)
• 2 sybills (each with 1/2-e) dont grow as fast, but still faster than more distributed case.
• what we're failing to account here is the actual storage power involved. we lost that along the way in refactoring this function. The weight of the chain must incorporate that.

For example (Y + (X * winnersPowerRatio)) * totalStorage (totalStorage wherever the other properties are sampled from-- ie lookback param). I'll think about why we didn't just do this-- there may be a bug with that too. Either way-- the actual storage power needs to factor into the best tipset rule.

[whyrusleeping]

@jbenet Yeah, one thing i'm thinking about is adding log(totalPower) to the end of that power delta.

A practical concern is that the weight could end up being a big number...

[jbenet]

one thing i'm thinking about is adding log(totalPower) to the end of that power delta.

Something like that should work.

Simulations @sternhenri and @ZenGround0 made might help

A practical concern is that the weight could end up being a big number...

There are ways to map functions to avoid that. (yeah log is a good way to do that)

[sternhenri]

@jbenet agreed. Am gonna work on that. The nice thing this affords us is that we can now use the same weighting function for network joining and general chain selection as a regular part of mining (see https://github.com/filecoin-project/specs/issues/106 which we can simplify)...

My orthogonal q now is simply whether the tie-break (based on miner portion of power) is really necessary. It seems to me that the chances of a long-running fork in which it comes into play are really low (need to sim) given the rule that members of a tipset have the same parents...

[ZenGround0]

My orthogonal q now is simply whether the tie-break (based on miner portion of power) is really necessary.

Even if we want a tie break using miner power seems unnecessary. Why not use some combo of chain randomness and id? Or just the log(Power) term? I don't know a compelling reason for using miner power as the tie break entropy. If we use some other tie breaker then the miner who becomes 100% by mining alone won't have any mining edge in the long run, which it needs to make up for all the null blocks it mined during the initial proving period of the attack when other miners still have power in the attacker fork.

For example (Y + (X * winnersPowerRatio)) * totalStorage (totalStorage wherever the other properties are sampled from-- ie lookback param). I'll think about why we didn't just do this-

• From @nicola in research week in December: could this disincentivize slashing if we're not careful? If two forks are competing and your funds are tied up on one fork maybe you are more likely to not slash a misbehaving miner on your own fork.

• Something @sternhenri and I have talked about before is another attack that choosing chains based on power opens up. If the blockchain typically does not add that much power then an attacker may be able to add enough storage power on a private fork to counteract the missing weight from null blocks and get a reorg.

• My suspicion is both the above can be mitigated more or less with careful parameter selection: slashing period to finality ratio, X / Y , lookback parameter for sampling IDs, etc

[sternhenri]

A few thoughts here:

• I think we should remove the tie-breaker until it is sufficiently motivated for the team. Complexity "just in case" is an attack vector. To your points @ZenGround0
• WRT to what form a tie-breaker should take, I think log(power) is not effective as it depends on power table sampling and other things but given all blocks in a tipset have the same parents, it is likely not to suffice for short-range attacks. Then again, the tie-breaker may be for long range forks, but then I just think it unlikely to actually be needed in practice. (insert math here)
• Your second bullet describes a 51% attack. We shouldn't try to safeguard against that. If an attacker can overtake the chain by adding more storage than all other miners combined, then hers is the real chain.
• Re slashing, I think collateral can help take care of this. With that said, there is a question of what happens if a whale gets slashed (say 20-30% of your chain's power)... I reckon there is a bit of a prisoner's dilemma in that if you know a single honest miner will do it, you're better off doing it instead as a rational miner... But worth running the math on.

[ZenGround0]

Your second bullet describes a 51% attack. We shouldn't try to safeguard against that. If an attacker can overtake the chain by adding more storage than all other miners combined, then hers is the real chain.

I see where you're coming from as my description was brief but I had something else in mind than your interpretation. I am imagining the attacker maintains the power of other miners on the private chain by replaying their PoSts, or making a small enough private chain that power loss is small. Then the attacker doesn't need to have 51% of total storage, it just needs to add more storage in the private fork than other miners add to the main chain. Depending on the rate of storage added to the main chain this could be low enough that a reorg is feasible.

This attack is kind of "dual" to the one described in this issue in that it relies on the ability to maintain other miners' power in a fork as opposed to the ability to remove other miners' power in a fork.

[sternhenri]

Thanks for expliciting that. The attack is really interesting indeed. @whyrusleeping was talking about limiting storage you could add in a given period (to a % of total power) so it could only become feasible to do this once the network is large enough (that the %age isn't met by the "honest" chain) which would make this costly. But it's a crappy defense.

I do wonder if this is really an attack though: you could argue that any "chain switch" is the result of a miner running this attack... When it's sort of just a feature of how weight works...

Could this be the SPC version of selfish mining @whyrusleeping? I do think null blocks will prevent this from working too long though: the rest of the network will win more often than I do on my side chain, so the real chain will end up heavier...

It deserves to be sim'd so we can see how long you could keep this running rationally...

[whyrusleeping]

To restate the attack i think we're talking about clearly:

At some point, a large miner is about to be slashed. Seeing this, an attacker forks the block before that slash lands. The intuition here being that in their fork, the total power is higher, so the weight addition is higher at each new block. However, that won't be the case, as the attacker will mine much much slower than the main chain due to null blocks.

I am imagining the attacker maintains the power of other miners on the private chain by replaying their PoSts

Not possible, PoSts are tied to a particular chain. This could only be done up to some small period of time (the grace period of the PoSt submission).

Now, the question of 'will this disincentivize slashing' ? I think that the expected increase in future block reward for slashing someone should be sufficient. In addition, since a miner who has not submitted their PoSts cannot create a block (their blocks are invalid) a chain that does not slash miners will grow more slowly.

[sternhenri]

On the PoSTs tied to a chain, this is actually one where the lbp hurts us. But again, I don't see this as a real threat vector either for a long-lived attack.

[sternhenri]

Tracking in https://github.com/filecoin-project/specs/pull/134.

I recommend we merge this in and leave open the question of whether the tie-breaker is necessary @whyrusleeping