WIP: Add two tests for weak subjectivity periods

[asn-d6]

Hello,

this is an attempt at writing unittests for the weak subjectivity code.

@adiasg Please let me know what you think!

Also, the second test test_is_within_weak_subjectivity_period() is not very sophisticated and it's probably also a bit tautological since it basically uses a big part of the function that it tests.

Based on our discussion yesterday, we could write a test which emulates the attacker's optimal strategy and verifies that it will indeed complete at exactly WS period steps. Such a test is more complicated but I can def work towards it if you think it's useful (and doable). Below, I describe the general algorithm for such a test, and I also have a few unknowns marked in brackets.

Start with a chain (at block #0), called `legit_chain` with 1024 validators (with average balance 16 ETH)
[How many of those validators should be attacker controlled?]
Cache the result of `compute_weak_subjectivity_period()` to 'ws_period'.
Copy the chain to `evil_chain`

Now start advancing blocks in both `legit_chain` and `evil_chain`. For each new block, perform the
attacker's optimal strategy:
   - In 'evil_chain', attacker activates max validators
   - In 'evil_chain', attacker tops up validators to 32 ETH
   - In 'legit_chain', attacker exits max attacker-controlled validators

After we finish adding a new block, we check the following things:
- If attacker-controlled balance is 2/3 of the total balance in `evil_chain` (this means that attacker can finalize blocks)
- If the intersection of validators between the two chains is `< 1/3 - D` of the total 
  validator set in `legit_chain` (this means that CASPER safety margin has been violated)

If these two conditions are true, we save the current epoch as `attack_now_epoch`.
We then assert that `attack_now_epoch` is equal to `ws_period` and end the test.

Does the above make sense and do you think it's a useful thing to do as part of these tests? Can you make it more useful? Do you think it's too much of a hassle for not enough reward?

Also two other more minor questions:

• I put the tests in test_finality.py for now, but maybe I should make a new file?
• Is test_weak_subjectivity_period_formula() too expensive? From a quick skim, I didn't find another test adding "so many" validators.

Cheers!

[hwwhww]

I put the tests in test_finality.py for now, but maybe I should make a new file?

Yep! If it doesn't output any test vectors for client teams, it should be under tests/core/pyspec/eth2spec/test/phase0/unittests/ folder.

Maybe add tests/core/pyspec/eth2spec/test/phase0/unittests/weak_subjectivity/test_weak_subjectivity.py?

p.s. some notes to explain the folder system: https://notes.ethereum.org/@hww/pyspec-tests :)

[adiasg]

I think it's useful to have actual WS attack scenario tests to sanity check the calculations.

For simplicity, it's easier to let the attacker control all the validators at a specific time, and generate two conflicting finalized chains in the least possible time with less than 1/3 - SAFETY_DECAY/100 fraction slashable.

The optimal attack strategy is as follows (refer section 2.3 from The Report):

The initial validator set is E_R + P_L + Q + P_R + E_L. In the end, there are two conflicting finalized chains chain_L and chain_R. The final validator set in chain_L is A_L + E_R + P_L + Q (and symmetrically for chain_R), where:

• A_L new validators have activated in chain_L
• E_R validators have exited from chain_R
• P_L validators have topped up to MAX_EFFECTIVE_BALANCE in chain_L.

A_L and E_R are of the maximum possible size allowed by the activation and exit queues. P_L is calculated on page 9 of The Report.

So, the strategy becomes:

For each new block, perform the attacker's optimal strategy:
   - In 'chain_L', attacker activates max possible validators
   - In 'chain_R', attacker activates max possible validators
   - In 'chain_L', attacker exits max possible validators, denoted by `e_L`
   - In 'chain_R', attacker exits max possible validators (none of which are from `e_L`)
   - In 'chain_L', attacker tops up *some* validators to 32 ETH, denoted by `p_L`
   - In 'chain_L', attacker tops up *some* validators to 32 ETH (none of which are from `p_L`)

Note that the WS checkpoint system is supposed to preserve the crypto-economic finality guarantee: two conflicting checkpoints means that a certain fraction of validators will be slashed. ws_period calculates the number of epochs required to execute this attack and withdraw the slashed validators' deposits. Hence, attack_now_epoch - start_epoch is going to be ws_period - MIN_VALIDATOR_WITHDRAWABILITY_DELAY. So, the test termination condition becomes:

If these two conditions are true, we save the current epoch as `attack_now_epoch`.
We then assert that `attack_now_epoch - start_epoch` is equal to `ws_period - MIN_VALIDATOR_WITHDRAWABILITY_DELAY`.

[djrtwo]

I would suggest we get the low-hanging fruit done in this PR, and then consider the deeper scenario testing in a followup.

1. these codepaths aren't tested at all yet
2. @asn-d6 is on his first spec testing journey so just getting the initial codepaths tested will be valuable and provide insight on how to do deeper testing

I can do a pass on this on Monday to provide some more input on a minimal pass

[adiasg]

@djrtwo @asn-d6 In that case, what do you think about converting the tests currently implemented in this PR to output client test vectors as well? The intention is to check that clients correctly calculate the WS period.

For example, in test_weak_subjectivity_period_formula, we output the state and check that the client also computes the same value for the WS period for the given state.

[djrtwo]

That seems reasonable!