Early Conf Time Sims

[sternhenri]

BLUF: for devnet purposes and related to preventing any DoSing from malicious nodes claiming to have fake blocks very far ahead (e.g.), we can conservatively take a lookback of 600 rounds.

This gives an attacker with 40% less than a .2% chance of successfully mining a double block by selfish mining.

For the sake of comparison, with a 30 sec block time, that's a 5 hour finality for FIL. For reference, the same level of security (ie chance of success for this attacker power) would take around 80 blocks in bitcoin, or a bit over 13 hours.

Key numbers are here.

Spun another way, the equivalent security to Bitcoin's 6 block confirmation (.1% chance with a 10% attacker, which is very insecure) would take around 30 blocks in FIL, or around 15 minutes.

For a 49% attacker, we suggest increasing to 5,000 blocks.

How we get these numbers

Short answer is from this sim.

It is worth mentioning that we are also working on a different methodology to confirm these results, though it currently has some issues we need to resolve.

The general Idea

@sa8 and I ran some simulations. I'll quickly run through methodology here. Happy to discuss more.

In general the idea is to model EC as a binomial draw. We do this in 1,000 sims. For each we look for an attack in which an adversarial miner with some power q tries to launch a selfish mining attack and run it as long as possible (thereby pushing finality to be as slow as possible --> the longer the potential attack, the farther back an honest party has to look to ensure that an attack isn't currently being run and their block may be part of the honest chain that will be overwritten).

For each of the sims, we look at how long the attack is and then we take the 1,000 as a way of determining how likely an attacker is to succeed in attacking the protocol for a given confirmation time of k.

For instance, if we set k=50, we would look for how many of our 1,000 runs had attacks that ran longer than 50 rounds. Say, 600 of those were longer, we would say that the likelihood of attacking it is 60%...

Some Caveats

• This is nonetheless a monte-carlo sim and not an analytical solution. We notice for instance that far enough back (eg a lookback of 5,000) a 52% attacker's chance of winning decreases. Analytically we know this to be impossible: a 52% attacker will always eventually win. This is a limitation of the sim.
• [Insider ball, a lot to unpack here] We are getting a strange result (insider ball) whereby comparing EC, EC without tipsets (longest chain variant), and EC without the headstart attack we have \nchance of success(EC_noHS) < CoS(EC) < CoS(EC_noTS)\n whereas we would expect to have\n CoS(EC_noHS) < CoS(EC_noTS) < CoS(EC)\n given the power of the headstart attack.
• Finally, this sim really only looks at selfish mining/block withholding as a threat and not other threat models or even potential conflicts between honest chains, so it is incomplete but I believe it covers the most pernicious attack against EC convergence.

For that reason, tread carefully with this sim.

Now some numbers

In all cases we look at the EC numbers (rather than without tipsets or without headstart).

Iteration 1: Simulating success by looking at the first attack in any block

Numbers from first attack - 2,000 rounds, 1,000 sims per q, lookahead = 0

This is the original sim, per this commit. It stops the sim as soon as the attacker has successfully run a single attack.

We see that 52% attackers begin to fail very quickly: by 35 blocks they are in the low double digit wins. Again, we know that in the limit, they will always win so this is a clear drawback of our method.

Iteration 2: Have the attacker run as many attacks as possible stopping only at the end of the sim.

Rather than take the length of the first attack for our benchmarking, we take the longest possible attack from the run.

Numbers from best attack sim - 5,000 rounds, 1,000 sims per q, lookahead = 0

This looks much better. At 95 blocks, a 48% attacker still succeeds 100% of the time.

Looking into the detail here at deeper block lengths, we see that to make a 40% attacker largely unsuccessful we would want to go back at least 375 rounds (I round up to 600 to be conservative). We can also see that foiling a 49% attacker is likely to take on the order of 5,000 blocks, or close to 2 days.

Though I am reluctant to take the sim at this length too faithfully (even the 52% attacker degrades here, we would need to run a much longer sim to get better data).

Iteration 3: the issue of our lookback parameter in EC.

As we know the lookback effectively acts as a look-ahead, potentially enabling the attacker to check ahead before ending their attack in case they will come back on top in the short term future.

We simulate the above with a look-ahead of 10 rounds and as expected this helps the attacker perform better (eg a 30% attacker wins 12% of the time 65 blocks back with the lookahead vs 5% without). We expect the attacker advantage grows with a higher look-ahead, but this last parameter should help us get a good estimate as we fiddle with the lbp in EC.

[sternhenri]

cc @whyrusleeping @nicola @ZenGround0 @anorth

[sternhenri]

Feel free to review the code (plz). You can ignore the second and third runs: they are useful to me but not you :b. Only the EC results matter for our purposes at this time.

[sternhenri]

Additional runs including quality. Some of the quality data doesn't compute just yet:

• Run 1
• Run 2
• Run 3
• Run 4

[sternhenri]

Additionally working through cranking up throughput (per your idea @jbenet): some results seem to point that convergence improves with increased throughput (where expectation > 1) and quality degrades. Both make sense to me. Ordering of options: EC <~ ECnoTS << ECnoHS remains the same.

• EC w e = 2
• EC w e = 3
• EC w e = 5
• EC w e = 10

[sternhenri]

And with lookbacks:

• EC w lb = 10
• EC w lb = 20
• EC w lb = 50
• EC w lb = 100

[sternhenri]

Reopening for @ZenGround0's sake. Will let him close if he is convinced by this as an arg for keeping TipSets in EC.

[sternhenri]

Adding results modeled from Markov Chain (ie closed form model):

• 1000m, without headstart
• 1000m, with headstart
• 100m, wo hs
• 10m, wo hs

[sternhenri]

• with wt fn

[sternhenri]

and with some json in there (in use by the conf time observable):

• no weighting fn, no lookback
• no weighting fn, 10 block lookback
• weighting fn, no lookback
• weighting fn, 10 block lookback

[sternhenri]

Note that the addition of this line https://github.com/filecoin-project/consensus/commit/7677cd32fa30342c0e2a60efc3f81dff178e4b4f#diff-18f5cc8bc445fdd420dd40ec0d521f2dR271 on June 27 changed quality meaningfully (made it far worse).

[sternhenri]

closed in favor of https://github.com/filecoin-project/consensus/issues/75